Tài liệu Đề tài " Cover times for Brownian motionand random walks in two dimensions " pdf

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Tài liệu Đề tài " Cover times for Brownian motionand random walks in two dimensions " pdf": http://123doc.vn/document/1036266-tai-lieu-de-tai-cover-times-for-brownian-motionand-random-walks-in-two-dimensions-pdf.htm

436 AMIR DEMBO, YUVAL PERES, JAY ROSEN, AND OFER ZEITOUNI
1.3. Covering a large disk by random walk in Z
2
. Over ten years ago,
Kesten (as quoted by Aldous [1] and Lawler [21]) and R´ev´esz [26] independently
considered a problem about simple random walks in Z
2
: How long does it take
for the walk to completely cover the disc of radius n? Denote this time by T
n
.
Kesten and R´ev´esz proved that
e
−b/t
≤ lim inf
n→∞
P(log T
n
≤ t(log n)
2
) ≤ lim sup
n→∞
P(log T
n
≤ t(log n)
2
) ≤ e
−a/t
(1.4)
for certain 0 <a<b<∞.R´ev´esz [26] conjectured that the limit exists and
has the form e
−λ/t
for some (unspecified) λ. Lawler [21] obtained (1.4) with
the constants a =2,b= 4 and quoted a conjecture of Kesten that the limit
equals e
−4/t
. We can now prove this:
Theorem 1.4. If T
n
denotes the time it takes for the simple random walk
in Z
2
to completely cover the disc of radius n, then
lim
n→∞
P(log T
n
≤ t(log n)
2
)=e
−4/t
.(1.5)
1.4. A birds-eye view. The basic approach of this paper, as in [13], is
to control ε-hitting times using excursions between concentric circles. The
number of excursions between two fixed concentric circles before ε-coverage is
so large, that the ε-hitting times will necessarily be concentrated near their
conditional means given the excursion counts (see Lemma 3.2).
The key idea in the proof of the lower bound in Theorem 1.2, is to control
excursions on many scales simultaneously, leading to a ‘multi-scale refinement’
of the classical second moment method. This is inspired by techniques from
probability on trees, in particular the analysis of first-passage percolation by
Lyons and Pemantle [22]. The approximate tree structure that we (implicitly)
use arises by consideration of circles of varying radii around different centers;
for fixed centers x, y, and “most” radii r (on a logarithmic scale) the discs
D
T
2
(x, r) and D
T
2
(y, r) are either well-separated (if r  d(x, y)) or almost
coincide (if r  d(x, y)). This tree structure was also the key to our work in
[13], but the dependence problems encountered in the present work are more
severe. While in [13] the number of macroscopic excursions was bounded, here
it is large; In the language of trees, one can say that while in [13] we studied
the maximal number of visits to a leaf until visiting the root, here we study the
number of visits to the root until every leaf has been visited. For the analogies
between trees and Brownian excursions to be valid, the effect of the initial
and terminal points of individual excursions must be controlled. To prevent
conditioning on the endpoints of the numerous macroscopic excursions to affect
the estimates, the ratios between radii of even the largest pair of concentric
circles where excursions are counted, must grow to infinity as ε decreases to
zero.
COVER TIMES FOR PLANAR BROWNIAN MOTION AND RANDOM WALKS
437
Section 2 provides simple lemmas which will be useful in exploiting the
link between excursions and ε-hitting times. These lemmas are then used
to obtain the upper bound in Theorem 1.2. In Section 3 we explain how to
obtain the analogous lower bound, leaving some technical details to lemmas
which are proven in Sections 6 and 7. In Section 4 we prove the lattice torus
covering time conjecture, Theorem 1.1, and in Section 5 we prove the Kesten-
R´ev´esz conjecture, Theorem 1.4. In Section 8 we consider Brownian motion
on manifolds and prove Theorem 1.3. Complements and open problems are
collected in the final section.
2. Hitting time estimates and upper bounds
We start with some definitions. Let {W
t
}
t≥0
denote planar Brownian
motion started at the origin. We use T
2
to denote the two dimensional torus,
which we identify with the set (−1/2, 1/2]
2
. The distance between x, y ∈ T
2
,
in the natural metric, is denoted d(x, y). Let X
t
= W
t
mod Z
2
denote the
Brownian motion on T
2
, where a mod Z
2
=[a+(1/2, 1/2)] mod Z
2
−(1/2, 1/2).
Throughout, D(x, r) and D
T
2
(x, r) denote the open discs of radius r centered
at x,inR
2
and in T
2
, respectively.
Fixing x ∈ T
2
let τ
ξ
= inf{t ≥ 0:X
t
∈ ∂D
T
2
(x, ξ)} for ξ>0. Also let
τ
ξ
= inf{t ≥ 0:B
t
∈ ∂D(0,ξ)}, for a standard Brownian motion B
t
on R
2
.
For any x ∈ T
2
, the natural bijection i = i
x
: D
T
2
(x, 1/2) → D(0, 1/2) with
i
x
(x) = 0 is an isometry, and for any z ∈ D
T
2
(x, 1/2) and Brownian motion X
t
on T
2
with X
0
= z, we can find a Brownian motion B
t
starting at i
x
(z) such
that τ
1/2
= τ
1/2
and {i
x
(X
t
),t≤ τ
1/2
} = {B
t
,t≤ τ
1/2
}. We shall hereafter use
i to denote i
x
, whenever the precise value of x is understood from the context,
or does not matter.
We start with some uniform estimates on the hitting times E
y
(τ
r
).
Lemma 2.1. For some c<∞ and all r>0 small enough,
τ
r
 := sup
