The continuity of biased random walk's spectral radius on free product graphs

He Song; Longmin Wang; Kainan Xiang; Qingpei Zang; He Song; Longmin Wang; Kainan Xiang; Qingpei Zang

doi:10.3934/math.2024952

AIMS Mathematics

2024, Volume 9, Issue 7: 19529-19545. doi: 10.3934/math.2024952

Previous Article Next Article

Research article

The continuity of biased random walk's spectral radius on free product graphs

1.
School of Mathematics and Statistics, Huaiyin Normal University Huai'an 223300, China
2.
School of Statistics and Data Science, Nankai University Tianjin 300071, China
3.
School of Mathematics and Computational Science, Xiangtan University Xiangtan City 210000, Hunan Province, China

Received: 28 January 2024 Revised: 15 May 2024 Accepted: 21 May 2024 Published: 13 June 2024
MSC : Primary 60J10, 60G50, 05C81, Secondary 60C05, 05C63, 05C80

R. Lyons, R. Pemantle and Y. Peres (Ann. Probab. 24 (4), 1996, 1993–2006) conjectured that for a Cayley graph $ G $ with a growth rate $ \mathrm{gr}(G) > 1 $, the speed of a biased random walk exists and is positive for the biased parameter $ \lambda \in (1, \mathrm{gr}(G)) $. And Gábor Pete (Probability and geometry on groups, Chaper 9, 2024) sheds light on the intricate relationship between the spectral radius of the graph and the speed of the biased random walk. Here, we focus on an example of a Cayley graph, a free product of complete graphs. In this paper, we establish the continuity of the spectral radius of biased random walks with respect to the bias parameter in this class of Cayley graphs. Our method relies on the Kesten-Cheeger-Dodziuk-Mohar theorem and the analysis of generating functions.
- biased random walk,
- spectral radius,
- continuous,
- Cayley graph,
- free product
Citation: He Song, Longmin Wang, Kainan Xiang, Qingpei Zang. The continuity of biased random walk's spectral radius on free product graphs[J]. AIMS Mathematics, 2024, 9(7): 19529-19545. doi: 10.3934/math.2024952

Related Papers:

Abstract

R. Lyons, R. Pemantle and Y. Peres (Ann. Probab. 24 (4), 1996, 1993–2006) conjectured that for a Cayley graph $ G $ with a growth rate $ \mathrm{gr}(G) > 1 $, the speed of a biased random walk exists and is positive for the biased parameter $ \lambda \in (1, \mathrm{gr}(G)) $. And Gábor Pete (Probability and geometry on groups, Chaper 9, 2024) sheds light on the intricate relationship between the spectral radius of the graph and the speed of the biased random walk. Here, we focus on an example of a Cayley graph, a free product of complete graphs. In this paper, we establish the continuity of the spectral radius of biased random walks with respect to the bias parameter in this class of Cayley graphs. Our method relies on the Kesten-Cheeger-Dodziuk-Mohar theorem and the analysis of generating functions.

References

