Constructive approach to limit theorems for recurrent diffusive random walks on a strip

Abstract

We consider recurrent diffusive random walks on a strip. We present constructive conditions on Green functions of finite sub-domains which imply a Central Limit Theorem with polynomial error bound, a Local Limit Theorem, and mixing of environment viewed by the particle process. Our conditions can be verified for a wide class of environments including independent environments, quasiperiodic environments, and environments which are asymptotically constant at infinity. The conditions presented deal with a fixed environment, in particular, no stationarity conditions are imposed.

Keywords

Random walks on a strip Green function RWRE CLT Local Limit Theorem environment viewed from the particle

1. Introduction

The one-dimensional random walk in random environment (RWRE) is a classical model in probability which was first considered in [47] and [30] in 1975. Remarkably, the behavior of the RWRE turns out to be quite different from that of the simple random walk. Perhaps the most famous example of that is the theorem of Sinai [45] which states that for the nearest neighbor random walks in the i.i.d. environment in the recurrent case the walker typically is in a $O ({ln}^{2} n)$ neighborhood of the origin after n steps.

For walks on $Z$ with bounded jumps, it was shown that in the recurrent case the Sinai behavior and the classical CLT are the only possible scenarios for two important classes of environments. Namely, [6] proves this for independent environments and [11] considers quasiperiodic Diophantine environments and proves that the CLT holds with probability one. Recently this result from [11] was extended in [19] to RWRE on a strip, a natural generalization of a random walk on $Z$ with bounded jumps which was introduced in [5]. In fact, it is shown in [19] that in both the i.i.d. and the quasiperiodic Diophantine environments the CLT holds in the recurrent case if and only if the potential is bounded (the precise definition of the potential is given in Section 2.4, see equation (2.22)). This is why it is natural and important to study recurrent RWs in a bounded potential. The recurrent RWs in bounded potential are the main object studied in this paper. However, in contrast to [19] we deal with a fixed environment. We develop a constructive approach which relates directly the rate of convergence of ergodic averages for some specific observables to the CLT. For a typical realization of a random environment our results recover the previously known results and, moreover, we obtain new information also for RWRE. Namely, in the quasiperiodic Diophantine case, the CLT is proven in [19] only for a set of environments of full measure, while our present methods imply that the CLT holds for all such environments without exception.

Our approach has several additional benefits. It allows us to

obtain explicit rate of convergence in the CLT;

establish the almost sure mixing estimates for environment seen by the particle thus extending the results of [33] and [46];

prove local limit theorems for several classes of environments;

apply our method to non stationary environments.

Let us describe the main novel techniques of the present paper which are crucial for our approach. The first one is the asymptotic formula for the Green function in a large finite domain obtained in Section 4. The derivation of this formula relies on an entirely new approach to the analysis of the martingale and the invariant measure equations which was recently discovered in [20]. This approach is further developed in this work and leads to new algebraic properties of the solutions to these equations. The second key ingredient is the weak law of large numbers for the environment viewed by the particle process. Our proof of the law of large numbers relies on the Green function estimates and because of that is more transparent and applicable to a much wider class of observables (the so called self-averaging observables) than the traditional approach based on the ergodic theorem (see e.g. [7,8]).

The layout of the paper is as follows. In Section 2 we define the model, introduce some notation, and provide the necessary background for RW on a strip. In particular we introduce RW in a bounded potential studied in [19]. In Section 3 we illustrate the main results of our paper by applying them to several important classes of environments. The precise formulation of the main results in the general case are given later since they are of a more technical nature. Section 4 contains bounds for the Green function of the walks with bounded potential. In Section 5 these bounds are used to give a constructive proof of ergodicity for the environment viewed by the particle process, giving a rate of convergence of time averages seen by the walker to the space averages. In particular, this allows us to control the drift and the variance of the increments of the walker on a mesoscopic scale. This allows us, in Section 6, to obtain the Central Limit Theorem by the martingale method and gives an estimate on the rate of convergence for several important classes of environments. In Section 7 we consider environments which have different asymptotic behaviors at $+ \infty$ and $- \infty$ and show how the arguments of the previous section could be modified to obtain convergence to the skew Brownian Motion type processes. In Section 8 we use a bootstrap argument to show that the distribution of the walker’s position is the same as for the Brownian Motion on a scale which is slightly larger than $O (1)$ . In Section 9 a local limit theorem for hitting times is used to obtain mixing of the environment seen by the particle. In Section 10 the results of Sections 8 and 9 are combined to obtain the local central limit theorem for the walker’s position.

2. Definition of the model and some preparatory results

2.1. Conventions and notation

The following notations and definitions are used throughout the paper.

All vectors and matrices below will be m-dimensional where m is the width of the strip. The dot product of vectors x and y will be denoted by $x y$ .

$1$ is a column vector whose components are all equal to 1.

$e_{i}$ is the vector whose i-th component is 1 and all other components are 0.

For a vector $x = (x_{i})$ and a matrix $A = (a (i, j))$ we set $\begin{matrix} ‖ x ‖ \overset{def}{=} max_{i} | x_{i} | which implies ‖ A ‖ = sup_{‖ x ‖ = 1} ‖ A x ‖ = max_{i} \sum_{j} | a (i, j) | . \end{matrix}$ We say that A is strictly positive (and we write $A > 0$ ), if all its matrix elements satisfy $a (i, j) > 0$ . A is called non-negative (and we write $A ⩾ 0$ ), if all $a (i, j)$ are non negative. A similar convention applies to vectors. Note that if A is a non-negative matrix then $‖ A ‖ = ‖ A 1 ‖$ .

$S$ denotes the strip, $S = Z \times {1, \dots, m}$ . Given a function $h : S \mapsto R$ , we can define a sequence of $R^{m}$ -vectors $h_{n}$ with components $h (n, i)$ . Vice versa, given a sequence of vectors $h_{n}$ , $- \infty < n < \infty$ , we define a function $h : S \mapsto R$ by setting $h (n, i) = h_{n} (i)$ , where $h_{n} (i)$ is the ith component of $h_{n}$ .

2.2. The model

We recall the definition of the RW on a strip from [5]. Let $L_{n} = {(n, i) : 1 ⩽ i ⩽ m}$ be layer n of the strip, $L_{n} \subset S$ . In our model, the walker is allowed to jump from a point $(n, i) \in L_{n}$ only to points in $L_{n - 1}$ , or $L_{n}$ , or $L_{n + 1}$ . To define the corresponding transition kernel consider a sequence ω of triples $(P_{n}, Q_{n}, R_{n})$ , $- \infty < n < \infty$ , of $m \times m$ non-negative matrices such that for all $n \in Z$ the sum $P_{n} + Q_{n} + R_{n}$ is a stochastic matrix: $\begin{matrix} (2.1) & (P_{n} + Q_{n} + R_{n}) 1 = 1 . \end{matrix}$ We say that the sequence ω is the environment on the strip $S$ .

The matrix elements of $P_{n}$ are denoted $P_{n} (i, j)$ , $1 ⩽ i, j ⩽ m$ , and similar notations are used for $Q_{n}$ and $R_{n}$ . We now set $\begin{matrix} (2.2) & P (z, z_{1}) \overset{def}{=} \{\begin{matrix} P_{n} (i, j) & if z = (n, i), z_{1} = (n + 1, j), \\ R_{n} (i, j) & if z = (n, i), z_{1} = (n, j), \\ Q_{n} (i, j) & if z = (n, i), z_{1} = (n - 1, j), \\ 0 & otherwise . \end{matrix} \end{matrix}$

Remark 2.1.
The study of one-dimensional RW on $Z$ with jumps of length $⩽ m$ can be reduced to the study of the above model by mapping $n \in Z$ to $(⌊ \frac{n}{m} ⌋, n - m ⌊ \frac{n}{m} ⌋) \in S$ , where $⌊ \cdot ⌋$ denotes the integer part. We refer the reader to [5] for the formulas for transition matrices in that case and to [6] for more comments concerning this relationship.

For a fixed ω we define a random walk $ξ (t) = (X (t), Y (t))$ , $t ⩾ 0$ , on $S$ in the usual way: for any starting point $z = (n, i) \in S$ and fixed ω the law $P_{ω, z}$ for the Markov chain $ξ (\cdot)$ is given by $\begin{matrix} (2.3) & P_{ω, z} (ξ (1) = z_{1}, \dots, ξ (t) = z_{t}) \overset{def}{=} P_{ω} (z, z_{1}) P_{ω} (z_{1}, z_{2}) \dots P_{ω} (z_{t - 1}, z_{t}) . \end{matrix}$ Let $Ξ_{z}$ be the set of trajectories $ξ (\cdot)$ starting at z. The just defined $P_{ω, z}$ is a probability measure on $Ξ_{z}$ ; we denote by $E_{ω, z}$ the expectation with respect to this measure.
Remark 2.2.
Fix $i \in {1, \dots, m}$ . With a slight abuse of notation, we shall often write $P$ and $E$ for $P_{ω, (0, i)}$ and $E_{ω, (0, i)}$ . We shall do that if the environment ω is fixed. Since the strip has finite width, all the results proved in the paper will be uniform with respect to $i$ .

Also it will often be convenient to write $ξ_{t}$ for $ξ (t)$ and $X_{t}$ and $Y_{t}$ for $X (t)$ and $Y (t)$ respectively.

Throughout the paper we suppose that the following ellipticity conditions are satisfied: there is an $\bar{ε} > 0$ and a positive integer number $k_{0} < \infty$ such that for any $n \in Z$ and any $i, j \in [1, m]$ $\begin{matrix} (2.4) & ‖ R_{n}^{k_{0}} ‖ ⩽ 1 - \bar{ε}, ({(I - R_{n})}^{- 1} P_{n}) (i, j) ⩾ \bar{ε}, and ({(I - R_{n})}^{- 1} Q_{n}) (i, j) ⩾ \bar{ε} . \end{matrix}$ Note that $({(I - R_{n})}^{- 1} P_{n}) (i, j)$ (respectively $({(I - R_{n})}^{- 1} Q_{n}) (i, j)$ ) is the probability that the walker starting from $(n, i)$ reaches $(n + 1, j)$ (respectively $(n - 1, j)$ ) at the first exit from the layer $L_{n}$ .
Remark 2.3.
Most of our results will be proved for environments which are not random but rather satisfy certain properties (which will be listed in due time). We shall show that it is possible to apply these results to certain important classes of random environments. More precisely, denote by $(Ω, F, P, T)$ the dynamical system where Ω is the space of all sequences $ω = {((P_{n}, Q_{n}, R_{n}))}_{n = - \infty}^{\infty}$ of triples described above, $F$ is the corresponding natural σ-algebra, P denotes the probability measure on $(Ω, F)$ , and T is the shift operator on Ω defined by $T (P_{n}, Q_{n}, R_{n}) = (P_{n + 1}, Q_{n + 1}, R_{n + 1})$ . We shall always suppose that T preserves measure P and is ergodic. The expectation with respect to P will be denoted by E.

To be able to apply the result obtained for deterministic environments in the context of random environment, we shall check that the conditions we need are satisfied by P-almost all random environments.
Remark 2.4.
Apart of the probability measures $P$ and P defined above, we shall quite often use measures which will be denoted by P, with related expectations denoted E, and which describe ‘reference’ probabilities and expectations related to, e. g., standard normal distribution, standard Wiener processe, well known results concerning martingales, etc. Theorems 3.6, 3.8, Corollary 6.5, Propositions 6.6, 6.7 are examples where this notation is used. In each such case, the precise meaning of $P (\cdot)$ is obvious from the context.

Denote by $J$ the following set of triples of $m \times m$ matrices: $\begin{matrix} J \overset{def}{=} {(P, Q, R) : P ⩾ 0, Q ⩾ 0, R ⩾ 0 and (P + Q + R) 1 = 1} . \end{matrix}$

We shall use the following metric on $Ω = J^{Z}$ . For $ω^{'} = {(P_{n}^{'}, Q_{n}^{'}, R_{n}^{'})}$ , $ω^{″} = {(P_{n}^{″}, Q_{n}^{″}, R_{n}^{″})}$ set $\begin{matrix} (2.5) & d (ω^{'}, ω^{″}) = \sum_{n \in Z} \frac{‖ P_{n}^{'} - P_{n}^{″} ‖ + ‖ Q_{n}^{'} - Q_{n}^{″} ‖ + ‖ R_{n}^{'} - R_{n}^{″} ‖}{2^{| n |}} . \end{matrix}$

Below, whenever we say that a function defined on Ω is continuous we mean that it is continuous with respect to the topology induced by the metric $d (\cdot, \cdot)$ .
2.3. Matrices $ζ_{n}$ , $A_{n}$ , $α_{n}$ and some related quantities

We are now in a position to recall the definitions of several objects most of which were first introduced and studied in [5,6] and which will play a crucial role in this work.

For a given $ω \in Ω$ , define a sequence of $m \times m$ stochastic matrices $ζ_{n}$ as follows. For an integer a let $ψ_{a}$ be a stochastic matrix. For $n > a$ define matrices $ψ_{n, a}$ recurrently as follows: $ψ_{a, a} = ψ_{a}$ and $\begin{matrix} (2.6) & ψ_{n, a} = {(I - R_{n} - Q_{n} ψ_{n - 1, a})}^{- 1} P_{n}, n = a + 1, a + 2, \dots . \end{matrix}$ It is easy to show (see [5]) that matrices $ψ_{n, a}$ are stochastic. Now for a fixed n define $\begin{matrix} (2.7) & ζ_{n} = lim_{a \to - \infty} ψ_{n, a} . \end{matrix}$ As shown in [5, Theorem 1] the limit (2.7) exists and is independent of the choice of the sequence ${ψ_{a}}$ .

Next, we define probability row-vectors $σ_{n} = σ_{n} (ω) = (σ_{n} (ω, 1), \dots, σ_{n} (ω, m))$ which are associated with the matrices $ζ_{n}$ . Let ${\tilde{σ}}_{a}$ be an arbitrary sequence of probability row-vectors (by which we mean that ${\tilde{σ}}_{a} ⩾ 0$ and $\sum_{i = 1}^{m} {\tilde{σ}}_{a} (i) = 1$ ). Set $\begin{matrix} (2.8) & σ_{n} \overset{def}{=} lim_{a \to - \infty} {\tilde{σ}}_{a} ζ_{a} \dots ζ_{n - 1} . \end{matrix}$ By the standard contraction property of the product of stochastic matrices, this limit exists and does not depend on the choice of the sequence ${\tilde{σ}}_{a}$ (see [24, Lemma 1]). Vectors $σ_{n}$ could be equivalently defined as the unique sequence of probability vectors satisfying the infinite system of equations $\begin{matrix} (2.9) & σ_{n} = σ_{n - 1} ζ_{n - 1}, n \in Z . \end{matrix}$ Combining (2.8) with standard contracting properties of stochastic matrices ζ we obtain for $k > n$ that $\begin{matrix} (2.10) & ‖ ζ_{n} \dots ζ_{k - 1} - (σ_{k} (1) 1, \dots, σ_{k} (m) 1) ‖ ⩽ C θ^{k - n}, \end{matrix}$ where $0 ⩽ θ < 1$ and C depend only on the $\bar{ε}$ from (2.4).

Define $\begin{matrix} (2.11) & α_{n} = Q_{n + 1} {(I - R_{n} - Q_{n} ζ_{n - 1})}^{- 1}, A_{n} = {(I - R_{n} - Q_{n} ζ_{n - 1})}^{- 1} Q_{n} . \end{matrix}$ Note that $α_{n} P_{n} = Q_{n + 1} ζ_{n}$ and hence $\begin{matrix} (2.12) & α_{n} = Q_{n + 1} {(I - R_{n} - α_{n - 1} P_{n - 1})}^{- 1} . \end{matrix}$ Conditions (2.4) imply (see [19, Remark 2.2]) that matrices $A_{n}$ have the following properties: $\begin{matrix} (2.13) & ‖ A_{n} ‖ ⩽ {(m \bar{ε})}^{- 1} and A_{n} (i, j) ⩾ \bar{ε} . \end{matrix}$ In turn, inequalities (2.13) imply the well known contracting property of the action of matrices $A_{n}$ . We shall make use of the following version of this property: the limit $\begin{matrix} (2.14) & v_{n} = lim_{a \to - \infty} \frac{A_{n} A_{n - 1} \dots A_{a + 1} {\tilde{v}}_{a}}{‖ A_{n} A_{n - 1} \dots A_{a + 1} {\tilde{v}}_{a} ‖} \end{matrix}$ exists and does not depend on the choice of the sequence of vectors ${\tilde{v}}_{a} ⩾ 0$ , $‖ {\tilde{v}}_{a} ‖ = 1$ . Moreover, there is a θ, $0 < θ < 1$ , such that $\begin{matrix} (2.15) & ‖ v_{n} - \frac{A_{n} A_{n - 1} \dots A_{a + 1} {\tilde{v}}_{a}}{‖ A_{n} A_{n - 1} \dots A_{a + 1} {\tilde{v}}_{a} ‖} ‖ = O (θ^{n - a}) . \end{matrix}$ For the sake of completeness, we prove (2.14) and (2.15) in Appendix B.

Similarly, for any sequence of row-vectors ${\tilde{l}}_{a} ⩾ 0$ , $‖ {\tilde{l}}_{a} ‖ = 1$ , define $\begin{matrix} (2.16) & l_{n} = lim_{a \to \infty} \frac{{\tilde{l}}_{a} α_{a - 1} \dots α_{n}}{‖ {\tilde{l}}_{a} α_{a - 1} \dots α_{n} ‖} . \end{matrix}$ Set $\begin{matrix} (2.17) & λ_{k} = ‖ A_{k} v_{k - 1} ‖ and {\tilde{λ}}_{k} = ‖ l_{k + 1} α_{k} ‖ . \end{matrix}$ Then obviously $\begin{matrix} (2.18) & l_{k + 1} α_{k} = {\tilde{λ}}_{k} l_{k}, A_{k} v_{k - 1} = λ_{k} v_{k} \end{matrix}$ and for any $n ⩾ k$ we have $\begin{matrix} (2.19) & ‖ A_{n} A_{n - 1} \dots A_{k} v_{k - 1} ‖ = λ_{n} \dots λ_{k}, ‖ l_{n + 1} α_{n} α_{n - 1} \dots α_{k} ‖ = {\tilde{λ}}_{n} \dots {\tilde{λ}}_{k} . \end{matrix}$

Remark 2.5.
It should be emphasized that even though [5,6] dealt with stationary ergodic environments, the proofs provided in [5,6] of the existence of the limits (2.7) and (2.14) are in fact working for all (and not just P – almost all) sequences ω satisfying (2.4).
Remark 2.6.
Note that $m = 1$ corresponds to the random walks on $Z$ with jumps to the nearest neighbours. In this case $p_{n} = P_{ω} (ξ (t + 1) = n + 1 | ξ (t) = n)$ and $q_{n} = 1 - p_{n}$ . The above formulae now become very simple, namely $ψ_{n} = ζ_{n} = 1$ , $v_{n} = l_{n} = 1$ , $A_{n} = λ_{n} = \frac{q_{n}}{p_{n}}$ , $α_{n} = {\tilde{λ}}_{n} = \frac{q_{n + 1}}{p_{n}}$ .

In the above considerations, matrices $P_{n}$ and $Q_{n}$ play asymmetric roles and it turns out to be useful to ‘symmetrize’ the situation. Namely, let us introduce stochastic matrices $ζ_{n}^{-}$ as the unique sequence of stochastic matrices satisfying the system of equations which is symmetric to (2.6), (2.7) $\begin{matrix} (2.20) & ζ_{n}^{-} = {(I - R_{n} - P_{n} ζ_{n + 1}^{-})}^{- 1} Q_{n}, - \infty < n < + \infty . \end{matrix}$ Next we set $\begin{matrix} (2.21) & A_{n}^{-} \overset{def}{=} {(I - R_{n} - P_{n} ζ_{n + 1}^{-})}^{- 1} P_{n}, α_{n}^{-} = P_{n - 1} {(I - R_{n} - P_{n} ζ_{n + 1}^{-})}^{- 1} . \end{matrix}$ All other related objects are introduced similarly.

Matrices $ζ_{n}^{-}$ , $α_{n}^{-}$ , $A_{n}^{-}$ , etc have properties which are similar to those of matrices $ζ_{n}$ , $α_{n}$ , $A_{n}$ etc listed above. All these objects will be used below without further explanations.
2.4. Walks in bounded potential

