×
Benjamini, Itai; Fontes, Luiz Renato; Hermon, Jonathan; Machado, Fábio Prates

On an epidemic model on finite graphs. (English) Zbl 1434.82074

Ann. Appl. Probab. 30, No. 1, 208-258 (2020).
Summary: We study a system of random walks, known as the frog model, starting from a profile of independent Poisson \((\lambda)\) particles per site, with one additional active particle planted at some vertex \(\mathbf{o}\) of a finite connected simple graph \(G=(V,E)\). Initially, only the particles occupying \(\mathbf{o}\) are active. Active particles perform \(t\in \mathbb{N}\cup\{\infty\}\) steps of the walk they picked before vanishing and activate all inactive particles they hit. This system is often taken as a model for the spread of an epidemic over a population. Let \(\mathcal{R}_t\) be the set of vertices which are visited by the process, when active particles vanish after \(t\) steps. We study the susceptibility of the process on the underlying graph, defined as the random quantity \(\mathcal{S}(G):=\inf\{t:\mathcal{R}_t=V\}\) (essentially, the shortest particles’ lifespan required for the entire population to get infected). We consider the cases that the underlying graph is either a regular expander or a \(d\)-dimensional torus of side length \(n\) (for all \(d\ge 1)\mathbb{T}_d(n)\) and determine the asymptotic behavior of \(\mathcal{S}\) up to a constant factor. In fact, throughout we allow the particle density \(\lambda\) to depend on \(n\) and for \(d\ge 2\) we determine the asymptotic behavior of \(\mathcal{S}(\mathbb{T}_d(n))\) up to smaller order terms for a wide range of \(\lambda=\lambda_n\).

Cited in 5 Documents

MSC:

82C41 Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
92D30 Epidemiology

Keywords:

frog model; epidemic spread; infection spread; rumor spread; simple random walk; susceptibility; cover time; multiple random walks
PDF BibTeX XML Cite
\textit{I. Benjamini} et al., Ann. Appl. Probab. 30, No. 1, 208--258 (2020; Zbl 1434.82074)
Full Text: DOI arXiv Euclid
  • logo of hbz
  • logo of WorldCat

References:

