Cover Times for Brownian Motion and Random Walks in Two Dimensions
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Let T(x,r) denote the first hitting time of the disc of radius r centered at x for Brownian motion on the two dimensional torus. We prove that sup_{x} T(x,r)/|log r|^2 --> 2/pi as r --> 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 Z_n^2 is asymptotic to (2n 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 non-rigorously in the physics literature. We also establish a conjecture, due to Kesten and Revesz, that describes the asymptotics for the number of steps needed by simple random walk in Z^2 to cover the disc of radius n.
Conflict between definitions of constants in section 5 cleared on November 26, 2003
Conflict between definitions of constants in section 5 cleared on November 26, 2003