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

Dembo, Amir; Peres, Yuval; Rosen, Jay; Zeitouni, Ofer

Ann. Math. (2) 160, No. 2, 433-464 (2004).

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\).

Reviewer: Aleksander Iksanov (Kiev)

MSC:

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

Citations:

Zbl 0679.60013