Cover times for Brownian motion and random walks in two dimensions

Amir Dembo¹ ; Yuval Peres² ; Jay Rosen³ ; Ofer Zeitouni⁴

¹ Department of Mathematics, Stanford University, Stanford, CA 94305, United States
² Department of Mathematics, University of California, Berkeley, Berkeley, CA 94702, United States
³ Department of Mathematics, College of Staten Island, CUNY, Staten Island, NY 10314, United States
⁴ Mathematics Department, Technion-Israel Institute of Technology, Haifa, 32000, Israel and Department of Mathematics, University of Minnesota, Minneapolis, MN 55455, United States

Annals of mathematics, Tome 160 (2004) no. 2, pp. 433-464

Résumé

Let $\mathcal{T}(x,\varepsilon)$ denote the first hitting time of the disc of radius $\varepsilon$ centered at $x$ for Brownian motion on the two dimensional torus $\mathbb{T}^2$. We prove that $\sup_{x\in \mathbb{T}^2} \mathcal{T}(x,\varepsilon)/|\log \varepsilon|^2 \to 2/\pi$ as $\varepsilon \rightarrow 0$. The same applies to Brownian motion on any smooth, compact connected, two-dimensional, Riemannian manifold with unit area and no boundary. As a consequence, we prove a conjecture, due to Aldous (1989), that the number of steps it takes a simple random walk to cover all points of the lattice torus $\mathbb{Z}_n^2$ is asymptotic to $4n^2(\log n)^2/\pi$. Determining these asymptotics is an essential step toward analyzing the fractal structure of the set of uncovered sites before coverage is complete; so far, this structure was only studied nonrigorously in the physics literature. We also establish a conjecture, due to Kesten and Révész, that describes the asymptotics for the number of steps needed by simple random walk in $\mathbb{Z}^2$ to cover the disc of radius $n$.

Détail

DOI : 10.4007/annals.2004.160.433