×

zbMATH — the first resource for mathematics

Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees. (English) Zbl 1316.60064
Summary: In this paper we show that on bounded degree graphs and general trees, the cover time of the simple random walk is asymptotically equal to the product of the number of edges and the square of the expected supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. Previously, this was only proved for regular trees and the 2D lattice. Furthermore, for general trees, we derive exponential concentration for the cover time, which implies that the standard deviation of the cover time is bounded by the geometric mean of the cover time and the maximal hitting time.

MSC:
60G50 Sums of independent random variables; random walks
60G60 Random fields
60G15 Gaussian processes
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
05C81 Random walks on graphs
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Addario-Berry, L. and Reed, B. (2009). Minima in branching random walks. Ann. Probab. 37 1044-1079. · Zbl 1196.60142
[2] Ajtai, M., Komlós, J. and Szemerédi, E. (1982). Largest random component of a \(k\)-cube. Combinatorica 2 1-7. · Zbl 0489.05053
[3] Aldous, D. and Fill, J. Reversible Markov chains and random walks on graphs. Unpublished manuscript. Available at .
[4] Aldous, D. J. (1991). Random walk covering of some special trees. J. Math. Anal. Appl. 157 271-283. · Zbl 0733.60092
[5] Aldous, D. J. (1991). Threshold limits for cover times. J. Theoret. Probab. 4 197-211. · Zbl 0717.60082
[6] Alon, N., Benjamini, I. and Stacey, A. (2004). Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 1727-1745. · Zbl 1046.05071
[7] Benjamini, I., Gurel-Gurevich, O. and Morris, B. (2010). Linear cover time is exponentially unlikely. Preprint. Available at . · Zbl 1259.05154
[8] Benjamini, I., Nachmias, A. and Peres, Y. (2011). Is the critical percolation probability local? Probab. Theory Related Fields 149 261-269. · Zbl 1230.60099
[9] Bolthausen, E., Deuschel, J.-D. and Giacomin, G. (2001). Entropic repulsion and the maximum of the two-dimensional harmonic crystal. Ann. Probab. 29 1670-1692. · Zbl 1034.82018
[10] Bolthausen, E., Deuschel, J. D. and Zeitouni, O. (2011). Recursions and tightness for the maximum of the discrete, two dimensional Gaussian free field. Electron. Commun. Probab. 16 114-119. · Zbl 1236.60039
[11] Bramson, M. and Zeitouni, O. (2009). Tightness for a family of recursion equations. Ann. Probab. 37 615-653. · Zbl 1169.60020
[12] Bramson, M. and Zeitouni, O. (2012). Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field. Comm. Pure Appl. Math. 65 1-20. · Zbl 1237.60041
[13] Bramson, M. D. (1978). Maximal displacement of branching Brownian motion. Comm. Pure Appl. Math. 31 531-581. · Zbl 0361.60052
[14] Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R. and Tiwari, P. (1996/97). The electrical resistance of a graph captures its commute and cover times. Comput. Complexity 6 312-340. · Zbl 0905.60049
[15] Chatterjee, S. (2008). Chaos, concentration, and multiple valleys. Preprint. Available at .
[16] 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
[17] Ding, J., Lee, J. R. and Peres, Y. (2012). Cover times, blanket times, and majorizing measures. Ann. of Math. (2) 175 1409-1471. · Zbl 1250.05098
[18] Ding, J. and Zeitouni, O. (2012). A sharp estimate for cover times on binary trees. Stochastic Process. Appl. 122 2117-2133. · Zbl 1255.05179
[19] Durrett, R. (2010). Probability : Theory and Examples , 4th ed. Cambridge Univ. Press, Cambridge. · Zbl 1202.60001
[20] Dynkin, E. B. (1980). Markov processes and random fields. Bull. Amer. Math. Soc. ( N.S. ) 3 975-999. · Zbl 0519.60046
[21] Dynkin, E. B. (1984). Gaussian and non-Gaussian random fields associated with Markov processes. J. Funct. Anal. 55 344-376. · Zbl 0533.60061
[22] Dynkin, E. B. (1984). Local times and quantum fields. In Seminar on Stochastic Processes , 1983 ( Gainesville , Fla. , 1983). Progr. Probab. Statist. 7 69-83. Birkhäuser, Boston, MA. · Zbl 0554.60058
[23] Eisenbaum, N. (1995). Une version sans conditionnement du théorème d’isomorphisms de Dynkin. In Séminaire de Probabilités , XXIX. Lecture Notes in Math. 1613 266-289. Springer, Berlin. · Zbl 0849.60075
[24] Eisenbaum, N., Kaspi, H., Marcus, M. B., Rosen, J. and Shi, Z. (2000). A Ray-Knight theorem for symmetric Markov processes. Ann. Probab. 28 1781-1796. · Zbl 1044.60064
[25] Feige, U. and Zeitouni, O. (2009). Deterministic approximation for the cover time of trees. Preprint. Available at .
[26] Fernique, X. (1974). Des résultats nouveaux sur les processus gaussiens. C. R. Acad. Sci. Paris Sér. A 278 363-365. · Zbl 0274.60029
[27] Janson, S. (1997). Gaussian Hilbert Spaces. Cambridge Tracts in Mathematics 129 . Cambridge Univ. Press, Cambridge. · Zbl 0887.60009
[28] Kahn, J., Kim, J. H., Lovász, L. and Vu, V. H. (2000). The cover time, the blanket time, and the Matthews bound. In 41 st Annual Symposium on Foundations of Computer Science ( Redondo Beach , CA , 2000) 467-475. IEEE Comput. Soc., Los Alamitos, CA.
[29] Klein, D. J. and Randić, M. (1993). Resistance distance. J. Math. Chem. 12 81-95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991).
[30] Knight, F. B. (1963). Random walks and a sojourn density process of Brownian motion. Trans. Amer. Math. Soc. 109 56-86. · Zbl 0119.14604
[31] Ledoux, M. (2001). The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89 . Amer. Math. Soc., Providence, RI. · Zbl 0995.60002
[32] Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times . Amer. Math. Soc., Providence, RI. With a chapter by James G. Propp and David B. Wilson. · Zbl 1160.60001
[33] Lovász, L. (1996). Random walks on graphs: A survey. In Combinatorics , Paul Erdős Is Eighty , Vol. 2 ( Keszthely , 1993). Bolyai Society Mathematical Studies 2 353-397. János Bolyai Math. Soc., Budapest. · Zbl 0854.60071
[34] Lyons, R. and Peres, Y. (2009). Probability on trees and networks. Unpublished manuscript. Current version available at .
[35] Marcus, M. B. and Rosen, J. (1992). Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes. Ann. Probab. 20 1603-1684. · Zbl 0762.60068
[36] Marcus, M. B. and Rosen, J. (2001). Gaussian processes and local times of symmetric Lévy processes. In Lévy Processes 67-88. Birkhäuser, Boston, MA. · Zbl 0988.60026
[37] Marcus, M. B. and Rosen, J. (2006). Markov Processes , Gaussian Processes , and Local Times. Cambridge Studies in Advanced Mathematics 100 . Cambridge Univ. Press, Cambridge. · Zbl 1129.60002
[38] Meka, R. (2012). A PTAS for computing the supremum of Gaussian processes. In Proceedings of the 2012 IEEE 53 rd Annual Symposium on Foundations of Computer Science 217-222. IEEE Computer Society, Washington, DC.
[39] Miller, J. and Peres, Y. (2012). Uniformity of the uncovered set of random walk and cutoff for lamplighter chains. Ann. Probab. 40 535-577. · Zbl 1251.60058
[40] Ray, D. (1963). Sojourn times of diffusion processes. Illinois J. Math. 7 615-630. · Zbl 0118.13403
[41] Talagrand, M. (1987). Regularity of Gaussian processes. Acta Math. 159 99-149. · Zbl 0712.60044
[42] Talagrand, M. (2005). The Generic Chaining : Upper and Lower Bounds of Stochastic Processes . Springer, Berlin. · Zbl 1075.60001
[43] Tutte, W. T. and Smith, C. A. B. (1941). On unicursal paths in a network of degree 4. Amer. Math. Monthly 48 233-237. · Zbl 0025.09103
[44] van Aardenne-Ehrenfest, T. and de Bruijn, N. G. (1951). Circuits and trees in oriented linear graphs. Simon Stevin 28 203-217. · Zbl 0044.38201
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.