In the context of random walks in random environments, the notion of potential was introduced in [45] in the case of the walks on $Z$ with jumps to nearest neighbors. The following extension of this definition to the case of random walks on a strip was given in [6].

Definition.
A potential is a function of n (and ω) defined by $\begin{matrix} (2.22) & U_{n} (ω) \equiv U_{n} \overset{def}{=} \{\begin{matrix} log ‖ A_{n} \dots A_{1} ‖ & if n ⩾ 1, \\ 0 & if n = 0, \\ - log ‖ A_{0} \dots A_{n + 1} ‖ & if n ⩽ - 1 . \end{matrix} \end{matrix}$ We say that a potential is bounded if there is a constant $C_{P}$ such that $\begin{matrix} (2.23) & | U_{n} | ⩽ C_{P} for all n . \end{matrix}$

Bounded potentials appear naturally in the study of the following two classes of environments. First, it has been proved in [6] that the recurrence of a random walk in an i.i.d. environment on a strip is equivalent to exactly one of two options: either the potential is bounded or it converges, after the diffusive rescaling, to the Wiener process. In the second case the walk exhibits the Sinai behavior [6]. Next, in [19] it was shown that for quasiperiodic environments with Diophantine frequencies the potential is bounded if and only if the random walk is recurrent.
2.5. One useful property of a bounded potential

Properties (2.23) and (2.13) imply that there is a constant ${\tilde{C}}_{P} > 0$ such that for any vector $x \in R^{m}$ , $x ⩾ 0$ , ( $x \neq 0$ ), and for any $n > k$ $\begin{matrix} (2.24) & e^{- {\tilde{C}}_{P}} ‖ x ‖ 1 ⩽ A_{n} \dots A_{k + 1} x ⩽ e^{{\tilde{C}}_{P}} ‖ x ‖ 1 . \end{matrix}$ We shall check this statement for the case $k ⩾ 1$ (other cases are similar).

Note that for any k and $x ⩾ 0$ the second inequality in (2.13) implies $(A_{k} x) (i) ⩾ \bar{ε} ‖ x ‖$ for all i, $1 ⩽ i ⩽ m$ , and so $A_{k} x ⩾ \bar{ε} ‖ x ‖ 1$ .

By (2.23), $‖ A_{k - 1} \dots A_{1} ‖ = ‖ A_{k - 1} \dots A_{1} 1 ‖ ⩾ e^{- C_{P}}$ which is equivalent to saying that there is $e_{i}$ such that $A_{k - 1} \dots A_{1} 1 ⩾ e^{- C_{P}} e_{i}$ . But then $\begin{matrix} A_{k} A_{k - 1} \dots A_{1} 1 ⩾ e^{- C_{P}} A_{k} e_{i} ⩾ e^{- C_{P}} \bar{ε} 1 . \end{matrix}$ So $1 ⩽ {\bar{ε}}^{- 1} e^{C_{P}} A_{k} \dots A_{1} 1$ and hence $\begin{matrix} A_{n} \dots A_{k + 1} x ⩽ ‖ x ‖ A_{n} \dots A_{k + 1} 1 ⩽ {\bar{ε}}^{- 1} e^{C_{P}} ‖ x ‖ A_{n} \dots A_{k + 1} A_{k} \dots A_{1} 1 ⩽ {\bar{ε}}^{- 1} e^{2 C_{P}} ‖ x ‖ 1 \end{matrix}$ proving the second inequality in (2.24).

Next, by the definition of the norm (and since matrices are positive) we have that $\begin{matrix} A_{k} \dots A_{1} 1 ⩽ e^{C_{P}} 1 and hence 1 ⩾ e^{- C_{P}} A_{k} \dots A_{1} 1 . \end{matrix}$ Since $A_{n} \dots A_{k + 1} x ⩾ \bar{ε} ‖ x ‖ A_{n} \dots A_{k + 1} 1$ , we obtain $\begin{matrix} A_{n} \dots A_{k + 1} x ⩾ \bar{ε} ‖ x ‖ A_{n} \dots A_{k + 1} 1 ⩾ \bar{ε} e^{- C_{P}} ‖ x ‖ A_{n} \dots A_{k + 1} A_{k} \dots A_{1} 1 ⩾ \bar{ε} e^{- 2 C_{P}} ‖ x ‖ 1 \end{matrix}$ which proves the first inequality in (2.24).

From now on we always suppose that the potential is bounded and we assume for the rest of the paper that ( 2.24 ) is satisfied.

In our previous work we have shown that walks in a bounded potential satisfy the following properties.

(I) There exists a non-constant sequence of column vectors $m_{n} \in R^{m}$ (with components $m_{n} (i)$ ) and a constant K such that $\begin{matrix} (2.25) & | m_{n^{'}} (i^{'}) - m_{n^{″}} (i^{″}) | ⩽ K if | n^{'} - n^{″} | ⩽ 1, \end{matrix}$ and for all n $\begin{matrix} (2.26) & m_{n} = P_{n} m_{n + 1} + R_{n} m_{n} + Q_{n} m_{n - 1} . \end{matrix}$ The construction of the sequence $m_{n}$ is presented in [19, Section 7]. We recall the probabilistic meaning of (2.26). Let $m : S \mapsto R$ be a function on a strip and $m_{n} \in R^{m}$ be a sequence of column vectors with components $m_{n} (i) = m (n, i)$ . If $ξ (t) = (X_{t}, Y_{t})$ , $t ⩾ 0$ , is the RW defined in Section 2.2 then the process $M (t) \overset{def}{=} m (ξ_{t}) \equiv m (X_{t}, Y_{t}) \equiv m_{X_{t}} (Y_{t})$ is a martingale if and only if the vectors $m_{n}$ satisfy (2.26).

(II) There exists a positive bounded solution $ρ_{n} = (ρ_{n} (1), \dots, ρ_{n} (m))$ , $- \infty < n < \infty$ , to the equation $\begin{matrix} (2.27) & ρ_{n} = ρ_{n - 1} P_{n - 1} + ρ_{n} R_{n} + ρ_{n + 1} Q_{n + 1} \end{matrix}$ which also satisfies $ρ_{n} = ρ_{n + 1} α_{n}$ , $ρ_{n + 1} = ρ_{n} α_{n + 1}^{-}$ .

Equation (2.27) appears in several contexts. First, for a fixed environment, it describes the invariant measure for the walker. Second, in the case when we deal with stationary environment the solution to (2.27) provides invariant densities for the environment viewed from the particle process. We refer the reader to [20] for a comprehensive analysis of this equation on the strip. The invariant measure equation for the stationary walks on $Z$ with bounded jumps was studied in [10].

In accordance with conventions of §2.1 we will often write $m (ξ_{t})$ instead of $m_{X_{t}} (Y_{t})$ and $ρ (ξ_{t})$ instead of $ρ (X_{t}, Y_{t}) = ρ_{X_{t}} (Y_{t})$ .

3. Application of results to some classes of environments

In this section we first discuss examples of important classes of environments. We then state the results which we obtained for these environments as corollaries of our main and more general (but also more technical) theorems proved in this paper.

3.1. Classes of environments

Example 3.1 (Quasiperiodic systems).

Consider the environment given by $\begin{matrix} {(P, Q, R)}_{n} = (P, Q, R) (ω + n γ), \end{matrix}$ where $ω, γ \in T^{d}$ , $T^{d}$ is a d-dimensional torus, and $P, Q, R : T^{d} \to R$ are $C^{\infty}$ functions. γ is called the rotation vector.

RWs in quasiperiodic environments received less attention than the walks discussed in the two other examples below, the main references relevant for our work being [1,11,28,46]. However, its continuous space analogue, the quasiperiodic diffusion, is a classical object in the PDE literature, see [27,31] and references therein.

For quasiperiodic environment there exists a continuous function $λ : T^{d} \to R$ such that $λ_{n} (ω) = λ (ω + n γ)$ ( $λ_{n}$ is defined in (2.17)). We say that γ is Diophantine if there are constants K, τ such that for each $k \in Z^{d} ∖ 0$ we have $\begin{matrix} (3.1) & d (γ k, 2 π Z) ⩾ \frac{K}{| k |^{τ}}, \end{matrix}$ where d denotes the distance on the line. If γ is Diophantine then $λ \in C^{\infty} (T^{d})$ , see Appendix C. The recurrence condition [5] amounts to $\begin{matrix} (3.2) & \int_{T^{d}} ln λ (ω) d ω = 0, \end{matrix}$ where $d ω$ is normalized Lebesgue measure on the torus. It is proven in [19] that if γ is Diophantine then for every triple $(P, Q, R)$ the CLT holds for almost all ω. We note that the Diophantine assumption (3.1) is necessary, since [16] gives examples showing that the CLT need not hold if (3.1) fails. In this paper we obtain additional information in the case when (3.1) and (3.2) hold.

Example 3.2 (Independent environments).

Here we suppose that ${(P, Q, R)}_{n}$ for different n are independent and identically distributed.

The study of RWRE on $Z$ goes back to [30,45,47]. We refer the reader to [50] for a good overview of this subject. The papers most relevant to the present work are also described below after the formulations of Theorems 3.6, 3.8, 3.10. The study of the walks on the strip was initiated in [5], the main references for limit theorems in this setting are [6,17,19,24].

In particular, for independent environments it was shown in [6] that in the recurrent case the Sinai behavior is observed unless ${(P, Q, R)}_{n}$ belong to a proper algebraic subvariety in the space of transition matrices. The behavior of the walker on this subvariety was investigated in [19] where it was proven that the solutions to (2.26) and (2.27) with properties (I) and (II) exist.

Example 3.3 (Small perturbations of the simple random walk on $Z$ ).

Consider a random walk on $Z$ with $p_{n} = \frac{1}{2} - a_{n}$ , $q_{n} = \frac{1}{2} + a_{n}$ where $a_{n}$ satisfy $\begin{matrix} | a_{n} | ⩽ \frac{K}{| n |^{κ} + 1}, where κ > 1 . \end{matrix}$

The condition $κ > 1$ is sufficient for recurrence (see e.g. [21]). However, for our results to apply we need one more condition, namely $\begin{matrix} (3.3) & υ = 1 where υ = \prod_{n \in Z} (\frac{p_{n}}{q_{n}}) . \end{matrix}$ Condition (3.3) appears to be restrictive. However, we will show in Corollary 7.3 that it is in fact necessary for the CLT to hold.

The study of environments where the limit ${lim}_{n \to \pm \infty} p_{n}$ exists has a long history. The limit theorems for such walks go back to [34,49]. The setting which perhaps is the closest to ours can be found in [42] where the Central Limit Theorem is obtained in the transient case. Small perturbations of RWRE were studied in [22,40,41]. We refer the reader to [39] and references therein for a review of more recent developments. In the present paper we show that such walks fit into the more general framework that we consider.

3.2. The results

Next, we describe applications of the general theory developed in this paper to the classes of environments described above. We assume throughout this section that the ellipticity condition (2.4) holds and that the walk is recurrent. In addition, we assume (2.24) (this assumption is only non-trivial in Example 3.2 while in Examples 3.1 and 3.3 it follows from recurrence and ellipticity).

We would like to emphasize that our results by no means are limited to Examples 3.1, 3.2, and 3.3. In fact, Theorems 3.4, 3.5, 3.6, 3.8, and 3.10 below will be obtained as corollaries of more general results, namely, Theorems 6.1, 7.1, 6.8, 9.1, and 10.1 respectively. The statements of these general theorems are more technical and will be given in a due course, after we introduce the necessary background.

Theorems 3.4, 3.6, 3.5, 3.8, and 3.10 below are valid for all environments in Examples 3.1 and 3.3 and for almost all environments in Example 3.2. However in that last case we provide explicit conditions on environment (see equations (6.11), (6.12), (6.13)) which guarantee the validity of these theorems.

Let $N$ be the standard normal random variable and Φ be the cumulative distribution function of $N$ .

Theorem 3.4 (Functional CLT).

There is a constant $D > 0$ such that the process $W_{N} (t) = \frac{X (t N)}{\sqrt{N}}$ converges in law as $N \to \infty$ to $W (t)$ -the Brownian Motion with zero mean and variance $D t$ .

In fact, we can obtain the functional CLT also for perturbations of our environments which decay at infinity sufficiently fast. Namely, consider a perturbation $\bar{P}$ of $P$ 1

¹
In the setting of Example 3.3 this means that we allow the environments which do not satisfy (3.3). In fact, it follows from the explicit expression for $p$ in terms of $υ$ (see equation (7.16)) that in Example 3.3 $p = \frac{1}{2}$ iff $υ = 1$ .

such that

\begin{matrix} | \bar{P} (z, z^{'}) - P (z, z^{'}) | ⩽ \frac{C}{| n |^{κ} + 1} where z = (n, j) and κ > 1 . \end{matrix}

Let

\bar{ξ} (t) = (\bar{X} (t), \bar{Y} (t))

denote the walk in the perturbed environment.

Theorem 3.5 (Functional CLT for the perturbed walk).

There exist constants $p$ and $D > 0$ such that the process $\frac{\bar{X} (t N)}{\sqrt{N}}$ converges in law as $N \to \infty$ to the skew Brownian Motion with zero mean, variance $D t$ , and skewness parameter $p$ .

The definition and basic properties of the skew Brownian Motion will be discussed in Section 7. Here we just mention that one way to construct the skew Brownian Motion with skewness parameter $p$ is to take the scaling limit for the random walk which is symmetric everywhere except the origin, and which moves to the right from the origin with probability $p$ and to the left with probability $1 - p$ (see [26]).

Theorem 3.6 (Effective CLT).

There are constants D, υ such that for each ε there is a constant $C_{ε}$ such that $\begin{matrix} sup_{x} | P (\frac{X (N)}{\sqrt{D N}} ⩽ x) - Φ (x) | ⩽ C_{ε} N^{- (υ - ε)} . \end{matrix}$

The exponent υ is explicit. Namely, $υ = \frac{1}{8}$ in Examples 3.1, 3.2, and $υ = min (\frac{κ - 1}{2}, \frac{1}{8})$ in Example 3.3.

For the next two theorems we assume for Examples 3.1 and 3.2 that the random walk is lazy in the sense that $\begin{matrix} (3.4) & R_{n} (i, i) ⩾ \bar{ε} > 0 . \end{matrix}$

Remark 3.7.
Assumption (3.4) is made for convenience only in order to simplify the statements. Indeed assumption (2.4) implies that the walker can reach all points at the neighboring layer by the time it changes layers. Therefore if we define the stopping times $τ (n)$ by the conditions $τ (0) = 0$ , $τ (n + 1) = min (τ > τ (n) : X_{τ} \neq X_{τ (n)})$ then the accelerated walk $ξ^{} (n) = ξ (τ (2 n))$ satisfies (3.4). However the natural objects associated with $ξ^{}$ (such as solutions to (2.27) etc) have a more complicated form than for ξ so we prefer to impose (3.4).
Theorem 3.8 (Local Limit Theorem).

In Examples 3.1 and 3.2 there are constants a, b such that uniformly for $k_{N} / \sqrt{N}$ in a compact set for each $y \in {1, \dots, m}$ we have $\begin{matrix} (3.5) & lim_{N \to \infty} \frac{P (ξ (N) = (k_{N}, y))}{P (\sqrt{\frac{b N}{a}} N \in [k_{N} - \frac{1}{2}, k_{N} + \frac{1}{2}]) ρ (k_{N}, y)} = \frac{1}{a} . \end{matrix}$

In Example 3.3 uniformly for $k_{N} / \sqrt{N}$ in a compact set if $k_{N}$ and N have the same parity then $\begin{matrix} (3.6) & lim_{N \to \infty} \frac{P (ξ (N) = k_{N})}{P (\sqrt{N} N \in [k_{N} - \frac{1}{2}, k_{N} + \frac{1}{2}]) ρ (k_{N})} = 2 . \end{matrix}$

Remark 3.9.
Equation (2.27) defines ρ up to a multiplicative constant. So to complete the statement of Theorem 3.8 one needs to explain how to normalize ρ. This will be done in Section 4 (see equations (4.6) and (4.7)).

It will be shown in Section 6 (see equation (6.35)) that with this choice of normalization, we have in Example 3.3 that ${lim}_{| k | \to \infty} ρ (k) = 1$ . Thus if in Theorem 3.8(b) $| k_{N} | \to \infty$ then (3.6) can be simplified to read $\begin{matrix} lim_{N \to \infty} \frac{P (ξ (N) = k_{N})}{P (\sqrt{N} N \in [k_{N} - \frac{1}{2}, k_{N} + \frac{1}{2}])} = 2 . \end{matrix}$ That is in that case the Local Limit Theorem takes the same form as for the simple random walk.

While the Central Limit Theorem was studied for many classes of RWRE, the Local Limit Theorem is less well understood. We note that there are two different classes of walks where the CLT is known and so it makes sense to study the LLT: ballistic walks are investigated in [2,18,37,46] and balanced walks in [13,46,48]. In both cases the Local Limit Theorem takes the same form (3.5), but the meaning of ρ is different: for ballistic walks $ρ_{z}$ is the expected number of visits to the site z while for recurrent walks it is proportional to the invariant measure of the walk restricted to a finite domain. For this reason different methods are usually employed to study these two cases. In the present paper we adapt the method used in [18] to study the ballistic walks to the recurrent case (our approach is a modification of the method of [24] and is related to extraction of a binomial component approach used in [15]). The universality of this method makes it promising in other problems where the Local Limit Theorem can be expected.

To formulate our last result we need one more definition. In Examples 3.1 and 3.2 a bounded function $h : S \to R$ will be called self-averaging if there is a constant $h$ (the average of h) and a sequence $δ_{N}$ converging to 0 as $N \to \infty$ such that for each ε, K for each k with $| k | ⩽ K \sqrt{N}$ $\begin{matrix} (3.7) & | \frac{1}{2 δ_{N} N^{1 / 4}} \sum_{l = k - δ_{N} N^{1 / 4}}^{k + δ_{N} N^{1 / 4}} ρ_{l} h_{l} - h | ⩽ ε \end{matrix}$ where $h_{l}$ is a vector with components $h_{l} (j) = h (l, j)$ , $ρ_{l}$ is the vector defined in (2.27), whose components are denoted by $ρ_{l} (j)$ , and $\begin{matrix} ρ_{l} h_{l} = \sum_{j = 1}^{m} ρ_{l} (j) h (l, j) . \end{matrix}$ In Example 3.3 the walk is periodic with period 2, so (3.7) has to be replaced by $\begin{matrix} (3.8) & \begin{array}{l} | \frac{1}{2 δ_{N} N^{1 / 4}} \sum_{l = - δ_{N} N^{1 / 4}}^{δ_{N} N^{1 / 4}} ρ_{k + 2 l} h_{k + 2 l} - h | ⩽ ε and \\ | \frac{1}{2 δ_{N} N^{1 / 4}} \sum_{l = - δ_{N} N^{1 / 4}}^{δ_{N} N^{1 / 4}} ρ_{k + 1 + 2 l} h_{k + 1 + 2 l} - h | ⩽ ε . \end{array} \end{matrix}$ The meaning of the notion of the self-averaging will be explained later (see Remark 5.2).
Theorem 3.10 (Mixing of environment viewed by the particle).

If $h : S \to R$ is self-averaging then $\begin{matrix} lim_{N \to \infty} E (h (ξ (N))) = \frac{h}{a} \end{matrix}$ where a is the same as in ( 3.5 ).

Remark 3.11.
The term mixing here refers to the fact that the expectation above is asymptotically independent of N. It follows from our proof that it is also independent of the starting point of the walk. Therefore Theorem 3.10 shows that the environment seen by the walker does not remember the remote past of the walker. Results similar to Theorem 3.10 are sometimes called renewal theorems since mixing for certain systems allows us to recover the classical renewal theorems. We prefer the term mixing since it appears to describe the phenomenon more precisely.

The environment viewed by the particle process is a standard tool in studying the random walk [7,8,32]. For ballistic nearest neighbor random walks on $Z$ in independent environments the mixing of this process was obtained in [29] in the annealed setting. The quenched result was proven in [33] for independent walks under the additional assumption that the fluctuations are diffusive (see [18] for a simple proof). [28,46] prove mixing for quasiperiodic walks. The results of [29] have been extended to walks on the strip in [44]. In this paper we obtain quenched mixing in both independent and quasiperiodic environments. In fact, the novel feature of our results is that they are applicable to the environments satisfying explicit estimates, so no stationarity is required in our approach.
4. The Green function

The main result of this section is the asymptotic expansion of the Green function for the exit from a large interval (see Lemma 4.3). This asymptotic expansion plays a major role in the proofs of our main results: it allows us to compute limits of ratios of various additive functionals of our random walk using moderate deviation estimates from Appendix A.

We begin with a preliminary fact, establishing a relation between two key quantities $m_{n}$ and $ρ_{n}$ which appear in the expansion of the Green function

Lemma 4.1.
If $m_{n}$ satisfies ( 2.26 ) and $ρ_{n}$ satisfies ( 2.27 ) then there exist a constant c such that for all n $\begin{array}{l} ρ_{n + 1} Q_{n + 1} (m_{n} - ζ_{n} m_{n + 1}) = c, \\ ρ_{n} P_{n} (m_{n + 1} - ζ_{n + 1}^{-} m_{n}) = - c . \end{array}$

This lemma complements [20, Lemmas 4.5 and 4.6] where other relations between $ρ_{n}$ and $m_{n}$ are described.
Proof.
Let $\begin{matrix} (4.1) & u_{n} = m_{n} - ζ_{n} m_{n + 1} . \end{matrix}$ Then $\begin{matrix} (4.2) & u_{n} = A_{n} u_{n - 1} . \end{matrix}$ Indeed (2.26) can be rewritten as $\begin{matrix} (4.3) & (I - R_{n}) m_{n} = P_{n} m_{n + 1} + Q_{n} m_{n - 1} . \end{matrix}$ Since $ζ_{n} = {(I - R_{n} - Q_{n} ζ_{n - 1})}^{- 1} P_{n}$ we have $\begin{matrix} P_{n} = (I - R_{n} - Q_{n} ζ_{n - 1}) ζ_{n} . \end{matrix}$ Plugging this into (4.3) we get $\begin{matrix} (I - R_{n}) m_{n} = (I - R_{n} - Q_{n} ζ_{n - 1}) ζ_{n} m_{n + 1} + Q_{n} m_{n - 1} . \end{matrix}$ Subtracting $Q_{n} ζ_{n - 1} m_{n}$ from both sides we get $\begin{matrix} (I - R_{n} - Q_{n} ζ_{n - 1}) m_{n} = (I - R_{n} - Q_{n} ζ_{n - 1}) ζ_{n} m_{n + 1} + Q_{n} (m_{n - 1} - ζ_{n - 1} m_{n}) . \end{matrix}$ Multiplying both sides by ${(I - R_{n} - Q_{n} ζ_{n - 1})}^{- 1}$ and remembering that $\begin{matrix} A_{n} = {(I - R_{n} - Q_{n} ζ_{n - 1})}^{- 1} Q_{n} \end{matrix}$ we obtain (4.2).

Observe that (2.11) implies that $Q_{n + 1} A_{n} = α_{n} Q_{n}$ . Hence (4.2) gives $\begin{matrix} ρ_{n + 1} Q_{n + 1} u_{n} = ρ_{n + 1} Q_{n + 1} A_{n} u_{n - 1} = ρ_{n + 1} α_{n} Q_{n} u_{n - 1} = ρ_{n} Q_{n} u_{n - 1} \end{matrix}$ proving the first claim of the lemma. A similar computation shows that $\begin{matrix} ρ_{n} P_{n} (m_{n + 1} - ζ_{n + 1}^{-} m_{n}) = c^{-} . \end{matrix}$ It remains to relate c to $c^{-}$ . To this end note that $\begin{array}{l} c & = ρ_{n + 1} Q_{n + 1} (m_{n} - ζ_{n} m_{n + 1}) \\ = ρ_{n + 1} Q_{n + 1} m_{n} - ρ_{n + 1} Q_{n + 1} {(I - R_{n} - Q_{n} ζ_{n - 1})}^{- 1} P_{n} m_{n + 1} \\ = ρ_{n + 1} Q_{n + 1} m_{n} - ρ_{n + 1} α_{n} P_{n} m_{n + 1} = ρ_{n + 1} Q_{n + 1} m_{n} - ρ_{n} P_{n} m_{n + 1} . \end{array}$ Likewise $\begin{matrix} c^{-} = ρ_{n} P_{n} m_{n + 1} - ρ_{n + 1} Q_{n + 1} m_{n} = - c \end{matrix}$ finishing the proof. □

Next, (2.24) and property (2.13) imply the following Lemma.
Lemma 4.2.
Suppose that ( 2.4 ) is satisfied and the potential ( 2.22 ) is bounded. Then:
there is a bounded solution $u_{n}$ to $u_{n} = A_{n} u_{n - 1}$ , $\infty < n < \infty$ , and such that all entries of all vectors $u_{n}$ have the same sign.

if a sequence of vectors ${\tilde{u}}_{n}$ satisfies ${\tilde{u}}_{n} = A_{n} {\tilde{u}}_{n - 1}$ , $\infty < n < \infty$ , and $\frac{1}{n} ln ‖ {\tilde{u}}_{n} ‖ \to 0$ as $n \to - \infty$ then ${\tilde{u}}_{n}$ is bounded and proportional to $u_{n}$ .

Proof.
It will be convenient to use the following notation: for $k ⩽ n$ $\begin{matrix} A_{n}^{k} = A_{n} \dots A_{k + 1}, with the convention A_{n}^{n} = I, A_{n}^{n - 1} = A_{n} . \end{matrix}$ We make use of $v_{n}$ from (2.14). To construct $u_{n}$ for $n ⩾ 0$ set $u_{0} = v_{0}$ and define $u_{n} = A_{n}^{0} u_{0}$ for $n ⩾ 1$ . Obviously, $u_{n} = A_{n} u_{n - 1}$ if $n ⩾ 1$ .

For $n ⩽ - 1$ , set $u_{n} \overset{def}{=} λ_{0}^{- 1} \dots λ_{n + 1}^{- 1} v_{n}$ . Then, taking into account (2.18), we have for $n ⩽ 0$ : $\begin{matrix} A_{n} u_{n - 1} = λ_{0}^{- 1} \dots λ_{n + 1}^{- 1} λ_{n}^{- 1} A_{n} v_{n - 1} = λ_{0}^{- 1} \dots λ_{n + 1}^{- 1} v_{n} = u_{n} . \end{matrix}$ The vectors $u_{n}$ are strictly positive since $v_{n} > 0$ for all n. Finally, since $u_{n} = A_{n} \dots A_{k + 1} u_{k}$ for any $n > k$ , the inequalities (2.24) imply that $e^{- {\tilde{C}}_{P}} ‖ u_{k} ‖ ⩽ ‖ u_{n} ‖ ⩽ e^{{\tilde{C}}_{P}} ‖ u_{k} ‖$ and so this solution is bounded. This completes the proof of (i).

Proof of (ii). We shall show that for any fixed n there is a c such that ${\tilde{u}}_{n} = c u_{n}$ .

For $k ⩽ n$ , present ${\tilde{u}}_{k} = {\tilde{u}}_{k}^{+} - {\tilde{u}}_{k}^{-}$ , where ${\tilde{u}}_{k}^{+} ⩾ 0$ and ${\tilde{u}}_{k}^{-} ⩾ 0$ are, respectively, the positive and the negative part of ${\tilde{u}}_{k}$ . Then $‖ {\tilde{u}}_{k}^{+} ‖ ⩽ ‖ {\tilde{u}}_{k} ‖$ and $‖ {\tilde{u}}_{k}^{-} ‖ ⩽ ‖ {\tilde{u}}_{k} ‖$ . It follows from (2.24) that $‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ = O (‖ {\tilde{u}}_{k}^{+} ‖) = O (‖ {\tilde{u}}_{k} ‖)$ . This, together with (2.15) implies $A_{n}^{k} {\tilde{u}}_{k}^{+} = ‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ (v_{n} + O (θ^{n - k})) = ‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ v_{n} + O (‖ {\tilde{u}}_{k} ‖ θ^{n - k})$ . Finally, $\begin{matrix} A_{n}^{k} {\tilde{u}}_{k}^{+} = ‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ ‖ u_{n} ‖^{- 1} u_{n} + O (‖ {\tilde{u}}_{k} ‖ θ^{k - n}) \end{matrix}$ since $v_{n} = u_{n} / ‖ u_{n} ‖$ . Similarly, $A_{n}^{k} {\tilde{u}}_{k}^{-} = ‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ ‖ u_{n} ‖^{- 1} u_{n} + O (‖ {\tilde{u}}_{k} ‖ θ^{n - k})$ . But ${\tilde{u}}_{n} = A_{n}^{k} {\tilde{u}}_{k}^{+} - A_{n}^{k} {\tilde{u}}_{k}^{-}$ we have $\begin{matrix} {\tilde{u}}_{n} = (‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ - ‖ A_{n}^{k} {\tilde{u}}_{k}^{-} ‖) ‖ u_{n} ‖^{- 1} u_{n} + O (‖ {\tilde{u}}_{k} ‖ θ^{n - k}) . \end{matrix}$ The growth of $‖ {\tilde{u}}_{k}^{-} ‖$ is sub-exponential and therefore, sending $k \to - \infty$ , we see that $c_{n} \overset{def}{=} {lim}_{k \to - \infty} (‖ A_{n}^{k} {\tilde{u}}_{k}^{+} ‖ - ‖ A_{n}^{k} {\tilde{u}}_{k}^{-} ‖) ‖ u_{n} ‖^{- 1}$ exists and ${\tilde{u}}_{n} = c_{n} u_{n}$ . But then $c_{n} u_{n} = c_{n - 1} A_{n} u_{n - 1}$ by the definition of ${\tilde{u}}_{n}$ which, together with (4.2), implies that $(c_{n} - c_{n - 1}) u_{n} = 0$ . Hence $c_{n} = c_{n - 1} = const$ . □

Returning to the main equation (2.26) for $m_{n}$ , we have now two possibilities.

$u_{n} \equiv 0$ . In this case, (4.1) implies that for each $k ⩾ 1$ , $m_{n} = ζ_{n} ζ_{n + 1} \dots ζ_{n + k} m_{n + k}$ . Sending k to infinity and using contracting properties of stochastic matrices we see that $m_{n} \equiv c 1$ for some constant c.

$u_{n}$ is non zero, so its entries have the same sign. Then $c = ρ_{n + 1} Q_{n + 1} u_{n} \neq 0$ .

We note that in the second case the martingale increases faster than some linear function. Namely there are constants $C_{1}$ , $C_{2}$ such that for any $n, k \in Z$ , $k ⩾ 0$ and for any $i, j \in {1, \dots, m}$ we have $\begin{matrix} (4.4) & \frac{k}{C_{1}} - C_{2} ⩽ m_{n + k} (j) - m_{n} (i) ⩽ C_{1} k + C_{2} . \end{matrix}$ Indeed, iterating (4.1) we obtain $\begin{matrix} (4.5) & m_{n} = \sum_{r = 0}^{k - 1} u_{n, r} + ζ_{n} \dots ζ_{n + k - 1} m_{n + k} \end{matrix}$ where $u_{n, r} = ζ_{n} \dots ζ_{n + r - 1} u_{n + r}$ . Note that by (2.24) the components of $u_{n}$ are uniformly bounded from above and bounded away from zero. Since ζ’s are stochastic, we conclude that the components of $u_{n, r}$ are uniformly bounded from above and bounded away from zero. Since $m$ has bounded increments we have that for each $j = 1, \dots, m$ , $m_{n + k} = m_{n + k} (j) 1 + O (1)$ . Plugging this into (4.5) and using that $ζ_{n} \dots ζ_{n + k - 1} 1 = 1$ we obtain (4.4).

In this paper we deal with the case where the martingale $m$ is non-trivial. Moreover, for the rest of the paper (except for the Section 7) we assume that $m$ is asymptotically linear and that $m$ and ρ are normalized so that $\begin{matrix} (4.6) & lim_{n \to \infty} \frac{M_{n}}{n} = m, \end{matrix}$ where $M_{n} = \sum_{j = 1}^{m} m_{n} (j)$ and $\begin{matrix} (4.7) & ρ_{n} P_{n} (m_{n + 1} - ζ_{n + 1}^{-} m_{n}) = \frac{1}{2 m} . \end{matrix}$ Note that (4.6) and (2.25) imply that $\begin{matrix} (4.8) & lim_{n \to \infty} \frac{m_{n} (y)}{n} = 1 \end{matrix}$ uniformly in $y \in {1, \dots, m}$ .

Asymptotically linear martingales exist in Examples 3.1–3.3. In fact, in Section 6.4 we will establish a stronger result (6.11).

Consider the Green function $\begin{matrix} G_{a, b} ((k, i); (n, j)) = E (η_{(n, j)} | ξ (0) = (k, i)), \end{matrix}$ where $η_{(n, j)}$ is the number of visits to $(n, j)$ by the walk starting at $(k, i)$ before it hits the segment $[a, b]$ . Lemma 4.3.
For $x, y \in (a, b)$ $\begin{matrix} G_{a, b} ((k, i); (n, j)) = G (M_{k}, M_{n}, M_{a}, M_{b}) ρ_{n} (j) + O (1) \end{matrix}$ where $\begin{matrix} G (x, y, a, b) = \frac{2 (min (x, y) - a) (b - max (x, y))}{(b - a)} . \end{matrix}$
Proof.
Let $\begin{matrix} (4.9) & {\tilde{G}}_{a, b} ((k, i); n) = \sum_{j} G_{a, b} ((k, i), (n, j)) . \end{matrix}$ A simple computation with Markov chains [17, Appendix A] shows that $\begin{matrix} G_{a, b} ((k, i), (n, j)) = {\tilde{G}}_{a, b} ((k, i), n) \frac{ρ_{n} (j)}{ρ_{n} 1} + O (1) \end{matrix}$ so it suffices to show that $\begin{matrix} (4.10) & {\tilde{G}}_{a, b} ((k, i); n) = G (M_{k}, M_{n}, M_{a}, M_{j}) ρ_{n} 1 + O (1) . \end{matrix}$ We consider first the case where $k = n$ . Let $d = min (n - a, b - n)$ . Denote $η_{n} = η_{n} 1$ . Let $p_{n, a, b}$ be the vector $\begin{matrix} p_{n, a, b} (i) = P (η_{n} = 1 | ξ (0) = (n, i)) . \end{matrix}$

We claim that $\begin{matrix} (4.11) & p_{n, a, b} = O (1 / d) . \end{matrix}$ Without loss of generality we may assume that $d = b - n$ . By (4.4) there exists k such that for any n, i, j $m_{n + k} (j) ⩾ m_{n} (i) + 1$ . Consider our walk started from $(n + k, j)$ . Let $s$ be the first time this walk reaches either $L_{n}$ or $L_{b}$ . Applying the Optional Stopping Theorem to this stopping time gives $\begin{matrix} m_{n + k} (j) = \sum_{i = 1}^{m} P (ξ_{s} = (n, i)) m_{n} (i) + \sum_{i = 1}^{m} P (ξ_{s} = (b, i)) m_{b} (i) . \end{matrix}$ Rewriting this identity as $\begin{matrix} (4.12) & \sum_{i = 1}^{m} P (ξ_{s} = (n, i)) [m_{n + k} (j) - m_{n} (i)] = \sum_{i = 1}^{m} P (ξ_{s} = (b, i)) [m_{b} (i) - m_{n + k} (j)] . \end{matrix}$ By our choice of k the LHS is at least $1 - P (ξ_{s} \in L_{b})$ while by (4.4) the RHS is at most $2 C_{1} d P (ξ_{s} \in L)$ . Thus $\begin{matrix} 1 ⩾ 2 C_{1} d P (ξ_{s} \in L) or P (ξ_{s} \in L_{b}) = O (1 / d) . \end{matrix}$ In other words, if the walker starts from the layer $n + k$ then the probability that it would not visit $L_{n}$ before reaching $L_{b}$ is $O (1 / d)$ . By the same argument, if the walker starts from the layer $n - k$ then the probability that it would not visit $L_{n}$ before reaching $L_{a}$ is $O (1 / d)$ . Since the walker starting from $L_{n}$ should visit $L_{n - k}$ before reaching $L_{a}$ and it should visit $L_{n + k}$ before reaching $L_{b}$ , (4.11) follows.

Let ${\tilde{S}}_{n}$ be the matrix with components ${\tilde{S}}_{n} (i, j)$ where ${\tilde{S}}_{n} (i, j)$ is the probability that the walker starting from $(n, i)$ returns to $L_{n}$ for the first time at $(n, j)$ given that it does not visit $L_{a}$ or $L_{b}$ in between. Let ${\tilde{π}}_{n}$ be the stationary distribution for ${\tilde{S}}_{n}$ . Also let $S_{n}$ be the matrix with components $S_{n} (i, j)$ , where $S_{n} (i, j)$ is the probability that the walker starting from $(n, i)$ returns to $L_{n}$ for the first time at $(n, j)$ . Thus $\begin{matrix} S_{n} = Q_{n} ζ_{n - 1} + R_{n} + P_{n} ζ_{n + 1}^{-} . \end{matrix}$ Let $π_{n}$ be the stationary distribution of $S_{n}$ . Note that $π_{n}$ can be expressed in terms of $ρ_{n}$ as $π_{n} (j) = \frac{ρ_{n} (j)}{ρ_{n} 1}$ . Since, by (4.11), $S_{n}$ and ${\tilde{S}}_{n}$ differ by conditioning on a set of measure $1 - O (\frac{1}{d})$ we have ${\tilde{S}}_{n} = S_{n} + O (\frac{1}{d})$ . Moreover we can write $\begin{matrix} {\tilde{S}}_{n} = Q_{n} {\tilde{ζ}}_{n - 1} + R_{n} + P_{n} {\tilde{ζ}}_{n + 1}^{-} \end{matrix}$ where ${\tilde{ζ}}_{n - 1} (i, j)$ and $ζ_{n + 1}^{-} (i, j)$ are the probabilities that the walker starting from $(n - 1, i)$ (respectively $(n + 1, i)$ ) returns to $L_{n}$ for the first time at $(n, j)$ given that it does not visit $L_{a}$ or $L_{b}$ in between. Then $\begin{matrix} (4.13) & {\tilde{ζ}}_{n - 1} = ζ_{n - 1} + O (\frac{1}{d}), {\tilde{ζ}}_{n + 1}^{-} = ζ_{n + 1}^{-} + O (\frac{1}{d}) . \end{matrix}$

Due to exponential mixing of both $S_{n}$ and ${\tilde{S}}_{n}$ (which is guaranteed by condition (2.4)) we have that $\begin{matrix} {\tilde{π}}_{n} = π_{n} + O (\frac{1}{d}) = \frac{ρ_{n}}{ρ_{n} 1} + O (\frac{1}{d}) . \end{matrix}$ We have $\begin{matrix} P (η_{n} = N + 1 | η_{n} > N, ξ (0) = (n, i)) = e_{i} {\tilde{S}}_{n}^{N} p_{n, a, b} . \end{matrix}$ By the first step analysis $\begin{matrix} (4.14) & p_{n, a, b} (i) = \sum_{j = 1}^{m} Q_{n} (i, j) p_{n}^{-} (j) + \sum_{j = 1}^{m} P_{n} (i, j) p_{n}^{+} (j) \end{matrix}$ where $p_{n}^{\pm} (j)$ is the probability that the walker starting from $(n \pm 1, j)$ does not return to $L_{n}$ before visiting the boundary of the segment a, b. By the Optional Stopping Theorem and (2.25) $\begin{matrix} (4.15) & p_{n}^{-} = \frac{{\tilde{ζ}}_{n - 1} m_{n} - m_{n - 1}}{\frac{1}{m} (M_{n} - M_{a})} + O (\frac{1}{d^{2}}), p_{n}^{+} = \frac{{\tilde{ζ}}_{n + 1}^{-} m_{n} - m_{n + 1}}{\frac{1}{m} (M_{b} - M_{n})} + O (\frac{1}{d^{2}}) . \end{matrix}$ From (4.14) and (4.15) we get using (4.13) that $\begin{matrix} (4.16) & p_{n, a, b} (i) = m e_{i} (Q_{n} \frac{ζ_{n - 1} m_{n} - m_{n - 1}}{M_{n} - M_{a}} + P_{n} \frac{ζ_{n + 1}^{-} m_{n} - m_{n + 1}}{M_{b} - M_{n}}) + O (\frac{1}{d^{2}}) . \end{matrix}$

Since $e_{i} {\tilde{S}}_{n}^{N} = {\tilde{π}}_{n} (1 + O (θ^{N}))$ for some $θ < 1$ , it follows that $\begin{matrix} e_{i} {\tilde{S}}_{n}^{N} p_{n, a, b} = {\tilde{π}}_{n} p_{n, a, b} + O (θ^{N}) . \end{matrix}$ From (4.16), Lemma 4.1 and (4.7) we get $\begin{array}{l} {\tilde{π}}_{n} p_{n, a, b} & = \frac{m}{ρ_{n} 1} (\frac{ρ_{n} Q_{n} (m_{n - 1} - ζ_{n - 1} m_{n})}{M_{n} - M_{a}} + \frac{ρ_{n} P_{n} (m_{n + 1} - ζ_{n + 1}^{-} m_{n})}{M_{b} - M_{n}} + O (\frac{1}{d^{2}})) \\ = \frac{1}{2 ρ_{n} 1} (\frac{1}{M_{n} - M_{a}} + \frac{1}{M_{b} - M_{n}} + O (\frac{1}{d^{2}})) . \end{array}$

It follows that ${\tilde{π}}_{n} p_{n, a, b} η_{n}$ has asymptotically exponential distribution with parameter 1 and hence $\begin{matrix} {\tilde{G}}_{a, b} ((n, i); n) = \frac{1}{{\tilde{π}}_{n} p_{n, a, b}} + O (1) = \frac{2 (M_{n} - M_{a}) (M_{b} - M_{n})}{(M_{b} - M_{a})} (ρ_{n} 1) + O (1) . \end{matrix}$ Next for $k < n$ let $\begin{matrix} P_{a} ((k, i); (n, j)) = P (ξ reaches L_{n} at (n, j) before reaching L_{a} | ξ (0) = (k, i)) . \end{matrix}$ Then $\begin{array}{l} {\tilde{G}}_{a, b} ((k, i); n) & = \sum_{j} P_{a} ((k, i); (n, j)) {\tilde{G}}_{a, b} ((n, j); n) \\ = [\frac{2 (M_{n} - M_{a}) (M_{b} - M_{n})}{(M_{b} - M_{a})} (ρ_{n} 1) + O (1)] \sum_{j} P_{a} ((k, i); (n, j)) . \end{array}$ Note that $\begin{matrix} P_{a} ((k, i); n) : = \sum_{j} P_{a} ((k, i); (n, j)) = P (ξ reaches L_{n} before reaching L_{a} | ξ (0) = (k, i)) . \end{matrix}$ Applying again the Optional Stopping Theorem to the stopping time $s$ which is the first time the walker reaches either $L_{a}$ or $L_{b}$ we get $\begin{matrix} (M_{n} + O (1)) P_{a} ((k, i); n) + (M_{a} + O (1)) (1 - P_{a} ((k, i); n)) = M_{k} + O (1) . \end{matrix}$ Hence $\begin{matrix} P_{a} ((k, i); n) = \frac{M_{k} - M_{a}}{M_{n} - M_{a}} + O (\frac{1}{d}) . \end{matrix}$ This proves (4.10) for $k < n$ . The case $k > n$ is analyzed similarly. □
Remark 4.4.
(4.12) also shows that there is a constant c such that for each $y \in {1, \dots, m}$ $\begin{matrix} (4.17) & P (η_{n} = 1 | ξ (0) = (n, y)) ⩽ \frac{c}{d} . \end{matrix}$ This bound will be useful in Section 6.

5. Environment viewed by the particle: The law of large numbers

From now on we consider only those environments which, in addition to (2.24), (4.6), (4.7), satisfy the following assumption: there exists a constant a such that $\begin{matrix} (5.1) & lim_{N \to \pm \infty} \frac{1}{| N |} \sum_{n = 0}^{N - 1} ρ_{n} 1 = a . \end{matrix}$ Examples 3.1–3.3 satisfy (5.1). In fact, in Section 6.4 we prove a stronger result (6.12).

Let $h : S \to R$ be a bounded function and $h_{n}$ be a sequence of vectors with components $h_{n} (i) = h (n, i)$ . Let $\begin{matrix} (5.2) & H_{N} = \sum_{n = 0}^{N - 1} h (ξ (n)) . \end{matrix}$ In this section we establish the following result.

Lemma 5.1.
Suppose that $h_{n}$ is such that $\begin{matrix} (5.3) & lim_{N \to \pm \infty} \frac{1}{| N |} \sum_{n = 0}^{N - 1} ρ_{n} h_{n} = h \end{matrix}$ for some constant $h$ . Then $\frac{H_{N}}{N}$ converges in probability, as $N \to \infty$ , to $\frac{h}{a}$ .
Remark 5.2.
Assumptions (5.1) and (5.3) imply that h is an extensive observable, that is there exists the finite volume limit $\begin{matrix} lim_{R \to \pm \infty} \frac{\int_{S_{R}} h (z) d μ (z)}{μ (S_{R})} = \frac{h}{a} \end{matrix}$ where $S_{R}$ is the set of points in the strip $S$ such that the x coordinate is between 0 and R and μ is the invariant measure for our walk: for $A \in S$ $\begin{matrix} μ (A) = \sum_{z \in A} ρ (z) . \end{matrix}$ We refer the reader to [36] for a discussion of the ergodic properties of extensive observables.

A typical application of Lemma 5.1 is the following. Suppose that the environment $ω = {((P_{n}, Q_{n}, R_{n}))}_{n = - \infty}^{\infty}$ is as in Remark 2.3 and set $h_{n} = 1_{(T^{n} ω, Y_{n}) \in A} 1$ , where $A \subset Ω \times {1, \dots, m}$ (this defines a function h – see Section 2.1). Then $\frac{H_{N}}{N}$ describes how often the walker sees the environment from $A$ . For example, one can ask how often the drift or the variance of the walker’s increment are of a certain size. Quite often the law of large numbers for $H_{N}$ is obtained as a consequence of ergodicity of the environment viewed by the particle process, see e.g. [7]. This approach, however, makes it difficult to control the exceptional zero measure set in the ergodic theorem. In this section we present a different argument which allows one to obtain explicit sufficient conditions for the law of large numbers (namely, (5.3)). Proof of Lemma 5.1.
Let us first describe the idea of the proof. Fix $ε > 0$ . We need to show that $H_{N} - (\frac{h}{a} - ε) N$ is positive for large N while $H_{N} - (\frac{h}{a} + ε) N$ is negative for large N with probability close to 1. To this end we divide the sum (5.2) into blocks. Choose a small constant δ (the exact requirements on δ will be explained later, see the proof of (5.9) below) and let $L_{N} = ⌊ δ \sqrt{N} ⌋$ . We will consider our random walk only at the moments when $X (t)$ visits the nodes of the lattice $L_{N} Z$ , more precisely, when X moves from one node to the next. That is, define $τ_{0} = 0$ , and for $k > 0$ let $\begin{matrix} (5.4) & τ_{k} = min (j ⩾ τ_{k - 1} : X_{j} = X_{τ_{k - 1}} - L_{N} or X_{j} = X_{τ_{k - 1}} + L_{N}) . \end{matrix}$ We would like to use the results of Section 4 to show $H_{(k, ε)}^{+} : = \sum_{n = 1}^{τ_{k}} [h (ξ (n)) - (\frac{h}{a} - ε)]$ is a submartingale and $H_{(k, ε)}^{-} : = \sum_{n = 1}^{τ_{k}} [h (ξ (n)) - (\frac{h}{a} + ε)]$ is a supermartingale with respect to the natural filtration and then use the large deviation estimates for supermartgales from Appendix A. However, for a fixed δ, (4.6) and (5.3) only allow us to control the nodes of $L_{N} Z$ which are not too far from the origin, so an additional cut off is required.

Using the maximal inequality for martingales we can find a constant K such that $\begin{matrix} P (max_{t \in [0, N]} | m (ξ (t)) | ⩾ \frac{K \sqrt{N}}{2}) ⩽ \frac{ε}{2} . \end{matrix}$ Now (4.8) gives $\begin{matrix} (5.5) & P (max_{t \in [0, N]} | X (t) | ⩾ K \sqrt{N}) ⩽ \frac{ε}{2} . \end{matrix}$

Denoting $a_{k} = X_{τ_{k - 1}} - L_{N}$ , $b_{k} = X_{τ_{k - 1}} + L_{N}$ we have $\begin{matrix} (5.6) & E (τ_{k} - τ_{k - 1} | ξ_{τ_{k - 1}}) = \sum_{n = a_{k}}^{b_{k}} \sum_{j = 1}^{m} G_{a_{k}, b_{k}} (ξ_{τ_{k - 1}}; (n, j)) . \end{matrix}$ We claim that for each K we have $\begin{matrix} (5.7) & E (τ_{k} - τ_{k - 1} | ξ_{τ_{k - 1}}) \sim a L_{N}^{2} \end{matrix}$ provided that N is large enough and $| X_{τ_{k - 1}} | ⩽ K \sqrt{N}$ .

To prove (5.7) divide the segment $[a_{k}, b_{k}]$ into subsegments $I_{j} = [s_{j}, s_{j + 1}]$ of length $[\tilde{δ} \sqrt{N}]$ where $\tilde{δ} ≪ δ$ . (4.6), Lemma 4.3, and (5.1) show that the contribution to (5.6) of terms with $n \in I_{j}$ is asymptotic to $\begin{matrix} {\tilde{δ}}_{N} a G (0, s_{j} - X_{τ_{k - 1}}; - L_{N}, L_{N}) . \end{matrix}$ Summing over the intervals $I_{j}$ we obtain (5.7).

Let $\begin{matrix} (5.8) & \hat{k} = a^{- 1} δ^{- 2}, \end{matrix}$ $T_{N} = τ_{\hat{k}}$ . We claim that if δ is sufficiently small then $\begin{matrix} (5.9) & P (| \frac{T_{N}}{N} - 1 | > ε) < ε . \end{matrix}$ Indeed define a sequence ${\tilde{τ}}_{k}$ such that ${\tilde{τ}}_{0} = 0$ and $\begin{matrix} {\tilde{τ}}_{k} - {\tilde{τ}}_{k - 1} = \{\begin{matrix} τ_{k} - τ_{k - 1} & if | ξ_{τ_{k - 1}} | ⩽ K \sqrt{N}, \\ a L_{N}^{2} & otherwise. \end{matrix} \end{matrix}$ We want to estimate $P ({\tilde{τ}}_{\hat{k}} ⩾ (1 + ε) N)$ . To this end we apply Proposition A.1 from Appendix A with $\begin{matrix} Δ_{k} = \frac{({\tilde{τ}}_{k} - {\tilde{τ}}_{k - 1})}{a L_{N}^{2}} - (1 + ε) . \end{matrix}$ To apply this proposition we need to check conditions (A.1) and (A.2). For the case at hand, (A.1) follows from (5.7). To prove (A.2) we use that there exists a constant $θ < 1$ such that for each $K \in R$ there is a constant $N_{0} = N_{0} (K)$ such that if $N ⩾ N_{0}$ and $| ξ_{τ_{k - 1}} | ⩽ K \sqrt{N}$ then for all $l \in N$ $\begin{matrix} (5.10) & P (τ_{k} - τ_{k - 1} > 2 a l L_{N}^{2}) < θ^{l} . \end{matrix}$ Indeed similarly to (5.7) one can show that if $N ⩾ N_{0} (K)$ then for each $(x, y)$ such that $| x - x (ξ_{τ_{k - 1}}) | ⩽ L_{N}$ for each $s \in Z$ we have $\begin{matrix} E (τ_{k} - s | ξ (s) = (x, y)) ⩽ 1.1 a L_{N}^{2} . \end{matrix}$ Combining this with the Markov inequality we see that for any stopping time $s$ $\begin{matrix} (5.11) & P (τ_{k} > s + 2 a L_{N}^{2} | τ_{k} ⩾ s) ⩽ \frac{1.1}{2} . \end{matrix}$ Applying (5.11) with $s = τ_{k - 1}$ we obtain (5.10) with $l = 1$ . (5.10) for $l > 1$ follows by induction on l by applying (5.11) with $s = τ_{k - 1} + 2 a (l - 1)$ .

Now Proposition A.1 gives $\begin{matrix} P ({\tilde{τ}}_{\hat{k}} ⩾ (1 + ε) N) ⩽ e^{- \bar{c} \sqrt{ε \hat{k}}} . \end{matrix}$ Likewise $\begin{matrix} P ({\tilde{τ}}_{\hat{k}} ⩽ (1 - ε) N) ⩽ e^{- \bar{c} \sqrt{ε \hat{k}}} . \end{matrix}$ Combining the last two displays with (5.8) we see that for large N $\begin{matrix} (5.12) & P (| \frac{{\tilde{τ}}_{\hat{k}}}{N} - 1 | > ε) < \frac{ε}{2} . \end{matrix}$ By our choice of K (see (5.5)), for large N we have $\begin{matrix} (5.13) & P ({\tilde{τ}}_{\hat{k}} \neq T_{N}) < \frac{ε}{2} . \end{matrix}$ Combining (5.12) and (5.13) we obtain (5.9).

Next, similarly to (5.7) we get $\begin{matrix} (5.14) & E (H_{τ_{k}} - H_{τ_{k - 1}} | ξ_{τ_{k - 1}}) \sim \frac{h L_{N}^{2}}{2} \end{matrix}$ and similarly to (5.9) we get (possibly, after decreasing δ) that $\begin{matrix} P (| \frac{H_{τ_{\bar{k}}}}{N} - \frac{h}{a} | > ε) < ε . \end{matrix}$ Indeed we can apply Proposition A.1 since (A.1) follows by (5.14) while (A.2) follows from (5.10) since h is bounded so for some constant C $\begin{matrix} | H_{τ_{k}} - H_{τ_{k - 1}} | ⩽ C (τ_{k} - τ_{k - 1}) . \end{matrix}$ Also since h is bounded, $\frac{| H_{τ_{\bar{k}}} - H_{N} |}{N} ⩽ C | \frac{τ_{\bar{k}}}{N} - 1 |$ and so (5.12) and (5.13) give $\begin{matrix} (5.15) & P (\frac{| H_{τ_{\bar{k}}} - H_{N} |}{N} > C ε) < ε . \end{matrix}$ Since ε is arbitrary, (5.14) and (5.15) prove the lemma. □
Remark 5.3.
We note that the information on $X_{τ_{k}}$ obtained in the proof of Lemma 5.1, especially (5.14), will play a crucial role in the sequel. In particular, it will be used in Section 6 to show that, under appropriate assumptions, $X_{τ_{k}} / L_{N}$ is well approximated by the simple random walk. Passing to the limit as $N \to \infty$ , $δ_{N} \to 0$ we shall obtain the CLT for $X (t)$ .

6. The Central Limit Theorem

6.1. Sufficient conditions for the CLT

In this section, with a slight abuse of notation, we write $ξ_{N t}$ , $X_{N t}$ , and $Y_{N t}$ for $ξ_{⌊ N t ⌋}$ , $X_{⌊ N t ⌋}$ , $Y_{⌊ N t ⌋}$ respectively.

Denote $W_{N} (t) = \frac{X_{N t}}{\sqrt{N}}$ , where $t \in [0, 1]$ . Let $q_{n}$ be a column vector with components $\begin{matrix} q_{n} (i) & = E ({(m (ξ_{k + 1}) - m (ξ_{k}))}^{2} | ξ_{k} = (n, i)) \\ = \sum_{j^{'} \in {- 1, 0, 1}, 1 ⩽ i^{'} ⩽ m} P ((n, i), (n + j^{'}, i^{'})) {(m_{n + j^{'}} (i^{'}) - m_{n} (i))}^{2}, \end{matrix}$ where $P (\cdot, \cdot)$ are the transition probabilities (2.2) and $m_{n} (i)$ , $m (ξ_{k})$ , etc are as in (2.26) and Remark 2.1.

Theorem 6.1.
If ( 5.1 ) holds and there is a constant b such that $\begin{matrix} (6.1) & lim_{N \to \pm \infty} \frac{1}{| N |} \sum_{n = 0}^{N - 1} ρ_{n} q_{n} = b \end{matrix}$ then $W_{N} (t)$ converges in law as $N \to \infty$ to $W (t)$ -the Brownian Motion with zero mean and variance $D t$ , where $D = \frac{b}{a}$ with b as in ( 6.1 ) and a as in ( 5.1 ).
Proof.
In view of (4.8) it suffices to show that $\begin{matrix} (6.2) & {\hat{W}}_{N} (t) \Rightarrow W \end{matrix}$ where $\begin{matrix} (6.3) & {\hat{W}}_{N} (t) = \frac{m (ξ_{N t})}{\sqrt{N}} . \end{matrix}$ Let $Q_{N} = \sum_{n = 0}^{N - 1} q (ξ_{n})$ , where $q (ξ_{n}) = q_{X_{n}} (Y_{n})$ . By [12, Theorem 3] to prove (6.2) it suffices to check that $\begin{matrix} (6.4) & \frac{Q_{N}}{N} \Rightarrow D, \end{matrix}$ but this follows from (6.1) and Lemma 5.1. □
Corollary 6.2.
For uniquely ergodic environments with bounded potential the Central Limit Theorem holds for all ω.

In [19], the Central Limit Theorem was proved for almost all ω for a wide class of environments which includes the uniquely ergodic ones as a particular case. Here, for uniquely ergodic environments, we prove that this result holds for all (rather than almost all) ω.
6.2. Expectation of the local time

Here we discuss the distribution of the local time of the walk. Let $V ((k, y), N)$ be the number of visits to the site $(k, y)$ by our walk before time N.

Lemma 6.3.
Under the assumptions of Section 4 for each $K > 0$ the collection of random variables $\begin{matrix} {\frac{V ((k, y), N) | ξ (0) = z)}{\sqrt{N}}} \end{matrix}$ is uniformly integrable where the uniformity is with respect to $N \in N$ , $z \in S$ , and $(k, y) \in S$ such that $| k | ⩽ K \sqrt{N}$ .

In the proof we will use the following notion. Let $X$ and $Y$ be non-negative random variables. We say that $Y$ stochastically dominates $X$ if for each $t > 0$ $P (X ⩾ t) ⩽ P (Y ⩾ t)$ . Clearly if $Y$ stochastically dominates $X$ then $E (Y) ⩾ E (X)$ .
Proof of Lemma 6.3.
It suffices to prove the result for the walk starting from $z = (k, y)$ since the local time does not accumulate before the first visit to the site $(k, y)$ .

By (5.7) and the maximal inequality for martingales, there is a constant $\hat{p} < 1$ such that for each K there exists $N_{0} (K)$ such that if $N ⩾ N_{0} (K)$ then for any $(k^{'}, y^{'}) \in S$ with $| k^{'} | ⩽ (K + 1) \sqrt{N}$ , the probability that the random walk exits the segment $[k^{'} - \sqrt{N}, k^{'} + \sqrt{N}]$ before time N is less than $\hat{p}$ (In fact, $\hat{p}$ can be any number which is greater than the probability that the Brownian motion with zero mean and with variance $D t$ exits the interval $[- 1, 1]$ before time 1).

Let η be the total number of visits to $(k, y)$ before the walk exits from the segment $(k - \sqrt{N}, k + \sqrt{N})$ . By the foregoing discussion, the probability that $V ((k, y), N) ⩽ η$ is greater than $1 - \hat{p}$ . Therefore, for large N, $V ((k, y), N)$ is stochastically dominated by $η + \hat{p} V ((k, y), N)$ . Iterating this estimate we conclude that $V ((k, y), N)$ is stochastically dominated by $V : = \sum_{r = 1}^{\hat{G}} η_{r}$ where $\hat{G}$ is has geometric distribution with parameter $1 - \hat{p}$ and $η_{r}$ are i.i.d. random variables independent of $\hat{G}$ and having the same distribution as η. Since $E (V) = \frac{E (η)}{1 - \hat{p}}$ it suffices to show the uniform integrability of $η / \sqrt{N}$ (with respect to time and the initial position of the walk). However the fact that ${η / \sqrt{N}}$ is uniformly integrable follows from (4.17). □

Let $l_{x, t}$ denote the local time of the standard Brownian motion.
Theorem 6.4.
Suppose that ( 5.1 ) and ( 6.1 ) hold. Let $(k_{N}, y_{N}) \in S$ be a sequences such that $\frac{k_{N}}{\sqrt{N}} \to x$ as $N \to \infty$ . Then, as $N \to \infty$ $\begin{matrix} \frac{V ((k_{N}, y_{N}), N)}{ρ_{k_{N}} (y_{N}) \sqrt{N}} \Rightarrow l_{x, 1 / a} . \end{matrix}$

Combining Theorem 6.4 with Lemma 6.3 we obtain Corollary 6.5.
Suppose that $(k_{N}, y_{N})$ is a sequence of points in $S$ such that $\frac{k_{N}}{\sqrt{N}} \to x$ . Then uniformly for x in a compact set we have $\begin{matrix} (6.5) & lim_{N \to \infty} E (\frac{V ((k_{N}, y_{N}), N)}{ρ_{k_{N}} (y_{N}) \sqrt{N}}) = E (l_{x, 1 / a}) . \end{matrix}$
Proof of the theorem.
Consider first the case $k_{N} \equiv 0$ . We use the same notation as in the proof of Lemma 5.1. In particular we let $L_{N} = ⌊ δ \sqrt{N} ⌋$ for a small constant δ.

Fix $ε > 0$ . We show that if δ is sufficiently small then for large N the following estimates hold: $\begin{matrix} (6.6) & max_{u \in R} | P (\frac{V ((0, y_{N}), τ_{\hat{k}})}{\sqrt{N}} ⩽ u) - P (ρ (0, y_{N}) l_{0, 1 / a} ⩽ u) | ⩽ ε, \end{matrix}$ where $\hat{k}$ is defined by (5.8), $τ_{k}$ is defined by (5.4) and $\begin{matrix} (6.7) & P (\frac{| V ((0, y_{N}), N) - V ((0, y_{N}), τ_{\hat{k}}) |}{\sqrt{N}} > \sqrt{ε}) ⩽ C \sqrt{ε} . \end{matrix}$

To prove (6.7) we note that by (5.9), if N is large enough, then $P (| τ_{\hat{k}} - N | ⩾ ε N) ⩽ ε$ . On the other hand if $| τ_{\hat{k}} - N | ⩽ ε N$ then $\begin{matrix} | V ((0, y_{N}), N) - V ((0, y_{N}), τ_{\hat{k}}) | ⩽ V ((0, y_{N}), (1 + ε) N) - V ((0, y_{N}), (1 - ε) N) . \end{matrix}$ By Lemma 6.3 the expectation of the RHS is less than $\bar{C} ε \sqrt{N}$ so by the Markov inequality $\begin{matrix} (6.8) & P (V ((0, y_{N}), (1 + ε) N) - V ((0, y_{N}), (1 - ε) N) ⩾ \sqrt{ε} \sqrt{N}) ⩽ \bar{C} \sqrt{ε} . \end{matrix}$ Combining (5.9) and (6.8) we obtain (6.7).

To prove (6.6) let $U_{j}$ be the number of visits to $(0, y_{N})$ during the time interval $[τ_{j - 1}, τ_{j}]$ . Note that $U_{j} = 0$ unless $ξ (τ_{j - 1}) \in L_{0}$ . In case $ξ (τ_{j - 1}) \in L_{0}$ , (4.17) shows that $\begin{matrix} P (U_{j} = 0 | ξ (τ_{j - 1}) \in L_{0}) ⩽ \frac{C}{L_{N}} . \end{matrix}$ On the other hand, the general theory of Markov chains shows that, conditioned on $U_{j} \neq 0$ , $U_{j}$ has geometric distribution with the mean $G_{- L_{N}, L_{N}} ((0, y_{N}); (0, y_{N}))$ and moreover it is independent of $ξ (τ_{j})$ . By Lemma 4.3 $\begin{matrix} G_{- L_{N}, L_{N}} ((0, y_{N}); (0, y_{N})) = L_{N} ρ (0, y_{N}) (1 + o_{N \to \infty} (1)) . \end{matrix}$ Now it is easy to show using, for example, Proposition A.1, that $\begin{matrix} P (| V ((0, y_{N}), τ_{\hat{k}}) - L_{N} n (\hat{k}) ρ (0, y_{N}) |) ⩾ \frac{ε \sqrt{N}}{3}) \to 0 as N \to \infty \end{matrix}$ where $n (k) = Card (j < k : ξ (τ_{j}) \in L_{0})$ .

Since the local time of the simple random walk converges after the diffusive rescaling to a local time of the Brownian Motion [9], we can take δ so small that $\begin{matrix} max_{u \in R} | P (δ \tilde{n} (\hat{k}) ⩽ u) - P (l_{0, 1 / a} ⩽ u) | ⩽ \frac{ε}{3} \end{matrix}$ where $\tilde{n} (\hat{k})$ is the number of times the simple symmetric random walk returns to 0 before time $\hat{k}$ . On the other hand, (4.6) and the Optional Stopping Theorem for martingales show that ${\frac{ξ (τ_{j})}{L_{N}}}_{j \in N}$ converges as $N \to \infty$ to the simple random walk on $Z$ . Hence for each δ we have $\begin{matrix} max_{u \in R} | P (δ \tilde{n} (\hat{k}) ⩽ u) - P (δ n (\hat{k}) ⩽ u) | ⩽ \frac{ε}{3} \end{matrix}$ provided that N is large enough. Combining the last three displays we obtain (6.6).

This completes the proof of the Theorem in the case $k_{N} \equiv 0$ . The same argument shows that for each $k_{N}$ , $y_{N}$ , $y_{N}^{'}$ , if the walk starts from $(k_{N}, y_{N}^{'})$ then $\frac{V ((k_{N}, y_{N}), N)}{\sqrt{N} ρ (k_{N}, y_{N})}$ converges to $l_{0, 1 / a}$ . Let $t_{k}$ be the first time the walk reaches layer $L_{k}$ . Divide $[0, 1]$ into intervals $I_{j}$ of small length h and let $t_{j}$ be the center of $I_{j}$ . By Theorem 6.1, the probability that $\frac{t_{k_{N}}}{N} \in I_{j}$ converges as $N \to \infty$ to $P (T_{x} \in I_{j})$ where $T_{x}$ is the first time the standard Brownian Motion reaches x. On the other hand conditioned on $\frac{t_{N}}{N} \in I_{j}$ we have that the distribution of $\frac{V ((k_{N}, y_{N}), N)}{\sqrt{N}}$ is close to the distribution of $l_{0, (1 - t_{j}) / a}$ (the closeness means that the error goes to 0 when $h \to 0$ and $N \to \infty$ ). Therefore for each s $\begin{matrix} lim_{N \to \infty} P (\frac{V ((k_{n}, y_{N}), N)}{\sqrt{N} ρ (k_{N}, y_{N})} ⩾ s) = \int_{0}^{1} f_{T} (t) P (l_{0, (1 - t) / a} ⩾ s) d t \end{matrix}$ where $f_{T_{x}}$ is the density of $T_{x}$ . The last integral is equal to $P (l_{x, 1 / a} ⩾ s)$ completing the proof of Theorem 6.4. □

6.3. Rate of convergence

Here we estimate the rate of convergence in Theorem 6.1 assuming that we have a good control of error rates in (4.6), (5.1), and (6.1).

Let $Φ (x)$ denote the distribution function of a standard normal random variable.

We will use the following two results.

Proposition 6.6 ([25, Theorem 3.7]).

Given constants $C_{1}$ , $C_{2}$ , $C_{3}$ there is a constant $C_{4}$ such that the following holds. Let $Z_{n}$ be a martingale difference sequence such that for $n ⩽ N$ $\begin{matrix} (6.9) & | Z_{n} | ⩽ C_{1} \end{matrix}$ and $Q_{N} = \sum_{n = 1}^{N} E (Z_{n}^{2} | F_{n - 1})$ satisfies $\begin{matrix} (6.10) & P (| Q_{N} - N | ⩾ C_{2} \sqrt{N} {ln}^{2} N) ⩽ \frac{C_{3} ln N}{N^{1 / 4}} . \end{matrix}$ Then $\begin{matrix} sup_{x} | P (\frac{\sum_{n = 1}^{N} Z_{n}}{\sqrt{N}} ⩽ x) - Φ (x) | ⩽ \frac{C_{4} ln N}{N^{1 / 4}} . \end{matrix}$

Proposition 6.7.
Let S, Z be random variables and set $\begin{matrix} δ = sup_{x} | P (S ⩽ x) - Φ (x) |, δ^{} = sup_{x} | P (S + Z ⩽ x) - Φ (x) | . \end{matrix}$ Then:*
There exists a constant C (independent of S and Z), such that $\begin{matrix} δ^{} ⩽ 2 δ + C {‖ \sqrt{E (Z^{2} | S)} ‖}_{\infty}, \end{matrix}$

$δ^{} ⩽ δ + P$ ( $Z \neq 0$ ).

Proof.
Part (a) is proven in [4, Lemma 1]. To prove part (b) it suffices to observe that by the triangle inequality $| δ - δ^{} | ⩽ {sup}_{x} | P (S ⩽ x) - P (S + Z ⩽ x) |$ . □

In this section, in order to bound the error rate in the CLT, we assume that there is $β_{1} < 1$ such that for each $L ⩾ N^{0.01}$ and each $| k | ⩽ N$ $\begin{array}{l} (6.11) & | m_{k + L} (1) - m_{k - L} (1) - 2 L | ⩽ C L^{1 - β_{1}}, \\ (6.12) & | \sum_{j = k - L}^{k + L} ρ_{j} 1 - 2 L a | ⩽ C L^{1 - β_{1}}, \\ (6.13) & | \sum_{j = k - L}^{k + L} ρ_{j} q_{j} - 2 L b | ⩽ C L^{1 - β_{1}} . \end{array}$ Recall the notation of Section 5. Define $τ_{j}$ as in (5.4) with $L_{N} = N^{1 / 4}$ . Note that (6.12), (6.13) implies that $\begin{array}{l} (6.14) & E (τ_{k} - τ_{k - 1} | ξ_{τ_{k - 1}}) = a L_{N}^{2} (1 + O (L_{N}^{- β_{1}})), \\ (6.15) & E (\sum_{n = τ_{k - 1}}^{τ_{k}} q (ξ_{n}) | ξ_{τ_{k - 1}}) = b L_{N}^{2} (1 + O (L_{N}^{- β_{1}})) \end{array}$ provided that $| X (τ_{k - 1}) | ⩽ N$ .

To establish (6.14) we temporarily denote $\begin{matrix} ξ = ξ_{τ_{k - 1}} = (x, y), c = X (τ_{k - 1}) - L_{N}, d = X (τ_{k - 1}) + L_{N} . \end{matrix}$ Then Lemma 4.3 gives $\begin{matrix} E (τ_{k} - τ_{k - 1} | ξ_{τ_{k - 1}}) = \sum_{n = c}^{d} {\tilde{G}}_{c, d} (ξ; n) . \end{matrix}$ In view of (4.10) and (6.11) $\begin{matrix} \sum_{n = c}^{d} {\tilde{G}}_{c, d} (ξ; n) = [\sum_{n = c}^{d} G (x, n, c, d) ρ_{n} 1] + O (L_{N}^{2 - β_{1}}) . \end{matrix}$ The main term equals to $\begin{array}{l} \sum_{n = c}^{d} G (x, n, c, d) ρ_{n} 1 & = \sum_{n = c}^{d} G (x, n, c, d) a + \sum_{n = c}^{d} G (x, n, c, d) (ρ_{n} 1 - a) \\ = a L_{N}^{2} + O (L_{N}) + \sum_{n = c}^{d} G (x, n, c, d) (ρ_{n} 1 - a) . \end{array}$ To estimate the last term denote $I_{n} = \sum_{k = x}^{n} (ρ_{n} 1 - a)$ . Summation by parts gives $\begin{matrix} \sum_{n = c}^{d} G (x, n, c, d) (ρ_{n} 1 - a) = - \sum_{n = c}^{d} I_{n} \nabla G (x, n, c, d) \end{matrix}$ where ∇ is the difference operator, $\nabla H = H_{n} - H_{n - 1}$ . The first term in the last sum is $O (L_{N}^{1 - β_{1}})$ and the second term is bounded. Whence the last sum is $O (L_{N}^{2 - β_{1}})$ proving (6.14). The proof of (6.15) is similar. Theorem 6.8.
If (* 6.11 ), ( 6.12 ) and ( 6.13 ) hold then for each $ε > 0$ there is a constant $C = C_{ε}$ such that $\begin{matrix} (6.16) & sup_{x} | P (\frac{X_{N}}{\sqrt{D N}} ⩽ x) - Φ (x) | ⩽ C N^{- (υ - ε)} \end{matrix}$ where $\begin{matrix} υ = \frac{1}{2} min (\frac{1}{4}, β_{1}) . \end{matrix}$
Proof.
To establish the theorem it suffices to show that $\begin{matrix} (6.17) & sup_{x} | P (\frac{m (ξ_{N})}{\sqrt{D N}} ⩽ x) - Φ (x) | ⩽ C N^{- \bar{υ}} \end{matrix}$ where $\begin{matrix} \bar{υ} = \frac{1}{2} min (\frac{1}{4} - ε, β_{1}) . \end{matrix}$ Indeed suppose that (6.17) holds. Let $\begin{matrix} {\tilde{X}}_{N} = \{\begin{matrix} X_{N} & if | m (ξ_{N}) | < N^{\frac{1 + \hat{ε}}{2}}, \\ m (ξ_{N}) & otherwise \end{matrix} \end{matrix}$ where $\hat{ε}$ is a sufficiently small number. Then due to (6.11) there is a constant K such that $| {\tilde{X}}_{N} - m (ξ_{N}) | ⩽ K N^{\frac{(1 + \hat{ε}) (1 - β_{1})}{2}}$ . Therefore $\begin{array}{l} (6.18) & \begin{matrix} P (\frac{m (ξ_{N})}{\sqrt{D N}} ⩽ x - \frac{K}{\sqrt{D}} N^{\frac{(1 - β_{1}) (1 + \hat{ε}) - 1}{2}}) & ⩽ P (\frac{{\tilde{X}}_{N}}{\sqrt{D N}} ⩽ x) \\ ⩽ P (\frac{m (ξ_{N})}{\sqrt{D N}} ⩽ x + \frac{K}{\sqrt{D}} N^{\frac{(1 - β_{1}) (1 + \hat{ε}) - 1}{2}}) . \end{matrix} \end{array}$ Combining (6.18) with (6.17) we obtain $\begin{matrix} (6.19) & sup_{x} | P (\frac{{\tilde{X}}_{N}}{\sqrt{D N}} ⩽ x) - Φ (x) | ⩽ C N^{- \bar{υ}} + \bar{K} N^{\frac{\hat{ε} - β_{1} (1 + \hat{ε})}{2}} ⩽ \bar{C} N^{- (υ - ε)} \end{matrix}$ provided that $\hat{ε}$ is small enough,

On the other hand, by Azuma inequality, there are constants ${\tilde{c}}_{1}$ , ${\tilde{c}}_{2}$ such that $\begin{matrix} (6.20) & P ({\tilde{X}}_{N} \neq X_{N}) = P (m (ξ_{N}) > N^{\frac{1 + \hat{ε}}{2}}) ⩽ c_{1} e^{- c_{2} N^{\hat{ε}}} . \end{matrix}$ Combining (6.19) with (6.20) we obtain (6.16).

It remains to obtain (6.17). Let $Z_{j} = \frac{m (ξ (τ_{j})) - m (ξ (τ_{j - 1}))}{L_{N}}$ and $\begin{array}{l} Q_{j} = \sum_{n = 1}^{τ_{j}} q (ξ (n)), j^{} = min (j : Q_{τ_{j}} > D N), τ^{} = τ_{j^{}}, Q^{} = Q_{τ^{}}, \\ m^{} = m (ξ_{τ^{}}) . \end{array}$ Note that $Z_{n} = \pm 1 + O (N^{- β_{1}})$ due to (6.11) and $\begin{matrix} (6.21) & P (D N ⩽ Q^{} < D N + L_{N}^{2} {ln}^{2} L_{N}) ⩽ θ^{{ln}^{2} L_{N}} \end{matrix}$ due to (5.10).

Next, we show that if $R_{1}$ is a large constant then for each $j ⩾ \frac{N}{10 a L_{N}^{2}}$ we have $\begin{matrix} (6.22) & P (| Q_{τ_{j}} - a L_{N}^{2} j | > R_{1} j L_{N}^{2 - β_{2}}) ⩽ c_{1} e^{- c_{2} N^{β_{3}}} \end{matrix}$ where $β_{2} = min (β_{1}, \frac{1}{4} - ε)$ , and $c_{1}$ , $c_{2}$ , and $β_{3}$ are positive constants. We will prove that $\begin{matrix} (6.23) & P (Q_{τ_{j}} - a L_{N}^{2} j > R_{1} j L_{N}^{2 - β_{2}}) ⩽ {\bar{c}}_{1} e^{- c_{2} N^{β_{3}}}, \end{matrix}$ the estimate of $P (Q_{τ_{j}} - a L_{N}^{2} j < - R_{1} j L_{N}^{2 - β_{2}})$ being similar.

To prove (6.23) we apply the results of Appendix A, specifically (A.11) with $\begin{matrix} Δ_{n} = \frac{\sum_{k = τ_{n - 1}}^{τ_{n}} q (ξ (k))}{L_{N}^{2}} - \frac{R_{1}}{2} L_{N}^{- β_{2}}, ε = \frac{R_{1}}{2} L_{N}^{- β_{2}} \end{matrix}$ and the number of summands equal to j. Observe that (A.11) is applicable, because (A.1) follows from (6.15) since $β_{2} ⩽ β_{1}$ , (A.2) holds by (5.10) and (A.10) holds because $β_{2} ⩽ \frac{1}{4} - ε$ .

(6.22) implies that $\begin{matrix} (6.24) & P (j^{} > \frac{2}{a} \sqrt{N}) = P (j^{} > \frac{2 N}{a L_{N}^{2}}) ⩽ C_{1} e^{- C_{2} N^{\tilde{δ}}} . \end{matrix}$ Let $z = \sum_{j = 1}^{min (\frac{2}{a} \sqrt{N}, j^{})} Z_{j}$ . By (6.24) $\begin{matrix} (6.25) & P (z \neq \frac{m}{\sqrt{N}}) ⩽ C_{1} e^{- C_{2} N^{\tilde{δ}}} . \end{matrix}$ (6.25) and (6.21) allow us to apply Proposition 6.6 to $z$ obtaining $\begin{matrix} sup_{x} | P (z ⩽ x) - Φ (x) | ⩽ \frac{C ln N}{N^{1 / 8}} \end{matrix}$ (note that $N^{1 / 8}$ appears in the denominator since we apply the proposition with $\frac{2}{a} \sqrt{N}$ instead of N). Using (6.25) once more we get $\begin{matrix} (6.26) & sup_{x} | P (\frac{m^{}}{\sqrt{D N}} ⩽ x) - Φ (x) | ⩽ \frac{C ln N}{N^{1 / 8}} . \end{matrix}$

Next, similarly to (6.22), one can show that there is a constant $C_{2}$ such that for each $j ⩾ \frac{N}{10 b L_{N}^{2}}$ we have $\begin{matrix} (6.27) & P (| τ_{j} - b L_{N}^{2} j | > R_{2} j L_{N}^{2 - β_{2}}) ⩽ c_{3} e^{- c_{4} N^{β_{3}}} . \end{matrix}$

Combining (6.22) with (6.27) we conclude that for sufficiently large $R_{3}$ $\begin{matrix} (6.28) & P (| τ^{} - N | ⩾ \frac{R_{3} N}{L_{N}^{β_{2}}}) ⩽ c_{5} e^{- c_{6} L_{N}^{β_{3}}} . \end{matrix}$ Letting $\begin{matrix} \tilde{m} = \{\begin{matrix} m (ξ_{N}) & if | τ^{} - N | ⩽ \frac{N}{L_{N}^{β_{2}}}, \\ m^{} & otherwise \end{matrix} \end{matrix}$ we get that with probability 1 $\begin{matrix} E ({(\tilde{m} - m^{})}^{2} | m^{}) ⩽ \frac{R_{4} N}{L_{N}^{β_{2}}} \end{matrix}$ or, equivalently, $\begin{matrix} (6.29) & E ({(\frac{\tilde{m} - m^{}}{\sqrt{N}})}^{2} | \frac{m^{*}}{\sqrt{N}}) ⩽ \frac{R_{4}}{L_{N}^{β_{2}}} . \end{matrix}$ Therefore combining Proposition 6.7(a) and (6.26) we obtain $\begin{matrix} sup_{x} | P (\frac{\tilde{m}}{\sqrt{D N}} ⩽ x) - Φ (x) | ⩽ C L_{N}^{- \bar{υ}} \end{matrix}$ (note that $\bar{υ} = \frac{β_{2}}{2} < \frac{1}{8}$ , so the main contribution to the error comes from (6.29) rather than from (6.26)).

Next, (6.28) shows that $\begin{matrix} P (\tilde{m} \neq m (ξ_{N})) ⩽ c_{5} e^{- c_{6} L_{N}^{β_{3}}} . \end{matrix}$ (6.17) follows from the last two displays and Proposition 6.7(b). □

6.4. Examples

Here we show that the examples of Section 3.1 satisfy (6.11), (6.12), and (6.13). It is convenient to denote $Δ_{n} = m_{n} - m_{n - 1}$ .

We begin with quasiperiodic systems from Example 3.1.

Proposition 6.9.
For quasiperiodic environments of Example 3.1 if γ is Diophantine then ( 6.11 ), ( 6.12 ), and ( 6.13 ) hold.
Proof.
It is proven in [19] that for quasiperiodic environments with Diophantine frequency γ $\begin{matrix} Δ_{n} = Δ (ω + n γ), ρ_{n} = ρ (ω + n γ) \end{matrix}$ where $Δ, ρ : T^{d} \to R$ are continuous functions. In Appendix C of the present paper we obtain a stronger result. Lemma 6.10.
Δ , $ρ$ are $C^{\infty}$ .

Lemma 6.10 implies (6.11), (6.12), and (6.13) with $β_{1} = 1$ . For example to check (6.11) we use the fact that for Diophantine γ there is a constant c and a function u such that $\begin{matrix} Δ (ω) 1 = c + u (ω + γ) - u (ω) . \end{matrix}$ It follows that $\begin{matrix} M_{k + L} - M_{k - L} = 2 L c + u (ω + L γ) - u (ω - L γ) . \end{matrix}$ Now (4.6) implies that $c = m$ proving (6.11). Estimates (6.12) and (6.13) are verified similarly. □

Since quasiperiodic environments satisfy (6.11), (6.12), and (6.13) with $β_{1} = 1$ , Theorem 6.8 holds for those environments with $υ = \frac{1}{8}$ .

Next, we consider independent environments from Example 3.2.
Proposition 6.11.
( 6.11 ) ( 6.12 ), and ( 6.13 ) hold for independent environments.
Proof.
Let $F_{a, b}$ be the σ algebra generated by ${{(P, Q, R)}_{n}}_{a ⩽ n ⩽ b}$ . We use the following fact from Appendix C. Lemma 6.12.
$ρ_{n} = ρ (T^{n} ω)$ and $Δ_{n} = Δ (T^{n} ω)$ where $ρ : Ω \to R^{m}$ is Holder continuous with respect to the metric d defined by ( 2.5 ).

By Lemma 6.12, there is $θ < 1$ such that for each l there is $F_{- l, l}$ measurable random vector $ρ^{(l)}$ such that $| ρ (ω) - ρ^{(l)} (ω) | ⩽ θ^{l}$ . Hence $\begin{matrix} | E (ρ_{n} 1 | F_{- \infty, n - l}) - E (ρ 1) | ⩽ C θ^{l} . \end{matrix}$ Now [23] tells us that for almost every ω there exists $N_{0} = N_{0} (ω)$ such that for all $| k | < N$ for all $L > N^{0.01}$ we have $\begin{matrix} (6.30) & | \sum_{n = k - L}^{k + L} ρ_{n} 1 - 2 L a | ⩽ \sqrt{L {ln}^{3} L} . \end{matrix}$ This proves (6.12). Estimates (6.11) and (6.12) can be established similarly. □

The foregoing discussion shows that (6.11) (6.12), and (6.13) hold with $β_{1} = \frac{1}{2} - ε$ (cf. (6.30)). Accordingly, Theorem 6.8 holds with $υ = \frac{1}{8}$ .

Finally we consider small perturbations of the simple random walk on $Z$ from Example 3.3.

Then the invariant measure equation (2.27) reduces to a zero flux condition (see e.g. [21, §5.5]) $\begin{matrix} p_{n} ρ_{n} = q_{n + 1} ρ_{n + 1} \end{matrix}$ which gives $\begin{matrix} \frac{ρ_{n + 1}}{ρ_{n}} = \frac{1 - 2 a_{n}}{1 + 2 a_{n + 1}} . \end{matrix}$ Considering first the case $n > 0$ we obtain $\begin{matrix} ρ_{n} = ρ_{0} [\prod_{j = 0}^{n - 1} (\frac{1 - 2 a_{j}}{1 + 2 a_{j + 1}})] . \end{matrix}$ Therefore the limit $ρ_{+} = {lim}_{n \to \infty} ρ_{n}$ exists and $\begin{matrix} (6.31) & ρ_{n} = ρ_{+} + O (\frac{1}{n^{κ - 1}}) . \end{matrix}$ Likewise the limit $ρ_{-} = {lim}_{n \to \infty} ρ_{- n}$ exists and $\begin{matrix} (6.32) & ρ_{- n} = ρ_{-} + O (\frac{1}{n^{κ - 1}}) . \end{matrix}$

Next, recall a formula for $m_{n}$ [21]. Let $Δ_{n} = m_{n + 1} - m_{n}$ . Then $\begin{matrix} Δ_{n + 1} = Δ_{n} \frac{1 + 2 a_{n}}{1 - 2 a_{n}} . \end{matrix}$ Thus the limit $Δ_{+} = {lim}_{n \to \infty} Δ_{n}$ exists and $\begin{matrix} (6.33) & Δ_{n} = Δ_{0} [\prod_{j = 0}^{n - 1} (\frac{1 + 2 a_{j}}{1 - 2 a_{j}})] = Δ_{+} + O (\frac{1}{n^{κ - 1}}) . \end{matrix}$ Likewise the limit $Δ_{-} = {lim}_{n \to \infty} Δ_{- n}$ exists and $\begin{matrix} (6.34) & Δ_{- n} = Δ_{0} [\prod_{j = 0}^{n - 1} (\frac{1 - 2 a_{- j}}{1 + 2 a_{- j}})] = Δ_{-} + O (\frac{1}{n^{κ - 1}}) . \end{matrix}$ Accordingly (3.3) is equivalent to the condition $Δ_{+} = Δ_{-}$ . Hence if (3.3) holds we can normalize ${Δ_{n}}$ in such a way that ${lim}_{n \to \pm \infty} Δ_{n} = 1$ . In this case (4.6) holds and (4.7) gives ${lim}_{n \to \pm \infty} ρ_{n} = 1$ .

Now (6.33), (6.34), (6.31), and (6.32) show that $\begin{matrix} (6.35) & Δ_{n} = 1 + O (\frac{1}{| n |^{κ - 1}}) and ρ_{n} = 1 + O (\frac{1}{| n |^{κ - 1}}) . \end{matrix}$ It follows that (6.11), (6.12) and (6.13) hold with $β_{1} = min (κ - 1, 1)$ . Hence Theorem 6.8 holds in Example 3.3 with $υ = min (\frac{κ - 1}{2}, \frac{1}{8})$ .
7. Different growth rates

7.1. Notation

In this section we consider the case where $m$ , ρ, and $q$ have different growth rates at $- \infty$ and $+ \infty$ . Thus we assume that instead of (4.6), (5.1) and (6.1) we have $\begin{array}{l} (7.1) & lim_{n \to - \infty} \frac{M_{n}}{n} = m μ_{-}, lim_{n \to + \infty} \frac{M_{n}}{n} = m μ_{+}; \\ (7.2) & lim_{N \to \infty} \frac{1}{N} \sum_{n = - N + 1}^{0} ρ_{n} 1 = a_{-}, lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N - 1} ρ_{n} 1 = a_{+}; \\ (7.3) & lim_{N \to \infty} \frac{1}{N} \sum_{n = - N + 1}^{0} ρ_{n} q_{n} = b_{-}, lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N - 1} ρ_{n} q_{n} = b_{+} . \end{array}$ We denote $D_{\pm} = \frac{b_{\pm}}{a_{\pm}}$ .

Given $μ_{1}$ , $μ_{2}$ let $\begin{matrix} S_{μ_{1}, μ_{2}} (w) = \{\begin{matrix} \frac{w}{μ_{1}} & if w ⩾ 0, \\ \frac{w}{μ_{2}} & if w ⩽ 0 . \end{matrix} \end{matrix}$

Given θ, γ and D we consider the following Markov process. Let $W_{D} (u)$ be the Brownian motion with zero mean and variance $D u$ . Denote by $u^{+} (u)$ the total time on $[0, u]$ when $W$ is positive and $u^{-} (u)$ the total time on $[0, u]$ when $W$ is negative. Given t let $u_{γ} (t)$ be the solution of $\begin{matrix} u^{+} (u_{γ}) + \frac{u^{-} (u_{γ})}{γ} = t . \end{matrix}$ Set $\begin{matrix} W_{γ, θ, D} (t) = S_{θ, 1} (W_{D} (u_{γ} (t))) . \end{matrix}$ Note that this process is defined using the function $S$ with parameters θ and 1. Allowing more general parameters does not increase the generality since $μ_{2} = 1$ can always be achieved by rescaling because $S_{μ_{1}, μ_{2}} (W_{D} (u_{γ} (\cdot)))$ has the same law as $W_{γ, \frac{μ_{2}}{μ_{1}}, \frac{D}{μ_{1}^{2}}}$ .

In the case where $\begin{matrix} (7.4) & γ = {(\frac{1 - p}{p})}^{2}, θ = \frac{1 - p}{p} \end{matrix}$ the process $W_{γ, θ, D}$ is referred to as the skew Brownian Motion with parameter $p$ . We will thus abbreviate $W_{{(\frac{1 - p}{p})}^{2}, \frac{1 - p}{p}, D}$ as $B_{p, D}$ . Note that $p$ in (7.4) is given by $\begin{matrix} (7.5) & p = \frac{1}{θ + 1} . \end{matrix}$

We refer the reader to [35] for description of various equivalent definitions of the skew Brownian Motion as well as its numerous applications. Of these definitions, the most relevant for us is the following one [26]: $B_{p, 1} (t)$ is the scaling limit of $\frac{X (t N)}{\sqrt{N}}$ where $X$ is the random walk on $Z$ which moves to the left and to the right with probability $1 / 2$ everywhere except the origin; at the origin $X$ moves to the right with probability $p$ and to the left with probability $1 - p$ .

7.2. Functional CLT

Theorem 7.1.
$W_{N} (t) = \frac{X_{N t}}{\sqrt{N}}$ converges in law as $N \to \infty$ to $W_{γ, θ, D}$ where $\begin{matrix} γ = \frac{D_{-}}{D_{+}}, θ = \frac{μ_{-}}{μ_{+}}, D = \frac{D^{+}}{μ_{+}^{2}} . \end{matrix}$
Proof.
The proof of Theorem 7.1 is very similar to the proof of Theorem 6.1 so we just sketch the argument. As in Theorem 6.1 it suffices to show that ${\hat{W}}_{N}$ defined by (6.3) converges to $W_{D^{+}} (u_{γ} (t))$ . We may assume without loss of generality that $D^{-} < D^{+}$ and so $γ < 1$ . If this is not the case we could consider the reflected walk $(- X (N), Y (N))$ . Let $\tilde{ξ} (u) = (\tilde{X} (u), \tilde{Y} (u))$ be the following lazy walk. If $\tilde{X} ⩾ 0$ then its transition probability coincides with $P$ . If $\tilde{X} < 0$ then, with probability $1 - γ$ , $\tilde{ξ}$ stays at its present location and with probability γ it moves according to $P$ . There is a natural coupling between ξ and $\tilde{ξ}$ such that $\tilde{ξ} (u) = ξ (t (u))$ . Let $u (t)$ be the left inverse to $t (u)$ . It is clear from the law of large numbers for sums of geometric random variables that with probability 1 $\begin{matrix} lim_{t \to \infty} \frac{t}{u^{+} (u (t)) + u^{-} (u (t)) / γ} = 1 \end{matrix}$ where $u^{+} (u)$ and $u^{-} (u)$ are occupation times of positive and negative semi-axis. It therefore suffices to show that $\begin{matrix} (7.6) & {\tilde{W}}_{N} \Rightarrow W_{D^{+}} \end{matrix}$ where ${\tilde{W}}_{N} (u) = \frac{m (\tilde{ξ} (N u))}{\sqrt{N}}$ and $W_{D^{+}}$ is the Brownian Motion with zero drift and variance $D^{+} u$ . Note that $m (\tilde{ξ} (u))$ is a martingale with quadratic variation $\sum_{n = 1}^{u} \tilde{q} (\tilde{ξ} (n))$ where $\begin{matrix} \tilde{q} (x, y) = \{\begin{matrix} q (x, y) & if x ⩾ 0, \\ γ q (x, y) & if x < 0 . \end{matrix} \end{matrix}$ According to [12] it suffices to show that $\begin{matrix} (7.7) & lim_{N \to \infty} \frac{\sum_{j = 1}^{N} \tilde{q} (\tilde{ξ} (j))}{N} = D^{+} . \end{matrix}$ The proof of (7.7) is the same as the proof of Lemma 5.1. The key step is to show that if $L_{N}$ is the same as in the lemma, $| x | ⩽ K \sqrt{N}$ and $\tilde{τ}$ is the exit time from $[x - L_{N}, x + L_{N}]$ by $\tilde{ξ}$ then we have that for each $y \in {1 \dots m}$ $\begin{matrix} (7.8) & {\tilde{D}}_{N} (x, y) \approx D^{+} where {\tilde{D}}_{N} (x, y) = \frac{E (\sum_{u = 0}^{\tilde{τ}} \tilde{q} (\tilde{ξ} (u)) | \tilde{ξ} (0) = (x, y))}{E (\tilde{τ} | \tilde{ξ} (0) = (x, y))} . \end{matrix}$ To fix the ideas, suppose that $[x - L_{N}, x + L_{N}] \subset (- \infty, 0)$ then $\begin{matrix} (7.9) & {\tilde{D}}_{N} (x, y) = γ \frac{E (\sum_{u = 0}^{\tilde{τ}} q (\tilde{ξ} (u)) | \tilde{ξ} (0) = (x, y))}{E (\tilde{τ} | \tilde{ξ} (0) = (x, y))} . \end{matrix}$ Note that ${\tilde{ξ}}_{N}$ satisfies (2.26), (2.27) with $\begin{matrix} \tilde{m} (x, y) = m (x, y), \tilde{ρ} (x, y) = \{\begin{matrix} ρ (x, y) & if x ⩾ 0, \\ \frac{ρ (x, y)}{γ} & if x < 0 . \end{matrix} \end{matrix}$ The computations in Section 5, in particular, (5.6) and (5.14), applied to $\tilde{ξ}$ , show that the second factor in the RHS of (7.9) is asymptotic to $D_{-}$ so that $\begin{matrix} {\tilde{D}}_{N} (x, y) \approx γ D^{-} = D^{+} \end{matrix}$ as claimed. Once (7.8) is established the proof of (7.7) proceeds as in Section 5. □
7.3. Small perturbations of the environment

Consider an environment on $S$ satisfying conditions (4.6), (5.1), and (6.1). Let $P$ be defined by (2.2). Consider a perturbation $\tilde{P}$ of $P$ such that $\begin{matrix} | \bar{P} (z, z^{'}) - P (z, z^{'}) | ⩽ \frac{C}{| n |^{κ} + 1} where z = (n, j) and κ > 1 . \end{matrix}$

Let $β_{n}$ , ${\tilde{β}}_{n}$ be sequences such that $\begin{matrix} (7.10) & λ_{n} = \frac{β_{n + 1}}{β_{n}}, {\tilde{λ}}_{n} = \frac{{\tilde{β}}_{n + 1}}{{\tilde{β}}_{n}} . \end{matrix}$ The following result is proven in Appendix C.

Lemma 7.2.

The following estimates hold $\begin{array}{l} (7.11) & ‖ ζ_{n} - {\bar{ζ}}_{n} ‖ ⩽ \frac{C}{| n |^{κ} + 1}, ‖ l_{n} - {\bar{l}}_{n} ‖ ⩽ \frac{C}{| n |^{κ} + 1}, ‖ v_{n} - {\bar{v}}_{n} ‖ ⩽ \frac{C}{| n |^{κ} + 1}, \\ (7.12) & ‖ A_{n} - {\bar{A}}_{n} ‖ ⩽ \frac{C}{| n |^{κ} + 1}, ‖ λ_{n} - {\bar{λ}}_{n} ‖ ⩽ \frac{C}{| n |^{κ} + 1}, ‖ {\tilde{λ}}_{n} - {\overline{\tilde{λ}}}_{n} ‖ ⩽ \frac{C}{| n |^{κ} + 1} . \end{array}$

The following limits exist $\begin{matrix} (7.13) & β_{\pm} = lim_{n \to \pm \infty} \frac{{\bar{β}}_{n}}{β_{n}} = lim_{n \to \pm \infty} \frac{{\overline{\tilde{β}}}_{n}}{{\tilde{β}}_{n}} . \end{matrix}$

The perturbed walk satisfies ( 7.1 ), ( 7.2 ) and ( 7.3 ) with $\begin{matrix} μ_{\pm} = β_{\pm}, a_{\pm} = a / β_{\pm}, b_{\pm} = b β_{\pm} \end{matrix}$ where a and b are the limits of ( 5.1 ) and ( 6.1 ) respectively for the unperturbed walk.

For random walks on $Z$ the lemma follows easily from the explicit expressions for the objects involved. Namely $\begin{matrix} (7.14) & A_{n} = \frac{q_{n}}{p_{n}} = λ_{n} = \frac{β_{n + 1}}{β_{n}}, and Δ_{n} = β_{n}, ρ_{n} = \frac{1}{β_{n} q_{n}}, q_{n} = β_{n + 1} β_{n} \end{matrix}$ (see [19, Section 5]). The case of the strip is more complicated and will be considered in Appendix C.

Combining Theorem 7.1 with Lemma 7.2 we obtain the following result.
Corollary 7.3.
Let $\bar{ξ} (t) = (\bar{X} (t), \bar{Y} (t))$ denote the walk in the perturbed environment $\overline{P}$ . $\begin{matrix} \frac{\bar{X} (t N)}{\sqrt{N}} \Rightarrow B_{p, D} \end{matrix}$ where D is the limiting variance of the walk in the unperturbed environment and $\begin{matrix} (7.15) & p = \frac{β_{+}}{β_{+} + β_{-}} . \end{matrix}$
Remark 7.4.
Note that (7.10) does not define $β_{n}$ and ${\tilde{β}}_{n}$ uniquely. Namely, if we replace $β_{n}$ by $c β_{n}$ and ${\tilde{β}}_{n}$ by $\tilde{c} β_{n}$ for any constants c, $\tilde{c}$ then (7.10) remains valid. In this case $β_{\pm}$ get replaced by $\frac{\tilde{c}}{c} β_{\pm}$ but expression of $p$ does not depend on the arbitrariness involved in the choice of c and $\tilde{c}$ .

For random walks on $Z$ using the explicit expression for $λ_{n}$ in terms of $p_{n}$ and $q_{n}$ (see (7.14)) we obtain $\begin{matrix} (7.16) & p = \frac{υ}{υ + 1} where υ = \prod_{n = - \infty}^{\infty} (\frac{{\tilde{q}}_{n} p_{n}}{{\tilde{p}}_{n} q_{n}}) . \end{matrix}$
8. Semilocal limit theorem

We say that $X_{N}$ satisfies the semilocal limit theorem at the scale $L_{N}$ with $1 ≪ L_{N} ≪ \sqrt{N}$ if there exists a constant $β > 0$ such that for each interval I of length $L_{N}$ , for each $(x, y)$ with $| x | ⩽ N$ $\begin{matrix} (8.1) & P (X_{N} - x \in I | ξ (0) = (x, y)) = P (\sqrt{D N} N \in I) + O (\frac{L_{N}^{1 - β}}{\sqrt{N}}), \end{matrix}$ where $N$ is the standard normal random variable and D is a positive number (in our case D comes from Theorem 6.1).

Clearly if for each $(x, y)$ with $| x | ⩽ N$ we have $\begin{matrix} sup_{z} | P (\frac{X_{N} - x}{\sqrt{D N}} ⩽ z | ξ (0) = (x, y)) - Φ (z) | ⩽ N^{- υ} \end{matrix}$ then X satisfies the semilocal limit theorem at the scale $N^{γ}$ for each $γ > \frac{1}{2} - υ$ . The next lemma allows us to decrease the scale in the semilocal limit theorem.

Lemma 8.1.
Let $ε, ε_{1} < ε_{2}$ be small positive constants. If N is sufficiently large and for each $\tilde{N}$ such that $N^{ε} ⩽ \tilde{N} ⩽ N$ , for each $(x, y)$ such that $| x | ⩽ N (1 + ε_{2})$ , for each interval I of length $L = {\tilde{N}}^{γ}$ where $\begin{matrix} γ < \frac{1}{2} and γ (\frac{1}{2} + γ) > ε \end{matrix}$ we have $\begin{matrix} (8.2) & P (X_{\tilde{N}} - x \in I | ξ (0) = (x, y)) = P (\sqrt{D \tilde{N}} N \in I) + O (\frac{L^{1 - β}}{\sqrt{\tilde{N}}}) \end{matrix}$ then ( 8.1 ) holds for all $(x, y)$ with $| x | < (1 + ε_{1}) N$ and $L_{N} = N^{(\frac{1}{2} + γ) γ}$ .

Applying this lemma several times we obtain the following Corollary 8.2.
Suppose that there exits $γ < \frac{1}{2}$ such that for each ε there are constants $ε_{1}$ , $ε_{2}$ , $N_{0}$ such that the conditions of Lemma 8.1 are satisfied for $N ⩾ N_{0}$ . Then, for arbitrarily small $\tilde{γ} > 0$ , X satisfies the semilocal limit theorem at scale $N^{\tilde{γ}}$ .
Proof of Lemma 8.1.
Throughout this proof we fix $(x, y)$ and let $\hat{P}$ denote the distribution of ξ under the condition that $ξ (0) = (x, y)$ .

Let $s = \frac{1}{2} + γ$ . Note that $s < 1$ . Consider an interval I of length $N^{γ s}$ . Let $N_{1} = N - N^{s}$ , $N_{2} = N^{s}$ . Divide $Z$ into intervals $I_{p}$ of size $N^{γ}$ . Let $\bar{x}$ be the center of I and $x_{p}$ be the centers of $I_{p}$ . Call p feasible if $\begin{matrix} | x_{p} - x | ⩽ N^{1 / 2 + ε} and | \bar{x} - x_{p} | ⩽ N_{2}^{1 / 2 + ε} . \end{matrix}$ By the Azuma inequality, if p is not feasible, then $\begin{matrix} \hat{P} (X_{N_{1}} \in I_{p}, X_{N} \in I) ⩽ exp (- N_{2}^{2 ε}) . \end{matrix}$ Accordingly $\begin{matrix} (8.3) & \hat{P} (X_{N} \in I) = \sum_{p -feasible} \hat{P} (X_{N_{1}} \in I_{p}) \hat{P} (X_{N} \in I | X_{N_{1}} \in I_{p}) + O (e^{- N_{2}^{2 ε}}) . \end{matrix}$ By (8.2) each individual term in this sum is $\begin{matrix} \frac{N^{γ}}{\sqrt{2 π D N_{1}}} e^{- {(x_{p} - x)}^{2} / (2 D N_{1})} \times \frac{N^{γ s}}{\sqrt{2 π D N_{2}}} e^{- {(\bar{x} - x_{p})}^{2} / (2 D N_{2})} + O (N^{(γ - \frac{1}{2}) (1 + s) - β s}) . \end{matrix}$ Since p is feasible we can replace $\begin{matrix} e^{- {(x_{p} - x)}^{2} / (2 D N_{1})} by e^{- {(\bar{x} - x)}^{2} / (2 D N_{1})} \end{matrix}$ with an error of order $O (N^{- ε})$ . Accordingly the main contribution to (8.3) comes from $\begin{array}{l} \frac{N^{γ s}}{\sqrt{2 π D N_{1}}} e^{- {(x - \bar{x})}^{2} / (2 D N_{1})} \sum_{p} \frac{N^{γ}}{\sqrt{2 π D N_{2}}} e^{- {(\bar{x} - x_{p})}^{2} / (2 D N_{2})} \\ = \frac{N^{γ s}}{\sqrt{2 π D N_{1}}} e^{- {(\bar{x} - x)}^{2} / (2 D N_{1})} [\int_{- \infty}^{\infty} \frac{1}{\sqrt{2 π D}} e^{- {(\bar{x} - z)}^{2} / (2 D)} d z + O (\frac{N^{γ}}{\sqrt{N_{2}}})] \\ = \frac{N^{γ s}}{\sqrt{2 π D N_{1}}} e^{- {(\bar{x} - x)}^{2} / (2 D N_{1})} [1 + O (N^{\frac{γ - 1 / 2}{2}})] \end{array}$ where the first equality is obtained by replacing the Riemann sum with step $ℏ = \frac{N^{γ}}{\sqrt{N_{2}}}$ with the Riemann integral with mistake $O (ℏ)$ . The result follows. □

9. Environment viewed by the particle: Mixing

9.1. General result

Here we provide sufficient conditions for mixing of the environment viewed by the particle process. Namely we assume that there is a sequence $δ_{N}$ converging to 0 as $N \to \infty$ , such that for each ε, K there exists $N_{0}$ such that for $N ⩾ N_{0}$ for each k with $| k | ⩽ K \sqrt{N}$ $\begin{matrix} (9.1) & | \frac{1}{2 δ_{N} N^{1 / 4}} \sum_{j = k - δ_{N} N^{1 / 4}}^{k + δ_{N} N^{1 / 4}} ρ_{j} 1 - a | ⩽ ε . \end{matrix}$ We consider functions $h : S \to R$ satisfying (3.7).

Theorem 9.1.
If ( 3.7 ), ( 3.4 ) and ( 9.1 ) hold then $E (h (ξ (N))) \to \frac{h}{a}$ as $N \to \infty$ .
Proof.
If (3.7), and (9.1) hold then the argument of Section 5 shows that for each ε, δ, K there exists $N_{1}$ such that for $N ⩾ N_{1}$ and for each $(k, y) \in S$ such that $| k | ⩽ K \sqrt{N}$ we have $\begin{matrix} (9.2) & P (| \frac{1}{δ \sqrt{N}} \sum_{j = 0}^{δ \sqrt{N} - 1} h (ξ (j)) - \frac{h}{a} | > ε | ξ (0) = (k, y)) < \frac{ε}{‖ h ‖_{\infty}} . \end{matrix}$ That is, the conclusion of Lemma 5.1 holds uniformly for initial conditions $(k, y)$ satisfying $| k | < K \sqrt{N}$ .

Given a trajectory ξ we denote by $\tilde{ξ}$ the accelerated trajectory which skips all steps where ξ stays at the same place. That is, $\tilde{ξ} (n) = ξ (t (n))$ where $t (0) = 0$ and for $n > 0$ , $t (n) = min (t > t (n - 1) : ξ (t) \neq ξ (t (n - 1)))$ . We denote by $s (n) = t (n + 1) - t (n)$ the time the walker spends at $\tilde{ξ} (n)$ .

A path is a finite set of points $W = {z_{0}, z_{1} \dots z_{l}}$ such that $z_{j} \neq z_{j + 1}$ for $j = 0, \dots, l - 1$ . The number $l = l (W)$ is called the length of the path. A path is called admissible if there is an accelerated trajectory $\tilde{ξ}$ such that $\tilde{ξ} (n) = z_{n}$ for $0 ⩽ n ⩽ l (W)$ . Given an admissible path W and a trajectory ξ following this path let $τ (W, ξ) = t (l (W))$ be the number of steps it takes ξ to traverse this path. Let $T (W)$ be the expectation of $τ (W, ξ)$ conditioned on the event that W is the beginning part of $\tilde{ξ}$ . Observe that $\begin{matrix} (9.3) & τ (W, ξ) = \sum_{n = 0}^{l - 1} s (n) \end{matrix}$ where, for a fixed W, $s (n)$ are independent random variables having geometric distributions with parameter $1 - P (\tilde{ξ} (n), \tilde{ξ} (n))$ .

Let $S (N)$ be the set of (admissible) paths such that $T (W) ⩾ \frac{N}{2}$ but $T (W^{-}) < \frac{N}{2}$ where $W^{-}$ is the path obtained by removing the last edge from W. Given $W \in S (N)$ , δ, j let $\begin{matrix} A_{W, δ, j} = {ξ : W = \tilde{ξ} ([0, l (W)]) and τ (W, ξ) \in [\frac{N}{2} + δ j \sqrt{N}, \frac{N}{2} + δ (j + 1) \sqrt{N})} . \end{matrix}$ By the Central Limit Theorem for $τ (W, ξ)$ , (see (9.3)), given $ε > 0$ we can find R such that $\begin{matrix} P (⋃_{W \in S (N)} {ξ : | τ (W, ξ) - \frac{N}{2} | > R \sqrt{N}}) ⩽ ε . \end{matrix}$ Accordingly $\begin{matrix} E (h (ξ (N))) = [\sum_{W \in S (N)} \sum_{| j | ⩽ R} P (A_{W, δ, j}) E (h (ξ (N)) | A_{W, δ, j})] + \tilde{ε} \end{matrix}$ where $\tilde{ε} ⩽ (sup | h |) ε$ .

We claim that $\begin{matrix} (9.4) & | \sum_{W \in S (N)} \sum_{| j | ⩽ R / δ} P (A_{W, δ, j}) E (h (ξ (N)) | A_{W, δ, j}) - \frac{h}{a} | ⩽ 3 ε \end{matrix}$ provided that δ is small enough. Indeed $\begin{array}{l} (9.5) & \begin{matrix} E (h (ξ (N)) | A_{W, δ, j}) & = \sum_{l = 1}^{δ \sqrt{N}} E (h (ξ (\frac{N}{2} - δ (j + 1) \sqrt{N} + l)) | ξ (0) = e (W)) \\ \times P (τ (W, ξ) = \frac{N}{2} + δ (j + 1) \sqrt{N} - l | A_{W, δ, j}) \end{matrix} \end{array}$ where $e (W) = (x (W), y (W))$ is the endpoint of W. By the Local Limit Theorem for the sum (9.3) [15,43] $\begin{matrix} (9.6) & | P (τ (W, ξ) = \frac{N}{2} + δ (j + 1) \sqrt{N} - l | A_{W, δ, j}) - \frac{1}{δ \sqrt{N}} | ⩽ \frac{ε}{‖ h ‖_{\infty}} \end{matrix}$ uniformly in $l ⩽ δ \sqrt{N}$ provided that δ is small enough. This allows us to replace $E (h (ξ (N)) | A_{W, δ, j})$ by $\begin{matrix} \frac{1}{δ \sqrt{N}} \sum_{l = 1}^{δ \sqrt{N}} E (h (ξ (b_{N, j, l})) | ξ (0) = e (W)), \end{matrix}$ where $\begin{matrix} (9.7) & b_{N, j, l} = \frac{N}{2} - δ (j + 1) \sqrt{N} + l . \end{matrix}$

To control this sum we consider two cases.

(I) The terms where $| x (W) |$ is large can be controlled as follows. By Theorem 6.1 $\begin{array}{l} \frac{1}{δ \sqrt{N}} \sum_{W \in S (N)} \sum_{| j | ⩽ R / δ} \sum_{| x (W) | > K \sqrt{N}} \sum_{l = 1}^{δ j \sqrt{N}} P (A_{W, δ, j}) P (ξ (b_{N, j, l}) = e (W) | ξ (0) = e (W)) \\ ⩽ P (| ξ (N) | > \frac{K \sqrt{N}}{2}) ⩽ \frac{ε}{‖ h ‖_{\infty}} \end{array}$ provided that K is sufficiently large and $N ⩾ N_{2} (K)$ .

(II) On the other hand if $| x (W) | ⩽ K \sqrt{N}$ then in view of (9.2) $\begin{matrix} | \frac{1}{δ \sqrt{N}} \sum_{l = 1}^{δ \sqrt{N}} E (h (ξ (b_{N, j, l})) | ξ (0) = e (W)) - \frac{h}{a} | ⩽ ε \end{matrix}$ provided that N is large enough.

Combining the estimates for the cases (I) and (II) above with (9.6) we obtain (9.4). Since ε is arbitrary Theorem 9.1 follows. □

9.2. Examples

Examples presented in Section 3.1 also satisfy (3.7) and (9.1).

In fact, in Example 3.1 we can replace quasiperiodic environments by more general environments generated by uniquely ergodic transformation (we refer the reader to [14, §1.8] (for background on uniquely ergodic transformations). That is, let T be a uniquely ergodic transformation of a compact metric space Ω, ${(P, Q, R)}_{n} (ω) = (P, Q, R) (T^{n} ω)$ and $h_{n} (ω) = H (T^{n} ω)$ .

Proposition 9.2.
If $(P, Q, R)$ and $H$ are continuous then ( 3.7 ) and ( 9.1 ) hold.
Proof.
By Section 6 and Appendix A of [19], $ρ_{n} = ρ (T^{n} ω)$ , where $ρ : X \to R^{m}$ is continuous. Therefore (3.7) and (9.1) follow from the fact that the convergence in ergodic theorem for uniquely ergodic systems is uniform with respect to ω [14, Theorem 1.8.2]. □

In the case of independent environments we suppose that $h_{n} = H (P_{n}, Q_{n}, R_{n})$ where $H$ is a bounded continuous function.
Proposition 9.3.
( 3.7 ) and ( 9.1 ) hold for independent environments.
Proof.
The proof of (9.1) is very similar to the proof of Proposition 6.11 so it can be left to the reader. The proof of (3.7) in case $H$ is a local function (that is there exists R such that $H (ω)$ depends only on ${(P_{n}, Q_{n}, R_{n})}_{n}$ with $| n | ⩽ R$ ) is also similar to Proposition 6.11. To prove (3.7) for general continuos function, it suffices to approximate it by a local function with error less than $ε / 2$ . □

Propositions 9.2 and 9.3 complete the proof of Theorem 3.10 for Examples 3.1 and 3.2. To prove Theorem 3.10 for Example 3.3 we need to take into account that the walk is not allowed to remain at the same site at two consecutive moments of time. Because of that, we consider ξ at odd and at even times separately and note that (3.8) implies (3.7) for both odd and even sublattices.
10. Local Limit Theorem

Theorem 10.1.

If ( 6.11 ), ( 6.12 ), and ( 6.13 ) hold then for each sequence $(k_{N}, y_{N})$ such that $k_{N} / \sqrt{N}$ is bounded we have $\begin{matrix} (10.1) & lim_{N \to \infty} \frac{P (ξ (N) = (k_{N}, y_{N}))}{P (\sqrt{\frac{b N}{a}} N \in [k_{N} - \frac{1}{2}, k_{N} + \frac{1}{2}]) ρ (k_{N}, y_{N})} = \frac{1}{a} \end{matrix}$ where a and b are the constants from ( 6.12 ) and ( 6.13 ) respectively.

Proof.

We use the same notation as in Section 9. In particular we choose a small constant $ε_{2}$ and let δ be as in the proof of Theorem 9.1. We have $\begin{matrix} (10.2) & P (ξ (N) = (k_{N}, y_{N})) = \sum_{W} \sum_{j} P (A_{W, δ, j}) P (ξ (N) = (k_{N}, y_{N}) | A_{W, δ, j}), \end{matrix}$ where the sum is over all admissible paths W.

Given $\bar{R}$ denote by $S_{\bar{R}} (N)$ the set of paths in $S (N)$ whose endpoint $e (W) = (x (W), y (W))$ satisfies $| x (W) | ⩽ \bar{R} \sqrt{N}$ . Pick $\bar{R} ≫ 1$ and divide the sum (10.2) into three parts.

(I) If $W \in S_{\bar{R}} (N)$ and $| j | < N^{\bar{ε}}$ then (9.6) allows us to replace $\begin{matrix} P (ξ (N) = (k_{N}, y_{N}) | A_{W, δ, j}) \end{matrix}$ by $\begin{matrix} \frac{1}{δ \sqrt{N}} \sum_{l = 1}^{δ \sqrt{N}} P (ξ (b_{N, j, l}) = (k_{N}, y_{N}) | ξ (0) = e (W)) \end{matrix}$ where $b_{N, j, 0} = \frac{N}{2} - δ (j + 1) \sqrt{N}$ , $b_{N, j, l} = b_{N, j, 0} + l$ (see (9.7)). Divide $Z$ into segments $I_{p}$ of length $L_{N} = N^{1 / 5}$ . Let ${\tilde{k}}_{p}$ be the center of $I_{p}$ . We split the above sum as $\begin{matrix} \sum_{p} \sum_{\begin{array}{c} \tilde{k} \in I_{p} \\ \tilde{y} \in {1, \dots, m} \end{array}} P (ξ (b_{N, j, 0}) = (\tilde{k}, \tilde{y}) | ξ (0) = e (W)) \frac{\sum_{l = 1}^{δ \sqrt{N}} P (ξ (l) = (k_{N}, y_{N}) | ξ (0) = (\tilde{k}, \tilde{y}))}{δ \sqrt{N}} . \end{matrix}$

Denote $\bar{N} = δ^{1 / 2} N^{1 / 4}$ . By Corollary 6.5 if $| k_{N} - {\tilde{k}}_{p} | ⩽ \bar{R} \sqrt{\bar{N}}$ and $\tilde{k} \in I_{p}$ then $\begin{array}{l} (10.3) & \begin{matrix} \frac{\sum_{l = 1}^{δ \sqrt{N}} P (ξ (l) = (k_{N}, y_{N}) | ξ (0) = (\tilde{k}, \tilde{y}))}{δ \sqrt{N}} & \sim \frac{E (l_{(k_{N} - \tilde{k}) / \bar{N}), 1 / a})}{\bar{N}} ρ_{k_{N}, y_{N}} \\ \sim \frac{E (l_{(k_{N} - {\tilde{k}}_{p}) / \bar{N}), 1 / a})}{\bar{N}} ρ_{k_{N}, y_{N}} \end{matrix} \end{array}$ where the last step uses that $| k_{N} - {\tilde{k}}_{p} | ≪ \sqrt{N}$ .

On the other hand Corollary 8.2 and Theorem 6.8 show that $\begin{array}{l} (10.4) & \begin{matrix} \sum_{\begin{array}{c} \tilde{k} \in I_{p} \\ \tilde{y} \in {1, \dots, m} \end{array}} P (ξ (b_{N, j, 0}) = (\tilde{k}, \tilde{y}) | ξ (0) = e (W)) \\ = \frac{L_{N} (1 + o_{N \to \infty} (1))}{\sqrt{π D N}} exp (- \frac{{(x (W) - {\tilde{k}}_{p})}^{2}}{D N}) \\ = \frac{L_{N} (1 + o_{N \to \infty} (1))}{\sqrt{π D N}} exp (- \frac{{(x (W) - k_{N})}^{2}}{D N}) \end{matrix} \end{array}$ where $D N = 2 D (\frac{N}{2})$ appears in the above expression since $b_{N, j, 0} = \frac{N}{2} + O (N^{(1 / 2) + ε})$ .

Next, if $\begin{matrix} (10.5) & | k_{N} - {\tilde{k}}_{p} | ⩾ \bar{R} \sqrt{\bar{N}} \end{matrix}$ then $\begin{array}{l} \frac{\sum_{l = 1}^{δ \sqrt{N}} P (ξ (l) = (k_{N}, y_{N}) | ξ (0) = (\tilde{k}, \tilde{y}))}{δ \sqrt{N}} \\ ⩽ P (ξ visits (k_{N}, y_{N}) before time δ \sqrt{N} | ξ (0) = (\tilde{k}, \tilde{y})) \\ (10.6) & \times E (Card (l ⩽ \sqrt{N} : ξ (l) = (k_{N}, y_{N})) | ξ (0) = (k_{N}, y_{N})) . \end{array}$ The first factor is $O (e^{- c {(k_{N} - \tilde{k})}^{2} / [{\bar{N}}^{2}]})$ by the Azuma inequality and the second factor is $O (\bar{N})$ by Lemma 6.3, so in case (10.5) we have $\begin{matrix} (10.7) & \frac{\sum_{l = 1}^{δ \sqrt{N}} P (ξ (l) = (k_{N}, y_{N}) | ξ (0) = (\tilde{k}, \tilde{y}))}{δ \sqrt{N}} ⩽ \frac{C}{\bar{N}} exp (- \frac{c {(k_{N} - {\tilde{k}}_{p})}^{2}}{{\bar{N}}^{2}}) . \end{matrix}$ Hence (see (10.4)) $\begin{array}{l} \sum_{\begin{array}{c} \tilde{k} \in I_{p} \\ \tilde{y} \in {1, \dots, m} \end{array}} P (ξ (b_{N, j, 0}) = (\tilde{k}, \tilde{y}) | ξ (0) = e (W)) \frac{\sum_{l = 1}^{δ \sqrt{N}} P (ξ (l) = (k_{N}, y_{N}) | ξ (0) = (\tilde{k}, \tilde{y}))}{δ \sqrt{N}} \\ (10.8) & ⩽ \frac{C L_{N}}{\bar{N} \sqrt{N}} exp (- \frac{c {(k_{N} - {\tilde{k}}_{p})}^{2}}{{\bar{N}}^{2}}) . \end{array}$

Next, we perform the summation over p. Equations (10.3), (10.4), (10.8) show that in case (I) $\begin{array}{l} \frac{1}{δ \sqrt{N}} \sum_{l = 1}^{δ \sqrt{N}} P (ξ (b_{N, j, l}) = (k_{N}, y_{N}) | ξ (0) = e (W)) \\ = \sum_{| k_{p} - {\tilde{k}}_{N} | < \bar{R} \sqrt{\bar{N}}} \frac{L_{N} (1 + o_{N \to \infty, \bar{R} \to \infty} (1))}{\sqrt{π D N}} \frac{E (l_{(k_{N} - {\tilde{k}}_{p}) / \bar{N}), 1 / a})}{\bar{N}} ρ_{k_{N}, y_{N}} exp (- \frac{{(x (W) - k_{N})}^{2}}{D N}) \\ (10.9) & = \frac{1}{\sqrt{π D N}} \frac{ρ_{k_{N}, y_{N}}}{a} exp [- \frac{{(x (W) - k_{N})}^{2}}{D N}] (1 + o_{N \to \infty, \bar{R} \to \infty} (1)) \end{array}$ where the last step relies on the fact that $\begin{matrix} \int_{- \infty}^{\infty} l_{x, t} d x = t . \end{matrix}$

(II) $W \notin S_{\bar{R}} (N)$ and $| j | < N^{\bar{ε}}$ . In this case the same argument as in the proof of (10.7) shows that $\begin{matrix} \frac{1}{δ \sqrt{N}} \sum_{l = 1}^{δ \sqrt{N}} P (ξ (b_{N, j, l}) = (k_{N}, y_{N}) | ξ (0) = e (W)) ⩽ \frac{ε (\bar{R})}{\sqrt{N}}, \end{matrix}$ where $ε (\bar{R}) \to 0$ as $\bar{R} \to \infty$ .

(III) $| j | ⩾ N^{\bar{ε}}$ . Due to moderate deviation estimate for sums of independent random variables applied to the sum (9.3). $\begin{matrix} P (⋃_{W} ⋃_{j ⩾ N^{\bar{ε}}} A_{W, δ, j}) ⩽ C e^{- c N^{2 \bar{ε}}} . \end{matrix}$ Thus the main contribution to (10.2) comes from case (I). Performing the summation over $W \in S_{\bar{R}} (N)$ and $j \in [- N^{\bar{ε}}, N^{\bar{ε}}]$ and using (10.9) and the CLT for $x (W)$ we obtain (10.1). □

Theorem 10.1 implies Theorem 3.8(a). To prove Theorem 3.8(b) we need to consider $ξ (2 N)$ and $ξ (2 N + 1)$ separately (see the discussion at the end of Section 9) and note that in Example 3.3 $D = 1$ since, due to equation (6.35), ξ is a small perturbation of the simple random walk away from the origin.

Footnotes

A rough bound on large and moderate deviations

Contraction properties of products of positive matrices

The proof of relations (2.14), (2.15) follows from very general and well known contracting properties of positive matrices which we now recall.

Let $A_{δ}$ be the set of positive $m \times m$ matrices such that for any $A = (A (i, j)) \in A_{δ}$ one has ${min}_{i, j, k} A (i, k) / A (j, k) ⩾ δ$ , where $δ > 0$ does not depend on A. Let $R_{+}^{m}$ be the cone of non-negative vectors in $R^{m}$ and $R_{+, δ}^{m}$ its sub-cone of positive column vectors with ${min}_{i, j} x_{i} / x_{j} ⩾ δ$ . Then $A R_{+}^{m} \subset R_{+, δ}^{m}$ for any $A \in A_{δ}$ . Indeed, for any vector $x ⩾ 0$ ( $x \neq 0$ ) we have $\begin{matrix} (B.1) & \frac{{(A x)}_{i}}{{(A x)}_{j}} = \frac{\sum_{k = 1}^{m} A (i, k) x_{k}}{\sum_{k = 1}^{m} A (j, k) x_{k}} ⩾ min_{k} \frac{A (i, k)}{A (j, k)} ⩾ δ . \end{matrix}$ Next denote by $C^{δ}$ the set of rays generated by vectors from $R_{+, δ}^{m}$ . Also, we introduce the convention that $C^{0}$ is the set of rays generated by vectors from $R_{+}^{m}$ . If $x, y \in C^{δ}$ are two rays generated by vectors $x, y \in R_{+, δ}^{m}$ then the Hilbert’s projective distance between them is defined by $\begin{matrix} r (x, y) = max_{i, j} ln \frac{x_{i} y_{j}}{x_{j} y_{i}} . \end{matrix}$ The set $C^{δ}$ equipped with this metric is a compact metric space. The action of a matrix $A \in A_{δ}$ on $C^{0}$ is naturally defined by its action on $R_{+}^{m}$ and for $x \in C^{0}$ we write $A x$ for the image of x under the action of A. (B.1) shows that in fact $A C^{0} \subset C^{δ}$ .

We need the following version of a (stronger) result from [3, Chapter XVI, Theorem 3]: for all $A \in A_{δ}$ and all $x, y \in C^{δ}$ $\begin{matrix} (B.2) & r (A x, A y) ⩽ c r (x, y), where c = \frac{1 - δ}{1 + δ} . \end{matrix}$

We are now in a position to prove (2.14) and (2.15) from Section 2.3. To this end, note first that (2.13) implies that $A_{n} \in A_{δ}$ with $δ = m {\bar{ε}}^{2}$ .

Next, for $a ⩽ n$ , the sets $C_{a} \overset{def}{=} A_{n} \dots A_{a} C^{0}$ form a decreasing sequence, $C_{a} \supset C_{a - 1}$ , of compact subsets of $C^{δ}$ and therefore $⋂_{a ⩽ n} C_{a} \neq \emptyset$ . Due to (B.2), for any two rays $x, y \in C^{δ}$ the projective distance between their images in $C_{a}$ decays exponentially as $a \to - \infty$ : $\begin{matrix} (B.3) & r (A_{n} \dots A_{a} x, A_{n} \dots A_{a} y) ⩽ c^{n - a} r (x, y) . \end{matrix}$ (There is no loss of generality in assuming that $x, y \in C^{δ}$ since $A_{a} C^{0} \subset C^{δ}$ .)

Therefore there is a unique ray $v_{n} = ⋂_{a ⩽ n} C_{a}$ and $v_{n}$ in (2.14) is the unit vector corresponding to $v_{n}$ which proves (2.14). It remains to note that at a small scale the standard distance between unit vectors (as in (2.15)) is equivalent to the distance between rays generated by these vectors which means that (B.3) is equivalent to (2.15).

Regularity of ρ and Δ

Here we discuss the regularity of ρ and Δ which plays a key role in our analysis. To this end we recall the formulas for these expressions obtained in [19].

Let Ω be a compact metric space and $T : Ω \to Ω$ be a continuous map. (This meaning for the letter T is reserved for Appendix C only.)

Throughout this section we assume that ${(P, Q, R)}_{n} (ω) = (P, Q, R) (T^{n} ω)$ where $(P, Q, R)$ are continuous functions such that (2.1) and (2.4) are satisfied. Define $\begin{matrix} (C.1) & \begin{matrix} ζ (ω) = ζ_{0} (ω), A (ω) = A_{0} (ω), α (ω) = α_{0} (ω), σ (ω) = σ_{0} (ω), \\ v (ω) = v_{0} (ω), l (ω) = l_{0} (ω) λ (ω) = λ_{0} (ω), \tilde{λ} (ω) = {\tilde{λ}}_{0} (ω) \end{matrix} \end{matrix}$ then $\begin{matrix} (C.2) & \begin{matrix} ζ_{n} = ζ (T^{n} ω), A_{n} = A (T^{n} ω), α_{n} = α (T^{n} ω), σ_{n} (ω) = σ (T^{n} ω), \\ v_{n} = v (T^{n} ω), l_{n} = l (T^{n} ω), λ_{n} = λ (T^{n} ω), {\tilde{λ}}_{n} = \tilde{λ} (T^{n} ω) . \end{matrix} \end{matrix}$ It is proven in [19] that RWRE in bounded potential enjoy the property that $\begin{matrix} (C.3) & \tilde{λ} (ω) = \frac{\tilde{β} (T ω)}{\tilde{β} (ω)}, λ (ω) = \frac{β (T ω)}{β (ω)} \end{matrix}$ for continuous functions β, $\tilde{β}$ . Moreover, the functions $ζ (\cdot)$ , $v (\cdot)$ , $l (\cdot)$ are continuous in ω. The continuity of all other functions is implied by the continuity of ζ, v, and l.

It is proven in [19] that $\begin{matrix} ρ_{n} (ω) = ρ (T^{n} ω) and Δ_{n} (ω) = Δ (T^{n} ω) \end{matrix}$ where $\begin{matrix} (C.4) & ρ (ω) = c \frac{l (ω)}{\tilde{β} (ω)} and Δ (ω) = β (T ω) σ (ω) v (ω) + B (T ω) - B (ω) \end{matrix}$ and $\begin{matrix} (C.5) & B (ω) = \sum_{k = 0}^{\infty} β (T^{k + 1} ω) [ζ_{0} \dots ζ_{k - 1} v_{k} - (σ_{k} v_{k}) 1] . \end{matrix}$

The proof of Lemma 7.2 relies on the following fact

References

Alili, Asymptotic behaviour for random walks in random environments, J. Appl. Prob. 36 (1999), 334–349. doi:10.1239/jap/1032374457.

Berger,

Cohen and

Rosenthal, Local limit theorem and equivalence of dynamic and static points of view for certain ballistic random walks in i.i.d. environments, Ann. Probab. 44 (2016), 2889–2979. doi:10.1214/15-AOP1038.

Birkhoff, Lattice Theory, 3rd edn, AMS Colloquium Publications, Vol. 25, Prvidence, Rhode Island, 1973, vi+418 pp.

Bolthausen, Exact convergence rates in some martingale central limit theorems, Ann. Probab. 10 (1982), 672–688. doi:10.1214/aop/1176993776.

Bolthausen and

Goldsheid, Recurrence and transience of random walks in random environments on a strip, Comm. Math. Phys. 214 (2000), 429–447. doi:10.1007/s002200000279.

Bolthausen and

Goldsheid, Lingering random walks in random environment on a strip, Comm. Math. Phys. 278 (2008), 253–288. doi:10.1007/s00220-007-0390-4.

Bolthausen and

A.-S.

Sznitman, Ten Lectures on Random Media, DMV Seminar, Vol. 32, Birkhauser, Basel, 2002.

Bolthausen and

A.-S.

Sznitman, On the static and dynamic poins of view for certain random walks in random environment, Methods and Applications of Analysis 9 (2002), 345–376. doi:10.4310/MAA.2002.v9.n3.a4.

A.N.

Borodin, The asymptotic behavior of local times of recurrent random walks with finite variance, Teor. Veroyatnost. i Primenen. 26 (1981), 769–783.

10.

Brémont, One-dimensional finite range random walk in random medium and invariant measure equation, Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), 70–103. doi:10.1214/07-AIHP150.

11.

Brémont, Random walk in quasi-periodic random environment, Stochastics and Dynamics 9 (2009), 47–70. doi:10.1142/S0219493709002543.

12.

B.M.

Brown, Martingale central limit theorems, Ann. Math. Statist. 42 (1971), 59–66. doi:10.1214/aoms/1177693494.

13.

Chiarini and

J.-D.

Deuschel, Local central limit theorem for diffusions in a degenerate and unbounded random medium, Electron. J. Probab. 20 (2015), paper 112, 30 pp.

14.

I.P.

Cornfeld,

S.V.

Fomin and

Ya.G.

Sinai, Ergodic Theory, Grundlehren der Mathematischen Wissenschaften, Vol. 245, Springer, New York, 1982, x+486 pp.

15.

Davis and

McDonald, An elementary proof of the local central limit theorem, J. Theoret. Probab. 8 (1995), 693–701. doi:10.1007/BF02218051.

16.

Dolgopyat,

Fayad and

Saprykina, Erratic behavior for 1-dimensional random walks in generic quasi-periodic environment, in preparation.

17.

Dolgopyat and

Goldsheid, Limit theorems for random walks on a strip in subdiffusive regimes, Nonlinearity 26 (2013), 1741–1782.

18.

Dolgopyat and

Goldsheid, Local Limit Theorems for random walks in a 1D random environment, Arch. Math. 101 (2013), 191–200. doi:10.1007/s00013-013-0547-7.

19.

Dolgopyat and

Goldsheid, Central Limit Theorem for recurrent random walks on a strip with bounded potential, Nonlinearity 31 (2018), 3381–3412. doi:10.1088/1361-6544/aab89b.

20.

Dolgopyat and

Goldsheid, Invariant measure for random walks on ergodic environments on a strip, Ann. Prob. 47(4) (2019), 2494–2528. doi:10.1214/18-AOP1313.

21.

Durrett, Probability: Theory and Examples, 4th edn, Cambridge Univ. Press, Cambridge, 2010.

22.

Gallesco,

Popov and

G.M.

Schütz, Localization for a random walk in slowly decreasing random potential, J. Stat. Phys. 150 (2013), 285–298. doi:10.1007/s10955-012-0671-y.

23.

V.P.

Gaposhkin, On the dependence of the convergence rate in the strong law of large numbers for stationary processes on the rate of decay of the correlation function, Th. Prob., Appl. 26 (1982), 706–720. doi:10.1137/1126078.

24.

Goldsheid, Linear and sub-linear growth and the CLT for hitting times of a random walk in random environment on a strip, Prob. Th. Rel. Fields 141 (2008), 471–511. doi:10.1007/s00440-007-0091-0.

25.

Hall and

C.C.

Heyde, Martingale Limit Theory and Its Application, Academic Press, New York–London, 1980, xii+308 pp.

26.

J.M.

Harrison and

L.A.

Shepp, On skew Brownian motion, Ann. Probab. 9 (1981), 309–313. doi:10.1214/aop/1176994472.

27.

V.V.

Jikov,

S.M.

Kozlov and

O.A.

Oleinik, Homogenization of Differential Operators and Integral Functionals, Springer, Berlin, 1994, xii+570 pp.

28.

Kaloshin and

Ya.

Sinai, Nonsymmetric random walks along orbits of ergodic automorphisms, AMS. Transl. Ser. 2 198 (2000), 8 pp.

29.

Kesten, A renewal theorem for random walk in a random environment, Proc. Sympos. Pure Math. 31 (1977), 67–77. doi:10.1090/pspum/031/0458648.

30.

Kesten,

M.V.

Kozlov and

Spitzer, Limit law for random walk in a random environment, Composito Mathematica 30 (1975), 145–168.

31.

Komorowski,

Landim and

Olla, Fluctuations in Markov Processes. Time Symmetry and Martingale Approximation, Grundlehren der Mathematischen Wissenschaften, Vol. 345, Springer, Heidelberg, 2012, xviii+491 pp.

32.

Kozlov, The method of averaging and walks in inhomogeneous environments, Russian Math. Surveys 40 (1985), 73–145. doi:10.1070/RM1985v040n02ABEH003558.

33.

Lalley, An extension of Kesten’s renewal theorem for random walk in a random environment, Adv. in Appl. Math. 7 (1986), 80–100. doi:10.1016/0196-8858(86)90008-4.

34.

Lamperti, A new class of probability limit theorems, J. Math. Mech. 11 (1962), 749–772.

35.

Lejay, On the constructions of the skew Brownian motion, Probab. Surv. 3 (2006), 413–466. doi:10.1214/154957807000000013.

36.

Lenci, On infinite-volume mixing, Comm. Math. Phys. 298 (2010), 485–514. doi:10.1007/s00220-010-1043-6.

37.

Leskela and

Stenlund, A local limit theorem for a transient chaotic walk in a frozen environment, Stochastic Process. Appl. 121 (2011), 2818–2838. doi:10.1016/j.spa.2011.07.010.

38.

A.N.

Livsic, Cohomology of dynamical systems, Izv. Akad. Nauk SSSR Ser. Mat. 36 (1972), 1296–1320 (Russian).

39.

Menshikov,

Popov and

Wade, Non-homogeneous Random Walks: Lyapunov Function Methods for Near-Critical Stochastic Systems, Cambridge Tracts in Math., Vol. 209, Cambridge Univ. Press, Cambridge, UK, 2017, xviii+363 pp.

40.

Menshikov and

Wade, Random walk in random environment with asymptotically zero perturbation, JEMS 8 (2006), 491–513. doi:10.4171/JEMS/64.

41.

Menshikov and

Wade, Logarithmic speeds for one-dimensional perturbed random walks in random environments, Stoch. Process. Appl. 118 (2008), 389–416. doi:10.1016/j.spa.2007.04.011.

42.

Menshikov and

Wade, Rate of escape and central limit theorem for the supercritical Lamperti problem, Stochastic Process. Appl. 120 (2010), 2078–2099. doi:10.1016/j.spa.2010.06.004.

43.

Yu.V.

Prokhorov, On the local limit theorem for lattice distributions, Dokl. Akad. Nauk SSSR 98 (1954), 535–538.

44.

Roitershtein, Tranzient random walks on a strip in a random environment, Ann. Probab. 36 (2009), 2354–2387. doi:10.1214/08-AOP393.

45.

Ya.G.

Sinai, The limiting behavior of a one-dimensional random walk in a random medium, Theory Prob. Appl. 27 (1982), 256–268. doi:10.1137/1127028.

46.

Ya.G.

Sinai, Simple random walks on tori, J. Statist. Phys. 94 (1999), 695–708. doi:10.1023/A:1004564824697.

47.

Solomon, Random walks in a random environment, Ann. Prob. 3 (1975), 1–31. doi:10.1214/aop/1176996444.

48.

Stenlund, A local limit theorem for random walks in balanced environments, Electron. Commun. Probab. 18 (2013), paper 19, 13 pp.

49.

Stone, Limit theorems for random walks, birth and death processes, and diffusion processes, Illinois J. Math. 7 (1963), 638–660. doi:10.1215/ijm/1255645101.

50.

Zeitouni, Random walks in random environment, in: XXXI Summer School in Probability, St. Flour (2001), Lecture Notes in Math., Vol. 1837, Springer, Berlin, 2004, pp. 193–312.

Constructive approach to limit theorems for recurrent diffusive random walks on a strip

Abstract

Keywords

1. Introduction

2. Definition of the model and some preparatory results

2.1. Conventions and notation

2.2. The model

3. Application of results to some classes of environments

3.1. Classes of environments

Example 3.1 (Quasiperiodic systems).

Example 3.2 (Independent environments).

Example 3.3 (Small perturbations of the simple random walk on Z ).

3.2. The results

Theorem 3.4 (Functional CLT).

1 In the setting of Example 3.3 this means that we allow the environments which do not satisfy (3.3). In fact, it follows from the explicit expression for p in terms of υ (see equation (7.16)) that in Example 3.3 p = 1 2 iff υ = 1 .

Theorem 3.6 (Effective CLT).

6.1. Sufficient conditions for the CLT

Proposition 6.6 ([25, Theorem 3.7]).

7.1. Notation

7.2. Functional CLT

9.1. General result

Footnotes

A rough bound on large and moderate deviations

Contraction properties of products of positive matrices

Regularity of ρ and Δ

References

Example 3.3 (Small perturbations of the simple random walk on $Z$ ).

¹
In the setting of Example 3.3 this means that we allow the environments which do not satisfy (3.3). In fact, it follows from the explicit expression for $p$ in terms of $υ$ (see equation (7.16)) that in Example 3.3 $p = \frac{1}{2}$ iff $υ = 1$ .