{'fraction_non_alphanumeric': 0.06535586886359776, 'fraction_numerical': 0.021488024460676065, 'mean_word_length': 3.6228896741264234, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Simple Transient Random Walks in One-dimensional Random Environment: the Central Limit Theorem

We consider a simple random walk (dimension one, nearest neighbour jumps) in a quenched random environment. The goal of this work is to provide sufficient conditions, stated in terms of properties of the environment, under which the Central Limit Theorem (CLT) holds for the position of the walk. Verifying these conditions leads to a complete solution of the problem in the case of independent identically distributed environments as well as in the case of uniformly ergodic (and thus also weakly mixing) environments.


Introduction
The study of the asymptotic behaviour of random walks (RW) in random environment (RWRE) has been started more than thirty years ago. The first mathematical results were obtained in the pioneering papers by M. Kozlov [5], Solomon [7], and Kesten-M. Kozlov-Spitzer [4]. The asymptotic behaviour of a RW in annealed environments has been described in [4] in detail for all regimes except the recurrent one. Sinai [6] has completed this description by discovering the log 2 law in the recurrent case. Recently, the results of [4] were extended by Mayer-Wolf-Roitershtein-Zeitouni to the case of Markovian environments [9].
But the question about the asymptotic behaviour of RW in a quenched (frozen) environment remains largely open. However, it has to be mentioned that Alili [1] proved the Central Limit Theorem (CLT) for a random walk in a quasi-periodic environment with very special additional properties.
The aim of this work is to prove that under certain sufficient conditions (which are often also necessary) the Central Limit Theorem (CLT) holds for simple (one-dimensional with nearest neighbour jumps) random walks in a typical quenched environment.
Traditionally, the simple random walk is characterized by two quantities: the hitting time T (n) of site n and the position of the walk X(t) at time t. One usually starts with the study of the asymptotic behaviour of T (n) as n → ∞ and then 'translates' the results of this study into results for the asymptotic behaviour of X(t) as t → ∞. Hitting times are easy to control due to the fact (used already in [7]) that, in this model, they can be presented as sums of independent random variables. In [1] the CLT for hitting times has been proved for RW's in ergodic environments. The proof of this fact is given below (Theorem 3) mainly because it is used in the proof of Theorem 4. Our main results are concerned with a less simple question about the position of the walk and are as follows.
Theorem 4 reduces the question about the CLT for X(t) to a question about certain properties of the environment. It also offers a choice of two random centerings for X(t) which are functions of the environment.
In Theorem 5 we prove that independent identically distributed (i.i.d.) random environments do have the properties allowing to apply Theorem 4 in this case. In fact it can be shown (though we don't do it here) that environments satisfying strong mixing conditions also have these properties.
Theorem 6 provides a very short and simple proof of the CLT for uniformly ergodic environments (in particular, quasi-periodic environments). It thus addresses the other side of the spectrum, as far as the mixing properties are concerned.
It should be emphasized that at present there is no proof of CLT for a position of the walk which would work in a general ergodic environment.
The CLT in annealed setting is not discussed in this paper. It can be derived from the quenched CLT in the case of environments with strong mixing properties but it should be stressed once gain that in the general ergodic setting even this question remains opened both for the hitting times and the position of the walk.
Apart of the above there is the following reason for appearance of this work. Our intention is to address the problem in the simplest case since this is where the ideas can be best explained and the proofs are short and transparent. The same approach, properly adapted, works in a much more general case of a RWRE on a strip but explaining it there is a much more technical matter.
Since the problems considered in this work stem directly from [7,4], we don't review the beautiful development that followed the appearance of these papers. Relatively recent and modern introductions to the subject as well as comprehensive reviews can be found in [10], [2], and [8].
The article is organized as follows.
We start by describing the models considered in this work. We then explain those results from [7], [4] and [1] which are relevant to this work. This is followed by statement of our main results which are then proved in the next section. Appendix contains several technical results some of which may be new and some are unlikely to be new but are included mainly for the sake of completeness.
I am grateful to E. Bolthausen and O. Zeitouni for valuable discussions and suggestions.
This paper was about to be submitted when I learned that O. Zeitouni & J. Peterson obtained a result which is similar to the one stated in Theorem 5.

Description of the model.
Let (Ω, F , P, T ) be a dynamical system with Ω = {ω} denoting a set of elementary events, F being a σ-algebra of subsets of Ω, P denoting a probability measure on (Ω, F ), and T : Ω → Ω being an invertible transformation of Ω preserving measure P. Next, let p : Ω → (0, 1) be a measurable real valued function on Ω such that 0 < p(ω) < 1 for all ω ∈ Ω.
Put p n ≡ p n (ω) = p(T n ω), q n = 1 − p n , −∞ < n < ∞. For any such sequence p n we shall now define a random walk X(t; ω, z) with discrete integer valued time t ≥ 0. The phase space of the walk is a one-dimensional lattice Z and p n , q n are its transition probabilities: For any starting point z ∈ Z the probability law on the space of trajectories is denoted by P r ω,z and is defined by its finite-dimensional distributions (1.2) We say that the sequence p n (or, equivalently, the ω) is the environment or the random environment of the walk. The annealed probability measure on the product of the space of environments Ω and the space of trajectories X(·; ω, z) starting form z is a semi-direct product of P×P r ω,z , defined by P(dω)P r ω,z (dX). We write P r ω for P r ω,z and X(·) for X(·; ω, z) when there is no danger of confusion. It is useful to remember that, unless explicitly stated otherwise, we always suppose that the environment is quenched (frozen).
The just described general class of models provides a natural setting for Theorems 3 and 4.
It has already been mentioned above that we shall consider two sub-classes of this model. The so called the i.i.d. environments form one of these sub-classes and arise when p n is a sequence of independent identically distributed random variables.
A sub-class of random environments which we call uniformly ergodic environments is obtained when the dynamical system has very good ergodic properties which are usually combined with very week mixing properties. It is convenient to give the precise definition later but it is natural to mention here that a quasiperiodic environment is also a uniformly ergodic environment.
The notation T (n) is reserved for the case k = 0. We put τ k = T k (k + 1). The random variables τ k are independent when ω is fixed (with their distributions depending on k and ω). As in [7], we shall make use of the following simple relation 2. Expectations. Throughout the paper E denotes the expectation with respect to the measure P. By E ω,z we denote the expectation with respect to the measure P r ω,z ; in those cases when the starting point of the walk is clearly defined by the context we may use E ω for E ω,z (e. g. E ω τ k ≡ E ω,k−1 τ k ). The notation Var ω will be used for the variance of a random variable calculated with respect to the measure P r ω,z , e. g.
3. Main assumptions. The following set of assumptions is called Condition C and is supposed to be satisfied throughout the paper: C3 There is a γ > 2 such that We shall now quote several statements from [7] in a form which suits us best. Let us put (it is clear that λ does not depend on j). The recurrence and transience criteria for our random walk are given by the following result from [7].
Theorem 1 Suppose that Condition C is satisfied. Then (i) λ < 0 implies for P-a.e. environment ω that X ω is transient to the right. Symmetrically, λ > 0, implies for P-a.e. environment ω that X ω is transient to the left.
(ii) λ = 0 if and only if X ω is recurrent for P-a.e. ω, that is From now on we consider only those RWRE which are transient to the right, that is λ < 0. To state further results it is convenient to define a function r(κ) depending on a parameter κ ∈ [0, γ], where γ is the same as in C2 ′ , namely: This function is a simple generalization of the one first considered in [4] (see also [9] where log r(κ) has been studied). If the p n 's are i.i.d. random variables then of course As has been shown in [4] and in [9], the asymptotic behaviour of the RWRE can be characterized in terms properties of r(κ) which are well worth of being studied. However, for the purposes of this work, we only need the following simple Lemma 1 Suppose that Condition C ′ is satisfied. Then the function ln r(κ) is continuous and convex on [0, γ).
The proof of this Lemma is given in the Appendix. Let us define a function which plays a very important role in this paper (as it did already in [7]): for a fixed environment ω put and The probabilistic meaning of µ k (ω) is explainne by the following [10]) If λ < 0 then µ k is finite for P-almost all ω and E ω τ k = µ k .
In particular if r(1) < 1 then The quenched Law of Large Numbers has been proved in [7] for i.i.d. environments and the same proof works in general ergodic setting (see [1] or [10] for more detailed explanations).
where the sequence ε n does not depend on ω and lim n→∞ ε n = 0. We say that a random environment is uniformly ergodic if T is µ 0 -uniformly ergodic.
Let us explain this statement in a more general setting. Suppose that T is a continuous homeomorphism of a compact metric space Ω and that P is its unique invariant measure. Suppose also that the function p(·) is continuous. It is then easy to see that r(κ) = e κλ . Indeed, where |ǫ n (ω)| ≤ ε n . Hence e κ(λ−εn) ≤ r(κ) ≤ e κ(λ+εn) and the statement follows. If now λ < 0, then series (1.6) converges uniformly in ω ∈ Ω and hence µ 0 is a continuous function on Ω. The latter in turn implies uniform ergodicity of the environment.

Main Results
In order to state the central limit theorem for T (n) one has to know the variance of this random variable. It turns out that in the case of the simple walk an explicit expression for the variance can be found and the calculations are not complicated. Formula (2.2) has been obtained in [1] where branching processes are used for its derivation. We use a different approach which works also for more general models ( [3]).
Lemma 3 Suppose that λ < 0. Then for P-almost every ω the variance of T (n) ≡ T (n; ω) is finite and is given by If in addition r(2) < 1, then If r(2) < 1 and the environment is i.i.d. then The proof of Lemma 3 is given in appendix. Denote where the last equality follows from (1.3) and Lemma 2. We often write H(n) for H(n, ω). It is clear from 2.5 that H(n) is the natural centering in the CLT for T (n). It turns out that centerings for X(t) can too be expressed, with a varying degree of explicitness, in terms of the function H(·).
In the sequel we denote ⌊y⌋ def = integer part of y, where y is any real number. We also use the following convention about summations. For any real numbers (2.6) In particular for y ≥ 0 we put H(y) def = H(⌊y⌋).
is said to be the explicit centering for X(t). The integer valued functionb(t; ω) such that is said to be the implicit centering for X(t).
It is easy to see that For the rest of the paper we suppose that Condition C ′ is satisfied and r(2) < 1.
Remark. Uniform convergence in (2.10) is used in the proof of Theorem 4.

Theorem 4
Suppose that at least one of the following two relations holds: (µ k − µ) = 0 with P-probability 1 for any real x (2.11) (µ k − µ) = 0 with P-probability 1 for any real x. (2.12) Then for P-almost every environment ω

13)
where σ * 2 = µ −3 σ 2 , the convergence in 2.13 is uniform in x and can be equal to any of the two if both (2.11) and (2.12) hold).
Remarks. 1. Note that in (2.11) and in (2.12) the summation is carried out within random limits.
2. The explicit form in which b(t) is given by (2.7) allows one to state condition (2.11) in the following equivalent form: (µ k − µ) = 0 with P-probability 1 for any real y.
However, (2.11) is in fact a good approximation for (2.12) in the case of environments with sufficiently strong mixing properties. Besides, it is also more convenient to use it in the proof of Theorem 4. We finish this section by stating two theorems which demonstrate the usefulness of conditions (2.11) and (2.12).
Theorem 5 In the i.i.d.random environment (2.11) holds and thus for P-almost every environment ω with convergence in (2.14) being uniform in x.
Theorem 6 Suppose that the environment is uniformly ergodic. Then (2.12) holds and thus for P-almost every environment ω and convergence in (2.15) is uniform in x.