[1]	E. Aïdékon, Monotonicity for $\lambda\leq \frac{1}{2}$, 2013. Available from: http://www.proba.jussieu.fr/dw/lib/exe/fetch.php?media = users: aidekon: noteaidekon.pdf
[2]	E. Aïdékon, Speed of the biased random walk on a Galton-Watson tree, Probab. Theory Relat. Fields., 159 (2014), 597–617. http://dx.doi.org/10.1007/s00440-013-0515-y doi: 10.1007/s00440-013-0515-y
[3]	G. B. Arous, Y. Y. Hu, S. Olla, O. Zeitouni, Einstein relation for biased random walk on Galton-Watson trees, Ann. Inst. H. Poincaré Probab. Statist., 49 (2013), 698–721. https://dx.doi.org/10.1214/12-AIHP486 doi: 10.1214/12-AIHP486
[4]	G. B. Arous, A. Fribergh, V. Sidoravicius, Lyons-Pemantle-Peres monotonicity problem for high biases, Commun. Pur. Appl. Math., 67 (2014), 519–530. http://dx.doi.org/10.1002/cpa.21505 doi: 10.1002/cpa.21505
[5]	A. Berretti, A. D. Sokal, New Monte Carlo method for the self-avoiding walk, J. Stat. Phys., 40 (1985), 483–531. http://dx.doi.org/10.1007/bf01017183 doi: 10.1007/bf01017183
[6]	E. A. Bender, Asymptotic methods in enumeration, SIAM. Rev., 16 (1974), 485–515. https://doi.org/10.1137/1016082 doi: 10.1137/1016082
[7]	M. Barma, D. Dhar, Directed diffusion in a percolation network, J. Phys. C: Solid State Phys., 16 (1983), 1451–1458. http://dx.doi.org/10.1088/0022-3719/16/8/014 doi: 10.1088/0022-3719/16/8/014
[8]	E. Candellero, L. A. Gilch, S. M$\ddot{u}$ller, Branching random walks on free products of groups, Proc. Lond. Math. Soc., 104 (2012), 1085–1120. http://dx.doi.org/10.1112/plms/pdr060 doi: 10.1112/plms/pdr060
[9]	D. Dhar, Diffusion and drift on percolation networks in an external field, J. Phys. A: Math. Gen., 17 (1984), L257. http://dx.doi.org/10.1088/0305-4470/17/5/007 doi: 10.1088/0305-4470/17/5/007
[10]	D. Dhar, D. Stauffer, Drifit and trapping in biased diffusion on disordered lattices, Int. J. Mod. Phys. C, 9 (1998), 349–355. http://dx.doi.org/10.1142/S0129183198000273 doi: 10.1142/S0129183198000273
[11]	R. Durrett, Probability: Theory and examples, Cambridge University Press, 2010.
[12]	S. Havlin, D. Ben-Avraham, Diffusion in disordered media, Adv. Phys., 36 (1987), 695–798. https://doi.org/10.1080/00018738700101072 doi: 10.1080/00018738700101072
[13]	G. F. Lawler, A. D. Sokal, Bounds on the $L^2$ spectrum for Markov chains and Markov processes: A generalization of Cheeger's inequality, Trans. Amer. Math. Soc., 309 (1988), 557–580. http://dx.doi.org/10.1090/S0002-9947-1988-0930082-9 doi: 10.1090/S0002-9947-1988-0930082-9
[14]	G. Pete, Probability and geometry on groups. Lecture notes for a graduate course, 2024. Available from: http://www.math.bme.hu/gabor
[15]	R. Lyons, Random walks and percolation on trees, Ann. Probab., 18 (1990), 931–958. http://dx.doi.org/10.1214/aop/1176990730 doi: 10.1214/aop/1176990730
[16]	R. Lyons, Random walks and the growth of groups, C. R. Acad. Sci. Paris Sér. I Math., 320 (1995), 1361–1366.
[17]	R. Lyons, R. Pemantle, Y. Peres, Random walks on the lamplighter group, Ann. Probab., 24 (1996), 1993–2006. http://dx.doi.org/10.1214/aop/1041903214 doi: 10.1214/aop/1041903214
[18]	R. Lyons, R. Pemantle, Y. Peres, Biased random walks on Galton-Watson trees, Probab. Theory Relat. Fields., 106 (1996), 249–264. http://dx.doi.org/10.1007/s004400050064 doi: 10.1007/s004400050064
[19]	R. Lyons, Y. Peres, Probability on trees and networks, Cambridge University Press, 2017. http://dx.doi.org/10.1017/9781316672815
[20]	D. J. Randall, Counting in lattices: Combinatorial problems for statistical mechanics, University of California, Berkeley, 1994.
[21]	A. Sinclair, M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. Comput., 82 (1989), 93–133. http://dx.doi.org/10.1016/0890-5401(89)90067-9 doi: 10.1016/0890-5401(89)90067-9
[22]	D. W. Strook, An introduction to Markov process, Heidelberg: Springer, 2005.
[23]	Y. L. Shang, Multi-agent coordination in directed moving neighbourhood random networks, Chinese Phys. B., 19 (2010), 070201. http://dx.doi.org/10.1088/1674-1056/19/7/070201 doi: 10.1088/1674-1056/19/7/070201
[24]	Y. L. Shang, Mean commute time for random walks on hierarchical scale-free networks, Internet Mathematics, 8 (2012), 321–337. http://dx.doi.org/10.1080/15427951.2012.685685 doi: 10.1080/15427951.2012.685685
[25]	Z. Shi, V. Sidoravicius, H. Song, L. Wang, K. N. Xiang, Uniform spanning forests on biased Euclidean lattices, Ann. Inst. H. Poincaré Probab. Statist., 57 (2021), 1569–1582. http://dx.doi.org/10.1214/20-AIHP1119 doi: 10.1214/20-AIHP1119
[26]	H. Song, L. M. Wang, K. N. Xiang, Monotonicity of speed for biased random walk on Galton-Watson tree, arXiv Preprint, 2016. http://dx.doi.org/10.48550/arXiv.1610.08151
[27]	W. Woess, Random walks on infinite graphs and groups, Cambridge University Press, 2000.

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)