y
E
y
(τ
r
) ≤ c|log r|.(2.1)
Further, there exists η(R) → 0 as R → 0, such that for all 0 < 2r ≤ R, x ∈ T
2
,
(1 − η)
π
log

R
r

≤ inf
y∈∂D
T
2
(x,R)
E
y
(τ
r
)(2.2)
≤ sup
y∈∂D
T
2
(x,R)
E
y
(τ
r
) ≤
(1 + η)
π
log

R
r

.
Proof of Lemma 2.1. Let ∆ denote the Laplacian, which on T
2
is just the
Euclidean Laplacian with periodic boundary conditions. It is well known that
for any x ∈ T
2
there exists a Green’s function G
x
(y), defined for y ∈ T
2
\{x},
438 AMIR DEMBO, YUVAL PERES, JAY ROSEN, AND OFER ZEITOUNI
such that ∆G
x
= 1 and F (x, y)=G
x
(y)+
1
2π
log d(x, y) is continuous on
T
2
× T
2
(c.f. [8, p. 106] or [16] where this is shown in the more general
context of smooth, compact two-dimensional Riemannian manifolds without
boundary). For completeness, we explicitly construct such G
x
(·) at the end of
the proof.
Let e(y)=E
y
(τ
r
). We have Poisson’s equation
1
2
∆e = −1onT
2
\D
T
2
(x, r)
and e =0on∂D
T
2
(x, r). Hence, with x fixed,
∆

G
x
+
1
2
e

=0 on T
2
\ D
T
2
(x, r).(2.3)
Applying the maximum principle for the harmonic function G
x
+
1
2
e on
T
2
\ D
T
2
(x, r), we see that for all y ∈ T
2
\ D
T
2
(x, r),
inf
z∈∂D
T
2
(x,r)
G
x
(z) ≤ G
x
(y)+
1
2
e(y) ≤ sup
z∈∂D
T
2
(x,r)
G
x
(z).(2.4)
Our lemma follows then, with
η(R)=
2π
log 2
sup
x∈
T
2
sup
y,z∈D
T
2
(x,R)
|F (x, z) − F (x, y)|
c =(1/π) + [(1/π) log diam(T
2
) + 4 sup
x,y∈
T
2
|F (x, y)|]/ log 4 < ∞ ,
except that we have proved (2.1) so far only for y/∈ D
T
2
(x, r). To com-
plete the proof, fix x

∈ T
2
with d(x, x

)=3ρ>0. For r<ρ, starting at
X
0
= y ∈ D
T
2
(x, r), the process X
t
hits ∂D
T
2
(x, r) before it hits ∂D
T
2
(x

,r).
Consequently, E
y
(τ
r
) ≤ c|log r| also for such y and r, establishing (2.1).
Turning to constructing G
x
(y), we use the representation T
2
=(−1/2, 1/2]
2
.
Let φ ∈ C
∞
(R) be such that φ = 1 in a small neighborhood of 0, and φ =0
outside a slightly larger neighborhood of 0. With r = |z| for z =(z
1
,z
2
), let
h(z)=−
1
2π
φ(r) log r
and note that by Green’s theorem

