Cover times of many diffusive or subdiffusive searchers. (English) Zbl 1534.60112
Summary: Cover times measure the speed of exhaustive searches which require the exploration of an entire spatial region(s). Applications include the immune system hunting pathogens, animals collecting food, robotic demining or cleaning, and computer search algorithms. Mathematically, a cover time is the first time a random searcher(s) comes within a specified “detection radius” of every point in the target region (often the entire spatial domain). Due to their many applications and their fundamental probabilistic importance, cover times have been extensively studied in the physics and probability literatures. This prior work has generally studied cover times of a single searcher with a vanishing detection radius or a large target region. This prior work has further claimed that cover times for multiple searchers can be estimated by a simple rescaling of the cover time of a single searcher. In this paper, we study cover times of many diffusive or subdiffusive searchers and show that prior estimates break down as the number of searchers grows. We prove a rather universal formula for all the moments of such cover times in the many searcher limit that depends only on (i) the searcher’s characteristic (sub)diffusivity and (ii) a certain geodesic distance between the searcher starting location(s) and the farthest point in the target. This formula is otherwise independent of the detection radius, space dimension, target size, and domain size. We illustrate our results in several examples and compare them to detailed stochastic simulations.
MSC:
| 60J65 | Brownian motion |
| 60J60 | Diffusion processes |
| 60G70 | Extreme value theory; extremal stochastic processes |
References:
| [1] | Aldous, D., An introduction to covering problems for random walks on graphs, J. Theoret. Probab., 2 (1989), pp. 87-89. · Zbl 0684.60054 |
| [2] | Aldous, D. J., On the time taken by random walks on finite groups to visit every state, Z. Wahrscheinlichkeitstheorie Verwandte Gebiete, 62 (1983), pp. 361-374. · Zbl 0488.60011 |
| [3] | Aldous, D. J., Lower bounds for covering times for reversible Markov chains and random walks on graphs, J. Theoret. Probab., 2 (1989), pp. 91-100. · Zbl 0684.60055 |
| [4] | Barkai, E., Garini, Y., and Metzler, R., Strange kinetics of single molecules in living cells, Phys. Today, 65 (2012), 29. |
| [5] | Belius, D., Gumbel fluctuations for cover times in the discrete torus, Probab. Theory Related Fields, 157 (2013), pp. 635-689. · Zbl 1295.60053 |
| [6] | Belius, D. and Kistler, N., The subleading order of two dimensional cover times, Probab. Theory Related Fields, 167 (2017), pp. 461-552. · Zbl 1365.60071 |
| [7] | Broder, A. Z. and Karlin, A. R., Bounds on the cover time, J. Theoret. Probab., 2 (1989), pp. 101-120. · Zbl 0681.60063 |
| [8] | Brummelhuis, M. and Hilhorst, H., Covering of a finite lattice by a random walk, Phys. A, 176 (1991), pp. 387-408. |
| [9] | Cheng, K., Dong, J.-Q., Huang, L., and Yang, L., Cover-time distribution of random processes in granular gases, Phys. Rev. E (3), 98 (2018), 042109. |
| [10] | Chou, T. and D’Orsogna, M. R., First passage problems in biology, in First-Passage Phenomena and Their Applications, World Scientific, Hackensack, NJ, 2014, pp. 306-345. |
| [11] | Chupeau, M., Bénichou, O., and Voituriez, R., Mean cover time of one-dimensional persistent random walks, Phys. Rev. E (3), 89 (2014), 062129. |
| [12] | Chupeau, M., Bénichou, O., and Voituriez, R., Cover times of random searches, Nature Phys., 11 (2015), pp. 844-847. |
| [13] | De Haan, L. and Ferreira, A., Extreme Value Theory: An Introduction, Springer, New York, 2006. · Zbl 1101.62002 |
| [14] | Dembo, A., Peres, Y., and Rosen, J., Brownian motion on compact manifolds: Cover time and late points, Electron. J. Probab., 8 (2003), 15, doi:10.1214/EJP.v8-139. · Zbl 1063.58021 |
| [15] | Dembo, A., Peres, Y., Rosen, J., and Zeitouni, O., Cover times for Brownian motion and random walks in two dimensions, Ann. of Math. (2), 160 (2004), pp. 433-464. · Zbl 1068.60018 |
| [16] | Ding, J., On cover times for 2d lattices, Electron. J. Probab., 17 (2012), 45. · Zbl 1258.60044 |
| [17] | Dong, J.-Q., Han, W.-H., Wang, Y., Chen, X.-S., and Huang, L., Universal cover-time distribution of heterogeneous random walks, Phys. Rev. E (3), 107 (2023), 024128. |
| [18] | Donsker, M. D. and Varadhan, S. S., Asymptotics for the Wiener sausage, Comm. Pure Appl. Math., 28 (1975), pp. 525-565. · Zbl 0333.60077 |
| [19] | Durrett, R., Probability: Theory and Examples, Cambridge University Press, Cambridge, 2019. · Zbl 1440.60001 |
| [20] | Golding, I. and Cox, E. C., Physical nature of bacterial cytoplasm, Phys. Rev. Lett., 96 (2006), 098102. |
| [21] | Grassberger, P., How fast does a random walk cover a torus?, Phys. Rev. E (3), 96 (2017), 012115. |
| [22] | Han, W.-H., Cheng, K., Liu, X.-N., Dong, J.-Q., Chen, X.-S., and Huang, L., Universal cover-time distributions of random motion in bounded granular gases, Chaos, 33 (2023), 023127. |
| [23] | Hemmer, P. and Hemmer, S., Lattice covering by two random walkers in one dimension, Phys. A, 251 (1998), pp. 245-250. |
| [24] | Höfling, F. and Franosch, T., Anomalous transport in the crowded world of biological cells, Rep. Prog. Phys., 76 (2013), 046602. |
| [25] | Kahn, J. D., Linial, N., Nisan, N., and Saks, M. E., On the cover time of random walks on graphs, J. Theoret. Probab., 2 (1989), pp. 121-128. · Zbl 0681.60064 |
| [26] | Klafter, J. and Sokolov, I. M., Anomalous diffusion spreads its wings, Phys. World, 18 (2005), 29. |
| [27] | Kloeden, P. E. and Platen, E., Numerical Solution of Stochastic Differential Equations, corrected ed., Springer, Berlin, 1992. · Zbl 0752.60043 |
| [28] | Lawley, S. D., Extreme first-passage times for random walks on networks, Phys. Rev. E (3), 102 (2020), 062118. |
| [29] | Lawley, S. D., Extreme statistics of anomalous subdiffusion following a fractional Fokker-Planck equation: Subdiffusion is faster than normal diffusion, J. Phys. A, 53 (2020), 385005. · Zbl 1519.35332 |
| [30] | Lawley, S. D., Universal formula for extreme first passage statistics of diffusion, Phys. Rev. E (3), 101 (2020), 012413. |
| [31] | Lawley, S. D., Extreme statistics of superdiffusive Lévy flights and every other Lévy subordinate Brownian motion, J. Nonlinear Sci., 33 (2023), 53. · Zbl 1515.60165 |
| [32] | Magdziarz, M., Weron, A., and Weron, K., Fractional Fokker-Planck dynamics: Stochastic representation and computer simulation, Phys. Rev. E (3), 75 (2007), 016708. |
| [33] | Magdziarz, M. and Zorawik, T., Stochastic representation of a fractional subdiffusion equation. The case of infinitely divisible waiting times, Lévy noise and space-time-dependent coefficients, Proc. Amer. Math. Soc., 144 (2016), pp. 1767-1778. · Zbl 1335.60126 |
| [34] | Majumdar, S. N., Sabhapandit, S., and Schehr, G., Exact distributions of cover times for n independent random walkers in one dimension, Phys. Rev. E (3), 94 (2016), 062131. |
| [35] | Maziya, G., Cocconi, L., Pruessner, G., and Moloney, N. R., Dynamically accelerated cover times, Phys. Rev. Res., 2 (2020), 023421. |
| [36] | Mendonça, J. R. G., Numerical evidence against a conjecture on the cover time of planar graphs, Phys. Rev. E (3), 84 (2011), 022103. |
| [37] | Metzler, R., Barkai, E., and Klafter, J., Anomalous diffusion and relaxation close to thermal equilibrium: A fractional Fokker-Planck equation approach, Phys. Rev. Lett., 82 (1999), pp. 3563-3567. |
| [38] | Metzler, R. and Klafter, J., The random walk’s guide to anomalous diffusion: A fractional dynamics approach, Phys. Rep., 339 (2000), pp. 1-77. · Zbl 0984.82032 |
| [39] | Nascimento, M. S., Coutinho-Filho, M. D., and Yokoi, C. S., Partial and random covering times in one dimension, Phys. Rev. E (3), 63 (2001), 066125. |
| [40] | Nemirovsky, A., Mártin, H., and Coutinho-Filho, M., Universality in the lattice-covering time problem, Phys. Rev. A (3), 41 (1990), 761. |
| [41] | Norris, J. R., Heat kernel asymptotics and the distance function in Lipschitz Riemannian manifolds, Acta Math., 179 (1997), pp. 79-103. · Zbl 0912.58041 |
| [42] | Oliveira, F. A., Ferreira, R., Lapas, L. C., and Vainstein, M. H., Anomalous diffusion: A basic mechanism for the evolution of inhomogeneous systems, Front. Phys., 7 (2019), 18. |
| [43] | Ozawa, S., An asymptotic formula for the eigenvalues of the Laplacian in a three-dimensional domain with a small hole, J. Fac. Sci. Univ. Tokyo Sect. IA Math., 30 (1983), pp. 243-257. · Zbl 0541.35060 |
| [44] | Redner, S., A Guide to First-Passage Processes, Cambridge University Press, Cambridge, 2001. · Zbl 0980.60006 |
| [45] | Ruiz, S. M., An algebraic identity leading to Wilson’s theorem, Math. Gaz., 80 (1996), pp. 579-582. |
| [46] | Samko, S. G., Kilbas, A. A., and Marichev, O. I., Fractional Integrals and Derivatives, Vol. 1, Gordon and Breach Science Publishers, Yverdon-les-Bains, Switzerland, 1993. · Zbl 0818.26003 |
| [47] | Sokolov, I. M., Models of anomalous diffusion in crowded environments, Soft Matter, 8 (2012), pp. 9043-9052. |
| [48] | Varadhan, S. R. S., Diffusion processes in a small time interval, Comm. Pure Appl. Math., 20 (1967), pp. 659-685. · Zbl 0278.60051 |
| [49] | Ward, M. J. and Keller, J. B., Strong localized perturbations of eigenvalue problems, SIAM J. Appl. Math., 53 (1993), pp. 770-798. · Zbl 0778.35081 |
| [50] | Yokoi, C. S., Hernández-Machado, A., and Ramírez-Piscina, L., Some exact results for the lattice covering time problem, Phys. Lett. A, 145 (1990), pp. 82-86. |
| [51] | Zlatanov, N. and Kocarev, L., Random walks on networks: Cumulative distribution of cover time, Phys. Rev. E (3), 80 (2009), 041102. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