Proofs
Proof of Theorem 3. Proving (2.10) essentially means proving a CLT for the sum of independent random variables τ k . Indeed, since Var ω (T (n)) nσ 2 , it is enough to check that for P-almost all ω and that CLT holds for T (n). Relation (3.2) follows from (2.1), (2.3), and the Birkhoff ergodic theorem. Next, for those ω for which (3.2) holds, also max 0≤k≤n−1 This in turn is well known to imply that the Lindeberg's conditions for the CLT for sums of non-identically distributed random variables τ k holds. Theorem 3 is proved.
Proof of Theorem 4. As usual with CLT's, it is sufficient to prove (2.13) for every fixed value of x. Thus, for the duration of the proof x, is considered to be a fixed parameter. The proof of (2.13) will be split into three parts. Part 1: approximating X(t) by n t . For any integer time t let n t be a positive random integer such that Remark. This definition of n t has been used already in [7] in the proof of the Law of Large Numbers cited above.
Since |X(t) − X(t ′ )| ≤ |t − t ′ | and since X(T (n t )) = n t and X(T (n t + 1)) = n t + 1 (by the definition of T (n)), it follows that The sequence τ k forms a stationary process in annealed environment and since E E ω τ 2 k < ∞ we have that t − 1 2 τ nt → 0 as t → ∞ with P × P r ω -probability 1 which in turn implies that it holds for P -almost every ω with P r ω -probability 1. This implies that proving (2.13) is equivalent to proving that Part 2: proof for the case when (2.11) holds. We need a simple (but very useful) identity. Namely, it follows from (3.3) and monotonicity of the function T (·) that for any y ≥ 0 the following two events coincide: where as before T (y + 1) ≡ T (⌊y⌋ + 1). This identity is a slight modification of the one which has been often used in the context of RWRE at least since the appearance of paper [4]. Hence, for sufficiently large values of t we can write It is natural to use the fact that, for a typical fixed ω, T (B(t) + 1) is an asymptotically normal random variable. Let us take a closer look at the parameters of this random variable. First of all it follows from (2.7) and the Birkhoff ergodic theorem that lim t→∞ t −1 B(t) = µ −1 for P-almost every ω. (3.9) Relation (3.9) and the Birkhoff ergodic theorem imply that for P-almost all ω t −1 Var ω (T (B(t) + 1)) = t −1 Finally, Returning to the original expression for B(t) and simultaneously replacing b(t) in the right hand side of (3.11) by its expression from (2.9) leads to we can present the right hand side of (3.8) as (3.13) But, according to (2.11), we have for P-almost every ω: and also, because of (2.10), we have that for P-almost every ω the sequence G(t) converges in distribution to a standard normal random variable. Hence which proves (2.13). Part 3: proof in the case when (2.12) holds. The proof goes along the same lines as in Part 2 with the natural replacement of b(t) byb(t). On the other hand, subtle differences appear at the end of the proof; this is why it may be useful to give a brief outline of it here. As in Part 2, it follows from (3.7) that where the second line in (3.17) follows from the definition ofb(t) (see (2.8)) and . We can then right that . We note that t − 1 2 µb (t) → 0 with Pprobability 1 because µ 2 k is a stationary sequence with Eµ 2 k < ∞ (see (1.8)). This together with (2.12) and the asymptotic normality ofG(t) finishes the proof.
Proof of Theorem 5. According to Theorem 4 we only have to check that for i.i.d. environments (2.11) holds true. In fact, we shall prove that i.i.d. environments satisfy (3.24) which is slightly stronger than (2.11). To explain the last statement let us put We shall use the following notations. If Y is a random variable then ||Y || is its usual norm in L 2+2δ (Ω), that is where δ > 0 is such that r(2 + 2δ) < 1. The constant C in (3.21) depends only on δ and the distribution of the environment.
Remark. Even though the random variables µ j are not independent, a statement which is stronger than (3.22) can be proved. We don't do this because (3.22) is sufficient for our purposes. The proof of Lemma 4 will be given at the end of this section. We now continue the proof of the theorem.
If ω is such that (3.22) holds then there is t(ω) such that We note next that, since c <c, the inequality i + |s| < n 1+c holds for sufficiently large values of n. This together with (3.27) implies that for sufficiently large n R(n 2 + i, c, ω) ≤ 2R(n 2 ,c, ω). Note that (3.21) is equivalent to saying that the sequence µ j has the following property: for any m where C is a constant (related to the previous C in an obvious way). Using (3.30) and stationarity of µ j we obtain that (3.31) It is now obvious that ifc and the latter in particular implies that lim n→∞ R(n 2 ,c, ω) = 0 for almost all ω. Lemma 5 and thus also Theorem 5 is proved.
Proof of Theorem 6. In order to check that (2.12) holds we note that µ 0uniform ergodicity (see Definition 1) implies that This is due to the fact that, since ω in (1.12) is arbitrary, it can be replaced by T k ω. In particular the left hand side in (2.12) can be estimated as The proof of (2.12) is finished.
Proof of Lemma 4. It follows from (1.7) that Let us put β = r(2 + 2δ) 1 2+2δ . Since ||A j . . . A j−i+1 || = β i and r(1) ≤ β by Jensen's inequality, we have The H(n, ω) can be presented as It is then clear that and hence where the last step is due to (3.36). To estimate ||B * n (i)|| we note that and then by Marcinkiewicz-Zygmund inequality where C δ depends only on δ and C 1 = 4 2+2δ 1+2δ C δ . But since we have that Substituting this estimate in (3.40), we obtain If we now put l = n 1 2 , then sup n C(n, n 1 2 ) ≤ C for some constant C. This proves (3.21). The proof of (3.22) follows immediately from Lemma 6 (see Appendix) whose conditions are satisfied because of (3.21) and because µ j is a stationary sequence.