T
2
∆h(z) dz =1.(2.5)
Recall that for any function f which depends only on r = |z|,
∆f = f

+
1
r
f

,
and therefore, for r>0
∆h(z)=−
1
2π
(φ

(r) log r +
2 + log r
r
φ

(r)).
COVER TIMES FOR PLANAR BROWNIAN MOTION AND RANDOM WALKS
439
Because of the support properties of φ(r) we see that H(z)=∆h(z) − 1isa
C
∞
function on T
2
, and consequently has an expansion in Fourier series
H(z)=
∞

j,k=0
a
j,k
cos(2πjz
1
) cos(2πkz
2
)
with a
j,k
rapidly decreasing. Note that as a consequence of (2.5) we have
a
0,0
= 0. Set
F (z)=
∞

j,k=0
(j,k)=(0,0)
a
j,k
4π
2
(j
2
+ k
2
)
cos(2πjz
1
) cos(2πkz
2
).
The function F (z) is then a C
∞
function on T
2
and it satisfies ∆F = −H.
Hence, if we set g(z)=h(z)+F (z) we have ∆g(z) = 1 for |z| > 0 and
g(z)+
1
2π
log |z| has a continuous extension to all of T
2
. The Green’s function
for T
2
is then G
x
(y)=g((x − y)
T
2
).
Fixing x ∈ T
2
and constants 0 < 2r ≤ R<1/2 let
τ
(0)
= inf{t ≥ 0 |X
t
∈ ∂D
T
2
(x, R)},(2.6)
σ
(1)
= inf{t ≥ 0 |X
t+τ
(0)
∈ ∂D
T
2
(x, r)}(2.7)
and define inductively for j =1, 2,
τ
(j)
= inf{t ≥ σ
(j)
|X
t+
T
j−1
∈ ∂D
T
2
(x, R)},(2.8)
σ
(j+1)
= inf{t ≥ 0 |X
t+
T
j
∈ ∂D
T
2
(x, r)},(2.9)
where T
j
=

j
i=0
τ
(i)
for j =0, 1, 2, Thus, τ
(j)
is the length of the j-th
excursion E
j
from ∂D
T
2
(x, R) to itself via ∂D
T
2
(x, r), and σ
(j)
is the amount
of time it takes to hit ∂D
T
2
(x, r) during the j-th excursion E
j
.
The next lemma, which shows that excursion times are concentrated
around their mean, will be used to relate excursions to hitting times.
Lemma 2.2. With the above notation, for any N ≥ N
0
, δ
0
> 0 small
enough,0<δ<δ
0
,0< 2r ≤ R<R
1
(δ), and x, x
0
∈ T
2
,
P
x
0


N

j=0
τ
(j)
≤ (1 − δ)N
1
π
log(R/r)


≤ e
−Cδ
2
N
(2.10)
and
P
x
0


N

j=0
τ
(j)
≥ (1 + δ)N
1
π
log(R/r)


≤ e
−Cδ
2
N
.(2.11)
Moreover, C = C(R, r) > 0 depends only upon δ
0
as soon as R>r
1−δ
0
.
440 AMIR DEMBO, YUVAL PERES, JAY ROSEN, AND OFER ZEITOUNI
Proof of Lemma 2.2. Applying Kac’s moment formula for the first hitting
time τ
r
of the strong Markov process X
t
(see [17, equation (6)]), we see that
for any θ<1/τ
r
,
sup
y
E
y
(e
θτ
r
) ≤
1
1 − θτ
r

.(2.12)
Consequently, by (2.1) we have that for some λ>0,
sup
0<r≤r
0
sup
x,y
E
y
(e
λτ
r
/|log r|
) < ∞.(2.13)
By the strong Markov property of X
t
at τ
(0)
and at τ
(0)
+ σ
(1)
we then deduce
that
sup
0<2r≤R<r
0
sup
x,y
E
y
(e
λ
T
1
/|log r|
) < ∞.(2.14)
Fixing x ∈ T
2
and 0 < 2r ≤ R<1/2 let τ = τ
(1)
and v =
1
π
log(R/r).
Recall that {X
t
: t ≤ τ
R
} starting at X
0
= z for some z ∈ ∂D
T
2
(x, r), has the
same law as {B
t
: t ≤ τ
R
} starting at B
0
= i(z) ∈ ∂D(0,r). Consequently,
τ
R

