Ballisticity of Random walks in Random Environments on $\mathbb{Z}$ with Bounded Jumps

An environment on $\mathbb{Z}$ is a nonnegative function $\omega:\mathbb{Z}\times\mathbb{Z}\to[0,1]$ such that for all $x\in\mathbb{Z}$, $\sum_{y\in\mathbb{Z}}\omega(x,y)=1$. For a fixed $x$ and $\omega$, we will let $\omega^{x}$ be the measure on $\mathbb{Z}$ defined by $\omega^{x}(y)=\omega(x,x+y)$. Then we can identify the function $\omega$ with the tuple $(\omega^{x})_{x\in\mathbb{Z}}$. Let $\mathcal{M}_{1}(\mathbb{Z})$ be the set of probability measures on $\mathbb{Z}$, (endowed with the topology of weak convergence); then $\Omega:=\prod_{x\in\mathbb{Z}}\mathcal{M}_{1}(\mathbb{Z})$ is the set of all environments on $\mathbb{Z}$.

For a given environment $\omega$ and $x\in\mathbb{Z}$, we can define the quenched measure $P_{\omega}^{x}$ on $\mathbb{Z}^{\mathbb{N}}$ (where we assume $0\in\mathbb{N}$) to be the law of a Markov chain ${\bf X}=(X_{n})_{n\geq 0}$ on $\mathbb{Z}$, started at $x$, with transition probabilities given by $\omega$. That is, $P_{\omega}^{x}(X_{0}=x)=1$, and for $n\geq 1$, $P_{\omega}^{x}(X_{n+1}=y|X_{0},\ldots,X_{n})=\omega(X_{n},y)$.

Let $\mathcal{F}$ be the Borel sigma field with respect to the product topology on $\Omega$, and let $P$ be a probability measure on $(\Omega,\mathcal{F})$. For a given $x\in\mathbb{Z}$, we define the annealed measure $\mathbb{P}^{x}=P\times P_{\omega}^{x}$ on $\Omega\times\mathbb{Z}^{\mathbb{N}}$ by

for measurable $A\subset\Omega,B\subset\mathbb{Z}^{\mathbb{N}}$. In particular, for all measurable events $B\subset\mathbb{Z}^{\mathbb{N}}$, we have $\mathbb{P}^{x}(\Omega\times B)=E[P_{\omega}^{x}(B)]$. We often abuse notation by writing $\mathbb{P}^{x}(B)$ instead of $\mathbb{P}^{x}(\Omega\times B)$.

As another notational convenience, we will use interval notation to denote sets of consecutive integers in the state space $\mathbb{Z}$, rather than subsets of $\mathbb{R}$. Thus, for example, we will use $[1,\infty)$ or $(0,\infty)$ to denote the set of integers strictly to the right of 0. However, we make one exception, using $[0,1]$ to denote the set of all real numbers from 0 to 1.

For a subset $S\subseteq\mathbb{Z}$, let $\omega^{S}=(\omega^{x})_{x\in S}$. In the case where $S$ is a half-infinite interval, we simplify our notation by using $\omega^{\leq x}$ to denote $\omega^{(-\infty,x]}$, and similarly with $\omega^{<x}$, $\omega^{\geq x}$, and $\omega^{>x}$.

We consider the following conditions for a probability measure $P$ on $\Omega$:

1. (C1)

   The $\{\omega^{x}\}_{x\in\mathbb{Z}}$ are i.i.d. under $P$.

2. (C2)

   For $P$–a.e. environment $\omega$, the Markov chain induced by $P_{\omega}^{0}$ is irreducible.

3. (C3)

   There exist $L$ and $R$ such that for $P$–a.e. environment $\omega$, $\omega(a,b)=0$ whenever $b$ is outside $[a-L,a+R]$.

It was shown in [7] that under the above assumptions, a 0-1 law holds for directional transience. That is, the walk is either almost surely transient to the right, almost surely transient to the left, or almost surely recurrent. We can also show that under these assumptions, a limiting velocity necessarily exists.

It was seen in [2] that this limiting velocity exists under a uniform ellipticity assumption, but it can be proven in the more general case with standard techniques, which we outline in Section 2.1. We then provide a characterization of ballisticity, making the following additional assumption for convenience.

1. (C4)

   For $P$–a.e. environment $\omega$, $\lim_{n\to\infty}X_{n}=\infty$, $P_{\omega}^{0}$–a.s.

By symmetry, our characterization also handles the case where the walk is transient to the left, and thus by the 0-1 law for directional transience, completely characterizes the regime $v\neq 0$ for all measures $P$ satisfying (C1), (C2), and (C3).

To formally state our characterization, we must establish notation for hitting times, as well as notation that counts the number of visits to a given site. For a given walk ${\bf X}=(X_{n})_{n=0}^{\infty}$, we define $H_{x}({\bf X})$ to be the first time the walk hits $x\in\mathbb{Z}$. That is,

