Frogs on trees? (English) Zbl 1390.60351

Summary: We study a system of simple random walks on \(\mathcal{T}_{d,n}=(\mathcal{V}_{d,n},\mathcal{E}_{d,n})\), the \(d\)-ary tree of depth \(n\), known as the frog model. Initially there are \(\mathrm{Pois}(\lambda)\) particles at each site, independently, with one additional particle planted at some vertex \(\mathbf{o}\). Initially all particles are inactive, except for the ones which are placed at \(\mathbf{o}\). Active particles perform independent simple random walk on the tree of length \(t \in\mathbb{N} \cup \{\infty \}\), referred to as the particles’ lifetime. When an active particle hits an inactive particle, the latter becomes active. The model is often interpreted as a model for a spread of an epidemic. As such, it is natural to investigate whether the entire population is eventually infected, and if so, how quickly does this happen. Let \(\mathcal{R}_t\) be the set of vertices which are visited by the process (with lifetime \(t\)). The susceptibility \(\mathcal{S}(\mathcal{T}_{d,n}):=\inf \{t:\mathcal{R}_t=\mathcal{V}_{d,n}\}\) is the minimal lifetime required for the process to visit all sites. The cover time \(\mathrm{CT}(\mathcal{T}_{d,n})\) is the first time by which every vertex was visited at least once, when we take \(t=\infty\). We show that there exist absolute constants \(c\),\(C>0\) such that for all \(d \geq 2\) and all \(\lambda = \lambda_n>0\) which does not diverge nor vanish too rapidly as a function of \(n\), with high probability \(c \leq \lambda\mathcal{S}(\mathcal{T}_{d,n})/[n\log (n/\lambda)] \leq C\) and \(\mathrm{CT}(\mathcal{T}_{d,n})\leq 3^{4\sqrt{\log |\mathcal{V}_{d,n}|}}\).


60K35 Interacting random processes; statistical mechanics type models; percolation theory
05C81 Random walks on graphs
Full Text: DOI arXiv Euclid