R
:= sup
x
sup
z∈D
T
2
(x,R)
E
z
(τ
R
) ≤ E
0
(τ
R
)=
R
2
2
→
R→0
0 ,(2.15)
by the radial symmetry of the Brownian motion B
t
.
By the strong Markov property of X
t
at τ
(0)
+ σ
(1)
we thus have that
E
y
(τ
r
) ≤ E
y
(τ) ≤ E
y
(τ
r
)+τ
R

R
for all y ∈ ∂D
T
2
(x, R) .
Consequently, with η = δ/6, let R
1
(δ) ≤ r
0
be small enough so that (2.2) and
(2.15) imply
(1 − η)v ≤inf
x
inf
y∈∂D
T
2
(x,R)
E
y
(τ)(2.16)
≤sup
x
sup
y∈∂D
T
2
(x,R)
E
y
(τ) ≤ (1+2η)v,
whenever R ≤ R
1
. It follows from (2.14) and (2.16) that there exists a universal
constant c
4
< ∞ such that for ρ = c
4
|log r|
2
and all θ ≥ 0,
sup
x
sup
y∈∂D
T
2
(x,R)
E
y
(e
−θτ
)(2.17)
≤ 1 − θ inf
x
inf
y∈∂D
T
2
(x,R)
E
y
(τ)+
θ
2
2
sup
x
sup
y∈∂D
T
2
(x,R)
E
y
(τ
2
)
≤ 1 − θ(1 − η)v + ρθ
2
≤ exp(ρθ
2
− θ(1 − η)v).
COVER TIMES FOR PLANAR BROWNIAN MOTION AND RANDOM WALKS
441
Since τ
(0)
≥ 0, using Chebyshev’s inequality we bound the left-hand side of
(2.10) by
(2.18)
P
x
0

N

j=1
τ
(j)
≤ (1 − 6η)vN

≤e
θ(1−3η)vN
E
x
0

e
−θ

N
j=1
τ
(j)

≤e
−θvNδ/3

e
θ(1−η)v
sup
y∈∂D
T
2
(x,R)
E
y
(e
−θτ
)

N
,
where the last inequality follows by the strong Markov property of X
t
at {T
j
}.
Combining (2.17) and (2.18) for θ = δv/(6ρ), results in (2.10), where C =
v
2
/36ρ>0 is bounded below by δ
2
0
/(36c
4
π
2
)ifr
1−δ
0
<R.
To prove (2.11) we first note that for θ = λ/|log r| > 0 and λ>0asin
(2.14), it follows that
P
x
0

τ
(0)
≥
δ
3
vN

≤ e
−θv(δ/3)N
E
x
0
(e
λτ
(0)
/|log r|
) ≤ c
5
e
−c
6
δN
,
where c
5
< ∞ is a universal constant and c
6
= c
6
(r, R) > 0 does not depend
upon N, δ or x
0
and is bounded below by some c
7
(δ
0
) > 0 when r
1−δ
0
<R.
Thus, the proof of (2.11), in analogy to that of (2.10), comes down to bounding
P
x
0

N

j=1
τ
(j)
≥ (1+4η)vN

≤ e
−θδvN/3

e
−θ(1+2η)v
sup
y∈∂D
T
2
(x,R)
E
y
(e
θτ
)

N
.
(2.19)
By (2.14) and (2.16), there exists a universal constant c
8
< ∞ such that for
ρ = c
8
|log r|
2
and all 0 <θ<λ/(2|log r|),
sup
x
sup
y∈∂D
T
2
(x,R)
E
y
(e
θτ
) ≤1+θ(1+2η)v + sup
x
sup
y∈∂D
T
2
(x,R)
∞

