On cover times for 2D lattices

Jian Ding (Stanford University)


We study the cover time $\tau_{\mathrm{cov}}$ by (continuous-time) random walk on the 2D box of side length $n$ with wired boundary or on the 2D torus,and show that in both cases with probability approaching $1$ as $n$ increases,$\sqrt{\tau_{\mathrm{cov}}}=\sqrt{2n^2 [\sqrt{2/\pi} \log n + O(\log\log n)]$. This improves a result of Dembo, Peres, Rosen, and Zeitouni (2004) and makes progresstowards a conjecture of Bramson and Zeitouni (2009).

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-18

Publication Date: June 16, 2012

DOI: 10.1214/EJP.v17-2089


  • D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  • Aldous, David J. Random walk covering of some special trees. J. Math. Anal. Appl. 157 (1991), no. 1, 271--283. MR1109456
  • Bolthausen, Erwin; Deuschel, Jean-Dominique; Giacomin, Giambattista. Entropic repulsion and the maximum of the two-dimensional harmonic crystal. Ann. Probab. 29 (2001), no. 4, 1670--1692. MR1880237
  • Bramson, Maury; Zeitouni, Ofer. Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field. Comm. Pure Appl. Math. 65 (2012), no. 1, 1--20. MR2846636
  • Bramson, Maury; Zeitouni, Ofer. Tightness for a family of recursion equations. Ann. Probab. 37 (2009), no. 2, 615--653. MR2510018
  • Daviaud, Olivier. Extremes of the discrete two-dimensional Gaussian free field. Ann. Probab. 34 (2006), no. 3, 962--986. MR2243875
  • Dembo, Amir; Peres, Yuval; Rosen, Jay; Zeitouni, Ofer. Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. (2) 160 (2004), no. 2, 433--464. MR2123929
  • J. Ding. Asymptotics of cover times via gaussian free fields: bounded-degree graphs and general trees. Preprint, availabel at erb|http://arxiv.org/abs/1103.4402|.
  • J. Ding, J. Lee, and Y. Peres. Cover times, blanket times, and majorizing measures. Annals of Mathematics. to appear.
  • Ding, Jian; Zeitouni, Ofer. A sharp estimate for cover times on binary trees. Stochastic Process. Appl. 122 (2012), no. 5, 2117--2133. MR2921974 http://arxiv.org/abs/1104.0434
  • Dynkin, E. B. Gaussian and non-Gaussian random fields associated with Markov processes. J. Funct. Anal. 55 (1984), no. 3, 344--376. MR0734803
  • Dynkin, E. B. Local times and quantum fields. Seminar on stochastic processes, 1983 (Gainesville, Fla., 1983), 69--83, Progr. Probab. Statist., 7, Birkhäuser Boston, Boston, MA, 1984. MR0902412
  • Eisenbaum, Nathalie. Une version sans conditionnement du théorème d'isomorphisms de Dynkin. (French) [An unconditioned version of Dynkin's isomorphism theorem] Séminaire de Probabilités, XXIX, 266--289, Lecture Notes in Math., 1613, Springer, Berlin, 1995. MR1459468
  • Eisenbaum, Nathalie; Kaspi, Haya; Marcus, Michael B.; Rosen, Jay; Shi, Zhan. A Ray-Knight theorem for symmetric Markov processes. Ann. Probab. 28 (2000), no. 4, 1781--1796. MR1813843
  • Fernique, X. Regularité des trajectoires des fonctions aléatoires gaussiennes. (French) École d'Été de Probabilités de Saint-Flour, IV-1974, pp. 1--96. Lecture Notes in Math., Vol. 480, Springer, Berlin, 1975. MR0413238
  • Janson, Svante. Gaussian Hilbert spaces. Cambridge Tracts in Mathematics, 129. Cambridge University Press, Cambridge, 1997. x+340 pp. ISBN: 0-521-56128-0 MR1474726
  • Lawler, Gregory F.; Limic, Vlada. Random walk: a modern introduction. Cambridge Studies in Advanced Mathematics, 123. Cambridge University Press, Cambridge, 2010. xii+364 pp. ISBN: 978-0-521-51918-2 MR2677157
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937
  • R. Lyons, with Y. Peres. Probability on Trees and Networks. In preparation. Current version available at texttt http://mypage.iu.edu/~rdlyons/prbtree/book.pdf, 2009.
  • Marcus, Michael B.; Rosen, Jay. Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes. Ann. Probab. 20 (1992), no. 4, 1603--1684. MR1188037
  • Marcus, Michael B.; Rosen, Jay. Gaussian processes and local times of symmetric Lévy processes. Lévy processes, 67--88, Birkhäuser Boston, Boston, MA, 2001. MR1833693
  • Marcus, Michael B.; Rosen, Jay. Markov processes, Gaussian processes, and local times. Cambridge Studies in Advanced Mathematics, 100. Cambridge University Press, Cambridge, 2006. x+620 pp. ISBN: 978-0-521-86300-1; 0-521-86300-7 MR2250510
  • Matthews, Peter. Covering problems for Markov chains. Ann. Probab. 16 (1988), no. 3, 1215--1228. MR0942764
  • Slepian, David. The one-sided barrier problem for Gaussian noise. Bell System Tech. J. 41 1962 463--501. MR0133183

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.