Cover times for Brownian motion and random walks in two dimensions

Abstract

Let T (x, ) denote the first hitting time of the disc of radius centered at x for Brownian motion on the two dimensional torus T 2 . We prove that sup xT 2 T (x, )/| log | 2 2/ as 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 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 Rvsz, that describes the asymptotics for the number of steps needed by simple random walk in Z 2 to cover the disc of radius n.