, , March 5, 2005. * Research partially supported by NSF grant #DMS-0406042 and #DMS-FRG-0244323. † Research partially supported by NSF grants #DMS-0104073 and #DMS-0244479. ‡ Research supported, in part, by grants from the NSF and from PSC-CUNY

Let

T_{r}

denote the time it takes for the simple random walk on

Z^{2}

starting at the origin to completely cover the disc

D (0, r)

of radius

r

centered at the origin (throughout this paper, “disc” refers to the intersection of

Z^{2}

with a Euclidean disc, but all our results apply if one takes a square instead). In [4,Theorem1.4] we proved the following conjecture of Kesten and Révész:

\begin{matrix} {lim}_{r \to \infty} P (log T_{r} \leq t (log r)^{2}) = e^{- 4 / t} . \end{matrix}

(1.1)

In other words, the radius

ρ_{o} (n)

of the largest disc centered at the origin which is covered after

n

steps of the random walk, satisfies

ρ_{o} (n) = exp (\sqrt{Y_{n} log n})

where

{lim}_{n \to \infty} P (Y_{n} \geq y) = e^{- 4 y}

If we ask for the largest disc covered after

n

steps of the walk without specifying the center of the disc, then the answer changes dramatically.

Theorem 1.1. If

ℛ_{n}

denotes the radius of the largest disc completely covered by a simple random walk on

Z^{2}

after

n

steps, then

ℛ_{n} = n^{1 / 4 + o (1)}

a.s., that is,

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{n}}{log n} = \frac{1}{4} a.s. \end{matrix}

(1.2)

The problem of finding the radius of the largest disc completely covered by a simple random walk on

Z^{2}

after

n

steps was first raised by Révész [10,page247] , who later found upper and lower bounds for the ratio

log ℛ_{n} / log n

in [11] . We thank Zhan Shi for informing us of simulations by Arvind Singh which indicated that this ratio tends to

1 / 4

If we require that our disc be multiply covered we obtain the following.

Theorem 1.2. If

ℛ_{n} (k)

denotes the radius of the largest disc completely covered at least

k

times by a simple random walk on

Z^{2}

after

n

steps, then for fixed

k

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{n} (k)}{log n} = \frac{1}{4} a.s. \end{matrix}

(1.3)

while for any

0 < α < 1

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{n} (4 α (log n)^{2} / π)}{log n} = \frac{1 - \sqrt{α}}{4} a.s. \end{matrix}

(1.4)

Note that ( 1.4 ) deals with the largest disc of

α

-favorite sites in

Z^{2}

by time

n

(c.f. [3,Section5] for the number of such sites).

We can generalize Theorem 1.1 by considering

k

independent simple random walks on

Z^{2}

Theorem 1.3. If

ℛ_{n, k}

denotes the radius of the largest disc completely covered by each of

k

independent simple random walks on

Z^{2}

after

n

steps, then

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{n, k}}{log n} = \frac{1}{2 + 2 \sqrt{k}} a.s. \end{matrix}

(1.5)

We can also solve a related problem raised by Révész in [11] .

Theorem 1.4. If

V_{n}

is the number of steps after step

n

until the simple random walk on

Z^{2}

first visits any of the previously unvisited sites, then

\begin{matrix} {limsup}_{n \to \infty} \frac{log V_{n}}{log n} = \frac{1}{2} a.s. \end{matrix}

(1.6)

Of course

{liminf}_{n \to \infty} V_{n} = 1

We note in passing that the situation is quite different for the simple random walk on

Z^{d}

for

d \geq 3

, where due to the transience of the process, one has that

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{n}}{log log n} = \frac{1}{d - 2}, a.s. \end{matrix}

(1.7)

as shown in [6] , and for

d = 1

, where

2 ℛ_{n}

is the difference between the maximum and the minimum of the walk, which upon scaling by

n^{- 1 / 2}

converges in law to an explicit non-degenerate limit (for finer information on the favorite sites in one dimension, see [1] ).

We now explain the intuitive picture behind Theorem 1.1 . Let

ρ_{k} = e^{k}

and for any

x \in Z^{2}

consider the family of discs centered at

x

{D (x, ρ_{k}); k = 0, 1, \dots, m}

. Starting from

\partial D (x, ρ_{β m})

, the probability of reaching

\partial D (x, ρ_{β m - 1})

before exiting

D (x, ρ_{m})

1 - 1 / ((1 - β) m)

, so that the probability of making

a (1 - β)^{2} m^{2}

excursions from

\partial D (x, ρ_{β m})

\partial D (x, ρ_{β m - 1})

before exiting

D (x, ρ_{m})

(referred to as

β

-excursions) is about

e^{- a (1 - β) m}

. Since there are about

e^{2 (1 - β) m}

disjoint discs of radius

ρ_{β m}

D (0, ρ_{m})

, ignoring the fact that they have different centers, we expect that the maximal number of

β

-excursions among all disc of radius

ρ_{β m}

will be about

2 (1 - β)^{2} m^{2}

On the other hand, the probability of not hitting the center of a disc during one

β

-excursion is

1 - 1 / (β m)

, so that the probability of not hitting the center during

c β^{2} m^{2}

β

-excursions is about

e^{- c β m}

. Since there are about

e^{2 β m}

points in

D (x, ρ_{β m})

, ignoring the fact that they are not centered, the expected number of points not visited during

c β^{2} m^{2}

β

-excursions is about

e^{(2 - c) β m}

. Hence about

2 β^{2} m^{2}

β

-excursions are needed for the random walk to visit all sites in a disc

D (x, ρ_{β m})

To find the maximal possible value of

β

for which some disc of radius

ρ_{β m}

is covered by the walk, equate

2 (1 - β)^{2} m^{2}

and

2 β^{2} m^{2}

to get

β = 1 / 2

. Since it takes about

O (ρ_{m}^{2})

steps for the walk to exit

D (0, ρ_{m})

we obtain Theorem 1.1 by setting

n = ρ_{m}^{2}

, so

ρ_{m / 2} = n^{1 / 4}