Sequences of random variables satisfying the maximal inequality.
Let Y 1 (ω), Y 2 (ω), ... be a sequence of random variables on the probability space (Ω, F , P). We put Lemma 6 Suppose that for some constant C the inequality ||S * k,n || ≤ Cn Proof. The condition of the lemma implies that This proves (4.1) for the subsequence n m . To control the rest of the sequence, we shall show that V (n, l) ≡ |(n m + l) − 1+c 2 S n m +l − n − 1+c 2 m S n m | → 0 as n → ∞ uniformly in l ∈ [1, (n + 1) m − n m ] with P-probability 1. To this end note that V (n, l) = |(n m + l) − 1+c 2 (S n m +l − S n m ) − (n − 1+c 2 m − (n m + l) − 1+c 2 )S n m | ≤ I 1 (n, l) + I 2 (n), where I 1 (n, l) = n −m 1+c 2 |S n m +l − S n m | and I 2 (n) = n −m 1+c 2 S n m . We have just proved that I 2 (n) → 0 as n → ∞. To estimate I 1 (n, l) note that But then where the choice of C 2 is obvious. It is now clear that ∞ n=1 E(I 3 (n)) 2+2δ < ∞ and hence lim n→∞ I 3 (n) = 0 with P-probability 1. This implies that I 1 (n, l) → 0 and thus also V (n, l) → 0 as n → ∞ uniformly in l ∈ [1, (n + 1) m − n m ] with P-probability 1. The lemma is proved.

