ALMOST SURE FUNCTIONAL CENTRAL LIMIT THEOREM FOR
NON-NESTLING RANDOM WALK IN RANDOM ENVIRONMENT
FIRAS RASSOUL-AGHA1 AND TIMO SEPPÄLÄINEN2
Abstract. We consider a non-nestling random walk in a product random environ-
ment. We assume an exponential moment for the step of the walk, uniformly in the
environment. We prove an invariance principle (functional central limit theorem)
under almost every environment for the centered and diffusively scaled walk. The
main point behind the invariance principle is that the quenched mean of the walk
behaves subdiffusively.
1. Introduction and main result
We prove a quenched functional central limit theorem for non-nestling random walk
in random environment (RWRE) on the d-dimensional integer lattice Zd in dimensions
d ≥ 2. Here is a general description of the model, fairly standard since quite a while.
An environment ω is a configuration of transition probability vectors ω = (ωx)x∈Zd ∈
Ω = PZd , where P = {(pz)z∈Zd : pz ≥ 0,
z pz = 1} is the simplex of all probability
vectors on Zd. Vector ωx = (ωx,z)z∈Zd gives the transition probabilities out of state
x, denoted by πx,y(ω) = ωx,y−x. To run the random walk, fix an environment ω and
an initial state z ∈ Zd. The random walk X0,∞ = (Xn)n≥0 in environment ω started
at z is then the canonical Markov chain with state space Zd whose path measure P ωz
satisfies
P ωz (X0 = z) = 1 and P
z (Xn+1 = y|Xn = x) = πx,y(ω).
On the space Ω we put its product σ-fieldS, natural shifts πx,y(Tzω) = πx+z,y+z(ω),
and a {Tz}-invariant probability measure P that makes the system (Ω,S, (Tz)z∈Zd,P)
ergodic. In this paper P is an i.i.d. product measure on PZd . In other words, the
vectors (ωx)x∈Zd are i.i.d. across the sites x under P.
Date: November 21, 2018.
2000 Mathematics Subject Classification. 60K37, 60F05, 60F17, 82D30.
Key words and phrases. Random walk, non-nestling, random environment, central limit theorem,
invariance principle, point of view of the particle, environment process, Green function.
1Department of Mathematics, University of Utah.
1Supported in part by NSF Grant DMS-0505030.
2Mathematics Department, University of Wisconsin-Madison.
2Supported in part by NSF Grant DMS-0402231.
http://arxiv.org/abs/0704.1022v2
2 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Statements, probabilities and expectations under a fixed environment, such as
the distribution P ωz above, are called quenched. When also the environment is av-
eraged out, the notions are called averaged, or also annealed. In particular, the
averaged distribution Pz(dx0,∞) of the walk is the marginal of the joint distribution
Pz(dx0,∞, dω) = P
z (dx0,∞)P(dω) on paths and environments.
Several excellent expositions on RWRE exist, and we refer the reader to the lectures
[3], [15] and [18]. We turn to the specialized assumptions imposed on the model in
this paper.
The main assumption is non-nestling (N) which guarantees a drift uniformly over
the environments. The terminology was introduced by Zerner [19].
Hypothesis (N). There exists a vector û ∈ Zd \ {0} and a constant δ > 0 such that
z · û π0,z(ω) ≥ δ
There is no harm in assuming û ∈ Zd, and this is convenient. We utilize two
auxiliary assumptions: an exponential moment bound (M) on the steps of the walk,
and some regularity (R) on the environments.
Hypothesis (M). There exist positive constants M and s0 such that
es0|z|π0,z(ω) ≤ es0M
Hypothesis (R). There exists a constant κ > 0 such that
z: z·û=1
π0,z(ω) ≥ κ
= 1. (1.1)
Let J = {z : Eπ0,z > 0} be the set of admissible steps under P. Then
P{∀z : π0,0 + π0,z < 1} > 0 and J 6⊂ Ru for all u ∈ Rd. (1.2)
Assumption (1.1) above is stronger than needed. In the proofs it is actually used in
the form (7.5) [Section 7] that permits backtracking before hitting the level x · û = 1.
At the expense of additional technicalities in Section 7 quenched assumption (1.1)
can be replaced by an averaged requirement.
Assumption (1.2) is used in Lemma 7.10. It is necessary for the quenched CLT as
was discovered already in the simpler forbidden direction case we studied in [10] and
[11]. Note that assumption (1.2) rules out the case d = 1. However, the issue is not
whether the walk is genuinely d-dimensional, but whether the walk can explore its
environment thoroughly enough to suppress the fluctuations of the quenched mean.
Most work on RWRE takes uniform ellipticity and nearest-neighbor jumps as standing
assumptions, which of course imply Hypotheses (M) and (R).
QUENCHED FUNCTIONAL CLT FOR RWRE 3
These assumptions are more than strong enough to imply a law of large numbers:
there exists a velocity v 6= 0 such that
n−1Xn = v
= 1. (1.3)
Representations for v are given in (2.5) and Lemma 5.1. Define the (approximately)
centered and diffusively scaled process
Bn(t) =
X[nt] − [nt]v√
. (1.4)
As usual [x] = max{n ∈ Z : n ≤ x} is the integer part of a real x. Let DRd[0,∞) be
the standard Skorohod space of Rd-valued cadlag paths (see [6] for the basics). Let
Qωn = P
0 (Bn ∈ · ) denote the quenched distribution of the process Bn on DRd[0,∞).
The results of this paper concern the limit of the process Bn as n → ∞. As
expected, the limit process is a Brownian motion with correlated coordinates. For a
symmetric, non-negative definite d × d matrix D, a Brownian motion with diffusion
matrix D is the Rd-valued process {B(t) : t ≥ 0} with continuous paths, independent
increments, and such that for s < t the d-vector B(t)−B(s) has Gaussian distribution
with mean zero and covariance matrix (t − s)D. The matrix D is degenerate in
direction u ∈ Rd if utDu = 0. Equivalently, u · B(t) = 0 almost surely.
Here is the main result.
Theorem 1.1. Let d ≥ 2 and consider a random walk in an i.i.d. product random
environment that satisfies non-nestling (N), the exponential moment hypothesis (M),
and the regularity in (R). Then for P-almost every ω distributions Qωn converge weakly
on DRd [0,∞) to the distribution of a Brownian motion with a diffusion matrix D
that is independent of ω. utDu = 0 iff u is orthogonal to the span of {x − y :
E(π0x)E(π0y) > 0}.
Eqn (2.6) gives the expression for the diffusion matrix D, familiar for example from
[14]. Before turning to the proofs we discuss briefly the current situation in this area
of probability and the place of this work in this context.
Several different approaches can be identified in recent work on quenched central
limit theorems for multidimensional RWRE. (i) Small perturbations of classical ran-
dom walk have been studied by many authors. The most significant results include the
early work of Bricmont and Kupiainen [4] and more recently Sznitman and Zeitouni
[16] for small perturbations of Brownian motion in dimension d ≥ 3. (ii) An aver-
aged CLT can be turned into a quenched CLT by bounding certain variances through
the control of intersections of two independent paths. This idea was introduced by
Bolthausen and Sznitman in [2] and more recently applied by Berger and Zeitouni
in [1]. Both utilize high dimension to handle the intersections. (iii) Our approach
is based on the subdiffusivity of the quenched mean of the walk. That is, we show
that the variance of Eω0 (Xn) is of order n
2α for some α < 1/2. We also achieve this
through intersection bounds. Instead of high dimension we assume strong enough
4 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
drift. We introduced this line of reasoning in [9] and later applied it to the case of
walks with a forbidden direction in [11]. The significant advance taken in the present
paper over [9] and [11] is the elimination of restrictions on the admissible steps of
the walk. Theorem 2.1 below summarizes the general principle for application in this
paper.
As the reader will see, the arguments in this paper are based on quenched expo-
nential bounds that flow from Hypotheses (N), (M) and (R). It is common in this
field to look for an invariant measure P∞ for the environment process that is mutu-
ally absolutely continuous with the original P, at least on the part of the space Ω
to which the drift points. In this paper we do things a little differently: instead of
the absolute continuity, we use bounds on the variation distance between P∞ and P.
This distance will decay exponentially in the direction û.
In the case of nearest-neighbor, uniformly elliptic non-nestling walks in dimension
d ≥ 4 the quenched CLT has been proved earlier: first by Bolthausen and Sznitman
[2] under a small noise assumption, and recently by Berger and Zeitouni [1] without
the small noise assumption. Berger and Zeitouni [1] go beyond non-nestling to more
general ballistic walks. The method in these two papers utilizes high dimension
crucially. Whether their argument can work in d = 3 is not presently clear. The
approach of the present paper should work for more general ballistic walks in all
dimensions d ≥ 2, as the main technical step that reduces the variance estimate to
an intersection estimate is generalized (Section 6 in the present paper).
We turn to the proofs. The next section collects some preliminary material and
finishes with an outline of the rest of the paper.
2. Preliminaries for the proof.
As mentioned, we can assume that û ∈ Zd. This is convenient because then the
lattice Zd decomposes into levels identified by the integer value x · û.
Let us summarize notation for the reader’s convenience. Constants whose exact
values are not important and can change from line to line are often denoted by C
and s. The set of nonnegative integers is N = {0, 1, 2, . . . }. Vectors and sequences
are abbreviated xm,n = (xm, xm+1, . . . , xn) and xm,∞ = (xm, xm+1, xm+2, . . . ). Similar
notation is used for finite and infinite random paths: Xm,n = (Xm, Xm+1, . . . , Xn)
and Xm,∞ = (Xm, Xm+1, Xm+2, . . . ). X[0,n] = {Xk : 0 ≤ k ≤ n} denotes the set of
sites visited by the walk. Dt is the transpose of a vector or matrix D. An element
of Rd is regarded as a d× 1 column vector. The left shift on the path space (Zd)N is
(θkx0,∞)n = xn+k.
E, E0, and E
0 denote expectations under, respectively, P, P0, and P
0 . P∞ will
denote an invariant measure on Ω, with expectation E∞. We abbreviate P
0 (·) =
0 (·) and E∞0 (·) = E∞Eω0 (·) to indicate that the environment of a quenched
expectation is averaged under P∞. A family of σ-algebras on Ω that in a sense look
towards the future is defined by Sℓ = σ{ωx : x · û ≥ ℓ}.
QUENCHED FUNCTIONAL CLT FOR RWRE 5
Define the drift
D(ω) = Eω0 (X1) =
zπ0z(ω).
The environment process is the Markov chain on Ω with transition kernel
Π(ω,A) = P ω0 (TX1ω ∈ A).
The proof of the quenched CLT Theorem 1.1 utilizes crucially the environment
process and its invariant distribution. A preliminary part of the proof is summarized
in the next theorem quoted from [9]. This Theorem 2.1 was proved by applying
the arguments of Maxwell and Woodroofe [8] and Derriennic and Lin [5] to the
environment process.
Theorem 2.1. [9] Let d ≥ 1. Suppose the probability measure P∞ on (Ω,S) is
invariant and ergodic for the Markov transition Π. Assume that
z |z|2E∞(π0z) <∞
and that there exists an α < 1/2 such that as n→ ∞
|Eω0 (Xn)− nE∞(D)|
= Ŏ (n2α). (2.1)
Then as n → ∞ the following weak limit happens for P∞-a.e. ω: distributions Qωn
converge weakly on the space DRd[0,∞) to the distribution of a Brownian motion with
a symmetric, non-negative definite diffusion matrix D that is independent of ω.
Another central tool for the development that follows is provided by the Sznitman-
Zerner regeneration times [17] that we now define. For ℓ ≥ 0 let λℓ be the first time
the walk reaches level ℓ relative to the initial level:
λℓ = min{n ≥ 0 : Xn · û−X0 · û ≥ ℓ}.
Define β to be the first backtracking time:
β = inf{n ≥ 0 : Xn · û < X0 · û}.
Let Mn be the maximum level, relative to the starting level, reached by time n:
Mn = max{Xk · û−X0 · û : 0 ≤ k ≤ n}.
For a > 0, and when β <∞, consider the first time by which the walker reaches level
Mβ + a:
λMβ+a = inf{n ≥ β : Xn · û−X0 · û ≥Mβ + a}.
Let S0 = λa and, as long as β ◦ θSk−1 < ∞, define Sk = Sk−1 + λMβ+a ◦ θSk−1 for
k ≥ 1. Finally, let the first regeneration time be
Sℓ1I{β ◦ θSk <∞ for 0 ≤ k < ℓ and β ◦ θSℓ = ∞}. (2.2)
Non-nestling guarantees that τ
1 is finite, and in fact gives moment bounds uniformly
in ω as we see in Lemma 3.1 below. Consequently we can iterate to define τ
0 = 0,
and for k ≥ 1
k = τ
k−1 + τ
1 ◦ θτ
k−1 . (2.3)
6 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
When the value of a is not important we simplify the notation to τk = τ
k . Sznit-
man and Zerner [17] proved that the regeneration slabs
τk+1 − τk, (Xτk+n −Xτk)0≤n≤τk+1−τk ,
{ωXτk+z : 0 ≤ z · û < (Xτk+1 −Xτk) · û}
) (2.4)
are i.i.d. for k ≥ 1, each distributed as
τ1, (Xn)0≤n≤τ1 , {ωz : 0 ≤ z·û < Xτ1 ·û}
under
P0( · | β = ∞). Strictly speaking, uniform ellipticity and nearest-neighbor jumps were
standing assumptions in [17], but these assumptions are not needed for the proof of
the i.i.d. structure.
From the renewal structure and moment estimates a law of large numbers (1.3) and
an averaged functional central limit theorem follow, along the lines of Theorem 2.3
in [17] and Theorem 4.1 in [14]. These references treat walks that satisfy Kalikow’s
condition, considerably more general than the non-nestling walks we study. The
limiting velocity for the law of large numbers is
E0(Xτ1 |β = ∞)
E0(τ1|β = ∞)
. (2.5)
The averaged CLT states that the distributions P0{Bn ∈ · } converge to the distri-
bution of a Brownian motion with diffusion matrix
(Xτ1 − τ1v)(Xτ1 − τ1v)t|β = ∞
E0[τ1|β = ∞]
. (2.6)
Once we know that the P-a.s. quenched CLT holds with a constant diffusion matrix,
this diffusion matrix must be the same D as for the averaged CLT. We give here the
argument for the degeneracy statement of Theorem 1.1.
Lemma 2.1. Define D by (2.6) and let u ∈ Rd. Then utDu = 0 iff u is orthogonal
to the span of {x− y : E(π0x)E(π0y) > 0}.
Proof. The argument is a minor embellishment of that given for a similar degeneracy
statement on p. 123–124 of [10] for the forbidden-direction case where π0,z is supported
by z · û ≥ 0. We spell out enough of the argument to show how to adapt that proof
to the present case.
Again, the intermediate step is to show that utDu = 0 iff u is orthogonal to the
span of {x− v : E(π0x) > 0}. The argument from orthogonality to utDu = 0 goes as
in [10, p. 124].
Suppose utDu = 0 which is the same as
P0(Xτ1 · u = τ1v · u | β = ∞) = 1.
Suppose z is such that Eπ0,z > 0 and z · û < 0. By non-nestling there must exist w
such that Eπ0,zπ0,w > 0 and w · û > 0. Pick m > 0 so that (z + mw) · û > 0 but
QUENCHED FUNCTIONAL CLT FOR RWRE 7
(z + (m− 1)w) · û ≤ 0. Take a = 1 in the definition (2.2) of regeneration. Then
P0[Xτ1 = z + 2mw, τ1 = 2m+ 1 | β = ∞]
[ ( m−1∏
πiw,(i+1)w
πmw,z+mw
( m−1∏
πz+(m+j)w,z+(m+j+1)w
P ωz+2mw(β = ∞)
Consequently
(z + 2mw) · u = (1 + 2m)v · u. (2.7)
In this manner, by replacing σ1 with τ1 and by adding in the no-backtracking
probabilities, the arguments in [10, p. 123] can be repeated to show that if Eπ0x > 0
then x · u = v · u for x such that x · û ≥ 0. In particular the very first step on p. 123
of [10] gives w · u = v · u. This combines with (2.7) above to give z · u = v · u. Now
simply follow the proof in [10, p. 123–124] to its conclusion. �
Here is an outline of the proof of Theorem 1.1. It all goes via Theorem 2.1.
(i) After some basic estimates in Section 3, we prove in Section 4 the existence of the
ergodic equilibrium P∞ required for Theorem 2.1. P∞ is not convenient to work with
so we still need to do computations with P. For this purpose Section 4 proves that in
the direction û the measures P∞ and P come exponentially close in variation distance
and that the environment process satisfies a P0-a.s. ergodic theorem. In Section 5
we show that P∞ and P are interchangeable both in the hypotheses that need to be
checked and in the conclusions obtained. In particular, the P∞-a.s. quenched CLT
coming from Theorem 2.1 holds also P-a.s. Then we know that the diffusion matrix
D is the one in (2.6).
The bulk of the work goes towards verifying condition (2.1), but under P instead
of P∞. There are two main stages to this argument.
(ii) By a decomposition into martingale increments the proof of (2.1) reduces to
bounding the number of common points of two independent walks in a common
environment (Section 6).
(iii) The intersections are controlled by introducing levels at which both walks
regenerate. These common regeneration levels are reached fast enough and the pro-
gression from one common regeneration level to the next is a Markov chain. When
this Markov chain drifts away from the origin it can be approximated well enough by
a symmetric random walk. This approximation enables us to control the growth of
the Green function of the Markov chain, and thereby the number of common points.
This is in Section 7 and in an Appendix devoted to the Green function bound.
3. Basic estimates for non-nestling RWRE
This section contains estimates that follow from Hypotheses (N) and (M), all col-
lected in the following lemma. These will be used repeatedly. In addition to the
8 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
stopping times already defined, let
Hz = min{n ≥ 1 : Xn = z}
be the first hitting time of site z.
Lemma 3.1. If P satisfies Hypotheses (N) and (M), then there exist positive constants
η, γ, κ, (Cp)p≥1, and s1 ≤ s0, possibly depending on M , s0, and δ, such that for all
x ∈ Zd, n ≥ 0, s ∈ [0, s1], p ≥ 1, ℓ ≥ 1, for z such that z · û ≥ 0, a ≥ 1, and for
P-a.e. ω,
Eωx (e
−sXn·û) ≤ e−sx·û(1− sδ/2)n, (3.1)
Eωx (e
s|Xn−x|) ≤ esMn, (3.2)
P ωx (X1 · û ≥ x · û+ γ) ≥ κ, (3.3)
Eωx (λ
ℓ) ≤ Cpℓp, (3.4)
Eωx (|Xλℓ − x|p) ≤ Cpℓp, (3.5)
Eω0 [(MHz − z · û)p1I{Hz < n}] ≤ CpℓpP ω0 (Hz < n) + Cps−pe−sℓ/2, (3.6)
P ωx (β = ∞) ≥ η, (3.7)
Eωx (|τ
1 |p) ≤ Cp ap, (3.8)
Eωx (|Xτ (a)1 +n −Xn|
p) ≤ Cq aq, for all q > p. (3.9)
The particular point in (3.8)–(3.9) is to make the dependence on a explicit. Note
that (3.7)–(3.8) give
E0(τj − τj−1)p <∞ (3.10)
for all j ≥ 1. In Section 4 we construct an ergodic invariant measure P∞ for the
environment chain in a way that preserves the conclusions of this lemma under P∞.
Proof. Replacing x by 0 and ω by Txω allows us to assume that x = 0. Then for all
s ∈ [0, s0/2]
∣∣Eω0 (e−sX1·û)− 1 + sEω0 (X1 · û)
∣∣ ≤ |û|2Eω0 (|X1|2es0|X1|/2)
≤ (2|û|/s0)2es0Ms2 = cs2,
where we used moment assumption (M). Then by the non-nestling assumption (N)
Eω0 (e
−sXn·û|Xn−1) = e−sXn−1·ûEωXn−1(e
−s(X1−X0)·û) ≤ e−sXn−1·û(1− sδ + cs2).
Taking now the quenched expectation of both sides and iterating the procedure proves
(3.1), provided s1 is small enough. To prove (3.2) one can instead show that
Eω0 (e
k=1 |Xk−Xk−1|) ≤ esnM .
This can be proved by induction as for (3.1), using only Hypothesis (M) and Hölder’s
inequality (to switch to s0).
QUENCHED FUNCTIONAL CLT FOR RWRE 9
Concerning (3.3), we have
P ω0 (X1 · û ≥ γ) ≥ (1− eγs(1− sδ/2))−→
sδ/2.
So taking γ small enough and κ slightly smaller than sδ/2 does the job.
Notice next that P ω0 (λ1 <∞) = 1 due to (3.1). P-a.s. Then
Eω0 (λ
(n+ 1)pP ω0 (λ1 > n) ≤
(n+ 1)pP ω0 (Xn · û ≤ 1)
(n + 1)pEω0 (e
−sXn·û).
The last expression is bounded if s is small enough. Therefore,
Eω0 (λ
ℓ) ≤ Eω0
[ ∣∣∣
[ℓ]+1∑
(λi − λi−1)
≤ ([ℓ] + 1)p−1
[ℓ]+1∑
EωXλi−1
≤ Cpℓp.
Bound (3.5) is proved similarly: by the Cauchy-Schwarz inequality, Hypothesis (M)
and (3.1),
Eω0 (|Xλ1 |p) ≤
Eω0 (|Xn|2p)1/2P ω0 (Xn−1 · û < 1)1/2
[2p]! s
−[2p]
s0Mes
)1/2 ∑
(1− sδ/2)(n−1)/2np ≤ Cp.
To prove (3.6), write
Eω0 [(MHz − z · û)p1I{Hz < n}]
ℓp−1P ω0 (MHz − z · û ≥ ℓ,Hz < n) + Cpℓ
0 (Hz < n)
ℓp−1Eω0 [P
Xλz·û+ℓ
(Xk · û−X0 · û ≤ −ℓ)] + Cpℓp0P ω0 (Hz < n)
ℓp−1e−sℓ + Cpℓ
0 (Hz < n) ≤ Cps−pe−sℓ0/2 + Cpℓ
0 (Hz < n).
To prove (3.7), note that Chebyshev inequality and (3.1) give, for s > 0 small
enough, ℓ ≥ 1, and P-a.e. ω
P ω0 (λ−ℓ+1 <∞) ≤
P ω0 (Xn · û ≤ −(ℓ− 1)) ≤ 2(sδ)−1e−s(ℓ−1).
On the other hand, for an integer ℓ ≥ 2 we have
P ω0 (λℓ < β) ≥
P ω0 (λℓ−1 < β,Xλℓ−1 = x)P
x (λ−ℓ+1 = ∞).
10 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Therefore, taking ℓ to infinity one has, for ℓ0 large enough,
P ω0 (β = ∞) ≥ P ω0 (λℓ0 < β)
(1− 2(sδ)−1e−sℓ).
Markov property and (3.3) give P ω0 (λℓ0 < β) ≥ κℓ0/γ+1 > 0 and (3.7) is proved.
Now we will bound the quenched expectation of λ
1I{β < ∞} uniformly in ω.
To this end, for p1 > p and q1 = p1(p1 − p)−1, we have by (3.7)
Eω0 (λ
1I{β <∞}) ≤
Eω0 (λ
1I{β = n})
Eω0 (λ
)p/p1(
P ω0 (β = n)
)1/q1
By (3.4) one has, for p2 > p1 > p and q2 = p2(p2 − p1)−1,
Eω0 (λ
Eω0 (λ
m+1+a)
)p1/p2(
P ω0 ([Mn] = m)
)1/q2
(m+ 1 + a)p1
P ω0 (Xi · û ≥ m)
)1/q2
where Cp really depends on p1 and p2, but these are chosen arbitrarily, as long as
they satisfy p2 > p1 > p. Using (3.2) one has
P ω0 (Xi · û ≥ m) ≤
1 if m < 2M |û|i,
e−smeM |û|si if m ≥ 2M |û|i.
Hence,
Eω0 (λ
) ≤ Cp
(m+ 1 + a)p1(n1I{m < 2Mn|û|}+ e−sm/2)1/q2
≤ Cpn(n+ a)p1n1/q2 + Cp
(m+ 1)p1e−sm/2q2 + Cpa
e−sm/2q2
≤ Cpn1+1/q2(n+ a)p1 .
Since {β = n} ⊂ {Xn · û ≤ 0}, one can use (3.1) to conclude that
Eω0 (λ
1I{β <∞}) ≤ Cp
np/p1+p/(p1q2)(n+ a)p(1− sδ/2)n/q1 ≤ Cpap.
QUENCHED FUNCTIONAL CLT FOR RWRE 11
In the last inequality we have used the fact that a ≥ 1. Using, (3.7), the definition
of the times Sk, and the Markov property, one has
Eω0 [S
ℓ 1I{β ◦ θSk <∞ for 0 ≤ k < ℓ and β ◦ θSℓ = ∞}]
≤ (ℓ+ 1)p−1
Eω0 [λ
a1I{β ◦ θSk <∞ for 0 ≤ k < ℓ}]
Eω0 [λ
◦ θSj1I{β ◦ θSk <∞ for 0 ≤ k < ℓ}]
≤ (ℓ+ 1)p−1
p(1− η)ℓ +
(1− η)jCpap(1− η)ℓ−j−1
≤ Cp(ℓ + 1)p(1− η)ℓ−1ap.
Bound (3.8) follows then from (2.2). To prove (3.9) let q > p and write
Eω0 (|Xτ (a)1 +n −Xn|
Eω0 (|Xk+1+n −Xk+n|p|τ
1 |p−11I{k < τ
k−1−q+pEω0 (|Xk+1+n −Xk+n|p|τ
1 |q)
k−1−q+pEω0 (|τ
1 |2q)1/2 ≤ Cq aq,
where we have used Hypothesis (M) along with the Cauchy-Schwarz inequality in
the second to last inequality and (3.8) in the last. This completes the proof of the
lemma. �
4. Invariant measure and ergodicity
For ℓ ∈ Z define the σ-algebras Sℓ = σ{ωx : x · û ≥ ℓ} on Ω. Denote the restriction
of the measure P to the σ-algebra Sℓ by P|Sℓ . In this section we prove the next
two theorems. The variation distance of two probability measures is dVar(µ, ν) =
sup{µ(A)− ν(A)} with the supremum taken over measurable sets A.
Theorem 4.1. Assume P is product non-nestling (N) and satisfies the moment hy-
pothesis (M). Then there exists a probability measure P∞ on Ω with these properties.
(a) P∞ is invariant and ergodic for the Markov transition kernel Π.
(b) There exist constants 0 < c, C <∞ such that for all ℓ ≥ 0
dVar(P∞|Sℓ ,P|Sℓ) ≤ Ce
−cℓ. (4.1)
(c) Hypotheses (N) and (M) and the conclusions of Lemma 3.1 hold P∞-almost
surely.
Along the way we also establish this ergodic theorem under the original environ-
ment measure. E∞ denotes expectation under P∞.
12 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Theorem 4.2. Assumptions as in Theorem 4.1 above. Let Ψ be a bounded S−a-
measurable function on Ω, for some 0 < a <∞. Then
Ψ(TXjω) = E∞Ψ P0-almost surely. (4.2)
The ergodic theorem tells us that there is a unique invariant P∞ in a natural
relationship to P, and that P∞ ≪ P on each σ-algebra S−a. Limit (4.2) cannot
hold for all bounded measurable Ψ on Ω because this would imply the absolute
continuity P∞ ≪ P on the entire space Ω. A counterexample that satisfies (N)
and (M) but where the quenched walk is degenerate was given by Bolthausen and
Sznitman [2, Proposition 1.5]. Whether regularity assumption (R) or ellipticity will
make a difference here is not presently clear. For the simpler case of space-time walks
(see description of model in [9]) with nondegenerate P ω0 absolute continuity P∞ ≪ P
does hold on the entire space. Theorem 3.1 in [2] proves this for nearest-neighbor
jumps with some weak ellipticity. The general case is no harder.
Proof of Theorems 4.1 and 4.2. Let Pn(A) = P0(TXnω ∈ A). A computation shows
fn(ω) =
(ω) =
P ωx (Xn = 0).
By hypotheses (M) and (N) we can replace the state space Ω = PZd with the
smaller space Ω0 = PZ
0 where
P0 = {(pz) ∈ P :
es0|z|pz ≤ es0M and
z · û pz ≥ δ }. (4.3)
Fatou’s lemma shows that the exponential bound is preserved by pointwise conver-
gence in P0. Then the exponential bound shows that the non-nestling property is also
preserved. Thus P0 is compact, and then Ω0 is compact under the product topology.
Compactness gives a subsequence {nj} along which the averages nj−1
m=1 Pm
converge weakly to a probability measure P∞ on Ω0. Hypotheses (N) and (M) transfer
to P∞ by virtue of having been included in the state space Ω0. Thus the proof of
Lemma 3.1 can be repeated for P∞-a.e. ω. We have verified part (c) of Theorem 4.1.
Next we check that P∞ is invariant under Π. Take a bounded, continuous local
function F on Ω0 that depends only on environments (ωx : |x| ≤ K). For ω, ω̄ ∈ Ω0
∣∣ΠF (ω)− ΠF (ω̄)
∣∣Eω0 [F (TX1ω)]−Eω̄0 [F (TX1ω̄)]
|z|≤C
∣∣∣π0,z(ω)F (Tzω)− π0,z(ω̄)F (Tzω̄)
∣∣∣+ ‖F‖∞
|z|>C
π0,z(ω) + π0,z(ω̄)
From this we see that ΠF is continuous. For let ω̄ → ω in Ω0 so that ω̄x,z → ωx,z at
each coordinate. Since the last term above is controlled by the uniform exponential
QUENCHED FUNCTIONAL CLT FOR RWRE 13
tail bound imposed on P0, continuity of ΠF follows. Consequently the weak limit
m=1 Pm → P∞ together with Pn+1 = PnΠ implies the Π-invariance of P∞.
We show the exponential bound (4.1) on the variation distance next because the
ergodicity proof depends on it. On metric spaces total variation distance can be
characterized in terms of continuous functions:
dVar(µ, ν) =
fdν : f continuous, sup |f | ≤ 1
This makes dVar(µ, ν) lower semicontinuous which we shall find convenient below.
Fix ℓ > 0. Then
dPn|Sℓ
dP|Sℓ
P ωx (Xn = 0,max
Xj · û ≤ ℓ/2)
E[P ωx (Xn = 0,max
Xj · û > ℓ/2)|Sℓ].
(4.4)
The L1(P)-norm of the second term is bounded by
In,ℓ = P0(max
Xj · û > Xn · û+ ℓ/2)
and (3.1) tells us that
In,ℓ ≤
e−sℓ/2(1− sδ/2)n−j ≤ Ce−sℓ/2. (4.5)
The integrand in the first term of (4.4) is measurable with respect to σ(ωx : x·û ≤ ℓ/2)
and therefore independent of Sℓ. The distance between the whole first term and 1 is
then Ŏ (In,ℓ). Thus for large enough ℓ,
dVar(Pn|Sℓ ,P|Sℓ) ≤
∫ ∣∣∣
dPn|Sℓ
dP|Sℓ
∣∣∣dP ≤ 2In,ℓ ≤ Ce−cℓ.
By the construction of P∞ as the Cesàro limit and by the lower semicontinuity and
convexity of the variation distance
dVar(P∞|Sℓ ,P|Sℓ) ≤ lim
dVar(Pm|Sℓ ,P|Sℓ) ≤ Ce
Part (b) has been verified.
As the last point we prove the ergodicity. Recall the notation E∞0 = E∞E
0 . Let
Ψ be a bounded local function on Ω. It suffices to prove that for some constant b
∣∣∣n−1
Ψ(TXjω)− b
∣∣∣ = 0. (4.6)
14 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
By an approximation it follows from this that for all F ∈ L1(P∞)
ΠjF (ω) → E∞F in L1(P∞). (4.7)
By standard theory (Section IV.2 in [12]) this is equivalent to ergodicity of P∞ for
the transition Π.
We combine the proof of Theorem 4.2 with the proof of (4.6). For this purpose let
Ψ be S−a+1-measurable with a <∞. Take a to be the parameter in the regeneration
times (2.2). Let
τi+1−1∑
Ψ(TXjω).
From the i.i.d. regeneration slabs and the moment bound (3.10) follows the limit
τm−1∑
Ψ(TXjω) = lim
ϕi = b0 P0-almost surely, (4.8)
where the constant b0 is defined by the limit.
To justify this more precisely, recall the definition of regeneration slabs given in
(2.4). Define a function Φ of the regeneration slabs by
Φ(S0,S1,S2, . . . ) =
τ2−1∑
Ψ(TXjω).
Since each regeneration slab has thickness in û-direction at least a, the Ψ-terms in
the sum do not read the environments below level zero and consequently the sum is
a function of (S0,S1,S2, . . . ). Next one can check for k ≥ 1 that
Φ(Sk−1,Sk,Sk+1, . . . ) =
τ2(Xτk−1+ · −Xτk−1 )−1∑
j=τ1(Xτk−1+ · −Xτk−1)
TXτk−1+j−Xτk−1 (TXτk−1ω)
= ϕk.
Now the sum of ϕ-terms in (4.8) can be decomposed into
ϕ0 + ϕ1 +
Φ(Sk,Sk+1,Sk+2, . . . ).
The limit (4.8) follows because the slabs (Sk)k≥1 are i.i.d. and the finite initial terms
ϕ0 + ϕ1 are eliminated by the m
−1 factor.
Let αn = inf{k : τk ≥ n}. Bounds (3.7)–(3.8) give finite moments of all orders to
the increments τk−τk−1 and this implies that n−1(ταn−1−ταn) → 0 P0-almost surely.
QUENCHED FUNCTIONAL CLT FOR RWRE 15
Consequently (4.8) yields the next limit, for another constant b:
Ψ(TXjω) = b P0-almost surely. (4.9)
By boundedness this limit is valid also in L1(P0) and the initial point of the walk is
immaterial by shift-invariance of P. Let ℓ > 0 and choose a small ε0 > 0. Abbreviate
Gn,x(ω) = E
[ ∣∣∣n−1
Ψ(TXjω)− b
∣∣∣1I
Xj · û ≥ X0 · û− ε0ℓ/2
I = {x ∈ Zd : x · û ≥ ε0ℓ, |x| ≤ Aℓ}
for some constant A. Use the bound (4.1) on the variation distance and the fact that
the functions Gn,x(ω) are uniformly bounded over all x, n, ω, and, if ℓ is large enough
relative to a and ε0, for x ∈ I the function Gn,x is Sε0ℓ/3-measurable.
P ω0 [Xℓ = x]Gn,x(ω) ≥ ε1
P∞{Gn,x(ω) ≥ ε1/(Cℓd)}
≤ Cℓdε−11
E∞Gn,x ≤ Cℓdε−11
EGn,x + Cℓ
2dε−11 e
−cε0ℓ/3.
By (4.9) EGn,x → 0 for any fixed x. Thus from above we get for any fixed ℓ,
1I{Xℓ ∈ I}Gn,Xℓ
≤ ε1 + Cℓ2dε−11 e−cε0ℓ/3. (4.10)
The reader should bear in mind that the constant C is changing from line to line.
Finally, we write
∣∣∣n−1
Ψ(TXjω)− b
≤ lim
1I{Xℓ ∈ I}
∣∣∣n−1
n+ℓ−1∑
Ψ(TXjω)− b
∣∣∣1I
Xj · û ≥ Xℓ · û− ε0ℓ/2
+ CP∞0 {Xℓ /∈ I} + CP∞0
Xj · û < Xℓ · û− ε0ℓ/2
≤ lim
1I{Xℓ ∈ I}Gn,Xℓ
+ CP∞0 {Xℓ · û < ε0ℓ}
+ CP∞0 { |Xℓ| > Aℓ} + CE∞0 P ωXℓ
Xj · û < X0 · û− ε0ℓ/2
As pointed out, P∞ satisfies Lemma 3.1 because hypotheses (N) and (M) were built
into the space Ω0 that supports P∞. This enables us to make the error probabilities
above small. Consequently, if we first pick ε0 and ε1 small enough, A large enough,
then ℓ large, and apply (4.10), we will have shown (4.6). Ergodicity of P∞ has been
shown. This concludes the proof of Theorem 4.1.
16 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Thereom 4.2 has also been established. It follows from the combination of (4.6)
and (4.9). �
5. Change of measure
There are several stages in the proof where we need to check that a desired con-
clusion is not affected by choice between P and P∞. We collect all instances of such
transfers in this section. The standing assumptions of this section are that P is an
i.i.d. product measure that satisfies Hypotheses (N) and (M), and that P∞ is the
measure given by Theorem 4.1. We show first that P∞ can be replaced with P in the
key condition (2.1) of Theorem 2.1.
Lemma 5.1. The velocity v defined by (2.5) satisfies v = E∞(D). There exists a
constant C such that
|E0(Xn)− nE∞(D)| ≤ C for all n ≥ 1. (5.1)
Proof. We start by showing v = E∞(D). The uniform exponential tail in the defi-
nition (4.3) of P0 makes the function D(ω) bounded and continuous on Ω0. By the
Cesàro definition of P∞,
E∞(D) = lim
nj−1∑
Ek(D) = lim
nj−1∑
E0[D(TXkω)].
The moment bounds (3.7)–(3.9) imply that the law of large numbers n−1Xn → v
holds also in L1(P0). From this and the Markov property
v = lim
E0(Xk+1 −Xk) = lim
E0[D(TXkω)].
We have proved v = E∞(D).
The variables (Xτj+1 −Xτj , τj+1−τj)j≥1 are i.i.d. with sufficient moments by (3.7)–
(3.9). With αn = inf{j ≥ 1 : τj − τ1 ≥ n} Wald’s identity gives
E0(Xταn−Xτ1) = E0(αn)E0(Xτ1 |β = ∞) and E0(ταn−τ1) = E0(αn)E0(τ1|β = ∞).
Consequently, by the definition (2.5) of v,
E0(Xn)− nv = vE0(ταn − τ1 − n)− E0(Xταn −Xτ1 −Xn).
It remains to show that E0(ταn − τ1−n) and E0(Xταn −Xτ1 −Xn) are bounded by
constants. We do this with a simple renewal argument. Let Yj = τj+1 − τj for j ≥ 1
and V0 = 0, Vm = Y1 + · · · + Ym. The quantity to bound is the forward recurrence
time Bn = min{k ≥ 0 : n+ k ∈ {Vm}} because ταn − τ1 − n = Bn.
We can write
Bn = (Y1 − n)+ +
1I{Y1 = k}Bn−k ◦ θ
QUENCHED FUNCTIONAL CLT FOR RWRE 17
where θ shifts the sequence {Yk} and makes Bn−k ◦ θ independent of Y1. The two
main terms on the right multiply to zero, so for any integer p ≥ 1
Bpn = ((Y1 − n)+)p +
1I{Y1 = k}(Bn−k ◦ θ)p.
Set z(n) = E0((Y1 − n)+)p. Moment bounds (3.7)–(3.8) give E0(Y p+11 ) < ∞ which
implies
z(n) <∞. Taking expectations and using independence gives the discrete
renewal equation
n = z(n) +
P0(Y1 = k)E0B
Induction on n shows that E0B
k=1 z(k) ≤ C(p) for all n. In particular,
E0(ταn − τ1 − n)p is bounded by a constant uniformly over n. To extend this to
E0|Xταn − Xτ1 − Xn|p apply an argument like the one given for (3.9) at the end of
Section 3. �
Proposition 5.2. Assume that there exists an ᾱ < 1/2 such that
|Eω0 (Xn)− E0(Xn)|
= Ŏ (n2ᾱ). (5.2)
Then condition (2.1) is satisfied for some α < 1/2.
Proof. By (5.1) assumption (5.2) turns into
|Eω0 (Xn)− nv|
= Ŏ (n2ᾱ). (5.3)
In the rest of this proof we use the conclusions of Lemma 3.1 under P∞ instead of P.
This is justified by part (c) of Theorem 4.1.
For k ≥ 1, recall that λk = inf{n ≥ 0 : (Xn − X0) · û ≥ k}. Take k = [nρ] for
a small enough ρ > 0. The point of the proof is to let the walk run up to a high
level k so that expectations under P∞ can be profitably related to expectations under
P through the variation distance bound (4.1). Estimation is needed to remove the
dependence on the environment on low levels. First compute as follows.
|Eω0 (Xn − nv)|
|Eω0 (Xn − nv, λk ≤ n) + Eω0 (Xn − nv, λk > n)|
≤ 2E∞
[ ∣∣Eω0 (Xn −Xλk − (n− λk)v, λk ≤ n)− Eω0 (λkv, λk ≤ n) + Eω0 (Xλk , λk ≤ n)2
n2E∞[P
0 (λk > n)]
≤ 8E∞
[ ∣∣∣
0≤m≤n
x·û≥k
P ω0 (Xm = x, λk = m)E
x {Xn−m − x− (n−m)v}
+ Ŏ (k2 + n2esk(1− sδ/2)n).
(5.4)
The last error term above is Ŏ (n2ρ). We used the Cauchy-Schwarz inequality and
Hypothesis (M) to get the second term in the first inequality, and then (3.1), (3.4),
and (3.5) in the last inequality.
18 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
To handle the expectation on line (5.4) we introduce a spanning set of vectors
that satisfy the main assumptions that û does. Namely, let {ûi}di=1 span Rd and
satisfy these conditions: |û − ûi| ≤ δ/(2M), where δ and M are the constants from
Hypotheses (N) and (M), and
αiûi with αi > 0. (5.5)
Then non-nestling (N) holds for each ûi with constant δ/2, and all the conclusions
of Lemma 3.1 hold when û is replaced by ûi and δ by δ/2. Define the event Ak =
{infiXi · û ≥ k} and the set
Λ = {x ∈ Zd : min
x · ûi ≥ 1}.
The point of introducing Λ is that the number of points x in Λ on level x · û = ℓ > 0
is of order Ŏ (ℓd−1).
By Jensen’s inequality the expectation on line (5.4) is bounded by
x∈Λ, x·û≥k
0≤m≤n
P ω0 (Xm = x, λk = m)
∣∣Eωx {Xn−m − x− (n−m)v, Ak/2}
(5.6)
0≤m≤n
x 6∈Λ
P ω0 (Xm = x, λk = m)
∣∣Eωx {Xn−m − x− (n−m)v}
+ 2E∞
0≤m≤n
x·û≥k
P ω0 (Xm = x, λk = m)
∣∣Eωx {Xn−m − x− (n−m)v, Ack/2}
By Cauchy-Schwarz, Hypothesis (M) and (3.1), the third term is Ŏ (n2e−sk/2) =
Ŏ (1). The second term is of order
n2max
0 (Xλk · ûi < 1)] ≤ n2max
P ω0 (Xm · ûi < 1)P ω0 (Xm · û ≥ k)
)1/2 ]
≤ es/2n2
(1− sδ/4)m/2e−µk/2eµM |û|m/2
= Ŏ (n2e−µk/2) = Ŏ (1),
for µ small enough. It remains to bound the term on line (5.6). To this end, by
Cauchy-Schwarz, (3.2) and (3.1),
P ω0 (Xm = x, λk = m) ≤ {e−sx·û/2esM |û|m/2∧1}×{eµk/2(1−µδ/2)(m−1)/2∧1} ≡ px,m,k.
Notice that ∑
{e−sx·û/2esM |û|m/2 ∧ 1} = Ŏ (md)
QUENCHED FUNCTIONAL CLT FOR RWRE 19
and ∑
md{eµk/2(1− µδ/2)(m−1)/2 ∧ 1} = Ŏ (kd+1).
Substitute these back into line (5.6) to eliminate the quenched probability coefficients.
The quenched expectation in (5.6) is Sk/2-measurable. Consequently variation dis-
tance bound (4.1) allows us to switch back to P and get this upper bound for line
(5.6):
x∈Λ, x·û≥k
0≤m≤n
px,m,kE[|Eωx {Xn−m − x− (n−m)v, Ak/2}|2] + Ŏ (kd+1n2e−ck/2).
The error term is again Ŏ (1).
Now insert Ac
back inside the quenched expectation, incurring another error term
of order Ŏ (kd+1n2e−sk/2) = Ŏ (1). Using the shift-invariance of P, along with (5.3),
and collecting all of the above error terms, we get
|Eω0 (Xn − nv)|
x∈Λ, x·û≥k
0≤m≤n
px,m,kE[ |Eωx {Xn−m − x− (n−m)v}|2] + Ŏ (n2ρ)
= Ŏ (kd+1n2ᾱ + n2ρ) = Ŏ (nρ(d+1)+2ᾱ).
Pick ρ > 0 small enough so that 2α = ρ(d + 1) + 2ᾱ < 1. The conclusion (2.1)
follows. �
Once we have verified the assumptions of Theorem 2.1 we have the CLT under
P∞-almost every ω. But we want the CLT under P-almost every ω. Thus as the final
point of this section we prove the transfer of the central limit theorem from P∞ to P.
This is where we use the ergodic theorem, Theorem 4.2. Let W be the probability
distribution of the Brownian motion with diffusion matrix D.
Lemma 5.3. Suppose the weak convergence Qωn ⇒ W holds for P∞-almost every ω.
Then the same is true for P-almost every ω.
Proof. It suffices to show that for any bounded uniformly continuous F on DRd[0,∞)
and any δ > 0
Eω0 [F (Bn)] ≤
F dW + δ P-a.s.
By considering also −F this gives Eω0 [F (Bn)] →
F dW P0-a.s. for each such func-
tion. A countable collection of them determines weak convergence.
Fix such an F . Let c =
F dW and
h(ω) = lim
Eω0 [F (Bn)].
20 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
For ℓ > 0 define the events
A−ℓ = {inf
Xn · û ≥ −ℓ}
and then
hℓ(ω) = lim
Eω0 [F (Bn), A−ℓ] and Ψ(ω) = 1I{ω : h̄ℓ(ω) ≤ c+ 12δ}.
The assumed quenched CLT under P∞ gives P∞{h = c} = 1. By (3.1), and by its
extension to P∞ in Theorem 4.1(c), there are constants 0 < C, s <∞ such that
|h(ω)− hℓ(ω)| ≤ Ce−sℓ
uniformly over all ω that support both P and P∞. Consequently if δ > 0 is given,
E∞Ψ = 1 for large enough ℓ. Since Ψ is S−ℓ-measurable Theorem 4.2 implies that
Ψ(TXjω) → 1 P0-a.s.
By increasing ℓ if necessary we can ensure that {h̄ℓ ≤ c + 12δ} ⊂ {h̄ ≤ c + δ} and
conclude that the stopping time
ζ = inf{n ≥ 0 : h̄(TXnω) ≤ c+ δ}
is P0-a.s. finite. From the definitions we now have
0 [F (Bn)] ≤
F dW + δ P0-a.s.
Then by bounded convergence
Eω0 E
0 [F (Bn)] ≤
F dW + δ P-a.s.
Since ζ is a finite stopping time, the strong Markov property, the uniform continuity
of F and the exponential moment bound (3.2) on X-increments imply
Eω0 [F (Bn)] ≤
F dW + δ P-a.s.
This concludes the proof. �
6. Reduction to path intersections
The preceding sections have reduced the proof of the main result Theorem 1.1 to
proving the estimate
|Eω0 (Xn)−E0(Xn)|
= Ŏ (n2α) for some α < 1/2. (6.1)
The next reduction takes us to the expected number of intersections of the paths of
two independent walks X and X̃ in the same environment. The argument uses a de-
composition into martingale differences through an ordering of lattice sites. This idea
QUENCHED FUNCTIONAL CLT FOR RWRE 21
for bounding a variance is natural and has been used in RWRE earlier by Bolthausen
and Sznitman [2].
Let P ω0,0 be the quenched law of the walks (X, X̃) started at (X0, X̃0) = (0, 0) and
P0,0 =
P ω0,0 P(dω) the averaged law with expectation operator E0,0. The set of sites
visited by a walk is denoted by X[0,n) = {Xk : 0 ≤ k < n} and |A| is the number of
elements in a discrete set A.
Proposition 6.1. Let P be an i.i.d. product measure and satisfy Hypotheses (N) and
(M). Assume that there exists an ᾱ < 1/2 such that
E0,0(|X[0,n) ∩ X̃[0,n)|) = Ŏ (n2ᾱ). (6.2)
Then condition (6.1) is satisfied.
Proof. For L ≥ 0, define B(L) = {x ∈ Zd : |x| ≤ L}. Fix n ≥ 1, c > |û|, and let
(xj)j≥1 be some fixed ordering of B(cMn) satisfying
∀i ≥ j : xi · û ≥ xj · û.
For B ⊂ Zd let SB = σ{ωx : x ∈ B}. Let Aj = {x1, . . . , xj}, ζ0 = E0(Xn), and for
j ≥ 1
ζj = E(E
0 (Xn)|SAj).
(ζj − ζj−1)j≥1 is a sequence of L2(P)-martingale differences and we have
E[ |Eω0 (Xn)− E0(Xn)| 2] (6.3)
|E0(Xn)− E{Eω0 (Xn)|SB(cMn)}|2
[ ∣∣Eω0 (Xn,max
|Xi| > cMn)
− E{Eω0 (Xn,max
|Xi| > cMn) |SB(cMn)}
∣∣2 ]
|B(cMn)|∑
E( |ζj − ζj−1|2 ) + Ŏ (n3e−sM(c−|û|)n). (6.4)
In the last inequality we have used (3.2). The error is Ŏ (1). For z ∈ Zd define
half-spaces
H(z) = {x ∈ Zd : x · û > z · û}.
Since Aj−1 ⊂ Aj ⊂ H(xj)c,
E(|ζj − ζj−1|2)
P(dωAj)
P(dωAc
)P(dω̃xj)
Eω0 (Xn)− E
〈ω,ω̃xj 〉
0 (Xn)
P(dωH(xj)c)P(dω̃xj)
P(dωH(xj))
Eω0 (Xn)− E
〈ω,ω̃xj 〉
0 (Xn)
. (6.5)
Above 〈ω, ω̃xj〉 denotes an environment obtained from ω by replacing ωxj with ω̃xj .
22 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
We fix a point z = xj to develop a bound for the expression above, and then return
to collect the estimates. Abbreviate ω̃ = 〈ω, ω̃xj〉. Consider two walks Xn and X̃n
starting at 0. Xn obeys environment ω, while X̃n obeys ω̃. We can couple the two
walks so that they stay together until the first time they visit z. Until a visit to z
happens, the walks are identical. So we write
P(dωH(z))
Eω0 (Xn)− Eω̃0 (Xn)
(6.6)
P(dωH(z))
P ω0 (Hz = m)
Eωz (Xn−m − z)− Eω̃z (Xn−m − z)
P(dωH(z))
P ω0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
Eωz (Xn−m − z)− Eω̃z (Xn−m − z)
(6.7)
Decompose H(z) = Hℓ(z) ∪H′ℓ(z) where
Hℓ(z) = {x ∈ Zd : z · û < x · û < z · û+ ℓ} and H′ℓ(z) = {x ∈ Zd : x · û ≥ z · û+ ℓ}.
Take a single (ℓ,m) term from the sum in (6.7) and only the expectation Eωz (Xn−m−
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
×Eωz (Xn−m − z)
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
×Eωz (Xτ (ℓ)1 +n−m −Xτ (ℓ)1 )
(6.8)
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
×Eωz (Xn−m −Xτ (ℓ)1 +n−m +Xτ (ℓ)1 − z)
(6.9)
The parameter ℓ in the regeneration time τ
1 of the walk started at z ensures that the
subsequent walkX
1 + ·
stays inH′ℓ(z). Below we make use of this to get independence
from the environments in H′ℓ(z)c. By (3.9) the quenched expectation in (6.9) can be
bounded by Cpℓ
p, for any p > 1.
QUENCHED FUNCTIONAL CLT FOR RWRE 23
Integral (6.8) is developed further as follows.
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
× Eωz (Xτ (ℓ)1 +n−m −Xτ (ℓ)1 )
P(dωHℓ(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
P(dωH′
(z))E
z (Xτ (ℓ)1 +n−m
P(dωHℓ(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
× Ez(Xτ (ℓ)1 +n−m −Xτ (ℓ)1 |SH′ℓ(z)c)
P(dωHℓ(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
× E0(Xn−m|β = ∞).
(6.10)
The last equality above comes from the regeneration structure, see Proposition 1.3 in
Sznitman-Zerner [17]. The σ-algebra SH′
(z)c is contained in the σ-algebra G1 defined
by (1.22) of [17] for the walk starting at z.
The last quantity (6.10) above reads the environment only until the first visit to z,
hence does not see the distinction between ω and ω̃. Hence when the integral (6.7) is
developed separately for ω and ω̃ into the sum of integrals (6.8) and (6.9), integrals
(6.8) for ω and ω̃ cancel each other. We are left only with two instances of integral
(6.9), one for both ω and ω̃. The last quenched expectation in (6.9) we bound by
p as was mentioned above.
Going back to (6.6), we get this bound:
P(dωH(z))
Eω0 (Xn)− Eω̃0 (Xn)
P(dωH(z))
ℓpP ω0 (Hz < n, ℓ− 1 ≤ max
0≤j≤Hz
Xj · û− z · û < ℓ)
P(dωH(z))E
0 [(MHz − z · û)p1I{Hz < n}]
≤ Cpnpε
P(dωH(z))P
0 (Hz < n) + Cps
−pe−sn
For the last inequality we used (3.6) with ℓ = nε and some small ε, s > 0. Square,
take z = xj , integrate as in (6.5), and use Jensen’s inequality to bring the square
inside the integral to get
E( |ζj − ζj−1|2 ) ≤ 2Cpn2pεE[ |P ω0 (Hxj < n)|2 ] + 2Cps−2pe−sn
24 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Substitute these bounds into line (6.4) and note that the error there is Ŏ (1).
E[ |Eω0 (Xn)−E0(Xn)|2 ]
≤ Cpn2pε
E[ |P ω0 (Hz < n)|2 ] + Ŏ (nds−2pe−sn
) + Ŏ (1)
= Cpn
P0,0(z ∈ X[0,n) ∩ X̃[0,n)) + Ŏ (1)
= Cpn
2pεE0,0[ |X[0,n) ∩ X̃[0,n)| ] + Ŏ (1).
Utilize assumption (6.2) and take ε > 0 small enough so that 2α = 2pε + 2ᾱ < 1.
(6.1) has been verified. �
7. Bound on intersections
The remaining piece of the proof of Theorem 1.1 is this estimate:
E0,0( |X[0,n) ∩ X̃[0,n)| ) = Ŏ (n2α) for some α < 1/2. (7.1)
X and X̃ are two independent walks in a common environment with quenched
distribution P ωx,y[X0,∞ ∈ A, X̃0,∞ ∈ B] = P ωx (A)P ωy (B) and averaged distribution
Ex,y(·) = EP ωx,y(·).
To deduce the sublinear bound we introduce regeneration times at which both
walks regenerate on the same level in space (but not necessarily at the same time).
Intersections happen only within the regeneration slabs, and the expected number
of intersections decays exponentially in the distance between the points of entry of
the walks in the slab. From regeneration to regeneration the difference of the two
walks operates like a Markov chain. This Markov chain can be approximated by
a symmetric random walk. Via this preliminary work the required estimate boils
down to deriving a Green function bound for a Markov chain that can be suitably
approximated by a symmetric random walk. This part is relegated to an appendix.
Except for the appendix, we complete the proof of the functional central limit theorem
in this section.
To aid our discussion of a pair of walks (X, X̃) we introduce some new notation.
We write θm,n for the shift on pairs of paths: θm,n(x0,∞, y0,∞) = (θ
mx0,∞, θ
ny0,∞). If
we write separate expectations for X and X̃ under P ωx,y, these are denoted by E
x and
Ẽωy .
By a joint stopping time we mean pair (α, α̃) that satisfies {α = m, α̃ = n} ∈
σ{X0,m, X̃0,n}. Under the distribution P ωx,y the walks X and X̃ are independent.
Consequently if α ∨ α̃ <∞ P ωx,y-almost surely then for any events A and B,
P ωx,y[(X0,α, X̃0,α̃) ∈ A, (Xα,∞, X̃α̃,∞) ∈ B]
= Eωx,y
1I{(X0,α, X̃0,α̃) ∈ A}P ωXα, eXα̃{(X0,∞, X̃0,∞) ∈ B}
QUENCHED FUNCTIONAL CLT FOR RWRE 25
This type of joint restarting will be used without comment in the sequel.
For this section it will be convenient to have level stopping times and running
maxima that are not defined relative to the initial level.
γℓ = inf{n ≥ 0 : Xn · û ≥ ℓ} and γ+ℓ = inf{n ≥ 0 : Xn · û > ℓ}.
Since û ∈ Zd, γ+ℓ is simply an abbreviation for γℓ+1. Let Mn = sup{Xi · û : i ≤ n}
be the running maximum. M̃n, γ̃ℓ and γ̃
ℓ are the corresponding quantities for the X̃
walk. The first backtracking time for the X̃ walk is β̃ = inf{n ≥ 1 : X̃n · û < X̃0 · û}.
Define
L = inf{ℓ > (X0 · û) ∧ (X̃0 · û) : Xγℓ · û = X̃γ̃ℓ · û = ℓ}
as the first fresh common level after at least one walk has exceeded its starting level.
Set L = ∞ if there is no such common level. When the walks are on a common level,
their difference will lie in the hyperplane
Vd = {z ∈ Zd : z · û = 0}.
We start with exponential tail bounds on the time to reach the common level.
Lemma 7.1. There exist constants 0 < a1, a2, C < ∞ such that, for all x, y ∈ Zd,
m ≥ 0 and P-a.e. ω,
P ωx,y(γL ∨ γ̃L ≥ m) ≤ Cea1|y·û−x·û|−a2m. (7.2)
For the proof we need a bound on the overshoot.
Lemma 7.2. There exist constants 0 < C, s < ∞ such that, for any level k, any
b ≥ 1, any x ∈ Zd such that x · û ≤ k, and P-a.e. ω,
P ωx [Xγk · û ≥ k + b] ≤ Ce−sb. (7.3)
Proof. From (3.1) it follows that for a constant C, for any level ℓ, any x ∈ Zd, and
P-a.e. ω,
Eωx [number of visits to level ℓ] =
P ωx [Xn · û = ℓ] ≤ C. (7.4)
(This is certainly clear if x · û = ℓ. Otherwise wait until the process first lands on
level ℓ, if ever.)
26 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
From this and the exponential moment hypothesis we deduce the required bound
on the overshoots: for any k, any x ∈ Zd such that x · û ≤ k, and P-a.e. ω,
P ωx [Xγk · û ≥ k + b] =
z·û<k
P ωx [γk > n, Xn = z, Xn+1 · û ≥ k + b]
z·û=k−ℓ
P ωx [γk > n, Xn = z]P
z [X1 · û ≥ k + b]
z·û=k−ℓ
P ωx [Xn = z]Ce
−s(ℓ+b)
≤ Ce−sb
e−sℓ ≤ Ce−sb. �
Proof of Lemma 7.1. Consider first γL, and let us restrict ourselves to the case where
the initial points x, y satisfy x · û < y · û.
Perform an iterative construction of stopping times ηi, η̃i and levels ℓ(i), ℓ̃(i). Let
η0 = η̃0 = 0, x0 = x and y0 = y. ℓ(0) and ℓ̃(0) need not be defined. Suppose that
the construction has been done to stage i − 1 with xi−1 = Xηi−1 , yi−1 = X̃η̃i−1 , and
xi−1 · û < yi−1 · û. Then set
ℓ(i) = Xγ(yi−1·û) · û, ℓ̃(i) = X̃γ̃(ℓ(i)) · û, ηi = γ(ℓ̃(i)) and η̃i = γ̃(Xηi · û+ 1).
In words, starting at (xi−1, yi−1) with yi−1 above xi−1, let X reach the level of yi−1
and let ℓ(i) be the level X lands on; let X̃ reach the level ℓ(i) and let ℓ̃(i) be the level
X̃ lands on. Now let X try to establish a new common level at ℓ̃(i) with X̃ : in other
words, follow X until the time ηi it reaches level ℓ̃(i) or above, and stop it there.
Finally, reset the situation by letting X̃ reach a level strictly above the level of Xηi ,
and stop it there at time η̃i. The starting locations for the next step are xi = Xηi ,
yi = X̃η̃i that satisfy xi · û < yi · û.
We show that within each step of the iteration there is a uniform lower bound on
the probability that a fresh common level was found. For this purpose we utilize
assumption (1.1) in the weaker form
P{ω : P ω0 (Xγ1 · û = 1) ≥ κ } = 1. (7.5)
Pick b large enough so that the bound in (7.3) is < 1. For z, w ∈ Zd such that
z · û ≥ w · û define a function
ψ(z, w) = P ωz,w[ Xγk · û = k for each k ∈ {z · û, . . . , z · û+ b},
X̃γ̃(z·û) · û− z · û ≤ b ]
≥ κb(1− Ce−sb) ≡ κ2 > 0.
QUENCHED FUNCTIONAL CLT FOR RWRE 27
The uniform lower bound comes from the independence of the walks, from (7.3) and
from iterating assumption (7.5). By the Markov property
P ωxi−1,yi−1[Xγ(ℓ̃(i)) · û = ℓ̃(i)]
≥ P ωxi−1,yi−1[ X̃γ̃(ℓ(i)) · û− ℓ(i) ≤ b, Xγk · û = k for each k ∈ {ℓ(i), . . . , ℓ(i) + b} ]
≥ Eωxi−1,yi−1
ψ(Xγ(yi−1·û), yi−1)
≥ κ2.
The first iteration on which the attempt to create a common level at ℓ̃(i) succeeds
I = inf{i ≥ 1 : Xγ
ℓ̃(i)
· û = ℓ̃(i)}.
Then ℓ̃(I) is a new fresh common level and consequently L ≤ ℓ̃(I). This gives the
upper bound
γL ≤ γℓ̃(I).
We develop an exponential tail bound for γℓ̃(I), still under the assumption x · û < y · û.
From the uniform bound above and the Markov property we get
P ωx,y[I > i] ≤ (1− κ2)i.
Lemma 7.2 gives an exponential bound
P ωx,y
(X̃η̃i − X̃η̃i−1) · û ≥ b
≤ Ce−sb (7.6)
because the distance (X̃η̃i − X̃η̃i−1) · û is a sum of four overshoots:
X̃η̃i − X̃η̃i−1
· û =
X̃γ̃(Xηi ·û+1) · û−Xηi · û− 1
+ 1 +
Xγ(ℓ̃(i)) · û− ℓ̃(i)
X̃γ̃(ℓ(i)) · û− ℓ(i)
γ( eXη̃i−1 ·û)
· û− X̃η̃i−1 · û
Next, from the exponential tail bound on
X̃η̃i − X̃η̃i−1
· û and from
ℓ̃(i) ≤ X̃η̃i · û =
X̃η̃j − X̃η̃j−1
· û+ y · û
we get the large deviation estimate
P ωx,y[ℓ̃(i) ≥ bi+ y · û] ≤ e−sbi for i ≥ 1 and b ≥ b0,
for some constants 0 < s < ∞ (small enough) and 0 < b0 < ∞ (large enough).
Combine this with the bound above on I to write
P ωx,y[ℓ̃(I) ≥ a] ≤ P ωx,y[I > i] + P ωx,y[ℓ̃(i) ≥ a]
≤ e−si + esy·û−sa ≤ 2esy·û−sa
where we assume a ≥ 2b0 + y · û and set the integer i = ⌊b−10 (a− y · û)⌋. Recall that
0 < s <∞ is a constant whose value can change from line to line.
28 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
From (3.1) and an exponential Chebyshev
P ωx,y[γk > m] ≤ P ωx [Xm · û ≤ k] ≤ esk−sx·û−h1m
for all x, y ∈ Zd, k ∈ Z and m ≥ 0. Above and in the remainder of this proof h1, h2
and h3 are small positive constants. Finally we derive
P ωx,y[γℓ̃(I) > m] ≤ P ωx,y[ℓ̃(I) ≥ k + x · û] + P ωx,y[γk+x·û > m]
≤ 2es(y−x)·û−sk + esk−h1m ≤ Ces(y−x)·û−h2m.
To justify the inequalities above assume m ≥ 4sb0/h1 > 4s/h1 and pick k in the
range
+ (y − x) · û ≤ k ≤ 3h1m
+ (y − x) · û.
To summarize, at this point we have
P ωx,y[γL > m] ≤ Ces(y−x)·û−h2m for x · û < y · û. (7.7)
To extend this estimate to the case x · û ≥ y · û, simply allow X̃ to go above x and
then apply (7.7). By an application of the overshoot bound (7.3) and (7.7) at the
point (x, X̃γ̃(x·û+1))
P ωx,y[γL > m] ≤ Eωx,yP ωx, eXγ̃(x·û+1)[γL > m]
≤ P ωx,y[X̃γ̃(x·û+1) > x · û+ εm] + Cesεm−h2m ≤ Ce−h3m
if we take ε > 0 small enough.
We have proved the lemma for γL, and the same argument works for γ̃L. �
Assuming that X0 · û = X̃0 · û define the joint stopping times
(ρ, ρ̃) = (γ+
, γ̃+
(ν1, ν̃1) =
(ρ, ρ̃) + (γL, γ̃L) ◦ θρ,ρ̃ if ρ ∨ ρ̃ <∞
∞ if ρ = ρ̃ = ∞.
(7.8)
Notice that ρ and ρ̃ are finite or infinite together, and they are infinite iff neither
walk backtracks below its initial level (β = β̃ = ∞). Let ν0 = ν̃0 = 0 and for k ≥ 0
define
(νk+1, ν̃k+1) = (νk, ν̃k) + (ν1, ν̃1) ◦ θνk,ν̃k .
Finally let (ν, ν̃) = (γL, γ̃L), K = sup{k ≥ 0 : νk ∨ ν̃k <∞}, and
(µ1, µ̃1) = (ν, ν̃) + (νK , ν̃K) ◦ θν,ν̃ . (7.9)
These represent the first common regeneration times of the two paths. Namely,
Xµ1 · û = X̃µ̃1 · û and for all n ≥ 1,
Xµ1−n · û < Xµ1 · û ≤ Xµ1+n · û and X̃µ̃1−n · û < X̃µ̃1 · û ≤ X̃µ̃1+n · û.
QUENCHED FUNCTIONAL CLT FOR RWRE 29
Next we extend the exponential tail bound to the regeneration times.
Lemma 7.3. There exist constants 0 < C < ∞ and η̄ ∈ (0, 1) such that, for all
x, y ∈ Vd = {z ∈ Zd : z · û = 0}, k ≥ 0, and P-a.e. ω, we have
P ωx,y(µ1 ∨ µ̃1 ≥ k) ≤ C(1− η̄)k. (7.10)
Proof. We prove geometric tail bounds successively for γ+1 , γ
ℓ , γ
, ρ, ν1, νk, and
finally for µ1. To begin, (3.1) implies that
P ω0 (γ
1 ≥ n) ≤ P ω0 (Xn−1 · û ≤ 1) ≤ es2(1− η1)n−1
with η1 = s2δ/2, for some small s2 > 0. By summation by parts
Eω0 (e
1 ) ≤ es2Js3 ,
for a small enough s3 > 0 and Js = 1 + (e
s − 1)/(1 − (1 − η1)es). By the Markov
property for ℓ ≥ 1,
Eω0 (e
ℓ ) ≤
x·û>ℓ−1
Eω0 (e
ℓ−1 , Xγ+
= x)Eωx (e
But if x · û > ℓ− 1, then Eωx (es3γ
ℓ ) ≤ ETxω0 (es3γ
1 ). Therefore by induction
Eω0 (e
ℓ ) ≤ (es2Js3)ℓ for any integer ℓ ≥ 0. (7.11)
Next for an integer r ≥ 1,
Eω0 (e
Mr ) =
Eω0 (e
ℓ ,Mr = ℓ) ≤
Eω0 (e
ℓ )1/2P ω0 (Mr = ℓ)
(es2J2s4)
ℓ/2(1I{ℓ < 3Mr|û|}+ e−s5ℓ)1/2 ≤ C(es2J2s4)Cr,
for some C and for positive but small enough s2, s4, and s5. In the last inequality
above we used the fact that es2J2s4 converges to 1 as first s4 ց 0 and then s2 ց 0.
In the second-to-last inequality we used (3.2) to get the bound
P ω0 (Xi · û ≥ ℓ) ≤
e−sℓeM |û|si ≤ Ce−s5ℓ if ℓ ≥ 3M |û|r.
Above we assumed that the walk X starts at 0. Same bounds work for any x ∈ Vd
because a shift orthogonal to û does not alter levels, in particular P ωx (Mr = ℓ) =
P Txω0 (Mr = ℓ).
By this same observation we show that for all x, y ∈ Vd
Eωx,y(e
fMr ) ≤ C(es2J2s4)Cr
by repeating the earlier series of inequalities.
30 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Using (3.1) and these estimates gives for x, y ∈ Vd
P ωx,y(ρ ≥ n, β ∧ β̃ <∞) =
P ωx,y(γ
Mr∨fMr
≥ n, β ∧ β̃ = r)
≤ e−s4n/2
1≤r≤εn
Eωx (e
Mr )1/2Eωx,y(e
fMr )1/2
P ωx {Xr · û < x · û}+ P ωy {X̃r · û < y · û}
≤ Cεne−s4n/2(es2J2s4)Cεn + C(1− s6δ/2)εn.
Taking ε > 0 small enough shows the existence of a constant η2 > 0 such that for all
x, y ∈ Vd, n ≥ 1, and P-a.e. ω,
P ωx,y(ρ ≥ n, β ∧ β̃ <∞) ≤ C(1− η2)n.
Same bound works for ρ̃ also. We combine this with (7.2) to get a geometric tail
bound for ν11I{β ∧ β̃ <∞}. Recall definition (7.8) and take ε > 0 small.
P ωx,y[ν1 ≥ k, β ∧ β̃ <∞]
≤ P ωx,y[ρ ≥ k/2, β ∧ β̃ <∞] + P ωx,y[β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| > εk]
+ P ωx,y[γL ◦ θρ,ρ̃ ≥ k/2, β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| ≤ εk ].
On the right-hand side above we have an exponential bound for each of the three
probabilities: the first probability gets it from the estimate immediately above, the
second from a combination of that and (3.2), and the third from (7.2):
P ωx,y[γL ◦ θρ,ρ̃ ≥ k/2, β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| ≤ εk ]
= Eωx,y
1I{β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| ≤ εk}P ωXρ , eXρ̃{γL ≥ k/2}
≤ Cea1εk−a2k/2.
The constants in the last bound above are those from (7.2), and we choose ε <
a2/(2a1). We have thus established that
Eωx,y(e
s7ν11I{β ∧ β̃ <∞}) ≤ J̄s7
for a small enough s7 > 0, with J̄s = C(1− (1− η3)es)−1 and η3 > 0.
To move from ν1 to νk use the Markov property and induction:
Eωx,y(e
s7νk1I{νk ∨ ν̃k <∞})
Eωx,y(e
s7νk−11I{νk−1 ∨ ν̃k−1 <∞, Xνk−1 = z, X̃ν̃k−1 = z̃})
× Eωz,z̃(es7ν11I{β ∧ β̃ <∞})
≤ J̄s7Eωx,y(es7νk−11I{νk−1 ∨ ν̃k−1 <∞}) ≤ · · · ≤ J̄ks7.
QUENCHED FUNCTIONAL CLT FOR RWRE 31
Next, use the Markov property at the joint stopping times (νk, ν̃k), (7.2), (3.7),
and induction to derive
P ωx,y(K ≥ k) ≤ P ωx,y(νk ∨ ν̃k <∞)
P ωx,y(νk−1 ∨ ν̃k−1 <∞, Xνk−1 = z, X̃ν̃k−1 = z̃)P ωz,z̃(β ∧ β̃ <∞)
≤ (1− η2)P ωx,y(νk−1 ∨ ν̃k−1 <∞) ≤ (1− η2)k.
Finally use the Cauchy-Schwarz and Chebyshev inequalities to write
P ωx,y(νK ≥ n) =
P ωx,y(νk ≥ n,K = k)
(1− η2)k + e−s7n
1≤k≤εn
Eωx,y(e
s7νk1I{νk ∨ ν̃k <∞})
≤ C(1− η2)εn + Cεne−s7nJ̄εns7 .
Looking at the definition (7.9) of µ1 we see that an exponential tail bound follows by
applying (7.2) to the ν-part and by taking ε > 0 small enough in the last calculation
above. Repeat the same argument for µ̃1 to conclude the proof of (7.10). �
After these preliminaries define the sequence of common regeneration times by
µ0 = µ̃0 = 0 and
(µi+1, µ̃i+1) = (µi, µ̃i) + (µ1, µ̃1) ◦ θµi,µ̃i. (7.12)
The next tasks are to identify suitable Markovian structures and to develop a cou-
pling.
Proposition 7.4. The process (X̃µ̃i−Xµi)i≥1 is a Markov chain on Vd with transition
probability
q(x, y) = P0,x[X̃µ̃1 −Xµ1 = y | β = β̃ = ∞]. (7.13)
Note that the time-homogeneous Markov chain does not start from X̃0−X0 because
the transition to X̃µ̃1 −Xµ1 does not include the condition β = β̃ = ∞.
Proof. Express the iteration of the common regeneration times as
(µi, µ̃i) = (µi−1, µ̃i−1) +
(ν, ν̃) + (νK , ν̃K) ◦ θν,ν̃
◦ θµi−1,µ̃i−1 , i ≥ 1.
Let Ki be the value of K at the ith iteration:
Ki = K ◦ θν,ν̃ ◦ θµi−1,µ̃i−1 .
32 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Let n ≥ 2 and z1, . . . , zn ∈ Vd. Write
P0,z[X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n] (7.14)
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
Ki = ki, µi = mi, µ̃i = m̃i,
Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1,
(X̃µ̃1 −Xµ1) ◦ θmn−1,m̃n−1 = zn
Above Ψ is the set of vectors (ki, mi, m̃i, vi, ṽi)1≤i≤n−1 such that ki is nonnegative and
mi, m̃i, vi · û, and ṽi · û are all positive and strictly increasing in i, and ṽi − vi = zi.
Define the events
Ak,b,b̃ = {ν + νk ◦ θν,ν̃ = b , ν̃ + ν̃k ◦ θν,ν̃ = b̃}
Bb,b̃ = {Xj · û ≥ X0 · û for 1 ≤ j ≤ b , X̃j · û ≥ X̃0 · û for 1 ≤ j ≤ b̃}.
Let m0 = m̃0 = 0, bi = mi −mi−1 and b̃i = m̃i − m̃i−1. Rewrite the sum from above
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
[ n−1∏
1I{Aki,bi,b̃i} ◦ θ
mi−1,m̃i−1
1I{Bbi, b̃i} ◦ θ
mi−1,m̃i−1 , Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1,
β ◦ θmn−1 = β̃ ◦ θm̃n−1 = ∞ , (X̃µ̃1 −Xµ1) ◦ θmn−1,m̃n−1 = zn
Next restart the walks at times (mn−1, m̃n−1) to turn the sum into the following.
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
Eω0,z
[ n−1∏
1I{Aki,bi,b̃i} ◦ θ
mi−1,m̃i−1
1I{Bbi, b̃i} ◦ θ
mi−1,m̃i−1 , Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1
× P ωvn−1 , ṽn−1
β = β̃ = ∞ , X̃µ̃1 −Xµ1 = zn
Inside the outermost braces the events in the first quenched expectation force the
level
ℓ = Xmn−1 · û = vn−1 · û = X̃m̃n−1 · û = ṽn−1 · û
QUENCHED FUNCTIONAL CLT FOR RWRE 33
to be a new maximal level for both walks. Consequently the first quenched expecta-
tion is a function of {ωx : x · û < ℓ} while the last quenched probability is a function
of {ωx : x · û ≥ ℓ}. By independence of the environments, the sum becomes
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
[ n−1∏
1I{Aki,bi,b̃i} ◦ θ
mi−1,m̃i−1 (7.15)
1I{Bbi, b̃i} ◦ θ
mi−1,m̃i−1 , Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1
× Pvn−1 , ṽn−1
β = β̃ = ∞ , X̃µ̃1 −Xµ1 = zn
By a shift and a conditioning the last probability transforms as follows.
Pvn−1 , ṽn−1
β = β̃ = ∞ , X̃µ̃1 −Xµ1 = zn
= P0,zn−1
X̃µ̃1 −Xµ1 = zn
∣∣ β = β̃ = ∞
Pvn−1 , ṽn−1
β = β̃ = ∞
= q(zn−1, zn)Pvn−1 , ṽn−1
β = β̃ = ∞
Now reverse the above use of independence to put the probability
Pvn−1 , ṽn−1 [β = β̃ = ∞]
back together with the expectation (7.15). Inside this expectation this furnishes the
event β ◦ θmn−1 = β̃ ◦ θm̃n−1 = ∞ and with this the union of the entire collection of
events turns back into X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n−1. Going back to the beginning
on line (7.14) we see that we have now shown
P0,z[X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n]
= P0,z[X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n− 1]q(zn−1, zn).
Continue by induction. �
The Markov chain Yk = X̃µ̃k − Xµk will be compared to a random walk obtained
by performing the same construction of joint regeneration times to two independent
walks in independent environments. To indicate the difference in construction we
change notation. Let the pair of walks (X, X̄) obey P0 ⊗Pz with z ∈ Vd, and denote
the first backtracking time of the X̄ walk by β̄ = inf{n ≥ 1 : X̄n · û < X̄0 · û}.
Construct the common regeneration times (ρk, ρ̄k)k≥1 for (X, X̄) by the same recipe
[(7.8), (7.9) and (7.12)] as was used to construct (µk, µ̃k)k≥1 for (X, X̃). Define
Ȳk = X̄ρ̄k − Xρk . An analogue of the previous proposition, which we will not spell
out, shows that (Ȳk)k≥1 is a Markov chain with transition
q̄(x, y) = P0 ⊗ Px[X̄ρ̄1 −Xρ1 = y | β = β̄ = ∞]. (7.16)
34 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
In the next two proofs we make use of the following decomposition. Suppose
x · û = y · û = 0, and let (x1, y1) be another pair of points on a common, higher level:
x1 · û = y1 · û = ℓ > 0. Then we can write
{(X0, X̃0) = (x, y), β = β̃ = ∞, (Xµ1 , X̃µ̃1) = (x1, y1)}
(γ,γ̃)
{X0,n(γ) = γ, X̃0,n(γ̃) = γ̃, β ◦ θn(γ) = β̃ ◦ θn(γ̃) = ∞}. (7.17)
Here (γ, γ̃) range over all pairs of paths that connect (x, y) to (x1, y1), that stay
between levels 0 and ℓ−1 before the final points, and for which a common regeneration
fails at all levels before ℓ. n(γ) is the index of the final point along the path, so for
example γ = (x = z0, z1, . . . , zn(γ)−1, zn(γ) = x1).
Proposition 7.5. The process (Ȳk)k≥1 is a symmetric random walk on Vd and its
transition probability satisfies
q̄(x, y) = q̄(0, y − x) = q̄(0, x− y) = P0 ⊗ P0[X̄ρ̄1 −Xρ1 = y − x | β = β̄ = ∞].
Proof. It remains to show that for independent (X, X̄) the transition (7.16) reduces to
a symmetric random walk. This becomes obvious once probabilities are decomposed
into sums over paths because the events of interest are insensitive to shifts by z ∈ Vd.
P0 ⊗ Px[β = β̄ = ∞ , X̄ρ̄1 −Xρ1 = y]
P0 ⊗ Px[β = β̄ = ∞ , Xρ1 = w , X̄ρ̄1 = y + w]
(γ,γ̄)
P0[X0,n(γ) = γ, β ◦ θn(γ) = ∞]Px[X0,n(γ̄) = γ̄, β ◦ θn(γ̄) = ∞]
(γ,γ̄)
P0[X0,n(γ) = γ]Px[X0,n(γ̄) = γ̄]
P0[β = ∞]
(7.18)
Above we used the decomposition idea from (7.17). Here (γ, γ̄) range over the
appropriate class of pairs of paths in Zd such that γ goes from 0 to w and γ̄ goes from
x to y + w. The independence for the last equality above comes from noticing that
the quenched probabilities P ω0 [X0,n(γ) = γ] and P
w [β = ∞] depend on independent
collections of environments.
The probabilities on the last line of (7.18) are not changed if each pair (γ, γ̄) is
replaced by (γ, γ′) = (γ, γ̄−x). These pairs connect (0, 0) to (w, y−x+w). Because
x ∈ Vd satisfies x · û = 0, the shift has not changed regeneration levels. This shift
turns Px[X0,n(γ̄) = γ̄] on the last line of (7.18) into P0[X0,n(γ′) = γ
′]. We can reverse
the steps in (7.18) to arrive at the probability
P0 ⊗ P0[β = β̄ = ∞ , X̄ρ̄1 −Xρ1 = y − x].
This proves q̄(x, y) = q̄(0, y − x).
QUENCHED FUNCTIONAL CLT FOR RWRE 35
Once both walks start at 0 it is immaterial which is labeled X and which X̄ , hence
symmetry holds. �
It will be useful to know that q̄ inherits all possible transitions from q.
Lemma 7.6. If q(z, w) > 0 then also q̄(z, w) > 0.
Proof. By the decomposition from (7.17) we can express
Px,y[(Xµ1 , X̃µ̃1) = (x1, y1)|β = β̃ = ∞] =
(γ,γ̃)
EP ω[γ]P ω[γ̃]P ωx1 [β = ∞]P
[β = ∞]
Px,y[β = β̃ = ∞]
If this probability is positive, then at least one pair (γ, γ̃) satisfies EP ω[γ]P ω[γ̃] > 0.
This implies that P [γ]P [γ̃] > 0 so that also
Px ⊗ Py[(Xµ1 , X̃µ̃1) = (x1, y1)|β = β̃ = ∞] > 0. �
In the sequel we detach the notations Y = (Yk) and Ȳ = (Ȳk) from their original
definitions in terms of the walks X , X̃ and X̄, and use (Yk) and (Ȳk) to denote
canonical Markov chains with transitions q and q̄. Now we construct a coupling.
Proposition 7.7. The single-step transitions q(x, y) for Y and q̄(x, y) for Ȳ can be
coupled in such a way that, when the processes start from a common state x,
Px,x[Y1 6= Ȳ1] ≤ Ce−α1|x|
for all x ∈ Vd. Here C and α1 are finite positive constants independent of x.
Proof. We start by constructing a coupling of three walks (X, X̃, X̄) such that the
pair (X, X̃) has distribution Px,y and the pair (X, X̄) has distribution Px ⊗ Py.
First let (X, X̃) be two independent walks in a common environment ω as before.
Let ω̄ be an environment independent of ω. Define the walk X̄ as follows. Initially
X̄0 = X̃0. On the sites {Xk : 0 ≤ k < ∞} X̄ obeys environment ω̄, and on all other
sites X̄ obeys ω. X̄ is coupled to agree with X̃ until the time
T = inf{n ≥ 0 : X̄n ∈ {Xk : 0 ≤ k <∞}}
it hits the path of X .
The coupling between X̄ and X̃ can be achieved simply as follows. Given ω and
ω̄, for each x create two independent i.i.d. sequences (zxk )k≥1 and (z̄
k)k≥1 with distri-
butions
Qω,ω̄[zxk = y] = πx,x+y(ω) and Q
ω,ω̄[z̄xk = y] = πx,x+y(ω̄).
Do this independently at each x. Each time the X̃-walk visits state x, it uses a new
zxk variable as its next step, and never reuses the same z
k again. The X̄ walk operates
the same way except that it uses the variables z̄xk when x ∈ {Xk} and the zxk variables
when x /∈ {Xk}. Now X̄ and X̃ follow the same steps zxk until X̄ hits the set {Xk}.
It is intuitively obvious that the walksX and X̄ are independent because they never
use the same environment. The following calculation verifies this. Let X0 = x0 = x
36 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
and X̃ = X̄ = y0 = y be the initial states, and Px,y the joint measure created by the
coupling. Fix finite vectors x0,n = (x0, . . . , xn) and y0,n = (y0, . . . , yn) and recall also
the notation X0,n = (X0, . . . , Xn).
The description of the coupling tells us to start as follows.
Px,y[X0,n = x0,n, X̄0,n = y0,n] =
P(dω)
P(dω̄)
P ωx (dz0,∞)1I{z0,n = x0,n}
i:yi /∈{zk : 0≤k<∞}
πyi,yi+1(ω) ·
i:yi∈{zk: 0≤k<∞}
πyi,yi+1(ω̄)
[by dominated convergence]
= lim
P(dω)
P(dω̄)
P ωx (dz0,N) 1I{z0,n = x0,n}
i:yi /∈{zk : 0≤k≤N}
πyi,yi+1(ω) ·
i:yi∈{zk: 0≤k≤N}
πyi,yi+1(ω̄)
= lim
z0,N :z0,n=x0,n
P(dω)P ωx [X0,N = z0,N ]
i:yi /∈{zk: 0≤k≤N}
πyi,yi+1(ω)
P(dω̄)
i:yi∈{zk: 0≤k≤N}
πyi,yi+1(ω̄)
[by independence of the two functions of ω]
= lim
z0,N :z0,n=x0,n
P(dω)P ωx [X0,N = z0,N ]
P(dω)
i:yi/∈{zk : 0≤k≤N}
πyi,yi+1(ω)
P(dω̄)
i:yi∈{zk: 0≤k≤N}
πyi,yi+1(ω̄)
= Px[X0,n = x0,n] · Py[X0,n = y0,n].
Thus at this point the coupled pairs (X, X̃) and (X, X̄) have the desired marginals
Px,y and Px ⊗ Py.
Next construct the common regeneration times (µ1, µ̃1) for (X, X̃) and (ρ1, ρ̄1) for
(X, X̄) by the earlier recipes. Define two pairs of walks stopped at their common
regeneration times:
(Γ, Γ̄) ≡
(X0, µ1 , X̃0, µ̃1), (X0, ρ1 , X̄0, ρ̄1)
. (7.19)
Suppose the sets X[0, µ1∨ρ1) and X̃[0, µ̃1∨ρ̄1) do not intersect. Then the construction
implies that the path X̄0, µ̃1∨ρ̄1 agrees with X̃0, µ̃1∨ρ̄1, and this forces the equalities
(µ1, µ̃1) = (ρ1, ρ̄1) and (Xµ1 , X̃µ̃1) = (Xρ1 , X̄ρ̄1). We insert an estimate on this event.
QUENCHED FUNCTIONAL CLT FOR RWRE 37
Lemma 7.8. There exist constants 0 < C, s < ∞ such that, for all x, y ∈ Vd and
P-a.e. ω,
P ωx,y(X[0, µ1∨ρ1) ∩ X̃[0, µ̃1∨ρ̄1) 6= ∅) ≤ Ce−s|x−y|. (7.20)
Proof. Write
P ωx,y(X[0, µ1∨ρ1) ∩ X̃[0, µ̃1∨ρ̄1) 6= ∅) ≤ P ωx,y(µ1 ∨ µ̃1 ∨ ρ1 ∨ ρ̄1 > ε|x− y|)
+ P ωx ( max
1≤i≤ε|x−y|
|Xi − x| ≥ |x− y|/2)
+ P ωy ( max
1≤i≤ε|x−y|
|Xi − y| ≥ |x− y|/2).
By (7.10) and its analogue for (ρ1, ρ̄1) the first term on the right-hand-side decays
exponentially in |x − y|. Using (3.2) the second and third terms are bounded by
ε|x − y|e−s|x−y|/2eεs|x−y|M , for s > 0 small enough. Choosing ε > 0 small enough
finishes the proof. �
From (7.20) we obtain
(Xµ1 , X̃µ̃1) 6= (Xρ1, X̄ρ̄1)
≤ Px,y
Γ 6= Γ̄
≤ Ce−s|x−y|. (7.21)
But we are not finished yet: it remains to include the conditioning on no back-
tracking. For this purpose generate an i.i.d. sequence (X(m), X̃(m), X̄(m))m≥1, each
triple constructed as above. Continue to write Px,y for the probability measure of
the entire sequence. Let M be the first m such that the paths (X(m), X̃(m)) do not
backtrack, which means that
k · û ≥ X
0 · û and X̃
k · û ≥ X̃
0 · û for all k ≥ 1.
Similarly define M̄ for (X(m), X̄(m))m≥1. M and M̄ are stochastically bounded by
geometric random variables by (3.7).
The pair of walks (X(M), X̃(M)) is now distributed as a pair of walks under the
measure Px,y[ · |β = β̃ = ∞], while (X(M̄), X̄(M̄)) is distributed as a pair of walks
under Px ⊗ Py[ · |β = β̄ = ∞].
Let also again
Γ(m) = (X
0 , µ
0 , µ̃
) and Γ̄(m) = (X
0 , ρ
0 , ρ̄
be the pairs of paths run up to their common regeneration times. Consider the two
pairs of paths (Γ(M), Γ̄(M̄)) chosen by the random indices (M, M̄). We insert one more
lemma.
Lemma 7.9. For s > 0 as above, and a new constant 0 < C <∞,
Γ(M) 6= Γ̄(M̄)
≤ Ce−s|x−y|/2. (7.22)
38 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Proof. Let Am be the event that the walks X̃(m) and X̄(m) agree up to the maximum
1 ∨ ρ̄
1 of their regeneration times. The equalities M = M̄ and Γ
(M) = Γ̄(M̄) are a
consequence of the event A1∩· · ·∩AM , for the following reason. As pointed out earlier,
on the event Am we have the equality of the regeneration times µ̃(m)1 = ρ̄
1 and of the
stopped paths X̃
0 , µ̃
0 , ρ̄
. By definition, these walks do not backtrack after
the regeneration time. Since the walks X̃(m) and X̄(m) agree up to this time, they
must backtrack or fail to backtrack together. If this is true for each m = 1, . . . ,M ,
it forces M̄ = M , since the other factor in deciding M and M̄ are the paths X(m)
that are common to both. And since the paths agree up to the regeneration times,
we have Γ(M) = Γ̄(M̄).
Estimate (7.22) follows:
Γ(M) 6= Γ̄(M̄)
≤ Px,y
Ac1 ∪ · · · ∪ AcM
Px,y[M ≥ m, Acm ] ≤
Px,y[M ≥ m]
)1/2(
Px,y[Acm]
≤ Ce−s|x−y|/2.
The last step comes from the estimate in (7.20) for each Acm and the geometric bound
on M . �
We are ready to finish the proof of Proposition 7.7. To create initial conditions
Y0 = Ȳ0 = x take initial states (X
0 , X̃
0 ) = (X
0 , X̄
0 ) = (0, x). Let the final
outcome of the coupling be the pair
(Y1, Ȳ1) =
− X(M)
− X(M̄)
under the measure P0,x. The marginal distributions of Y1 and Ȳ1 are correct [namely,
given by the transitions (7.13) and (7.16)] because, as argued above, the pairs of
walks themselves have the right marginal distributions. The event Γ(M) = Γ̄(M̄)
implies Y1 = Ȳ1, so estimate (7.22) gives the bound claimed in Proposition 7.7. �
The construction of the Markov chain is complete, and we return to the main
development of the proof. It remains to prove a sublinear bound on the expected
number E0,0|X[0,n)∩ X̃[0,n)| of common points of two independent walks in a common
environment. Utilizing the common regeneration times, write
E0,0|X[0,n) ∩ X̃[0,n)| ≤
E0,0|X[µi,µi+1) ∩ X̃[µ̃i,µ̃i+1)|. (7.23)
The term i = 0 is a finite constant by bound (7.10) because the number of common
points is bounded by the number µ1 of steps. For each 0 < i < n apply a decom-
position into pairs of paths from (0, 0) to given points (x1, y1) in the style of (7.17):
QUENCHED FUNCTIONAL CLT FOR RWRE 39
(γ, γ̃) are the pairs of paths with the property that
(γ,γ̃)
{X0,n(γ) = γ, X̃0,n(γ̃) = γ̃, β ◦ θn(γ) = β̃ ◦ θn(γ̃) = ∞}
= {X0 = X̃0 = 0, Xµi = x1, X̃µ̃i = y1}.
Each term i > 0 in (7.23) we rearrange as follows.
E0,0|X[µi,µi+1) ∩ X̃[µ̃i,µ̃i+1)|
x1,y1
(γ,γ̃)
EP ω0,0[X0,n(γ) = γ, X̃0,n(γ̃) = γ̃]
×Eωx1,y1(1I{β = β̃ = ∞}|X[0 , µ1) ∩ X̃[0 , µ̃1)| )
x1,y1
(γ,γ̃)
EP ω0,0[X0,n(γ) = γ, X̃0,n(γ̃) = γ̃]P
x1,y1
[β = β̃ = ∞]
×Eωx1,y1( |X[0 , µ1) ∩ X̃[0 , µ̃1)| | β = β̃ = ∞ )
x1,y1
EP ω0,0[Xµi = x1, X̃µ̃i = y1]E
x1,y1
( |X[0 , µ1) ∩ X̃[0 , µ̃1)| | β = β̃ = ∞ ).
The last conditional quenched expectation above is handled by estimates (3.7), (7.10),
(7.20) and Schwarz inequality:
Eωx1,y1( |X[0 , µ1) ∩ X̃[0 , µ̃1)| | β = β̃ = ∞ ) ≤ η
−2Eωx1,y1( |X[0 , µ1) ∩ X̃[0 , µ̃1)| )
≤ η−2Eωx1,y1(µ1 · 1I{X[0 , µ1) ∩ X̃[0 , µ̃1) 6= ∅} )
≤ η−2
Eωx1,y1[µ
)1/2(
P ωx1,y1{X[0 , µ1) ∩ X̃[0 , µ̃1) 6= ∅}
≤ Ce−s|x1−y1|/2.
Define h(x) = Ce−s|x|/2, insert the last bound back up, and appeal to the Markov
property established in Proposition 7.4:
E0,0|X[µi,µi+1) ∩ X̃[µ̃i,µ̃i+1)| ≤ E0,0
h(X̃µ̃i −Xµi)
P0,0[X̃µ̃1 −Xµ1 = x]
qi−1(x, y)h(y).
In order to apply Theorem A.1 from the Appendix, we check its hypotheses in the
next lemma. Assumption (1.2) enters here for the first and only time.
Lemma 7.10. The Markov chain (Yk)k≥0 with transition q(x, y) and the symmet-
ric random walk (Ȳk)k≥0 with transition q̄(x, y) satisfy assumptions (A.i), (A.ii) and
(A.iii) stated in the beginning of the Appendix.
Proof. From Lemma 7.3 and (3.2) we get moment bounds
E0,x|X̄ρ̄k |m + E0,x|Xρk |m <∞
40 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
for any power m < ∞. This gives assumption (A.i), namely that E0|Ȳ1|3 < ∞. The
second part of assumption (A.ii) comes from Lemma 7.6. Assumption (A.iii) comes
from Proposition 7.7.
The only part that needs work is the first part of assumption (A.ii). We show
that it follows from part (1.2) of Hypothesis (R). By (1.2) and non-nestling (N) there
exist two non-zero vectors y 6= z such that z · û > 0 and Eπ0,yπ0,z > 0. Now we have
a number of cases to consider. In each case we should describe an event that gives
Y1−Y0 a particular nonzero value and whose probability is bounded away from zero,
uniformly over x = Y0.
Case 1: y is noncollinear with z. The sign of y · û gives three subcases. We do
the trickiest one explicitly. Assume y · û < 0. Find the smallest positive integer b
such that (y + bz) · û > 0. Then find the minimal positive integers k,m such that
k(y + bz) · û = mz · û. Below Px is the path measure of the Markov chain (Yk) and
then P0,x the measure of the walks (X, X̃) as before.
Px{Y1 − Y0 = ky + (kb−m)z}
≥ P0,x
X̃µ̃1 = x+ ky + (k + 1)bz , Xµ1 = (m+ b)z , β = β̃ = ∞
P Txω0 {Xi(b+1)+1 = i(y + bz) + z, . . . , Xi(b+1)+b = i(y + bz) + bz,
X(i+1)(b+1) = (i+ 1)(y + bz) for 0 ≤ i ≤ k − 1, and then
Xk(b+1)+1 = k(y + bz) + z , . . . , Xk(b+1)+b = k(y + bz) + bz }
× P ω0 {X1 = z , X2 = 2z , . . . , Xm+b = (m+ b)z }
× P ωx+ky+(k+1)bz{β = ∞}P ω(m+b)z{β = ∞}
Regardless of possible intersections of the paths, assumption (1.2) and inequality (3.7)
imply that the quantity above has a positive lower bound that is independent of x.
The assumption that y, z are nonzero and noncollinear ensures that ky+(kb−m)z 6= 0.
Case 2: y is collinear with z. Then there is a vector w 6∈ Rz such that Eπ0,w > 0. If
w · û ≤ 0, then by Hypothesis (N) there exists u such that u · û > 0 and Eπ0,wπ0,u > 0.
If u is collinear with z, then replacing z by u and y by w puts us back in Case 1. So,
replacing w by u if necessary, we can assume that w · û > 0. We have four subcases,
depending on whether x = 0 or not and y · û < 0 or not.
(2.a) The case x 6= 0 is resolved simply by taking paths consisting of only w-steps
for one walk and only z-steps for the other, until they meet on a common level and
then never backtrack.
(2.b) The case y · û > 0 corresponds to Case 3 in the proof of [11, Lemma 5.5].
(2.c) The only case left is x = 0 and y · û < 0. Let b and c be the smallest positive
integers such that (y + bw) · û ≥ 0 and (y + cz) · û > 0. Choose minimal positive
QUENCHED FUNCTIONAL CLT FOR RWRE 41
integeres m ≥ b and n > c such that m(w · û) = n(z · û). Then,
P0{Y1 − Y0 = nz −mw}
≥ P0,0{X̃µ̃1 = y + bw + nz,Xµ1 = y + (b+m)w}
P ω0 {Xi = iw for 1 ≤ i ≤ b and Xb+1+j = y + (b+ j)w for 0 ≤ j ≤ m}
× P ω0 {Xi = iw for 0 ≤ i ≤ b,Xb+1 = bw + z and then
Xb+1+j = y + bw + jz for 1 ≤ j ≤ n}
× P ωy+(b+m)w(β = ∞)P ωy+bw+nz(β = ∞)
Since w and z are noncollinear, mw 6= nz. For the same reason, w-steps are always
taken at points not visited before. This makes the above lower bound positive. By
the choice of b and z · û > 0, neither walk dips below level 0.
We can see that the first common regeneration level for the two paths is (y+ bw+
nz)·û. The first walk backtracks from level bw ·û so this is not a common regeneration
level. The second walk splits from the first walk at bw, takes a z-step up, and then
backtracks using a y-step. So the common regeneration level can only be at or above
level (y+ bw+(c+1)z) · û. The fact that n > c ensures that (y+ bw+nz) · û is high
enough. The minimality of n ensures that this is the first such level. �
Now that the assumptions have been checked, Theorem A.1 gives constants 0 <
C <∞ and 0 < η < 1 such that
qi−1(x, y)h(y) ≤ Cn1−η for all x ∈ Vd and n ≥ 1.
Going back to (7.23) and collecting the bounds along the way gives the final estimate
E0,0|X[0,n) ∩ X̃[0,n)| ≤ Cn1−η
for all n ≥ 1. This is (6.2) which was earlier shown to imply condition (2.1) required
by Theorem 2.1. Previous work in Sections 2 and 5 convert the CLT from Theorem
2.1 into the main result Theorem 1.1. The entire proof is complete, except for the
Green function estimate furnished by the Appendix.
Appendix A. A Green function type bound
Let us write a d-vector in terms of coordinates as x = (x1, . . . , xd), and similarly
for random vectors X = (X1, . . . , Xd).
Let Y = (Yk)k≥0 be a Markov chain on Z
d with transition probability q(x, y),
and let Ȳ = (Ȳk)k≥0 be a symmetric random walk on Z
d with transition probability
q̄(x, y) = q̄(y, x) = q̄(0, y − x). Make the following assumptions.
(A.i) A third moment bound E0|Ȳ1|3 <∞.
42 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
(A.ii) Some uniform nondegeneracy: there is at least one index j ∈ {1, . . . , d} and
a constant κ0 such that the coordinate Y
j satisfies
Px{Y j1 − Y
0 ≥ 1} ≥ κ0 > 0 for all x. (A.1)
(The inequality ≥ 1 can be replaced by ≤ −1, the point is to assure that a cube is
exited fast enough.) Furthermore, for every i ∈ {1, . . . , d}, if the one-dimensional
random walk Ȳ i is degenerate in the sense that q̄(0, y) = 0 for yi 6= 0, then so is
the process Y i in the sense that q(x, y) = 0 whenever xi 6= yi. In other words, any
coordinate that can move in the Y chain somewhere in space can also move in the Ȳ
walk.
(A.iii) Most importantly, assume that for any initial state x the transitions q and
q̄ can be coupled so that
Px,x[Y1 6= Ȳ1] ≤ Ce−α1|x|
where 0 < C, α1 <∞ are constants independent of x.
Throughout the section C will change value but α1 remains the constant in the
assumption above. Let h be a function on Zd such that 0 ≤ h(x) ≤ Ce−α2|x| for
constants 0 < α2, C < ∞. This section is devoted to proving the following Green
function type bound on the Markov chain.
Theorem A.1. There are constants 0 < C, η <∞ such that
Ezh(Yk) =
P0(Yk = y) ≤ Cn1−η for all n ≥ 1 and z ∈ Zd.
To prove the estimate, we begin by discarding terms outside a cube of side r =
c1 logn. Bounding probabilities crudely by 1 gives
|y|>c1 logn
Pz(Yk = y) ≤ n
|y|>c1 logn
h(y) ≤ Cn
k>c1 logn
kd−1e−α2k
k>c1 logn
e−(α2/2)k ≤ Cne−(α2/2)c1 logn ≤ Cn1−η
as long as n is large enough so that kd−1 ≤ eα2k/2, and this works for any c1.
B = [−c1 log n, c1 log n]d.
Since h is bounded, it now remains to show that
Pz(Yk ∈ B) ≤ Cn1−η. (A.2)
For this we can assume z ∈ B since accounting for the time to enter B for the first
time can only improve the estimate.
QUENCHED FUNCTIONAL CLT FOR RWRE 43
Bound (A.2) will be achieved in two stages. First we show that the Markov chain Y
does not stay in B longer than a time whose mean is a power of the size of B. Second,
we show that often enough Y follows the random walk Ȳ during its excursions outside
B. The random walk excursions are long and thereby we obtain (A.2). Thus our first
task is to construct a suitable coupling of Y and Ȳ .
Lemma A.1. Let ζ = inf{n ≥ 1 : Ȳ ∈ A} be the first entrance time of Ȳ into some
set A ⊆ Zd. Then we can couple Y and Ȳ so that
Px,x[ Yk 6= Ȳk for some 1 ≤ k ≤ ζ ] ≤ CEx
e−α1|Ȳk|.
The proof shows that the statement works also if ζ = ∞ is possible, but we will
not need this case.
Proof. For each state x create an i.i.d. sequence (Zxk , Z̄
k )k≥1 such that Z
k has distri-
bution q(x, x+ · ), Z̄xk has distribution q̄(x, x+ · ) = q̄(0, · ), and each pair (Zxk , Z̄xk )
is coupled so that P (Zxk 6= Z̄xk ) ≤ Ce−α1|x|. For distinct x these sequences are inde-
pendent.
Construct the process (Yn, Ȳn) as follows: with counting measures
Ln(x) =
1I{Yk = x} and L̄n(x) =
1I{Ȳk = x} (n ≥ 0)
and with initial point (Y0, Ȳ0) given, define for n ≥ 1
Yn = Yn−1 + Z
Ln−1(Yn−1)
and Ȳn = Ȳn−1 + Z̄
Ȳn−1
L̄n−1(Ȳn−1)
In words, every time the chain Y visits a state x, it reads its next jump from a new
variable Zxk which is then discarded and never used again. And similarly for Ȳ . This
construction has the property that, if Yk = Ȳk for 0 ≤ k ≤ n with Yn = Ȳn = x, then
the next joint step is (Zxk , Z̄
k ) for k = Ln(x) = L̄n(x). In other words, given that the
processes agree up to the present and reside together at x, the probability that they
separate in the next step is bounded by Ce−α1|x|.
44 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Now follow self-evident steps.
Px,x[ Yk 6= Ȳk for some 1 ≤ k ≤ ζ ]
Px,x[ Yj = Ȳj ∈ Ac for 1 ≤ j < k, Yk 6= Ȳk ]
1I{ Yj = Ȳj ∈ Ac for 1 ≤ j < k }PYk−1,Ȳk−1(Y1 6= Ȳ1)
1I{ Yj = Ȳj ∈ Ac for 1 ≤ j < k }e−α1|Ȳk−1|
≤ CEx
e−α1|Ȳm|. �
For the remainder of this section Y and Ȳ are always coupled in the manner that
satisfies Lemma A.1.
Lemma A.2. Let j ∈ {1, . . . , d} be such that the one-dimensional random walk Ȳ j is
not degenerate. Let r0 be a positive integer and w̄ = inf{n ≥ 1 : Ȳ jn ≤ r0} the first
time the random walk Ȳ enters the half-space H = {x : xj ≤ r0}. Couple Y and Ȳ
starting from a common initial state x /∈ H. Then there is a constant C independent
of r0 such that
Px,x[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ] ≤ Ce−α1r0 for all r0 ≥ 1.
The same result holds for H = {x : xj ≥ −r0}.
Proof. By Lemma A.1
Px,x[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ] ≤ CEx
[ w̄−1∑
e−α1|Ȳk|
≤ CExj
[ w̄−1∑
e−α1Ȳ
t=r0+1
e−α1tg(xj, t)
where for s, t ∈ [r0 + 1,∞)
g(s, t) =
Ps[Ȳ
n = t , w̄ > n]
is the Green function of the half-line (−∞, r0] for the one-dimensional random walk
Ȳ j. This is the expected number of visits to t before entering (−∞, r0], defined on
p. 209 in Spitzer [13]. The development in Sections 18 and 19 in [13] gives the bound
g(s, t) ≤ C(1 + (s− r0 − 1) ∧ (t− r0 − 1)) ≤ C(t− r0), s, t ∈ [r0 + 1,∞). (A.3)
QUENCHED FUNCTIONAL CLT FOR RWRE 45
Here is some more detail. Shift r0 + 1 to the origin to match the setting in [13].
Then P19.3 on p. 209 gives
g(x, y) =
u(x− n)v(y − n) for x, y > 0
where the functions u and v are defined on p. 201. For a symmetric random walk
u = v. P18.7 on p. 202 implies that
v(m) =
P[Z1 + · · ·+ Zk = m]
where c is a certain constant and {Zi} are i.i.d. strictly positive, integer-valued ladder
variables for the underlying random walk. Now one can show inductively that v(m) ≤
v(0) for each m so the quantities u(m) = v(m) are bounded. This justifies (A.3).
Continuing from further above we get the estimate claimed in the statement:
[ w̄−1∑
e−α1|Ȳk|
(t− r0)e−α1t ≤ Ce−α1r0. �
For the next lemmas abbreviate Br = [−r, r]d for d-dimensional centered cubes.
Lemma A.3. With α1 given in the coupling hypothesis (A.iii), fix any positive constant
κ1 > 2α
1 . Consider large positive integers r0 and r that satisfy
2α−11 log r ≤ r0 ≤ κ1 log r < r.
Then there exist a positive integer m0 and a constant 0 < α3 <∞ such that, for large
enough r,
x∈BrrBr0
Px[without entering Br0 chain Y exits Br by time r
m0 ] ≥ α3
. (A.4)
Proof. We consider first the case where x ∈ BrrBr0 has a coordinate xj that satisfies
xj ∈ [−r,−r0 − 1] ∪ [r0 + 1, r] and Ȳ j is nondegenerate. For this case we can take
m0 = 4. A higher m0 may be needed to move a suitable coordinate out of the interval
[−r0, r0]. This is done in the second step of the proof.
The same argument works for both xj ∈ [−r,−r0−1] and xj ∈ [r0+1, r]. We treat
the case xj ∈ [r0 + 1, r]. One way to realize the event in (A.4) is this: starting at xj ,
the Ȳ j walk exits [r0 + 1, r] by time r
4 through the right boundary into [r + 1,∞),
and Y and Ȳ stay coupled together throughout this time. Let ζ̄ be the time Ȳ j exits
[r0+1, r] and w̄ the time Ȳ
j enters (−∞, r0]. Then w̄ ≥ ζ̄. Thus the complementary
probability of (A.4) is bounded by
Pxj{ Ȳ j exits [r0 + 1, r] into (−∞, r0] }
+ Pxj{ζ̄ > r4} + Px,x{ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} }.
(A.5)
46 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
We treat the terms one at a time. From the development on p. 253-255 in [13] we
get the bound
Pxj{ Ȳ j exits [r0 + 1, r] into (−∞, r0] } ≤ 1−
(A.6)
for some constant α4 > 0. In some more detail: P22.7 on p. 253, the inequality in
the third display of p. 255, and the third moment assumption on the steps of Ȳ give
a lower bound
Pxj{ Ȳ j exits [r0 + 1, r] into [r + 1,∞) } ≥
xj − r0 − 1− c1
r − r0 − 1
(A.7)
for the probability of exiting to the right. Here c1 is a constant that comes from
the term denoted in [13] by M
s=0(1 + s)a(s) whose finiteness follows from the
third moment assumption. The text on p. 254-255 suggests that these steps need the
aperiodicity assumption. This need for aperiodicity can be traced back via P22.5 to
P22.4 which is used to assert the boundedness of u(x) and v(x). But as we observed
above in the derivation of (A.3) boundedness of u(x) and v(x) is true without any
additional assumptions.
To go forward from (A.7) fix any m > c1 so that the numerator above is positive
for xj = r0 + 1 +m. The probability in (A.7) is minimized at x
j = r0 + 1, and from
xj = r0 + 1 there is a fixed positive probability θ to take m steps to the right to get
past the point xj = r0 + 1 +m. Thus for all x
j ∈ [r0 + 1, r] we get the lower bound
Pxj{ Ȳ j exits [r0 + 1, r] into [r + 1,∞) } ≥
θ(m− c1)
r − r0 − 1
and (A.6) is verified.
As in (A.3) let g(s, t) be the Green function of the random walk Ȳ j for the half-
line (−∞, r0], and let g̃(s, t) be the Green function for the complement of the interval
[r0 + 1, r]. Then g̃(s, t) ≤ g(s, t), and by (A.3) we get this moment bound:
Exj [ ζ̄ ] =
t=r0+1
g̃(xj , t) ≤
t=r0+1
g(xj, t) ≤ Cr2.
Consequently, uniformly over xj ∈ [r0 + 1, r],
Pxj [ζ̄ > r
4] ≤ C
. (A.8)
From Lemma A.2
Px[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ] ≤ Ce−α1r0 . (A.9)
Putting bounds (A.6), (A.8) and (A.9) together gives an upper bound of
1 − α4
+ Ce−α1r0
QUENCHED FUNCTIONAL CLT FOR RWRE 47
for the sum in (A.5) which bounds the complement of the probability in (A.4). By
assumption r0 > 2α
1 log r, so for large enough r the sum above is not more than
1− α3/r for some constant α3 > 0.
The lemma is now proved for those x ∈ Br r Br0 for which some
j ∈ J ≡ {1 ≤ j ≤ d : the one-dimensional walk Ȳ j is nondegenerate}
satisfies xj ∈ [−r,−r0 − 1] ∪ [r0 + 1, r]. Now suppose x ∈ Br r Br0 but all j ∈ J
satisfy xj ∈ [−r0, r0]. Let
T = inf{n ≥ 1 : Y jn /∈ [−r0, r0] for some j ∈ J}.
The first part of the proof gives Px-almost surely
PYT [without entering Br0 chain Y exits Br by time r
4/2] ≥ α3
Replacing r4 by r4/2 only affects the constant in (A.8). It can of course happen that
YT /∈ Br but then we interpret the above probability as one.
By the Markov property it remains to show that for a suitable m0
Px[T ≤ rm0/2] : x ∈ Br r Br0 but xj ∈ [−r0, r0] for all j ∈ J
(A.10)
is bounded below by a positive constant. Hypothesis (A.1) implies that for some
constant b1, ExT ≤ br01 uniformly over the relevant x. This is because one way to
realize T is to wait until some coordinate Y j takes 2r0 successive identical steps.
By hypothesis (A.1) this random time is stochastically bounded by a geometrically
distributed random variable.
It is also necessary for this argument that during time [0, T ] the chain Y does not
enter Br0. Indeed, under the present assumptions the chain never enters Br0 . This is
because for x ∈ BrrBr0 some coordinate i must satisfy xi ∈ [−r,−r0−1]∪ [r0+1, r].
But now this coordinate i /∈ J , and so by hypothesis (A.ii) the one-dimensional
process Y i is constant, Y in = x
i /∈ [−r0, r0] for all n.
Finally, the required positive lower bound for (A.10) comes by Chebychev. Take
m0 ≥ κ1 log b1 +1 where κ1 comes from the assumptions of the lemma. Then, by the
hypothesis r0 ≤ κ1 log r,
Px[T > r
m0/2] ≤ 2r−m0br01 ≤ 2rκ1 log b1−m0 ≤ 12
for r ≥ 4. �
We come to one of the main auxiliary lemmas of this development.
Lemma A.4. Let U = inf{n ≥ 0 : Yn /∈ Br} be the first exit time from Br for the
Markov chain Y . Then there exist finite positive constants C1, m1 such that
Ex(U) ≤ C1rm1 for all 1 ≤ r <∞.
48 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Proof. First observe that supx∈Br Ex(U) < ∞ by assumption (A.1) because by a
geometric time some coordinate Y j has experienced 2r identical steps in succession.
Throughout, let r0 < r satisfy the assumptions of Lemma A.3. Once the statement
is proved for large enough r, we obtain it for all r ≥ 1 by increasing C1.
Let 0 = T0 = S0 ≤ T1 ≤ S1 ≤ T2 ≤ · · · be the successive exit and entrance times
into Br0 . Precisely, for i ≥ 1 as long as Si−1 <∞
Ti = inf{n ≥ Si−1 : Yn /∈ Br0} and Si = inf{n ≥ Ti : Yn ∈ Br0}
Once Si = ∞ then we set Tj = Sj = ∞ for all j > i. If Y0 ∈ Br r Br0 then also
T1 = 0. Again by assumption (A.1) (and as observed in the proof of Lemma A.3)
there is a constant 0 < b1 <∞ such that
x∈Br0
Ex[T1] ≤ br01 . (A.11)
So a priori T1 is finite but S1 = ∞ is possible. Since T1 ≤ U <∞ we can decompose
as follows:
Ex[U ] =
Ex[U, Tj ≤ U < Sj ]
Ex[Tj , Tj ≤ U < Sj] +
Ex[U − Tj , Tj ≤ U < Sj].
(A.12)
We first treat the last sum in (A.12). By an inductive application of Lemma A.3,
for any z ∈ Br rBr0 ,
Pz[U > jr
m0 , U < S1] ≤ Pz[ Yk ∈ Br r Br0 for k ≤ jrm0 ]
1I{ Yk ∈ Br r Br0 for k ≤ (j − 1)rm0 }PY(j−1)rm0 { Yk ∈ Br r Br0 for k ≤ r
≤ · · · ≤ (1− α3r−1)j .
Utilizing this, still for z ∈ Br r Br0 ,
Ez[U, U < S1] =
Pz[U > m , U < S1]
≤ rm0
Pz[U > jr
m0 , U < S1] ≤ rm0+1α−13 .
(A.13)
Next we take into consideration the failure to exit Br during the earlier excursions
in Br rBr0 . Let
Hi = {Yn ∈ Br for Ti ≤ n < Si}
be the event that in between the ith exit from Br0 and entrance back into Br0 the
chain Y does not exit Br. We shall repeatedly use this consequence of Lemma A.3:
for i ≥ 1, on the event {Ti <∞}, Px[Hi | FTi] ≤ 1− α3r−1. (A.14)
QUENCHED FUNCTIONAL CLT FOR RWRE 49
Here is the first instance.
Ex[U − Tj , Tj ≤ U < Sj ] = Ex
[ j−1∏
1IHk · 1I{Tj <∞} · EYTj (U, U < S1)
≤ rm0+1α−13 Ex
[ j−1∏
1IHk · 1I{Tj−1 <∞}
≤ rm0+1α−13 (1− α3r−1)j−1.
Note that if YTj above lies outside Br then EYTj (U) = 0. In the other case YTj ∈
Br rBr0 and (A.13) applies. So for the last sum in (A.12):
Ex[U − Tj , Tj ≤ U < Sj] ≤
rm0+1α−13 (1− α3r−1)j−1 ≤ rm0+2α−23 . (A.15)
We turn to the second-last sum in (A.12). Utilizing (A.11) and (A.14),
Ex[Tj , Tj ≤ U < Sj] ≤
[ j−1∏
1IHk · 1I{Tj <∞} · (Ti+1 − Ti)
≤ br01 (1− α3r−1)j−1
[ i−1∏
1IHk · (Ti+1 − Ti)1IHi · 1I{Ti+1 <∞}
(1− α3r−1)j−1−i.
(A.16)
Split the last expectation as
[ i−1∏
1IHk · (Ti+1 − Ti)1IHi · 1I{Ti+1 <∞}
[ i−1∏
1IHk · (Ti+1 − Si)1IHi · 1I{Si <∞}
[ i−1∏
1IHk · (Si − Ti)1IHi · 1I{Ti <∞}
[ i−1∏
1IHk · 1I{Si <∞} · EYSi (T1)
[ i−1∏
1IHk · 1I{Ti <∞} ·EYTi (S1 · 1IH1)
[ i−1∏
1IHk · 1I{Ti−1 <∞}
(br01 + r
m0+1α−13 )
≤ (1− α3r−1)i−1(br01 + rm0+1α−13 ). (A.17)
In the second-last inequality above, before applying (A.14) to theHk’s, EYSi (T1) ≤ b
comes from (A.11). The other expectation is estimated again by iterating Lemma
50 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
A.3 and again with z ∈ Br rBr0 :
Ez(S1 · 1IH1) =
Pz[S1 > m , H1] ≤
Pz[ Yk ∈ Br rBr0 for k ≤ m ]
≤ rm0
Pz[ Yk ∈ Br r Br0 for k ≤ jrm0 ] ≤ rm0+1α−13 .
Insert the bound from line (A.17) back up into (A.16) to get the bound
Ex[Tj , Tj ≤ U < Sj] ≤ (2br01 + rm0+1α−13 )j(1− α3r−1)j−2.
Finally, bound the second-last sum in (A.12):
Ex[Tj , Tj ≤ U < Sj] ≤
2br01 r
2α−23 + r
m0+3α−33
(1− α3r−1)−1.
Taking r large enough so that α3r
−1 < 1/2 and combining this with (A.12) and
(A.15) gives
Ex[U ] ≤ rm0+2α−21 + 4br01 r2α−23 + 2rm0+3α−33 .
Since r0 ≤ κ1 log r for some constant C, the above bound simplifies to C1rm1 . �
For the remainder of the proof we work with B = Br for r = c1 log n. The above
estimate gives us one part of the argument for (A.2), namely that the Markov chain
Y exits B = [−c1 log n, c1 logn]d fast enough.
Let 0 = V0 < U1 < V1 < U2 < V2 < · · · be the successive entrance times Vi into B
and exit times Ui from B for the Markov chain Y , assuming that Y0 = z ∈ B. It is
possible that some Vi = ∞. But if Vi < ∞ then also Ui+1 < ∞ due to assumption
(A.1), as already observed. The time intervals spent in B are [Vi, Ui+1) each of length
at least 1. Thus, by applying Lemma A.4,
Pz(Yk ∈ B) ≤
(Ui+1 − Vi)1I{Vi ≤ n}
EYVi (U1)1I{Vi ≤ n}
≤ C(logn)m1Ez
1I{Vi ≤ n}
(A.18)
QUENCHED FUNCTIONAL CLT FOR RWRE 51
Next we bound the expected number of returns to B by the number of excursions
outside B that fit in a time of length n:
1I{Vi ≤ n}
(Vj − Vj−1) ≤ n
(Vj − Uj) ≤ n
(A.19)
According to the usual notion of stochastic dominance, the random vector (ξ1, . . . , ξn)
dominates (η1, . . . , ηn) if
Ef(ξ1, . . . , ξn) ≥ Ef(η1, . . . , ηn)
for any function f that is coordinatewise nondecreasing. If the {ξi : 1 ≤ i ≤ n} are
adapted to the filtration {Gi : 1 ≤ i ≤ n}, and P [ξi > a|Gi−1] ≥ 1 − F (a) for some
distribution function F , then the {ηi} can be taken i.i.d. F -distributed.
Lemma A.5. There exist positive constants c1, c2 and γ such that the following holds:
the excursion lengths {Vj − Uj : 1 ≤ j ≤ n} stochastically dominate i.i.d. variables
{ηj} whose common distribution satisfies P[η ≥ a] ≥ c1a−1/2 for 1 ≤ a ≤ c2nγ.
Proof. Since Pz[Vj − Uj ≥ a|FUj ] = PYUj [V ≥ a] where V means first entrance time
into B, we shall bound Px[V ≥ a] below uniformly over
x /∈ B :
Pz[YU1 = x] > 0
Fix such an x and an index 1 ≤ j ≤ d such that xj /∈ [−r, r]. Since the coordinate Y j
can move out of [−r, r], this coordinate is not degenerate, and hence by assumption
(A.ii) the random walk Ȳ j is nondegenerate. As before we work through the case
xj > r because the argument for the other case xj < −r is the same.
Let w̄ = inf{n ≥ 1 : Ȳ jn ≤ r} be the first time the one-dimensional random walk
Ȳ j enters the half-line (−∞, r]. If both Y and Ȳ start at x and stay coupled together
until time w̄, then V ≥ w̄. This way we bound V from below. Since the random
walk is symmetric and can be translated, we can move the origin to xj and use classic
results about the first entrance time into the left half-line, T̄ = inf{n ≥ 1 : Ȳ jn < 0}.
Pxj [w̄ ≥ a] ≥ Pr+1[w̄ ≥ a] = P0[T̄ ≥ a] ≥
for a constant α5. The last inequality follows for one-dimensional symmetric walks
from basic random walk theory. For example, combine equation (7) on p. 185 of [13]
with a Tauberian theorem such as Theorem 5 on p. 447 of Feller [7]. Or see directly
Theorem 1a on p. 415 of [7].
52 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Now start both Y and Ȳ from x. Apply Lemma A.2 and recall that r = c1 log n.
Px[V ≥ a] ≥ Px,x[V ≥ a, Yk = Ȳk for k = 1, . . . , w̄ ]
≥ Px,x[w̄ ≥ a, Yk = Ȳk for k = 1, . . . , w̄ ]
≥ Pxj [w̄ ≥ a]− Px,x[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ]
≥ α5√
− Cn−c1α1 .
This gives a lower bound
Px[V ≥ a] ≥
if a ≤ α25(2C)−2n2c1α1 . This lower bound is independent of x. We have proved the
lemma. �
We can assume that the random variables ηj given by the lemma satisfy 1 ≤ ηj ≤
γ and we can assume both c2, γ ≤ 1 because this merely weakens the result. For
the renewal process determined by {ηj} write
S0 = 0 , Sk =
ηj , and K(n) = inf{k : Sk > n}
for the renewal times and the number of renewals up to time n (counting the renewal
S0 = 0). Since the random variables are bounded, Wald’s identity gives
EK(n) · Eη = ESK(n) ≤ n+ c2nγ ≤ 2n,
while
∫ c2nγ
ds ≥ c3nγ/2.
Together these give
EK(n) ≤ 2n
≤ C2n1−γ/2.
Now we pick up the development from line (A.19). Since the negative of the
function of (Vj − Uj)1≤i≤n in the expectation on line (A.19) is nondecreasing, the
stochastic domination of Lemma A.5 gives an upper bound of (A.19) in terms of the
i.i.d. {ηj}. Then we use the renewal bound from above.
1I{Vi ≤ n}
(Vj − Uj) ≤ n
ηj ≤ n
= EK(n) ≤ C2n1−γ/2.
QUENCHED FUNCTIONAL CLT FOR RWRE 53
Returning back to (A.18) to collect the bounds, we have shown that
Pz(Yk ∈ B) ≤ C(logn)m1Ez
1I{Vi ≤ n}
≤ C(logn)m1C2n1−γ/2
and thereby verified (A.2).
References
[1] N. Berger and O. Zeitouni. A quenched invariance principle for certain ballistic
random walks in i.i.d. environments.
http://front.math.ucdavis.edu/math.PR/0702306.
[2] E. Bolthausen and A.-S. Sznitman. On the static and dynamic points of view for
certain random walks in random environment. Methods Appl. Anal., 9(3):345–
375, 2002. Special issue dedicated to Daniel W. Stroock and Srinivasa S. R.
Varadhan on the occasion of their 60th birthday.
[3] E. Bolthausen and A.-S. Sznitman. Ten lectures on random media, volume 32 of
DMV Seminar. Birkhäuser Verlag, Basel, 2002.
[4] J. Bricmont and A. Kupiainen. Random walks in asymmetric random environ-
ments. Comm. Math. Phys., 142(2):345–420, 1991.
[5] Y. Derriennic and M. Lin. The central limit theorem for Markov chains started
at a point. Probab. Theory Related Fields, 125(1):73–76, 2003.
[6] S. N. Ethier and T. G. Kurtz. Markov processes. Wiley Series in Probability and
Mathematical Statistics: Probability and Mathematical Statistics. John Wiley
& Sons Inc., New York, 1986. Characterization and convergence.
[7] W. Feller. An introduction to probability theory and its applications. Vol. II.
Second edition. John Wiley & Sons Inc., New York, 1971.
[8] M. Maxwell and M. Woodroofe. Central limit theorems for additive functionals
of Markov chains. Ann. Probab., 28(2):713–724, 2000.
[9] F. Rassoul-Agha and T. Seppäläinen. An almost sure invariance principle for
random walks in a space-time random environment. Probab. Theory Related
Fields, 133(3):299–314, 2005.
[10] F. Rassoul-Agha and T. Seppäläinen. Ballistic random walk in a random en-
vironment with a forbidden direction. ALEA Lat. Am. J. Probab. Math. Stat.,
1:111–147 (electronic), 2006.
[11] F. Rassoul-Agha and T. Seppäläinen. Quenched invariance principle for multi-
dimensional ballistic random walk in a random environment with a forbidden
direction. Ann. Probab., 35(1):1–31, 2007.
[12] M. Rosenblatt. Markov processes. Structure and asymptotic behavior. Springer-
Verlag, New York, 1971. Die Grundlehren der mathematischen Wissenschaften,
Band 184.
[13] F. Spitzer. Principles of random walks. Springer-Verlag, New York, second
edition, 1976. Graduate Texts in Mathematics, Vol. 34.
54 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
[14] A.-S. Sznitman. Slowdown estimates and central limit theorem for random walks
in random environment. J. Eur. Math. Soc. (JEMS), 2(2):93–143, 2000.
[15] A.-S. Sznitman. Topics in random walks in random environment. In School
and Conference on Probability Theory, ICTP Lect. Notes, XVII, pages 203–266
(electronic). Abdus Salam Int. Cent. Theoret. Phys., Trieste, 2004.
[16] A.-S. Sznitman and O. Zeitouni. An invariance principle for isotropic diffusions
in random environment. Invent. Math., 164(3):455–567, 2006.
[17] A.-S. Sznitman and M. Zerner. A law of large numbers for random walks in
random environment. Ann. Probab., 27(4):1851–1869, 1999.
[18] O. Zeitouni. Random walks in random environments, volume 1837 of Lecture
Notes in Mathematics. Springer-Verlag, Berlin, 2004. Lectures from the 31st
Summer School on Probability Theory held in Saint-Flour, July 8–25, 2001,
Edited by Jean Picard.
[19] M. P. W. Zerner. Lyapounov exponents and quenched large deviations for mul-
tidimensional random walk in random environment. Ann. Probab., 26(4):1446–
1476, 1998.
F. Rassoul-Agha, 155 S 1400 E, Salt Lake City, UT 84112
E-mail address : firas@math.utah.edu
URL: www.math.utah.edu/∼firas
T. Seppäläinen, 419 Van Vleck Hall, Madison, WI 53706
E-mail address : seppalai@math.wisc.edu
URL: www.math.wisc.edu/∼seppalai
	1. Introduction and main result
	2. Preliminaries for the proof.
	3. Basic estimates for non-nestling RWRE
	4. Invariant measure and ergodicity
	5. Change of measure
	6. Reduction to path intersections
	7. Bound on intersections
	Appendix A. A Green function type bound
	References

  We consider a non-nestling random walk in a product random environment. We
assume an exponential moment for the step of the walk, uniformly in the
environment. We prove an invariance principle (functional central limit
theorem) under almost every environment for the centered and diffusively scaled
walk. The main point behind the invariance principle is that the quenched mean
of the walk behaves subdiffusively.

Introduction and main result
We prove a quenched functional central limit theorem for non-nestling random walk
in random environment (RWRE) on the d-dimensional integer lattice Zd in dimensions
d ≥ 2. Here is a general description of the model, fairly standard since quite a while.
An environment ω is a configuration of transition probability vectors ω = (ωx)x∈Zd ∈
Ω = PZd , where P = {(pz)z∈Zd : pz ≥ 0,
z pz = 1} is the simplex of all probability
vectors on Zd. Vector ωx = (ωx,z)z∈Zd gives the transition probabilities out of state
x, denoted by πx,y(ω) = ωx,y−x. To run the random walk, fix an environment ω and
an initial state z ∈ Zd. The random walk X0,∞ = (Xn)n≥0 in environment ω started
at z is then the canonical Markov chain with state space Zd whose path measure P ωz
satisfies
P ωz (X0 = z) = 1 and P
z (Xn+1 = y|Xn = x) = πx,y(ω).
On the space Ω we put its product σ-fieldS, natural shifts πx,y(Tzω) = πx+z,y+z(ω),
and a {Tz}-invariant probability measure P that makes the system (Ω,S, (Tz)z∈Zd,P)
ergodic. In this paper P is an i.i.d. product measure on PZd . In other words, the
vectors (ωx)x∈Zd are i.i.d. across the sites x under P.
Date: November 21, 2018.
2000 Mathematics Subject Classification. 60K37, 60F05, 60F17, 82D30.
Key words and phrases. Random walk, non-nestling, random environment, central limit theorem,
invariance principle, point of view of the particle, environment process, Green function.
1Department of Mathematics, University of Utah.
1Supported in part by NSF Grant DMS-0505030.
2Mathematics Department, University of Wisconsin-Madison.
2Supported in part by NSF Grant DMS-0402231.
http://arxiv.org/abs/0704.1022v2
2 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Statements, probabilities and expectations under a fixed environment, such as
the distribution P ωz above, are called quenched. When also the environment is av-
eraged out, the notions are called averaged, or also annealed. In particular, the
averaged distribution Pz(dx0,∞) of the walk is the marginal of the joint distribution
Pz(dx0,∞, dω) = P
z (dx0,∞)P(dω) on paths and environments.
Several excellent expositions on RWRE exist, and we refer the reader to the lectures
[3], [15] and [18]. We turn to the specialized assumptions imposed on the model in
this paper.
The main assumption is non-nestling (N) which guarantees a drift uniformly over
the environments. The terminology was introduced by Zerner [19].
Hypothesis (N). There exists a vector û ∈ Zd \ {0} and a constant δ > 0 such that
z · û π0,z(ω) ≥ δ
There is no harm in assuming û ∈ Zd, and this is convenient. We utilize two
auxiliary assumptions: an exponential moment bound (M) on the steps of the walk,
and some regularity (R) on the environments.
Hypothesis (M). There exist positive constants M and s0 such that
es0|z|π0,z(ω) ≤ es0M
Hypothesis (R). There exists a constant κ > 0 such that
z: z·û=1
π0,z(ω) ≥ κ
= 1. (1.1)
Let J = {z : Eπ0,z > 0} be the set of admissible steps under P. Then
P{∀z : π0,0 + π0,z < 1} > 0 and J 6⊂ Ru for all u ∈ Rd. (1.2)
Assumption (1.1) above is stronger than needed. In the proofs it is actually used in
the form (7.5) [Section 7] that permits backtracking before hitting the level x · û = 1.
At the expense of additional technicalities in Section 7 quenched assumption (1.1)
can be replaced by an averaged requirement.
Assumption (1.2) is used in Lemma 7.10. It is necessary for the quenched CLT as
was discovered already in the simpler forbidden direction case we studied in [10] and
[11]. Note that assumption (1.2) rules out the case d = 1. However, the issue is not
whether the walk is genuinely d-dimensional, but whether the walk can explore its
environment thoroughly enough to suppress the fluctuations of the quenched mean.
Most work on RWRE takes uniform ellipticity and nearest-neighbor jumps as standing
assumptions, which of course imply Hypotheses (M) and (R).
QUENCHED FUNCTIONAL CLT FOR RWRE 3
These assumptions are more than strong enough to imply a law of large numbers:
there exists a velocity v 6= 0 such that
n−1Xn = v
= 1. (1.3)
Representations for v are given in (2.5) and Lemma 5.1. Define the (approximately)
centered and diffusively scaled process
Bn(t) =
X[nt] − [nt]v√
. (1.4)
As usual [x] = max{n ∈ Z : n ≤ x} is the integer part of a real x. Let DRd[0,∞) be
the standard Skorohod space of Rd-valued cadlag paths (see [6] for the basics). Let
Qωn = P
0 (Bn ∈ · ) denote the quenched distribution of the process Bn on DRd[0,∞).
The results of this paper concern the limit of the process Bn as n → ∞. As
expected, the limit process is a Brownian motion with correlated coordinates. For a
symmetric, non-negative definite d × d matrix D, a Brownian motion with diffusion
matrix D is the Rd-valued process {B(t) : t ≥ 0} with continuous paths, independent
increments, and such that for s < t the d-vector B(t)−B(s) has Gaussian distribution
with mean zero and covariance matrix (t − s)D. The matrix D is degenerate in
direction u ∈ Rd if utDu = 0. Equivalently, u · B(t) = 0 almost surely.
Here is the main result.
Theorem 1.1. Let d ≥ 2 and consider a random walk in an i.i.d. product random
environment that satisfies non-nestling (N), the exponential moment hypothesis (M),
and the regularity in (R). Then for P-almost every ω distributions Qωn converge weakly
on DRd [0,∞) to the distribution of a Brownian motion with a diffusion matrix D
that is independent of ω. utDu = 0 iff u is orthogonal to the span of {x − y :
E(π0x)E(π0y) > 0}.
Eqn (2.6) gives the expression for the diffusion matrix D, familiar for example from
[14]. Before turning to the proofs we discuss briefly the current situation in this area
of probability and the place of this work in this context.
Several different approaches can be identified in recent work on quenched central
limit theorems for multidimensional RWRE. (i) Small perturbations of classical ran-
dom walk have been studied by many authors. The most significant results include the
early work of Bricmont and Kupiainen [4] and more recently Sznitman and Zeitouni
[16] for small perturbations of Brownian motion in dimension d ≥ 3. (ii) An aver-
aged CLT can be turned into a quenched CLT by bounding certain variances through
the control of intersections of two independent paths. This idea was introduced by
Bolthausen and Sznitman in [2] and more recently applied by Berger and Zeitouni
in [1]. Both utilize high dimension to handle the intersections. (iii) Our approach
is based on the subdiffusivity of the quenched mean of the walk. That is, we show
that the variance of Eω0 (Xn) is of order n
2α for some α < 1/2. We also achieve this
through intersection bounds. Instead of high dimension we assume strong enough
4 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
drift. We introduced this line of reasoning in [9] and later applied it to the case of
walks with a forbidden direction in [11]. The significant advance taken in the present
paper over [9] and [11] is the elimination of restrictions on the admissible steps of
the walk. Theorem 2.1 below summarizes the general principle for application in this
paper.
As the reader will see, the arguments in this paper are based on quenched expo-
nential bounds that flow from Hypotheses (N), (M) and (R). It is common in this
field to look for an invariant measure P∞ for the environment process that is mutu-
ally absolutely continuous with the original P, at least on the part of the space Ω
to which the drift points. In this paper we do things a little differently: instead of
the absolute continuity, we use bounds on the variation distance between P∞ and P.
This distance will decay exponentially in the direction û.
In the case of nearest-neighbor, uniformly elliptic non-nestling walks in dimension
d ≥ 4 the quenched CLT has been proved earlier: first by Bolthausen and Sznitman
[2] under a small noise assumption, and recently by Berger and Zeitouni [1] without
the small noise assumption. Berger and Zeitouni [1] go beyond non-nestling to more
general ballistic walks. The method in these two papers utilizes high dimension
crucially. Whether their argument can work in d = 3 is not presently clear. The
approach of the present paper should work for more general ballistic walks in all
dimensions d ≥ 2, as the main technical step that reduces the variance estimate to
an intersection estimate is generalized (Section 6 in the present paper).
We turn to the proofs. The next section collects some preliminary material and
finishes with an outline of the rest of the paper.
2. Preliminaries for the proof.
As mentioned, we can assume that û ∈ Zd. This is convenient because then the
lattice Zd decomposes into levels identified by the integer value x · û.
Let us summarize notation for the reader’s convenience. Constants whose exact
values are not important and can change from line to line are often denoted by C
and s. The set of nonnegative integers is N = {0, 1, 2, . . . }. Vectors and sequences
are abbreviated xm,n = (xm, xm+1, . . . , xn) and xm,∞ = (xm, xm+1, xm+2, . . . ). Similar
notation is used for finite and infinite random paths: Xm,n = (Xm, Xm+1, . . . , Xn)
and Xm,∞ = (Xm, Xm+1, Xm+2, . . . ). X[0,n] = {Xk : 0 ≤ k ≤ n} denotes the set of
sites visited by the walk. Dt is the transpose of a vector or matrix D. An element
of Rd is regarded as a d× 1 column vector. The left shift on the path space (Zd)N is
(θkx0,∞)n = xn+k.
E, E0, and E
0 denote expectations under, respectively, P, P0, and P
0 . P∞ will
denote an invariant measure on Ω, with expectation E∞. We abbreviate P
0 (·) =
0 (·) and E∞0 (·) = E∞Eω0 (·) to indicate that the environment of a quenched
expectation is averaged under P∞. A family of σ-algebras on Ω that in a sense look
towards the future is defined by Sℓ = σ{ωx : x · û ≥ ℓ}.
QUENCHED FUNCTIONAL CLT FOR RWRE 5
Define the drift
D(ω) = Eω0 (X1) =
zπ0z(ω).
The environment process is the Markov chain on Ω with transition kernel
Π(ω,A) = P ω0 (TX1ω ∈ A).
The proof of the quenched CLT Theorem 1.1 utilizes crucially the environment
process and its invariant distribution. A preliminary part of the proof is summarized
in the next theorem quoted from [9]. This Theorem 2.1 was proved by applying
the arguments of Maxwell and Woodroofe [8] and Derriennic and Lin [5] to the
environment process.
Theorem 2.1. [9] Let d ≥ 1. Suppose the probability measure P∞ on (Ω,S) is
invariant and ergodic for the Markov transition Π. Assume that
z |z|2E∞(π0z) <∞
and that there exists an α < 1/2 such that as n→ ∞
|Eω0 (Xn)− nE∞(D)|
= Ŏ (n2α). (2.1)
Then as n → ∞ the following weak limit happens for P∞-a.e. ω: distributions Qωn
converge weakly on the space DRd[0,∞) to the distribution of a Brownian motion with
a symmetric, non-negative definite diffusion matrix D that is independent of ω.
Another central tool for the development that follows is provided by the Sznitman-
Zerner regeneration times [17] that we now define. For ℓ ≥ 0 let λℓ be the first time
the walk reaches level ℓ relative to the initial level:
λℓ = min{n ≥ 0 : Xn · û−X0 · û ≥ ℓ}.
Define β to be the first backtracking time:
β = inf{n ≥ 0 : Xn · û < X0 · û}.
Let Mn be the maximum level, relative to the starting level, reached by time n:
Mn = max{Xk · û−X0 · û : 0 ≤ k ≤ n}.
For a > 0, and when β <∞, consider the first time by which the walker reaches level
Mβ + a:
λMβ+a = inf{n ≥ β : Xn · û−X0 · û ≥Mβ + a}.
Let S0 = λa and, as long as β ◦ θSk−1 < ∞, define Sk = Sk−1 + λMβ+a ◦ θSk−1 for
k ≥ 1. Finally, let the first regeneration time be
Sℓ1I{β ◦ θSk <∞ for 0 ≤ k < ℓ and β ◦ θSℓ = ∞}. (2.2)
Non-nestling guarantees that τ
1 is finite, and in fact gives moment bounds uniformly
in ω as we see in Lemma 3.1 below. Consequently we can iterate to define τ
0 = 0,
and for k ≥ 1
k = τ
k−1 + τ
1 ◦ θτ
k−1 . (2.3)
6 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
When the value of a is not important we simplify the notation to τk = τ
k . Sznit-
man and Zerner [17] proved that the regeneration slabs
τk+1 − τk, (Xτk+n −Xτk)0≤n≤τk+1−τk ,
{ωXτk+z : 0 ≤ z · û < (Xτk+1 −Xτk) · û}
) (2.4)
are i.i.d. for k ≥ 1, each distributed as
τ1, (Xn)0≤n≤τ1 , {ωz : 0 ≤ z·û < Xτ1 ·û}
under
P0( · | β = ∞). Strictly speaking, uniform ellipticity and nearest-neighbor jumps were
standing assumptions in [17], but these assumptions are not needed for the proof of
the i.i.d. structure.
From the renewal structure and moment estimates a law of large numbers (1.3) and
an averaged functional central limit theorem follow, along the lines of Theorem 2.3
in [17] and Theorem 4.1 in [14]. These references treat walks that satisfy Kalikow’s
condition, considerably more general than the non-nestling walks we study. The
limiting velocity for the law of large numbers is
E0(Xτ1 |β = ∞)
E0(τ1|β = ∞)
. (2.5)
The averaged CLT states that the distributions P0{Bn ∈ · } converge to the distri-
bution of a Brownian motion with diffusion matrix
(Xτ1 − τ1v)(Xτ1 − τ1v)t|β = ∞
E0[τ1|β = ∞]
. (2.6)
Once we know that the P-a.s. quenched CLT holds with a constant diffusion matrix,
this diffusion matrix must be the same D as for the averaged CLT. We give here the
argument for the degeneracy statement of Theorem 1.1.
Lemma 2.1. Define D by (2.6) and let u ∈ Rd. Then utDu = 0 iff u is orthogonal
to the span of {x− y : E(π0x)E(π0y) > 0}.
Proof. The argument is a minor embellishment of that given for a similar degeneracy
statement on p. 123–124 of [10] for the forbidden-direction case where π0,z is supported
by z · û ≥ 0. We spell out enough of the argument to show how to adapt that proof
to the present case.
Again, the intermediate step is to show that utDu = 0 iff u is orthogonal to the
span of {x− v : E(π0x) > 0}. The argument from orthogonality to utDu = 0 goes as
in [10, p. 124].
Suppose utDu = 0 which is the same as
P0(Xτ1 · u = τ1v · u | β = ∞) = 1.
Suppose z is such that Eπ0,z > 0 and z · û < 0. By non-nestling there must exist w
such that Eπ0,zπ0,w > 0 and w · û > 0. Pick m > 0 so that (z + mw) · û > 0 but
QUENCHED FUNCTIONAL CLT FOR RWRE 7
(z + (m− 1)w) · û ≤ 0. Take a = 1 in the definition (2.2) of regeneration. Then
P0[Xτ1 = z + 2mw, τ1 = 2m+ 1 | β = ∞]
[ ( m−1∏
πiw,(i+1)w
πmw,z+mw
( m−1∏
πz+(m+j)w,z+(m+j+1)w
P ωz+2mw(β = ∞)
Consequently
(z + 2mw) · u = (1 + 2m)v · u. (2.7)
In this manner, by replacing σ1 with τ1 and by adding in the no-backtracking
probabilities, the arguments in [10, p. 123] can be repeated to show that if Eπ0x > 0
then x · u = v · u for x such that x · û ≥ 0. In particular the very first step on p. 123
of [10] gives w · u = v · u. This combines with (2.7) above to give z · u = v · u. Now
simply follow the proof in [10, p. 123–124] to its conclusion. �
Here is an outline of the proof of Theorem 1.1. It all goes via Theorem 2.1.
(i) After some basic estimates in Section 3, we prove in Section 4 the existence of the
ergodic equilibrium P∞ required for Theorem 2.1. P∞ is not convenient to work with
so we still need to do computations with P. For this purpose Section 4 proves that in
the direction û the measures P∞ and P come exponentially close in variation distance
and that the environment process satisfies a P0-a.s. ergodic theorem. In Section 5
we show that P∞ and P are interchangeable both in the hypotheses that need to be
checked and in the conclusions obtained. In particular, the P∞-a.s. quenched CLT
coming from Theorem 2.1 holds also P-a.s. Then we know that the diffusion matrix
D is the one in (2.6).
The bulk of the work goes towards verifying condition (2.1), but under P instead
of P∞. There are two main stages to this argument.
(ii) By a decomposition into martingale increments the proof of (2.1) reduces to
bounding the number of common points of two independent walks in a common
environment (Section 6).
(iii) The intersections are controlled by introducing levels at which both walks
regenerate. These common regeneration levels are reached fast enough and the pro-
gression from one common regeneration level to the next is a Markov chain. When
this Markov chain drifts away from the origin it can be approximated well enough by
a symmetric random walk. This approximation enables us to control the growth of
the Green function of the Markov chain, and thereby the number of common points.
This is in Section 7 and in an Appendix devoted to the Green function bound.
3. Basic estimates for non-nestling RWRE
This section contains estimates that follow from Hypotheses (N) and (M), all col-
lected in the following lemma. These will be used repeatedly. In addition to the
8 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
stopping times already defined, let
Hz = min{n ≥ 1 : Xn = z}
be the first hitting time of site z.
Lemma 3.1. If P satisfies Hypotheses (N) and (M), then there exist positive constants
η, γ, κ, (Cp)p≥1, and s1 ≤ s0, possibly depending on M , s0, and δ, such that for all
x ∈ Zd, n ≥ 0, s ∈ [0, s1], p ≥ 1, ℓ ≥ 1, for z such that z · û ≥ 0, a ≥ 1, and for
P-a.e. ω,
Eωx (e
−sXn·û) ≤ e−sx·û(1− sδ/2)n, (3.1)
Eωx (e
s|Xn−x|) ≤ esMn, (3.2)
P ωx (X1 · û ≥ x · û+ γ) ≥ κ, (3.3)
Eωx (λ
ℓ) ≤ Cpℓp, (3.4)
Eωx (|Xλℓ − x|p) ≤ Cpℓp, (3.5)
Eω0 [(MHz − z · û)p1I{Hz < n}] ≤ CpℓpP ω0 (Hz < n) + Cps−pe−sℓ/2, (3.6)
P ωx (β = ∞) ≥ η, (3.7)
Eωx (|τ
1 |p) ≤ Cp ap, (3.8)
Eωx (|Xτ (a)1 +n −Xn|
p) ≤ Cq aq, for all q > p. (3.9)
The particular point in (3.8)–(3.9) is to make the dependence on a explicit. Note
that (3.7)–(3.8) give
E0(τj − τj−1)p <∞ (3.10)
for all j ≥ 1. In Section 4 we construct an ergodic invariant measure P∞ for the
environment chain in a way that preserves the conclusions of this lemma under P∞.
Proof. Replacing x by 0 and ω by Txω allows us to assume that x = 0. Then for all
s ∈ [0, s0/2]
∣∣Eω0 (e−sX1·û)− 1 + sEω0 (X1 · û)
∣∣ ≤ |û|2Eω0 (|X1|2es0|X1|/2)
≤ (2|û|/s0)2es0Ms2 = cs2,
where we used moment assumption (M). Then by the non-nestling assumption (N)
Eω0 (e
−sXn·û|Xn−1) = e−sXn−1·ûEωXn−1(e
−s(X1−X0)·û) ≤ e−sXn−1·û(1− sδ + cs2).
Taking now the quenched expectation of both sides and iterating the procedure proves
(3.1), provided s1 is small enough. To prove (3.2) one can instead show that
Eω0 (e
k=1 |Xk−Xk−1|) ≤ esnM .
This can be proved by induction as for (3.1), using only Hypothesis (M) and Hölder’s
inequality (to switch to s0).
QUENCHED FUNCTIONAL CLT FOR RWRE 9
Concerning (3.3), we have
P ω0 (X1 · û ≥ γ) ≥ (1− eγs(1− sδ/2))−→
sδ/2.
So taking γ small enough and κ slightly smaller than sδ/2 does the job.
Notice next that P ω0 (λ1 <∞) = 1 due to (3.1). P-a.s. Then
Eω0 (λ
(n+ 1)pP ω0 (λ1 > n) ≤
(n+ 1)pP ω0 (Xn · û ≤ 1)
(n + 1)pEω0 (e
−sXn·û).
The last expression is bounded if s is small enough. Therefore,
Eω0 (λ
ℓ) ≤ Eω0
[ ∣∣∣
[ℓ]+1∑
(λi − λi−1)
≤ ([ℓ] + 1)p−1
[ℓ]+1∑
EωXλi−1
≤ Cpℓp.
Bound (3.5) is proved similarly: by the Cauchy-Schwarz inequality, Hypothesis (M)
and (3.1),
Eω0 (|Xλ1 |p) ≤
Eω0 (|Xn|2p)1/2P ω0 (Xn−1 · û < 1)1/2
[2p]! s
−[2p]
s0Mes
)1/2 ∑
(1− sδ/2)(n−1)/2np ≤ Cp.
To prove (3.6), write
Eω0 [(MHz − z · û)p1I{Hz < n}]
ℓp−1P ω0 (MHz − z · û ≥ ℓ,Hz < n) + Cpℓ
0 (Hz < n)
ℓp−1Eω0 [P
Xλz·û+ℓ
(Xk · û−X0 · û ≤ −ℓ)] + Cpℓp0P ω0 (Hz < n)
ℓp−1e−sℓ + Cpℓ
0 (Hz < n) ≤ Cps−pe−sℓ0/2 + Cpℓ
0 (Hz < n).
To prove (3.7), note that Chebyshev inequality and (3.1) give, for s > 0 small
enough, ℓ ≥ 1, and P-a.e. ω
P ω0 (λ−ℓ+1 <∞) ≤
P ω0 (Xn · û ≤ −(ℓ− 1)) ≤ 2(sδ)−1e−s(ℓ−1).
On the other hand, for an integer ℓ ≥ 2 we have
P ω0 (λℓ < β) ≥
P ω0 (λℓ−1 < β,Xλℓ−1 = x)P
x (λ−ℓ+1 = ∞).
10 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Therefore, taking ℓ to infinity one has, for ℓ0 large enough,
P ω0 (β = ∞) ≥ P ω0 (λℓ0 < β)
(1− 2(sδ)−1e−sℓ).
Markov property and (3.3) give P ω0 (λℓ0 < β) ≥ κℓ0/γ+1 > 0 and (3.7) is proved.
Now we will bound the quenched expectation of λ
1I{β < ∞} uniformly in ω.
To this end, for p1 > p and q1 = p1(p1 − p)−1, we have by (3.7)
Eω0 (λ
1I{β <∞}) ≤
Eω0 (λ
1I{β = n})
Eω0 (λ
)p/p1(
P ω0 (β = n)
)1/q1
By (3.4) one has, for p2 > p1 > p and q2 = p2(p2 − p1)−1,
Eω0 (λ
Eω0 (λ
m+1+a)
)p1/p2(
P ω0 ([Mn] = m)
)1/q2
(m+ 1 + a)p1
P ω0 (Xi · û ≥ m)
)1/q2
where Cp really depends on p1 and p2, but these are chosen arbitrarily, as long as
they satisfy p2 > p1 > p. Using (3.2) one has
P ω0 (Xi · û ≥ m) ≤
1 if m < 2M |û|i,
e−smeM |û|si if m ≥ 2M |û|i.
Hence,
Eω0 (λ
) ≤ Cp
(m+ 1 + a)p1(n1I{m < 2Mn|û|}+ e−sm/2)1/q2
≤ Cpn(n+ a)p1n1/q2 + Cp
(m+ 1)p1e−sm/2q2 + Cpa
e−sm/2q2
≤ Cpn1+1/q2(n+ a)p1 .
Since {β = n} ⊂ {Xn · û ≤ 0}, one can use (3.1) to conclude that
Eω0 (λ
1I{β <∞}) ≤ Cp
np/p1+p/(p1q2)(n+ a)p(1− sδ/2)n/q1 ≤ Cpap.
QUENCHED FUNCTIONAL CLT FOR RWRE 11
In the last inequality we have used the fact that a ≥ 1. Using, (3.7), the definition
of the times Sk, and the Markov property, one has
Eω0 [S
ℓ 1I{β ◦ θSk <∞ for 0 ≤ k < ℓ and β ◦ θSℓ = ∞}]
≤ (ℓ+ 1)p−1
Eω0 [λ
a1I{β ◦ θSk <∞ for 0 ≤ k < ℓ}]
Eω0 [λ
◦ θSj1I{β ◦ θSk <∞ for 0 ≤ k < ℓ}]
≤ (ℓ+ 1)p−1
p(1− η)ℓ +
(1− η)jCpap(1− η)ℓ−j−1
≤ Cp(ℓ + 1)p(1− η)ℓ−1ap.
Bound (3.8) follows then from (2.2). To prove (3.9) let q > p and write
Eω0 (|Xτ (a)1 +n −Xn|
Eω0 (|Xk+1+n −Xk+n|p|τ
1 |p−11I{k < τ
k−1−q+pEω0 (|Xk+1+n −Xk+n|p|τ
1 |q)
k−1−q+pEω0 (|τ
1 |2q)1/2 ≤ Cq aq,
where we have used Hypothesis (M) along with the Cauchy-Schwarz inequality in
the second to last inequality and (3.8) in the last. This completes the proof of the
lemma. �
4. Invariant measure and ergodicity
For ℓ ∈ Z define the σ-algebras Sℓ = σ{ωx : x · û ≥ ℓ} on Ω. Denote the restriction
of the measure P to the σ-algebra Sℓ by P|Sℓ . In this section we prove the next
two theorems. The variation distance of two probability measures is dVar(µ, ν) =
sup{µ(A)− ν(A)} with the supremum taken over measurable sets A.
Theorem 4.1. Assume P is product non-nestling (N) and satisfies the moment hy-
pothesis (M). Then there exists a probability measure P∞ on Ω with these properties.
(a) P∞ is invariant and ergodic for the Markov transition kernel Π.
(b) There exist constants 0 < c, C <∞ such that for all ℓ ≥ 0
dVar(P∞|Sℓ ,P|Sℓ) ≤ Ce
−cℓ. (4.1)
(c) Hypotheses (N) and (M) and the conclusions of Lemma 3.1 hold P∞-almost
surely.
Along the way we also establish this ergodic theorem under the original environ-
ment measure. E∞ denotes expectation under P∞.
12 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Theorem 4.2. Assumptions as in Theorem 4.1 above. Let Ψ be a bounded S−a-
measurable function on Ω, for some 0 < a <∞. Then
Ψ(TXjω) = E∞Ψ P0-almost surely. (4.2)
The ergodic theorem tells us that there is a unique invariant P∞ in a natural
relationship to P, and that P∞ ≪ P on each σ-algebra S−a. Limit (4.2) cannot
hold for all bounded measurable Ψ on Ω because this would imply the absolute
continuity P∞ ≪ P on the entire space Ω. A counterexample that satisfies (N)
and (M) but where the quenched walk is degenerate was given by Bolthausen and
Sznitman [2, Proposition 1.5]. Whether regularity assumption (R) or ellipticity will
make a difference here is not presently clear. For the simpler case of space-time walks
(see description of model in [9]) with nondegenerate P ω0 absolute continuity P∞ ≪ P
does hold on the entire space. Theorem 3.1 in [2] proves this for nearest-neighbor
jumps with some weak ellipticity. The general case is no harder.
Proof of Theorems 4.1 and 4.2. Let Pn(A) = P0(TXnω ∈ A). A computation shows
fn(ω) =
(ω) =
P ωx (Xn = 0).
By hypotheses (M) and (N) we can replace the state space Ω = PZd with the
smaller space Ω0 = PZ
0 where
P0 = {(pz) ∈ P :
es0|z|pz ≤ es0M and
z · û pz ≥ δ }. (4.3)
Fatou’s lemma shows that the exponential bound is preserved by pointwise conver-
gence in P0. Then the exponential bound shows that the non-nestling property is also
preserved. Thus P0 is compact, and then Ω0 is compact under the product topology.
Compactness gives a subsequence {nj} along which the averages nj−1
m=1 Pm
converge weakly to a probability measure P∞ on Ω0. Hypotheses (N) and (M) transfer
to P∞ by virtue of having been included in the state space Ω0. Thus the proof of
Lemma 3.1 can be repeated for P∞-a.e. ω. We have verified part (c) of Theorem 4.1.
Next we check that P∞ is invariant under Π. Take a bounded, continuous local
function F on Ω0 that depends only on environments (ωx : |x| ≤ K). For ω, ω̄ ∈ Ω0
∣∣ΠF (ω)− ΠF (ω̄)
∣∣Eω0 [F (TX1ω)]−Eω̄0 [F (TX1ω̄)]
|z|≤C
∣∣∣π0,z(ω)F (Tzω)− π0,z(ω̄)F (Tzω̄)
∣∣∣+ ‖F‖∞
|z|>C
π0,z(ω) + π0,z(ω̄)
From this we see that ΠF is continuous. For let ω̄ → ω in Ω0 so that ω̄x,z → ωx,z at
each coordinate. Since the last term above is controlled by the uniform exponential
QUENCHED FUNCTIONAL CLT FOR RWRE 13
tail bound imposed on P0, continuity of ΠF follows. Consequently the weak limit
m=1 Pm → P∞ together with Pn+1 = PnΠ implies the Π-invariance of P∞.
We show the exponential bound (4.1) on the variation distance next because the
ergodicity proof depends on it. On metric spaces total variation distance can be
characterized in terms of continuous functions:
dVar(µ, ν) =
fdν : f continuous, sup |f | ≤ 1
This makes dVar(µ, ν) lower semicontinuous which we shall find convenient below.
Fix ℓ > 0. Then
dPn|Sℓ
dP|Sℓ
P ωx (Xn = 0,max
Xj · û ≤ ℓ/2)
E[P ωx (Xn = 0,max
Xj · û > ℓ/2)|Sℓ].
(4.4)
The L1(P)-norm of the second term is bounded by
In,ℓ = P0(max
Xj · û > Xn · û+ ℓ/2)
and (3.1) tells us that
In,ℓ ≤
e−sℓ/2(1− sδ/2)n−j ≤ Ce−sℓ/2. (4.5)
The integrand in the first term of (4.4) is measurable with respect to σ(ωx : x·û ≤ ℓ/2)
and therefore independent of Sℓ. The distance between the whole first term and 1 is
then Ŏ (In,ℓ). Thus for large enough ℓ,
dVar(Pn|Sℓ ,P|Sℓ) ≤
∫ ∣∣∣
dPn|Sℓ
dP|Sℓ
∣∣∣dP ≤ 2In,ℓ ≤ Ce−cℓ.
By the construction of P∞ as the Cesàro limit and by the lower semicontinuity and
convexity of the variation distance
dVar(P∞|Sℓ ,P|Sℓ) ≤ lim
dVar(Pm|Sℓ ,P|Sℓ) ≤ Ce
Part (b) has been verified.
As the last point we prove the ergodicity. Recall the notation E∞0 = E∞E
0 . Let
Ψ be a bounded local function on Ω. It suffices to prove that for some constant b
∣∣∣n−1
Ψ(TXjω)− b
∣∣∣ = 0. (4.6)
14 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
By an approximation it follows from this that for all F ∈ L1(P∞)
ΠjF (ω) → E∞F in L1(P∞). (4.7)
By standard theory (Section IV.2 in [12]) this is equivalent to ergodicity of P∞ for
the transition Π.
We combine the proof of Theorem 4.2 with the proof of (4.6). For this purpose let
Ψ be S−a+1-measurable with a <∞. Take a to be the parameter in the regeneration
times (2.2). Let
τi+1−1∑
Ψ(TXjω).
From the i.i.d. regeneration slabs and the moment bound (3.10) follows the limit
τm−1∑
Ψ(TXjω) = lim
ϕi = b0 P0-almost surely, (4.8)
where the constant b0 is defined by the limit.
To justify this more precisely, recall the definition of regeneration slabs given in
(2.4). Define a function Φ of the regeneration slabs by
Φ(S0,S1,S2, . . . ) =
τ2−1∑
Ψ(TXjω).
Since each regeneration slab has thickness in û-direction at least a, the Ψ-terms in
the sum do not read the environments below level zero and consequently the sum is
a function of (S0,S1,S2, . . . ). Next one can check for k ≥ 1 that
Φ(Sk−1,Sk,Sk+1, . . . ) =
τ2(Xτk−1+ · −Xτk−1 )−1∑
j=τ1(Xτk−1+ · −Xτk−1)
TXτk−1+j−Xτk−1 (TXτk−1ω)
= ϕk.
Now the sum of ϕ-terms in (4.8) can be decomposed into
ϕ0 + ϕ1 +
Φ(Sk,Sk+1,Sk+2, . . . ).
The limit (4.8) follows because the slabs (Sk)k≥1 are i.i.d. and the finite initial terms
ϕ0 + ϕ1 are eliminated by the m
−1 factor.
Let αn = inf{k : τk ≥ n}. Bounds (3.7)–(3.8) give finite moments of all orders to
the increments τk−τk−1 and this implies that n−1(ταn−1−ταn) → 0 P0-almost surely.
QUENCHED FUNCTIONAL CLT FOR RWRE 15
Consequently (4.8) yields the next limit, for another constant b:
Ψ(TXjω) = b P0-almost surely. (4.9)
By boundedness this limit is valid also in L1(P0) and the initial point of the walk is
immaterial by shift-invariance of P. Let ℓ > 0 and choose a small ε0 > 0. Abbreviate
Gn,x(ω) = E
[ ∣∣∣n−1
Ψ(TXjω)− b
∣∣∣1I
Xj · û ≥ X0 · û− ε0ℓ/2
I = {x ∈ Zd : x · û ≥ ε0ℓ, |x| ≤ Aℓ}
for some constant A. Use the bound (4.1) on the variation distance and the fact that
the functions Gn,x(ω) are uniformly bounded over all x, n, ω, and, if ℓ is large enough
relative to a and ε0, for x ∈ I the function Gn,x is Sε0ℓ/3-measurable.
P ω0 [Xℓ = x]Gn,x(ω) ≥ ε1
P∞{Gn,x(ω) ≥ ε1/(Cℓd)}
≤ Cℓdε−11
E∞Gn,x ≤ Cℓdε−11
EGn,x + Cℓ
2dε−11 e
−cε0ℓ/3.
By (4.9) EGn,x → 0 for any fixed x. Thus from above we get for any fixed ℓ,
1I{Xℓ ∈ I}Gn,Xℓ
≤ ε1 + Cℓ2dε−11 e−cε0ℓ/3. (4.10)
The reader should bear in mind that the constant C is changing from line to line.
Finally, we write
∣∣∣n−1
Ψ(TXjω)− b
≤ lim
1I{Xℓ ∈ I}
∣∣∣n−1
n+ℓ−1∑
Ψ(TXjω)− b
∣∣∣1I
Xj · û ≥ Xℓ · û− ε0ℓ/2
+ CP∞0 {Xℓ /∈ I} + CP∞0
Xj · û < Xℓ · û− ε0ℓ/2
≤ lim
1I{Xℓ ∈ I}Gn,Xℓ
+ CP∞0 {Xℓ · û < ε0ℓ}
+ CP∞0 { |Xℓ| > Aℓ} + CE∞0 P ωXℓ
Xj · û < X0 · û− ε0ℓ/2
As pointed out, P∞ satisfies Lemma 3.1 because hypotheses (N) and (M) were built
into the space Ω0 that supports P∞. This enables us to make the error probabilities
above small. Consequently, if we first pick ε0 and ε1 small enough, A large enough,
then ℓ large, and apply (4.10), we will have shown (4.6). Ergodicity of P∞ has been
shown. This concludes the proof of Theorem 4.1.
16 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Thereom 4.2 has also been established. It follows from the combination of (4.6)
and (4.9). �
5. Change of measure
There are several stages in the proof where we need to check that a desired con-
clusion is not affected by choice between P and P∞. We collect all instances of such
transfers in this section. The standing assumptions of this section are that P is an
i.i.d. product measure that satisfies Hypotheses (N) and (M), and that P∞ is the
measure given by Theorem 4.1. We show first that P∞ can be replaced with P in the
key condition (2.1) of Theorem 2.1.
Lemma 5.1. The velocity v defined by (2.5) satisfies v = E∞(D). There exists a
constant C such that
|E0(Xn)− nE∞(D)| ≤ C for all n ≥ 1. (5.1)
Proof. We start by showing v = E∞(D). The uniform exponential tail in the defi-
nition (4.3) of P0 makes the function D(ω) bounded and continuous on Ω0. By the
Cesàro definition of P∞,
E∞(D) = lim
nj−1∑
Ek(D) = lim
nj−1∑
E0[D(TXkω)].
The moment bounds (3.7)–(3.9) imply that the law of large numbers n−1Xn → v
holds also in L1(P0). From this and the Markov property
v = lim
E0(Xk+1 −Xk) = lim
E0[D(TXkω)].
We have proved v = E∞(D).
The variables (Xτj+1 −Xτj , τj+1−τj)j≥1 are i.i.d. with sufficient moments by (3.7)–
(3.9). With αn = inf{j ≥ 1 : τj − τ1 ≥ n} Wald’s identity gives
E0(Xταn−Xτ1) = E0(αn)E0(Xτ1 |β = ∞) and E0(ταn−τ1) = E0(αn)E0(τ1|β = ∞).
Consequently, by the definition (2.5) of v,
E0(Xn)− nv = vE0(ταn − τ1 − n)− E0(Xταn −Xτ1 −Xn).
It remains to show that E0(ταn − τ1−n) and E0(Xταn −Xτ1 −Xn) are bounded by
constants. We do this with a simple renewal argument. Let Yj = τj+1 − τj for j ≥ 1
and V0 = 0, Vm = Y1 + · · · + Ym. The quantity to bound is the forward recurrence
time Bn = min{k ≥ 0 : n+ k ∈ {Vm}} because ταn − τ1 − n = Bn.
We can write
Bn = (Y1 − n)+ +
1I{Y1 = k}Bn−k ◦ θ
QUENCHED FUNCTIONAL CLT FOR RWRE 17
where θ shifts the sequence {Yk} and makes Bn−k ◦ θ independent of Y1. The two
main terms on the right multiply to zero, so for any integer p ≥ 1
Bpn = ((Y1 − n)+)p +
1I{Y1 = k}(Bn−k ◦ θ)p.
Set z(n) = E0((Y1 − n)+)p. Moment bounds (3.7)–(3.8) give E0(Y p+11 ) < ∞ which
implies
z(n) <∞. Taking expectations and using independence gives the discrete
renewal equation
n = z(n) +
P0(Y1 = k)E0B
Induction on n shows that E0B
k=1 z(k) ≤ C(p) for all n. In particular,
E0(ταn − τ1 − n)p is bounded by a constant uniformly over n. To extend this to
E0|Xταn − Xτ1 − Xn|p apply an argument like the one given for (3.9) at the end of
Section 3. �
Proposition 5.2. Assume that there exists an ᾱ < 1/2 such that
|Eω0 (Xn)− E0(Xn)|
= Ŏ (n2ᾱ). (5.2)
Then condition (2.1) is satisfied for some α < 1/2.
Proof. By (5.1) assumption (5.2) turns into
|Eω0 (Xn)− nv|
= Ŏ (n2ᾱ). (5.3)
In the rest of this proof we use the conclusions of Lemma 3.1 under P∞ instead of P.
This is justified by part (c) of Theorem 4.1.
For k ≥ 1, recall that λk = inf{n ≥ 0 : (Xn − X0) · û ≥ k}. Take k = [nρ] for
a small enough ρ > 0. The point of the proof is to let the walk run up to a high
level k so that expectations under P∞ can be profitably related to expectations under
P through the variation distance bound (4.1). Estimation is needed to remove the
dependence on the environment on low levels. First compute as follows.
|Eω0 (Xn − nv)|
|Eω0 (Xn − nv, λk ≤ n) + Eω0 (Xn − nv, λk > n)|
≤ 2E∞
[ ∣∣Eω0 (Xn −Xλk − (n− λk)v, λk ≤ n)− Eω0 (λkv, λk ≤ n) + Eω0 (Xλk , λk ≤ n)2
n2E∞[P
0 (λk > n)]
≤ 8E∞
[ ∣∣∣
0≤m≤n
x·û≥k
P ω0 (Xm = x, λk = m)E
x {Xn−m − x− (n−m)v}
+ Ŏ (k2 + n2esk(1− sδ/2)n).
(5.4)
The last error term above is Ŏ (n2ρ). We used the Cauchy-Schwarz inequality and
Hypothesis (M) to get the second term in the first inequality, and then (3.1), (3.4),
and (3.5) in the last inequality.
18 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
To handle the expectation on line (5.4) we introduce a spanning set of vectors
that satisfy the main assumptions that û does. Namely, let {ûi}di=1 span Rd and
satisfy these conditions: |û − ûi| ≤ δ/(2M), where δ and M are the constants from
Hypotheses (N) and (M), and
αiûi with αi > 0. (5.5)
Then non-nestling (N) holds for each ûi with constant δ/2, and all the conclusions
of Lemma 3.1 hold when û is replaced by ûi and δ by δ/2. Define the event Ak =
{infiXi · û ≥ k} and the set
Λ = {x ∈ Zd : min
x · ûi ≥ 1}.
The point of introducing Λ is that the number of points x in Λ on level x · û = ℓ > 0
is of order Ŏ (ℓd−1).
By Jensen’s inequality the expectation on line (5.4) is bounded by
x∈Λ, x·û≥k
0≤m≤n
P ω0 (Xm = x, λk = m)
∣∣Eωx {Xn−m − x− (n−m)v, Ak/2}
(5.6)
0≤m≤n
x 6∈Λ
P ω0 (Xm = x, λk = m)
∣∣Eωx {Xn−m − x− (n−m)v}
+ 2E∞
0≤m≤n
x·û≥k
P ω0 (Xm = x, λk = m)
∣∣Eωx {Xn−m − x− (n−m)v, Ack/2}
By Cauchy-Schwarz, Hypothesis (M) and (3.1), the third term is Ŏ (n2e−sk/2) =
Ŏ (1). The second term is of order
n2max
0 (Xλk · ûi < 1)] ≤ n2max
P ω0 (Xm · ûi < 1)P ω0 (Xm · û ≥ k)
)1/2 ]
≤ es/2n2
(1− sδ/4)m/2e−µk/2eµM |û|m/2
= Ŏ (n2e−µk/2) = Ŏ (1),
for µ small enough. It remains to bound the term on line (5.6). To this end, by
Cauchy-Schwarz, (3.2) and (3.1),
P ω0 (Xm = x, λk = m) ≤ {e−sx·û/2esM |û|m/2∧1}×{eµk/2(1−µδ/2)(m−1)/2∧1} ≡ px,m,k.
Notice that ∑
{e−sx·û/2esM |û|m/2 ∧ 1} = Ŏ (md)
QUENCHED FUNCTIONAL CLT FOR RWRE 19
and ∑
md{eµk/2(1− µδ/2)(m−1)/2 ∧ 1} = Ŏ (kd+1).
Substitute these back into line (5.6) to eliminate the quenched probability coefficients.
The quenched expectation in (5.6) is Sk/2-measurable. Consequently variation dis-
tance bound (4.1) allows us to switch back to P and get this upper bound for line
(5.6):
x∈Λ, x·û≥k
0≤m≤n
px,m,kE[|Eωx {Xn−m − x− (n−m)v, Ak/2}|2] + Ŏ (kd+1n2e−ck/2).
The error term is again Ŏ (1).
Now insert Ac
back inside the quenched expectation, incurring another error term
of order Ŏ (kd+1n2e−sk/2) = Ŏ (1). Using the shift-invariance of P, along with (5.3),
and collecting all of the above error terms, we get
|Eω0 (Xn − nv)|
x∈Λ, x·û≥k
0≤m≤n
px,m,kE[ |Eωx {Xn−m − x− (n−m)v}|2] + Ŏ (n2ρ)
= Ŏ (kd+1n2ᾱ + n2ρ) = Ŏ (nρ(d+1)+2ᾱ).
Pick ρ > 0 small enough so that 2α = ρ(d + 1) + 2ᾱ < 1. The conclusion (2.1)
follows. �
Once we have verified the assumptions of Theorem 2.1 we have the CLT under
P∞-almost every ω. But we want the CLT under P-almost every ω. Thus as the final
point of this section we prove the transfer of the central limit theorem from P∞ to P.
This is where we use the ergodic theorem, Theorem 4.2. Let W be the probability
distribution of the Brownian motion with diffusion matrix D.
Lemma 5.3. Suppose the weak convergence Qωn ⇒ W holds for P∞-almost every ω.
Then the same is true for P-almost every ω.
Proof. It suffices to show that for any bounded uniformly continuous F on DRd[0,∞)
and any δ > 0
Eω0 [F (Bn)] ≤
F dW + δ P-a.s.
By considering also −F this gives Eω0 [F (Bn)] →
F dW P0-a.s. for each such func-
tion. A countable collection of them determines weak convergence.
Fix such an F . Let c =
F dW and
h(ω) = lim
Eω0 [F (Bn)].
20 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
For ℓ > 0 define the events
A−ℓ = {inf
Xn · û ≥ −ℓ}
and then
hℓ(ω) = lim
Eω0 [F (Bn), A−ℓ] and Ψ(ω) = 1I{ω : h̄ℓ(ω) ≤ c+ 12δ}.
The assumed quenched CLT under P∞ gives P∞{h = c} = 1. By (3.1), and by its
extension to P∞ in Theorem 4.1(c), there are constants 0 < C, s <∞ such that
|h(ω)− hℓ(ω)| ≤ Ce−sℓ
uniformly over all ω that support both P and P∞. Consequently if δ > 0 is given,
E∞Ψ = 1 for large enough ℓ. Since Ψ is S−ℓ-measurable Theorem 4.2 implies that
Ψ(TXjω) → 1 P0-a.s.
By increasing ℓ if necessary we can ensure that {h̄ℓ ≤ c + 12δ} ⊂ {h̄ ≤ c + δ} and
conclude that the stopping time
ζ = inf{n ≥ 0 : h̄(TXnω) ≤ c+ δ}
is P0-a.s. finite. From the definitions we now have
0 [F (Bn)] ≤
F dW + δ P0-a.s.
Then by bounded convergence
Eω0 E
0 [F (Bn)] ≤
F dW + δ P-a.s.
Since ζ is a finite stopping time, the strong Markov property, the uniform continuity
of F and the exponential moment bound (3.2) on X-increments imply
Eω0 [F (Bn)] ≤
F dW + δ P-a.s.
This concludes the proof. �
6. Reduction to path intersections
The preceding sections have reduced the proof of the main result Theorem 1.1 to
proving the estimate
|Eω0 (Xn)−E0(Xn)|
= Ŏ (n2α) for some α < 1/2. (6.1)
The next reduction takes us to the expected number of intersections of the paths of
two independent walks X and X̃ in the same environment. The argument uses a de-
composition into martingale differences through an ordering of lattice sites. This idea
QUENCHED FUNCTIONAL CLT FOR RWRE 21
for bounding a variance is natural and has been used in RWRE earlier by Bolthausen
and Sznitman [2].
Let P ω0,0 be the quenched law of the walks (X, X̃) started at (X0, X̃0) = (0, 0) and
P0,0 =
P ω0,0 P(dω) the averaged law with expectation operator E0,0. The set of sites
visited by a walk is denoted by X[0,n) = {Xk : 0 ≤ k < n} and |A| is the number of
elements in a discrete set A.
Proposition 6.1. Let P be an i.i.d. product measure and satisfy Hypotheses (N) and
(M). Assume that there exists an ᾱ < 1/2 such that
E0,0(|X[0,n) ∩ X̃[0,n)|) = Ŏ (n2ᾱ). (6.2)
Then condition (6.1) is satisfied.
Proof. For L ≥ 0, define B(L) = {x ∈ Zd : |x| ≤ L}. Fix n ≥ 1, c > |û|, and let
(xj)j≥1 be some fixed ordering of B(cMn) satisfying
∀i ≥ j : xi · û ≥ xj · û.
For B ⊂ Zd let SB = σ{ωx : x ∈ B}. Let Aj = {x1, . . . , xj}, ζ0 = E0(Xn), and for
j ≥ 1
ζj = E(E
0 (Xn)|SAj).
(ζj − ζj−1)j≥1 is a sequence of L2(P)-martingale differences and we have
E[ |Eω0 (Xn)− E0(Xn)| 2] (6.3)
|E0(Xn)− E{Eω0 (Xn)|SB(cMn)}|2
[ ∣∣Eω0 (Xn,max
|Xi| > cMn)
− E{Eω0 (Xn,max
|Xi| > cMn) |SB(cMn)}
∣∣2 ]
|B(cMn)|∑
E( |ζj − ζj−1|2 ) + Ŏ (n3e−sM(c−|û|)n). (6.4)
In the last inequality we have used (3.2). The error is Ŏ (1). For z ∈ Zd define
half-spaces
H(z) = {x ∈ Zd : x · û > z · û}.
Since Aj−1 ⊂ Aj ⊂ H(xj)c,
E(|ζj − ζj−1|2)
P(dωAj)
P(dωAc
)P(dω̃xj)
Eω0 (Xn)− E
〈ω,ω̃xj 〉
0 (Xn)
P(dωH(xj)c)P(dω̃xj)
P(dωH(xj))
Eω0 (Xn)− E
〈ω,ω̃xj 〉
0 (Xn)
. (6.5)
Above 〈ω, ω̃xj〉 denotes an environment obtained from ω by replacing ωxj with ω̃xj .
22 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
We fix a point z = xj to develop a bound for the expression above, and then return
to collect the estimates. Abbreviate ω̃ = 〈ω, ω̃xj〉. Consider two walks Xn and X̃n
starting at 0. Xn obeys environment ω, while X̃n obeys ω̃. We can couple the two
walks so that they stay together until the first time they visit z. Until a visit to z
happens, the walks are identical. So we write
P(dωH(z))
Eω0 (Xn)− Eω̃0 (Xn)
(6.6)
P(dωH(z))
P ω0 (Hz = m)
Eωz (Xn−m − z)− Eω̃z (Xn−m − z)
P(dωH(z))
P ω0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
Eωz (Xn−m − z)− Eω̃z (Xn−m − z)
(6.7)
Decompose H(z) = Hℓ(z) ∪H′ℓ(z) where
Hℓ(z) = {x ∈ Zd : z · û < x · û < z · û+ ℓ} and H′ℓ(z) = {x ∈ Zd : x · û ≥ z · û+ ℓ}.
Take a single (ℓ,m) term from the sum in (6.7) and only the expectation Eωz (Xn−m−
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
×Eωz (Xn−m − z)
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
×Eωz (Xτ (ℓ)1 +n−m −Xτ (ℓ)1 )
(6.8)
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
×Eωz (Xn−m −Xτ (ℓ)1 +n−m +Xτ (ℓ)1 − z)
(6.9)
The parameter ℓ in the regeneration time τ
1 of the walk started at z ensures that the
subsequent walkX
1 + ·
stays inH′ℓ(z). Below we make use of this to get independence
from the environments in H′ℓ(z)c. By (3.9) the quenched expectation in (6.9) can be
bounded by Cpℓ
p, for any p > 1.
QUENCHED FUNCTIONAL CLT FOR RWRE 23
Integral (6.8) is developed further as follows.
P(dωH(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
× Eωz (Xτ (ℓ)1 +n−m −Xτ (ℓ)1 )
P(dωHℓ(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
P(dωH′
(z))E
z (Xτ (ℓ)1 +n−m
P(dωHℓ(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
× Ez(Xτ (ℓ)1 +n−m −Xτ (ℓ)1 |SH′ℓ(z)c)
P(dωHℓ(z))P
0 (Hz = m, ℓ− 1 ≤ max
0≤j≤m
Xj · û− z · û < ℓ)
× E0(Xn−m|β = ∞).
(6.10)
The last equality above comes from the regeneration structure, see Proposition 1.3 in
Sznitman-Zerner [17]. The σ-algebra SH′
(z)c is contained in the σ-algebra G1 defined
by (1.22) of [17] for the walk starting at z.
The last quantity (6.10) above reads the environment only until the first visit to z,
hence does not see the distinction between ω and ω̃. Hence when the integral (6.7) is
developed separately for ω and ω̃ into the sum of integrals (6.8) and (6.9), integrals
(6.8) for ω and ω̃ cancel each other. We are left only with two instances of integral
(6.9), one for both ω and ω̃. The last quenched expectation in (6.9) we bound by
p as was mentioned above.
Going back to (6.6), we get this bound:
P(dωH(z))
Eω0 (Xn)− Eω̃0 (Xn)
P(dωH(z))
ℓpP ω0 (Hz < n, ℓ− 1 ≤ max
0≤j≤Hz
Xj · û− z · û < ℓ)
P(dωH(z))E
0 [(MHz − z · û)p1I{Hz < n}]
≤ Cpnpε
P(dωH(z))P
0 (Hz < n) + Cps
−pe−sn
For the last inequality we used (3.6) with ℓ = nε and some small ε, s > 0. Square,
take z = xj , integrate as in (6.5), and use Jensen’s inequality to bring the square
inside the integral to get
E( |ζj − ζj−1|2 ) ≤ 2Cpn2pεE[ |P ω0 (Hxj < n)|2 ] + 2Cps−2pe−sn
24 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Substitute these bounds into line (6.4) and note that the error there is Ŏ (1).
E[ |Eω0 (Xn)−E0(Xn)|2 ]
≤ Cpn2pε
E[ |P ω0 (Hz < n)|2 ] + Ŏ (nds−2pe−sn
) + Ŏ (1)
= Cpn
P0,0(z ∈ X[0,n) ∩ X̃[0,n)) + Ŏ (1)
= Cpn
2pεE0,0[ |X[0,n) ∩ X̃[0,n)| ] + Ŏ (1).
Utilize assumption (6.2) and take ε > 0 small enough so that 2α = 2pε + 2ᾱ < 1.
(6.1) has been verified. �
7. Bound on intersections
The remaining piece of the proof of Theorem 1.1 is this estimate:
E0,0( |X[0,n) ∩ X̃[0,n)| ) = Ŏ (n2α) for some α < 1/2. (7.1)
X and X̃ are two independent walks in a common environment with quenched
distribution P ωx,y[X0,∞ ∈ A, X̃0,∞ ∈ B] = P ωx (A)P ωy (B) and averaged distribution
Ex,y(·) = EP ωx,y(·).
To deduce the sublinear bound we introduce regeneration times at which both
walks regenerate on the same level in space (but not necessarily at the same time).
Intersections happen only within the regeneration slabs, and the expected number
of intersections decays exponentially in the distance between the points of entry of
the walks in the slab. From regeneration to regeneration the difference of the two
walks operates like a Markov chain. This Markov chain can be approximated by
a symmetric random walk. Via this preliminary work the required estimate boils
down to deriving a Green function bound for a Markov chain that can be suitably
approximated by a symmetric random walk. This part is relegated to an appendix.
Except for the appendix, we complete the proof of the functional central limit theorem
in this section.
To aid our discussion of a pair of walks (X, X̃) we introduce some new notation.
We write θm,n for the shift on pairs of paths: θm,n(x0,∞, y0,∞) = (θ
mx0,∞, θ
ny0,∞). If
we write separate expectations for X and X̃ under P ωx,y, these are denoted by E
x and
Ẽωy .
By a joint stopping time we mean pair (α, α̃) that satisfies {α = m, α̃ = n} ∈
σ{X0,m, X̃0,n}. Under the distribution P ωx,y the walks X and X̃ are independent.
Consequently if α ∨ α̃ <∞ P ωx,y-almost surely then for any events A and B,
P ωx,y[(X0,α, X̃0,α̃) ∈ A, (Xα,∞, X̃α̃,∞) ∈ B]
= Eωx,y
1I{(X0,α, X̃0,α̃) ∈ A}P ωXα, eXα̃{(X0,∞, X̃0,∞) ∈ B}
QUENCHED FUNCTIONAL CLT FOR RWRE 25
This type of joint restarting will be used without comment in the sequel.
For this section it will be convenient to have level stopping times and running
maxima that are not defined relative to the initial level.
γℓ = inf{n ≥ 0 : Xn · û ≥ ℓ} and γ+ℓ = inf{n ≥ 0 : Xn · û > ℓ}.
Since û ∈ Zd, γ+ℓ is simply an abbreviation for γℓ+1. Let Mn = sup{Xi · û : i ≤ n}
be the running maximum. M̃n, γ̃ℓ and γ̃
ℓ are the corresponding quantities for the X̃
walk. The first backtracking time for the X̃ walk is β̃ = inf{n ≥ 1 : X̃n · û < X̃0 · û}.
Define
L = inf{ℓ > (X0 · û) ∧ (X̃0 · û) : Xγℓ · û = X̃γ̃ℓ · û = ℓ}
as the first fresh common level after at least one walk has exceeded its starting level.
Set L = ∞ if there is no such common level. When the walks are on a common level,
their difference will lie in the hyperplane
Vd = {z ∈ Zd : z · û = 0}.
We start with exponential tail bounds on the time to reach the common level.
Lemma 7.1. There exist constants 0 < a1, a2, C < ∞ such that, for all x, y ∈ Zd,
m ≥ 0 and P-a.e. ω,
P ωx,y(γL ∨ γ̃L ≥ m) ≤ Cea1|y·û−x·û|−a2m. (7.2)
For the proof we need a bound on the overshoot.
Lemma 7.2. There exist constants 0 < C, s < ∞ such that, for any level k, any
b ≥ 1, any x ∈ Zd such that x · û ≤ k, and P-a.e. ω,
P ωx [Xγk · û ≥ k + b] ≤ Ce−sb. (7.3)
Proof. From (3.1) it follows that for a constant C, for any level ℓ, any x ∈ Zd, and
P-a.e. ω,
Eωx [number of visits to level ℓ] =
P ωx [Xn · û = ℓ] ≤ C. (7.4)
(This is certainly clear if x · û = ℓ. Otherwise wait until the process first lands on
level ℓ, if ever.)
26 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
From this and the exponential moment hypothesis we deduce the required bound
on the overshoots: for any k, any x ∈ Zd such that x · û ≤ k, and P-a.e. ω,
P ωx [Xγk · û ≥ k + b] =
z·û<k
P ωx [γk > n, Xn = z, Xn+1 · û ≥ k + b]
z·û=k−ℓ
P ωx [γk > n, Xn = z]P
z [X1 · û ≥ k + b]
z·û=k−ℓ
P ωx [Xn = z]Ce
−s(ℓ+b)
≤ Ce−sb
e−sℓ ≤ Ce−sb. �
Proof of Lemma 7.1. Consider first γL, and let us restrict ourselves to the case where
the initial points x, y satisfy x · û < y · û.
Perform an iterative construction of stopping times ηi, η̃i and levels ℓ(i), ℓ̃(i). Let
η0 = η̃0 = 0, x0 = x and y0 = y. ℓ(0) and ℓ̃(0) need not be defined. Suppose that
the construction has been done to stage i − 1 with xi−1 = Xηi−1 , yi−1 = X̃η̃i−1 , and
xi−1 · û < yi−1 · û. Then set
ℓ(i) = Xγ(yi−1·û) · û, ℓ̃(i) = X̃γ̃(ℓ(i)) · û, ηi = γ(ℓ̃(i)) and η̃i = γ̃(Xηi · û+ 1).
In words, starting at (xi−1, yi−1) with yi−1 above xi−1, let X reach the level of yi−1
and let ℓ(i) be the level X lands on; let X̃ reach the level ℓ(i) and let ℓ̃(i) be the level
X̃ lands on. Now let X try to establish a new common level at ℓ̃(i) with X̃ : in other
words, follow X until the time ηi it reaches level ℓ̃(i) or above, and stop it there.
Finally, reset the situation by letting X̃ reach a level strictly above the level of Xηi ,
and stop it there at time η̃i. The starting locations for the next step are xi = Xηi ,
yi = X̃η̃i that satisfy xi · û < yi · û.
We show that within each step of the iteration there is a uniform lower bound on
the probability that a fresh common level was found. For this purpose we utilize
assumption (1.1) in the weaker form
P{ω : P ω0 (Xγ1 · û = 1) ≥ κ } = 1. (7.5)
Pick b large enough so that the bound in (7.3) is < 1. For z, w ∈ Zd such that
z · û ≥ w · û define a function
ψ(z, w) = P ωz,w[ Xγk · û = k for each k ∈ {z · û, . . . , z · û+ b},
X̃γ̃(z·û) · û− z · û ≤ b ]
≥ κb(1− Ce−sb) ≡ κ2 > 0.
QUENCHED FUNCTIONAL CLT FOR RWRE 27
The uniform lower bound comes from the independence of the walks, from (7.3) and
from iterating assumption (7.5). By the Markov property
P ωxi−1,yi−1[Xγ(ℓ̃(i)) · û = ℓ̃(i)]
≥ P ωxi−1,yi−1[ X̃γ̃(ℓ(i)) · û− ℓ(i) ≤ b, Xγk · û = k for each k ∈ {ℓ(i), . . . , ℓ(i) + b} ]
≥ Eωxi−1,yi−1
ψ(Xγ(yi−1·û), yi−1)
≥ κ2.
The first iteration on which the attempt to create a common level at ℓ̃(i) succeeds
I = inf{i ≥ 1 : Xγ
ℓ̃(i)
· û = ℓ̃(i)}.
Then ℓ̃(I) is a new fresh common level and consequently L ≤ ℓ̃(I). This gives the
upper bound
γL ≤ γℓ̃(I).
We develop an exponential tail bound for γℓ̃(I), still under the assumption x · û < y · û.
From the uniform bound above and the Markov property we get
P ωx,y[I > i] ≤ (1− κ2)i.
Lemma 7.2 gives an exponential bound
P ωx,y
(X̃η̃i − X̃η̃i−1) · û ≥ b
≤ Ce−sb (7.6)
because the distance (X̃η̃i − X̃η̃i−1) · û is a sum of four overshoots:
X̃η̃i − X̃η̃i−1
· û =
X̃γ̃(Xηi ·û+1) · û−Xηi · û− 1
+ 1 +
Xγ(ℓ̃(i)) · û− ℓ̃(i)
X̃γ̃(ℓ(i)) · û− ℓ(i)
γ( eXη̃i−1 ·û)
· û− X̃η̃i−1 · û
Next, from the exponential tail bound on
X̃η̃i − X̃η̃i−1
· û and from
ℓ̃(i) ≤ X̃η̃i · û =
X̃η̃j − X̃η̃j−1
· û+ y · û
we get the large deviation estimate
P ωx,y[ℓ̃(i) ≥ bi+ y · û] ≤ e−sbi for i ≥ 1 and b ≥ b0,
for some constants 0 < s < ∞ (small enough) and 0 < b0 < ∞ (large enough).
Combine this with the bound above on I to write
P ωx,y[ℓ̃(I) ≥ a] ≤ P ωx,y[I > i] + P ωx,y[ℓ̃(i) ≥ a]
≤ e−si + esy·û−sa ≤ 2esy·û−sa
where we assume a ≥ 2b0 + y · û and set the integer i = ⌊b−10 (a− y · û)⌋. Recall that
0 < s <∞ is a constant whose value can change from line to line.
28 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
From (3.1) and an exponential Chebyshev
P ωx,y[γk > m] ≤ P ωx [Xm · û ≤ k] ≤ esk−sx·û−h1m
for all x, y ∈ Zd, k ∈ Z and m ≥ 0. Above and in the remainder of this proof h1, h2
and h3 are small positive constants. Finally we derive
P ωx,y[γℓ̃(I) > m] ≤ P ωx,y[ℓ̃(I) ≥ k + x · û] + P ωx,y[γk+x·û > m]
≤ 2es(y−x)·û−sk + esk−h1m ≤ Ces(y−x)·û−h2m.
To justify the inequalities above assume m ≥ 4sb0/h1 > 4s/h1 and pick k in the
range
+ (y − x) · û ≤ k ≤ 3h1m
+ (y − x) · û.
To summarize, at this point we have
P ωx,y[γL > m] ≤ Ces(y−x)·û−h2m for x · û < y · û. (7.7)
To extend this estimate to the case x · û ≥ y · û, simply allow X̃ to go above x and
then apply (7.7). By an application of the overshoot bound (7.3) and (7.7) at the
point (x, X̃γ̃(x·û+1))
P ωx,y[γL > m] ≤ Eωx,yP ωx, eXγ̃(x·û+1)[γL > m]
≤ P ωx,y[X̃γ̃(x·û+1) > x · û+ εm] + Cesεm−h2m ≤ Ce−h3m
if we take ε > 0 small enough.
We have proved the lemma for γL, and the same argument works for γ̃L. �
Assuming that X0 · û = X̃0 · û define the joint stopping times
(ρ, ρ̃) = (γ+
, γ̃+
(ν1, ν̃1) =
(ρ, ρ̃) + (γL, γ̃L) ◦ θρ,ρ̃ if ρ ∨ ρ̃ <∞
∞ if ρ = ρ̃ = ∞.
(7.8)
Notice that ρ and ρ̃ are finite or infinite together, and they are infinite iff neither
walk backtracks below its initial level (β = β̃ = ∞). Let ν0 = ν̃0 = 0 and for k ≥ 0
define
(νk+1, ν̃k+1) = (νk, ν̃k) + (ν1, ν̃1) ◦ θνk,ν̃k .
Finally let (ν, ν̃) = (γL, γ̃L), K = sup{k ≥ 0 : νk ∨ ν̃k <∞}, and
(µ1, µ̃1) = (ν, ν̃) + (νK , ν̃K) ◦ θν,ν̃ . (7.9)
These represent the first common regeneration times of the two paths. Namely,
Xµ1 · û = X̃µ̃1 · û and for all n ≥ 1,
Xµ1−n · û < Xµ1 · û ≤ Xµ1+n · û and X̃µ̃1−n · û < X̃µ̃1 · û ≤ X̃µ̃1+n · û.
QUENCHED FUNCTIONAL CLT FOR RWRE 29
Next we extend the exponential tail bound to the regeneration times.
Lemma 7.3. There exist constants 0 < C < ∞ and η̄ ∈ (0, 1) such that, for all
x, y ∈ Vd = {z ∈ Zd : z · û = 0}, k ≥ 0, and P-a.e. ω, we have
P ωx,y(µ1 ∨ µ̃1 ≥ k) ≤ C(1− η̄)k. (7.10)
Proof. We prove geometric tail bounds successively for γ+1 , γ
ℓ , γ
, ρ, ν1, νk, and
finally for µ1. To begin, (3.1) implies that
P ω0 (γ
1 ≥ n) ≤ P ω0 (Xn−1 · û ≤ 1) ≤ es2(1− η1)n−1
with η1 = s2δ/2, for some small s2 > 0. By summation by parts
Eω0 (e
1 ) ≤ es2Js3 ,
for a small enough s3 > 0 and Js = 1 + (e
s − 1)/(1 − (1 − η1)es). By the Markov
property for ℓ ≥ 1,
Eω0 (e
ℓ ) ≤
x·û>ℓ−1
Eω0 (e
ℓ−1 , Xγ+
= x)Eωx (e
But if x · û > ℓ− 1, then Eωx (es3γ
ℓ ) ≤ ETxω0 (es3γ
1 ). Therefore by induction
Eω0 (e
ℓ ) ≤ (es2Js3)ℓ for any integer ℓ ≥ 0. (7.11)
Next for an integer r ≥ 1,
Eω0 (e
Mr ) =
Eω0 (e
ℓ ,Mr = ℓ) ≤
Eω0 (e
ℓ )1/2P ω0 (Mr = ℓ)
(es2J2s4)
ℓ/2(1I{ℓ < 3Mr|û|}+ e−s5ℓ)1/2 ≤ C(es2J2s4)Cr,
for some C and for positive but small enough s2, s4, and s5. In the last inequality
above we used the fact that es2J2s4 converges to 1 as first s4 ց 0 and then s2 ց 0.
In the second-to-last inequality we used (3.2) to get the bound
P ω0 (Xi · û ≥ ℓ) ≤
e−sℓeM |û|si ≤ Ce−s5ℓ if ℓ ≥ 3M |û|r.
Above we assumed that the walk X starts at 0. Same bounds work for any x ∈ Vd
because a shift orthogonal to û does not alter levels, in particular P ωx (Mr = ℓ) =
P Txω0 (Mr = ℓ).
By this same observation we show that for all x, y ∈ Vd
Eωx,y(e
fMr ) ≤ C(es2J2s4)Cr
by repeating the earlier series of inequalities.
30 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Using (3.1) and these estimates gives for x, y ∈ Vd
P ωx,y(ρ ≥ n, β ∧ β̃ <∞) =
P ωx,y(γ
Mr∨fMr
≥ n, β ∧ β̃ = r)
≤ e−s4n/2
1≤r≤εn
Eωx (e
Mr )1/2Eωx,y(e
fMr )1/2
P ωx {Xr · û < x · û}+ P ωy {X̃r · û < y · û}
≤ Cεne−s4n/2(es2J2s4)Cεn + C(1− s6δ/2)εn.
Taking ε > 0 small enough shows the existence of a constant η2 > 0 such that for all
x, y ∈ Vd, n ≥ 1, and P-a.e. ω,
P ωx,y(ρ ≥ n, β ∧ β̃ <∞) ≤ C(1− η2)n.
Same bound works for ρ̃ also. We combine this with (7.2) to get a geometric tail
bound for ν11I{β ∧ β̃ <∞}. Recall definition (7.8) and take ε > 0 small.
P ωx,y[ν1 ≥ k, β ∧ β̃ <∞]
≤ P ωx,y[ρ ≥ k/2, β ∧ β̃ <∞] + P ωx,y[β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| > εk]
+ P ωx,y[γL ◦ θρ,ρ̃ ≥ k/2, β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| ≤ εk ].
On the right-hand side above we have an exponential bound for each of the three
probabilities: the first probability gets it from the estimate immediately above, the
second from a combination of that and (3.2), and the third from (7.2):
P ωx,y[γL ◦ θρ,ρ̃ ≥ k/2, β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| ≤ εk ]
= Eωx,y
1I{β ∧ β̃ <∞, |Xρ · û− X̃ρ̃ · û| ≤ εk}P ωXρ , eXρ̃{γL ≥ k/2}
≤ Cea1εk−a2k/2.
The constants in the last bound above are those from (7.2), and we choose ε <
a2/(2a1). We have thus established that
Eωx,y(e
s7ν11I{β ∧ β̃ <∞}) ≤ J̄s7
for a small enough s7 > 0, with J̄s = C(1− (1− η3)es)−1 and η3 > 0.
To move from ν1 to νk use the Markov property and induction:
Eωx,y(e
s7νk1I{νk ∨ ν̃k <∞})
Eωx,y(e
s7νk−11I{νk−1 ∨ ν̃k−1 <∞, Xνk−1 = z, X̃ν̃k−1 = z̃})
× Eωz,z̃(es7ν11I{β ∧ β̃ <∞})
≤ J̄s7Eωx,y(es7νk−11I{νk−1 ∨ ν̃k−1 <∞}) ≤ · · · ≤ J̄ks7.
QUENCHED FUNCTIONAL CLT FOR RWRE 31
Next, use the Markov property at the joint stopping times (νk, ν̃k), (7.2), (3.7),
and induction to derive
P ωx,y(K ≥ k) ≤ P ωx,y(νk ∨ ν̃k <∞)
P ωx,y(νk−1 ∨ ν̃k−1 <∞, Xνk−1 = z, X̃ν̃k−1 = z̃)P ωz,z̃(β ∧ β̃ <∞)
≤ (1− η2)P ωx,y(νk−1 ∨ ν̃k−1 <∞) ≤ (1− η2)k.
Finally use the Cauchy-Schwarz and Chebyshev inequalities to write
P ωx,y(νK ≥ n) =
P ωx,y(νk ≥ n,K = k)
(1− η2)k + e−s7n
1≤k≤εn
Eωx,y(e
s7νk1I{νk ∨ ν̃k <∞})
≤ C(1− η2)εn + Cεne−s7nJ̄εns7 .
Looking at the definition (7.9) of µ1 we see that an exponential tail bound follows by
applying (7.2) to the ν-part and by taking ε > 0 small enough in the last calculation
above. Repeat the same argument for µ̃1 to conclude the proof of (7.10). �
After these preliminaries define the sequence of common regeneration times by
µ0 = µ̃0 = 0 and
(µi+1, µ̃i+1) = (µi, µ̃i) + (µ1, µ̃1) ◦ θµi,µ̃i. (7.12)
The next tasks are to identify suitable Markovian structures and to develop a cou-
pling.
Proposition 7.4. The process (X̃µ̃i−Xµi)i≥1 is a Markov chain on Vd with transition
probability
q(x, y) = P0,x[X̃µ̃1 −Xµ1 = y | β = β̃ = ∞]. (7.13)
Note that the time-homogeneous Markov chain does not start from X̃0−X0 because
the transition to X̃µ̃1 −Xµ1 does not include the condition β = β̃ = ∞.
Proof. Express the iteration of the common regeneration times as
(µi, µ̃i) = (µi−1, µ̃i−1) +
(ν, ν̃) + (νK , ν̃K) ◦ θν,ν̃
◦ θµi−1,µ̃i−1 , i ≥ 1.
Let Ki be the value of K at the ith iteration:
Ki = K ◦ θν,ν̃ ◦ θµi−1,µ̃i−1 .
32 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Let n ≥ 2 and z1, . . . , zn ∈ Vd. Write
P0,z[X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n] (7.14)
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
Ki = ki, µi = mi, µ̃i = m̃i,
Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1,
(X̃µ̃1 −Xµ1) ◦ θmn−1,m̃n−1 = zn
Above Ψ is the set of vectors (ki, mi, m̃i, vi, ṽi)1≤i≤n−1 such that ki is nonnegative and
mi, m̃i, vi · û, and ṽi · û are all positive and strictly increasing in i, and ṽi − vi = zi.
Define the events
Ak,b,b̃ = {ν + νk ◦ θν,ν̃ = b , ν̃ + ν̃k ◦ θν,ν̃ = b̃}
Bb,b̃ = {Xj · û ≥ X0 · û for 1 ≤ j ≤ b , X̃j · û ≥ X̃0 · û for 1 ≤ j ≤ b̃}.
Let m0 = m̃0 = 0, bi = mi −mi−1 and b̃i = m̃i − m̃i−1. Rewrite the sum from above
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
[ n−1∏
1I{Aki,bi,b̃i} ◦ θ
mi−1,m̃i−1
1I{Bbi, b̃i} ◦ θ
mi−1,m̃i−1 , Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1,
β ◦ θmn−1 = β̃ ◦ θm̃n−1 = ∞ , (X̃µ̃1 −Xµ1) ◦ θmn−1,m̃n−1 = zn
Next restart the walks at times (mn−1, m̃n−1) to turn the sum into the following.
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
Eω0,z
[ n−1∏
1I{Aki,bi,b̃i} ◦ θ
mi−1,m̃i−1
1I{Bbi, b̃i} ◦ θ
mi−1,m̃i−1 , Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1
× P ωvn−1 , ṽn−1
β = β̃ = ∞ , X̃µ̃1 −Xµ1 = zn
Inside the outermost braces the events in the first quenched expectation force the
level
ℓ = Xmn−1 · û = vn−1 · û = X̃m̃n−1 · û = ṽn−1 · û
QUENCHED FUNCTIONAL CLT FOR RWRE 33
to be a new maximal level for both walks. Consequently the first quenched expecta-
tion is a function of {ωx : x · û < ℓ} while the last quenched probability is a function
of {ωx : x · û ≥ ℓ}. By independence of the environments, the sum becomes
(ki,mi,m̃i,vi,ṽi)1≤i≤n−1∈Ψ
[ n−1∏
1I{Aki,bi,b̃i} ◦ θ
mi−1,m̃i−1 (7.15)
1I{Bbi, b̃i} ◦ θ
mi−1,m̃i−1 , Xmi = vi and X̃m̃i = ṽi for 1 ≤ i ≤ n− 1
× Pvn−1 , ṽn−1
β = β̃ = ∞ , X̃µ̃1 −Xµ1 = zn
By a shift and a conditioning the last probability transforms as follows.
Pvn−1 , ṽn−1
β = β̃ = ∞ , X̃µ̃1 −Xµ1 = zn
= P0,zn−1
X̃µ̃1 −Xµ1 = zn
∣∣ β = β̃ = ∞
Pvn−1 , ṽn−1
β = β̃ = ∞
= q(zn−1, zn)Pvn−1 , ṽn−1
β = β̃ = ∞
Now reverse the above use of independence to put the probability
Pvn−1 , ṽn−1 [β = β̃ = ∞]
back together with the expectation (7.15). Inside this expectation this furnishes the
event β ◦ θmn−1 = β̃ ◦ θm̃n−1 = ∞ and with this the union of the entire collection of
events turns back into X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n−1. Going back to the beginning
on line (7.14) we see that we have now shown
P0,z[X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n]
= P0,z[X̃µ̃i −Xµi = zi for 1 ≤ i ≤ n− 1]q(zn−1, zn).
Continue by induction. �
The Markov chain Yk = X̃µ̃k − Xµk will be compared to a random walk obtained
by performing the same construction of joint regeneration times to two independent
walks in independent environments. To indicate the difference in construction we
change notation. Let the pair of walks (X, X̄) obey P0 ⊗Pz with z ∈ Vd, and denote
the first backtracking time of the X̄ walk by β̄ = inf{n ≥ 1 : X̄n · û < X̄0 · û}.
Construct the common regeneration times (ρk, ρ̄k)k≥1 for (X, X̄) by the same recipe
[(7.8), (7.9) and (7.12)] as was used to construct (µk, µ̃k)k≥1 for (X, X̃). Define
Ȳk = X̄ρ̄k − Xρk . An analogue of the previous proposition, which we will not spell
out, shows that (Ȳk)k≥1 is a Markov chain with transition
q̄(x, y) = P0 ⊗ Px[X̄ρ̄1 −Xρ1 = y | β = β̄ = ∞]. (7.16)
34 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
In the next two proofs we make use of the following decomposition. Suppose
x · û = y · û = 0, and let (x1, y1) be another pair of points on a common, higher level:
x1 · û = y1 · û = ℓ > 0. Then we can write
{(X0, X̃0) = (x, y), β = β̃ = ∞, (Xµ1 , X̃µ̃1) = (x1, y1)}
(γ,γ̃)
{X0,n(γ) = γ, X̃0,n(γ̃) = γ̃, β ◦ θn(γ) = β̃ ◦ θn(γ̃) = ∞}. (7.17)
Here (γ, γ̃) range over all pairs of paths that connect (x, y) to (x1, y1), that stay
between levels 0 and ℓ−1 before the final points, and for which a common regeneration
fails at all levels before ℓ. n(γ) is the index of the final point along the path, so for
example γ = (x = z0, z1, . . . , zn(γ)−1, zn(γ) = x1).
Proposition 7.5. The process (Ȳk)k≥1 is a symmetric random walk on Vd and its
transition probability satisfies
q̄(x, y) = q̄(0, y − x) = q̄(0, x− y) = P0 ⊗ P0[X̄ρ̄1 −Xρ1 = y − x | β = β̄ = ∞].
Proof. It remains to show that for independent (X, X̄) the transition (7.16) reduces to
a symmetric random walk. This becomes obvious once probabilities are decomposed
into sums over paths because the events of interest are insensitive to shifts by z ∈ Vd.
P0 ⊗ Px[β = β̄ = ∞ , X̄ρ̄1 −Xρ1 = y]
P0 ⊗ Px[β = β̄ = ∞ , Xρ1 = w , X̄ρ̄1 = y + w]
(γ,γ̄)
P0[X0,n(γ) = γ, β ◦ θn(γ) = ∞]Px[X0,n(γ̄) = γ̄, β ◦ θn(γ̄) = ∞]
(γ,γ̄)
P0[X0,n(γ) = γ]Px[X0,n(γ̄) = γ̄]
P0[β = ∞]
(7.18)
Above we used the decomposition idea from (7.17). Here (γ, γ̄) range over the
appropriate class of pairs of paths in Zd such that γ goes from 0 to w and γ̄ goes from
x to y + w. The independence for the last equality above comes from noticing that
the quenched probabilities P ω0 [X0,n(γ) = γ] and P
w [β = ∞] depend on independent
collections of environments.
The probabilities on the last line of (7.18) are not changed if each pair (γ, γ̄) is
replaced by (γ, γ′) = (γ, γ̄−x). These pairs connect (0, 0) to (w, y−x+w). Because
x ∈ Vd satisfies x · û = 0, the shift has not changed regeneration levels. This shift
turns Px[X0,n(γ̄) = γ̄] on the last line of (7.18) into P0[X0,n(γ′) = γ
′]. We can reverse
the steps in (7.18) to arrive at the probability
P0 ⊗ P0[β = β̄ = ∞ , X̄ρ̄1 −Xρ1 = y − x].
This proves q̄(x, y) = q̄(0, y − x).
QUENCHED FUNCTIONAL CLT FOR RWRE 35
Once both walks start at 0 it is immaterial which is labeled X and which X̄ , hence
symmetry holds. �
It will be useful to know that q̄ inherits all possible transitions from q.
Lemma 7.6. If q(z, w) > 0 then also q̄(z, w) > 0.
Proof. By the decomposition from (7.17) we can express
Px,y[(Xµ1 , X̃µ̃1) = (x1, y1)|β = β̃ = ∞] =
(γ,γ̃)
EP ω[γ]P ω[γ̃]P ωx1 [β = ∞]P
[β = ∞]
Px,y[β = β̃ = ∞]
If this probability is positive, then at least one pair (γ, γ̃) satisfies EP ω[γ]P ω[γ̃] > 0.
This implies that P [γ]P [γ̃] > 0 so that also
Px ⊗ Py[(Xµ1 , X̃µ̃1) = (x1, y1)|β = β̃ = ∞] > 0. �
In the sequel we detach the notations Y = (Yk) and Ȳ = (Ȳk) from their original
definitions in terms of the walks X , X̃ and X̄, and use (Yk) and (Ȳk) to denote
canonical Markov chains with transitions q and q̄. Now we construct a coupling.
Proposition 7.7. The single-step transitions q(x, y) for Y and q̄(x, y) for Ȳ can be
coupled in such a way that, when the processes start from a common state x,
Px,x[Y1 6= Ȳ1] ≤ Ce−α1|x|
for all x ∈ Vd. Here C and α1 are finite positive constants independent of x.
Proof. We start by constructing a coupling of three walks (X, X̃, X̄) such that the
pair (X, X̃) has distribution Px,y and the pair (X, X̄) has distribution Px ⊗ Py.
First let (X, X̃) be two independent walks in a common environment ω as before.
Let ω̄ be an environment independent of ω. Define the walk X̄ as follows. Initially
X̄0 = X̃0. On the sites {Xk : 0 ≤ k < ∞} X̄ obeys environment ω̄, and on all other
sites X̄ obeys ω. X̄ is coupled to agree with X̃ until the time
T = inf{n ≥ 0 : X̄n ∈ {Xk : 0 ≤ k <∞}}
it hits the path of X .
The coupling between X̄ and X̃ can be achieved simply as follows. Given ω and
ω̄, for each x create two independent i.i.d. sequences (zxk )k≥1 and (z̄
k)k≥1 with distri-
butions
Qω,ω̄[zxk = y] = πx,x+y(ω) and Q
ω,ω̄[z̄xk = y] = πx,x+y(ω̄).
Do this independently at each x. Each time the X̃-walk visits state x, it uses a new
zxk variable as its next step, and never reuses the same z
k again. The X̄ walk operates
the same way except that it uses the variables z̄xk when x ∈ {Xk} and the zxk variables
when x /∈ {Xk}. Now X̄ and X̃ follow the same steps zxk until X̄ hits the set {Xk}.
It is intuitively obvious that the walksX and X̄ are independent because they never
use the same environment. The following calculation verifies this. Let X0 = x0 = x
36 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
and X̃ = X̄ = y0 = y be the initial states, and Px,y the joint measure created by the
coupling. Fix finite vectors x0,n = (x0, . . . , xn) and y0,n = (y0, . . . , yn) and recall also
the notation X0,n = (X0, . . . , Xn).
The description of the coupling tells us to start as follows.
Px,y[X0,n = x0,n, X̄0,n = y0,n] =
P(dω)
P(dω̄)
P ωx (dz0,∞)1I{z0,n = x0,n}
i:yi /∈{zk : 0≤k<∞}
πyi,yi+1(ω) ·
i:yi∈{zk: 0≤k<∞}
πyi,yi+1(ω̄)
[by dominated convergence]
= lim
P(dω)
P(dω̄)
P ωx (dz0,N) 1I{z0,n = x0,n}
i:yi /∈{zk : 0≤k≤N}
πyi,yi+1(ω) ·
i:yi∈{zk: 0≤k≤N}
πyi,yi+1(ω̄)
= lim
z0,N :z0,n=x0,n
P(dω)P ωx [X0,N = z0,N ]
i:yi /∈{zk: 0≤k≤N}
πyi,yi+1(ω)
P(dω̄)
i:yi∈{zk: 0≤k≤N}
πyi,yi+1(ω̄)
[by independence of the two functions of ω]
= lim
z0,N :z0,n=x0,n
P(dω)P ωx [X0,N = z0,N ]
P(dω)
i:yi/∈{zk : 0≤k≤N}
πyi,yi+1(ω)
P(dω̄)
i:yi∈{zk: 0≤k≤N}
πyi,yi+1(ω̄)
= Px[X0,n = x0,n] · Py[X0,n = y0,n].
Thus at this point the coupled pairs (X, X̃) and (X, X̄) have the desired marginals
Px,y and Px ⊗ Py.
Next construct the common regeneration times (µ1, µ̃1) for (X, X̃) and (ρ1, ρ̄1) for
(X, X̄) by the earlier recipes. Define two pairs of walks stopped at their common
regeneration times:
(Γ, Γ̄) ≡
(X0, µ1 , X̃0, µ̃1), (X0, ρ1 , X̄0, ρ̄1)
. (7.19)
Suppose the sets X[0, µ1∨ρ1) and X̃[0, µ̃1∨ρ̄1) do not intersect. Then the construction
implies that the path X̄0, µ̃1∨ρ̄1 agrees with X̃0, µ̃1∨ρ̄1, and this forces the equalities
(µ1, µ̃1) = (ρ1, ρ̄1) and (Xµ1 , X̃µ̃1) = (Xρ1 , X̄ρ̄1). We insert an estimate on this event.
QUENCHED FUNCTIONAL CLT FOR RWRE 37
Lemma 7.8. There exist constants 0 < C, s < ∞ such that, for all x, y ∈ Vd and
P-a.e. ω,
P ωx,y(X[0, µ1∨ρ1) ∩ X̃[0, µ̃1∨ρ̄1) 6= ∅) ≤ Ce−s|x−y|. (7.20)
Proof. Write
P ωx,y(X[0, µ1∨ρ1) ∩ X̃[0, µ̃1∨ρ̄1) 6= ∅) ≤ P ωx,y(µ1 ∨ µ̃1 ∨ ρ1 ∨ ρ̄1 > ε|x− y|)
+ P ωx ( max
1≤i≤ε|x−y|
|Xi − x| ≥ |x− y|/2)
+ P ωy ( max
1≤i≤ε|x−y|
|Xi − y| ≥ |x− y|/2).
By (7.10) and its analogue for (ρ1, ρ̄1) the first term on the right-hand-side decays
exponentially in |x − y|. Using (3.2) the second and third terms are bounded by
ε|x − y|e−s|x−y|/2eεs|x−y|M , for s > 0 small enough. Choosing ε > 0 small enough
finishes the proof. �
From (7.20) we obtain
(Xµ1 , X̃µ̃1) 6= (Xρ1, X̄ρ̄1)
≤ Px,y
Γ 6= Γ̄
≤ Ce−s|x−y|. (7.21)
But we are not finished yet: it remains to include the conditioning on no back-
tracking. For this purpose generate an i.i.d. sequence (X(m), X̃(m), X̄(m))m≥1, each
triple constructed as above. Continue to write Px,y for the probability measure of
the entire sequence. Let M be the first m such that the paths (X(m), X̃(m)) do not
backtrack, which means that
k · û ≥ X
0 · û and X̃
k · û ≥ X̃
0 · û for all k ≥ 1.
Similarly define M̄ for (X(m), X̄(m))m≥1. M and M̄ are stochastically bounded by
geometric random variables by (3.7).
The pair of walks (X(M), X̃(M)) is now distributed as a pair of walks under the
measure Px,y[ · |β = β̃ = ∞], while (X(M̄), X̄(M̄)) is distributed as a pair of walks
under Px ⊗ Py[ · |β = β̄ = ∞].
Let also again
Γ(m) = (X
0 , µ
0 , µ̃
) and Γ̄(m) = (X
0 , ρ
0 , ρ̄
be the pairs of paths run up to their common regeneration times. Consider the two
pairs of paths (Γ(M), Γ̄(M̄)) chosen by the random indices (M, M̄). We insert one more
lemma.
Lemma 7.9. For s > 0 as above, and a new constant 0 < C <∞,
Γ(M) 6= Γ̄(M̄)
≤ Ce−s|x−y|/2. (7.22)
38 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Proof. Let Am be the event that the walks X̃(m) and X̄(m) agree up to the maximum
1 ∨ ρ̄
1 of their regeneration times. The equalities M = M̄ and Γ
(M) = Γ̄(M̄) are a
consequence of the event A1∩· · ·∩AM , for the following reason. As pointed out earlier,
on the event Am we have the equality of the regeneration times µ̃(m)1 = ρ̄
1 and of the
stopped paths X̃
0 , µ̃
0 , ρ̄
. By definition, these walks do not backtrack after
the regeneration time. Since the walks X̃(m) and X̄(m) agree up to this time, they
must backtrack or fail to backtrack together. If this is true for each m = 1, . . . ,M ,
it forces M̄ = M , since the other factor in deciding M and M̄ are the paths X(m)
that are common to both. And since the paths agree up to the regeneration times,
we have Γ(M) = Γ̄(M̄).
Estimate (7.22) follows:
Γ(M) 6= Γ̄(M̄)
≤ Px,y
Ac1 ∪ · · · ∪ AcM
Px,y[M ≥ m, Acm ] ≤
Px,y[M ≥ m]
)1/2(
Px,y[Acm]
≤ Ce−s|x−y|/2.
The last step comes from the estimate in (7.20) for each Acm and the geometric bound
on M . �
We are ready to finish the proof of Proposition 7.7. To create initial conditions
Y0 = Ȳ0 = x take initial states (X
0 , X̃
0 ) = (X
0 , X̄
0 ) = (0, x). Let the final
outcome of the coupling be the pair
(Y1, Ȳ1) =
− X(M)
− X(M̄)
under the measure P0,x. The marginal distributions of Y1 and Ȳ1 are correct [namely,
given by the transitions (7.13) and (7.16)] because, as argued above, the pairs of
walks themselves have the right marginal distributions. The event Γ(M) = Γ̄(M̄)
implies Y1 = Ȳ1, so estimate (7.22) gives the bound claimed in Proposition 7.7. �
The construction of the Markov chain is complete, and we return to the main
development of the proof. It remains to prove a sublinear bound on the expected
number E0,0|X[0,n)∩ X̃[0,n)| of common points of two independent walks in a common
environment. Utilizing the common regeneration times, write
E0,0|X[0,n) ∩ X̃[0,n)| ≤
E0,0|X[µi,µi+1) ∩ X̃[µ̃i,µ̃i+1)|. (7.23)
The term i = 0 is a finite constant by bound (7.10) because the number of common
points is bounded by the number µ1 of steps. For each 0 < i < n apply a decom-
position into pairs of paths from (0, 0) to given points (x1, y1) in the style of (7.17):
QUENCHED FUNCTIONAL CLT FOR RWRE 39
(γ, γ̃) are the pairs of paths with the property that
(γ,γ̃)
{X0,n(γ) = γ, X̃0,n(γ̃) = γ̃, β ◦ θn(γ) = β̃ ◦ θn(γ̃) = ∞}
= {X0 = X̃0 = 0, Xµi = x1, X̃µ̃i = y1}.
Each term i > 0 in (7.23) we rearrange as follows.
E0,0|X[µi,µi+1) ∩ X̃[µ̃i,µ̃i+1)|
x1,y1
(γ,γ̃)
EP ω0,0[X0,n(γ) = γ, X̃0,n(γ̃) = γ̃]
×Eωx1,y1(1I{β = β̃ = ∞}|X[0 , µ1) ∩ X̃[0 , µ̃1)| )
x1,y1
(γ,γ̃)
EP ω0,0[X0,n(γ) = γ, X̃0,n(γ̃) = γ̃]P
x1,y1
[β = β̃ = ∞]
×Eωx1,y1( |X[0 , µ1) ∩ X̃[0 , µ̃1)| | β = β̃ = ∞ )
x1,y1
EP ω0,0[Xµi = x1, X̃µ̃i = y1]E
x1,y1
( |X[0 , µ1) ∩ X̃[0 , µ̃1)| | β = β̃ = ∞ ).
The last conditional quenched expectation above is handled by estimates (3.7), (7.10),
(7.20) and Schwarz inequality:
Eωx1,y1( |X[0 , µ1) ∩ X̃[0 , µ̃1)| | β = β̃ = ∞ ) ≤ η
−2Eωx1,y1( |X[0 , µ1) ∩ X̃[0 , µ̃1)| )
≤ η−2Eωx1,y1(µ1 · 1I{X[0 , µ1) ∩ X̃[0 , µ̃1) 6= ∅} )
≤ η−2
Eωx1,y1[µ
)1/2(
P ωx1,y1{X[0 , µ1) ∩ X̃[0 , µ̃1) 6= ∅}
≤ Ce−s|x1−y1|/2.
Define h(x) = Ce−s|x|/2, insert the last bound back up, and appeal to the Markov
property established in Proposition 7.4:
E0,0|X[µi,µi+1) ∩ X̃[µ̃i,µ̃i+1)| ≤ E0,0
h(X̃µ̃i −Xµi)
P0,0[X̃µ̃1 −Xµ1 = x]
qi−1(x, y)h(y).
In order to apply Theorem A.1 from the Appendix, we check its hypotheses in the
next lemma. Assumption (1.2) enters here for the first and only time.
Lemma 7.10. The Markov chain (Yk)k≥0 with transition q(x, y) and the symmet-
ric random walk (Ȳk)k≥0 with transition q̄(x, y) satisfy assumptions (A.i), (A.ii) and
(A.iii) stated in the beginning of the Appendix.
Proof. From Lemma 7.3 and (3.2) we get moment bounds
E0,x|X̄ρ̄k |m + E0,x|Xρk |m <∞
40 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
for any power m < ∞. This gives assumption (A.i), namely that E0|Ȳ1|3 < ∞. The
second part of assumption (A.ii) comes from Lemma 7.6. Assumption (A.iii) comes
from Proposition 7.7.
The only part that needs work is the first part of assumption (A.ii). We show
that it follows from part (1.2) of Hypothesis (R). By (1.2) and non-nestling (N) there
exist two non-zero vectors y 6= z such that z · û > 0 and Eπ0,yπ0,z > 0. Now we have
a number of cases to consider. In each case we should describe an event that gives
Y1−Y0 a particular nonzero value and whose probability is bounded away from zero,
uniformly over x = Y0.
Case 1: y is noncollinear with z. The sign of y · û gives three subcases. We do
the trickiest one explicitly. Assume y · û < 0. Find the smallest positive integer b
such that (y + bz) · û > 0. Then find the minimal positive integers k,m such that
k(y + bz) · û = mz · û. Below Px is the path measure of the Markov chain (Yk) and
then P0,x the measure of the walks (X, X̃) as before.
Px{Y1 − Y0 = ky + (kb−m)z}
≥ P0,x
X̃µ̃1 = x+ ky + (k + 1)bz , Xµ1 = (m+ b)z , β = β̃ = ∞
P Txω0 {Xi(b+1)+1 = i(y + bz) + z, . . . , Xi(b+1)+b = i(y + bz) + bz,
X(i+1)(b+1) = (i+ 1)(y + bz) for 0 ≤ i ≤ k − 1, and then
Xk(b+1)+1 = k(y + bz) + z , . . . , Xk(b+1)+b = k(y + bz) + bz }
× P ω0 {X1 = z , X2 = 2z , . . . , Xm+b = (m+ b)z }
× P ωx+ky+(k+1)bz{β = ∞}P ω(m+b)z{β = ∞}
Regardless of possible intersections of the paths, assumption (1.2) and inequality (3.7)
imply that the quantity above has a positive lower bound that is independent of x.
The assumption that y, z are nonzero and noncollinear ensures that ky+(kb−m)z 6= 0.
Case 2: y is collinear with z. Then there is a vector w 6∈ Rz such that Eπ0,w > 0. If
w · û ≤ 0, then by Hypothesis (N) there exists u such that u · û > 0 and Eπ0,wπ0,u > 0.
If u is collinear with z, then replacing z by u and y by w puts us back in Case 1. So,
replacing w by u if necessary, we can assume that w · û > 0. We have four subcases,
depending on whether x = 0 or not and y · û < 0 or not.
(2.a) The case x 6= 0 is resolved simply by taking paths consisting of only w-steps
for one walk and only z-steps for the other, until they meet on a common level and
then never backtrack.
(2.b) The case y · û > 0 corresponds to Case 3 in the proof of [11, Lemma 5.5].
(2.c) The only case left is x = 0 and y · û < 0. Let b and c be the smallest positive
integers such that (y + bw) · û ≥ 0 and (y + cz) · û > 0. Choose minimal positive
QUENCHED FUNCTIONAL CLT FOR RWRE 41
integeres m ≥ b and n > c such that m(w · û) = n(z · û). Then,
P0{Y1 − Y0 = nz −mw}
≥ P0,0{X̃µ̃1 = y + bw + nz,Xµ1 = y + (b+m)w}
P ω0 {Xi = iw for 1 ≤ i ≤ b and Xb+1+j = y + (b+ j)w for 0 ≤ j ≤ m}
× P ω0 {Xi = iw for 0 ≤ i ≤ b,Xb+1 = bw + z and then
Xb+1+j = y + bw + jz for 1 ≤ j ≤ n}
× P ωy+(b+m)w(β = ∞)P ωy+bw+nz(β = ∞)
Since w and z are noncollinear, mw 6= nz. For the same reason, w-steps are always
taken at points not visited before. This makes the above lower bound positive. By
the choice of b and z · û > 0, neither walk dips below level 0.
We can see that the first common regeneration level for the two paths is (y+ bw+
nz)·û. The first walk backtracks from level bw ·û so this is not a common regeneration
level. The second walk splits from the first walk at bw, takes a z-step up, and then
backtracks using a y-step. So the common regeneration level can only be at or above
level (y+ bw+(c+1)z) · û. The fact that n > c ensures that (y+ bw+nz) · û is high
enough. The minimality of n ensures that this is the first such level. �
Now that the assumptions have been checked, Theorem A.1 gives constants 0 <
C <∞ and 0 < η < 1 such that
qi−1(x, y)h(y) ≤ Cn1−η for all x ∈ Vd and n ≥ 1.
Going back to (7.23) and collecting the bounds along the way gives the final estimate
E0,0|X[0,n) ∩ X̃[0,n)| ≤ Cn1−η
for all n ≥ 1. This is (6.2) which was earlier shown to imply condition (2.1) required
by Theorem 2.1. Previous work in Sections 2 and 5 convert the CLT from Theorem
2.1 into the main result Theorem 1.1. The entire proof is complete, except for the
Green function estimate furnished by the Appendix.
Appendix A. A Green function type bound
Let us write a d-vector in terms of coordinates as x = (x1, . . . , xd), and similarly
for random vectors X = (X1, . . . , Xd).
Let Y = (Yk)k≥0 be a Markov chain on Z
d with transition probability q(x, y),
and let Ȳ = (Ȳk)k≥0 be a symmetric random walk on Z
d with transition probability
q̄(x, y) = q̄(y, x) = q̄(0, y − x). Make the following assumptions.
(A.i) A third moment bound E0|Ȳ1|3 <∞.
42 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
(A.ii) Some uniform nondegeneracy: there is at least one index j ∈ {1, . . . , d} and
a constant κ0 such that the coordinate Y
j satisfies
Px{Y j1 − Y
0 ≥ 1} ≥ κ0 > 0 for all x. (A.1)
(The inequality ≥ 1 can be replaced by ≤ −1, the point is to assure that a cube is
exited fast enough.) Furthermore, for every i ∈ {1, . . . , d}, if the one-dimensional
random walk Ȳ i is degenerate in the sense that q̄(0, y) = 0 for yi 6= 0, then so is
the process Y i in the sense that q(x, y) = 0 whenever xi 6= yi. In other words, any
coordinate that can move in the Y chain somewhere in space can also move in the Ȳ
walk.
(A.iii) Most importantly, assume that for any initial state x the transitions q and
q̄ can be coupled so that
Px,x[Y1 6= Ȳ1] ≤ Ce−α1|x|
where 0 < C, α1 <∞ are constants independent of x.
Throughout the section C will change value but α1 remains the constant in the
assumption above. Let h be a function on Zd such that 0 ≤ h(x) ≤ Ce−α2|x| for
constants 0 < α2, C < ∞. This section is devoted to proving the following Green
function type bound on the Markov chain.
Theorem A.1. There are constants 0 < C, η <∞ such that
Ezh(Yk) =
P0(Yk = y) ≤ Cn1−η for all n ≥ 1 and z ∈ Zd.
To prove the estimate, we begin by discarding terms outside a cube of side r =
c1 logn. Bounding probabilities crudely by 1 gives
|y|>c1 logn
Pz(Yk = y) ≤ n
|y|>c1 logn
h(y) ≤ Cn
k>c1 logn
kd−1e−α2k
k>c1 logn
e−(α2/2)k ≤ Cne−(α2/2)c1 logn ≤ Cn1−η
as long as n is large enough so that kd−1 ≤ eα2k/2, and this works for any c1.
B = [−c1 log n, c1 log n]d.
Since h is bounded, it now remains to show that
Pz(Yk ∈ B) ≤ Cn1−η. (A.2)
For this we can assume z ∈ B since accounting for the time to enter B for the first
time can only improve the estimate.
QUENCHED FUNCTIONAL CLT FOR RWRE 43
Bound (A.2) will be achieved in two stages. First we show that the Markov chain Y
does not stay in B longer than a time whose mean is a power of the size of B. Second,
we show that often enough Y follows the random walk Ȳ during its excursions outside
B. The random walk excursions are long and thereby we obtain (A.2). Thus our first
task is to construct a suitable coupling of Y and Ȳ .
Lemma A.1. Let ζ = inf{n ≥ 1 : Ȳ ∈ A} be the first entrance time of Ȳ into some
set A ⊆ Zd. Then we can couple Y and Ȳ so that
Px,x[ Yk 6= Ȳk for some 1 ≤ k ≤ ζ ] ≤ CEx
e−α1|Ȳk|.
The proof shows that the statement works also if ζ = ∞ is possible, but we will
not need this case.
Proof. For each state x create an i.i.d. sequence (Zxk , Z̄
k )k≥1 such that Z
k has distri-
bution q(x, x+ · ), Z̄xk has distribution q̄(x, x+ · ) = q̄(0, · ), and each pair (Zxk , Z̄xk )
is coupled so that P (Zxk 6= Z̄xk ) ≤ Ce−α1|x|. For distinct x these sequences are inde-
pendent.
Construct the process (Yn, Ȳn) as follows: with counting measures
Ln(x) =
1I{Yk = x} and L̄n(x) =
1I{Ȳk = x} (n ≥ 0)
and with initial point (Y0, Ȳ0) given, define for n ≥ 1
Yn = Yn−1 + Z
Ln−1(Yn−1)
and Ȳn = Ȳn−1 + Z̄
Ȳn−1
L̄n−1(Ȳn−1)
In words, every time the chain Y visits a state x, it reads its next jump from a new
variable Zxk which is then discarded and never used again. And similarly for Ȳ . This
construction has the property that, if Yk = Ȳk for 0 ≤ k ≤ n with Yn = Ȳn = x, then
the next joint step is (Zxk , Z̄
k ) for k = Ln(x) = L̄n(x). In other words, given that the
processes agree up to the present and reside together at x, the probability that they
separate in the next step is bounded by Ce−α1|x|.
44 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Now follow self-evident steps.
Px,x[ Yk 6= Ȳk for some 1 ≤ k ≤ ζ ]
Px,x[ Yj = Ȳj ∈ Ac for 1 ≤ j < k, Yk 6= Ȳk ]
1I{ Yj = Ȳj ∈ Ac for 1 ≤ j < k }PYk−1,Ȳk−1(Y1 6= Ȳ1)
1I{ Yj = Ȳj ∈ Ac for 1 ≤ j < k }e−α1|Ȳk−1|
≤ CEx
e−α1|Ȳm|. �
For the remainder of this section Y and Ȳ are always coupled in the manner that
satisfies Lemma A.1.
Lemma A.2. Let j ∈ {1, . . . , d} be such that the one-dimensional random walk Ȳ j is
not degenerate. Let r0 be a positive integer and w̄ = inf{n ≥ 1 : Ȳ jn ≤ r0} the first
time the random walk Ȳ enters the half-space H = {x : xj ≤ r0}. Couple Y and Ȳ
starting from a common initial state x /∈ H. Then there is a constant C independent
of r0 such that
Px,x[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ] ≤ Ce−α1r0 for all r0 ≥ 1.
The same result holds for H = {x : xj ≥ −r0}.
Proof. By Lemma A.1
Px,x[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ] ≤ CEx
[ w̄−1∑
e−α1|Ȳk|
≤ CExj
[ w̄−1∑
e−α1Ȳ
t=r0+1
e−α1tg(xj, t)
where for s, t ∈ [r0 + 1,∞)
g(s, t) =
Ps[Ȳ
n = t , w̄ > n]
is the Green function of the half-line (−∞, r0] for the one-dimensional random walk
Ȳ j. This is the expected number of visits to t before entering (−∞, r0], defined on
p. 209 in Spitzer [13]. The development in Sections 18 and 19 in [13] gives the bound
g(s, t) ≤ C(1 + (s− r0 − 1) ∧ (t− r0 − 1)) ≤ C(t− r0), s, t ∈ [r0 + 1,∞). (A.3)
QUENCHED FUNCTIONAL CLT FOR RWRE 45
Here is some more detail. Shift r0 + 1 to the origin to match the setting in [13].
Then P19.3 on p. 209 gives
g(x, y) =
u(x− n)v(y − n) for x, y > 0
where the functions u and v are defined on p. 201. For a symmetric random walk
u = v. P18.7 on p. 202 implies that
v(m) =
P[Z1 + · · ·+ Zk = m]
where c is a certain constant and {Zi} are i.i.d. strictly positive, integer-valued ladder
variables for the underlying random walk. Now one can show inductively that v(m) ≤
v(0) for each m so the quantities u(m) = v(m) are bounded. This justifies (A.3).
Continuing from further above we get the estimate claimed in the statement:
[ w̄−1∑
e−α1|Ȳk|
(t− r0)e−α1t ≤ Ce−α1r0. �
For the next lemmas abbreviate Br = [−r, r]d for d-dimensional centered cubes.
Lemma A.3. With α1 given in the coupling hypothesis (A.iii), fix any positive constant
κ1 > 2α
1 . Consider large positive integers r0 and r that satisfy
2α−11 log r ≤ r0 ≤ κ1 log r < r.
Then there exist a positive integer m0 and a constant 0 < α3 <∞ such that, for large
enough r,
x∈BrrBr0
Px[without entering Br0 chain Y exits Br by time r
m0 ] ≥ α3
. (A.4)
Proof. We consider first the case where x ∈ BrrBr0 has a coordinate xj that satisfies
xj ∈ [−r,−r0 − 1] ∪ [r0 + 1, r] and Ȳ j is nondegenerate. For this case we can take
m0 = 4. A higher m0 may be needed to move a suitable coordinate out of the interval
[−r0, r0]. This is done in the second step of the proof.
The same argument works for both xj ∈ [−r,−r0−1] and xj ∈ [r0+1, r]. We treat
the case xj ∈ [r0 + 1, r]. One way to realize the event in (A.4) is this: starting at xj ,
the Ȳ j walk exits [r0 + 1, r] by time r
4 through the right boundary into [r + 1,∞),
and Y and Ȳ stay coupled together throughout this time. Let ζ̄ be the time Ȳ j exits
[r0+1, r] and w̄ the time Ȳ
j enters (−∞, r0]. Then w̄ ≥ ζ̄. Thus the complementary
probability of (A.4) is bounded by
Pxj{ Ȳ j exits [r0 + 1, r] into (−∞, r0] }
+ Pxj{ζ̄ > r4} + Px,x{ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} }.
(A.5)
46 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
We treat the terms one at a time. From the development on p. 253-255 in [13] we
get the bound
Pxj{ Ȳ j exits [r0 + 1, r] into (−∞, r0] } ≤ 1−
(A.6)
for some constant α4 > 0. In some more detail: P22.7 on p. 253, the inequality in
the third display of p. 255, and the third moment assumption on the steps of Ȳ give
a lower bound
Pxj{ Ȳ j exits [r0 + 1, r] into [r + 1,∞) } ≥
xj − r0 − 1− c1
r − r0 − 1
(A.7)
for the probability of exiting to the right. Here c1 is a constant that comes from
the term denoted in [13] by M
s=0(1 + s)a(s) whose finiteness follows from the
third moment assumption. The text on p. 254-255 suggests that these steps need the
aperiodicity assumption. This need for aperiodicity can be traced back via P22.5 to
P22.4 which is used to assert the boundedness of u(x) and v(x). But as we observed
above in the derivation of (A.3) boundedness of u(x) and v(x) is true without any
additional assumptions.
To go forward from (A.7) fix any m > c1 so that the numerator above is positive
for xj = r0 + 1 +m. The probability in (A.7) is minimized at x
j = r0 + 1, and from
xj = r0 + 1 there is a fixed positive probability θ to take m steps to the right to get
past the point xj = r0 + 1 +m. Thus for all x
j ∈ [r0 + 1, r] we get the lower bound
Pxj{ Ȳ j exits [r0 + 1, r] into [r + 1,∞) } ≥
θ(m− c1)
r − r0 − 1
and (A.6) is verified.
As in (A.3) let g(s, t) be the Green function of the random walk Ȳ j for the half-
line (−∞, r0], and let g̃(s, t) be the Green function for the complement of the interval
[r0 + 1, r]. Then g̃(s, t) ≤ g(s, t), and by (A.3) we get this moment bound:
Exj [ ζ̄ ] =
t=r0+1
g̃(xj , t) ≤
t=r0+1
g(xj, t) ≤ Cr2.
Consequently, uniformly over xj ∈ [r0 + 1, r],
Pxj [ζ̄ > r
4] ≤ C
. (A.8)
From Lemma A.2
Px[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ] ≤ Ce−α1r0 . (A.9)
Putting bounds (A.6), (A.8) and (A.9) together gives an upper bound of
1 − α4
+ Ce−α1r0
QUENCHED FUNCTIONAL CLT FOR RWRE 47
for the sum in (A.5) which bounds the complement of the probability in (A.4). By
assumption r0 > 2α
1 log r, so for large enough r the sum above is not more than
1− α3/r for some constant α3 > 0.
The lemma is now proved for those x ∈ Br r Br0 for which some
j ∈ J ≡ {1 ≤ j ≤ d : the one-dimensional walk Ȳ j is nondegenerate}
satisfies xj ∈ [−r,−r0 − 1] ∪ [r0 + 1, r]. Now suppose x ∈ Br r Br0 but all j ∈ J
satisfy xj ∈ [−r0, r0]. Let
T = inf{n ≥ 1 : Y jn /∈ [−r0, r0] for some j ∈ J}.
The first part of the proof gives Px-almost surely
PYT [without entering Br0 chain Y exits Br by time r
4/2] ≥ α3
Replacing r4 by r4/2 only affects the constant in (A.8). It can of course happen that
YT /∈ Br but then we interpret the above probability as one.
By the Markov property it remains to show that for a suitable m0
Px[T ≤ rm0/2] : x ∈ Br r Br0 but xj ∈ [−r0, r0] for all j ∈ J
(A.10)
is bounded below by a positive constant. Hypothesis (A.1) implies that for some
constant b1, ExT ≤ br01 uniformly over the relevant x. This is because one way to
realize T is to wait until some coordinate Y j takes 2r0 successive identical steps.
By hypothesis (A.1) this random time is stochastically bounded by a geometrically
distributed random variable.
It is also necessary for this argument that during time [0, T ] the chain Y does not
enter Br0. Indeed, under the present assumptions the chain never enters Br0 . This is
because for x ∈ BrrBr0 some coordinate i must satisfy xi ∈ [−r,−r0−1]∪ [r0+1, r].
But now this coordinate i /∈ J , and so by hypothesis (A.ii) the one-dimensional
process Y i is constant, Y in = x
i /∈ [−r0, r0] for all n.
Finally, the required positive lower bound for (A.10) comes by Chebychev. Take
m0 ≥ κ1 log b1 +1 where κ1 comes from the assumptions of the lemma. Then, by the
hypothesis r0 ≤ κ1 log r,
Px[T > r
m0/2] ≤ 2r−m0br01 ≤ 2rκ1 log b1−m0 ≤ 12
for r ≥ 4. �
We come to one of the main auxiliary lemmas of this development.
Lemma A.4. Let U = inf{n ≥ 0 : Yn /∈ Br} be the first exit time from Br for the
Markov chain Y . Then there exist finite positive constants C1, m1 such that
Ex(U) ≤ C1rm1 for all 1 ≤ r <∞.
48 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Proof. First observe that supx∈Br Ex(U) < ∞ by assumption (A.1) because by a
geometric time some coordinate Y j has experienced 2r identical steps in succession.
Throughout, let r0 < r satisfy the assumptions of Lemma A.3. Once the statement
is proved for large enough r, we obtain it for all r ≥ 1 by increasing C1.
Let 0 = T0 = S0 ≤ T1 ≤ S1 ≤ T2 ≤ · · · be the successive exit and entrance times
into Br0 . Precisely, for i ≥ 1 as long as Si−1 <∞
Ti = inf{n ≥ Si−1 : Yn /∈ Br0} and Si = inf{n ≥ Ti : Yn ∈ Br0}
Once Si = ∞ then we set Tj = Sj = ∞ for all j > i. If Y0 ∈ Br r Br0 then also
T1 = 0. Again by assumption (A.1) (and as observed in the proof of Lemma A.3)
there is a constant 0 < b1 <∞ such that
x∈Br0
Ex[T1] ≤ br01 . (A.11)
So a priori T1 is finite but S1 = ∞ is possible. Since T1 ≤ U <∞ we can decompose
as follows:
Ex[U ] =
Ex[U, Tj ≤ U < Sj ]
Ex[Tj , Tj ≤ U < Sj] +
Ex[U − Tj , Tj ≤ U < Sj].
(A.12)
We first treat the last sum in (A.12). By an inductive application of Lemma A.3,
for any z ∈ Br rBr0 ,
Pz[U > jr
m0 , U < S1] ≤ Pz[ Yk ∈ Br r Br0 for k ≤ jrm0 ]
1I{ Yk ∈ Br r Br0 for k ≤ (j − 1)rm0 }PY(j−1)rm0 { Yk ∈ Br r Br0 for k ≤ r
≤ · · · ≤ (1− α3r−1)j .
Utilizing this, still for z ∈ Br r Br0 ,
Ez[U, U < S1] =
Pz[U > m , U < S1]
≤ rm0
Pz[U > jr
m0 , U < S1] ≤ rm0+1α−13 .
(A.13)
Next we take into consideration the failure to exit Br during the earlier excursions
in Br rBr0 . Let
Hi = {Yn ∈ Br for Ti ≤ n < Si}
be the event that in between the ith exit from Br0 and entrance back into Br0 the
chain Y does not exit Br. We shall repeatedly use this consequence of Lemma A.3:
for i ≥ 1, on the event {Ti <∞}, Px[Hi | FTi] ≤ 1− α3r−1. (A.14)
QUENCHED FUNCTIONAL CLT FOR RWRE 49
Here is the first instance.
Ex[U − Tj , Tj ≤ U < Sj ] = Ex
[ j−1∏
1IHk · 1I{Tj <∞} · EYTj (U, U < S1)
≤ rm0+1α−13 Ex
[ j−1∏
1IHk · 1I{Tj−1 <∞}
≤ rm0+1α−13 (1− α3r−1)j−1.
Note that if YTj above lies outside Br then EYTj (U) = 0. In the other case YTj ∈
Br rBr0 and (A.13) applies. So for the last sum in (A.12):
Ex[U − Tj , Tj ≤ U < Sj] ≤
rm0+1α−13 (1− α3r−1)j−1 ≤ rm0+2α−23 . (A.15)
We turn to the second-last sum in (A.12). Utilizing (A.11) and (A.14),
Ex[Tj , Tj ≤ U < Sj] ≤
[ j−1∏
1IHk · 1I{Tj <∞} · (Ti+1 − Ti)
≤ br01 (1− α3r−1)j−1
[ i−1∏
1IHk · (Ti+1 − Ti)1IHi · 1I{Ti+1 <∞}
(1− α3r−1)j−1−i.
(A.16)
Split the last expectation as
[ i−1∏
1IHk · (Ti+1 − Ti)1IHi · 1I{Ti+1 <∞}
[ i−1∏
1IHk · (Ti+1 − Si)1IHi · 1I{Si <∞}
[ i−1∏
1IHk · (Si − Ti)1IHi · 1I{Ti <∞}
[ i−1∏
1IHk · 1I{Si <∞} · EYSi (T1)
[ i−1∏
1IHk · 1I{Ti <∞} ·EYTi (S1 · 1IH1)
[ i−1∏
1IHk · 1I{Ti−1 <∞}
(br01 + r
m0+1α−13 )
≤ (1− α3r−1)i−1(br01 + rm0+1α−13 ). (A.17)
In the second-last inequality above, before applying (A.14) to theHk’s, EYSi (T1) ≤ b
comes from (A.11). The other expectation is estimated again by iterating Lemma
50 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
A.3 and again with z ∈ Br rBr0 :
Ez(S1 · 1IH1) =
Pz[S1 > m , H1] ≤
Pz[ Yk ∈ Br rBr0 for k ≤ m ]
≤ rm0
Pz[ Yk ∈ Br r Br0 for k ≤ jrm0 ] ≤ rm0+1α−13 .
Insert the bound from line (A.17) back up into (A.16) to get the bound
Ex[Tj , Tj ≤ U < Sj] ≤ (2br01 + rm0+1α−13 )j(1− α3r−1)j−2.
Finally, bound the second-last sum in (A.12):
Ex[Tj , Tj ≤ U < Sj] ≤
2br01 r
2α−23 + r
m0+3α−33
(1− α3r−1)−1.
Taking r large enough so that α3r
−1 < 1/2 and combining this with (A.12) and
(A.15) gives
Ex[U ] ≤ rm0+2α−21 + 4br01 r2α−23 + 2rm0+3α−33 .
Since r0 ≤ κ1 log r for some constant C, the above bound simplifies to C1rm1 . �
For the remainder of the proof we work with B = Br for r = c1 log n. The above
estimate gives us one part of the argument for (A.2), namely that the Markov chain
Y exits B = [−c1 log n, c1 logn]d fast enough.
Let 0 = V0 < U1 < V1 < U2 < V2 < · · · be the successive entrance times Vi into B
and exit times Ui from B for the Markov chain Y , assuming that Y0 = z ∈ B. It is
possible that some Vi = ∞. But if Vi < ∞ then also Ui+1 < ∞ due to assumption
(A.1), as already observed. The time intervals spent in B are [Vi, Ui+1) each of length
at least 1. Thus, by applying Lemma A.4,
Pz(Yk ∈ B) ≤
(Ui+1 − Vi)1I{Vi ≤ n}
EYVi (U1)1I{Vi ≤ n}
≤ C(logn)m1Ez
1I{Vi ≤ n}
(A.18)
QUENCHED FUNCTIONAL CLT FOR RWRE 51
Next we bound the expected number of returns to B by the number of excursions
outside B that fit in a time of length n:
1I{Vi ≤ n}
(Vj − Vj−1) ≤ n
(Vj − Uj) ≤ n
(A.19)
According to the usual notion of stochastic dominance, the random vector (ξ1, . . . , ξn)
dominates (η1, . . . , ηn) if
Ef(ξ1, . . . , ξn) ≥ Ef(η1, . . . , ηn)
for any function f that is coordinatewise nondecreasing. If the {ξi : 1 ≤ i ≤ n} are
adapted to the filtration {Gi : 1 ≤ i ≤ n}, and P [ξi > a|Gi−1] ≥ 1 − F (a) for some
distribution function F , then the {ηi} can be taken i.i.d. F -distributed.
Lemma A.5. There exist positive constants c1, c2 and γ such that the following holds:
the excursion lengths {Vj − Uj : 1 ≤ j ≤ n} stochastically dominate i.i.d. variables
{ηj} whose common distribution satisfies P[η ≥ a] ≥ c1a−1/2 for 1 ≤ a ≤ c2nγ.
Proof. Since Pz[Vj − Uj ≥ a|FUj ] = PYUj [V ≥ a] where V means first entrance time
into B, we shall bound Px[V ≥ a] below uniformly over
x /∈ B :
Pz[YU1 = x] > 0
Fix such an x and an index 1 ≤ j ≤ d such that xj /∈ [−r, r]. Since the coordinate Y j
can move out of [−r, r], this coordinate is not degenerate, and hence by assumption
(A.ii) the random walk Ȳ j is nondegenerate. As before we work through the case
xj > r because the argument for the other case xj < −r is the same.
Let w̄ = inf{n ≥ 1 : Ȳ jn ≤ r} be the first time the one-dimensional random walk
Ȳ j enters the half-line (−∞, r]. If both Y and Ȳ start at x and stay coupled together
until time w̄, then V ≥ w̄. This way we bound V from below. Since the random
walk is symmetric and can be translated, we can move the origin to xj and use classic
results about the first entrance time into the left half-line, T̄ = inf{n ≥ 1 : Ȳ jn < 0}.
Pxj [w̄ ≥ a] ≥ Pr+1[w̄ ≥ a] = P0[T̄ ≥ a] ≥
for a constant α5. The last inequality follows for one-dimensional symmetric walks
from basic random walk theory. For example, combine equation (7) on p. 185 of [13]
with a Tauberian theorem such as Theorem 5 on p. 447 of Feller [7]. Or see directly
Theorem 1a on p. 415 of [7].
52 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
Now start both Y and Ȳ from x. Apply Lemma A.2 and recall that r = c1 log n.
Px[V ≥ a] ≥ Px,x[V ≥ a, Yk = Ȳk for k = 1, . . . , w̄ ]
≥ Px,x[w̄ ≥ a, Yk = Ȳk for k = 1, . . . , w̄ ]
≥ Pxj [w̄ ≥ a]− Px,x[ Yk 6= Ȳk for some k ∈ {1, . . . , w̄} ]
≥ α5√
− Cn−c1α1 .
This gives a lower bound
Px[V ≥ a] ≥
if a ≤ α25(2C)−2n2c1α1 . This lower bound is independent of x. We have proved the
lemma. �
We can assume that the random variables ηj given by the lemma satisfy 1 ≤ ηj ≤
γ and we can assume both c2, γ ≤ 1 because this merely weakens the result. For
the renewal process determined by {ηj} write
S0 = 0 , Sk =
ηj , and K(n) = inf{k : Sk > n}
for the renewal times and the number of renewals up to time n (counting the renewal
S0 = 0). Since the random variables are bounded, Wald’s identity gives
EK(n) · Eη = ESK(n) ≤ n+ c2nγ ≤ 2n,
while
∫ c2nγ
ds ≥ c3nγ/2.
Together these give
EK(n) ≤ 2n
≤ C2n1−γ/2.
Now we pick up the development from line (A.19). Since the negative of the
function of (Vj − Uj)1≤i≤n in the expectation on line (A.19) is nondecreasing, the
stochastic domination of Lemma A.5 gives an upper bound of (A.19) in terms of the
i.i.d. {ηj}. Then we use the renewal bound from above.
1I{Vi ≤ n}
(Vj − Uj) ≤ n
ηj ≤ n
= EK(n) ≤ C2n1−γ/2.
QUENCHED FUNCTIONAL CLT FOR RWRE 53
Returning back to (A.18) to collect the bounds, we have shown that
Pz(Yk ∈ B) ≤ C(logn)m1Ez
1I{Vi ≤ n}
≤ C(logn)m1C2n1−γ/2
and thereby verified (A.2).
References
[1] N. Berger and O. Zeitouni. A quenched invariance principle for certain ballistic
random walks in i.i.d. environments.
http://front.math.ucdavis.edu/math.PR/0702306.
[2] E. Bolthausen and A.-S. Sznitman. On the static and dynamic points of view for
certain random walks in random environment. Methods Appl. Anal., 9(3):345–
375, 2002. Special issue dedicated to Daniel W. Stroock and Srinivasa S. R.
Varadhan on the occasion of their 60th birthday.
[3] E. Bolthausen and A.-S. Sznitman. Ten lectures on random media, volume 32 of
DMV Seminar. Birkhäuser Verlag, Basel, 2002.
[4] J. Bricmont and A. Kupiainen. Random walks in asymmetric random environ-
ments. Comm. Math. Phys., 142(2):345–420, 1991.
[5] Y. Derriennic and M. Lin. The central limit theorem for Markov chains started
at a point. Probab. Theory Related Fields, 125(1):73–76, 2003.
[6] S. N. Ethier and T. G. Kurtz. Markov processes. Wiley Series in Probability and
Mathematical Statistics: Probability and Mathematical Statistics. John Wiley
& Sons Inc., New York, 1986. Characterization and convergence.
[7] W. Feller. An introduction to probability theory and its applications. Vol. II.
Second edition. John Wiley & Sons Inc., New York, 1971.
[8] M. Maxwell and M. Woodroofe. Central limit theorems for additive functionals
of Markov chains. Ann. Probab., 28(2):713–724, 2000.
[9] F. Rassoul-Agha and T. Seppäläinen. An almost sure invariance principle for
random walks in a space-time random environment. Probab. Theory Related
Fields, 133(3):299–314, 2005.
[10] F. Rassoul-Agha and T. Seppäläinen. Ballistic random walk in a random en-
vironment with a forbidden direction. ALEA Lat. Am. J. Probab. Math. Stat.,
1:111–147 (electronic), 2006.
[11] F. Rassoul-Agha and T. Seppäläinen. Quenched invariance principle for multi-
dimensional ballistic random walk in a random environment with a forbidden
direction. Ann. Probab., 35(1):1–31, 2007.
[12] M. Rosenblatt. Markov processes. Structure and asymptotic behavior. Springer-
Verlag, New York, 1971. Die Grundlehren der mathematischen Wissenschaften,
Band 184.
[13] F. Spitzer. Principles of random walks. Springer-Verlag, New York, second
edition, 1976. Graduate Texts in Mathematics, Vol. 34.
54 F. RASSOUL-AGHA AND T. SEPPÄLÄINEN
[14] A.-S. Sznitman. Slowdown estimates and central limit theorem for random walks
in random environment. J. Eur. Math. Soc. (JEMS), 2(2):93–143, 2000.
[15] A.-S. Sznitman. Topics in random walks in random environment. In School
and Conference on Probability Theory, ICTP Lect. Notes, XVII, pages 203–266
(electronic). Abdus Salam Int. Cent. Theoret. Phys., Trieste, 2004.
[16] A.-S. Sznitman and O. Zeitouni. An invariance principle for isotropic diffusions
in random environment. Invent. Math., 164(3):455–567, 2006.
[17] A.-S. Sznitman and M. Zerner. A law of large numbers for random walks in
random environment. Ann. Probab., 27(4):1851–1869, 1999.
[18] O. Zeitouni. Random walks in random environments, volume 1837 of Lecture
Notes in Mathematics. Springer-Verlag, Berlin, 2004. Lectures from the 31st
Summer School on Probability Theory held in Saint-Flour, July 8–25, 2001,
Edited by Jean Picard.
[19] M. P. W. Zerner. Lyapounov exponents and quenched large deviations for mul-
tidimensional random walk in random environment. Ann. Probab., 26(4):1446–
1476, 1998.
F. Rassoul-Agha, 155 S 1400 E, Salt Lake City, UT 84112
E-mail address : firas@math.utah.edu
URL: www.math.utah.edu/∼firas
T. Seppäläinen, 419 Van Vleck Hall, Madison, WI 53706
E-mail address : seppalai@math.wisc.edu
URL: www.math.wisc.edu/∼seppalai
	1. Introduction and main result
	2. Preliminaries for the proof.
	3. Basic estimates for non-nestling RWRE
	4. Invariant measure and ergodicity
	5. Change of measure
	6. Reduction to path intersections
	7. Bound on intersections
	Appendix A. A Green function type bound
	References
