, , March 2, 2005. ‡ Research supported, in part, by grants from the NSF and from PSC-CUNY

In our paper [1] we proved a conjecture of Erdős and Taylor concerning the number

L_{n}^{*}

of visits to the most visited site for the simple random walk in

Z^{2}

up to step

n

Theorem 1.1. Let

{X_{j}; j \geq 1}

be the simple random walk in

Z^{2}

. Then

\begin{matrix} {lim}_{n \to \infty} \frac{L_{n}^{*}}{(log n)^{2}} = 1 / π a.s. \end{matrix}

(1.1)

Our approach in that paper was to first prove an analogous result for planar Brownian motion and then to use strong approximation. The goal of this paper, which is purely expository, is to show how to prove ( 1.1 ) using only random walk methods. We also go beyond ( 1.1 ) and study the size of the set of `frequent points', i.e. those points in

Z^{2}

which are visited an unusually large number of times, of order

(log n)^{2}

. Perhaps more important than our specific results, we develop powerful estimates for the simple random walk which we expect will have wide applicability.

Let

L_{n}^{x}

denote the number of times that

x \in Z^{2}

is visited by the random walk in

Z^{2}

up to step

n

, (so that

L_{n}^{*} = {max}_{x \in Z^{2}} L_{n}^{x}

). Set

\begin{matrix} Θ_{n} (α) = {x \in Z^{2} : \frac{L_{n}^{x}}{(log n)^{2}} \geq α / π} . \end{matrix}

(1.2)

Let

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

. Let

T_{B} = inf {i \geq 0 | X_{i} \in B}

for any

B \subseteq Z^{2}

and set

\begin{matrix} Ψ_{n} (a) = {x \in D (0, n) : \frac{L_{T_{D (0, n)^{c}}}^{x}}{(log n)^{2}} \geq 2 a / π} . \end{matrix}

(1.3)

Theorem 1.2. Let

{X_{j}; j \geq 1}

be the simple random walk in

Z^{2}

. Then for any

0 < α < 1

\begin{matrix} {lim}_{n \to \infty} \frac{log | Θ_{n} (α) |}{log n} = 1 - α a.s. \end{matrix}

(1.4)

Equivalently, for any

0 < a < 2

\begin{matrix} {lim}_{n \to \infty} \frac{log | Ψ_{n} (a) |}{log n} = 2 - a a.s. \end{matrix}

(1.5)

The equivalence of ( 1.4 ) and ( 1.5 ) follows from the strong invariance principle which implies that

\begin{matrix} {lim}_{n \to \infty} \frac{log T_{D (0, n)^{c}}}{log n} = 2 a.s. \end{matrix}

(1.6)

In particular, ( 1.1 ) is equivalent to

\begin{matrix} {lim}_{n \to \infty} \frac{L_{D (0, n)^{c}}^{*}}{(log n)^{2}} = 2 / π a.s. \end{matrix}

(1.7)

In Section 2 we prove the upper bound for Theorem 1.2 , and the lower bound is proven in Section 3 , subject to Lemma 3.2 . Sections 4 - 6 are devoted to the proof of Lemma 3.2 .

Here are the basic ideas behind our proof of ( 1.7 ). It is not too hard to get good estimates on

P (L_{T_{D (0, n)^{c}}}^{x} \geq (2 - ε) (log n)^{2} / π)

for

x \in D (0, n)

, and indeed this is how we obtain the upper bound for ( 1.7 ) in Section 2 . On the other hand, the lower bound requires a second moment estimate, which is problematic due to the large correlation between the events

{L_{T_{D (0, n)^{c}}}^{x} \geq (2 - ε) (log n)^{2} / π}

for different

x \in D (0, n)

. Rather than study the events

{L_{T_{D (0, n)^{c}}}^{x} \geq (2 - ε) (log n)^{2} / π}

, we define a point

x \in D (0, n)

to be `n-succesful' if, up to time

T_{D (0, n)^{c}}

, there is a specified number of excursions between circles centered at

x

. The `excursion count' is chosen to be `typical' for

x

with

{L_{T_{D (0, n)^{c}}}^{x} \geq (2 - ε) (log n)^{2} / π}

, so that the probability of

x

being `n-succesful' is close to

P (L_{T_{D (0, n)^{c}}}^{x} \geq (2 - ε) (log n)^{2} / π)

and also, for large enough

n

, all `n-succesful' points

x

have

L_{T_{D (0, n)^{c}}}^{x} \geq (2 - 2 ε) (log n)^{2} / π

