How large a disc is covered by a random walk in n steps?

Abstract

We show that the largest disc covered by a simple random walk (SRW) on ${\mathbb{Z}}^2$ after n steps has radius n^{1/4+o(1)}, thus resolving an open problem of Révész [Random Walk in Random and Non-Random Environments (1990) World Scientific, Teaneck, NJ]. For any fixed $\ell$, the largest disc completely covered at least $\ell$ times by the SRW also has radius n^{1/4+o(1)}. However, the largest disc completely covered by each of $\ell$ independent simple random walks on ${\mathbb{Z}}^2$ after $n$ steps is only of radius $n^{1/(2+2\sqrt{\ell })+o(1)}$. We complement this by showing that the radius of the largest disc completely covered at least a fixed fraction $\alpha$ of the maximum number of visits to any site during the first $n$ steps of the SRW on ${\mathbb{Z}}^2$, is $n^{(1-\sqrt{\alpha })/4+o(1)}$. We also show that almost surely, for infinitely many values of $n$ it takes about $n^{1/2+o(1)}$ steps after step n for the SRW to reach the first previously unvisited site (and the exponent 1/2 is sharp). This resolves a problem raised by Révész [Ann. Probab. 21 (1993) 318--328].

Published at http://dx.doi.org/10.1214/009117906000000854 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Extremes of the discrete two-dimensional Gaussian free field
• Late points for random walks in two dimensions

Cited by in corpus (5)

• Extremes of the discrete two-dimensional Gaussian free field
• From Maximum of Intervisit Times to Starving Random Walks
• Geometric structures of late points of a two-dimensional simple random walk
• Dynamic Space Filling
• Topics and problems on favorite sites of random walks