How Large A Disc Is Covered By A Random Walk In N Steps?

We show that the largest disc covered by a simple random walk (SRW) on \(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 \(ℓ\), the largest disc completely covered at least \(ℓ\) times by the SRW also has radius n^{1/4+o(1)}. However, the largest disc completely covered by each of \(ℓ\) independent simple random walks on \(Z_2\) after \(n\) steps is only of radius \(n_{1/(2+2\sqrt{ℓ√})+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 \(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].