, see Lemma 3.1 . The advantage of working with `n-succesful' points is that the correlation between two such points,

x, y

, can be controlled using the tree-like structure of circles centered at the two points. In particular we show that for

x, y

far apart, excursions between circles centered at

x

and close to

x

are almost independent of the excursions between circles centered at

y

and close to

y

2 Local time estimates and upper bounds

Let

X_{n}, n \geq 0

denote the simple random walk in

Z^{2}

. We use

P^{x}, E^{x}

for the probability and expectation for the walk started at

x

, and write simply

P, E

for the walk started at the origin. For any set

A \subseteq Z^{2}

we define the boundary

\partial A

A

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

. For

x, y \in Z^{2}

define the Green's function

\begin{matrix} G_{A} (x, y) = \sum_{i = 0}^{\infty} P^{x} (X_{i} = y, i < T_{A^{c}}) . \end{matrix}

(2.1)

Lemma 2.1. For

| x_{0} | = r < R

and some finite constant

γ

\begin{matrix} E^{x_{0}} (L_{T_{D (0, R)^{c}}}^{0}) = G_{D (0, R)} (x_{0}, 0) = {\begin{matrix} \frac{2}{π} log (R) + γ + O (R^{- 1}) & if x_{0} = 0 \\ \frac{2}{π} log (\frac{R}{r}) + O (r^{- 1}) & if x_{0} \neq 0 . \end{matrix} \end{matrix}

(2.2)

Let

x_{0} \neq 0

. For any

0 < φ \leq 1

\begin{matrix} E^{x_{0}} (e^{- \frac{φ}{G_{D (0, R)} (0, 0)} L_{T_{D (0, R)^{c}}}^{0}}) = 1 - \frac{log (\frac{R}{r})}{log (R)} \frac{φ}{1 + φ} (1 + O (\frac{1}{log (r)})) \end{matrix}

(2.3)

and for all

z \geq 1

\begin{matrix} P^{x_{0}} (L_{T_{D (0, R)^{c}}}^{0} \geq z G_{D (0, R)} (0, 0)) \leq c \sqrt{z} e^{- z} \end{matrix}

(2.4)

for some

c < \infty

independent of

x_{0}, z, R

Proof of Lemma 2.1 : By Theorem 1.6.6 of [4] ,

\begin{matrix} G_{D (0, R)} (0, 0) = \frac{2}{π} log R + γ + O (R^{- 1}) \end{matrix}

(2.5)

for an explicit constant

γ

, and by Proposition 1.6.7 of [4]

\begin{matrix} G_{D (0, R)} (x, 0) = \frac{2}{π} log (\frac{R}{| x |}) + O (| x |^{- 1}) . \end{matrix}

(2.6)

Since

\begin{matrix} L_{T_{D (0, R)^{c}}}^{0} = \sum_{i < T_{D (0, R)^{c}}} 1_{{X_{i} = 0}}, \end{matrix}

(2.7)

( 2.2 ) follows.

For ( 2.3 ), note that, conditional on hitting

0

L_{T_{D (0, R)^{c}}}^{0}

is a geometric random variable with mean

G_{D (0, R)} (0, 0)

. Hence,

\begin{matrix} E^{x_{0}} (e^{- \frac{φ}{G_{D (0, R)} (0, 0)} L_{T_{D (0, R)^{c}}}^{0}}) \end{matrix}

\begin{matrix} = 1 - P^{x_{0}} (T_{0} < T_{D (0, R)^{c}}) \end{matrix}

\begin{matrix} + P^{x_{0}} (T_{0} < T_{D (0, R)^{c}}) (\frac{1}{(e^{\frac{φ}{G_{D (0, R)} (0, 0)}} - 1) G_{D (0, R)} (0, 0) + 1}) . \end{matrix}

(2.8)

Since by ( 2.5 )

\begin{matrix} \frac{1}{G_{D (0, R)} (0, 0)} = O (1 / log (R)) \end{matrix}

(2.9)

we have

\begin{matrix} (e^{\frac{φ}{G_{D (0, R)} (0, 0)}} - 1) G_{D (0, R)} (0, 0) + 1 = 1 + φ + O (\frac{1}{log (R)}) . \end{matrix}

(2.10)

Furthermore, using the strong Markov property at the stopping time

T_{0}

\begin{matrix} G_{D (0, R)} (x_{0}, 0) & = & P^{x_{0}} (\sum_{i < T_{D (0, R)^{c}}} 1_{{X_{i} = 0}}) \end{matrix}

\begin{matrix} = & P^{x_{0}} (\sum_{i < T_{D (0, R)^{c}}} 1_{{X_{i} = 0}} \circ θ_{T_{0}}; T_{0} < T_{D (0, R)^{c}}) \end{matrix}

(2.11)

\begin{matrix} = & P^{x_{0}} (T_{0} < T_{D (0, R)^{c}}) P^{0} (\sum_{i < T_{D (0, R)^{c}}} 1_{{X_{i} = 0}}) \end{matrix}

\begin{matrix} = & P^{x_{0}} (T_{0} < T_{D (0, R)^{c}}) G_{D (0, R)} (0, 0) \end{matrix}

so that

\begin{matrix} P^{x_{0}} (T_{0} < T_{D (0, R)^{c}}) = \frac{G_{D (0, R)} (x_{0}, 0)}{G_{D (0, R)} (0, 0)} . \end{matrix}

(2.12)

By ( 2.5 ) and ( 2.6 ),

\begin{matrix} \frac{G_{D (0, R)} (x_{0}, 0)}{G_{D (0, R)} (0, 0)} = \frac{log (\frac{R}{r})}{log (R)} (1 + O (\frac{1}{log (r)})), \end{matrix}

(2.13)

and ( 2.3 ) then follows.

For ( 2.4 ) note that by the strong Markov property we have

\begin{matrix} E^{x_{0}} (L_{T_{D (0, R)^{c}}}^{0})^{k} & \leq & k! E^{x_{0}} ({\sum_{0 \leq j_{1} \leq \dots \leq j_{k} < T_{D (0, R)^{c}}}}^{k} \prod_{i = 1} 1_{{X_{j_{i}} = 0}}) \end{matrix}

\begin{matrix} \leq & k! E^{x_{0}} ({\sum_{0 \leq j_{1} \leq \dots \leq j_{k - 1} < T_{D (0, R)^{c}}}}^{k - 1} \prod_{i = 1} 1_{{X_{j_{i}} = 0}} G_{D (0, R)} (0, 0)) \end{matrix}

\begin{matrix} = & k! G_{D (0, R)} (0, 0) E^{x_{0}} ({\sum_{0 \leq j_{1} \leq \dots \leq j_{k - 1} < T_{D (0, R)^{c}}}}^{k - 1} \prod_{i = 1} 1_{{X_{j_{i}} = 0}}), \end{matrix}

and by iteration we obtain

\begin{matrix} E^{x_{0}} (L_{T_{D (0, R)^{c}}}^{0})^{k} \leq k! G_{D (0, R)} (x_{0}, 0) (G_{D (0, R)} (0, 0))^{k - 1} . \end{matrix}

(2.14)

To prove ( 2.4 ), use ( 2.14 ), the fact that

G_{D (0, R)} (x_{0}, 0) \leq G_{D (0, R)} (0, 0)

by ( 2.11 ), and Chebysheff to obtain

\begin{matrix} P^{x_{0}} (L_{T_{D (0, R)^{c}}}^{0} \geq z G_{D (0, R)} (0, 0)) \leq \frac{k!}{z^{k}} \end{matrix}

(2.15)

then take

k = [z]

and use Stirling's formula.

We next provide the required upper bounds in Theorem 1.2 . Namely, we will show that for any

a \in (0, 2]

\begin{matrix} {limsup}_{m \to \infty} \frac{log | {x \in D (0, m) : L_{T_{D (0, m)^{c}}}^{x} \geq (2 a / π) (log m)^{2}} |}{log m} \leq 2 - a a . s . \end{matrix}

(2.16)

To see this fix

δ > 0

and note that by ( 2.4 ), for some

0 < ε < δ

, all

x \in D (0, m)

and all large enough

m

\begin{matrix} P (\frac{L_{T_{D (x, 2 m)^{c}}}^{x}}{(log m)^{2}} \geq 2 a / π) \leq m^{- a + ε} \end{matrix}

(2.17)

Therefore

\begin{matrix} P (| {x \in D (0, m) : \frac{L_{T_{D (0, m)^{c}}}^{x}}{(log m)^{2}} \geq 2 a / π} | \geq m^{2 - a + δ}) \end{matrix}

(2.18)

\begin{matrix} \leq m^{- (2 - a) - δ} E^{0} (| {x \in D (0, m) : \frac{L_{T_{D (0, m)^{c}}}^{x}}{(log m)^{2}} \geq 2 a / π} |) \end{matrix}

\begin{matrix} = m^{- (2 - a) - δ} \sum_{x \in D (0, m)} P^{0} (\frac{L_{T_{D (0, m)^{c}}}^{x}}{(log m)^{2}} \geq 2 a / π) \end{matrix}

\begin{matrix} \leq m^{- (2 - a) - δ} \sum_{x \in D (0, m)} P^{0} (\frac{L_{T_{D (x, 2 m)^{c}}}^{x}}{(log m)^{2}} \geq 2 a / π) \end{matrix}

\begin{matrix} \leq m^{- (δ - ε)} . \end{matrix}

Now apply our result to

m = m_{n} = e^{n}

to see by Borel-Cantelli that for some

N (ω) < \infty

a.s. we have that for all

n \geq N (ω)

\begin{matrix} | {x \in D (0, e^{n}) : \frac{L_{T_{D (0, e^{n})^{c}}}^{x}}{(log e^{n})^{2}} \geq 2 a / π} | \leq e^{(2 - a + δ) n} . \end{matrix}

(2.19)

Then if

e^{n} \leq m \leq e^{n + 1}

\begin{matrix} | {x \in D (0, m) : \frac{L_{T_{D (0, m)^{c}}}^{x}}{(log m)^{2}} \geq 2 a / π} | \end{matrix}

(2.20)

\begin{matrix} \leq | {x \in D (0, e^{n + 1}) : \frac{L_{T_{D (0, e^{n + 1})^{c}}}^{x}}{(log e^{n})^{2}} \geq 2 a / π} | \end{matrix}

\begin{matrix} = | {x \in D (0, e^{n + 1}) : \frac{L_{T_{D (0, e^{n + 1})^{c}}}^{x}}{(log e^{n + 1})^{2}} \geq 2 a (1 + 1 / n)^{- 2} / π} | \end{matrix}

\begin{matrix} \leq e^{(2 - a (1 + 1 / n)^{- 2} + δ) (n + 1)} \leq m^{(2 - a (1 + 1 / n)^{- 2} + δ) (n + 1) / n} . \end{matrix}

( 2.16 ) now follows on taking

δ \to 0

3 Lower bounds for probabilities

Fixing

0 < a < 2

, we prove in this section that

\begin{matrix} {liminf}_{m \to \infty} \frac{log | {x \in D (0, m) : L_{T_{D (0, m)^{c}}}^{x} \geq (2 a / π) (log m)^{2}} |}{log m} \geq 2 - a a . s . \end{matrix}

(3.1)

In view of ( 2.16 ), we will obtain Theorem 1.2 .

Set

K_{n} = 16 e^{n} n^{3 n}

. Using the fact that

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

, a simple interpolation argument shows that in order to prove ( 3.1 ) it suffices to show that

\begin{matrix} {liminf}_{n \to \infty} \frac{log | {x \in D (0, K_{n}) : L_{T_{D (0, K_{n})^{c}}}^{x} \geq (2 a / π) (log K_{n})^{2}} |}{log K_{n}} \geq 2 - a a . s . \end{matrix}

(3.2)

It suffices to prove that for any

δ > 0

and sufficiently large

n

\begin{matrix} P (| {x \in D (0, K_{n}) : \frac{L_{T_{D (0, K_{n})^{c}}}^{x}}{(log K_{n})^{2}} \geq (2 a / π)} | \geq K_{n}^{2 - a - δ}) \geq p_{δ} > 0 . \end{matrix}

(3.3)

For then

\begin{matrix} P (| {x \in D (0, K_{n}) : \frac{L_{T_{D (0, K_{n})^{c}}}^{x}}{(log K_{n + 1})^{2}} \geq (2 a - δ) / π} | \leq K_{n + 1}^{2 - a - 2 δ}) \leq 1 - p_{δ}, \end{matrix}

(3.4)

By considering the stopping times

τ_{l} = : T_{D (0, l K_{n})^{c}}; l = 0, 1, 2, \dots, n^{3} - 1

and setting

\begin{matrix} A_{l} = {| {x \in D (X_{τ_{l}}, K_{n}) : \frac{L_{T_{D (X_{τ_{l}}, K_{n})^{c}}}^{x}}{(log K_{n + 1})^{2}} \geq (2 a - δ) / π} | \leq K_{n + 1}^{2 - a - 2 δ}} \end{matrix}

(3.5)

we have that

\begin{matrix} {| {x \in D (0, K_{n + 1}) : \frac{L_{T_{D (0, K_{n + 1})^{c}}}^{x}}{(log K_{n + 1})^{2}} \geq (2 a - δ) / π} | \leq K_{n + 1}^{2 - a - 2 δ}} \end{matrix}

(3.6)

\begin{matrix} \subseteq \cap_{l = 0}^{n^{3} - 1} A_{l} \circ θ_{τ_{l}} . \end{matrix}

Hence using the strong Markov property and ( 3.4 ) we see that

P (| {x \in D (0, K_{n + 1}) : \frac{L_{T_{D (0, K_{n + 1})^{c}}}^{x}}{(log K_{n + 1})^{2}} \geq (2 a - δ) / π} | \leq K_{n + 1}^{2 - a - 2 δ}) \leq (1 - p_{δ})^{n^{3}} .

An application of the Borel-Cantelli lemma followed by taking the

δ \to 0

limit then gives ( 3.2 ).

We start by constructing a subset of the set appearing in ( 3.3 ), the probability of which is easier to bound below. To this end fix

n

, and let

r_{n, k} = e^{n} n^{3 (n - k)}, k = 0, \dots, n

. In particular,

r_{n, n} = e^{n}

and

r_{n, 0} = e^{n} n^{3 n}

Set

K_{n} = 16 r_{n, 0} = 16 e^{n} n^{3 n}

Let

U_{n} = [2 r_{n, 0}, 3 r_{n, 0}]^{2} \subseteq D (0, K_{n})

. For

x \in U_{n}

, let

N_{n, k}^{x}

denote the number of excursions from

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

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

until time

T_{D (0, K_{n})^{c}}

Set

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

, and

k_{0} = 4 \lor inf {k | n_{k} \geq 2 k}

We will say that a point

x \in U_{n}

n

-successful if

N_{n, k}^{x} = 1, \forall k = 1, \dots, k_{0} - 1

and

\begin{matrix} n_{k} - k \leq N_{n, k}^{x} \leq n_{k} + k \forall k = k_{0}, \dots, n \end{matrix}

(3.7)

Let

Y (n, x); x \in U_{n}

be the collection of random variables defined by

Y (n, x) = 1 if x is n -successful

and

Y (n, x) = 0

otherwise. Set

{\bar{q}}_{n, x} = P (Y (n, x) = 1) = E (Y (n, x))

The next lemma relates the notion of

n

-successful and local times. As usual we write

{log}_{2} n

for

log log n

Lemma 3.1. Let

S_{n} = {x \in U_{n} | x is n -successful} .

Then for some

N (ω) < \infty

a.s., for all

n \geq N (ω)

and all

x \in S_{n}

\frac{L_{T_{D (0, K_{n})^{c}}}^{x}}{(log K_{n})^{2}} \geq 2 a / π - 2 / {log}_{2} n .

Proof of Lemma 3.1 : Recall that if

x

is n-successful then

N_{n, n}^{x} \geq n_{n} - n = a (3 n^{2} log n) - n

. Let

L^{x, j}

denote the number of visits to

x

during the

j

'th excursion from

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

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

. Then for any

0 < λ < \infty

\begin{matrix} P_{x} & : = & P (L_{T_{D (0, K_{n})^{c}}}^{x} \leq (2 a / π - 2 / {log}_{2} n) (log K_{n})^{2}, x \in S_{n}) \end{matrix}

\begin{matrix} \leq & P (\sum_{j = 0}^{n_{n} - n} L^{x, j} \leq (2 a / π - 1 / {log}_{2} n) (3 n log n)^{2}) \end{matrix}

\begin{matrix} \leq & exp (λ (2 a / π - 1 / {log}_{2} n) (3 n log n)^{2}) E (e^{- λ \sum_{j = 0}^{n_{n} - n} L^{x, j}}) . \end{matrix}

(3.8)

τ

denotes the first time that the

n_{n} - n

'th excursion from

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

reaches

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

then by the strong Markov property

\begin{matrix} E (e^{- λ \sum_{j = 0}^{n_{n} - n} L^{x, j}}) \end{matrix}

(3.9)

\begin{matrix} = E (e^{- λ \sum_{j = 0}^{n_{n} - n - 1} L^{x, j}} E^{X_{τ}} (e^{- λ L_{T_{D (x, r_{n, n - 1})^{c}}}^{x}})) . \end{matrix}

Set

λ = φ / G_{D (x, r_{n, n - 1})} (x, x)

. By ( 2.3 ), with

r = r_{n, n} = e^{n}, R = r_{n, n - 1} = n^{3} e^{n}

, for any

0 < φ \leq 1

and large

n

\begin{matrix} {sup}_{y \in \partial D (x, r_{n, n})} E^{y} (e^{- λ L_{T_{D (x, r_{n, n - 1})^{c}}}^{x}}) \leq exp (- \frac{(1 - 1 / 2 log n) φ}{1 + φ} 3 (log n) / n) . \end{matrix}

(3.10)

Hence by induction

\begin{matrix} E (e^{- λ \sum_{j = 0}^{n_{n} - n} L^{x, j}}) \leq exp (- \frac{(1 - 1 / log n) φ}{1 + φ} 9 a n (log n)^{2}) . \end{matrix}

(3.11)

Then with this choice of

λ

, noting that

G_{D (x, r_{n, n - 1})} (x, x) \sim \frac{2}{π} n

by ( 2.5 ), we have

\begin{matrix} P_{x} \leq {inf}_{φ > 0} exp ({φ (1 - 1 / 2 {log}_{2} n) - \frac{(1 - 1 / log n) φ}{1 + φ}} 9 a n (log n)^{2}) . \end{matrix}

(3.12)

A straightforward computation shows that

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

(3.13)

which is achieved for

φ = \sqrt{β} / \sqrt{α} - 1

. Using this in ( 3.12 ) we find that

\begin{matrix} P_{x} \leq exp (- c n (log n / {log}_{2} n)^{2}) . \end{matrix}

(3.14)

Note that

| U_{n} | \leq e^{c n log n}

. Summing over all

x \in U_{n}

and then over

n

and applying Borel-Cantelli will then complete the proof of Lemma 3.1 .

Using this Lemma we see that to prove ( 3.3 ) it will suffice to show that for any

δ > 0

we can find

p_{0} > 0

and

N_{0} < \infty

such that

\begin{matrix} P (\sum_{x \in U_{n}} Y (n, x) \geq K_{n}^{2 - a - δ}) \geq p_{0} \end{matrix}

(3.15)

for all

n \geq N_{0}

We will see by ( 3.20 ) of the next Lemma below that for some sequence

δ_{n} \to 0

and constant

c > 0

\begin{matrix} E (\sum_{x \in U_{n}} Y (n, x)) = \sum_{x \in U_{n}} {\bar{q}}_{n, x} \geq c K_{n}^{2 - a - δ_{n}} . \end{matrix}

(3.16)

Recall the Paley-Zygmund inequality (see [3,page8] ): for any

W \in L^{2} (Ω)

and

0 < λ < 1

\begin{matrix} P (W \geq λ E (W)) \geq (1 - λ)^{2} \frac{(E (W))^{2}}{E (W^{2})} . \end{matrix}

(3.17)

We will apply this with

W = W_{n} = \sum_{x \in U_{n}} Y (n, x)

. Thus to complete the proof of ( 3.15 ) it suffices to show that

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

(3.18)

for some

c < \infty

all

n

sufficiently large. Furthermore, using ( 3.16 ) it suffices to show that

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

(3.19)

The next lemma, which provides estimates for the first and second moments of

Y (n, x)

, will be proven in the following sections.

Lemma 3.2. There exists

δ_{n} \to 0

such that for all

n \geq 1

\begin{matrix} {\bar{q}}_{n, x} \geq Q_{n} = {inf}_{x \in U_{n}} P (x is n -successful) \geq K_{n}^{- (a + δ_{n})}, \end{matrix}

(3.20)

and

\begin{matrix} Q_{n} \geq c {\bar{q}}_{n, x} \end{matrix}

(3.21)

for some

c > 0

and all

n

and

x \in U_{n}

There exists

C < \infty

and

δ_{n}^{'} \to 0

such that for all

n

x \neq y

and

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

\begin{matrix} E (Y (n, x) Y (n, y)) \leq C Q_{n}^{2} (l (x, y)!)^{3 a + δ_{l (x, y)}^{'}} . \end{matrix}

(3.22)

In the sequel, we let

C_{m}

denote generic finite constants that are independent of

n

. The definition of

l (x, y) \geq 1

implies that

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

. Recall that there are at most

C_{0} r_{n, l - 1}^{2} \leq C_{0} K_{n}^{2} l^{6} (l!)^{- 6}

points

y

in the ball of radius

2 r_{n, l - 1}

centered at

x

. Thus, it follows from Lemma 3.2 that

\begin{matrix} \sum_{\overset{x, y \in U_{n}}{2 r_{n, n} \leq | x - y | \leq 2 r_{n, 0}}} E (Y (n, x) Y (n, y)) \end{matrix}

(3.23)

\begin{matrix} \leq C_{1} \sum_{\overset{x, y \in U_{n}}{2 r_{n, n} \leq | x - y | \leq 2 r_{n, 0}}} Q_{n}^{2} (l (x, y)!)^{3 a + δ_{l (x, y)}^{'}} \end{matrix}

\begin{matrix} \leq C_{2} Q_{n}^{2} K_{n}^{2} \sum_{l = 1}^{n} K_{n}^{2} l^{6} (l!)^{- 6} (l!)^{3 a + δ_{l}^{'}} \end{matrix}

\begin{matrix} \leq C_{3} (K_{n}^{2} Q_{n})^{2} \sum_{l = 1}^{n} l^{6} (l!)^{- 3 (2 - a) + δ_{l}^{'}} \end{matrix}

\begin{matrix} \leq C_{4} (K_{n}^{2} Q_{n})^{2} \leq C_{5} {E (\sum_{x \in U_{n}} Y (n, x))}^{2} \end{matrix}

where we used the fact from ( 3.20 ) that

\begin{matrix} K_{n}^{2} Q_{n} \leq c \sum_{x \in U_{n}} {\bar{q}}_{n, x} = c E (\sum_{x \in U_{n}} Y (n, x)) . \end{matrix}

(3.24)

Similarly

\begin{matrix} \sum_{\overset{x, y \in U_{n}}{| x - y | \leq 2 r_{n, n}}} E (Y (n, x) Y (n, y)) \leq \sum_{\overset{x, y \in U_{n}}{| x - y | \leq 2 r_{n, n}}} E (Y (n, y)) \end{matrix}

(3.25)

\begin{matrix} \leq C_{6} \sum_{x; | x | \leq 2 r_{n, n}} K_{n}^{2} Q_{n} \leq C_{7} e^{2 n} K_{n}^{2} Q_{n} \leq C_{8} {E (\sum_{x \in U_{n}} Y (n, x))}^{2} \end{matrix}

using ( 3.24 ) and ( 3.16 ). This completes the proof of ( 3.19 ) and hence of ( 3.1 ).

4 First moment estimates

By ( 2.12 ), ( 2.5 ) and ( 2.6 ) we have that for any

x \in D (0, n)

\begin{matrix} P^{x} (T_{0} < T_{D (0, n)^{c}}) & = & \frac{(2 / π) log (n / | x |) + O (| x |^{- 1})}{(2 / π) log n + γ + O (n^{- 1})} \end{matrix}

\begin{matrix} = & \frac{log (n / | x |) + O (| x |^{- 1})}{log (n)} (1 + O ((log n)^{- 1}) . \end{matrix}

(4.1)

By Exercise 1.6.8 of [4] we have that uniformly in

r < | x | < R

\begin{matrix} P^{x} (T_{D (0, R)^{c}} < T_{D (0, r)}) = \frac{log (| x | / r) + O (r^{- 1})}{log (R / r)} \end{matrix}

(4.2)

and

\begin{matrix} P^{x} (T_{D (0, r)} < T_{D (0, R)^{c}}) = \frac{log (R / | x |) + O (r^{- 1})}{log (R / r)} . \end{matrix}

(4.3)

Proof of Lemma 3.2 : For

x \in U_{n}

we begin by getting bounds on the probability of reaching

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

before

T_{\partial D (0, K_{n})}

. Since

\begin{matrix} P (T_{\partial D (x, r_{n, 0})} < T_{\partial D (0, K_{n})}) \geq P (T_{\partial D (x, r_{n, 0})} < T_{\partial D (x, \frac{1}{2} K_{n})}) \end{matrix}

(4.4)

we see from ( 4.3 ) that uniformly in

n

and

x \in U_{n}

\begin{matrix} P (T_{\partial D (x, r_{n, 0})} < T_{\partial D (0, K_{n})}) \geq c \end{matrix}

(4.5)

for some

c > 0

. And since for

x \in U_{n}

and

y \in \partial D (x, r_{n, 0})

\begin{matrix} P^{y} (T_{\partial D (x, r_{n, 1})} < T_{\partial D (x, \frac{1}{2} K_{n})}) \end{matrix}

(4.6)

\begin{matrix} \leq P^{y} (T_{\partial D (x, r_{n, 1})} < T_{\partial D (0, K_{n})}) \end{matrix}

\begin{matrix} \leq P^{y} (T_{\partial D (x, r_{n, 1})} < T_{\partial D (x, 2 K_{n})}) \end{matrix}

we see from ( 4.3 ) that uniformly in

n

x \in U_{n}

and

y \in \partial D (x, r_{n, 0})

\begin{matrix} c / log n \leq P^{y} (T_{\partial D (x, r_{n, 1})} < T_{\partial D (0, K_{n})}) \leq c^{'} / log n . \end{matrix}

(4.7)

Similarly, since for

x \in U_{n}

and

y \in \partial D (x, r_{n, 0})

\begin{matrix} P^{y} (T_{\partial D (0, K_{n})} < T_{\partial D (x, r_{n, 1})}) \geq P^{y} (T_{\partial D (x, 2 K_{n})} < T_{\partial D (x, r_{n, 1})}) \end{matrix}

(4.8)

we see from ( 4.2 ) that uniformly in

n

x \in U_{n}

and

y \in \partial D (x, r_{n, 0})

\begin{matrix} P^{y} (T_{\partial D (0, K_{n})} < T_{\partial D (x, r_{n, 1})}) \geq c > 0 . \end{matrix}

(4.9)

These bounds will be used for excursions at the `top' levels. To bound excursions at `intermediate' levels we note that using ( 4.2 ), we have uniformly for