n=2
θ
n
n!
E
y
(τ
n
)
≤1+θ(1+2η)v + ρθ
2
≤ exp(θ(1+2η)v + ρθ
2
);
the proof of (2.11) now follows as in the proof of (2.10).
Lemma 2.3. For any δ>0 there exist c<∞ and ε
0
> 0 so that for all
ε ≤ ε
0
and y ≥ 0
P
x
0

T (x, ε) ≥ y(log ε)
2

≤ cε
(1−δ)πy
(2.20)
for all x, x
0
∈ T
2
.
Proof of Lemma 2.3. We use the notation of the last lemma and its proof,
with R<R
1
(δ) and r = R/e chosen for convenience so that log(R/r) = 1. Let
442 AMIR DEMBO, YUVAL PERES, JAY ROSEN, AND OFER ZEITOUNI
n
ε
:= (1 − δ)πy(log ε)
2
. Then,
P
x
0

T (x, ε) ≥ y(log ε)
2

(2.21)
≤ P
x
0


T (x, ε) ≥
n
ε

j=0
τ
(j)


+ P
x
0


n
ε

j=0
τ
(j)
≥ y(log ε)
2


.
It follows from Lemma 2.2 that
P
x
0


n
ε

j=0
τ
(j)
≥ y(log ε)
2


≤ e
−C

y(log ε)
2
(2.22)
for some C

= C

(δ) > 0. On the other hand, the first probability in the
second line of (2.21) is bounded above by the probability of B
t
not hitting
i(D
T
2
(x, ε)) = D(0,ε) during n
ε
excursions, each starting at i(∂D
T
2
(x, r)) =
∂D(0,r) and ending at i(∂D
T
2
(x, R)) = ∂D(0,R), so that
P
x
0


T (x, ε) ≥
n
ε

j=0
τ
(j)


≤

1 −
1
log
R
ε

n
ε
≤ e
−(1−δ)πy|log ε|
(2.23)
and (2.20) follows.
We next show that
lim sup
ε→0
sup
x∈
T
2
T (x, ε)
(log ε)
2
≤
2
π
, a.s.(2.24)
from which the upper bound for (1.2) follows.
Set h(ε)=|log ε|
2
. Fix δ>0, and set ˜ε
n
= e
−n
so that
h(˜ε
n+1
) = (1 +
1
n
)
2
h(˜ε
n
).(2.25)
For ˜ε
n+1
≤ ε ≤ ˜ε
n
,
T (x, ˜ε
n+1
)
h(˜ε
n+1
)
=
h(˜ε
n
)
h(˜ε
n+1
)
T (x, ˜ε
n+1
)
h(˜ε
n
)
≥ (1 +
1
n
)
−2
T (x, ε)
h(ε)
.(2.26)
Fix x
0
∈ T
2
and let {x
j
: j =1, ,
¯
K
n
}, denote a maximal collection of points
in T
2
, such that inf
=j
d(x

,x
j
) ≥ δ˜ε
n
. Let a =(2+δ)/(1 − 10δ) and A
n
be
the set of 1 ≤ j ≤
¯
K
n
, such that
T (x
j
, (1 − δ)˜ε
n
) ≥ (1 − 2δ)ah(˜ε
n
)/π.
It follows by Lemma 2.3 that
P
x
0
(T (x, (1 − δ)˜ε
n
) ≥ (1 − 2δ)ah(˜ε
n
)/π) ≤ c ˜ε
(1−10δ)a
n
,
for some c = c(δ) < ∞, all sufficiently large n and any x ∈ T
2
. Thus, for all
sufficiently large n,anyj and a>0,
P
x
0
(j ∈A
n
) ≤ c ˜ε
(1−10δ)a
n
.(2.27)
COVER TIMES FOR PLANAR BROWNIAN MOTION AND RANDOM WALKS
443
This implies
∞

n=1
P
x
0
(|A
n
|≥1) ≤
∞

n=1
E
x
0
|A
n
|≤c

∞