General equations for E x T x and Var x (T x ).
We shall make use of two general equations. One is the well known equation for the expectations of hitting times (equation (4.2) below). It can be found in any textbook on Markov chains. The other (equation (4.3)) establishes relationbetween the expectation and the variance of a hitting time of a random walk. It is equally elementary but it seems that it is easier to derive it than to find a proper reference. Since the proof of (4.3) naturally includes the derivation of (4.2) both relations are proved here.
Consider a connected Markov chain with a with a discrete phase space S and a transition kernel k(x, y), and let B be a proper subset of S. For x ∈ S \ B denote by T x the first moment at which the random walk starting from x hits B. Put e(x) where E x is the usual expectation with respect to the measure on the space of trajectories starting from x. All expectations considered in this section are supposed to be finite.

Lemma 7
The functions e(x) and v(x) satisfy the following systems of equations: where f (x) = y k(x, y)(e(y) − e(x) + 1) 2 .
Proof. Denote by χ x,y the indicator function of the event { the first step of a random walk starting from x is to y}.
Obviously 1 = y χ x,y and hence Since E x (χ x,y (T y + 1)) = k(x, y)(E y T y + 1), applying E x to both parts of (4.4) leads to (4.2). Similarly and applying E x to both parts of (4.5) leads to In order to obtain the first equation of (4.3) it remains to observe that E y (T y + 1 − e(x)) 2 = E y (T y − e(y)) 2 + (e(y)− e(x)+ 1) 2 = v(y)+ (e(y)− e(x)+ 1) 2 and to substitute the last relation into (4.6). Finally, the second equation in (4.2) and (4.3) is obvious.

