Cover times for Brownian motion and random walks in two dimensions

Abstract

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$.

Authors

Amir Dembo

Department of Mathematics, Stanford University, Stanford, CA 94305, United States

Yuval Peres

Department of Mathematics, University of California, Berkeley, Berkeley, CA 94702, United States

Jay Rosen

Department of Mathematics, College of Staten Island, CUNY, Staten Island, NY 10314, United States

Ofer Zeitouni

Mathematics Department, Technion-Israel Institute of Technology, Haifa, 32000, Israel and Department of Mathematics, University of Minnesota, Minneapolis, MN 55455, United States