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

DOI10.1214/009117906000000854MaRDI QIDQ2371949zbMATH OpenOpenAlexFDO

Authors Amir Dembo, Yuval Peres, Jay Rosen

Publication date 9 July 2007

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0503139

zbMATH Keywords

Euclidian disclargest disc coveredlower and upper boundrandom walk

Mathematics Subject Classification ID

Sample path properties (60G17) Sums of independent random variables; random walks (60G50) Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics (82C41)

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'{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+2sqrtell)+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-sqrtalpha)/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].

Review text

Consider a simple random walk (SRW) on \({\mathbb Z}^2\) starting at the origin and run for \(n\) steps. The authors ask for the largest disc covered of the SRW without specifying the center of the disc. In the paper the following four main results are given: (1) one concerning the radius of the largest disc completely covered; (2) one if the disc is required to be multiply covered; (3) one if there are \(\ell\) independent SRW; (4) one concerning the random times in which the SRW is sufficiently inside a completely covered disc. We note that these results solve some problems raised by Révész in 1990 and 1993 [\textit{P. Révész}, Random walk in random and non-random environments, World Scientific (1990; Zbl 0733.60091), \textit{N. J. Teaneck} and \textit{P. Révész}, Ann. Probab. 21, No. 1, 318--328 (1993; Zbl 0770.60034)].

Recommendations

• Clusters of a random walk on the plane
• scientific article; zbMATH DE number 4126434
• Estimates of the largest disc covered by a random walk
• scientific article; zbMATH DE number 863589
• Publication:3484130

Cites work

• A random walk proof of the Erdős-Taylor conjecture
• Clusters of a random walk on the plane
• Cover times for Brownian motion and random walks in two dimensions
• Extremes of the discrete two-dimensional Gaussian free field
• Favourite sites of simple random walk
• scientific article; zbMATH DE number 3911357 (Why is no real title available?)
• scientific article; zbMATH DE number 47625 (Why is no real title available?)
• scientific article; zbMATH DE number 168143 (Why is no real title available?)
• Intersections of random walks.
• Late points for random walks in two dimensions
• Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk

Cited in

(11)

• Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
• Asymptotic entropy of the ranges of random walks on discrete groups
• Geometric structures of late points of a two-dimensional simple random walk
• Exponents for the number of pairs of \(\alpha \)-favorite points of a simple random walk in \(\mathbb{Z}^2\)
• Clusters of a random walk on the plane
• Extremes of the discrete two-dimensional Gaussian free field
• Estimates of the largest disc covered by a random walk
• Random non-overlapping walks of disks on the plane
• scientific article; zbMATH DE number 4155607 (Why is no real title available?)
• Exponent for sets of frequently visited points of a simple random walk in two dimensions
• Dynamic space filling

This page was built for publication: How large a disc is covered by a random walk in \(n\) steps?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2371949)