n=1
˜ε
δ
n
< ∞.
By Borel-Cantelli, it follows that A
n
is empty a.s. for all n>n
0
(ω) and some
n
0
(ω) < ∞. By (2.26) we then have for some n
1
(δ, ω) < ∞ and all n>n
1
(ω)
sup
ε≤˜ε
n
1
sup
x∈
T
2
T (x, ε)
(log ε)
2
≤
a
π
,
and (2.24) follows by taking δ ↓ 0.
3. Lower bound for covering times
Fixing δ>0 and a<2, we prove in this section that
lim inf
ε→0
C
ε
(log ε)
2
≥ (1 − δ)
a
π
a.s.(3.1)
In view of (2.24), we then obtain Theorem 1.2.
We start by constructing an almost sure lower bound on C
ε
for a spe-
cific deterministic sequence ε
n,1
. To this end, fix ε
1
≤ R
1
(δ) as in Lemma
2.2 and the square S =[ε
1
, 2ε
1
]
2
. Let ε
k
= ε
1
(k!)
−3
and n
k
=3ak
2
log k.
For fixed n ≥ 3, let ε
n,k
= ρ
n
ε
n
(k!)
3
for ρ
n
= n
−25
and k =1, ,n. Ob-
serve that ε
n,1
= ρ
n
ε
n
, ε
n,n
= ρ
n
ε
1
, and ε
n,k
≤ ρ
n
ε
n+1−k
≤ ε
n+1−k
for all
1 ≤ k ≤ n. Recall the natural bijection i : D
T
2
(0, 1/2) → D(0, 1/2). For
any x ∈ S, let R
x
n
denote the time until X
t
completes n
n
excursions from
i
−1
(∂D(x, ε
n,n−1
)) to i
−1
(∂D(x, ε
n,n
)). (In the notation of Section 2, if we set
R = ε
n,n
and r = ε
n,n−1
, then R
x
n
=

n
n
j=0
τ
(j)
.) Note that i
−1
(∂D(x, ε
n,k
)) is
just ∂D
T
2
(i
−1
(x),ε
n,k
), but the former notation will allow easy generalization
to the case of general manifolds treated in Section 8.
For x ∈ S,2≤ k ≤ n let N
x
n,k
denote the number of excursions of X
t
from i
−1
(∂D(x, ε
n,k−1
)) to i
−1
(∂D(x, ε
n,k
)) until time R
x
n
. Thus, N
x
n,n
= n
n
=
3an
2
log n. A point x ∈ S is called n-successful if
N
x
n,2
=0,n
k
− k ≤ N
x
n,k
≤ n
k
+ k ∀k =3, ,n− 1 .(3.2)
In particular, if x is n-successful, then T (i
−1
(x),ε
n,1
) > R
x
n
.
For n ≥ 3 we partition S into M
n
= ε
2
1
/(2ε
n
)
2
=(1/4)

n
l=1
l
6
nonoverlap-
ping squares of edge length 2ε
n
=2ε
1
/(n!)
3
, with x
n,j
, j =1, ,M
n
denoting
the centers of these squares. Let Y (n, j), j =1, ,M
n
, be the sequence of
random variables defined by
Y (n, j)=1 ifx
n,j
is n-successful
and Y (n, j) = 0 otherwise. Set ¯q
n
= P(Y (n, j)=1)=E(Y (n, j)), noting that
this probability is independent of j (and of the value of ρ
n
).
444 AMIR DEMBO, YUVAL PERES, JAY ROSEN, AND OFER ZEITOUNI
The next lemma, which is a direct consequence of Lemmas 6.2 and 7.1,
provides bounds on the first and second moments of Y (n, j), that are used
in order to show the existence of at least one n-successful point x
n,j
for large
enough n.
Lemma 3.1. There exists δ
n
→ 0 such that for all n ≥ 1,
¯q
n
= P (x is n-successful) ≥ ε
a+δ
n
n
.(3.3)
For some C
0
< ∞ and all n, if |x
n,i
− x
n,j
|≥2ε
n,n
, then
E(Y (n, i)Y (n, j)) ≤ (1 + C
0
n
−1
log n)¯q
2
n
.(3.4)
Further, for any γ>0 there exists C = C(γ) < ∞ so that for all n and
l = l(i, j) = max{k ≤ n : |x
n,i
− x
n,j
|≥2ε
n,k
}∨1,
E(Y (n, i)Y (n, j)) ≤ ¯q
2
n
C
n−l
n
39

ε
n,n
ε
n,l+1

a+γ
.(3.5)
Fix γ>0 such that 2 − a − γ>0. By (3.3) for all n large enough,
E


M
n

j=1
Y (n, j)