Similar reasoning predicts the results of Theorem 1.2 and Theorem 1.3 . To prove these, one needs non-trivial modifications of the classical second moment method. Fortunately, adapting the `multi-scale refinement' machinery of [3, 4, 5] to the present context, provides the necessary ingredients for proving these results. Indeed, in Sections 2 and 3 we prove the bounds on

ℛ_{n}

for Theorem 1.1 (lower bounds and upper bounds, respectively), and in Sections 5 and 6 , extend these bounds to the setting of Theorem 1.2 , whereas Section 4 extend both bounds to the setting of Theorem 1.3 .

Finally, Section 7 is devoted to the derivation of Theorem 1.4 .

Though we deal here exclusively with the simple random walk on

Z^{2}

, similar results apply for the whole class of random walks considered in [3,Theorem5.1] upon appropriately modifying the relevant proofs. We note in passing that this work inspired Daviaud's analogous treatment of extremal points of the discrete Gaussian free field in the box

[- n, n]^{2}

subject to zero boundary conditions, where for example the size of the largest sub-box of

α

-high points of the field corresponds to ( 1.4 ) here (see [2] for details).

2 The lower bound for Theorem 1.1

Let

θ_{n}

be the number of steps until the simple random walk first exits

D (0, n)

. Since

\begin{matrix} {lim}_{n \to \infty} \frac{log θ_{n}}{log n} = 2, a.s. \end{matrix}

(2.1)

Theorem 1.1 is equivalent to the following theorem.

Theorem 2.1. If

ℛ_{n}

denotes the radius of the largest disc completely covered by simple random walk on

Z^{2}

after

n

steps, then

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{θ_{n}}}{log n} = \frac{1}{2} a.s. \end{matrix}

(2.2)

We shall thus prove Theorem 2.1 instead of directly proving Theorem 1.1 . To this end, let

S_{n}, n \geq 0

denote the simple random walk (SRW) on

Z^{2}

with

D (x, r) = {y \in Z^{2} : | y - x | < r}

denoting the disc of radius

r

centered at

x

. For any set

A \subseteq Z^{2}

we let

\partial A = {y \in Z^{2} : y / \in A, and {inf}_{x \in A} | y - x | = 1}

denote the boundary of

A

Z^{2}

and

T_{A} = inf {i \geq 0 : S_{i} \in A}

the hitting time of

A

, so in particular

θ_{n} = T_{\partial D (0, n)}

. Hereafter we let

r_{0} = 0

and

r_{k} = (k!)^{3}

for

k \geq 1

. Using the monotonicity of

n \mapsto ℛ_{θ_{n}}

and the fact that

{lim}_{n \to \infty} log r_{n} / log r_{n - 1} = 1

, it follows by a simple interpolation argument that ( 2.2 ) is an immediate consequence of

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{θ_{r_{n}}}}{log r_{n}} = \frac{1}{2} a.s. \end{matrix}

(2.3)

We proceed to provide here the relevant lower bound

\begin{matrix} {liminf}_{n \to \infty} \frac{log ℛ_{θ_{r_{n}}}}{log r_{n}} \geq \frac{1}{2} a.s. \end{matrix}

(2.4)

deferring the corresponding upper bound to Section 3 . It actually suffices to prove that for any

η > 0

and all sufficiently large

n

\begin{matrix} P (\frac{log ℛ_{θ_{8 r_{n}}}}{log r_{n}} \geq \frac{1}{2} - 2 η) \geq p_{η} > 0 . \end{matrix}

(2.5)

Indeed, then for all

n

large enough,

P (\frac{log ℛ_{θ_{r_{n}}}}{log r_{n + 1}} \leq \frac{1}{2} - 3 η) \leq 1 - p_{η} < 1 .

Further, with

ℛ_{[s, t]}

denoting the radius of the largest disc completely covered by

{S_{i} : i = s, \dots, t}

, we have that

ℛ_{θ_{r_{n + 1}}} \geq max {ℛ_{[θ_{(k - 1) r_{n}}, θ_{k r_{n}}]} : k = 1, \dots, n^{3}} .

So, by the strong Markov property of the SRW at the successive stopping times

θ_{k r_{n}}, k = 1, 2, \dots

and the fact that

D (S_{θ_{(k - 1) r_{n}}}, r_{n}) \subseteq D (0, k r_{n})

, we get that

P (\frac{log ℛ_{θ_{r_{n + 1}}}}{log r_{n + 1}} \leq \frac{1}{2} - 3 η) \leq (1 - p_{η})^{n^{3}} .

Consequently, an application of the Borel-Cantelli lemma, followed by taking

η ↓ 0

yields the bound of ( 2.4 ).

Turning to the proof of ( 2.5 ), we next construct a subset of the event appearing in ( 2.5 ), the probability of which is easier to bound below. To this end, let

r_{n, k} = (n!)^{3} / (k!)^{3}, k = 1, \dots, n

so that

r_{n, 1} = r_{n} = (n!)^{3}

and

r_{n, n} = 1

. Then, fixing

a > 0

we set

n_{k} = n_{k} (a) = 3 a k^{2} log k

for

3 \leq k \leq n - 1

and for any

x \in Z^{2}

, let

N_{n, k}^{x}

denote the number of excursions of

{S_{i}}

from

\partial D (x, r_{n, k})

\partial D (x, r_{n, k - 1})

until time

T_{\partial D (0, 8 r_{n})}

. Further, fixing

0 < β < 1

, let

ℋ_{β n}^{x}

be the event that the SRW visits each point in

D (x, r_{n, β n + 1})

during the first

N_{n, β n}^{x}

excursions from

\partial D (x, r_{n, β n})

\partial D (x, r_{n, β n - 1})

. We say that a point

x \in Z^{2}

n, β

-successful if

\begin{matrix} ℋ_{β n}^{x} occurs and n_{k} (a) - k \leq N_{n, k}^{x} \leq n_{k} (a) + k for k = 3, \dots, β n . \end{matrix}

(2.6)

Let

A_{n} \subseteq Z^{2}

be a maximal collection of points in

[3 r_{n}, 4 r_{n}]^{2}

such that the distance between any two points in

A_{n}

is at least

4 r_{n, β n}

The existence of an

n, β

-successful point in

A_{n}

implies that

ℛ_{θ_{8 r_{n}}} \geq r_{n, β n + 1}

. Noting that

log r_{n, β n + 1} \sim 3 (1 - β) n log n

and

log r_{n} \sim 3 n log n

(with the convention that

a_{n} \sim b_{n}

iff

a_{n} / b_{n} \to 1

n \to \infty

), we thus establish ( 2.5 ) by showing that for

β = 1 / 2 + η > 1 / 2

and

a = a (β) < 2

such that

\begin{matrix} a β^{2} > 2 (1 - β)^{2}, \end{matrix}

(2.7)

the probability that there is at least one

n, β

-successful point in

A_{n}

is bounded away from zero as

n \to \infty

As we will show, the fact that

a < 2

guarantees that with a probability that is bounded away from zero as

n \to \infty

, there exists at least one

x \in A_{n}

for which

n_{k} (a) - k \leq N_{n, k}^{x} \leq n_{k} (a) + k

k = 3, \dots, β n

, and the relation ( 2.7 ) guarantees that with very high probability

ℋ_{β n}^{x}

then holds as well.

Let

Y (n, x)

be the indicator random variable for the event

{x

n, β

-successful

}

, so we have ( 2.5 ) as soon as we show that for any

δ > 0

and all

n

sufficiently large,

\begin{matrix} P (\sum_{x \in A_{n}} Y (n, x) \geq r_{β n}^{2 - a - δ}) \geq c_{δ} > 0 \end{matrix}

(2.8)

Note that

| A_{n} | = r_{n}^{2} / (16 r_{n, β n}^{2}) = r_{β n}^{2} / 16

so that by ( 2.12 ) of the next lemma below

\begin{matrix} E (\sum_{x \in A_{n}} Y (n, x)) = (1 + o (1_{n})) \sum_{x \in A_{n}} {\bar{q}}_{n} \geq r_{β n}^{2 - a - δ_{n}} . \end{matrix}

(2.9)

(Here and below,

f (n) = o (1_{n})

means that

{lim}_{n \to \infty} f (n) = 0

Applying the Paley-Zygmund inequality (see [7,page8] ), it thus suffices to show that

\begin{matrix} E ({\sum_{x \in A_{n}} Y (n, x)}^{2}) \leq C {E (\sum_{x \in A_{n}} Y (n, x))}^{2} \end{matrix}

(2.10)

for some

C < \infty

and all

n

sufficiently large. Furthermore, by ( 2.9 )

E (\sum_{x \in A_{n}} Y (n, x))

tends to

\infty

, so it suffices to show that

\begin{matrix} E (\sum_{\overset{x, y \in A_{n}}{x \neq y}} Y (n, x) Y (n, y)) \leq C {E (\sum_{x \in A_{n}} Y (n, x))}^{2} \end{matrix}

(2.11)

The next lemma will be proven at the end of this section.

Lemma 2.2. Assume that

a, β

satisfy ( 2.7 ). Then there exists

δ_{n} \to 0

such that

\begin{matrix} {\bar{q}}_{n} = : P ((2 r_{n}, 0) is n, β -successful) \geq r_{β n}^{- (a + δ_{n})} \end{matrix}

(2.12)

and uniformly in

x \in A_{n}

\begin{matrix} P (x is n, β -successful) = (1 + o (1_{n})) {\bar{q}}_{n} . \end{matrix}

(2.13)

Let

l (x, y) = min {m : D (x, r_{n, m}) \cap D (y, r_{n, m}) = \emptyset}

. For all

n

and

x, y \in A_{n}

with

1 \leq l (x, y) \leq β n

\begin{matrix} P (x, y are n, β -successful) \leq {\bar{q}}_{n}^{2} r_{l (x, y)}^{a + δ_{l (x, y)}} . \end{matrix}

(2.14)

We return to the proof of ( 2.5 ). In the sequel, we let

C_{m}

denote finite constants that are independent of

n

. The definition of

l (x, y) \geq 1

implies that

2 r_{n, l (x, y)} \leq | x - y | \leq 2 r_{n, l (x, y) - 1} .

Note that there are at most

C_{0} r_{n, l - 1}^{2} / r_{n, β n}^{2} = C_{0} r_{β n}^{2} / r_{l - 1}^{2} = C_{0}^{'} | A_{n} | r_{l - 1}^{- 2}

points

y \in A_{n}

in the ball of radius

2 r_{n, l - 1}

centered at

x

. Thus, it follows from Lemma 2.2 that

\begin{matrix} \sum_{\overset{x, y \in A_{n}}{1 \leq l (x, y) \leq β n}} E (Y (n, x) Y (n, y)) & \leq & C_{1} \sum_{\overset{x, y \in A_{n}}{1 \leq l (x, y) \leq β n}} {\bar{q}}_{n}^{2} r_{l (x, y)}^{a + γ} \end{matrix}

\begin{matrix} \leq & C_{2} {\bar{q}}_{n}^{2} | A_{n} |^{2} \sum_{l = 1}^{β n} r_{l - 1}^{- 2} r_{l}^{a + γ} \leq C_{2} (| A_{n} | {\bar{q}}_{n})^{2} \sum_{l = 1}^{β n} r_{l}^{- (2 - a - 2 γ)} \end{matrix}

\begin{matrix} \leq & C_{2} (| A_{n} | {\bar{q}}_{n})^{2} \sum_{j = 1}^{\infty} r_{j}^{- (2 - a - 2 γ)} \leq C_{3} {E \sum_{x \in A_{n}} Y (n, x)}^{2} . \end{matrix}

(In the second inequality we chose

γ > 0

so that

2 - a - 2 γ > 0

This completes the proof of ( 2.5 ).

Proof of Lemma 2.2 : We say that a point

x \in A_{n} \subseteq Z^{2}

n, β

-pre-successful if

n_{k} (a) - k \leq N_{n, k}^{x} \leq n_{k} (a) + k for k = 3, \dots, β n .

The proof of Lemma 3.2 of [12] establishes the analog of the statements ( 2.12 )–( 2.14 ) with

n, β

-successful replaced by

n, β

-pre-successful,

β = 1

and where instead of

r_{n, k}

we have

n^{3 (n - k)} e^{n}

. This proof works just as well for our choice of

β

and

r_{n, k}

. Since an

n, β

-successful point is also

n, β

-pre-successful this establishes the upper bound of ( 2.14 ). It thus remains only to show that uniformly in

x

\begin{matrix} P (x is n, β -successful) = (1 + o (1_{n})) P (x is n, β -pre-successful) . \end{matrix}

(2.15)

To this end, let

ℒ_{z, n, β}

denote the event that

z

is not visited during the first

n_{β n} - β n

excursions from

\partial D (x, r_{n, β n})

\partial D (x, r_{n, β n - 1})

. We first show that

\begin{matrix} ξ_{n} = {sup}_{x \in A_{n}} P (⋃_{z \in D (x, r_{n, β n + 1})} ℒ_{z, n, β}) \to 0 as n \to \infty . \end{matrix}

(2.16)

To see this, note that for

x \in A_{n}

\begin{matrix} P (⋃_{z \in D (x, r_{n, β n + 1})} ℒ_{z, n, β}) \leq r_{n, β n + 1}^{2} {sup}_{z \in D (x, r_{n, β n + 1})} P (ℒ_{z, n, β}), \end{matrix}

(2.17)

and

\begin{matrix} P (ℒ_{z, n, β}) \leq {({sup}_{y \in \partial D (x, r_{n, β n})} P^{y} (T_{z} > T_{\partial D (x, r_{n, β n - 1})}))}^{n_{β n} - β n} . \end{matrix}

(2.18)

Now

\begin{matrix} {inf}_{y \in \partial D (x, r_{n, β n})} P^{y} (T_{z} < T_{\partial D (x, r_{n, β n - 1})}) \end{matrix}

(2.19)

\begin{matrix} \geq {inf}_{y \in \partial D (z, r_{n, β n} + | z - x |)} P^{y} (T_{z} < T_{\partial D (z, r_{n, β n - 1} - | z - x |)}) \end{matrix}

\begin{matrix} = \frac{log ((r_{n, β n - 1} - | z - x |) / (r_{n, β n} + | z - x |)) + O (n^{- 1})}{log (r_{n, β n - 1} - | z - x |)} \end{matrix}

\begin{matrix} \geq \frac{1 - δ^{'}}{(1 - β) n} \end{matrix}

where we have used Proposition 1.6.7 of [8] . Hence by ( 2.18 )

\begin{matrix} P (ℒ_{z, n, β}) \leq {(1 - \frac{1 - δ^{'}}{(1 - β) n})}^{n_{β n} - β n} \leq e^{- (1 - 2 δ^{'}) 3 a β^{2} n log n / (1 - β)} . \end{matrix}

(2.20)

Since

r_{n, β n + 1}^{2} \leq e^{2 (1 + δ^{'}) 3 (1 - β) n log n}

, ( 2.16 ) now follows from ( 2.17 ), ( 2.20 ) and ( 2.7 ) for

δ^{'}

sufficiently small.

We will write

N \overset{k}{\sim} n_{k}

| N - n_{k} | \leq k

. If

G_{β n}^{x}

denotes the

σ

-algebra generated by all the excursions from

\partial D (x, r_{n, β n})

\partial D (x, r_{n, β n - 1})

and

ℋ_{β n}^{x}

denotes the event that the random walk visits each point in

D (x, r_{n, β n + 1})

during the first

N_{n, β n}^{x}

excursions from

\partial D (x, r_{n, β n})

\partial D (x, r_{n, β n - 1})

, then using Lemma 2.4 of [5] and then ( 2.16 ), we have that for any

m \overset{β n}{\sim} n_{β n}

and

x \in A_{n}

\begin{matrix} P (ℋ_{β n}^{x} | G_{β n}^{x}, N_{n, β n}^{x} = m) = (1 + o (1_{n})) (1 - ξ_{n}) \to 1 \end{matrix}

(2.21)

n \to \infty

. Since

{N_{n, k}^{x} \overset{k}{\sim} n_{k}, \forall k \in [3, β n]} \in G_{β n}^{x}

we deduce that

\begin{matrix} P (x is n, β -successful) = P (N_{n, k}^{x} \overset{k}{\sim} n_{k}, \forall k \in [3, β n]; ℋ_{β n}^{x}) \end{matrix}

(2.22)

\begin{matrix} = \sum_{m \overset{β n}{\sim} n_{β n}} P (N_{n, k}^{x} \overset{k}{\sim} n_{k}, \forall k \in [3, β n - 1]; N_{n, β n}^{x} = m; ℋ_{β n}^{x}) \end{matrix}

\begin{matrix} = (1 + o (1_{n})) (1 - ξ_{n}) P (N_{n, k}^{x} \overset{k}{\sim} n_{k}, \forall k \in [3, β n]) . \end{matrix}

by ( 2.21 ). Therefore,

P (x is n, β -successful) = (1 + o (1_{n})) P (N_{n, k}^{x} \overset{k}{\sim} n_{k}, \forall k \in [3, β n]),

which amounts to ( 2.15 ).

3 The Upper Bound for Theorem 1.1

In this section we establish the upper bound for ( 2.3 ):

\begin{matrix} {limsup}_{n \to \infty} \frac{log ℛ_{θ_{r_{n}}}}{log r_{n}} \leq 1 / 2 a.s. \end{matrix}

(3.1)

Fix

0 < β < 1

. We begin by describing a two-tiered collection of discs in

D (0, r_{n})

. Let

ℬ_{n, 2}

be a maximal collection of points in

D (0, r_{n - 1})

such that the discs

{D (x_{i}, r_{β n + 2}); x_{i} \in ℬ_{n, 2}}

are disjoint. For each

x \in ℬ_{n, 2}

, let

ℬ_{n, 1} (x)

be a maximal collection of points such that the discs

{D (y_{i}, r_{β n}); y_{i} \in ℬ_{n, 1} (x)}

are disjoint and contained in

D (x, r_{β n + 2})

. Let

ℬ_{n, 1} = \cup_{x \in ℬ_{n, 2}} ℬ_{n, 1} (x)

For any

y \in ℬ_{n, 1}

, we let

N_{n} (y)

denote the number of excursions from

\partial D (y, r_{β n - 1})

\partial D (y, r_{β n})

until time

θ_{r_{n}}

. Fix

a > 0

and recall the notation

n_{k} = 3 a k^{2} log (k)

. Let

\begin{matrix} G_{n} = ⋂_{y \in ℬ_{n, 1}} {N_{n} (y) \leq n_{(1 - β) n}} . \end{matrix}

(3.2)

The following lemma will be proven below.

Lemma 3.1. For any

a > 2

we can find

ζ = ζ (a, β) > 0

such that

\begin{matrix} P (G_{n}) = 1 - O (e^{- ζ n}) . \end{matrix}

(3.3)

For any

D (x, r) \subseteq Z^{2}

, let

C (x, r)

denote the number of steps needed to cover

D (x, r)

. Note that if the walk covers some disc of radius

r_{β n + 3}

with center in

D (0, r_{n - 1})

, then for some

x \in ℬ_{n, 2}

it covers

D (x, r_{β n + 2})

. It is therefore easy to see that our upper bound will follow once we show that for any

1 / 2 < β < 1

\begin{matrix} \sum_{n = 5}^{\infty} P (⋃_{x \in ℬ_{n, 2}} {C (x, r_{β n + 2}) \leq θ_{r_{n}}}) < \infty . \end{matrix}

(3.4)

By Lemma 3.1 it suffices to show that

\begin{matrix} \sum_{n = 5}^{\infty} P (⋃_{x \in ℬ_{n, 2}} {C (x, r_{β n + 2}) \leq θ_{r_{n}}} | G_{n}) < \infty . \end{matrix}

(3.5)

We have

\begin{matrix} P (⋃_{x \in ℬ_{n, 2}} {C (x, r_{β n + 2}) \leq θ_{r_{n}}} | G_{n}) \leq \sum_{x \in ℬ_{n, 2}} P (C (x, r_{β n + 2}) \leq θ_{r_{n}} | G_{n}) . \end{matrix}

(3.6)

Since

| ℬ_{n, 2} | = O (e^{n^{2}})

, ( 3.5 ) will follow from the next lemma.

Lemma 3.2. Fix

1 / 2 < β < 1

. Uniformly for

x \in ℬ_{n, 2}

\begin{matrix} P (C (x, r_{β n + 2}) \leq θ_{r_{n}} | G_{n}) \leq e^{- n^{3}} . \end{matrix}

(3.7)

Proof of Lemma 3.2 : Clearly

\begin{matrix} {C (x, r_{β n + 2}) \leq θ_{r_{n}}} \subseteq ⋂_{y \in ℬ_{n, 1} (x)} {C (y, r_{β n - 2}) \leq θ_{r_{n}}} . \end{matrix}

(3.8)

Let

\tilde{C} (y, r_{β n - 2}; m)

denote the event that

D (y, r_{β n - 2})

is covered in the first

m

excursions from

\partial D (y, r_{β n - 1})

\partial D (y, r_{β n})

. Using Lemma 2.4 of [5] , ( 3.8 ) implies that

\begin{matrix} P (C (x, r_{β n + 2}) \leq θ_{r_{n}} | G_{n}) \leq \prod_{y \in ℬ_{n, 1} (x)} (1 + o (1_{n})) P (\tilde{C} (y, r_{β n - 2}; n_{(1 - β) n})) . \end{matrix}

(3.9)

Fix

y \in ℬ_{n, 1}

. Note that for any

1 / 2 < β < 1

we can choose

a > 2

such that

\begin{matrix} a (1 - β)^{2} < 2 β^{2} . \end{matrix}

(3.10)

We will show that uniformly for

y \in ℬ_{n, 1} (x)

and

x \in ℬ_{n, 2}

\begin{matrix} P (\tilde{C} (y, r_{β n - 2}; n_{(1 - β) n})) = o (1_{n}) \end{matrix}

(3.11)

Since

| ℬ_{n, 1} (x) | \geq n^{4}

, our lemma will follow.

To prove ( 3.11 ) we begin by applying (3.19) of [5] with

R = r_{β n}, r = r_{β n - 1}

and

N = n_{(1 - β) n} = 3 a (1 - β)^{2} n^{2} log (1 - β) n \leq 3 (2 - 2 ε) β^{2} n^{2} log β n

for some

ε > 0

by ( 3.10 ) to see that with probability

1 - o (1_{n})

the number of steps it takes for

N

excursions from

\partial D (y, r_{β n - 1})

\partial D (y, r_{β n})

Z_{r_{β^{'} n}}^{2}

with

β^{'} > β

is less than

T = (4 - ε) (r_{β^{'} n} log r_{β^{'} n})^{2} / π

. It follows from Theorem 1.2 of [5] that for

β^{'}

sufficiently close to

β

the probability of covering

D (y, r_{β n - 2})

Z_{r_{β^{'} n}}^{2}

T

steps is

o (1_{n})

. Thus, the probability of covering

D (y, r_{β n - 2})

during the first

N

excursions from

\partial D (y, r_{β n - 1})

\partial D (y, r_{β n})

Z_{r_{β^{'} n}}^{2}

o (1_{n})

. We, however, are interested in excursions in

Z^{2}

. Now, in either case, conditional on their beginning and end points the excursions are independent. Lemma 2.4 of [5] shows that the probability we are considering is, up to a factor

1 + o (1_{n})

, independent of the beginning and end points of the excursions. This completes the proof of ( 3.11 ) and hence of our lemma.

Proof of Lemma 3.1 : The proof is similar to that of Lemma 2.2 . We have to show that for some

ζ = ζ (a, β) > 0

\begin{matrix} {lim}_{n \to \infty} P (⋃_{y \in ℬ_{n, 1}} {N_{n} (y) > n_{(1 - β) n}}) = O (e^{- ζ n}) . \end{matrix}

(3.12)

To see this, note that

\begin{matrix} P (⋃_{y \in ℬ_{n, 1}} {N_{n} (y) > n_{(1 - β) n}}) \leq | ℬ_{n, 1} | {sup}_{y \in ℬ_{n, 1}} P (N_{n} (y) > n_{(1 - β) n}), \end{matrix}

(3.13)

and

\begin{matrix} P (N_{n} (y) > n_{(1 - β) n}) \leq {({sup}_{x \in \partial D (y, r_{β n})} P^{x} (T_{\partial D (0, r_{n})} > T_{\partial D (y, r_{β n - 1})}))}^{n_{(1 - β) n}} . \end{matrix}

(3.14)

Now

\begin{matrix} {inf}_{x \in \partial D (y, r_{β n})} P^{x} (T_{\partial D (0, r_{n})} < T_{\partial D (y, r_{β n - 1})}) \end{matrix}

(3.15)

\begin{matrix} \geq {inf}_{x \in \partial D (y, r_{β n})} P^{x} (T_{\partial D (y, r_{n} + | y |)} < T_{\partial D (y, r_{β n - 1})}) \end{matrix}

\begin{matrix} = \frac{log (r_{β n} / r_{β n - 1}) + O (n^{- 1})}{log ((r_{n} + | y |) / r_{β n - 1})} \end{matrix}

\begin{matrix} \geq \frac{1 - δ^{'}}{(1 - β) n} \end{matrix}

where we have used Exercise 1.6.8 of [8] . Hence by ( 3.14 )

\begin{matrix} P (N_{n} (y) > n_{(1 - β) n}) \leq {(1 - \frac{1 - δ^{'}}{(1 - β) n})}^{n_{(1 - β) n}} \leq e^{- (1 - 2 δ^{'}) 3 a (1 - β) n log n} . \end{matrix}

(3.16)

Since

| ℬ_{n, 1} | \leq e^{2 (1 + δ^{'}) 3 (1 - β) n log n}

, ( 3.12 ) now follows from ( 3.13 ) and ( 3.16 ) for

δ^{'}

sufficiently small.

4 Proof of Theorem 1.3

Let

S_{n}^{j}, n \geq 0, 1 \leq j \leq l

denote

l

independent simple random walks (SRW) on

Z^{2}

. Let

θ_{n}^{j}

be the number of steps until the simple random walk

S_{n}^{j}

first exits

D (0, n)

and set

θ_{n, l} = (θ_{n}^{1}, \dots, θ_{n}^{l})

As before, Theorem 1.3 is equivalent to

Theorem 4.1. If

ℛ_{θ_{n, l}}

denotes the radius of the largest disc completely covered by each of

l

independent simple random walks in

Z^{2}

run until it first exits

D (0, n)

, then

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{θ_{n}, l}}{log n} = 1 / (1 + \sqrt{l}) a.s. \end{matrix}

(4.1)

Using our previous notation, we can show as before that the lower bound for ( 4.1 ) will follow once we can show that for any

δ > 0

and sufficiently large

n

\begin{matrix} P (\frac{log ℛ_{θ_{8 r_{n}, l}}}{log r_{n}} \geq 1 / (1 + \sqrt{l}) - δ) \geq p_{δ} > 0 . \end{matrix}

(4.2)

For

x \in Z^{2}

3 \leq k \leq n - 1

and

1 \leq j \leq l

let

N_{n, k}^{x, j}

denote the number of excursions of the

j

'th random walk from

\partial D (x, r_{n, k})

\partial D (x, r_{n, k - 1})

until time

T_{\partial D (0, 8 r_{n})}

. Fix

a > 0

and set

n_{k} = 3 a k^{2} log k

Fix

0 < β < 1

. We will say that a point

x \in Z^{2}

n, β, l

-successful if the following two conditions hold:

$∙$ $n_{k} - k \leq N_{n, k}^{x, j} \leq n_{k} + k, \forall k = 3, \dots, β n, and \forall j = 1, \dots, l .$
$∙$ Each point in $D (x, r_{n, β n + 1})$ is visited during the first $N_{n, β n}^{x, j} (1)$ excursions from $\partial D (x, r_{n, β n})$ to $\partial D (x, r_{n, β n - 1})$ for all $j = 1, \dots, l$ .

As before,

A_{n} \subseteq Z^{2}

be a maximal collection of points in

[3 r_{n}, 4 r_{n}]^{2}

such that the distance between any two points in

A_{n}

is at least

4 r_{n, β n}

. Note that

log r_{n, β n + 1} \sim 3 (1 - β) n log n

and

log r_{n} \sim 3 n log n

Thus, by showing that with positive probability there is at least one

n, β, l

-successful point in

A_{n}

for

β > 1 - 1 / (1 + \sqrt{l})

sufficiently close to

1 - 1 / (1 + \sqrt{l})

we establish ( 4.2 ).

We will choose

a, β

so that

\begin{matrix} a β^{2} > 2 (1 - β)^{2} . \end{matrix}

(4.3)

As before, this will guarantee that the second condition in the definition of

n, β, l

-successful is satisfied. Then we will see that

a < 2 / l

guarantees the existence of at least one

n, β, l

-successful point in

A_{n}

. Noting that we can take

β ↓ 1 - 1 / (1 + \sqrt{l})

a ↑ 2 / l

, the argument of the previous paragraph then establishes ( 4.2 ).

Arguing as before, the existence of at least one

n, β, l

-successful point in

A_{n}

, and hence ( 4.2 ) follows from the next Lemma if

a < 2 / l

Lemma 4.2. Assume that

a, β

satisfy ( 4.3 ). Then there exists

δ_{n} \to 0

such that

\begin{matrix} {\bar{q}}_{n, l} = : P ((2 r_{n}, 0) is n, β, l -successful) \geq r_{β n}^{- (a l + δ_{n})} \end{matrix}

(4.4)

and

\begin{matrix} P (x is n, β, l -successful) = (1 + o (1_{n})) {\bar{q}}_{n, l} . \end{matrix}

(4.5)

uniformly in

x \in A_{n}

Let

l (x, y) = min {m : D (x, r_{n, m}) \cap D (y, r_{n, m}) = \emptyset}

. For all

n

and

x, y \in A_{n}

with

1 \leq l (x, y) \leq β n

\begin{matrix} E (x, y are n, β, l -successful) \leq {\bar{q}}_{n, l}^{2} r_{l (x, y)}^{a l + δ_{l (x, y)}} . \end{matrix}

(4.6)

The proof of this Lemma follows easily from the proof of Lemma 2.2 . Just as before, ( 4.3 ) guarantees that the second condition in the definition of

n, β, l

-successful doesn't affect the probabilities, while the fact that the first condition involves

l

independent walks raises the probabilities to the

l

'th power. This completes the proof of the lower bound for ( 4.1 ).

We turn next to the upper bound for ( 4.1 ):

\begin{matrix} {limsup}_{n \to \infty} \frac{log ℛ_{θ_{r_{n}, l}}}{log r_{n}} \leq 1 / (1 + \sqrt{l}) a.s. \end{matrix}

(4.7)

Fix

0 < β < 1

. We use the same two-tiered collection of discs in

D (0, r_{n})

as before. For any

y \in ℬ_{n, 1}

, we let

N_{n}^{j} (y)

denote the number of excursions of the

j

'th walk from

\partial D (y, r_{β n - 1})

\partial D (y, r_{β n})

until time

θ_{r_{n}}^{j}

. Fix

a > 0

and recall the notation

n_{k} = 3 a k^{2} log (k)

. Let

\begin{matrix} G_{n, l} = {⋂_{y \in ℬ_{n, 1}}}^{l} ⋃_{j = 1} {N_{n}^{j} (y) \leq n_{(1 - β) n}} . \end{matrix}

(4.8)

The following lemma will be proven below.

Lemma 4.3. For any

a > 2 / l

we can find

ζ = ζ (a, β) > 0

such that

\begin{matrix} P (G_{n, l}) = 1 - O (e^{- ζ n}) . \end{matrix}

(4.9)

For any

D (x, r) \subseteq Z^{2}

, let

C_{l} (x, r)

denote the number of steps until each of our

l

independent walks cover

D (x, r)

. Note that if all

l

walks cover some disc of radius

r_{β n + 3}

with center in

D (0, r_{n - 1})

, then for some

x \in ℬ_{n, 2}

they all cover

D (x, r_{β n + 2})

. It is therefore easy to see that our upper bound will follow once we show that for any

1 / (1 + \sqrt{l}) < β < 1

\begin{matrix} \sum_{n = 5}^{\infty} P (⋃_{x \in ℬ_{n, 2}} {C_{l} (x, r_{β n + 2}) \leq θ_{r_{n}, l}}) < \infty . \end{matrix}

(4.10)

As before, this will follow from the next lemma.

Lemma 4.4. Fix

1 / (1 + \sqrt{l}) < β < 1

. Uniformly for

x \in ℬ_{n, 2}

\begin{matrix} P (C_{l} (x, r_{β n + 2}) \leq θ_{r_{n}, l} | G_{n, l}) \leq e^{- n^{3}} . \end{matrix}

(4.11)

Proof of Lemma 4.4 : Let

{\tilde{C}}_{l} (y, r_{β n - 2}; m)

denote the event that

D (y, r_{β n - 2})

is covered by each of the

l

walks in the first

m

excursions from

\partial D (y, r_{β n - 1})

\partial D (y, r_{β n})

. As in the proof of Lemma 3.2 we have that

\begin{matrix} P (C_{l} (x, r_{β n + 2}) \leq θ_{r_{n}, l} | G_{n, l}) \leq \prod_{y \in ℬ_{n, 1} (x)} (1 + o (1_{n})) P ({\tilde{C}}_{l} (y, r_{β n - 2}; n_{(1 - β) n})) . \end{matrix}

(4.12)

Fix

y \in ℬ_{n, 1}

. Note that for any

1 / (1 + \sqrt{l}) < β < 1

we can choose

a > 2 / l

such that

\begin{matrix} a (1 - β)^{2} < 2 β^{2} . \end{matrix}

(4.13)

We will show that uniformly for

y \in ℬ_{n, 1} (x)

and

x \in ℬ_{n, 2}

\begin{matrix} P ({\tilde{C}}_{l} (y, r_{β n - 2}; n_{(1 - β) n})) = o (1_{n}) \end{matrix}

(4.14)

Since

| ℬ_{n, 1} (x) | \geq n^{4}

, our lemma will follow.

( 4.14 ) follows from the proof of Lemma 3.2 after observing that

n_{(1 - β) n} = 3 a (1 - β)^{2} n^{2} log (1 - β) n \leq 3 (2 - 2 ε) β^{2} n^{2} log β n

for some

ε > 0

by ( 4.13 ).

Proof of Lemma 4.3 : The proof is similar to that of Lemma 3.1 . We have to show that for some

ζ = ζ (a, β) > 0

\begin{matrix} {lim}_{n \to \infty} P ({⋃_{y \in ℬ_{n, 1}}}^{l} ⋂_{j = 1} {N_{n}^{j} (y) > n_{(1 - β) n}}) = O (e^{- ζ n}) . \end{matrix}

(4.15)

But

\begin{matrix} P ({⋃_{y \in ℬ_{n, 1}}}^{l} ⋂_{j = 1} {N_{n}^{j} (y) > n_{(1 - β) n}}) \leq | ℬ_{n, 1} | {({sup}_{y \in ℬ_{n, 1}} P (N_{n} (y) > n_{(1 - β) n}))}^{l}, \end{matrix}

(4.16)

and using the estimates from the proof of Lemma 3.1 we obtain ( 4.16 ) for

δ^{'}

sufficiently small.

5 The Lower Bound for Theorem 1.2

We use the notation of the proof of the lower bound for Theorem 1.1 . Let

ℒ_{z, n, β} (α)

denote the event that

z

is visited less than

4 α (log r_{n})^{2} / π

times during the first

n_{β n} - β n

excursions from

\partial D (x, r_{n, β n})

\partial D (x, r_{n, β n - 1})

. As in the proof of the lower bound for Theorem 1.1 it suffices to show that uniformly in

x \in A_{n}

\begin{matrix} {lim}_{n \to \infty} P (⋃_{z \in D (x, r_{n, β n + 1})} ℒ_{z, n, β} (α)) = 0 . \end{matrix}

(5.1)

To see this, note first that

\begin{matrix} P (⋃_{z \in D (x, r_{n, β n + 1})} ℒ_{z, n, β} (α)) \leq r_{n, β n + 1}^{2} {sup}_{z \in D (x, r_{n, β n + 1})} P (ℒ_{z, n, β} (α)) . \end{matrix}

(5.2)

We now fix

z \in D (x, r_{n, β n + 1})

and obtain a bound on

P (ℒ_{z, n, β} (α))

uniform in

x, z

. Set

R_{z} = r_{n, β n - 1} - | x - z |

and

r_{z} = r_{n, β n} + | x - z |

. Since

| x - z | \leq r_{n, β n + 1}

it is easily checked that

D (x, r_{n, β n}) \subseteq D (z, r_{z}) \subseteq D (z, R_{z}) \subseteq D (x, r_{n, β n - 1})

so that we will have at least

n_{β n} - β n

excursions from

\partial D (z, r_{z})

\partial D (z, R_{z})

during the first

n_{β n} - β n

excursions from

\partial D (x, r_{n, β n})

\partial D (x, r_{n, β n - 1})

Let

ℒ_{z, n, β}^{'} (α)

denote the event that

z

is visited less than

4 α (log r_{n})^{2} / π

times during the first

n_{β n} - β n

excursions from

\partial D (z, r_{z})

\partial D (z, R_{z})

. Clearly

\begin{matrix} P (ℒ_{z, n, β} (α)) \leq P (ℒ_{z, n, β}^{'} (α)) . \end{matrix}

(5.3)

Let

Z_{j}

denote the number of visits to

z

during the

j

'th excursion from

\partial D (z, r_{z})

\partial D (z, R_{z})

Then for any

λ > 0

\begin{matrix} P (ℒ_{z, n, β}^{'} (α)) & = & P (\sum_{j = 1}^{n_{β n} - β n} Z_{j} < 4 α (log r_{n})^{2} / π) \end{matrix}

(5.4)

\begin{matrix} \leq & e^{λ 4 α (log r_{n})^{2} / π} E (e^{- λ \sum_{j = 1}^{n_{β n} - β n} Z_{j}}) \end{matrix}

by Chebycheff 's inequality. Fix a

y \in \partial D (z, r_{z})

. Let

Z_{j}^{'}

be i.i.d. random variables each distributed as

Z^{'}

, the number of visits to

z

of a simple random walk started at

y

and killed upon reaching

\partial D (z, R_{z})

. Then by the proof of Lemma 2.4 of [5] , see also the remark following the proof, we have that

\begin{matrix} E (e^{- λ \sum_{j = 1}^{n_{β n} - β n} Z_{j}}) & \leq & 2 E (e^{- λ \sum_{j = 1}^{n_{β n} - β n} Z_{j}^{'}}) \end{matrix}

(5.5)

\begin{matrix} = & 2 {(E^{y} (e^{- λ Z^{'}}))}^{n_{β n} - β n} . \end{matrix}

From now on we can take

z = 0

, (but retain the notation

r_{z}, R_{z}

for the radii). Let

G_{R_{z}} (a, b) = E^{a} (\sum_{j = 0}^{θ_{R_{z}}} 1_{{S_{j} = b}})

be the Green's function for

D (0, R_{z})

. It is then easy to see that, conditional on hitting the origin,

Z^{'}

is a geometric random variable with mean

G_{R_{z}} (0, 0)

, and

P^{y} (T_{0} < T_{\partial D (0, R_{z})}) = G_{R_{z}} (y, 0) / G_{R_{z}} (0, 0)

Hence

\begin{matrix} E^{y} (e^{- \frac{φ}{G_{R_{z}} (0, 0)} Z^{'}}) = 1 - \frac{G_{R_{z}} (y, 0)}{G_{R_{z}} (0, 0)} + \frac{G_{R_{z}} (y, 0)}{G_{R_{z}} (0, 0)} (\frac{1}{(e^{\frac{φ}{G_{R_{z}} (0, 0)}} - 1) G_{R_{z}} (0, 0) + 1}) . \end{matrix}

(5.6)

By Proposition 1.6.6 and 1.6.7 of [8] ,

1 / G_{R_{z}} (0, 0) = o (1 / n)

and

\begin{matrix} \frac{G_{R_{z}} (y, 0)}{G_{R_{z}} (0, 0)} = \frac{1}{(1 - β) n} + o (\frac{1}{n}) \end{matrix}

(5.7)

so that

\begin{matrix} E^{y} (e^{- \frac{φ}{G_{R_{z}} (0, 0)} Z^{'}}) = 1 - \frac{1}{(1 - β) n} (\frac{φ}{1 + φ}) + o (\frac{1}{n}) . \end{matrix}

(5.8)

Hence

\begin{matrix} {(E^{y} (e^{- \frac{φ}{G_{R_{z}} (0, 0)} Z^{'}}))}^{n_{β n} - β n} & \leq & e^{- (1 - o (1_{n})) \frac{φ}{1 + φ} \frac{n_{β n}}{(1 - β) n}} \end{matrix}

(5.9)

\begin{matrix} = & e^{- (1 - o (1_{n})) \frac{φ}{1 + φ} \frac{a β^{2} log r_{n}}{(1 - β)}} . \end{matrix}

Hence combined with ( 5.4 ) and ( 5.5 ), for any

φ > 0

\begin{matrix} P (ℒ_{z, n, β}^{'} (α)) \leq 2 e^{\frac{φ}{G_{R_{z}} (0, 0)} 4 α (log r_{n})^{2} / π} e^{- (1 - o (1_{n})) \frac{φ}{1 + φ} \frac{a β^{2} log r_{n}}{(1 - β)}} . \end{matrix}

(5.10)

By Proposition 1.6.6 of [8] ,

G_{R_{z}} (0, 0) = (1 + o (1_{n})) \frac{2}{π} (1 - β) log r_{n}

hence

\begin{matrix} P (ℒ_{z, n, β}^{'} (α)) \leq 2 e^{((1 + o (1_{n})) φ α - (1 - o (1_{n})) \frac{φ}{1 + φ} \frac{a}{2} β^{2}) \frac{2 log r_{n}}{(1 - β)}} . \end{matrix}

(5.11)

A straightforward computation shows that

\begin{matrix} {inf}_{φ > 0} (φ α - \frac{φ}{1 + φ} β^{2}) = - {(β - \sqrt{α})}^{2} \end{matrix}

(5.12)

which is achieved for

φ = β / \sqrt{α} - 1

. Using this value in ( 5.11 ) and taking

a < 2

sufficiently close to

2

we have for

n

large and any

δ > 0

\begin{matrix} P (ℒ_{z, n, β}^{'} (α)) \leq 2 e^{- (1 - δ) {(β - \sqrt{α})}^{2} \frac{2 log r_{n}}{(1 - β)}} . \end{matrix}

(5.13)

Combining this with ( 5.2 ), ( 5.3 ) and the fact that

log r_{n, β n + 1} \sim (1 - β) log r_{n}

we see that ( 5.1 ) will hold if we choose

β

so that

\begin{matrix} (1 - β)^{2} < {(β - \sqrt{α})}^{2} \end{matrix}

(5.14)

which holds whenever

1 - β < (1 - \sqrt{α}) / 2

. Since

log r_{n, β n} \sim (1 - β) log r_{n}

this completes the proof of the lower bound for Theorem 1.2 .

6 The Upper Bound for Theorem 1.2

As before, ( 1.4 ) of Theorem 1.2 is equivalent to the following theorem.

Theorem 6.1. If

ℛ_{n} (k)

denotes the radius of the largest disc completely covered

k

times by a simple random walk in

Z^{2}

after

n

steps, then for any

0 < α < 1

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{θ_{n}} (4 α (log n)^{2} / π)}{log n} = (1 - \sqrt{α}) / 2 a.s. \end{matrix}

(6.1)

We will prove ( 6.1 ) thereby establishing ( 1.4 ) and then ( 1.3 ) will also follow by comparison with ( 1.4 ), (letting

α \to 0

), and Theorem 1.1 .

In this section we prove the upper bound, and by the now standard interpolation it suffices to show that

\begin{matrix} {lim}_{n \to \infty} \frac{log ℛ_{θ_{r_{n}}} (4 α (log r_{n})^{2} / π)}{log r_{n}} \leq (1 - \sqrt{α}) / 2 a.s. \end{matrix}

(6.2)

In other words, we show that in any disc of radius

r_{β n}

with

β > (1 - \sqrt{α}) / 2

, there will be points visited less than

4 α (log r_{n})^{2} / π

times up till time

θ_{r_{n}}

Since

β > (1 - \sqrt{α}) / 2

we can choose

a > 2

sufficiently close to

2

a^{'} < 2 α

sufficiently close to

2 α

, and

ρ > 0

sufficiently close to

0

so that

\begin{matrix} (\sqrt{a} (1 - β) - \sqrt{a^{'}})^{2} < 2 (β - ρ)^{2} . \end{matrix}

(6.3)

Let

{\tilde{C}}_{α} (z, r_{β n - 2}; m)

denote the event that every point in

D (z, r_{β n - 2})

is visited at least

4 α (log r_{n})^{2} / π

times during the first

m

excursions from

\partial D (z, r_{β n - 1})

\partial D (z, r_{β n})

. Arguing as in the proof of the upper bound for Theorem 1.1 , we see that ( 6.2 ) will follow from the next lemma (compare with inequality ( 4.14 )).

Lemma 6.2. With

a, β, α

as defined before ( 6.3 ), we have uniformly in

z \in Z^{2}

\begin{matrix} P ({\tilde{C}}_{α} (z, r_{β n - 2}; n_{(1 - β) n})) = o (1_{n}) . \end{matrix}

(6.4)

Proof of Lemma 6.2 : Set

n_{k} = 3 a k^{2} log k

and

\begin{matrix} m_{k} = 3 {(\frac{\sqrt{a} (1 - β) - \sqrt{a^{'}}}{β - ρ})}^{2} {(k - \frac{(\sqrt{a} ρ (1 - β) - \sqrt{a^{'}} β)}{(\sqrt{a} (1 - β) - \sqrt{a^{'}})} n)}^{2} log n, ρ n \leq k \leq β n, \end{matrix}

(6.5)

and observe that

m_{β n} \sim n_{(1 - β) n}

and

m_{ρ n} \sim 3 a^{'} n^{2} log n

Fixing

z \in Z^{2}

, let

ℛ_{β n}^{z}

denote the time until completion of the first

m_{β n}

excursions from

\partial D (z, r_{β n - 1})

\partial D (z, r_{β n})

. For

z^{'} \in Z^{2}

ρ n \leq k \leq β n

let

N_{β n, k}^{z^{'}}

denote the number of excursions from

\partial D (z^{'}, r_{k - 1})

\partial D (z^{'}, r_{k})

until time

ℛ_{β n}^{z}

and let

L_{k}^{z^{'}}

denote the number of visits to

z^{'}

until time

k

. For some fixed

b > 0

to be determined, we say that a point

z^{'} \in Z^{2}

z, n, β

-sluggish if the following two conditions hold:

$∙$ $m_{k} - k \leq N_{β n, k}^{z^{'}} \leq m_{k} + k, \forall k = ρ n, \dots, β n - b .$
$∙$ $L_{ℛ_{β n}^{z}}^{z^{'}} < 4 α (log r_{n})^{2} / π$ .

Let

Z_{ρ n} \subset Z^{2}

be a maximal set of points in

D (z, r_{β n - 2})

which are

4 r_{ρ n}

separated and such that

z \in Z_{ρ n}

Lemma 6.3. Let

h = \frac{(\sqrt{a} (1 - β) - \sqrt{a^{'}})^{2}}{β - ρ}

. Then there exists

δ_{n} \to 0

such that uniformly in

z \in Z^{2}

\begin{matrix} {\bar{q}}_{n} = : P (z is z, n, β -sluggish) \geq r_{n}^{- (h + δ_{n})} \end{matrix}

(6.6)

and

\begin{matrix} P (x is z, n, β -sluggish) = (1 + o (1_{n})) {\bar{q}}_{n} . \end{matrix}

(6.7)

uniformly in

z

and

x \in Z_{ρ n}

Let

l (x, y) = max {m : D (x, r_{m}) \cap D (y, r_{m}) = \emptyset}

. Then, for some

C, c < \infty

which are both independent of

b

, all

n

z

and

x, y \in Z_{ρ n}

with

ρ n \leq l (x, y) < β n - b

\begin{matrix} P (x, y are z, n, β -sluggish) \leq {\bar{q}}_{n}^{2} n^{c} C^{β n - l (x, y)} {(\frac{r_{β n - b}}{r_{l (x, y)}})}^{h / (β - ρ) + δ_{l (x, y)}} . \end{matrix}

(6.8)

Furthermore, if

l (x, y) \geq β n - b

for

x, y \in Z_{ρ n}

, then

\begin{matrix} P (x, y are z, n, β -sluggish) = {\bar{q}}_{n}^{2} (1 + o (1_{n})) . \end{matrix}

(6.9)

Proof of Lemma 6.3 : We have

\begin{matrix} P (N_{β n, k}^{z^{'}} \overset{k}{\sim} m_{k}, k = ρ n, \dots, β n - b) \end{matrix}

\begin{matrix} = & (1 + o (1_{n})) P (N_{β n, β n - b}^{z^{'}} \overset{β n - b}{\sim} m_{β n - b})^{β n - b - 1} \prod_{k = ρ n} P (N_{β n, k}^{z^{'}} \overset{k}{\sim} m_{k} | N_{β n, k + 1}^{z^{'}} \overset{k + 1}{\sim} m_{k + 1}) . \end{matrix}

Further,

\begin{matrix} P (N_{β n, k}^{z^{'}} \overset{k}{\sim} m_{k} | N_{β n, k + 1}^{z^{'}} \overset{k + 1}{\sim} m_{k + 1}) \end{matrix}

\begin{matrix} \sim exp (- 3 {(\frac{\sqrt{a} (1 - β) - \sqrt{a^{'}}}{β - ρ})}^{2} log (k - \frac{(\sqrt{a} ρ (1 - β) - \sqrt{a^{'}} β)}{(\sqrt{a} (1 - β) - \sqrt{a^{'}})} n)), \end{matrix}

which follows as in the proof of Lemma 7.2 of [3] since

\begin{matrix} | \frac{m_{k + 1}}{m_{k}} - 1 - \frac{2}{k - \frac{(\sqrt{a} ρ (1 - β) - \sqrt{a^{'}} β)}{(\sqrt{a} (1 - β) - \sqrt{a^{'}})} n} | \leq \frac{C}{k log k} . \end{matrix}

(6.10)

We claim that if

a^{'} < 2 α

then uniformly in

z

and

z^{'}

\begin{matrix} p_{n} : = P (L_{ℛ_{β n}^{z}}^{z^{'}} < 4 α (log r_{n})^{2} / π | N_{β n, ρ n}^{z^{'}} \overset{ρ n}{\sim} 3 a^{'} n^{2} log n) = 1 - o (1_{n}) . \end{matrix}

(6.11)

Putting this together gives ( 6.6 ) and ( 6.7 ). The rest of proof of Lemma 6.3 follows by arguments similar to those in proving Lemma 7.1 of [4] (see also the proof of Lemma 4.2 of [5] for the adaptations one should make from the Brownian motion to the random walk case). Turning to prove ( 6.11 ), observe first that uniformly in

z

and

z^{'}

p_{n} \geq (1 + o (1_{n})) (1 - P ({\hat{ℒ}}_{z^{'}, n, ρ}))

for the event

{\hat{ℒ}}_{z^{'}, n, ρ}

that

z^{'}

is visited more than

4 α (log r_{n})^{2} / π

times during the first

m_{ρ n} + ρ n

excursions from

\partial D (z^{'}, r_{ρ n - 1})

\partial D (z^{'}, r_{ρ n})

(with

m_{ρ n} = 3 a^{'} n^{2} log n

this is an easy consequence of Lemma 2.4 of [5] ).

The proof of ( 6.11 ) is thus completed by an argument similar to the one detailed in ( 5.4 )–( 5.13 ).

That is, with the number of visits to

z^{'}

expressed as the sum of the contributions

Z_{j}

of the different excursions, we apply Chebycheff 's inequality and Lemma 2.4 of [5] to get the bound

P ({\hat{ℒ}}_{z^{'}, n, ρ}) \leq 2 e^{- λ 4 α (log r_{n})^{2} / π} (E^{y} e^{λ Z^{'}})^{m_{ρ n} + ρ n},

where

Z^{'}

is the number of visits of

0

by a simple random walk started at a fixed

y \in \partial D (0, r_{ρ n - 1})

and killed upon reaching

\partial D (0, r_{ρ n})

. Recall that

G = G_{r_{ρ n}} (0, 0) = (1 + o (1_{n})) \frac{2}{π} ρ log r_{n}

(see Proposition 1.6.6 of [8] ) and that for

φ > 0

E^{y} (e^{φ Z^{'} / G})^{m_{ρ n} + ρ n} \leq exp ((1 + o (1_{n})) \frac{φ}{1 - φ} \frac{a^{'}}{ρ} log r_{n})

(c.f. ( 5.9 ) for a similar derivation). Since

2 α > a^{'}

, taking

λ = φ / G

for

φ > 0

small enough leads to

P ({\hat{ℒ}}_{z^{'}, n, ρ}) \leq r_{n}^{- δ} \to 0

, where

δ = δ (ρ, φ, α, a^{'}) > 0

is independent of

z^{'}

and

n

We apply Lemma 6.3 to control the deviation of the number of

z, n, β

-sluggish points in

Z_{ρ n}

from its mean

| Z_{ρ n} | {\bar{q}}_{n} (1 + o (1_{n}))

. This is done by bounding the second moment of this random variable,in a manner similar to that of (3.8) and (3.9) of [4] . To this end, we determine

b

to be large enough so that

(r_{β n - 2} / r_{β n - b})^{2} \geq n^{c + 10}

. Since the mean number of

z, n, β

-sluggish points in

Z_{ρ n}

goes to

\infty

with

n

by ( 6.6 ) and our choice of parameters (see ( 6.3 )), it follows that in any disc

D (z, r_{β n - 2})

the probability of finding a

z, n, β

-sluggish point is

1 - o (1_{n})

. Since such a point is visited less than

4 α (log r_{n})^{2} / π

times during the first

n_{(1 - β) n}

excursions from

\partial D (z, r_{β n - 1})

\partial D (z, r_{β n})

, this completes the proof of Lemma 6.2 .

7 Proof of Theorem 1.4

Recall that

V_{n}

is the number of steps after step

n

until the simple random walk in

Z^{2}

visits a previously unvisited site. Fix

ε > 0

. We first prove the upper bound

\begin{matrix} {limsup}_{n \to \infty} \frac{log V_{n}}{log n} \leq 1 / 2 + 10 ε a.s. \end{matrix}

(7.1)

Let

\begin{matrix} J_{n} = {V_{n} \geq n^{1 / 2 + 10 ε}} \end{matrix}

(7.2)

and

\begin{matrix} ℒ_{n} = {ℛ_{m} < m^{1 / 4 + ε}; \forall m \geq n} \cap {θ_{m^{1 / 4 + 2 ε}} < m^{1 / 2 + 4.5 ε}; \forall m \geq n} . \end{matrix}

(7.3)

We show below that

\begin{matrix} P (J_{n} | ℒ_{n}) \leq e^{- n^{ε}} . \end{matrix}

(7.4)

Then

\begin{matrix} \sum_{n = 5}^{\infty} P (J_{n} \cap ℒ_{n}) < \infty \end{matrix}

(7.5)

and therefore, by the Borel-Cantelli lemma,

1_{{J_{n}}} (ω) 1_{{ℒ_{n}}} (ω) = 0

for all

n \geq N (ω)

with

N (ω) < \infty

a.s. ( 7.1 ) then follows from Theorem 1.1 and ( 2.1 ) which imply that

1_{{ℒ_{n}}} (ω) = 1

for all

n \geq N^{'} (ω)

with

N^{'} (ω) < \infty

a.s. It thus remains to prove ( 7.4 ).

Given

ℒ_{n}

, for any

n + 1 \leq m \leq n + n^{1 / 2 + 10 ε}

, there will be at least one uncovered point in

D (S_{m}, m^{1 / 4 + ε})

. Thus, using Proposition 1.6.7 of [8] , the probability of the random walk

{S_{m + i}}_{i \geq 1}

hitting an uncovered point prior to exiting

D (S_{m}, m^{1 / 4 + 2 ε})

is at least

c / log n

for some

c > 0

independent of

n

. Consequently, given

ℒ_{n}

, the probability of the random walk

{S_{m + i}; 1 \leq i \leq n^{1 / 2 + 5 ε}}

hitting an uncovered point is at least

c / log n

for some

c > 0

independent of

n

. Partitioning the interval

[1, 2, \dots, n^{1 / 2 + 10 ε}]

into

n^{5 ε}

disjoint segments of length

n^{1 / 2 + 5 ε}

shows that

\begin{matrix} P (J_{n} | ℒ_{n}) \leq (1 - \frac{c}{log n})^{n^{5 ε}} \end{matrix}

(7.6)

which gives ( 7.4 ).

We now establish the lower bound

\begin{matrix} {limsup}_{n \to \infty} \frac{log V_{n}}{log n} \geq 1 / 2 - 10 ε a.s. \end{matrix}

(7.7)

Let

\begin{matrix} M (n) = inf {m \geq n | S_{m} is in a fully covered disc D_{m} of radius m^{1 / 4 - ε}} \end{matrix}

(7.8)

and note that by Theorem 1.1 we have that

M (n) < \infty

a.s. for each

n

. Let

\begin{matrix} ℋ_{n} = {V_{m} \geq m^{1 / 2 - 5 ε} for some M (n) \leq m \leq M (n)^{1 + ε}} . \end{matrix}

(7.9)

We show below that for some

p_{0} > 0

and

n_{0} < \infty

\begin{matrix} P (ℋ_{n}) \geq p_{0}, \forall n \geq n_{0} . \end{matrix}

(7.10)

Define inductively

τ_{1} = 1 + n_{0}

τ_{j} = j + τ_{j - 1} + M (τ_{j - 1})^{1 + 2 ε}

. By ( 7.10 )

\begin{matrix} \sum_{j = 2}^{\infty} P (ℋ_{τ_{j}} \circ θ_{τ_{j}}) = \infty . \end{matrix}

(7.11)

Note that by definition,

P^{x} (ℋ_{n})

is independent of the starting point

x

, and

ℋ_{n} \in ℱ_{M (n)^{1 + 2 ε}}

. Thus

ℋ_{τ_{j}} \circ θ_{τ_{j}} \in ℱ_{τ_{j} + M (τ_{j})^{1 + 2 ε}} \subseteq ℱ_{τ_{j + 1}}

. Consequently, the events

{ℋ_{τ_{j}} \circ θ_{τ_{j}}; j = 2, \dots}

are independent, and the Borel-Cantelli lemma shows that

{limsup}_{j \to \infty} 1_{{ℋ_{τ_{j}}}} (τ_{j} ω) = 1

a.s. Since

1_{{ℋ_{τ_{j}}}} (τ_{j} ω) = 1

readily implies that

V_{m} \geq m^{1 / 2 - 10 ε}

for some

m \geq τ_{j}

, ( 7.7 ) follows. It thus remains to show ( 7.10 ).

Note that since

S_{M (n)}

is in a fully covered disc

D_{M (n)} = D (x, M (n)^{1 / 4 - ε})

, by Exercise 1.6.8 of [8] there is a strictly positive probability, independent of

M (n)

, that the random walk

S_{M (n) + i}; i = 1, 2, \dots

will enter

D (x, M (n)^{1 / 4 - 2 ε})

before exiting

D (x, M (n)^{1 / 4})

, hence a strictly positive probability, independent of

M (n)

, that the random walk

S_{M (n) + i}; i = 1, 2, \dots, M (n)^{1 / 2 + ε}

will enter

D (x, M (n)^{1 / 4 - 2 ε})

But having entered

D^{'} = D (x, M (n)^{1 / 4 - 2 ε})

there is a strictly positive probability, independent of

M (n)

, that the random walk

S_{M (n) + T_{D^{'}} + i}; i = 1, 2, \dots

will take at least

M (n)^{1 / 2 - 5 ε}

steps before exiting the fully covered disc

D_{M (n)} = D (x, M (n)^{1 / 4 - ε})

. Finally, ( 7.10 ) follows.

Acknowledgement. We are grateful to Zhan Shi and Ofer Zeitouni for useful discussions, and to Olivier Daviaud and J. Ben Hough for comments on the manuscript.

References

R. F. Bass and P. S. Griffin, The most visited site of Brownian motion and simple random walk, Z. Wahrsch. Verw. Gebiete 70 (1985), 417–436.
O. Daviaud, Extremes of the discrete two-dimensional Gaussian free field, Preprint (2004), see arXiv.org/abs/math.PR/0406609.
A. Dembo, Y. Peres, J. Rosen and O. Zeitouni, Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk, Acta Math. 186 (2001), 239–270.
A. Dembo, Y. Peres, J. Rosen and O. Zeitouni, Cover time for Brownian motion and random walks in two dimensions, Ann. Math. 160 (2004), 433–467; see also arXiv.org/abs/math.PR/0107191.
A. Dembo, Y. Peres, J. Rosen and O. Zeitouni, Late points for random walks in two dimensions, Ann. Probab., (2005) to appear; See arXiv.org/abs/math.PR/0303102.
P. Erdős, and P. Révész, Three problems on the random walk in $Z^{d}$ , Studia Sci. Math. Hung., 26 (1991), 309–320.
J.-P. Kahane, Some random series of functions: Second Edition, Cambridge University Press, (1985).
G. Lawler, Intersections of random walks. Birkhauser, (1991).
G. Lawler, On the covering time of a disc by a random walk in two dimensions, In Seminar in Stochastic Processes 1992, 189-208. Birkhauser, (1993).
P. Révész, Random Walk in Random and Non-Random Environments, World Scientific, Singapore (1990).
P. Révész, Clusters of a random walk in the plane, Ann. Probab., 21 (1993), 318–328.
J. Rosen, A random walk proof of the Erdős-Taylor conjecture, Periodica Mathematica Hungarica, to appear. http://front.math.ucdavis.edu/math.PR/0503108

	Amir Dembo	Yuval Peres
	Departments of Mathematics	Departments of Statistics
	and of Statistics	and of Mathematics
	Stanford University	UC Berkeley
	Stanford, CA 94305	Berkeley, CA 94720
	amir@math.stanford.edu	peres@stat.berkeley.edu



	Jay Rosen
	Department of Mathematics
	College of Staten Island, CUNY
	Staten Island, NY 10314
	jrosen3@earthlink.net

March 5, 2005. * Research partially supported by NSF grant #DMS-0406042 and #DMS-FRG-0244323. † Research partially supported by NSF grants #DMS-0104073 and #DMS-0244479. ‡ Research supported, in part, by grants from the NSF and from PSC-CUNY

Amir Dembo * Yuval Peres † Jay Rosen ‡