Random Walks


Two simple random walks in the torus.  Points are colored according to occupation measure (left) and hitting time (right).  Pictures created by Raissa D'Souza.



Occupation measure results:

Denote by T(x,r) the occupation measure of a disc of radius r around x by planar Brownian motion run till time 1, and let T(r) be the maximum of T(x,r) over x in the plane. We prove in [1] that T(r) is a.s. asymptotic to 2 r2 |log r|2 as r tends to 0, thus solving a problem posed by Perkins and Taylor (1987). Furthermore, for any a<2, the Hausdorff dimension of the set of points x for which T(x,r) is asymptotic to a r2|log r|2, is almost surely 2-a. As a consequence, we prove a conjecture about planar simple random walk due to Erdős and Taylor (1960):  The number of visits to the most frequently visited lattice site in the first n steps of the walk, is asymptotic to (log n)2/pi. We also show that for a between 0 and 1/pi, the number of points visited more than a(log n)2 times in the first n steps, is approximately n{1-a pi}.


Hitting time results:

Let H(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 in [2] that sup{x} H(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 Zn2 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 Z2 to cover the disc of radius n.


  1. Thick points for planar Brownian motion and the Erdos-Taylor conjecture on random walk. (A. Dembo, Y. Peres, J. Rosen and O. Zeitouni).  Acta Math. 186 no. 2, (2001),  239--270.

  2. Cover Times for Brownian Motion and Random Walks in Two Dimensions. (A. Dembo, Y. Peres, J. Rosen, and O. Zeitouni).  Ann. Math., 160 (2004).

  3. Late Points for Random Walks in Two Dimensions. (A. Dembo, Y. Peres, J. Rosen, O. Zeitouni).  Annals of Probability.  To appear.