We usually write it as $H_{x}$ when we can do so without ambiguity. For a subset $S\subset\mathbb{Z}$, let $H_{S}=\min_{x\in S}H_{x}$. First positive hitting times are denoted as $\tilde{H}_{x}$ or $\tilde{H}_{S}$. That is,

and $\tilde{H}_{S}=\min_{x\in S}\tilde{H}_{x}$. If the set is the half-infinite interval $[x,\infty)$, we use $H_{\geq x}$ to denote its hitting time, and similarly with $H_{>x}$, $H_{\leq x}$, and $H_{>x}$. For a walk ${\bf X}=(X_{n})_{n=0}^{\infty}$ on $\mathbb{Z}$ with $x\in\mathbb{Z}$, $N_{x}({\bf X})=\#\{n\in\mathbb{N}:X_{n}=x\}$ is the number of times the walk is at site $x$. We usually write it as $N_{x}$ if we are able to do so without ambiguity. For a subset $S\subset\mathbb{Z}$, let $N_{S}=\sum_{x\in S}N_{x}$.

Becasue the proof of Proposition 1.1 is only a slight modification of work that has already been done, we simply outline some details of the argument rather than giving a full proof.

The proof for the recurrent case (where, necessarily, $v=0$) can be done by a slight modification of arguments in [12], which we leave to the reader. The proof for the directionally transient case follows [6] in defining regeneration times $(\tau_{k})_{k=0}^{\infty}$. Let $\tau_{0}:=0$, and for $k\geq 1$, define

We can then show

where the numerator is always finite and the fraction is understood to be 0 if the denominator is infinite. It is standard (e.g., [6], [10]) to prove a LLN like (4) by the following steps:

1. (a)

   Show that $\frac{X_{\tau_{k}}}{k}$ approaches $\mathbb{E}[X_{\tau_{2}}-X_{\tau_{1}}]$.

2. (b)

   Show that $\frac{\tau_{k}}{k}$ approaches $\mathbb{E}[\tau_{2}-\tau_{1}]$.

3. (c)

   Show that $\mathbb{E}[X_{\tau_{2}}-X_{\tau_{1}}]<\infty$.

4. (d)

   Conclude that the limit (4) holds for the subsequence $\left(\frac{X_{\tau_{k}}}{\tau_{k}}\right)_{k}$.

5. (e)

   Use straightforward bounds that come from the definitions of the $\tau_{k}$ to get the limit for the entire sequence $\left(\frac{X_{n}}{n}\right)_{n}$.

The identity $\lim_{x\to\infty}\frac{H_{\geq x}}{x}=\frac{1}{v}$ then comes from a comparison of $\frac{x}{H_{\geq x}}$ with a subsequence of $\frac{X_{n}}{n}$.

The definition of the regeneration times is precisely set up so that both the sequences $(\tau_{k}-\tau_{k-1})_{k\geq 2}$ and $(X_{\tau_{k}}-X_{\tau_{k-1}})_{k\geq 2}$ are i.i.d. sequences, so proving the limits (a) and (b) is a matter of tracing how the i.i.d. feature follows from the definitions and applying the strong law of large numbers. In fact, arguing as in [6, Lemma 1], one can show that the triples

are i.i.d. under $\mathbb{P}^{0}=P\times P_{\omega}^{0}$ for $n\geq 2$.

The finiteness in (c) can be shown using arguments along the lines of those in [11, Lemma 3.2.5]. Because we have assumed almost-sure transience to the right, the measure $\mathbb{Q}$ introduced there is unnecessary. Another difference is that in our model, transience to the right does not imply that every vertex to the right of the origin is hit. There is a point in the argument from [11] where Zeitouni argues the the $\mathbb{Q}$-probability, for a given $x$, that a regeneration occurs at site $x$ approaches $\mathbb{P}^{0}(H_{<0}=\infty)$. Instead, we focus on the probability that the regeneration occurs on a given interval of length $R$. For $z\geq 0$, let $B_{z}$ be the event that for some $k$, $X_{\tau_{k}}\in[zR,(z+1)R)$. Then

where the second to last equality comes from the fact that $\omega^{<zR}$ is independent of $\omega^{\geq zR+i}$, and the last comes from translation invariance and the fact that $H_{[zR,(z+1)R)}<\infty$ $\mathbb{P}^{0}$–a.s. The rest of the argument from [11] goes through to prove (c), and (d) and (e) easily follow.

For the rest of this paper, assume $P$ satisfies (C1), (C2), (C3), and (C4). Our goal is to prove Theorem 1.2. We begin with the following lemma, from which $(b)\Rightarrow(c)$ follows immediately.

Our next goal is to prove (c) $\Rightarrow$ (a). The proof of the following lemma, will use the regeneration times defined in (3).

