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

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$$.

### 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
Full Text:

### References:

  Aldous, D. and Fill, J. (2002). Reversible Markov chains and random walks on graphs.  Aldous, D. J. (1991). Threshold limits for cover times. J. Theoret. Probab. 4 197-211. · Zbl 0717.60082  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  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  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  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  Basu, R., Hermon, J. and Peres, Y. (2017). Characterization of cutoff for reversible Markov chains. Ann. Probab. 45 1448-1487. · Zbl 1374.60129  Belius, D. (2013). Gumbel fluctuations for cover times in the discrete torus. Probab. Theory Related Fields 157 635-689. · Zbl 1295.60053  Belius, D. and Kistler, N. (2017). The subleading order of two dimensional cover times. Probab. Theory Related Fields 167 461-552. · Zbl 1365.60071  Benjamini, I. and Hermon, J. (2019). Rapid social connectivity. Electron. J. Probab. 24 Paper No. 32, 33. · Zbl 1419.82053  Benjamini, I., Nachmias, A. and Peres, Y. (2011). Is the critical percolation probability local? Probab. Theory Related Fields 149 261-269. · Zbl 1230.60099  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  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  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  Ding, J. (2012). On cover times for 2D lattices. Electron. J. Probab. 17 no. 45, 18. · Zbl 1258.60044  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  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  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  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  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  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  Goel, S., Montenegro, R. and Tetali, P. (2006). Mixing time bounds via the spectral profile. Electron. J. Probab. 11 1-26. · Zbl 1109.60061  Hermon, J. (2018). Frogs on trees? Electron. J. Probab. 23 Paper No. 17, 40. · Zbl 1390.60351  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.  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  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  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  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  Johnson, T. and Junge, M. (2018). Stochastic orders and the frog model. Ann. Inst. Henri Poincaré Probab. Stat. 54 1013-1030. · Zbl 1391.60236  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  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  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  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  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  Levin, D. A. and Peres, Y. (2017). Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI.  Matthews, P. (1988). Covering problems for Markov chains. Ann. Probab. 16 1215-1228. · Zbl 0712.60076  Penrose, M. D. and Pisztora, A. (1996). Large deviations for discrete and continuous percolation. Adv. in Appl. Probab. 28 29-52. · Zbl 0853.60085  Popov, S. Yu. (2001). Frogs in random environment. J. Stat. Phys. 102 191-201. · Zbl 0972.60101  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  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  Rosenberg, J. (2017). The frog model with drift on $$\mathbb{R}$$. Electron. Commun. Probab. 22 Paper No. 30, 14. · Zbl 1364.60098  Starr, N. (1966). Operator limit theorems. Trans. Amer. Math. Soc. 121 90-115. · Zbl 0147.15601  Telcs, A. and Wormald, N. C. (1999). Branching and tree indexed random walks on fractals. J. Appl. Probab. 36 999-1011. · Zbl 0967.60059  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.