x \in \partial D (0, r_{n, l})

, with

1 \leq l \leq n - 1

\begin{matrix} P^{x} (T_{\partial D (0, r_{n, l - 1})} < T_{\partial D (0, r_{n, l + 1})}) = 1 / 2 + O (n^{- 8}) \end{matrix}

(4.10)

and consequently also

\begin{matrix} P^{x} (T_{\partial D (0, r_{n, l + 1})} < T_{\partial D (0, r_{n, l - 1})}) = 1 / 2 + O (n^{- 8}) . \end{matrix}

(4.11)

Let

\bar{m} = (m_{2}, m_{3}, \dots, m_{n})

and set

| \bar{m} | = 2 \sum_{j = 2}^{n} m_{j} + 1

. Let

ℋ_{n} (\bar{m})

, be the collection of maps, (`histories'),

φ : {0, 1, \dots, | \bar{m} |} \mapsto {0, 1, \dots, n}

such that

φ (0) = 1, φ (j + 1) = φ (j) \pm 1, | \bar{m} | = inf {j; φ (j) = 0}

and the number of upcrossings from

ℓ - 1

ℓ

u (ℓ) = : | {(j, j + 1) | (φ (j), φ (j + 1)) = (ℓ - 1, ℓ)} | .

The number of ways to partition the

u (ℓ + 1)

upcrossings from

ℓ

ℓ + 1

among and after the

u (ℓ)

upcrossings from

ℓ - 1

ℓ

\begin{matrix} (\binom{u (ℓ + 1) + u (ℓ) - 1}{u (ℓ) - 1}) . \end{matrix}

(4.12)

Since

u (ℓ) = m_{ℓ}

and the mapping

φ

is completely determined once we know the relative order of all its upcrossings

\begin{matrix} | ℋ_{n} (\bar{m}) | =^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) . \end{matrix}

(4.13)

To each random walk path we assign a `history'

h (ω)

as follows. Let

τ (0)

be the time of the first visit to

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

, and define

τ (1), τ (2), \dots

to be the successive hitting times of different elements of

{\partial D (x, r_{n, 0}), \dots, \partial D (x, r_{n, n})}

until the first downcrossing from

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

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

. Setting

Φ (y) = k

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

, let

h (ω) (j) = Φ (ω (τ (j)))

. Let

h_{|_{k}}

be the restriction of

h

{0, \dots, k}

. We claim that uniformly for any

φ \in ℋ_{n} (\bar{m})

and

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

\begin{matrix} P^{z} {h_{|_{| \bar{m} |}} = φ} = {(\frac{1}{2})}^{| \bar{m} | - m_{n}} {1 + O (n^{- 8})}^{| \bar{m} | - m_{n}} . \end{matrix}

(4.14)

To see this, simply use the Markov property successively at the times

τ (0), τ (1), \dots, τ (| \bar{m} | - 1)

and then use ( 4.10 ), ( 4.11 ). (The

m_{n}

downcrossings from

n

n - 1

come `for free').

Writing

m \overset{k}{\sim} n_{k}

m = 1

for

k < k_{0}

and

| m - n_{k} | \leq k

for

k \geq k_{0}

we see that uniformly in

m_{n} \overset{n}{\sim} n_{n}

we have that

{1 + O (n^{- 8})}^{| \bar{m} |} = 1 + O (n^{- 4})

. Combining this with ( 4.13 ) and ( 4.14 ) we see that uniformly in

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

\begin{matrix} \sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}} P^{z} {h_{|_{| \bar{m} |}} \in ℋ_{n} (\bar{m})} \end{matrix}

(4.15)

\begin{matrix} = (1 + O (n^{- 4})) \sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}} {(\frac{1}{2})}^{| \bar{m} | - m_{n}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) \end{matrix}

\begin{matrix} = (1 + O (n^{- 4})) \frac{1}{4} {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} . \end{matrix}

Here we used the fact that

m_{2} = 1

so that

| \bar{m} | - m_{n} = 2 + \sum_{ℓ = 2}^{n - 1} (m_{ℓ + 1} + m_{ℓ})

Lemma 4.1. For some

C = C (a) < \infty

and all

k \geq 2

| m - n_{k + 1} | \leq k + 1

| ℓ + 1 - n_{k} | \leq k

\begin{matrix} \frac{C^{- 1} k^{- 3 a - 1}}{\sqrt{log k}} \leq (\binom{m + ℓ}{ℓ}) {(\frac{1}{2})}^{m + ℓ + 1} \leq \frac{C k^{- 3 a - 1}}{\sqrt{log k}} . \end{matrix}

(4.16)

Proof of Lemma 4.1 : It suffices to consider

k ≫ 1

in which case the binomial coefficient in ( 4.16 ) is well approximated by Stirling's formula

m! = \sqrt{2 π} m^{m} e^{- m} \sqrt{m} (1 + o (1)) .

With

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

it follows that for some

C_{1} < \infty

and all

k

large enough, if

| m - n_{k + 1} | \leq 2 k

| ℓ - n_{k} | \leq 2 k

then

\begin{matrix} | \frac{m}{ℓ} - 1 - \frac{2}{k} | \leq \frac{C_{1}}{k log k} . \end{matrix}

(4.17)

Hereafter, we use the notation

f \sim g

f / g

is bounded and bounded away from zero as

k \to \infty

, uniformly in

{m : | m - n_{k + 1} | \leq 2 k}

and

{ℓ : | ℓ - n_{k} | \leq 2 k}

. We then have by the preceeding observations that

\begin{matrix} (\binom{m + ℓ}{ℓ}) {(\frac{1}{2})}^{m + ℓ + 1} \sim \frac{(m + ℓ)^{m + ℓ}}{\sqrt{ℓ} ℓ^{ℓ} m^{m}} {(\frac{1}{2})}^{m + ℓ} \sim \frac{exp (- ℓ I (\frac{m}{ℓ}))}{\sqrt{k^{2} log k}}, \end{matrix}

(4.18)

where

I (λ) = - (1 + λ) log (1 + λ) + λ log λ + λ log 2 + log 2 .

The function

I (λ)

and its first order derivative vanishes at

1

, with the second derivative

I_{λ λ} (1) = 1 / 2

. Thus, by a Taylor expansion to second order of

I (λ)

1

, the estimate ( 4.17 ) results with

\begin{matrix} | I (\frac{m}{ℓ}) - \frac{1}{k^{2}} | \leq \frac{C_{2}}{k^{2} log k} \end{matrix}

(4.19)

for some

C_{2} < \infty

, all

k

large enough and

m, ℓ

in the range considered here.

Since

| ℓ - 3 a k^{2} log k | \leq 2 k

, combining ( 4.18 ) and ( 4.19 ) we establish ( 4.16 ).

Using the last Lemma we have that

\begin{matrix} {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} \frac{C^{- 1} ℓ^{- 3 a - 1}}{\sqrt{log ℓ}} \end{matrix}

\begin{matrix} \leq {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} \end{matrix}

(4.20)

\begin{matrix} \leq {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} \frac{C ℓ^{- 3 a - 1}}{\sqrt{log ℓ}} . \end{matrix}

Using the fact that

| {m_{ℓ} | m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}} | = 2 ℓ + 1

, this shows that for some

C_{1} < \infty

\begin{matrix} n^{n - 1} \prod_{ℓ = 2} \frac{C_{1}^{- 1} ℓ^{- 3 a}}{\sqrt{log ℓ}} \end{matrix}

\begin{matrix} \leq {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} \end{matrix}

(4.21)

\begin{matrix} \leq n^{n - 1} \prod_{ℓ = 2} \frac{C_{1} ℓ^{- 3 a}}{\sqrt{log ℓ}} . \end{matrix}

Since for any

c < \infty

, for some

ζ_{n}, ζ_{n}^{'} \to 0

\begin{matrix} n {c^{n}}^{n - 1} \prod_{ℓ = 2} log ℓ = n^{n ζ_{n}} = (n!)^{ζ_{n}^{'}} \end{matrix}

(4.22)

we see that for some

δ_{1, n}, δ_{2, n} \to 0

\begin{matrix} {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} = (n!)^{- 3 a - δ_{1, n}} = r_{n, 0}^{- a - δ_{2, n}} . \end{matrix}

(4.23)

( 4.5 )-( 4.9 ) and ( 4.15 ) show that for some

0 < c, c^{'} < \infty

\begin{matrix} \frac{c}{log n} {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} \end{matrix}

(4.24)

\begin{matrix} \leq Q_{n} = {inf}_{x \in U_{n}} P (x is n -successful) \end{matrix}

\begin{matrix} \leq \frac{c^{'}}{log n} {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} . \end{matrix}

Together with ( 4.23 ) this gives ( 3.20 ) and ( 3.21 ).

Let

N_{n, i, m, k}^{x}

denote the number of excursions from

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

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

until completion of the first

m

excursions from

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

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

We note here for later reference that the analysis of this section shows that uniformly in

m_{k} \overset{k}{\sim} n_{k}, k = l, l + 1, \dots, n

and

z \in \partial D (x, r_{n, l})

\begin{matrix} P^{z} (N_{n, l, m_{l}, k}^{x} = m_{k}, k = l + 1, \dots, n) \end{matrix}

(4.25)

\begin{matrix} = (1 + O (n^{- 4}))^{n - 1} \prod_{k = l} (\binom{m_{k + 1} + m_{k} - 1}{m_{k} - 1}) {(\frac{1}{2})}^{m_{k + 1} + m_{k}} . \end{matrix}

Our analysis also shows that for some

δ_{3, l} \to 0

\begin{matrix} {inf}_{\overset{m_{l}}{m_{l} \overset{l}{\sim} n_{l}}} ({\sum_{\overset{m_{2}, \dots, m_{l - 1}}{m_{k} \overset{k}{\sim} n_{k}}}}^{l - 1} \prod_{k = 2} (\binom{m_{k + 1} + m_{k} - 1}{m_{k} - 1}) {(\frac{1}{2})}^{m_{k + 1} + m_{k}}) \geq ((l - 1)!)^{- 3 a - δ_{3, l}}, \end{matrix}

(4.26)

and since

\begin{matrix} {\sum_{\overset{m_{2}, \dots, m_{n}}{m_{ℓ} \overset{ℓ}{\sim} n_{ℓ}}}}^{n - 1} \prod_{ℓ = 2} (\binom{m_{ℓ + 1} + m_{ℓ} - 1}{m_{ℓ} - 1}) {(\frac{1}{2})}^{m_{ℓ + 1} + m_{ℓ}} \end{matrix}

(4.27)

\begin{matrix} \geq {\sum_{\overset{m_{l}, \dots, m_{n}}{m_{k} \overset{k}{\sim} n_{k}}}}^{n - 1} \prod_{k = l} (\binom{m_{k + 1} + m_{k} - 1}{m_{k} - 1}) {(\frac{1}{2})}^{m_{k + 1} + m_{k}} \end{matrix}

\begin{matrix} {inf}_{\overset{m_{l}}{m_{l} \overset{l}{\sim} n_{l}}} ({\sum_{\overset{m_{2}, \dots, m_{l - 1}}{m_{k} \overset{k}{\sim} n_{k}}}}^{l - 1} \prod_{k = 2} (\binom{m_{k + 1} + m_{k} - 1}{m_{k} - 1}) {(\frac{1}{2})}^{m_{k + 1} + m_{k}}) \end{matrix}

(here we used the bound that for

C (i, j), D (i, j)

non-negative,

\sum_{i, j, k} C (i, j) D (j, k) = \sum_{j} \sum_{i} C (i, j) \sum_{k} D (j, k) \geq (\sum_{i, j} C (i, j)) {inf}_{j} \sum_{k} D (j, k)

), we see from ( 4.25 ) and ( 4.24 ) that uniformly in

z \in \partial D (x, r_{n, l})

\begin{matrix} \sum_{\overset{m_{l}, \dots, m_{n}}{m_{k} \overset{k}{\sim} n_{k}}} P^{z} (N_{n, l, m_{l}, k}^{x} = m_{k}, k = l + 1, \dots, n) \leq C log n Q_{n} (l!)^{3 a + δ_{3, l}} . \end{matrix}

(4.28)

Thus from ( 4.7 ) we have

\begin{matrix} \sum_{\overset{m_{l}, \dots, m_{n}}{m_{k} \overset{k}{\sim} n_{k}}} P (N_{n, l, m_{l}, k}^{x} = m_{k}, k = l + 1, \dots, n) \leq C Q_{n} (l!)^{3 a + δ_{3, l}} . \end{matrix}

(4.29)

Similarly, uniformly in

m_{k} \overset{k}{\sim} n_{k}, k = 2, 3, \dots, l

and

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

\begin{matrix} P^{z} (N_{n, 1, 1, k}^{x} = m_{k}, k = 2, \dots, l) \end{matrix}

(4.30)

\begin{matrix} = (1 + O (n^{- 4}))^{l - 1} \prod_{k = 2} (\binom{m_{k + 1} + m_{k} - 1}{m_{k} - 1}) {(\frac{1}{2})}^{m_{k + 1} + m_{k}} . \end{matrix}

5 Second moment estimates

We begin by defining the

σ

-algebra

G_{n, l}^{x}

of excursions from

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

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

. To this end, fix

x \in Z^{2}

, let

{\bar{τ}}_{0} = 0

and for

i = 1, 2, \dots

define

\begin{matrix} τ_{i} & = & inf {t \geq {\bar{τ}}_{i - 1} : X_{t} \in \partial D (x, r_{n, l})}, \end{matrix}

\begin{matrix} {\bar{τ}}_{i} & = & inf {t \geq τ_{i} : X_{t} \in \partial D (x, r_{n, l - 1})} . \end{matrix}

Then

G_{n, l}^{x}

is the

σ

-algebra generated by the excursions

{e^{(j)}, j = 1, \dots}

, where

e^{(j)} = {X_{t} : {\bar{τ}}_{j - 1} \leq t \leq τ_{j}}

is the

j

-th excursion from

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

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

(so for

j = 1

we do begin at

t = 0

The following Lemma is proven in the next section. Note that for any

σ

-algebra

G

and event

B \in G

, we have

P (A, B | G) = P (A | G) 1_{{B}}

Lemma 5.1 (Decoupling Lemma). Let

Γ_{n, l}^{y} = {N_{n, i}^{y} = m_{i}; i = l + 1, l + 2, \dots, n}

. Then, uniformly over all

l \leq n,

m_{l} \overset{l}{\sim} n_{l}

{m_{i} : i = l + 1, l + 2, \dots, n}

y \in U_{n}

and

x_{0}, x_{1} \in Z^{2} \ D (y, r_{n, l})

\begin{matrix} P^{x_{0}} (Γ_{n, l}^{y}, N_{n, l}^{y} = m_{l} | G_{n, l}^{y}) \end{matrix}

(5.1)

\begin{matrix} = (1 + O (n^{- 1} log n)) P^{x_{1}} (Γ_{n, l}^{y} | N_{n, l}^{y} = m_{l}) 1_{{N_{n, l}^{y} = m_{l}}} \end{matrix}

Remark 1. The intuition behind the Decoupling Lemma is that what happens `deep inside'

D (y, r_{n, l})

, e.g.

Γ_{n, l}^{y}

, is `almost' independent of what happens outside

D (y, r_{n, l})

, i.e.

G_{n, l}^{y}

Proof of ( 3.22 ): Recall that

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

and that we write

m \overset{k}{\sim} n_{k}

m = 1

for

k < k_{0}

and

| m - n_{k} | \leq k

for

k \geq k_{0}

. Relying upon the first moment estimates and Lemma 5.1 , we next prove the second moment estimates ( 3.22 ). Take

x, y \in U_{n}

with

l (x, y) = l - 1

. Thus

2 r_{n, l - 1} + 2 \leq | x - y | < 2 r_{n, l - 2} + 2

for some

2 \leq l \leq n

. Since

r_{n, l - 3} - r_{n, l - 2} ≫ 2 r_{n, l - 1}

, it is easy to see that

D (y, r_{n, l - 1}) \cap \partial D (x, r_{n, k}) = \emptyset

for all

k \neq l - 2

. Replacing hereafter

l

l \land (n - 3)

, it follows that for

k \neq l - 1, l - 2

, the events

{N_{n, k}^{x} \overset{k}{\sim} n_{k}}

are measurable on the

σ

-algebra

G_{n, l}^{y}

. With

J_{l} : = {l + 1, \dots, n}

and

I_{l} : = {2, \dots, l - 3, l, \dots, n}

, set

{\tilde{Γ}}_{n}^{y} (J_{l}) = {N_{n, k}^{y} \overset{k}{\sim} n_{k}, k \in J_{l}}

and

{\tilde{Γ}}_{n}^{x} (I_{l}) = {N_{n, k}^{x} \overset{k}{\sim} n_{k}, k \in I_{l}}

. We note that

\begin{matrix} {x, y are n -successful} \end{matrix}

(5.2)

\begin{matrix} \subseteq ⋃_{m_{l} \overset{l}{\sim} n_{l}} {\tilde{Γ}}_{n}^{y} (J_{l}) \cap {N_{n, l}^{y} = m_{l}} \cap {\tilde{Γ}}_{n}^{x} (I_{l}) . \end{matrix}

Applying ( 5.1 ), we have that for some universal constant

C_{3} < \infty

\begin{matrix} P (x and y are n -successful) \end{matrix}

(5.3)

\begin{matrix} \leq \sum_{m_{l} \overset{l}{\sim} n_{l}} P [{\tilde{Γ}}_{n}^{y} (J_{l}), {N_{n, l}^{y} = m_{l}}, {\tilde{Γ}}_{n}^{x} (I_{l})] \end{matrix}

\begin{matrix} = \sum_{m_{l} \overset{l}{\sim} n_{l}} E [P ({\tilde{Γ}}_{n}^{y} (J_{l}), N_{n, l}^{y} = m_{l} | G_{n, l}^{y}); {\tilde{Γ}}_{n}^{x} (I_{l})] \end{matrix}

\begin{matrix} \leq C_{3} P ({\tilde{Γ}}_{n}^{x} (I_{l})) \sum_{m_{l} \overset{l}{\sim} n_{l}} P ({\tilde{Γ}}_{n}^{y} (J_{l}) | N_{n, l}^{y} = m_{l}) \end{matrix}

Using the Markov property and ( 4.29 ), for some universal constant

C_{5} < \infty

\begin{matrix} \sum_{m_{l} \overset{l}{\sim} n_{l}} P ({\tilde{Γ}}_{n}^{y} (J_{l}) | N_{n, l}^{y} = m_{l}) \leq C_{5} Q_{n} (l!)^{3 a + δ_{3, l}} . \end{matrix}

(5.4)

Similarly, with

M_{l - 3} : = {2, \dots, l - 3}

, and

{\tilde{Γ}}_{n}^{x} (M_{l - 3}) = {N_{n, k}^{x} \overset{k}{\sim} n_{k}, k \in M_{l - 3}},

( 5.1 ) shows that

\begin{matrix} P ({\tilde{Γ}}_{n}^{x} (I_{l})) & \leq & \sum_{m_{l} \overset{l}{\sim} n_{l}} E [P ({\tilde{Γ}}_{n}^{x} (J_{l}), N_{n, l}^{x} = m_{l} | G_{n, l}^{x}); {\tilde{Γ}}^{x} (M_{l - 3})] \end{matrix}

(5.5)

\begin{matrix} \leq & C_{6} P ({\tilde{Γ}}_{n}^{x} (M_{l - 3})) \sum_{m_{l} \overset{l}{\sim} n_{l}} P ({\tilde{Γ}}_{n}^{x} (J_{l}) | N_{n, l}^{x} = m_{l}) . \end{matrix}

Using ( 4.15 ), ( 4.23 ) and ( 5.4 ) we get that, for some

δ_{4, l} \to 0

\begin{matrix} P ({\tilde{Γ}}_{n}^{x} (I_{l})) \leq C_{7} l^{15} (l!)^{δ_{4, l}} Q_{n} . \end{matrix}

(5.6)

Putting ( 5.3 ), ( 5.4 ) and ( 5.6 ) together and adjusting

C

and

δ_{l - 1}^{'}

proves ( 3.22 ) for

l (x, y) = l - 1

6 Harnack inequalities and approximate decoupling

The goal of this section is to prove the Decoupling Lemma, Lemma 5.1 .

Since what happens `deep inside'

D (y, r_{n, l})

, e.g.

Γ_{n, l}^{y}

, depends on what happens outside

D (y, r_{n, l})

, i.e. on

G_{n, l}^{y}

, only through the initial and end points of the excursions from

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

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

, we begin by studying the dependence on these initial and end points. The following Harnack inequality plays a crucial role in this analysis.

Define the hitting distribution of

A

\begin{matrix} H_{A} (x, y) = P^{x} (X_{T_{A}} = y) . \end{matrix}

(6.1)

Lemma 6.1. Uniformly for

x, x^{'} \in D (0, ɛ n)

ɛ < 1 / 4

and

y \in D (0, n)^{c}

\begin{matrix} H_{D (0, n)^{c}} (x, y) = (1 + O (ɛ)) H_{D (0, n)^{c}} (x^{'}, y) . \end{matrix}

(6.2)

Furthermore, if

ɛ^{'} < ɛ

are such that

{inf}_{x \in \partial D (0, ɛ n)} P^{x} (T_{D (0, n)^{c}} < T_{\partial D (0, ɛ^{'} n)}) \geq 1 / 4,

then uniformly in

x \in \partial D (0, ɛ n)

and

y \in D (0, n)^{c}

\begin{matrix} P^{x} (X_{T_{D (0, n)^{c}}} = y, T_{D (0, n)^{c}} < T_{\partial D (0, ɛ^{'} n)}) \end{matrix}

(6.3)

\begin{matrix} = (1 + O (ɛ)) P^{x} (T_{D (0, n)^{c}} < T_{\partial D (0, ɛ^{'} n)}) H_{D (0, n)^{c}} (x, y) . \end{matrix}

Proof of Lemma 6.1 : ( 6.2 ) is formula (2.7) of [4] .

Turning to ( 6.3 ), we have

\begin{matrix} P^{x} (X_{T_{D (0, n)^{c}}} = y, T_{D (0, n)^{c}} < T_{\partial D (0, ɛ^{'} n)}) \end{matrix}

(6.4)

\begin{matrix} = H_{D (0, n)^{c}} (x, y) - P^{x} (X_{T_{D (0, n)^{c}}} = y, T_{D (0, n)^{c}} > T_{\partial D (0, ɛ^{'} n)}) . \end{matrix}

By the strong Markov property at

T_{\partial D (0, ɛ^{'} n)}

\begin{matrix} P^{x} (X_{T_{D (0, n)^{c}}} = y, T_{D (0, n)^{c}} > T_{\partial D (0, ɛ^{'} n)}) \end{matrix}

(6.5)

\begin{matrix} = E^{x} (H_{D (0, n)^{c}} (X_{T_{\partial D (0, ɛ^{'} n)}}, y); T_{D (0, n)^{c}} > T_{\partial D (0, ɛ^{'} n)}) . \end{matrix}

By ( 6.2 ), uniformly in

w \in \partial D (0, ɛ^{'} n)

H_{D (0, n)^{c}} (w, y) = (1 + O (ɛ)) H_{D (0, n)^{c}} (x, y)) .

Substituting back into ( 6.5 ) we have

\begin{matrix} P^{x} (X_{T_{D (0, n)^{c}}} = y, T_{D (0, n)^{c}} > T_{\partial D (0, ɛ^{'} n)}) \end{matrix}

\begin{matrix} = (1 + O (ɛ)) P^{x} (T_{D (0, n)^{c}} > T_{\partial D (0, ɛ^{'} n)}) H_{D (0, n)^{c}} (x, y) . \end{matrix}

Combining this with ( 6.4 ) we obtain

\begin{matrix} P^{x} (X_{T_{D (0, n)^{c}}} = y, T_{D (0, n)^{c}} < T_{\partial D (0, ɛ^{'} n)}) \end{matrix}

(6.6)

\begin{matrix} = (P^{x} (T_{D (0, n)^{c}} < T_{\partial D (0, ɛ^{'} n)}) + O (ɛ)) H_{D (0, n)^{c}} (x, y) . \end{matrix}

Using the assumptions of the lemma we obtain ( 6.3 ) which completes the proof of Lemma 6.1 .

Consider a random path beginning at

z \in \partial D (0, r_{n, l})

. We will show that for

n

large, a certain

σ

-algebra of excursions of the path from

\partial D (0, r_{n, l + 1})

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

prior to

T_{\partial D (0, r_{n, l - 1})}

, is almost independent of the choice of initial point

z \in \partial D (0, r_{n, l})

and final point

w \in \partial D (0, r_{n, l - 1})

. Let

τ_{0} = 0

and for

i = 0, 1, \dots

define

\begin{matrix} τ_{2 i + 1} & = & inf {t \geq τ_{2 i} : X_{t} \in \partial D (0, r_{n, l + 1}) \cup \partial D (0, r_{n, l - 1})} \end{matrix}

\begin{matrix} τ_{2 i + 2} & = & inf {t \geq τ_{2 i + 1} : X_{t} \in \partial D (0, r_{n, l})} . \end{matrix}

Abbreviating

\bar{τ} = T_{\partial D (0, r_{n, l - 1})}

note that

\bar{τ} = τ_{2 I + 1}

for some (unique) non-negative integer

I

. As usual,

ℱ_{j}

will denote the

σ -

algebra generated by

{X_{l}, l = 0, 1, \dots, j}

, and for any stopping time

τ

ℱ_{τ}

will denote the collection of events

A

such that

A \cap {τ = j} \in ℱ_{j}

for all

j

Let

ℋ_{n, l}

denote the

σ

-algebra generated by the excursions of the path from

\partial D (0, r_{n, l + 1})

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

, prior to

T_{\partial D (0, r_{n, l - 1})}

. Then

ℋ_{n, l}

is the

σ

-algebra generated by the excursions

{v^{(j)}, j = 1, \dots, I}

, where

v^{(j)} = {X_{t} : τ_{2 j - 1} \leq t \leq τ_{2 j}}

is the

j

-th excursion from

\partial D (0, r_{n, l + 1})

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

. We denote by

U ({ℋ_{n, l}})

the collection of sequences of sets

{B_{n}; n = 1, 2, \dots}, B_{n} \in ℋ_{n, l}

such that uniformly in

x, x^{'} \in \partial D (0, r_{n, l + 1})

\begin{matrix} P^{x} (B_{n}) = (1 + O (n^{- 4})) P^{x^{'}} (B_{n}) . \end{matrix}

(6.7)

Lemma 6.2. For a random walk path starting at

z \in \partial D (0, r_{n, l})

, let

ℋ_{n, l}

denote the

σ

-algebra generated by the excursions of the path from

\partial D (0, r_{n, l + 1})

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

, prior to

T_{\partial D (0, r_{n, l - 1})}

. Then, uniformly in

n

z \in \partial D (0, r_{n, l})

w \in \partial D (0, r_{n, l - 1})

, and

B_{n} \in ℋ_{n, l}

\begin{matrix} P^{z} (B_{n} | X_{T_{\partial D (0, r_{n, l - 1})}} = w) = (1 + O (n^{- 3})) P^{z} (B_{n}) . \end{matrix}

(6.8)

Furthermore, uniformly in

n

z, z^{'} \in \partial D (0, r_{n, l})

, and sequences

B_{n} \in U ({ℋ_{n, l}})

\begin{matrix} P^{z} (B_{n}) = (1 + O (n^{- 3})) P^{z^{'}} (B_{n}) . \end{matrix}

(6.9)

When we say that a statement such as ( 6.9 ) is uniform in sequences

B_{n} \in U ({ℋ_{n, l}})

, we mean that there exists a

0 < d < \infty

such that if uniformly in

x, x^{'} \in \partial D (0, r_{n, l + 1})

\begin{matrix} (1 - c n^{- 4}) P^{x^{'}} (B_{n}) \leq P^{x} (B_{n}) \leq (1 + c n^{- 4}) P^{x^{'}} (B_{n}) . \end{matrix}

(6.10)

then uniformly in

z, z^{'} \in \partial D (0, r_{n, l})

\begin{matrix} (1 - d c n^{- 3}) P^{z^{'}} (B_{n}) \leq P^{z} (B_{n}) \leq (1 + d c n^{- 3}) P^{z^{'}} (B_{n}) . \end{matrix}

(6.11)

Proof of Lemma 6.2 : Fixing

z \in \partial D (0, r_{n, l})

it suffices to consider

B_{n} \in ℋ_{n, l}

for which

P^{z} (B_{n}) > 0

. Fix such a set

B_{n}

and a point

w \in \partial D (0, r_{n, l - 1})

Using the notation introduced right before the statement of our Lemma, for any

i \geq 1

, we can write

{B_{n}, I = i} = {B_{n, i}, τ_{2 i} < \bar{τ}} \cap ({I = 0} \circ θ_{τ_{2 i}})

for some

B_{n, i} \in ℱ_{τ_{2 i}} = {A | A \cap}

, so by the strong Markov property at

τ_{2 i}

P^{z} [X_{\bar{τ}} = w; B_{n}, I = i] = E^{z} [P^{X_{τ_{2 i}}} (X_{\bar{τ}} = w, I = 0); B_{n, i}, τ_{2 i} < \bar{τ}],

and

P^{z} (B_{n}, I = i) = E^{z} [P^{X_{τ_{2 i}}} (I = 0); B_{n, i}, τ_{2 i} < \bar{τ}] .

Consequently, for all

i \geq 1

\begin{matrix} P^{z} [X_{\bar{τ}} = w; B_{n}, I = i] \end{matrix}

(6.12)

\begin{matrix} \geq P^{z} (B_{n}, I = i) {inf}_{x \in \partial D (0, r_{n, l})} \frac{P^{x} (X_{\bar{τ}} = w; I = 0)}{P^{x} (I = 0)} . \end{matrix}

Necessarily

P^{z} (B_{n} | I = 0) \in {0, 1}

and is independent of

z

for any

B_{n} \in ℋ_{n, l}

, implying that ( 6.12 ) applies for

i = 0

as well. By ( 6.3 ), ( 6.2 ) and ( 4.2 ) there exists

c < \infty

such that for any

z, x \in \partial D (0, r_{n, l})

and

w \in \partial D (0, r_{n, l - 1})

\frac{P^{x} (X_{\bar{τ}} = w; I = 0)}{E^{x} (I = 0)} \geq (1 - c n^{- 3}) H_{D (0, r_{n, l - 1})^{c}} (z, w) .

Hence, summing ( 6.12 ) over

I = 0, 1, \dots

, we get that

P^{z} [X_{\bar{τ}} = w, B_{n}] \geq (1 - c n^{- 3}) P^{z} (B_{n}) H_{D (0, r_{n, l - 1})^{c}} (z, w) .

A similar argument shows that

P^{z} [X_{\bar{τ}} = w, B_{n}] \leq (1 + c n^{- 3}) P^{z} (B_{n}) H_{D (0, r_{n, l - 1})^{c}} (z, w),

and we thus obtain ( 6.8 ).

By the Markov property at

τ_{1}

, for any

z \in \partial D (0, r_{n, l})

\begin{matrix} P^{z} (B_{n}) = P^{z} (B_{n}, I = 0) \end{matrix}

\begin{matrix} + \sum_{x \in \partial D (0, r_{n, l + 1})} H_{D (0, r_{n, l + 1}) \cup D (0, r_{n, l - 1})^{c}} (z, x) P^{x} (B_{n}) . \end{matrix}

The term involving

{B_{n}, I = 0}

is dealt with by ( 4.10 ) and by ( 6.7 ). For any fixed

x_{0} \in \partial D (0, r_{n, l + 1})

\begin{matrix} \sum_{x \in \partial D (0, r_{n, l + 1})} H_{D (0, r_{n, l + 1}) \cup D (0, r_{n, l - 1})^{c}} (z, x) P^{x} (B_{n}) \end{matrix}

(6.13)

\begin{matrix} = (1 + O (n^{- 4})) P^{x_{0}} (B_{n}) \sum_{x \in \partial D (0, r_{n, l + 1})} H_{D (0, r_{n, l + 1}) \cup D (0, r_{n, l - 1})^{c}} (z, x) \end{matrix}

\begin{matrix} = (1 + O (n^{- 4})) P^{x_{0}} (B_{n}) P^{z} (T_{D (0, r_{n, l + 1})} < T_{D (0, r_{n, l - 1})^{c}}) \end{matrix}

so that ( 6.9 ) follows by ( 4.11 ).

Building upon Lemma 6.2 we quantify the independence between the

σ

-algebra

G_{n, l}^{x}

of excursions from

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

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

introduced in the previous section and the

σ

-algebra

ℋ_{n, l}^{x} (m)

of excursions from

\partial D (x, r_{n, l + 1})

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

during the first

m

excursions from

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

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

To this end, fix

x \in Z^{2}

, let

{\bar{τ}}_{0} = 0

and for

i = 1, 2, \dots

recall that

\begin{matrix} τ_{i} & = & inf {t \geq {\bar{τ}}_{i - 1} : X_{t} \in \partial D (x, r_{n, l})}, \end{matrix}

\begin{matrix} {\bar{τ}}_{i} & = & inf {t \geq τ_{i} : X_{t} \in \partial D (x, r_{n, l - 1})} \end{matrix}

and that

G_{n, l}^{x}

is the

σ

-algebra generated by the excursions

{e^{(j)}, j = 1, \dots}

, where

e^{(j)} = {X_{t} : {\bar{τ}}_{j - 1} \leq t \leq τ_{j}}

is the

j

-th excursion from

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

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

(so for

j = 1

we do begin at

t = 0

We denote by

ℋ_{n, l}^{x} (m)

the

σ

-algebra generated by all excursions from

\partial D (x, r_{n, l + 1})

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

from time

τ_{1}

until time

{\bar{τ}}_{m}

. In more detail, for each

j = 1, 2, \dots, m

let

{\bar{ζ}}_{j, 0} = τ_{j}

and for

i = 1, \dots

define

\begin{matrix} ζ_{j, i} & = & inf {t \geq {\bar{ζ}}_{j, i - 1} : X_{t} \in \partial D (x, r_{n, l + 1})}, \end{matrix}

\begin{matrix} {\bar{ζ}}_{j, i} & = & inf {t \geq ζ_{j, i} : X_{t} \in \partial D (x, r_{n, l})} . \end{matrix}

Let

v_{j, i} = {X_{t} : ζ_{j, i} \leq t \leq {\bar{ζ}}_{j, i}}

and

Z^{j} = sup {i \geq 0 : {\bar{ζ}}_{j, i} < {\bar{τ}}_{j}}

Then,

ℋ_{n, l}^{x} (m)

is the product

σ

-algebra generated by the

σ

-algebras

ℋ_{n, l, j}^{x} = σ (v_{j, i}, i = 1, \dots, Z^{j})

of the excursions between times

τ_{j}

and

{\bar{τ}}_{j}

, for

j = 1, \dots, m

We denote by

U ({ℋ_{n, l}^{x} (m)})

the collection of sequences of sets

H_{n} \in ℋ_{n, l}^{x} (m)

of the form

H_{n} = H_{n, 1} \cap H_{n, 2} \cap \dots \cap H_{n, m}

, with

H_{n, j} \in U ({ℋ_{n, l, j}^{x}})

for

j = 1, \dots, m

Lemma 6.3. Uniformly over all

l \leq n

m \leq (n log n)^{2}

x, y_{0}, y_{1} \in Z^{2}

and

H_{n} \in U ({ℋ_{n, l}^{x} (m)})

\begin{matrix} (1 - O (m n^{- 3})) P^{y_{1}} (H_{n}) \leq P^{y_{0}} (H_{n} | G_{n, l}^{x}) \end{matrix}

(6.14)

\begin{matrix} \leq (1 + O (m n^{- 3})) P^{y_{1}} (H_{n}) . \end{matrix}

Proof of Lemma 6.3 : We can write

H_{n} = H_{n, 1} \cap H_{n, 2} \cap \dots \cap H_{n, m}

, with

H_{n, j} \in U ({ℋ_{n, l, j}^{x}})

for

j = 1, \dots, m

. Conditioned upon

G_{n, l}^{x}

the events

H_{n, j}

are independent. Further, each

H_{n, j}

then has the conditional law of an event

B_{n, j}

in the collection

U ({ℋ_{n, l}})

of Lemma 6.2 , for some random

z_{j} = X_{τ_{j}} - x \in \partial D (0, r_{n, l})

and

w_{j} = X_{{\bar{τ}}_{j}} - x \in \partial D (0, r_{n, l - 1})

, both measurable on

G_{n, l}^{x}

. By our conditions, the uniform estimates ( 6.8 ) and ( 6.9 ) yield that for any fixed

z^{'} \in \partial D (0, r_{n, l})_{s}

\begin{matrix} P^{y_{0}} (H_{n} | G_{n, l}^{x}) & = P^{y_{0}} (\cap_{j = 1}^{m} (H_{n, j}) | G_{n, l}^{x}) \end{matrix}

(6.15)

\begin{matrix} =^{m} \prod_{j = 1} P^{z_{j}} (B_{n, j} | X_{T_{\partial D (0, r_{n, l})^{c}}} = w_{j}) \end{matrix}

\begin{matrix} =^{m} \prod_{j = 1} (1 + O (n^{- 3})) P^{z_{j}} (B_{n, j}) \end{matrix}

\begin{matrix} = (1 + O (n^{- 3}) {)^{m}}^{m} \prod_{j = 1} P^{z^{'}} (B_{n, j}) . \end{matrix}

Since

m \leq (n log n)^{2}

and the right-hand side of ( 6.15 ) neither depends on

y_{0} \in Z^{2}

nor on the extra information in

G_{n, l}^{x}

, we get ( 6.14 ) by averaging over

G_{n, l}^{x}

Proof of Lemma 5.1 : For

j = 1, 2, \dots

and

i = l + 1, l + 2, \dots, n

, let

Z_{i}^{j}

denote the number of excursions from

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

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

by the random walk during the time interval

[τ_{j}, {\bar{τ}}_{j}]

. Using ( 4.25 ), the event

H_{n} = {\sum_{j = 1}^{m_{l}} Z_{i}^{j} = m_{i} : i = l + 1, l + 2, \dots, n}

can be written as a disjoint union of events in the collection

U ({ℋ_{n, l}^{y} (m_{l})})

of Lemma 6.3 . It is easy to verify that starting at any

x / \in D (y, r_{n, l})

, when the event

{N_{n, l}^{y} = m_{l}} \in G_{n, l}^{y}

occurs, it implies that

N_{n, i}^{y} = \sum_{j = 1}^{m_{l}} Z_{i}^{j}

for

i = l + 1, l + 2, \dots, n

. Thus,

\begin{matrix} P^{x_{0}} (Γ_{n, l}^{y} | G_{n, l}^{y}) 1_{{N_{n, l}^{y} = m_{l}}} = P^{x_{0}} (H_{n} | G_{n, l}^{y}) 1_{{N_{n, l}^{y} = m_{l}}} . \end{matrix}

(6.16)

With

m_{l} / (n^{2} log n)

bounded above, by ( 6.14 ) we have, uniformly in

y \in Z^{2}

and

x_{0}, x_{1} \in Z^{2} \ D (y, r_{n, l})

\begin{matrix} P^{x_{0}} (H_{n} | G_{n, l}^{y}) = (1 + O (n^{- 1} log n)) P^{x_{1}} (H_{n}) . \end{matrix}

(6.17)

Hence,

\begin{matrix} P^{x_{0}} (Γ_{n, l}^{y} | G_{n, l}^{y}) 1_{{N_{n, l}^{y} = m_{l}}} = (1 + O (n^{- 1} log n)) P^{x_{1}} (H_{n}) 1_{{N_{n, l}^{y} = m_{l}}} . \end{matrix}

(6.18)

Taking

x_{0} = x_{1}

and averaging, one has

\begin{matrix} P^{x_{1}} (Γ_{n, l}^{y} | N_{n, l}^{y} = m_{l}) = (1 + O (n^{- 1} log n)) P^{x_{1}} (H_{n}) \end{matrix}

(6.19)

Hence,

\begin{matrix} P^{x_{1}} (Γ_{n, l}^{y} | N_{n, l}^{y} = m_{l}) 1_{{N_{n, l}^{y} = m_{l}}} \end{matrix}

(6.20)

\begin{matrix} = (1 + O (n^{- 1} log n)) P^{x_{1}} (H_{n}) 1_{{N_{n, l}^{y} = m_{l}}} \end{matrix}

\begin{matrix} = (1 + O (n^{- 1} log n)) P^{x_{0}} (Γ_{n, l}^{y} | G_{n, l}^{y}) 1_{{N_{n, l}^{y} = m_{l}}} \end{matrix}

where we used ( 6.18 ) for the last equality. Using that

{N_{n, l}^{y} = m_{l}} \subset G_{n, l}^{y}

, this is ( 5.1 ).

Acknowledgements I am grateful to Endre Csáki and Antónia Földes for many helpful comments.

References

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, Late points for random walks in two dimensions, Annals of Probability, to appear.
J.-P. Kahane, Some random series of functions: Second Edition, Cambridge University Press, (1985).
G. Lawler, Intersections of random walks. Birkhauser, (1991).
P. Révész, Random Walk in Random and Non-Random Environments, World Scientific, Singapore (1990).

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

March 2, 2005. ‡ Research supported, in part, by grants from the NSF and from PSC-CUNY

Jay Rosen ‡