Proof of Lemma 3.
To prove Lemma 3 we shall use the results of the previous subsection in the case when S = Z is a line and B ≡ B n is a semi-line of integers which are ≥ n. Technically, equations (4.2) are a particular case of (4.3) and it makes sense to solve that latter for a general function f (x). Note first that (4.3) can be re-written in terms of parameters p k , −∞ < k < ∞, as follows: g k = p k g k+1 + q k g k−1 + f k if k < n, g n = 0, (4.7) where the meaning of g k depends on the choice of f . Solving (4.7) is a relatively simple and well studied matter. The following lemma is included into this work for the sake of completeness. As before, A j = p j q −1 j ≡ p j (1−p j ) −1 ; the sequence ω = (p j ) −∞<j<∞ is fixed throughout this section.
We shall now prove Lemma 3. To this end note first that if we substitute f k ≡ 1 into (4.8) and (4.9), then, according to (4.2) we obtain formulae for e k ≡ E ω T k (n) and thus also for µ k = e k+1 − e k (see Lemma 2). Next, to find v k ≡ Var ω T k (n) we have to put f k = p k (e k+1 − e k + 1) 2 + q k (e k−1 − e k + 1) 2 = p k (µ k + 1) 2 + q k (1 − µ k−1 ) 2 .
The main equation in (4.8) can be rewritten as p k (g k −g k+1 ) = q k (g k−1 −g k )+f k and thus (g k −g k+1 ) = A k (g k−1 −g k )+p −1 k f k .
In particular this leads to the following relations: To see now that d j in (4.8) turns into (2.2) a matter of very simple calculation. Relation (2.3) follows now from the condition r(2) < 1. Finally the explicit expression (2.4) is again a matter of simple calculation. Lemma 3 is proved.