[1] David Aldous, Random walk covering of some special trees, J. Math. Anal. Appl. 157 (1991), no. 1, 271–283. · Zbl 0733.60092
[2] David Aldous, Threshold limits for cover times, J. Theoret. Probab. 4 (1991), no. 1, 197–211. · Zbl 0717.60082
[3] David Aldous and Jim Fill, Reversible Markov chains and random walks on graphs, 2002. Unfinished manuscript.
[4] O. S. M. Alves, F. P. Machado, and S. Yu. Popov, Phase transition for the frog model, Electron. J. Probab. 7 (2002), no. 16, 21. · Zbl 1013.60081
[5] O. S. M. Alves, F. P. Machado, and S. Yu. Popov, The shape theorem for the frog model, Ann. Appl. Probab. 12 (2002), no. 2, 533–546. · Zbl 1013.60081
[6] O. S. M. Alves, F. P. Machado, S. Yu. Popov, and K. Ravishankar, The shape theorem for the frog model with random initial configuration, Markov Process. Related Fields 7 (2001), no. 4, 525–539. · Zbl 0991.60097
[7] Riddhipratim Basu, Jonathan Hermon, and Yuval Peres, Characterization of cutoff for reversible Markov chains, Ann. Probab. 45 (2017), no. 3, 1448–1487. · Zbl 1374.60129
[8] Itai Benjamini, Private communication, 2012.
[9] Itai Benjamini, Luiz Renato Fontes, Jonathan Hermon, and Fabio Prates Machado, On an epidemic model on finite graphs, arXiv:1610.04301 (2016).
[10] Itai Benjamini and Jonathan Hermon, Rapid social connectivity, arXiv:1608.07621 (2016). · Zbl 1419.82053
[11] Lucas Boczkowski, Yuval Peres, and Perla Sousi, Sensitivity of mixing times in Eulerian digraphs, arXiv:1603.05639 (2016). · Zbl 1390.05219
[12] Christian Döbler, Nina Gantert, Thomas Höfelsauer, Serguei Popov, and Felizitas Weidner, Recurrence and transience of frogs with drift on \(\Bbb Z^d\), arXiv:1709.00038 (2017). · Zbl 1414.60057
[13] Christian Döbler and Lorenz Pfeifroth, Recurrence for the frog model with drift on \(\Bbb Z^d\), Electron. Commun. Probab. 19 (2014), no. 79, 13. · Zbl 1325.60155
[14] Uriel Feige, A tight lower bound on the cover time for random walks on graphs, Random Structures & Algorithms 6 (1995), no. 4, 433–438. · Zbl 0832.60016
[15] James Allen Fill, The passage time distribution for a birth-and-death chain: strong stationary duality gives a first stochastic proof, J. Theoret. Probab. 22 (2009), no. 3, 543–557. · Zbl 1178.60054
[16] N. Gantert and P. Schmidt, Recurrence for the frog model with drift on \(\Bbb Z\), Markov Process. Related Fields 15 (2009), no. 1, 51–58. · Zbl 1172.60030
[17] Arka Ghosh, Steven Noren, and Alexander Roitershtein, On the range of the transient frog model on \(\Bbb{Z} \), Adv. in Appl. Probab. 49 (2017), no. 2, 327–343.
[18] Sharad Goel, Ravi Montenegro, and Prasad Tetali, Mixing time bounds via the spectral profile, Electron. J. Probab. 11 (2006), no. 1, 1–26. · Zbl 1109.60061
[19] Jonathan Hermon, Ben Morris, Chuan Qin, and Allan Sly, The social network model on infinite graphs, arXiv:1610.04293 (2016).
[20] Christopher Hoffman, Tobias Johnson, and Matthew Junge, From transience to recurrence with Poisson tree frogs, Ann. Appl. Probab. 26 (2016), no. 3, 1620–1635. · Zbl 1345.60116
[21] Christopher Hoffman, Tobias Johnson, and Matthew Junge, Infection spread for the frog model on trees, arXiv:1710.05884 (2017). · Zbl 1385.60058
[22] Christopher Hoffman, Tobias Johnson, and Matthew Junge, Recurrence and transience for the frog model on trees, Ann. Probab. 45 (2017), no. 5, 2826–2854. · Zbl 1385.60058
[23] Tobias Johnson and Matthew Junge, The critical density for the frog model is the degree of the tree, Electron. Commun. Probab. 21 (2016), Paper No. 82, 12. · Zbl 1354.60119
[24] Tobias Johnson and Matthew Junge, Stochastic orders and the frog model, arXiv:1602.04411 (2016). · Zbl 1354.60119
[25] O. Kallenberg, Foundations of modern probability, springer, 2002. · Zbl 0996.60001
[26] Samuel Karlin and James McGregor, Coincidence properties of birth and death processes, Pacific J. Math. 9 (1959), 1109–1140. · Zbl 0097.34102
[27] Julian Keilson, Markov chain models, rarity and exponentiality, vol. 28, Springer Science & Business Media, 2012. · Zbl 0411.60068
[28] Harry Kesten and Vladas Sidoravicius, The spread of a rumor or infection in a moving population, Ann. Probab. 33 (2005), no. 6, 2402–2462. · Zbl 1111.60074
[29] Harry Kesten and Vladas Sidoravicius, A phase transition in a model for the spread of an infection, Illinois J. Math. 50 (2006), no. 1-4, 547–634. · Zbl 1101.92040
[30] Harry Kesten and Vladas Sidoravicius, A shape theorem for the spread of an infection, Ann. of Math. 167 (2008), no. 3, 701–766. · Zbl 1202.92077
[31] Elena Kosygina and Martin P. W. Zerner, A zero-one law for recurrence and transience of frog processes, Probab. Theory Related Fields 168 (2017), no. 1-2, 317–346. · Zbl 1372.60047
[32] David Asher Levin and Yuval Peres, Markov chains and mixing times, American Mathematical Soc. (2017). With contributions by Elizabeth L. Wilmer and a chapter by James G. Propp and David B. Wilson. MR3726904 · Zbl 1390.60001
[33] Eyal Lubetzky and Yuval Peres, Cutoff on all Ramanujan graphs, Geom. Funct. Anal. 26 (2016), no. 4, 1190–1216. · Zbl 1351.05208
[34] Laurent Miclo, On absorption times and Dirichlet eigenvalues, ESAIM Probab. Stat. 14 (2010), 117–150. · Zbl 1222.60050
[35] S. Yu. Popov, Frogs in random environment, J. Statist. Phys. 102 (2001), no. 1-2, 191–201. · Zbl 0972.60101
[36] A. F. Ramírez and V. Sidoravicius, Asymptotic behavior of a stochastic combustion growth process, J. Eur. Math. Soc. (JEMS) 6 (2004), no. 3, 293–334. · Zbl 1049.60089
[37] Joshua Rosenberg, The frog model with drift on \(\Bbb R\), Electron. Commun. Probab. 22 (2017), Paper No. 30, 14. · Zbl 1364.60098
[38] András Telcs and Nicholas C. Wormald, Branching and tree indexed random walks on fractals, J. Appl. Probab. 36 (1999), no. 4, 999–1011. · Zbl 0967.60059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.