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