On large deviations for the cover time of two-dimensional torus
Christophe Gallesco (UNICAMP)
Serguei Popov (UNICAMP)
Marina Vachkovskaia (UNICAMP)
Abstract
Let $\mathcal{T}_n$ be the cover time of two-dimensional discrete torus $\mathbb{Z}^2_n=\mathbb{Z}^2/n\mathbb{Z}^2$. We prove that $\mathbb{P}[\mathcal{T}_n\leq \frac{4}{\pi}\gamma n^2\ln^2 n]=\exp(-n^{2(1-\sqrt{\gamma})+o(1)})$ for $\gamma\in (0,1)$. One of the main methods used in the proofs is the decoupling of the walker's trace into independent excursions by means of soft local times.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-18
Publication Date: November 6, 2013
DOI: 10.1214/EJP.v18-2856
References
- D. Aldous, J. Fill (2010) Reversible Markov Chains and Random Walks on Graphs. In preparation. http://www.stat.berkeley.edu/~aldous/RWG/book.html
- D. Belius (2013) Gumbel fluctuations for cover times in the discrete torus. To appear in: Probab. Theory Relat. Fields
- I. Benjamini, O. Gurel-Gurevich, B. Morris. Linear cover time is exponentially unlikely. Probab. Theory Relat.\ Fields 155 (2013), 451-461.
- Bramson, Maury; Zeitouni, Ofer. Tightness for a family of recursion equations. Ann. Probab. 37 (2009), no. 2, 615--653. MR2510018
- Dembo, Amir. Favorite points, cover times and fractals. Lectures on probability theory and statistics, 1--101, Lecture Notes in Math., 1869, Springer, Berlin, 2005. MR2228383
- 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
- Dembo, Amir; Peres, Yuval; Rosen, Jay; Zeitouni, Ofer. Late points for random walks in two dimensions. Ann. Probab. 34 (2006), no. 1, 219--263. MR2206347
- Ding, Jian. On cover times for 2D lattices. Electron. J. Probab. 17 (2012), no. 45, 18 pp. MR2946152
- Einmahl, Uwe. Extensions of results of Komlós, Major, and Tusnády to the multivariate case. J. Multivariate Anal. 28 (1989), no. 1, 20--68. MR0996984
- J. Goodman, F. den~Hollander (2012) Extremal geometry of a Brownian porous medium. arXiv:1211.3630
- Kahn, J.; Kim, J. H.; Lovász, L.; Vu, V. H. The cover time, the blanket time, and the Matthews bound. 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), 467--475, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000. MR1931843
- Komlós, J.; Major, P.; Tusnády, G. An approximation of partial sums of independent ${\rm RV}$'s and the sample ${\rm DF}$. I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32 (1975), 111--131. MR0375412
- 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
- Matthews, Peter. Covering problems for Markov chains. Ann. Probab. 16 (1988), no. 3, 1215--1228. MR0942764
- S. Popov, A. Teixeira (2013) Soft local times and decoupling of random interlacements. arXiv:1212.1605
- Shi, Zhan. Problèmes de recouvrement et points exceptionnels pour la marche aléatoire et le mouvement Brownien (d'après Dembo, Peres, Rosen et Zeitouni). (French) [Covering problems and exceptional points for random walks and Brownian motion (after Dembo, Peres, Rosen and Zeitouni)] Séminaire Bourbaki. Vol. 2004/2005. Astérisque No. 307 (2006), ISBN: 978-2-85629-224-2 Exp. No. 951, x, 469--480. MR2296427
- Wilf, Herbert S. The editor's corner: the white screen problem. Amer. Math. Monthly 96 (1989), no. 8, 704--707. MR1019150
This work is licensed under a Creative Commons Attribution 3.0 License.