Mathematics – Probability
Scientific paper
2005-03-08
Annals of Probability 2007, Vol. 35, No. 2, 577-601
Mathematics
Probability
Published at http://dx.doi.org/10.1214/009117906000000854 in the Annals of Probability (http://www.imstat.org/aop/) by the Ins
Scientific paper
10.1214/009117906000000854
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\'{e}v\'{e}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\'{e}v\'{e}sz [Ann. Probab. 21 (1993) 318--328].
Dembo Amir
Peres Yuval
Rosen Jay
No associations
LandOfFree
How large a disc is covered by a random walk in n steps? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with How large a disc is covered by a random walk in n steps?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How large a disc is covered by a random walk in n steps? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-403569