[1] Aldous, D. and Fill, J. (2002). Reversible Markov chains and random walks on graphs.
[2] Aldous, D. J. (1991). Threshold limits for cover times. J. Theoret. Probab. 4 197-211. · Zbl 0717.60082
[3] Alon, N., Avin, C., Koucký, M., Kozma, G., Lotker, Z. and Tuttle, M. R. (2011). Many random walks are faster than one. Combin. Probab. Comput. 20 481-502. · Zbl 1223.05284
[4] Alves, O. S. M., Machado, F. P. and Popov, S. Yu. (2002). Phase transition for the frog model. Electron. J. Probab. 7 no. 16, 21. · Zbl 1012.60081
[5] Alves, O. S. M., Machado, F. P. and Popov, S. Yu. (2002). The shape theorem for the frog model. Ann. Appl. Probab. 12 533-546. · Zbl 1013.60081
[6] Alves, O. S. M., Machado, F. P., Popov, S. Yu. and Ravishankar, K. (2001). The shape theorem for the frog model with random initial configuration. Markov Process. Related Fields 7 525-539. · Zbl 0991.60097
[7] Basu, R., Hermon, J. and Peres, Y. (2017). Characterization of cutoff for reversible Markov chains. Ann. Probab. 45 1448-1487. · Zbl 1374.60129
[8] Belius, D. (2013). Gumbel fluctuations for cover times in the discrete torus. Probab. Theory Related Fields 157 635-689. · Zbl 1295.60053
[9] Belius, D. and Kistler, N. (2017). The subleading order of two dimensional cover times. Probab. Theory Related Fields 167 461-552. · Zbl 1365.60071
[10] Benjamini, I. and Hermon, J. (2019). Rapid social connectivity. Electron. J. Probab. 24 Paper No. 32, 33. · Zbl 1419.82053
[11] Benjamini, I., Nachmias, A. and Peres, Y. (2011). Is the critical percolation probability local? Probab. Theory Related Fields 149 261-269. · Zbl 1230.60099
[12] Boczkowski, L., Peres, Y. and Sousi, P. (2018). Sensitivity of mixing times in Eulerian digraphs. SIAM J. Discrete Math. 32 624-655. · Zbl 1390.05219
[13] Comets, F., Gallesco, C., Popov, S. and Vachkovskaia, M. (2013). On large deviations for the cover time of two-dimensional torus. Electron. J. Probab. 18 no. 96, 18. · Zbl 1294.60066
[14] Dembo, A., Peres, Y., Rosen, J. and Zeitouni, O. (2004). Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. (2) 160 433-464. · Zbl 1068.60018
[15] Ding, J. (2012). On cover times for 2D lattices. Electron. J. Probab. 17 no. 45, 18. · Zbl 1258.60044
[16] Döbler, C., Gantert, N., Höfelsauer, T., Popov, S. and Weidner, F. (2017). Recurrence and transience of frogs with drift on \(\mathbb{Z}^d \). Preprint. Available at arXiv:1709.00038. · Zbl 1414.60057
[17] Döbler, C. and Pfeifroth, L. (2014). Recurrence for the frog model with drift on \(\mathbb{Z}^d \). Electron. Commun. Probab. 19 no. 79, 13. · Zbl 1325.60155
[18] Efremenko, K. and Reingold, O. (2009). How well do random walks parallelize? In Approximation, Randomization, and Combinatorial Optimization. Lecture Notes in Computer Science 5687 476-489. Springer, Berlin. · Zbl 1255.05180
[19] Elsässer, R. and Sauerwald, T. (2011). Tight bounds for the cover time of multiple random walks. Theoret. Comput. Sci. 412 2623-2641. · Zbl 1227.68030
[20] Gantert, N. and Schmidt, P. (2009). Recurrence for the frog model with drift on \(\mathbb{Z} \). Markov Process. Related Fields 15 51-58. · Zbl 1172.60030
[21] Ghosh, A., Noren, S. and Roitershtein, A. (2017). On the range of the transient frog model on \(\mathbb{Z} \). Adv. in Appl. Probab. 49 327-343. · Zbl 1425.60063
[22] Goel, S., Montenegro, R. and Tetali, P. (2006). Mixing time bounds via the spectral profile. Electron. J. Probab. 11 1-26. · Zbl 1109.60061
[23] Hermon, J. (2018). Frogs on trees? Electron. J. Probab. 23 Paper No. 17, 40. · Zbl 1390.60351
[24] Hermon, J., Morris, B., Qin, C. and Sly, A. (2016). The social network model on infinite graphs. Preprint. Available at arXiv:1610.04293. Ann. Appl. Probab. To appear.
[25] Hoffman, C., Johnson, T. and Junge, M. (2016). From transience to recurrence with Poisson tree frogs. Ann. Appl. Probab. 26 1620-1635. · Zbl 1345.60116
[26] Hoffman, C., Johnson, T. and Junge, M. (2017). Infection spread for the frog model on trees. Preprint. Available at arXiv:1710.05884. · Zbl 1427.60201
[27] Hoffman, C., Johnson, T. and Junge, M. (2017). Recurrence and transience for the frog model on trees. Ann. Probab. 45 2826-2854. · Zbl 1385.60058
[28] Johnson, T. and Junge, M. (2016). The critical density for the frog model is the degree of the tree. Electron. Commun. Probab. 21 Paper No. 82, 12. · Zbl 1354.60119
[29] Johnson, T. and Junge, M. (2018). Stochastic orders and the frog model. Ann. Inst. Henri Poincaré Probab. Stat. 54 1013-1030. · Zbl 1391.60236
[30] Kesten, H. and Sidoravicius, V. (2005). The spread of a rumor or infection in a moving population. Ann. Probab. 33 2402-2462. · Zbl 1111.60074
[31] Kesten, H. and Sidoravicius, V. (2006). A phase transition in a model for the spread of an infection. Illinois J. Math. 50 547-634. · Zbl 1101.92040
[32] Kesten, H. and Sidoravicius, V. (2008). A shape theorem for the spread of an infection. Ann. of Math. (2) 167 701-766. · Zbl 1202.92077
[33] Kosygina, E. and Zerner, M. P. W. (2017). A zero-one law for recurrence and transience of frog processes. Probab. Theory Related Fields 168 317-346. · Zbl 1372.60047
[34] Kurkova, I., Popov, S. and Vachkovskaia, M. (2004). On infection spreading and competition between independent random walks. Electron. J. Probab. 9 293-315. · Zbl 1065.60148
[35] Levin, D. A. and Peres, Y. (2017). Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI.
[36] Matthews, P. (1988). Covering problems for Markov chains. Ann. Probab. 16 1215-1228. · Zbl 0712.60076
[37] Penrose, M. D. and Pisztora, A. (1996). Large deviations for discrete and continuous percolation. Adv. in Appl. Probab. 28 29-52. · Zbl 0853.60085
[38] Popov, S. Yu. (2001). Frogs in random environment. J. Stat. Phys. 102 191-201. · Zbl 0972.60101
[39] Popov, S. Yu. (2003). Frogs and some other interacting random walks models. In Discrete Random Walks (Paris, 2003). Discrete Math. Theor. Comput. Sci. Proc., AC 277-288. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1034.60089
[40] Ramírez, A. F. and Sidoravicius, V. (2004). Asymptotic behavior of a stochastic combustion growth process. J. Eur. Math. Soc. (JEMS) 6 293-334. · Zbl 1049.60089
[41] Rosenberg, J. (2017). The frog model with drift on \(\mathbb{R} \). Electron. Commun. Probab. 22 Paper No. 30, 14. · Zbl 1364.60098
[42] Starr, N. (1966). Operator limit theorems. Trans. Amer. Math. Soc. 121 90-115. · Zbl 0147.15601
[43] Telcs, A. and Wormald, N. C. (1999). Branching and tree indexed random walks on fractals. J. Appl. Probab. 36 999-1011. · Zbl 0967.60059
[44] Zuckerman, D. (1992). A technique for lower bounding the cover time. SIAM J. Discrete Math. 5 81-87. · Zbl 0743.60068
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.