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 Z2 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 Z2 after n steps is only of radius n1/(2+2ℓ√)+o(1). We complement this by showing that the radius of the largest disc completely covered at least a fixed fraction α of the maximum number of visits to any site during the first n steps of the SRW on Z2, is n(1−α√)/4+o(1). We also show that almost surely, for infinitely many values of n it takes about n1/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].