Cover times for Brownian motion and random walks in two dimensions. (English) Zbl 1068.60018

Authors’ summary: 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 \to 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 D. Aldous [“Probability approximations via the Poisson clumping heuristic” (1989; Zbl 0679.60013)], 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^2n/\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\).


60D05 Geometric probability and stochastic geometry
60J65 Brownian motion
60G50 Sums of independent random variables; random walks


Zbl 0679.60013
Full Text: DOI arXiv Euclid