Next, we will define a “walk from $-\infty$ to $\infty$.” Call the set of vertices $((k-1)R,kR]$ the $k$th level of $\mathbb{Z}$, and for $x\in\mathbb{Z}$, let $[[x]]_{R}$ denote the level containing $x$. Let $\omega$ be a given environment. From each point $a\in\mathbb{Z}$, run a walk according to the transition probabilities given by $\omega$ until it reaches the next level (i.e., $[[a+R]]_{R}$). This will happen $P_{\omega}^{a}$–a.s. for $P$–a.e. $\omega$, by assumption (C4) and because it is not possible to jump over a set of length $R$. Do this independently at every point for every level. This gives what we will call a cascade: a set of (almost surely finite) walks indexed by $\mathbb{Z}$, where the walk indexed by $a\in\mathbb{Z}$ starts at $a$ and ends upon reaching level $[[a+R]]_{R}$. Equip the set of cascades with the natural sigma field, let $P_{\omega}$ be the probability measure we have just described on the space of cascades, and let $\mathbb{P}=P\times P_{\omega}$.

For $\mathbb{P}$–almost every cascade (i.e., those where the walk started from each vertex hits the level to its right), we can concatenate an appropriate chain of these finite walks to generate a walk started at any point $a\in\mathbb{Z}$. To the walk started from $a=a_{0}$, append the walk started from the point $a_{1}\in[[a+R]]_{R}$ where that walk lands. And to that, append the walk started from the point $a_{2}\in[[a+2R]]_{R}$ where the finite walk from $a_{1}$ lands, and so on. This gives, for each point $a$, a right-infinite walk ${\bf X}^{a}=(X_{n}^{a})_{n=0}^{\infty}$. It is crucial to note that by the strong Markov property, the law of ${\bf X}^{a}$ under $P_{\omega}$ is the same as the law of ${\bf X}$ under $P_{\omega}^{a}$, which also implies that the law of ${\bf X}^{a}$ under $\mathbb{P}$ is the same as the law of ${\bf X}$ under $\mathbb{P}^{a}$.

For each $x\in\mathbb{Z}$, let the “coalescence event” $C_{x}$ be the event that all the walks from level $[[x-R]]_{R}$ first hit level $[[x]]_{R}$ at $x$. On the event $C_{x}$, we say a coalescence occurs at $x$.

Assume the environment and cascade are in the event $\mathcal{E}_{1}$ defiend in the above lemma. Let $(x_{k})_{k\in\mathbb{Z}}$ be the locations of coalescence events (with $x_{0}$ the smallest non-negative $x$ such that $C_{x}$ occurs). By definition of the $x_{k}$, for every $k$ and for every $a$ to the left of $[[x_{k}]]_{R}$, $H_{[[x_{k}]]_{R}}({\bf X}^{a})=H_{x_{k}}({\bf X}^{a})<\infty$. Now for $j<k$, it necessarily holds that $x_{j}$ is to the left of $[[x_{k}]]_{R}$, since there can be only one $x_{k}$ per level. Define $\nu(j,k):=H_{x_{k}}({\bf X}^{x_{j}})$. By definition of the walks ${\bf X}^{a}$, we have for $j<k$, $n\geq 0$,

From this one can easily check that the $\nu(j,k)$ are additive; that is, for $j<k<\ell$, we have $\nu(j,\ell)=\nu(j,k)+\nu(k,\ell)$. Because all the ${\bf X}^{x_{k}}$ agree with each other in the sense of (11), we may define a single, bi-infinite walk $\overline{\bf X}=(\overline{X}_{n})_{n\in\mathbb{Z}}$ that agrees with all of the ${\bf X}^{x_{k}}$. We choose to let $\overline{X}_{0}=x_{0}$. For $n\geq 0$, let $\overline{X}_{n}=X_{n}^{x_{0}}$. For $n<0$, choose $j<0$ such that $\nu(j,0)>|n|$, and let $X_{n}=X_{\nu(j,0)-|n|}^{x_{j}}$. This definition is independent of the choice of $j$, because if $j<k<0$ with $v(k,0)>|n|$, then by (11) and the additivity of the $\nu(j,k)$, we have

We may then define $\overline{N}_{x}:=\#\{n\in\mathbb{Z}:\overline{X}_{n}=x\}$ to be the amount of time the walk $\overline{\bf X}$ spends at $x$. Thus, $\overline{N}_{x}=\lim_{a\to-\infty}N_{x}({\bf X}^{a})$.

We now give the connection between $\overline{N}_{0}$ and the limiting velocity $v$.

We note that a similar formula for the limiting speed in the ballistic case can be obtained from [4, Theorem 6.12] for discrete-time RWRE on a strip, but under a stronger ellipticity assumption (and with a less explicit probabilisitic interpretation).

Now we can see that the walk is ballistic if and only if $\mathbb{E}[\overline{N}_{0}]<\infty$. We now compare $\mathbb{E}[\overline{N}_{0}]$ with $\mathbb{E}^{0}[N_{0}]$.

We are now in a position to prove our main theorem, and in fact two of the three implications are already done.