= M
n
¯q
n
≥ ε
−(2−a−γ)
n
.(3.6)
In the sequel, we let C
m
denote generic finite constants that are independent
of n, l, i and j. Recall that there are at most C
1
ε
2
n,l+1
ε
−2
n
points x
n,j
, j = i,
in D(x
n,i
, 2ε
n,l+1
). Further, our choice of ρ
n
guarantees that (ε
n,n
/ε
n
)
2
≤
C
2
M
n
n
−50
. Hence, it follows from (3.5) that for n − 1 ≥ l ≥ 1,
V
l
:= (M
n
¯q
n
)
−2
M
n

i=j=1
l(i,j)=l
E

Y (n, i)Y (n, j)

(3.7)
≤ C
1
M
−1
n
ε
2
n,l+1
ε
−2
n
C
n−l
n
39

ε
n,l+1
ε
n,n

−a−γ
≤ C
1
C
2
n
−3
C
n−l

ε
n,l+1
ε
n,n

2−a−γ
,
and since (ε
n,l+1
/ε
n,n
) ≤ (ε
n−l
/ε
1
) for all 1 ≤ l ≤ n − 1, we deduce that
n−1

l=1
V
l
≤ C
3
n
−3
∞

j=1
C
j
ε
2−a−γ
j
≤ C
4
n
−3
.(3.8)
We have, by Chebyshev’s inequality (see [6, Theorem 4.3.1]) and (3.4), that
P(
M
n

j=1
Y (n, j)=0)≤(M
n
¯q
n
)
−2
E


M
n

i=1
Y (n, i)

2

− 1
≤(M
n
¯q
n
)
−1
+ C
0
n
−1
log n +
n−1

l=1
V
l
.
COVER TIMES FOR PLANAR BROWNIAN MOTION AND RANDOM WALKS
445
Combining this with (3.6) and (3.8), we see that
P(
M
n

j=1
Y (n, j)=0)≤ C
5
n
−1
log n.(3.9)
The next lemma relates the notion of n-successful to the ε
n,1
-hitting time.
Lemma 3.2. For each n let V
n
be a finite subset of S with cardinality
bounded by e
o(n
2
)
. There exists m(ω) < ∞ a.s. such that for all n ≥ m and all
x ∈V
n
,ifx is n-successful then
T (i
−1
(x),ε
n,1
) ≥ (log ε
n,1
)
2

a
π
−
2
√
log n

.(3.10)
Proof of Lemma 3.2. Recall that if x is n-successful then T (i
−1
(x),ε
n,1
) >

n
n
j=0
τ
(j)
. Hence, using (2.10) with N = n
n
=3an
2
log n, δ
n
= π/(a
√
log n),
R = ε
n,n
, and r = ε
n,n−1
so that log(R/r)=3logn and R>r
0.8
, we see that
for some C>0 that is independent of n,
P
x
:= P
x
0

T (i
−1
(x),ε
n,1
) ≤ (
a
π
−
2
√
log n
)(log ε
n,1
)
2
,xis n-successful

≤ P
x
0


N

j=0
τ
(j)
≤ (
a
π
−
1
√
log n
)(3n log n)
2


≤ P
x
0


1
N
N

j=0
τ
(j)
≤ (1 − δ
n
)
log(R/r)
π


≤ e
−Cn
2
.
Consequently, the sum of P
x
over all x ∈V
n
and then over all n is finite, and
the Borel-Cantelli lemma then completes the proof of Lemma 3.2.
Taking V
n
= {x
n,k
: k =1, ,M
n
}, and the subsequence n(j)=
j(log j)
3
, it follows from (3.9), (3.10) and the Borel-Cantelli lemma that a.s.
C
ε
n(j),1
≥ (log ε
n(j),1
)
2

a
π
−
2

log n(j)

,(3.11)
for all j large enough. Since ε →C
ε
is monotone nondecreasing, it follows that
for any ε
n(j+1),1
≤ ε ≤ ε
n(j),1
C
ε
(log ε)
2
≥
C
ε
n(j+1),1
(log ε
n(j),1
)
2
.
Observing that (log ε
n(j+1),1
)/(log ε
n(j),1
) → 1asj →∞, we thus see that
(3.1) is an immediate consequence of (3.11).