# Random walk driven by the simple exclusion process

François Huveneers, François Simenhaus

► To cite this version:

François Huveneers, François Simenhaus. Random walk driven by the simple exclusion process. Electronic Journal of Probability, 2015, 20 (105), pp.1-42. 10.1214/EJP.v20-3906. hal-01099144v2

HAL Id: hal-01099144

https://hal.science/hal-01099144v2

Submitted on 8 Jan 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

Electron. J. Probab. 20 (2015), no. 105, 1–42.
ISSN: 1083-6489 DOI: 10.1214/EJP.v20-3906

Random walk driven by the simple exclusion process

François Huveneers\* François Simenhaus\dagger

**Abstract**

We prove a strong law of large numbers and an annealed invariance principle for a random walk in a one-dimensional dynamic random environment evolving as the simple exclusion process with jump parameter $\gamma$. First, we establish that if the asymptotic velocity of the walker is non-zero in the limiting case $"\gamma = \infty"$, where the environment gets fully refreshed between each step of the walker, then, for $\gamma$ large enough, the walker still has a non-zero asymptotic velocity in the same direction. Second, we establish that if the walker is transient in the limiting case $\gamma = 0$, then, for $\gamma$ small enough but positive, the walker has a non-zero asymptotic velocity in the direction of the transience. These two limiting velocities can sometimes be of opposite sign. In all cases, we show that the fluctuations are normal.

**Keywords:** Random walk in dynamic random environment; limit theorem; renormalization; renewal times.

AMS MSC 2010: 60K37; 60F17.

Submitted to EJP on November 4, 2014, final version accepted on September 26, 2015.

# 1 Introduction

The question of the evolution of a random walk in a disordered environment has attracted a lot of attention in both the mathematical and the physical communities over the past few decades. The first studies were concerned with static random environments. In this set-up, anomalous slowdowns are expected in comparison with the homogeneous case, as the environment may create traps where the walker gets stuck for long times. This effect is particularly strong in one dimension, where it is by now well understood (see [24] for background). In dynamical random environments instead, the transition probabilities of the walker evolve with time too. If the environment has good space-time mixing properties, one expects the trapping phenomenon to disappear, and the walker to behave very much as if the medium was homogeneous. The study of this case has recently led to intense researches; see for example [13, 21] and references therein, as well as [2] for an overview and further references.

However, examples of dynamical environments with slow relaxation times occur naturally. Indeed, in the presence of a macroscopically conserved quantity, the environment

<footnote>\*Université Paris-Dauphine, France. E-mail: huveneers@ceremade.dauphine.fr</footnote>

<footnote>†Université Paris-Dauphine, France. E-mail: simenhaus@ceremade.dauphine.fr</footnote>
may evolve diffusively. Time correlations then only decay as $t^{-d/2}$ in dimension $d$. Especially for $d=1$, correlations decay so slowly that the results developed for fast mixing environments do not apply (see e.g. [3, 10, 13, 20, 21]). Slowly mixing environments form an intermediate class of models, which is still far for being well understood at the present time [2, 5].

In this paper, we are interested in the asymptotic behavior as $t \to \infty$ of $X_t/t$, where $X_t$ denotes the position at time $t$ of a walker driven by the one-dimensional simple exclusion process, at equilibrium with density $0 < \rho < 1$. The walker evolves in discrete time: if he sits on a particle at the moment of jumping, he moves to the right with probability $\alpha$ and to the left with probability $1-\alpha$ for some $0 < \alpha < 1$, while, if he sits on a vacant site, these probabilities become respectively $\beta$ and $1-\beta$ for some $0 < \beta < 1$ (see Figure 1, as well as Section 1.1 below for a more rigorous description). Of particular interest is the case $\alpha < \frac{1}{2} < \beta$ or vice versa, as we then see reappearing the possibility of trapping mechanisms.

<figure><img src="image_3.png" /><figcaption>Figure 1: Transition probabilities for the walker (red) evolving on top of the particles of the simple exclusion process (blue).</figcaption></figure>

Let $\gamma$ be the jump rate of the particles of the exclusion dynamics. Two regimes, depending on the value of $\gamma$, are considered in this article. We first deal with the fluid regime $\gamma \gg 1$. In the formal limit $"\gamma = \infty"$, the walker evolves as in an homogeneous medium: he jumps to the right with the homogenized probability $\tilde{p} = \rho\alpha + (1-\rho)\beta$ and to the left with probability $1-\tilde{p}$. We assume $\tilde{p} \neq \frac{1}{2}$, and say $\tilde{p} > \frac{1}{2}$ to fix things. The walker drifts thus to the right in the limiting case $"\gamma = \infty"$ and the fluctuations are normal. Let us now take $1 \ll \gamma < \infty$. In the time interval left between each step of the walker, the exclusion process mixes the particles in boxes of size $\gamma^{1/2}$. Therefore, most of the time, the walk will behave in the same way as the limiting homogeneous walk. However, the walker will eventually enter some regions where the density of particles is anomalously high or small, and behave then differently. But regions of size $l$ with an anomalous density of particles (with respect to the equilibrium measure) are typically at distance $e^{cl}$ from the origin for some $c > 0$, while only a time of order $l^2$ is needed for the dynamics to disaggregate them. Therefore, these regions do not act as efficient barriers to the evolution of the walker, which exhibits thus a positive asymptotic velocity. This is made precise in Theorem 1.1, where it is also shown that fluctuations are normal.

We next deal with the quasi-static regime $\gamma \ll 1$. The dynamics is then no longer dominated by the homogenized probability $\tilde{p}$. Instead of the condition $\tilde{p} \neq \frac{1}{2}$, we now assume that, in the limiting static case $\gamma = 0$, the walk is transient, say to the right (see the criterium (1.9) below, as well as Chapter 2.1 in [24]). Under this hypothesis, when $\gamma = 0$, it is known that $X_t$ behaves as $t^\delta$ as $t \to \infty$ for some $0 < \delta \le 1$. The sub-ballistic behavior corresponding to cases where $\delta < 1$ appears when $\rho^{1-\frac{\alpha}{\alpha}} + (1-\rho)^{1-\frac{\beta}{\beta}} > 1$ and is due to the fluctuations of the environment (see [18] for precise results on this regime). Let us now take $\gamma > 0$. The environment does not evolve significantly over a time $t = \tau\gamma^{-1}$ for some small $\tau > 0$. Therefore, taking $\gamma$ small enough, the walker will move to the right by an amount of order $t^\delta$ if started in a typical environment with respect to the Gibbs measure. Thus, as long as the walk evolves in such configurations of the environment, it drifts to the right. Nevertheless, when entering a region where the
density of particles is anomalous, its progression may be greatly slowed. However, since
$\gamma$ is positive, we may just reuse the argument developed for large $\gamma$ and show that traps
are irrelevant: large traps (of size $l$) disappear on much shorter time scales ($\gamma^{-1}l^2$) than
the time needed for the walker to see a next trap of that size (a time at least of order $l^K$
for some $K \gg 1$, see Section 4). We conclude that the walker has a positive velocity to
the right, as stated in Theorem 1.2. Again, we show also that fluctuations are normal.

From these two results, we conclude that the value of the limiting velocity $v(\gamma)$ may
change drastically between the large and small $\gamma$ regimes. Indeed, for some values $\rho, \alpha$
and $\beta$, the walk is transient to the right in a static environment while the homogenized
drift $2\tilde{p} - 1$ is negative (take e.g. $\rho = 9/10$, $\alpha = 1/4$ and $\beta = 1 - \epsilon$ with $\epsilon$ small enough in
(1.9) and (1.8) below). In this case, the asymptotic velocity in a static environment is
necessarily zero (Jensen's inequality implies $\rho \frac{1-\alpha}{\alpha} + (1-\rho) \frac{1-\beta}{\beta} > 1$). Therefore, it holds
that $v(0) = 0$, $v(\gamma) > 0$ for small enough $\gamma > 0$, and $v(\gamma) < 0$ for large enough $\gamma$.

We did not show that $v(\gamma)$ converges to $v(0)$ as $\gamma$ goes to 0, nor to $2\tilde{p} - 1$ as $\gamma$ goes to $\infty$, but we expect both of these limits to hold. While the latter could be shown using the techniques of the present article, at the cost of slightly more involved estimates (control on both excess and shortage of particles), some more work should be needed to check the continuity at 0.

Theorems 1.1 and 1.2 are shown in essentially the same way. In a first step, by means
of a multi-scale analysis, we show recursively that the walker can pass larger and larger
traps, allowing for a set of initial environments of larger and larger measure. The intro-
duction of renormalization techniques to study random walks in random environments
goes back to [8] and [10], from where our strategy is inspired. A similar method is used
in [16] (see also [12] and [14] for a slightly different approach). From this first step, one
concludes that the walker drifts almost surely to the left or to the right.

The law of large numbers and the invariance principle are deduced in a second step.
As the environment evolves only on diffusive time scales, a ballistic walker discovers fresh
randomness most of the time. From this observation, it is possible to build up a renewal
structure, allowing to cut the full trajectory into pieces that are mutually independent.
This idea was first introduced in [23] for the case of a static i.i.d. environment, and further
adapted by [11] to deal with the case of static environments with good mixing properties.
It was exploited in [3] to obtain a law of large numbers for dynamic environments with
good mixing rates, and then in [4, 9, 16] for a one-dimensional diffusive environment.
As this method is rather delicate and model dependent, we had to perform specific
constructions and estimates (see Section 5).

Let us now discuss some existing works that are directly related to our results. A
rather comprehensive study of the model studied here was initiated in [5], where several
conjectures, based on numerical computations and some heuristics, were presented.
Our Theorem 1.2 answers negatively one of the "key open questions" asked in (3.8)
in [5] (for $\beta = 1 - \alpha$ and $\rho \neq 1/2$, the velocity of the walker is non-zero for all $\gamma > 0$
small enough). Moreover, two dimensional analogs of our model have been studied in
the physics literature. In [6], the differential mobility of a tagged particle driven by an
external field is shown, by means of numerical computations, to undergo a transition
from a quasi-static to a fluid regime as $\gamma$ is increased. These two regimes are somehow
analogous to the ones described by our Theorem 1.2 and Theorem 1.1 respectively. In
addition, the same model was studied in [7] as a way to probe the glassy transition in
liquids, and the possibility of anomalous fluctuations was alluded. Our results suggest
that no anomalous fluctuation should be observed.

Finally, in a recent work [16], a law of large numbers and an invariance principle for
the fluctuations of a walker were obtained in a set-up close to ours. The authors consider
indeed a random walk driven by a set of non-interacting particles at equilibrium with
density $0 < \rho < +\infty$. The transition probability of the walker differs if he sits on a vacant site or on a site occupied by at least one particle. Their results hold then for all $\rho$ large enough, assuming that the limiting velocity is non-zero in the limiting case "$\rho = \infty$". This is thus a situation analogous to the one described by our Theorem 1.1, which proof is moreover based on a similar architecture as their. Nevertheless, we stress that, even for Theorem 1.1, we developed our strategy independently, and that a closer look at the details shows that many steps cannot be simply taken over.

## 1.1 Model

An environment is a function $(\omega(t, x))_{t \ge 0, x \in \mathbb{Z}}$ with values in the interval $[0, 1]$; we refer to $t \in \mathbb{R}_+$ as the (continuous) time, and to $x \in \mathbb{Z}$ as the position. Given such a function $\omega$ we define, for any space-time point $(n, x) \in \mathbb{N} \times \mathbb{Z}$, the Markovian (discrete time) law $P_{n,x}^{\omega}$ by

$$P_{n,x}^{\omega}(X_0 = x) = 1 \text{ and, for all } k \ge 0 \text{ and } z \in \mathbb{Z}, \qquad (1.1)$$

$$P_{n,x}^{\omega}(X_{k+1} = z + 1 | X_k = z) = \omega(n + k, z), \qquad (1.2)$$

$$P_{n,x}^{\omega}(X_{k+1} = z - 1 | X_k = z) = 1 - \omega(n + k, z). \qquad (1.3)$$

Given the discrete time process $(X_n)_{n \in \mathbb{N}}$, we also define, with a slight abuse of notation, the continuous time process $(X_t)_{t \ge 0} := (X_{[t]})_{t \ge 0}$ with $t \in \mathbb{R}_+$.

Consider the simple exclusion process on $\mathbb{Z}$,

$$(\eta(t))_{t \ge 0} = (\eta_x(t))_{t \ge 0, x \in \mathbb{Z}} \in \{0, 1\}^{\mathbb{Z}},$$

defined by its generator

$$\mathcal{L}f = \gamma \sum_{x \in \mathbb{Z}} (f \circ \sigma_{x,x+1} - f), \qquad (1.4)$$

where $\gamma > 0$ is the jump rate of the particles (the intensity of the process), and where $\sigma_{x,y}$ is defined for any $x, y \in \mathbb{Z}$ by

$$\sigma_{x,y}(\eta) = (\dots, \eta_y, \dots, \eta_x, \dots) \quad \text{if} \quad \eta = (\dots, \eta_x, \dots, \eta_y, \dots).$$

If $\eta_x(t) = 1$, the site $x$ is said to be occupied by a particle at time $t$, while it is said to be vacant if $\eta_x(t) = 0$. For any $0 \le \rho \le 1$, the probability measure $\pi_{\rho} = (\rho\delta_1 + (1-\rho)\delta_0)^{\otimes\mathbb{Z}}$ is invariant for the simple exclusion process. Remark that for any $x$, $\pi_{\rho}(\eta_x = 1) = \rho$. We denote by $\mathbb{P}_{\rho}$ the law of the process with initial condition distributed according to $\pi_{\rho}$.

Let $0 \le \alpha, \beta \le 1$. Given a realization of $\eta$ we define an environment $\omega$ as a function of $\eta$ by

$$\omega(\eta)(t, x) = \begin{cases} \alpha & \text{if } \eta_x(t) = 1, \\ \beta & \text{if } \eta_x(t) = 0. \end{cases} \qquad (1.5)$$

We define $\mathbb{P}$, a law on the space of environments, as the push-forward of $\mathbb{P}_{\rho}$ through this function. To fix the ideas, we will from now on assume that the drift corresponding to empty sites is larger than the drift corresponding to occupied sites:

$$0 \le \alpha < \beta \le 1.$$

We define for any space-time point $(n, x) \in \mathbb{N} \times \mathbb{Z}$ the annealed law by

$$P_{n,x} = \mathbb{P} \times P_{n,x}^{\omega}. \qquad (1.6)$$

Remark that the law of $(X_k - x)_{k \ge 0}$ under $P_{n,x}$ is the same as the law of $(X_k)_{k \ge 0}$ under $P_{0,0}$, that we will often denote simply by $P_0$.
## 1.2 Results

We assume that the environment is elliptic:

$$0 < \alpha, \beta < 1. \qquad (1.7)$$

For our first result, we assume that the walker would drift to the right if, at each of his step, the environment would be entirely refreshed according to the equilibrium measure (the limiting case "$\gamma = \infty$"). We assume thus that $\rho, \alpha$ and $\beta$ are such that

$$E_0(X_1) = \mathbb{E}(2\omega - 1) = \rho(2\alpha - 1) + (1 - \rho)(2\beta - 1) > 0, \qquad (1.8)$$

where $E_0$ is the expectation with respect to $P_0$ and $\mathbb{E}$ the expectation with respect to $\mathbb{P}$. We show that the drift to the right will still be observed if, instead of refreshing the environment at each step of the walker, it evolves according to the dynamics generated by (1.4) with initial condition distributed as $P_\rho$, provided that $\gamma$ is taken large enough once the parameters $\rho, \alpha$ and $\beta$ have been fixed. The following theorem may therefore be seen as a perturbative result around the trivial case "$\gamma = \infty$":

**Theorem 1.1.** Assume that the ellipticity condition (1.7) and the drift condition (1.8) hold. There exists $v_* > 0$ so that, for $\gamma$ large enough,

1. there exists $v(\gamma) \ge v_*$ so that

$$\lim_{t \to \infty} \frac{X_t}{t} = v(\gamma) \quad P_0 - \text{a.s.},$$

2. the annealed central limit theorem holds: under $P_0$

$$\left( \frac{X_{nt} - ntv(\gamma)}{\sqrt{n}} \right)_{t \ge 0} \implies (B_t)_{t \ge 0},$$

where $(B_t)_{t \ge 0}$ is a non-degenerate Brownian motion, and where the convergence in law is in the Skorohod topology.

For our second result, we assume that the walker is transient to the right in a static environment ($\gamma = 0$), i.e. that the parameters $\rho, \alpha$ and $\beta$ are such that

$$\mathbb{E} \left( \ln \frac{1-\omega}{\omega} \right) = \rho \ln \frac{1-\alpha}{\alpha} + (1-\rho) \ln \frac{1-\beta}{\beta} < 0. \qquad (1.9)$$

For background about static random walks in random environments, see e.g. [24]. We show that, for strictly positive and small enough $\gamma$, the walker has a positive velocity:

**Theorem 1.2.** Assume that the ellipticity condition (1.7), as well as the condition (1.9) for transience to the right in a static environment, hold. Then, for $\gamma > 0$ small enough,

1. there exists $v(\gamma) > 0$ such that

$$\lim_{t \to \infty} \frac{X_t}{t} = v(\gamma) \quad P_0 - \text{a.s.},$$

2. the annealed central limit theorem holds: under $P_0$

$$\left( \frac{X_{nt} - ntv(\gamma)}{\sqrt{n}} \right)_{t \ge 0} \implies (B_t)_{t \ge 0},$$

where $(B_t)_{t \ge 0}$ is a non-degenerate Brownian motion, and where the convergence in law is in the Skorohod topology.

We stress that in the case where (1.8) holds while the left hand side of (1.9) is strictly positive, the asymptotic velocity of the walker can be either positive or negative according to the value of $\gamma$. We can thus exclude that any of our two theorems can be valid as such for all strictly positive $\gamma$.
## 1.3 Outline of the paper

The rest of the article is organized in four sections. In Section 2, we control the time of dissipation of zones with high density of particles. In Section 3, we use these results on the environment together with a renormalization procedure to derive that, if the assumption (1.8) holds and if $\gamma$ is large enough, the walk is ballistic to the right. In Section 4, the same ideas are used to prove that the walk is ballistic to the right if the assumption (1.9) holds and if $\gamma > 0$ is small enough. Finally, in Section 5, we build a renewal structure to show that the bounds obtained in Sections 3 and 4 imply the law of large numbers and the annealed invariance principle stated in Theorems 1.1 and 1.2.

# 2 Dissipation of traps

The walker can be slowed in the places where the concentration of particles is too high with respect to the expected density $\rho$. These locally anomalous configurations of the environment are called traps. Here we make precise the idea that traps disappear on diffusive time scales. Concretely, we establish that, if in a box of size $L$ around a point $x$, the density of particles is very close to the density $\rho$ for a given initial profile $\eta \in \{0, 1\}^Z$, then, waiting a time bigger than $L^2$, the density in smaller boxes around $x$ becomes close to $\rho$ as well, with high probability with respect to the evolution of the process. The section is divided into three parts: we first state our results, then show some technical lemmas, and finally give the proof of our propositions. The technical estimates in Section 2.2 are very close to some results obtained in [14] (see Lemma 5.3 there).

Before starting, let us introduce an extra notation, to be in use mainly in Sections 2-4. For $\eta \in \{0, 1\}^Z$, we define the law $P^\eta$ of the simple exclusion process, defined by (1.4), for the deterministic initial condition $\eta$. We define then

$$P^{\eta} = P^{\eta} \times P_{0,0}^{\omega}, \qquad (2.1)$$

where $\omega$ is the environment built from $(\eta(t, x))_{t \ge 0, x \in \mathbb{Z}}$ (see (1.5)).

## 2.1 Statement of the results

Given $x \in \mathbb{Z}$, $L \in \mathbb{N}$ and $\eta \in \mathbb{N}^Z$, let

$$\langle \eta \rangle_{x,L} = \frac{1}{|B(x,L)|} \sum_{y \in B(x,L)} \eta_y \qquad (2.2)$$

be the empirical density of particles in a box of radius $L$ around the point $x$. In (2.2), we have used the notations

$$B(x, L) = [x - L, x + L] \cap \mathbb{Z} \quad \text{and} \quad |B(x, L)| = 2L + 1.$$

Let $(\epsilon_L)_{L \ge 0}$ be some decreasing sequence of numbers in $[0, 1]$. The numbers $\epsilon_L$ will serve to control the difference between the density $\rho$ and the empirical density in a box of size $L$. Given $\eta \in \{0, 1\}^Z$ and $L \in \mathbb{N}$, we define the set of good sites $G(\eta, L) \subset \mathbb{Z}$ as follows: we say that $x \in G(\eta, L)$ if

$$\langle \eta \rangle_{x,L'} \le (1 + \epsilon_L)\rho \quad \text{for all} \quad L' \ge L. \qquad (2.3)$$

The main result of this section is contained in the following proposition, where we use the assumption $\gamma t \ge L^3$ instead of the more natural assumption $\gamma t \ge CL^2$ for some large constant $C$, in order to avoid the introduction of too many constants.
**Proposition 2.1.** There exist some constants $C < +\infty$ and $c > 0$ such that, given an initial profile $\eta \in \{0, 1\}^Z$, and given $x \in \mathbb{Z}$, $t \ge 0$ and $J, L \in \mathbb{N}$, the conditions

$$x \in G(\eta, L), \quad \gamma t \ge L^3, \quad J \le L, \quad L(\epsilon_J - \epsilon_L) \ge C,$$

imply that

$$P^{\eta}(x \notin G(\eta(t), J)) \le C \frac{\exp(-cJ\rho^2(\epsilon_J - \epsilon_L)^2)}{\rho^2(\epsilon_J - \epsilon_L)^2}. \quad (2.4)$$

This proposition can only be applied if, given a profile $\eta$, one waits a time $\gamma t \ge L^3$. The next proposition furnishes a control that holds for short times too,

**Proposition 2.2.** There exist a constant $c > 0$ such that, given an initial profile $\eta \in \{0, 1\}^Z$, and given $\epsilon > 0$, $t \ge 0$, $x \in \mathbb{Z}$ and $L \in \mathbb{N}$, it holds that, if

$$y \in G(\eta, L) \quad \forall y \in B(x, L) \quad \text{and} \quad \epsilon \ge \epsilon_L,$$

then

$$P^{\eta}(\langle \eta(t) \rangle_{x,L} \ge (1+\epsilon)\rho) \le \exp(-cL\rho^2(\epsilon - \epsilon_L)^2).$$

One observes that $\gamma$ plays no role in Proposition 2.2.

## 2.2 Some lemmas: heat equation properties and concentration

We let

$$\bar{\eta}(t) = E^{\eta}(\eta(t)) \quad (2.5)$$

be the mean value of the field after a time $t$, starting from the initial field $\eta$, where we have used $E^{\eta}$ for the expectation with respect to $P^{\eta}$. The mean evolution $\bar{\eta}(t)$ solves the discrete heat equation $\partial_t \bar{\eta} = \gamma \Delta \bar{\eta}$ with initial condition $\bar{\eta}(0) = \eta$. The operator $\Delta$ appearing here is the discrete Laplacian defined by $\Delta u(x) = u(x+1) - 2u(x) + u(x-1)$ for $u: \mathbb{Z} \to \mathbb{R}$.

We find it convenient to introduce three closely related kernels. Let first $p: \mathbb{R}_+ \times \mathbb{Z} \to \mathbb{R}$ be the heat kernel associated to the Laplacian $\gamma \Delta$: $p$ solves the initial value problem

$$p(0, \cdot) = \delta_0(\cdot), \quad \partial_t p = \gamma \Delta p. \quad (2.6)$$

So, for $x \in \mathbb{Z}$ and $t \ge 0$, $p(t, x)$ represents the probability that a free particle jumping with rate $\gamma$ starting at origin sits on site $x$ at time $t$. Given $L \in \mathbb{N}$, let then $p_L$ and $p_L$ be given by

$$p_L(t, x) = \sum_{y \in B(0, L)} p(t, x+y) \quad \text{and} \quad p_L(t, x) = \frac{1}{|B(0, L)|} p_L(t, x) \quad (2.7)$$

for $(t, x) \in \mathbb{R}_+ \times \mathbb{Z}$. The quantity $p_L(t, x)$ represents the probability that a free particle starting from the origin lies in the box of size $L$ centered at $x$ at time $t$.

Our first lemma furnishes a concentration bound: with high probability, the empirical density of $\eta(t)$ in a box of size $L$ does not deviate too much from the empirical density of the mean evolution $\bar{\eta}(t)$ in the same box. This result does not depend on $\gamma$.

**Lemma 2.3.** There exists a constant $c > 0$ such that, given $\eta \in \{0, 1\}^Z$, $L \in \mathbb{N}$, $x \in \mathbb{Z}$, $t \ge 0$ and $a \ge 0$,

$$P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x,L} \ge a) \le e^{-ca^2L}.$$

*Proof.* Given $\delta \ge 0$, it follows from Markov's inequality that

$$P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x,L} \ge a) \le e^{-\delta a} \cdot e^{-\delta \langle \bar{\eta}(t) \rangle_{x,L}} \cdot E^{\eta}(e^{\delta \langle \eta(t) \rangle_{x,L}}). \quad (2.8)$$
Let us first give an expression for $\langle \bar{\eta}(t) \rangle_{x,L}$. For $x \in \mathbb{Z}$, $\bar{\eta}_x(t) = P^\eta(\eta_x(t) = 1)$. Note that $\{\eta_x(t) = 1\} = \bigcup_{z \in \mathbb{Z}, \eta_z = 1} A_z(t, x)$, where $A_z(t, x)$ is the event that a particle initially at $z$, sits at $x$ at time $t$. As these events are mutually disjoint due to the exclusion constraint, $\bar{\eta}_x(t) = \sum_{z \in \mathbb{Z}} p(t, x - z)\eta_z$, and we compute

$$ \begin{aligned} \langle \bar{\eta}(t) \rangle_{x,L} &= \frac{1}{2L+1} \sum_{y \in B(0,L)} \bar{\eta}_{x+y}(t) = \frac{1}{2L+1} \sum_{y \in B(0,L)} \sum_{z \in \mathbb{Z}} p(t, x+y-z)\eta_z \\ &= \sum_{z \in \mathbb{Z}} p_L(t, x-z)\eta_z, \end{aligned} \qquad (2.9) $$

as is seen from the definition (2.7) of $p_L$.

Let us then work out the third factor in (2.8). We will use Liggett's inequality to get rid of the exclusion constraint (see Proposition 1.7 p.366 in [19]). Let us define the process $\theta$ that represents the collective motion of independent particles evolving on $\mathbb{Z}$. So, let $\theta = (\theta(t))_{t \ge 0}$ be the process on $\mathbb{N}^\mathbb{Z}$ defined by the generator

$$ \bar{\mathcal{L}}f(\theta) = \sum_{x \in \mathbb{Z}} \theta_x (f(\theta^{x,x+1}) - 2f(\theta) + f(\theta^{x,x-1})), $$

with $\theta^{x,y} = (\dots, \theta_x - 1, \dots, \theta_y + 1, \dots)$ if $\theta = (\dots, \theta_x, \dots, \theta_y, \dots)$. We assume that $\theta(0) = \eta$. It is convenient to adopt the following interpretation: we say that there are $n \in \mathbb{N}$ particles at $x \in \mathbb{Z}$ at time $t \ge 0$ if and only if $\theta_x(t) = n$. Let us label all the particles, in an arbitrary way, by $k \in \mathbb{N}^*$. Let $X_k(t)$ be their position at time $t$. At any time $t \ge 0$, the variables $(X_k(t))_{k \ge 1}$ are independent.

While Liggett's inequality is stated for a finite number of particles, it is possible to use it here for the whole infinite system. Indeed, we can use it first for any truncated initial condition $\eta^N$, $N \ge 1$, where $\eta_i^N = 0$ if $|i| > N$ and $\eta_i^N = \eta_i$ if $|i| \le N$. We then couple these various initial conditions using the Harris graphical construction (see [15]), and finally use the monotone convergence theorem to extend Liggett's comparison inequality to the whole system starting from $\eta$ (see for example [1] for a similar generalization). Remembering the definition (2.7) of $p_L$, we get

$$ \begin{aligned} E^\eta \big( e^{\delta \langle \eta(t) \rangle_{x,L}} \big) \le E^\eta \big( e^{\delta \langle \theta(t) \rangle_{x,L}} \big) &= E^\eta \big( e^{\frac{\delta}{2L+1} \sum_{k \ge 1} \mathbf{1}_{B(x,L)}(X_k(t))} \big) = \prod_{k \ge 1} E^\eta \big( e^{\frac{\delta}{2L+1} \mathbf{1}_{B(x,L)}(X_k(t))} \big) \\ &= \prod_{k \ge 1} \bigg( e^{\frac{\delta}{2L+1}} \mathbf{p}_L(t, X_k(0) - x) + (1 - \mathbf{p}_L(t, X_k(0) - x)) \bigg)^{\eta_z} \\ &= \prod_{z \in \mathbb{Z}} \bigg( e^{\frac{\delta}{2L+1}} \mathbf{p}_L(t, z - x) + (1 - \mathbf{p}_L(t, z - x)) \bigg)^{\eta_z} \\ &\le \exp \bigg( \bigg( e^{\delta/(2L+1)} - 1 \bigg) \sum_{z \in \mathbb{Z}} \mathbf{p}_L(t, z - x) \eta_z \bigg) \\ &= \exp \bigg( \bigg( e^{\delta/(2L+1)} - 1 \bigg) (2L+1) \langle \bar{\eta}(t) \rangle_{x,L} \bigg), \end{aligned} \qquad (2.10) $$

where the last expression follows from (2.9).

Let us now come back to (2.8). Assuming that $\delta/(2L+1) \le 1$, we conclude, using (2.10) and expanding $e^{\delta/(2L+1)} - 1$ in first order in $\delta/(2L+1)$, that we can find a constant $C < +\infty$ such that

$$ e^{-\delta \langle \bar{\eta}(t) \rangle_{x,L}} \cdot E^\eta \big( e^{\delta \langle \eta(t) \rangle_{x,L}} \big) \le e^{\frac{C\delta^2}{2L+1} \langle \bar{\eta}(t) \rangle_{x,L}}. $$

Therefore

$$ P^\eta \big( \langle \eta(t) - \bar{\eta}(t) \rangle_{x,L} \ge a \big) \le e^{-a\delta + \frac{C\langle \bar{\eta}(t) \rangle_{x,L}}{2L+1} \delta^2} \quad \text{for} \quad 0 \le \delta \le 2L+1. $$
Random walk driven by the simple exclusion process

This inequality is optimized for $\delta = \min\{\frac{a(2L+1)}{2C\langle\bar{\eta}(t)\rangle_{x,L}}, 2L+1\}$. If $\delta = \frac{a(2L+1)}{2C\langle\bar{\eta}(t)\rangle_{x,L}}$, we find

$$P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x,L} \ge a) \le e^{-\frac{a^2(2L+1)}{4C\langle\bar{\eta}(t)\rangle_{x,L}}} \le e^{-\frac{a^2(2L+1)}{4C}}, \quad (2.11)$$

as $\langle\bar{\eta}(t)\rangle_{x,L} \le 1$ for the simple exclusion process. If instead $\delta = 2L+1$, we obtain

$$P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x,L} \ge a) \le e^{-a(2L+1)(1 - \frac{C\langle\bar{\eta}(t)\rangle_{x,L}}{a})}.$$

Because in this case $2L+1 \le \frac{a(2L+1)}{2C\langle\bar{\eta}(t)\rangle_{x,L}}$, this implies

$$P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x,L} \ge a) \le e^{-a(2L+1)/2}. \quad (2.12)$$

The Lemma is obvious for $a > 1$ and, for $a \le 1$, (2.11) is always larger than (2.12) as soon as $C \ge 1/2$. This gives the claim. $\square$

The next two lemmas furnish a control on the solution of the heat equation. The first of these makes precise the fact that, after a time $t$, the solution at $x$ is well approximated by the empirical density of the initial profile in a box of size $(\gamma t)^{1/2}$ around $x$.

**Lemma 2.4.** There exists a constant $C < +\infty$ such that, given $\eta \in \{0, 1\}^Z$, $M, L \in \mathbb{N}$, $x \in \mathbb{Z}$ and $t \ge 0$,

$$\langle \bar{\eta}(t) \rangle_{x,M} \le \left(1 + \frac{CL^2}{\gamma t}\right) \sup \{\langle \eta \rangle_{x,r} : r \ge L\}.$$

*Proof.* Let us start by quoting a property of the heat equation. Let $f: \mathbb{Z} \to \mathbb{R}$ be such that $f(x) = f(-x)$ for all $x \in \mathbb{Z}$, and such that, for all $x \ge 0$, it holds that $f(x) - f(x+1) \ge 0$. For $x \in \mathbb{Z}$ and $t \ge 0$, let also $f(t, x)$ be the solution of the initial value problem $f(0, x) = f(x)$ and $\partial_t f(t, x) = \gamma \Delta f(t, x)$. It is verified that, for all $t > 0$, we still have $f(t, x) = f(t, -x)$ for all $x \in \mathbb{Z}$, and $f(t, x) - f(t, x+1) \ge 0$ for all $x \ge 0$.

This has the following consequence. It is seen from the definition (2.7) of $p_M$ that $p_M(0, x) = p_M(0, -x)$ for all $x \in \mathbb{Z}$, that $p_M(0, x) - p_M(0, x+1) \ge 0$ for all $x \ge 0$, and that $p_M$ solves the heat equation $\partial_t p_M(t, x) = \gamma \Delta p_M(t, x)$ for $x \in \mathbb{Z}$ and $t \ge 0$. Therefore, for any function $u: \mathbb{Z} \to \mathbb{R}$, it holds that

$$\sum_{z \in \mathbb{Z}} p_M(t, z-x)u(z) = \sum_{z \ge 0} (p_M(t, z) - p_M(t, z+1))(2z+1)\langle u \rangle_{x,z}, \quad (2.13)$$

where $p_M(t, z) - p_M(t, z+1) \ge 0$ for all $z \ge 0$.

Let us now write for simplicity

$$R := \sup \{\langle \eta \rangle_{x,r} : r \ge L\}.$$

As shown in (2.9), it holds that $\langle\bar{\eta}(t)\rangle_{x,M} = \sum_{z \in \mathbb{Z}} p_M(t, z-x)\eta_z$, so that, using (2.13), we find

$$\langle \bar{\eta}(t) \rangle_{x,M} = \langle \bar{\eta}(t) \rangle_{x,M} - R + R = \sum_{z \ge 0} (p_M(t, z) - p_M(t, z+1))(2z+1)(\langle \eta \rangle_{x,z} - R) + R. \quad (2.14)$$

If $z \ge L$, then

$$\langle \eta \rangle_{x,z} - R = \langle \eta \rangle_{x,z} - \sup \{\langle \eta \rangle_{x,r} : r \ge L\} \le 0,$$

while, if $z < L$, then still

$$(2z+1)(\langle \eta \rangle_{x,z} - R) \le (2z+1)\langle \eta \rangle_{x,z} = \sum_{y \in \mathbb{B}(0,z)} \eta_{x+y} \le (2L+1)R.$$
We see that we already obtain the result if $L = 0$, so that we can further assume $L \ge 1$.
Inserting these two estimates in (2.14), we find

$$ \langle \bar{\eta}(t) \rangle_{x,L} \le (2L+1)R \sum_{z=0}^{L-1} (p_M(t,z)-p_M(t,z+1)) + R = \{1+(2L+1)(p_M(t,0)-p_M(t,L))\}R. \quad (2.15) $$

For any $z \in \mathbb{Z}$ and $t > 0$, expanding $p(t, z) = e^{\gamma \Delta^t} \delta_0(z)$ in the Fourier variables, and writing $\omega(\xi) = 2(1 - \cos \xi)$, we find

$$ |p(t, z) - p(t, z + 1)| = \left| \int_{-\pi}^{\pi} e^{-\omega(\xi)\gamma t} (e^{i\xi z} - e^{i\xi(z+1)}) \frac{d\xi}{2\pi} \right| \le C \int_{\mathbb{R}} e^{-c\xi^2\gamma t} |\xi| d\xi \le \frac{C'}{\gamma t}, $$

for some $c > 0$ and $C < C' < +\infty$. Therefore

$$ p_M(t, 0) - p_M(t, L) \le \frac{CL}{\gamma t}. $$

Inserting this estimate in (2.15) furnishes the claim. $\square$

Our last lemma gives a bound that does not require to wait a time $\gamma t \ge L^3$ to hold:
**Lemma 2.5.** Given $\eta \in \{0, 1\}^Z$, $x \in \mathbb{Z}$, $t \ge 0$ and $L \in \mathbb{N}$, it holds that

$$ \langle \bar{\eta}(t) \rangle_{x,L} \le \sup \{ \langle \eta \rangle_{y,r} : r \ge L, y \in \mathcal{B}(x, L) \}. $$

*Proof.* For $L = 0$, the lemma follows from Lemma 2.4. We assume $L \ge 1$. To simplify writings, let us write

$$ R := \sup \{ \langle \eta \rangle_{y,r} : r \ge L, y \in \mathcal{B}(x, L) \}. $$

We decompose

$$ p(t, \cdot) = \tilde{p}(t, \cdot) + \sum_{k \ge L} p_k(t, \cdot), $$

with

$$ p_k(t, \cdot) = (p(t, k) - p(t, k + 1)) \mathbb{I}_{\mathcal{B}(0, k)}(\cdot), \quad k \ge L, $$

and

$$ \tilde{p}(t, z) = p(t, z) - \sum_{k \ge L} p_k(t, z) \quad \text{if } z \in \mathcal{B}(0, L-1) \quad \text{and} \quad \tilde{p}(t, z) = 0 \quad \text{otherwise.} $$

Let $y \in \mathcal{B}(x, L)$. It holds that

$$ \bar{\eta}_y(t) = \sum_{z \in \mathbb{Z}} p(t, y-z)\eta_z = \sum_{z \in \mathbb{Z}} \tilde{p}(t, y-z)\eta_z + \sum_{k \ge L} \sum_{z \in \mathbb{Z}} p_k(t, y-z)\eta_z. $$

Since, for $k \ge L$,

$$ \sum_{z \in \mathbb{Z}} p_k(t, y-z)\eta_z = (p(t, k) - p(t, k+1)) \sum_{z \in \mathcal{B}(0, k)} \eta_{y+z} = (p(t, k) - p(t, k+1))(2k+1)\langle \eta \rangle_{y,k}, $$

and since we assume $y \in \mathcal{B}(x, L)$, our hypotheses imply $\langle \eta \rangle_{y,k} \le R$, so that

$$ \bar{\eta}_y(t) \le \sum_{z \in \mathcal{B}(0, L-1)} \tilde{p}(t, z)\eta_{z+y} + \sum_{k \ge L} (p(t, k) - p(t, k+1))(2k+1)R. $$

Therefore

$$ \begin{aligned} \langle \bar{\eta}(t) \rangle_{x,L} &= \frac{1}{|\mathcal{B}(x, L)|} \sum_{y \in \mathcal{B}(x, L)} \bar{\eta}_y(t) \\ &\le \sum_{z \in \mathcal{B}(0, L-1)} \tilde{p}(t, z) \frac{1}{|\mathcal{B}(x, L)|} \sum_{y \in \mathcal{B}(x, L)} \eta_{z+y} + \sum_{k \ge L} (p(t, k) - p(t, k+1))(2k+1)R. \end{aligned} $$
Random walk driven by the simple exclusion process

If $z \in B(0, L - 1)$, we have $x + z \in B(x, L)$, and so by hypothesis,

$$ \frac{1}{|B(x, L)|} \sum_{y \in B(x, L)} \eta_{z+y} = \frac{1}{|B(0, L)|} \sum_{w \in B(0, L)} \eta_{x+z+w} \le R. $$

We thus conclude that

$$ \langle \bar{\eta}(t) \rangle_{x,L} \le \left\{ \sum_{z \in B(0, L-1)} \tilde{p}(t, z) + \sum_{k \ge L} (p(t, k) - p(t, k+1))(2k+1) \right\} R = R, $$

which is the claim.

□

## 2.3 Proof of Propositions 2.1 and 2.2

*Proof of Proposition 2.1. We have*

$$ P^{\eta}(x \notin G(\eta(t), J)) \le \sum_{J' \ge J} P^{\eta}(\langle \eta(t) \rangle_{x, J'} > (1 + \epsilon_J)\rho). \quad (2.16) $$

By Lemma 2.4, and since by hypothesis $\gamma t \ge L^3$ and $x \in G(\eta, L)$, we find for all $J' \in \mathbb{N}$ that

$$ \langle \bar{\eta}(t) \rangle_{x, J'} \le (1 + C/L) \sup \{ \langle \eta \rangle_{x, r} : r \ge L \} \le (1 + C/L)(1 + \epsilon_L)\rho. $$

Therefore, thanks to the hypothesis that $L(\epsilon_J - \epsilon_L)$ is large enough, we get

$$ (1 + \epsilon_J)\rho - \langle \bar{\eta}(t) \rangle_{x, J'} \ge (\epsilon_J - \epsilon_L - 2C/L)\rho \ge \frac{\rho}{2}(\epsilon_J - \epsilon_L) \ge 0. \quad (2.17) $$

This last inequality allows us to use the concentration estimate stated in Lemma 2.3:

$$ \begin{aligned} P^{\eta}(\langle \eta(t) \rangle_{x, J'} \ge (1 + \epsilon_J)\rho) &= P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x, J'} \ge (1 + \epsilon_J)\rho - \langle \bar{\eta}(t) \rangle_{x, J'}) \\ &\le P^{\eta}(\langle \eta(t) - \bar{\eta}(t) \rangle_{x, J'} \ge \frac{\rho}{2}(\epsilon_J - \epsilon_L)) \\ &\le \exp(-cJ'\rho^2(\epsilon_J - \epsilon_L)^2), \end{aligned} \quad (2.18) $$

where we have used (2.17) to get the first inequality. Inserting (2.18) in (2.16), we obtain

$$ P^{\eta}(x \notin G(\eta(t), J)) \le \sum_{J' \ge J} e^{-cJ'\rho^2(\epsilon_J - \epsilon_L)^2} \le C \frac{e^{-cJ\rho^2(\epsilon_J - \epsilon_L)^2}}{\rho^2(\epsilon_J - \epsilon_L)^2}, $$

since $\rho^2(\epsilon_J - \epsilon_L)^2 \le 1$. This is the claim.

□

*Proof of Proposition 2.2. We write*

$$ P^{\eta}(\langle \eta(t) \rangle_{x, L} \ge (1 + \epsilon)\rho) = P^{\eta}(\langle \eta(t) \rangle_{x, L} - \langle \bar{\eta}(t) \rangle_{x, L} \ge (1 + \epsilon)\rho - \langle \bar{\eta}(t) \rangle_{x, L}). $$

It follows from the hypotheses and from Lemma 2.5 that

$$ (1 + \epsilon)\rho - \langle \bar{\eta}(t) \rangle_{x, L} \ge (1 + \epsilon)\rho - (1 + \epsilon_L)\rho = (\epsilon - \epsilon_L)\rho, $$

so that, by Lemma 2.3, we find indeed $P^{\eta}(\langle \eta(t) \rangle_{x, L} \ge (1+\epsilon)\rho) \le \exp(-cL\rho^2(\epsilon-\epsilon_L)^2)$. □
### 3 Drift for large $\gamma$

We here prove

**Theorem 3.1.** Assume that the drift condition (1.8) holds. Then, there exists $v_* > 0$ so that, for $\gamma$ large enough, there exists $v(\gamma) \ge v_*$ so that

$$ \liminf_{t \to \infty} \frac{X_t}{t} = v(\gamma) \quad P_0 - a.s. $$

Remark that the ellipticity condition (1.7) is not required.

Before we proceed to prove Theorem 3.1, let us fix some parameters. First, for the whole section, we assume that $\alpha, \beta$ and $\rho$ are chosen so that the drift condition (1.8) holds. Next, from now on, we assume that the sequence $(\epsilon_L)_{L \ge 0}$ introduced in Section 2 to control the excess of density in boxes of size $L$, is given by

$$ \epsilon_L = \frac{1}{1 + \ln(L + 1)} \quad \text{for} \quad L \in \mathbb{N}. \qquad (3.1) $$

With this choice, the sequence $(\epsilon_L)_{L \ge 0}$ satisfies two useful requirements: First, in view of the definition (2.3) of good sites, $\epsilon_L \gg L^{-1/2}$ is needed for a given site to be good with high probability for large $L$; this is the case with (3.1), and the probability that $x \notin G(\eta, L)$ decays faster with $L$ than $e^{-c_\tau L^\tau}$ for any $\tau < 1$. Second, we will apply Proposition 2.1 with $J$ and $L$ going together to infinity, in the ratio $L \sim J^2$. The bound (2.4) in Proposition 2.1 is only meaningful for $(\epsilon_J - \epsilon_L)^2 \gg J^{-1}$; again $(\epsilon_L)_{L \ge 0}$ defined by (3.1) satisfies this condition, and the bound (2.4) becomes $O(e^{-c_\tau J^\tau})$ for any $\tau < 1$.

Finally, we define a sequence $(\phi_L)_{L \ge 0}$, where $\phi_L$ will represent the size of the traps in a box of size $L$. Intuitively, typical regions of anomalous density in a box of size $L$ are of size $\ln L$. Nevertheless, for our estimates, we found it convenient to overestimate their size; we set

$$ \phi_L = L^{1/100} \quad \text{for} \quad L \in \mathbb{N}. \qquad (3.2) $$

In the sequel, we will tacitly use the bound $|X_t - X_s| \le t - s$, valid for all $0 \le s \le t$.

### 3.1 Outline of the proof

The proof of Theorem 3.1 is divided into three steps.

First, we show that, given any (arbitrarily large) time $T$, there exists $\gamma$ large enough so that the walker drifts to the right, for a large set of initial conditions on the environment. This is the content of Lemma 3.2 below. This is an easy result as we first fix $T$, and then chose $\gamma$ large enough so that the law of $X_T$ is well approximated by the law of a walk in a homogeneous environment, with drift given by (1.8).

Second, we keep $\gamma$ fixed, and we use a renormalization procedure to extend the previous result to arbitrarily long times $t$, and for a set of initial conditions which probability converges quickly to 1 as $t \to \infty$. This is done in Proposition 3.3 below, at the cost of reducing slightly our lower bound on the drift (v in (3.3) becomes $v/2$ in (3.13)). Our scheme is eventually inspired by a method developed in [8] (see also [10] for a dynamical uniformly mixing environment), though our problem requires much less involved estimates. As we cannot go at once to arbitrarily long times, let us first consider the special case $t = T'$ with $T' = T(T+1) \sim T^2$, as will be done in the proof of Proposition 3.3 (the choice $T' \sim T^2$ is arbitrary to a large extend). Once this will be understood, the procedure will just be iterated to reach all times $T^{2k}$ for any $k \ge 1$ (it is then not hard to see that all intermediate times can be reached as well).

Over a time $T'$, the walker will evolve in the ball $B(0, T')$ if it starts initially at the origin. Therefore, up to a small extra boundary of size $\sqrt{T'}$, we need to control the initial environment in $B(0, T')$. In the box $B(0, T')$, we allow for an initial environment $\eta$ such
that all traps are of size no larger than $\phi_{T'}$ (see (3.2)), i.e. such that $B(0, T') \subset G(\eta, \phi_{T'})$ (see (2.3)). Incidentally, we notice that we already achieved one of our goals: the measure of the set of initial configurations that we need to exclude when we observe the walker over a time $T'$, is smaller than it was over a time $T$ (this set was the set of $\eta$ such that $B(0, T) \not\subset G(\eta, \phi_{T'})$, see Lemma 3.2 below).

We then decompose $X_{T'}$ as $X_{T'} = \sum_{k=1}^{T} (X_{kT} - X_{(k-1)T})$ (see Figure 2 with $t_n = r = T$ and $t_{n+1} = T'$). We would like to use our knowledge on the behavior of the walk over a time $T$ to control the behavior of each increment $X_{kT} - X_{(k-1)T}$. This is not possible for the first term $X_T - X_0$ though, since we only know that $B(0, T') \subset G(\eta, \phi_{T'})$, while we would need $B(0, T) \subset G(\eta, \phi_{T'})$ (see Lemma 3.2 below); therefore, we just use the trivial bound $X_T - X_0 \ge -T$ (this is still fine since $T \ll T'$). However, with high probability with respect to the evolution of the environment, all points $y \in B(0, T)$ are such that $y \in G(\eta_{kT}, \phi_T)$ for all $1 \le k \le T - 1$, so that we do have a good control on all the steps $X_{kT} - X_{(k-1)T}$ with $2 \le k \le T$. This is actually the main point of the argument; it is a consequence of the relaxation of traps as expressed by Proposition 2.1 and of the choice of suitable sequence $(\epsilon_L)_{L \ge 1}$ (see the comments after (3.1)). Thanks to the quantitative estimate (3.3) in Lemma 3.2 below, we deduce then a lower bound on the drift of $X_{T'}$ by reducing a bit the bound $v$ in (3.3) (see (3.15)). The iteration of this procedure to larger scales is straightforward.

Finally, Theorem 3.1 is established thanks to a Borel-Cantelli type of argument.

## 3.2 Initial step

In the next Lemma, $T$ is both a time and spatial scale; the condition $\gamma \ge \phi_T^3$ and the bound (3.3) turn out to be convenient but are not optimal.

**Lemma 3.2.** Let $T \in \mathbb{N}$ be large enough, and let $\gamma \ge \phi_T^3$. There exists a constant $v > 0$ (that depends only on $\alpha, \beta$ and $\rho$) such that, given $\eta \in \{0, 1\}^\mathbb{Z}$ such that

$$ \forall y \in B(0, T), \quad y \in G(\eta, \phi_T), $$

it holds that

$$ P^{\eta}(X_T \le vT) \le e^{-\phi_T^{1/4}}. \quad (3.3) $$

*Proof.* Letting $v > 0$ be a constant that we will determine later, we first write

$$ P^{\eta}(X_T \le vT) \le P^{\eta}(X_T - X_1 \le vT + 1), \quad (3.4) $$

as the hypotheses do not allow to determine whether the site 0 is initially occupied or not.

Let us define a few objects. Since we assume $\alpha \le \beta$, there exists $\delta > 0$ small enough so that (1.8) will still be satisfied with any $\rho' \in [0, \rho + \delta]$ instead of $\rho$. Let $\delta > 0$ be such that this holds. Up to an enlargement of the probability space we define a sequence of i.i.d. random variables $(Y_k)_{k \ge 1}$ that are independent from both the exclusion process and the walker with distribution

$$ P^{\eta}(Y_k = 1) = \beta + (\alpha - \beta)(\rho + \delta), \quad P^{\eta}(Y_k = -1) = 1 - P^{\eta}(Y_k = 1). \quad (3.5) $$

Thanks to (1.8) and our choice of $\delta$, it holds that $P^{\eta}(Y_k = 1) > 1/2$. For $m \ge 2$, we define the events

$$ \mathcal{E}_{m-1} = \{y \in G(\eta(m-1), J), \forall y \in B(0, m)\} \quad \text{with} \quad J = [\phi_T^{1/2}], \quad (3.6) $$

and $\mathcal{E}_0 = \{y \in G(\eta(0), \phi_T), \forall y \in B(0, 1)\}$. By hypothesis, $P^{\eta}(\mathcal{E}_0) = 1$.
We aim to show that

$$P^{\eta}(X_T - X_1 \le \nu T + 1) \le P^{\eta}\left(\sum_{k=1}^{T-1} Y_k \le \nu T + 1\right) + \sum_{k=1}^{T-1} P^{\eta}(\mathcal{E}_{k-1}^c). \quad (3.7)$$

Before deriving this expression, let us see that it implies the lemma for v small enough depending on the values of $\alpha, \beta$ and $\rho$. Indeed for such a v, by (3.5), the first term in the right hand side of (3.7) is seen to be bounded as

$$P^{\eta}\left(\sum_{k=1}^{T-1} Y_k \le \nu T + 1\right) \le e^{-cT} \quad (3.8)$$

for some constant $c > 0$. The second term in the right hand side of (3.7) is then bounded by means of Proposition 2.1. Since $T$ is assumed to be large enough, and since $\gamma \ge \phi_T^3$, we deduce that

$$\sum_{k=1}^{T-1} P^{\eta}(\mathcal{E}_{k-1}^c) \le \sum_{\substack{y \in B(0,T), \\ s \in \{1, \dots, T-2\}}} P^{\eta}(y \notin G(\eta(s), J)) \le C \sum_{y,s} \frac{\exp(-cJ\rho^2(\epsilon_J - \epsilon_{\phi_T})^2)}{\rho^2(\epsilon_J - \epsilon_{\phi_T})^2} \\ \le C T^2 \frac{\exp(-cJ\rho^2(\epsilon_J - \epsilon_{\phi_T})^2)}{\rho^2(\epsilon_J - \epsilon_{\phi_T})^2} \le e^{-\phi_T^{1/3}}, \quad (3.9)$$

where, to get the last inequality, we have used the explicit expressions (3.1) and (3.2) and (3.6), as well as the fact that $T$ is large enough. We obtain the lemma by inserting the bounds (3.8) and (3.9) in (3.7), and then (3.7) in (3.4).

We are thus left with the proof of (3.7). For this, we show that, for any $m \ge 1$ and any $a \in \mathbb{R}$,

$$P^{\eta}(X_{1+m} - X_1 \le a) \le P^{\eta}(X_{1+(m-1)} + Y_m - X_1 \le a) + P^{\eta}(\mathcal{E}_{m-1}^c), \quad (3.10)$$

from which (3.7) follows by iteration using Fubini.

Let us first deal with the case $m = 1$. We need to show that $P^{\eta}(X_2 - X_1 \le a) \le P^{\eta}(Y_1 \le a)$, but for this it is enough to establish that $P^{\eta}(X_2 - X_1 = -1) \le P^{\eta}(Y_1 = -1)$. It holds that

$$\begin{aligned} P^{\eta}(X_2 - X_1 = -1) &= \sum_{z \in \mathbb{Z}} \sum_{\sigma=0,1} P^{\eta}(X_2 - X_1 = -1 | X_1 = z, \eta_z(1) = \sigma) P^{\eta}(X_1 = z, \eta_z(1) = \sigma) \\ &= \sum_{z \in \mathbb{Z}} P^{\eta}(X_1 = z) \sum_{\sigma=0,1} P^{\eta}(X_2 - X_1 = -1 | X_1 = z, \eta_z(1) = \sigma) P^{\eta}(\eta_z(1) = \sigma) \\ &= \sum_{z \in \mathbb{B}(0,1)} P^{\eta}(X_1 = z) (1 - \beta + (\beta - \alpha)P^{\eta}(\eta_z(1) = 1)). \end{aligned}$$

Since, by (3.5), we have $P^{\eta}(Y_1 = -1) = 1 - \beta + (\beta - \alpha)(\rho + \delta)$, we will conclude by showing that $P^{\eta}(\eta_z(1) = 1) \le \rho + \delta$ for any $z \in \mathbb{B}(0, 1)$. Let $z \in \mathbb{B}(0, 1)$. It holds that

$$P^{\eta}(\eta_z(1) = 1) = \sum_{w \in \mathbb{Z}} \eta_w p(1, w-z) = \bar{\eta}_z(1), \quad (3.11)$$

with $\bar{\eta}(t)$ defined in (2.5). We can use Lemma 2.4, with $M = 0$, $L = \phi_T$, $t = 1$ and $x = z$, to estimate the right hand side of (3.11). Since $\gamma \ge \phi_T^3$ and $z \in G(\eta, \phi_T)$ by hypothesis, we conclude that if $T$ is large enough,

$$P^{\eta}(\eta_z(1) = 1) \le \left(1 + \frac{C\phi_T^2}{\gamma}\right) \sup\{\langle\eta\rangle_{z,r} : r \ge \phi_T\} \le \left(1 + \frac{C\phi_T^2}{\phi_T^3}\right) (1 + \epsilon_{\phi_T})\rho < \rho + \delta. \quad (3.12)$$
Let us next consider the case $m > 1$ in (3.10):

$$ 
\begin{aligned}
P^{\eta}(X_{1+m} - X_1 \le a) &= P^{\eta}(X_{1+m} - X_m + X_m - X_1 \le a) \\
&\le P^{\eta}(\mathcal{E}_{m-1}^c) + \sum_{z_1, z_m \in \mathbb{Z}} P^{\eta}(X_{1+m} - X_m \le a - (z_m - z_1) | X_1 = z_1, X_m = z_m, \mathcal{E}_{m-1}) P^{\eta}(X_1 = z_1, X_m = z_m, \mathcal{E}_{m-1}).
\end{aligned}
$$

For each term of the sum, we proceed with the first factor exactly as for $m = 1$. Replacing $L = \phi_T$ by $L = J$ in (3.12), we find

$$ P^{\eta}(X_{1+m} - X_m \le a - (z_m - z_1) | X_1 = z_1, X_m = z_m, \mathcal{E}_{m-1}) \le P^{\eta}(Y_m \le a - (z_m - z_1)). $$

Altogether, we obtain

$$ 
\begin{aligned}
P^{\eta}(X_{1+m} - X_1 \le a) &\le \sum_{z_1, z_m \in \mathbb{Z}} P^{\eta}(Y_m \le a - (z_m - z_1)) P^{\eta}(X_1 = z_1, X_m = z_m) + P^{\eta}(\mathcal{E}_{m-1}^c) \\
&= P^{\eta}(X_{1+(m-1)} + Y_m - X_1 \le a) + P^{\eta}(\mathcal{E}_{m-1}^c),
\end{aligned}
$$

as desired.

□

### 3.3 Renormalization procedure

Let $v$ be as in Lemma 3.2.

**Proposition 3.3.** Let $T$ be large enough and let $\gamma \ge \phi_T^3$. Given $\eta \in \{0, 1\}^Z$ and $t \ge T$ such that

$$ \forall y \in B(0, t), \quad y \in G(\eta, \phi_t), $$

it holds that

$$ P^{\eta}\left(X_t \le \frac{v}{2}t\right) \le e^{-\phi_t^{1/4}}. \qquad (3.13) $$

*Proof of Proposition 3.3.* The main construction of the proof is illustrated on Figure 2. We consider $T$ large enough so that the conclusions of Lemma 3.2 hold for the time $T^{1/3}$. We then define a sequence $(t_n)_{n \ge 0}$ with $t_0 \in [T^{1/3}, T]$ and

$$ \text{for } n \ge 0, \quad t_{n+1} \in [t_n^2, (t_n+1)^2] \qquad (3.14) $$

such that for some $N \ge 0$, $t_N = t$ (for example define recursively, from $t_N = t$ with some suitable $N$, $t_{k-1} = \lfloor \sqrt{t_k} \rfloor$ until reaching the interval $[T^{1/3}, T]$). We define also a sequence $(c_n)_{n \ge 0} \subset \mathbb{R}_+$ by

$$ v \ge c_n = \left(3 - \sum_{k=0}^{n} \frac{1}{2^k}\right) \frac{v}{2} \ge \frac{v}{2} \quad (n \ge 0). \qquad (3.15) $$

We prove by recurrence on $n \ge 0$ that, given $\eta \in \{0, 1\}^Z$ and $n \ge n_0$, if, for any $y \in B(0, t_n)$, it holds that $y \in G(\eta, \phi_{t_n})$, then

$$ P^{\eta}(X_{t_n} \le c_n t_n) \le e^{-\phi_{t_n}^{1/4}}. \qquad (3.16) $$

This will imply the claim.

By Lemma 3.2 and the hypotheses, (3.16) holds true for $n = 0$ since $\gamma \ge \phi_T^3$. We now assume that (3.16) holds for some $n \ge 0$, and we show that it implies it for $n + 1$. We follow the same steps as in the proof of Lemma 3.2. To simplify notations, let us write $t_n = t$ and $t_{n+1} = t'$, as well as $c_n = c$ and $c_{n+1} = c'$. As in Lemma 3.2, we first need to wait an initial step, as the information on the initial environment does not allow us to use our inductive hypothesis. It follows from the definition (3.14) of $(t_n)_{n \ge 1}$ that $t' = r + (t-1)t$ for some $t \le r < 4t$. We write

$$ P^{\eta}(X_{t'} \le c't') \le P^{\eta}(X_{t'} - X_r \le c't' + r). \qquad (3.17) $$
<figure><img src="image_4.png" /><figcaption>Figure 2: Renormalization procedure used in the proof of Proposition 3.3. Up to time $r$, we assume the worst case scenario ($X_r = -r$) since we lack a good control on the initial environment. With high probability, it is then possible to apply $t_n$ times our inductive hypothesis, providing a lower bound for the drift of the walker. In the rare cases (4$^{th}$ and 11$^{th}$ space-time blocks from below on the figure) where $X_{kt_n} - X_{(k-1)t_n} < c_n t_n$, we assume again the worst case scenario.</figcaption></figure>

If $n_0$ is large enough, waiting this time $r$ will suffice to dissipate possible traps with high probability.

As in the proof of Lemma 3.2 we define on the same probability space (enlarged if necessary) a sequence $(Y_k)_{k \ge 1}$ of i.i.d. random variables independent from both the exclusion process and the walker with distribution

$$P^{\eta}(Y_k = \text{ct}) = 1 - e^{-\phi_t^{1/4}}, \quad P^{\eta}(Y_k = -\text{t}) = e^{-\phi_t^{1/4}}.$$

Using our inductive hypothesis, we aim to show that

$$P^{\eta}(X_{t'} - X_r \le c't' + r) \le P^{\eta}\left(\sum_{k=1}^{t-1} Y_k \le c't' + r\right) + \sum_{\substack{y \in B(0,t'), \\ r \le s \le t'}} P^{\eta}(y \notin G(\eta(s), \phi_t)). \quad (3.18)$$

To see this, we show that, for any $m \ge 1$ and any $a \in \mathbb{R}$, we have

$$P^{\eta}(X_{r+mt} - X_r \le a) \le P^{\eta}(X_{r+(m-1)t} + Y_m - X_r \le a) + P^{\eta}(\mathcal{E}_{m-1}^c) \quad (3.19)$$

where

$$\mathcal{E}_{m-1} = \{\forall y \in B(0, r+mt), y \in G(\eta(r+(m-1)t), \phi_t)\}.$$

Since $t' = r + (t - 1)t$, (3.18) follows from (3.19) by iteration.

We prove now (3.19). For any $m \ge 1$,

$$P^{\eta}(X_{r+mt} - X_r \le a) = P^{\eta}(X_{r+mt} - X_{r+(m-1)t} + X_{r+(m-1)t} - X_r \le a) \\ \le P^{\eta}(\mathcal{E}_{m-1}^c) + \sum_{z_0, z_{m-1} \in \mathbb{Z}} P^{\eta}(X_{r+mt} - X_{r+(m-1)t} \le a - (z_{m-1} - z_0) | A_{z_0, z_{m-1}}) P^{\eta}(X_{r+(m-1)t} = z_{m-1}, X_r = z_0).$$
with

$$
A_{z_0, z_{m-1}} = \{X_{r+(m-1)t} = z_{m-1}, X_r = z_0, \mathcal{E}_{m-1}\}.
$$

Using the inductive hypothesis each term of the sum can be controlled by

$$
P^{\eta}(X_{r+mt} - X_{r+(m-1)t} \le a - (z_{m-1} - z_0) | A_{z_0,z_{m-1}}) \le P^{\eta}(Y_m \le a - (z_{m-1} - z_0)).
$$

Therefore indeed $P^{\eta}(X_{r+mt} - X_r \le a) \le P^{\eta}(Y_m + X_{r+(m-1)t} - X_r \le a) + P^{\eta}(\mathcal{E}_{m-1}^c)$. So (3.19) and hence (3.18) are shown.

We now proceed to bound each term in the right hand side of (3.18) separately. First, it follows from the definition (3.14) of $(t_n)_{n \ge 0}$ and the definition (3.15) of $(c_n)_{n \ge 0}$ that, if $T$ is large enough,

$$
Mt := E^{\eta}(Y_k) = \mathrm{ct}(1 - e^{-\phi_t^{1/4}}) - te^{-\phi_t^{1/4}} \geq \frac{c+c'}{2}t. \quad (3.20)
$$

Therefore

$$
\begin{align*}
P^{\eta}\left(\sum_{k=1}^{t-1} Y_k \le c't' + r\right) &\le P^{\eta}\left(\sum_{k=1}^{t-1} (Y_k - Mt) \le (c' - M)(t-1)t + 8t\right) \\
&\le P^{\eta}\left(\sum_{k=1}^{t-1} (Y_k - Mt) \le -\frac{c-c'}{2}(t-1)t + 8t\right) \\
&\le P^{\eta}\left(\sum_{k=1}^{t-1} (Y_k - Mt) \le -t^{3/4}(t-1)\right) \le e^{-ct^{1/2}}, \quad (3.21)
\end{align*}
$$

where we have used the decomposition $t' = r + (t-1)t$, as well as the bounds $r \le 4t$ and $c' \le 1$ to get the first inequality, the estimate (3.20) to get the second one, the definitions (3.14) of $(t_n)_{n \ge 0}$ and (3.15) of $(c_n)_{n \ge 0}$ to get the third one, and finally a classical concentration bound for sum of independent bounded variables ($|Y_k| \le t$ a.s.) to obtain the last one.

We then use Proposition 2.1 to get a bound on the second term in the right hand side of (3.18). By assumption, $y \in G(\eta, \phi_{t'})$ as soon as $y \in B(0, t')$, while, by the definition (3.2) of the sequence $(\phi_L)$, we have $\gamma r \ge \gamma t \ge \phi_t^3$. Therefore

$$
\sum_{\substack{y \in B(0, t'), \\ r \le s \le t'}} P^{\eta}(y \notin G(\eta(s), \phi_t)) \le C t'^2 \frac{\exp(-c \phi_t \rho^2 (\epsilon_{\phi_t} - \epsilon_{\phi_{t'}})^2)}{\rho^2 (\epsilon_{\phi_t} - \epsilon_{\phi_{t'}})^2} \le e^{-\phi_t^{1/3}}, \quad (3.22)
$$

where the last bound is obtained using the explicit expressions (3.1) for $(\epsilon_L)$, (3.2) for $(\phi_L)$, and (3.14) for $(t_n)_{n \ge 1}$.

The result is obtained by inserting (3.21) and (3.22) in (3.18), and then (3.18) in (3.17). □

**3.4 Proof of Theorem 3.1**

*Proof of Theorem 3.1.* Let us first show that there exists a constant $C < +\infty$ and $\alpha > 0$ such that

$$
\mathbb{P}_{\rho} (\exists y \in B(0, t) \text{ s.t. } y \notin G(\eta, \phi_t)) \leq C e^{-t^{\alpha}}. \quad (3.23)
$$

Indeed, because the equilibrium measure is a Bernoulli product measure, we find

$$
\begin{align*}
\mathbb{P}_{\rho}(\exists y \in B(0,t) \text{ s.t. } y \notin G(\eta, \phi_t)) &\le \sum_{y \in B(0,t)} \mathbb{P}_{\rho}(y \notin G(\eta, \phi_t)) \\
&\le \sum_{y \in B(0,t)} \sum_{L \ge \phi_t} \mathbb{P}_{\rho}(\langle \eta \rangle_{y,L} > (1+\epsilon_{\phi_t})\rho) \\
&\le 2 \sum_{y \in B(0,t)} \sum_{L \ge \phi_t} e^{-cL\epsilon_{\phi_t}^2 \rho} \\
&\le Ct \frac{e^{-c\rho\phi_t\epsilon_{\phi_t}^2}}{\epsilon_{\phi_t}^2 \rho}.
\end{align*}
$$
Relation (3.23) is then obtained by inserting the values of $\phi_t$ and $\epsilon_{\phi_t}$ given by (3.1) and (3.2).

By the Borel-Cantelli lemma, it then follows from Proposition 3.3 and (3.23) that $\liminf_{t \to \infty} X_t \ge vt/2 P_0 - a.s.$, where v as in Lemma 3.2. $\square$

# 4 Drift for small $\gamma$

We here prove

**Theorem 4.1.** Assume that the condition (1.9) for transience to the right in a static environment holds. Then, for $\gamma$ small enough, there exists $v(\gamma) > 0$ such that

$$ \liminf_{t \to \infty} \frac{X_t}{t} = v(\gamma) \quad P_0 - a.s. $$

Remark that the ellipticity condition (1.7) is not required. The cases where (1.9) holds while (1.7) is violated correspond to the cases $(\alpha = 1, \beta > 0)$ or $(\alpha > 0, \beta = 1)$. Since (1.9) still holds if the values or $\alpha$ or $\beta$ are lowered by a small enough amount, we conclude by a coupling argument that the hypothesis (1.7) can be added without loss of generality. We will thus assume that (1.7) holds.

## 4.1 Outline of the proof

The overall strategy to prove Theorem 3.1 and Theorem 4.1 are completely analogous, but the actual implementation of the proofs differs in several respects.

The main new conceptual difficulty appears when initializing the renormalization procedure. Indeed, Theorem 3.1 was obviously valid in the formal limit $"\gamma = \infty"$, and we could easily provide the initial step in Lemma 3.2. Theorem 4.1 becomes wrong though, in the limit $\gamma = 0$. Two competing factors determine the behavior of the walk in the regime $\gamma \to 0$ ($\gamma > 0$): though the evolution of the walker is better and better approximated by its evolution in a static environment as $\gamma \to 0$, implying transience to the right, the dissipation of traps gets slower and slower (the asymptotic velocity of the walker goes to 0 as $\gamma \to 0$). Quantitative estimates are needed to compute the resulting effect.

In Lemma 4.2 below, we provide the needed specific estimates expressing that, if $\gamma = 0$, there exists $\delta > 0$ so that $X_t \sim t^\delta$ if the hypothesis (1.9) holds. Taking now $\gamma > 0$ small enough, we show in Lemma 4.3 below that the behavior of the walker is well approximated by its behavior in a static environment as long as $t \sim \gamma^{-1}$, so that $X_t \sim t^\delta$ for $t \sim \gamma^{-1}$. It proves convenient to look at the evolution of $Y_t := X_{\gamma^{-1}t}$ instead of $X_t$ (we do not use the notation $Y_t$ through the proof): First, since the environment evolves over time scales of order $\gamma^{-1}$, corresponding to one "step" $Y_t - Y_{t-1}$, the dissipation of traps seen by the walker ($Y_t$)$_{t \ge 0}$ does not get slowed as $\gamma \to 0$. Second, the expected drift of ($Y_t$)$_{t \ge 0}$, $E_0(Y_1)$, does not vanish in the limit $\gamma \to 0$ (it is actually of order $\gamma^{-\delta}$). Therefore, for ($Y_t$)$_{t \ge 0}$, we can proceed as in the previous section: Lemma 4.3 will play the role of Lemma 3.2, to initialize the procedure, and Proposition 4.5 the role of Proposition 3.3, where the renormalization is worked out. Finally, as $\gamma$ will eventually be fixed, the result for ($Y_t$)$_{t \ge 0}$ implies the result for ($X_t$)$_{t \ge 0}$.

There is however still one technical problem hidden in the above description. In the previous section, we used repeatedly the deterministic bound $X_t - X_s > -(t-s)$ for $s \le t$. However, for ($Y_t$)$_{t \ge 0}$, this becomes $Y_t - Y_s > -\gamma^{-1}(t-s)$. As this bound clearly deteriorates as $\gamma \to 0$, we need to replace it by a probabilistic estimate. This is the aim of Lemma 4.4 below (see also the comments above this lemma). Unfortunately, the lack of a simple deterministic bound makes the whole proof considerably more heavy.
Several constants will appear through the proof. Since it matters to select them in a given order, we list all of them already now (though some of them will only be formally introduced later):

1. As before, we let the sequence $(\epsilon_L)_L$ be given by (3.1).

2. We fix the parameters of the model, $\alpha, \beta$ and $\rho$, so that (1.7) and (1.9) hold.

3. We fix an exponent $q \ge 2$, that appears in Lemma 4.3 and Proposition 4.5 below. It is used to quantify the probability of the exceptional event where the walker does not drift to the right (see (4.16) below)

4. We fix $\tau > 0$ small enough so that the environment can be accurately approximated by a static environment on time intervals of length $\gamma^{-1}\tau$. This is used in the proofs of Lemmas 4.3 and 4.4 below.

5. We fix $K > 0$ large enough so that environments with no trap of size larger or equal to $K \ln L$ in a given region of size $L$, are typical with respect to the equilibrium measure. This is used in Lemmas 4.3 and 4.4 and in Proposition 4.5 below. Incidentally, taking $K$ large enough allows also to successfully apply Propositions 2.1 and 2.2.

6. We fix $\delta > 0$ small enough so that, in a static environment, the walker drifts a distance $t^\delta$ to the right in a time $t$ with high probability. It is used in Lemmas 4.3 and 4.4 and in Proposition 4.5 below.

7. Finally, we take $\gamma > 0$ small enough.

## 4.2 Static environment

In this section, we consider a random walk in a static random environment. We refer to [24] for background. Given an environment $\omega \in [0, 1]^Z$, we define $S_x^\omega$ to be the law of the walker starting at time 0 in $x \in Z$, and evolving in the static environment $\omega$. We write $S^\omega$ for $S_0^\omega$. Given $\eta \in \{0, 1\}^Z$, we can define via (1.5) an environment $\omega(\eta)$. To simplify notations, we write $S^\eta$ for $S^\omega(\eta)$. Given a static environment $\omega$, we define the associated potential $V$ by

$$V(0) = 0 \quad \text{and} \quad \forall i \in Z, \quad V(i+1) - V(i) = \ln \frac{1 - \omega_{i+1}}{\omega_{i+1}}.$$

**Lemma 4.2.** Let $K$, and $\delta$ be positive numbers. Let $\tilde{\rho} \in [\rho, 1[$ be small enough so that

$$E^{\tilde{\rho}} \left( \ln \frac{1-\omega}{\omega} \right) < \frac{1}{2} E^{\rho} \left( \ln \frac{1-\omega}{\omega} \right),$$

where $E^\rho$ denotes the expectation with respect to $P_\rho$.

1. There exists $C > 0$ so that, for $t$ large enough (depending on $\delta$), if the environment satisfies $\langle \eta \rangle_{-t^\delta/2, t^\delta/2} \le \tilde{\rho}$, then

$$S^\eta \left( \inf_{0 \le s \le t} X_s \le -t^\delta \right) \le e^{-Ct^\delta}. \quad (4.1)$$

2. For $t$ large enough (depending on $\delta$ and $K$), if the environment satisfies

$$\forall x \in B(0, 2t^\delta), \quad \langle \eta \rangle_{x,K \ln t^\delta} \le \tilde{\rho},$$

then, there exists $C_K > 0$ such that

$$S^\eta(X_t \le t^\delta) \le t^{-(1-C_K\delta)}. \quad (4.2)$$
Random walk driven by the simple exclusion process

Note that the assumption of point 2 implies the assumption of point 1.

*Proof.* For simplicity, to avoid the use of integer parts, we assume that $t^\delta$ is an integer.
We start with point 1. Under the assumption $\langle \eta \rangle_{-t^\delta/2, t^\delta/2} \le \tilde{\rho}$,

$$V(-t^\delta) \ge -t^\delta \mathrm{E}^{\tilde{\rho}} \left( \ln \frac{1-\omega}{\omega} \right) \ge -t^\delta \frac{\mathrm{E}^{\rho} \left( \ln \frac{1-\omega}{\omega} \right)}{2}.$$

Recall that (see e.g. [24])

$$S^{\eta}(T_{-t^{\delta}} < T_1) = \frac{1}{\sum_{i=-t^{\delta}}^{0} e^{V(i)}} \le e^{t^{\delta} \frac{\mathrm{E}^{\rho} \left( \ln \frac{1-\omega}{\omega} \right)}{2}}.$$

Therefore, using Markov's property at successive return times in 0, we obtain

$$S^{\eta} \left( \inf_{0 \le s \le t} X_s \le -t^{\delta} \right) \le t e^{t^{\delta} \frac{\mathrm{E}^{\rho} \left( \ln \frac{1-\omega}{\omega} \right)}{2}}.$$

This concludes the proof of (4.1).

We turn to point 2. We first control the probability that the walker has not exited the interval $[-2t^\delta, 2t^\delta]$ at time $t$. Let $T := \min\{k \ge 0, X_k \notin [-2t^\delta, 2t^\delta]\}$. Define the environment $\tilde{\omega}$ for $i \in \mathbb{Z}$ by

$$\tilde{\omega}_i = \begin{cases} \omega_i & \text{if } i \ge -2t^\delta, \\ 0 & \text{if } i < -2t^\delta. \end{cases}$$

By an obvious coupling of $S^\eta$ and $S^{\tilde{\omega}}$,

$$S^{\eta}(T \ge t) \le S^{\tilde{\omega}}(T_{2t^{\delta}} \ge t),$$

where $T_x$ denotes the hitting time of $x \in \mathbb{Z}$. Using a classical recurrence (see [24] p.59 for example), we find

$$E_{S^{\tilde{\omega}}}(T_{2t^{\delta}}) \le \frac{1}{\alpha} (4t^{\delta})^2 e^{[V]_{-t^{\delta},t^{\delta}}},$$

where for $a, b \in \mathbb{Z}$, $[V]_{a,b} = \max\{V(j) - V(i), 1 \le i \le j \le b\}$. The assumption of point 2 implies that any excursion above a minimum of $V$ has length at most $K \ln t^\delta$, and thus $[V]_{-2t^\delta, 2t^\delta} \le K \ln(t^\delta) \ln(\frac{1-\alpha}{\alpha})$. Finally, using Markov's inequality,

$$S^{\eta}(T \ge t) \le \frac{16}{\alpha} t^{2\delta - 1 + \delta K \ln(\frac{1-\alpha}{\alpha})}.$$

We turn to the probability that the walker is at the left of $t^\delta$ at time $t$:

$$S^{\eta}(X_t \le t^{\delta}) \le S^{\eta}(T \ge t) + S^{\eta}(\inf_{0 \le s \le t} X_s \le -2t^{\delta}) + S^{\eta}(T_{2t^{\delta}} < t, X_t \le t^{\delta}).$$

We have already controlled the first two terms. For the last one, we apply Markov's property at time $T_{t^\delta}$ and then we use (4.1) to derive

$$S^{\eta}(T_{2t^{\delta}} < t, X_t \le t^{\delta}) \le t e^{\frac{t^{\delta}}{4} \mathrm{E}^{\rho} \left( \ln \frac{1-\omega}{\omega} \right)} \le e^{-Ct^{\delta}}.$$

The largest of the three terms is thus the first one, at least for $t$ large enough. This concludes the proof of (4.2). □
## 4.3 Initial step

The assumption $\gamma t \ge L^3$ in Proposition 2.1 will read $t \ge K^3 \ln^3(\gamma^{-\delta}t)$, for $t$ replaced by $\gamma^{-1}t$ and $L$ replaced by $K \ln(\gamma^{-\delta}t)$, as it will be the case in the renormalization procedure (see Proposition 4.5 below). This procedure can thus only be initiated for times satisfying this bound, hence the choice of a window $\ln^4(\gamma^{-1}) \le T \le \ln^9(\gamma^{-1})$ in the next lemma:

**Lemma 4.3.** Let $q \ge 2$. Let $K > 0$ large enough then $\delta > 0$ small enough and then $\gamma > 0$ small enough. Let $\ln^4(\gamma^{-1}) \le T \le \ln^9(\gamma^{-1})$. Assume that the initial environment $\eta \in \{0, 1\}^Z$ is such that

$$ \forall x \in B(0, (\gamma^{-\delta}T)^2), \quad x \in G(\eta, K \ln(\gamma^{-\delta}T)). $$

Then,

$$ P^{\eta}(X_{\gamma^{-1}T} \le \gamma^{-\delta}T) \le \frac{1}{T^q}. $$

*Proof.* Let $\tau > 0$ be a real number that we will fix later. Let us first define an event $E$ relative to the exclusion process alone. We set

$$ E = \bigcap_{j=0}^{T/\tau-1} (A_j \cap B_j), $$

with, for $j = 0, \dots, T/\tau - 1$,

* $(\eta(t))_{t \ge 0} \in A_j$ if and only if

$$ \forall x \in B(0, (\gamma^{-\delta}T)^2), \quad \langle \eta(t_j) \rangle_{x,L} \le (1+\epsilon_{L^{1/2}})\rho \quad \text{where} \quad t_j = j\tau, \quad L = K \ln(\gamma^{-\delta}T), $$

* $(\eta(t))_{t \ge 0} \in B_j$, if and only if, for all $x \in B(0, (\gamma^{-\delta}T)^2)$, the number of jumps of the exclusion process that moves particles in the time-space window $[\gamma^{-1}t_j, \gamma^{-1}t_{j+1}] \times [x - L, x + L]$ is bounded by $\tau^{1/2}(2L)$.

We then decompose

$$ P^{\eta}(X_{\gamma^{-1}T} \le \gamma^{-\delta}T) \le P^{\eta}(X_{\gamma^{-1}T} \le \gamma^{-\delta}T|E) + P^{\eta}(E^c). \quad (4.3) $$

Let us estimate the first term in the right hand side of (4.3). Let $\omega$ be an environment such that the corresponding $(\eta(t))_{t \ge 0}$ satisfies $(\eta(t))_{t \ge 0} \in E$. Let $x_j = j\gamma^{-\delta}\tau$ ($0 \le j \le T/\tau - 1$). A coupling argument shows that

$$ P_{0,0}^{\omega}(X_{\gamma^{-1}T} > \gamma^{-\delta}T) \ge \prod_{j=0}^{T/\tau-1} P_{\gamma^{-1}t_j, x_j}^{\omega}(X_{\gamma^{-1}t_{j+1}} - X_{\gamma^{-1}t_j} > \gamma^{-\delta}\tau). \quad (4.4) $$

For any $0 \le j \le T/\tau - 1$, we define $\tilde{\eta}$ by

$$ \tilde{\eta}_j = \max_{t_j \le s \le t_{j+1}} \eta(\gamma^{-1}s). $$

On $A_j \cap B_j$, it holds that

$$ \langle \tilde{\eta}_j \rangle_{x_j, L} \le (1 + \epsilon_{L^{1/2}} + \tau^{1/2})\rho := \tilde{\rho}. $$

For $\tau$ and $\gamma$ small enough, it holds that $E^{\tilde{\rho}}((1-\omega)/\omega) < \frac{1}{2}E^{\rho}((1-\omega)/\omega)$. It then follows from the second part of Lemma 4.2 with $t = \gamma^{-1}\tau$, that for $\gamma$ small enough,

$$ \begin{aligned} P_{\gamma^{-1}t_j, x_j}^{\omega} (X_{\gamma^{-1}t_{j+1}} - X_{\gamma^{-1}t_j} > \gamma^{-\delta}\tau) &\ge S_{x_j}^{\tilde{\eta}_j} (X_{\gamma^{-1}\tau} - x_j > \gamma^{-\delta}\tau) \\ &\ge S_{x_j}^{\tilde{\eta}_j} (X_{\gamma^{-1}\tau} - x_j > (\gamma^{-1}\tau)^{\delta}) \ge 1 - \gamma^{1-C_K\delta}. \end{aligned} \quad (4.5) $$
Inserting this estimate in (4.4), we find that, for $\delta > 0$ small enough and $\gamma > 0$ small enough,

$$P_{0,0}^{\omega}(X_{\gamma^{-1}T} > \gamma^{-\delta}T) \geq (1 - \gamma^{1-C_{\kappa}\delta})^{T/\tau} \geq \exp(-(T/\tau)\gamma^{1-C_{\kappa}\delta}/2).$$

Therefore, thanks to the hypothesis $\ln^4(\gamma^{-1}) \leq T \leq \ln^9(\gamma^{-1})$, it also holds that

$$P^{\eta}(X_{\gamma^{-1}T} \leq \gamma^{-\delta}T|E) \leq 1 - \exp(-(T/\tau)\gamma^{1-C_{\kappa}\delta}/2) \leq T^{-(q+1)}. \quad (4.6)$$

We next come to the second term in the right hand side of (4.3):

$$P^{\eta}(E^c) \leq \sum_{j=0}^{T/\tau-1} P^{\eta}((A_j \cap B_j)^c) \leq \sum_{j=0}^{T/\tau-1} (P^{\eta}(A_j^c) + P^{\eta}(B_j^c|A_j)). \quad (4.7)$$

First, applying Proposition 2.2 we find that for $\gamma$ small enough and $j = 0, \dots, T/\tau - 1$,

$$P^{\eta}(A_j^c) \leq \sum_{x \in B(0, (\gamma^{-\delta}T)^2)} P^{\eta}(\langle \eta(t_j) \rangle_{x,L} > (1+\epsilon_{L^{1/2}})\rho) \leq C(\gamma^{-\delta}T)^2 e^{-cL(\epsilon_{L^{1/2}}-\epsilon_L)^2} \leq (\gamma^{-\delta}T)^{2-cK}.$$

Next, by a classical concentration bound, for $\tau$ small enough, there exists $c(\tau) > 0$ so that, for $j = 0, \dots, T/\tau - 1$,

$$P^{\eta}(B_j^c|A_j) \leq C(\gamma^{-\delta}T)^2 e^{-c(\tau)L} \leq (\gamma^{-\delta}T)^{2-cK}.$$

Inserting these two last bounds in (4.7), we conclude that, if $K$ is large enough,

$$P^{\eta}(E^c) \leq T^{-(q+1)}. \quad (4.8)$$

The result is obtained by inserting (4.6) and (4.8) in (4.3). □

## 4.4 Rough lower bound for intermediate times

Lemma 4.3 derived above does not yet allow to initiate the renormalization procedure described in the proof of Proposition 4.5 below. Indeed, while it ensures that the walker moves a distance $\gamma^{-\delta}t$ to the right over a time $\gamma^{-1}t$, with probability $1 - 1/t^q$ for good initial environments, we only know that the walker does not move more than a distance $\gamma^{-1}t$ to the left, with probability $1/t^q$ for good initial environments. Since Lemma 4.3 is only valid for a time $t \leq \ln^9(\gamma^{-1})$, we cannot yet exclude that $E^{\eta}(X_{\gamma^{-1}T}) < 0$. For intermediate times $t$ such that $T \leq t \leq \gamma^{-1}$, with $T$ as in Lemma 4.3, the next lemma furnishes a better lower bound than the deterministic bound $X_s \geq -s$ ($s \geq 0$). In particular, once combined with Lemma 4.4, Lemma 4.3 ensures now that the walker drifts to the right over a time $\gamma^{-1}T$. We will use the full power of Lemma 4.4, i.e. when $T < t \leq \gamma^{-1}$, for the first iterations in the proof of Proposition 4.5, where the same type of difficulty shows up.

**Lemma 4.4.** Let $K > 0$ large enough, then $\delta > 0$ small enough, and then $\gamma > 0$ small enough. Assume that $T$ is chosen as in Lemma 4.3, i.e. $\ln^4(\gamma^{-1}) \leq T \leq \ln^9(\gamma^{-1})$, and let $T \leq t \leq \gamma^{-1}$. Assume that the initial state $\eta \in \{0, 1\}^Z$ is such that

$$\forall x \in B(0, (\gamma^{-\delta}t)^2), \quad x \in G(\eta, K \ln(\gamma^{-\delta}t)). \quad (4.9)$$

Then for all $1 \leq s \leq t$,

$$P^{\eta}(X_{\gamma^{-1}s} \leq -\gamma^{-\delta}s) \leq e^{-s^{\delta/2}}.$$
Random walk driven by the simple exclusion process

Proof. We first notice that the hypothesis (4.9) implies

$$ \forall x \in B(0, (\gamma^{-\delta}t)^2), \quad x \in G(\eta, (\tau\gamma^{-1})^{\delta}/2), \qquad (4.10) $$

provided that $(\epsilon_L)_{L \ge 0}$ is no longer given by (3.1), but is such that

$$ \epsilon_{(\tau\gamma^{-1})^{\delta}/2} = \frac{1}{1 + \ln(1 + \ln(\gamma^{-\delta}t))}. \qquad (4.11) $$

For the present proof, we assume that (4.11) holds instead of (3.1), and we use directly the hypothesis (4.10) instead of (4.9).

Fix $1 \le s \le t$ and define an event $E$ relative to the exclusion process alone. We set

$$ E = \bigcap_{j=0}^{s/\tau-1} (A_j \cap B_j), $$

with

* $(\eta(t))_{t \ge 0} \in A_j$ if and only if

$$ \langle \eta(\gamma^{-1}t_j) \rangle_{x_{j-L}, L} \le (1+\epsilon_{L^{1/2}})\rho \quad \text{where} \quad t_j = j\tau, \quad x_j = -k(\tau\gamma^{-1})^\delta, \quad L = (\tau\gamma^{-1})^\delta/2, $$

* $(\eta(t))_{t \ge 0} \in B_j$ if and only if the number of jumps of the exclusion process that moves particles in the time-space window $[x_j - 2L, x_j] \times [\gamma^{-1}t_j, \gamma^{-1}t_{j+1}]$ is bounded by $\tau^{1/2}(2L)$.

We then decompose

$$ P^{\eta}(X_{\gamma^{-1}s} \le -\gamma^{-\delta}s) \le P^{\eta}(X_{\gamma^{-1}s} \le -\gamma^{-\delta}s|E) + P^{\eta}(E^c). \qquad (4.12) $$

Let us estimate the first term in the right hand side of (4.12). Let $\omega$ be an environment such that the corresponding $(\eta(t))_{t \ge 0}$ satisfies $(\eta(t))_{t \ge 0} \in E$. A coupling argument shows that

$$ P_{0,0}^{\omega}(X_{\gamma^{-1}s} \le -\gamma^{-\delta}s) \le \sum_{j=0}^{s/\tau-1} P_{\gamma^{-1}t_j, x_j}^{\omega}(X_{\gamma^{-1}t_{j+1}} - X_{\gamma^{-1}t_j} \le -2L). \qquad (4.13) $$

For any $0 \le j \le s/\tau - 1$, we define $\tilde{\eta}$ by

$$ \tilde{\eta}_j = \max_{t_j \le r \le t_{j+1}} \eta(\gamma^{-1}r). $$

It holds that

$$ \langle \tilde{\eta}_j \rangle_{x_{j-L}, L} \le (1 + \epsilon_{L^{1/2}} + \tau^{1/2})\rho := \tilde{\rho}. $$

For $\tau$ small enough and $\gamma$ small enough, it holds that $E^{\tilde{\rho}}((1-\omega)/\omega) < \frac{1}{2}E^{\rho}((1-\omega)/\omega)$. By a coupling argument and the first part of Lemma 4.2, we obtain, for some $c > 0$,

$$ P_{\gamma^{-1}t_j, x_j}^{\omega}(X_{\gamma^{-1}t_{j+1}} - X_{\gamma^{-1}t_j} \le -2L) \le S_{x_j}^{\tilde{\eta}_j}(X_{\gamma^{-1}\tau} - x_j \le -2L) \le e^{-cL}. $$

Therefore, inserting this estimate in (4.13), it holds that $P_{0,0}^{\omega}(X_{\gamma^{-1}s} \le -\gamma^{-\delta}s) \le (s/\tau)e^{-cL}$, so that

$$ P^{\eta}(X_{\gamma^{-1}s} \le -\gamma^{-\delta}s|E) \le \frac{s}{\tau}e^{-cL}. \qquad (4.14) $$

For the second term in the right hand side of (4.12), we have too

$$ P^{\eta}(E^c) \le \sum_{j=0}^{s/\tau-1} P^{\eta}((A_j \cap B_j)^c) \le \sum_{j=0}^{s/\tau-1} (P^{\eta}(A_j^c) + P^{\eta}(B_j^c|A_j)) \le \frac{s}{\tau}e^{-cL}, \qquad (4.15) $$
since, applying Proposition 2.2 we find $P^{\eta}(A_j^c) \le e^{-cL}$ if $K$ is large enough, while, if $\tau$ is chosen small enough, a classical concentration bound furnishes $P^{\eta}(B_j^c|A_j) \le e^{-cL}$.

Inserting (4.14) and (4.15) into (4.12), we obtain for $\gamma$ large enough,

$$P^{\eta}(X_{\gamma^{-1}s} \le -\gamma^{-\delta}s) \le C\gamma^{-1}\tau^{-1}e^{-cL} \le e^{-\gamma^{-\delta/2}} \le e^{-s^{\delta/2}}.$$

since $s \le \gamma^{-1}$.

□

## 4.5 Renormalization procedure

We use Lemma 4.3 as initial step, Proposition 2.1 to guarantee the dissipation of possible traps with high probability, and Lemma 4.4 as lower bound for intermediate times, to derive

**Proposition 4.5.** Let $q \ge 2$. Let $K$ be large enough, then $\delta > 0$ small enough and finally $\gamma > 0$ small enough. Fix $t \ge \ln^9(\gamma^{-1})$ and assume that the initial environment $\eta \in \{0, 1\}^Z$ is such that

$$\forall x \in B(0, (\gamma^{-\delta}t)^2), \quad x \in G(\eta, K \ln(\gamma^{-\delta}t)).$$

Then,

$$P^{\eta}(X_{\gamma^{-1}t} \le \gamma^{-\delta}t/2) \le 1/t^q. \qquad (4.16)$$

*Proof.* We take $K < +\infty$, $\delta > 0$ and $\gamma > 0$ such that Lemmas 4.3 and 4.4 hold. Given $t \ge \ln^9(\gamma^{-1})$, we define a sequence $(t_n)_{n \ge 0}$ with $t_0 \in [\ln^4 \gamma^{-1}, \ln^9 \gamma^{-1}]$ and for $n \ge 0$, $t_{n+1} \in [t_n^2, (t_n+1)^2]$, such that for some $N \ge 0$, $t_N = t$. Recall the definition of $(c_n)_{n \ge 0}$ in (3.15) with $\nu = 1$ so that the sequence is decreasing from 1 to $1/2$. We prove by recurrence that, given $\eta \in \{0, 1\}^Z$ and $n \ge 0$, if, for any $x \in B(0, (\gamma^{-\delta}t_n)^2)$, it holds that $x \in G(\eta, K \ln \gamma^{-\delta}t_n)$, then

$$P^{\eta}(X_{\gamma^{-1}t_n} \le c_n \gamma^{-\delta} t_n) \le t_n^{-q}. \qquad (4.17)$$

This will imply the claim.

By Lemma 4.3 and by the hypotheses, (4.17) holds true for $n = 0$. We now assume that (4.17) holds for some $n \ge 0$, and we show that it implies it for $n + 1$. To simplify notations, let us write $t_n = t$ and $t_{n+1} = t'$, as well as $c_n = c$ and $c_{n+1} = c'$. It holds that $t' = r + (t - 1)t$ for some $t \le r < 4t$. The cases $t' \le \gamma^{-1}$ and $t' > \gamma^{-1}$ are treated differently. We first write a bound analogous to (3.17) in the proof of Proposition 3.3:

$$P^{\eta}(X_{\gamma^{-1}t'} \le c'\gamma^{-\delta}t') \le P^{\eta}(X_{\gamma^{-1}t'} - X_{\gamma^{-1}r} \le c'\gamma^{-\delta}t' + \gamma^{-\delta}r) + e^{-t^{\delta/2}} \quad \text{if } t' \le \gamma^{-1}, \qquad (4.18)$$

$$P^{\eta}(X_{\gamma^{-1}t'} \le c'\gamma^{-\delta}t') \le P^{\eta}(X_{\gamma^{-1}t'} - X_{\gamma^{-1}r} \le c'\gamma^{-\delta}t' + \gamma^{-1}r) \quad \text{if } t' > \gamma^{-1}, \qquad (4.19)$$

where (4.18) is derived from Lemma 4.4 while the bound $X_{\gamma^{-1}r} \ge -\gamma^{-1}r$ in (4.19) is deterministic.

We need to evaluate the right hand side of either of these bounds. For this, we define on the same probability space (enlarged if necessary) a sequence $(Y_k)_{k \ge 1}$ of i.i.d. random variables independent from both the exclusion process and the walker with distribution:

$$P^{\eta}(Y_k = c\gamma^{-\delta}t) = 1 - t^{-q}, \qquad P^{\eta}(Y_k = -\gamma^{-\delta}t) = t^{-q} \quad \text{if } t' \le \gamma^{-1}, \qquad (4.20)$$

$$P^{\eta}(Y_k = c\gamma^{-\delta}t) = 1 - t^{-q}, \qquad P^{\eta}(Y_k = -\gamma^{-\delta}t) = t^{-q} \quad \text{if } t' > \gamma^{-1}. \qquad (4.21)$$
Random walk driven by the simple exclusion process

For any integer $m \ge 0$, let us also define the events

$$
\begin{align*}
\mathcal{D}_m &= \{X_{\gamma^{-1}(r+mt)} \geq -\gamma^{-\delta}t'\}, \\
\mathcal{E}_m &= \{\forall x \in B(0, (\gamma^{-\delta}t')^2), x \in G(\eta(\gamma^{-1}(r+mt)), K \ln(\gamma^{-\delta}t))\}.
\end{align*}
$$

Using our inductive hypothesis, we aim to show that, for $t' \le \gamma^{-1}$,

$$
\begin{align}
P^{\eta} (X_{\gamma^{-1}t'} - X_{\gamma^{-1}r} \le c' \gamma^{-\delta} t' + \gamma^{-\delta} r) &\le P^{\eta} \left( \sum_{k=1}^{t-1} Y_k \le c' \gamma^{-\delta} t' + \gamma^{-\delta} r \right) \nonumber \\
&\quad + \sum_{1 \le m \le t-1} P^{\eta} (X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} \le -\gamma^{-\delta} t | \mathcal{D}_{m-1}, \mathcal{E}_{m-1}) \nonumber \\
&\quad + \sum_{1 \le m \le t-1} (P^{\eta}(\mathcal{D}_{m-1}^c) + P^{\eta}(\mathcal{E}_{m-1}^c)) \tag{4.22}
\end{align}
$$

with $(Y_k)_{k \ge 1}$ given by (4.20), and for $t' > \gamma^{-1}$,

$$
P^{\eta} (X_{\gamma^{-1}t'} - X_{\gamma^{-1}r} \le c' \gamma^{-\delta} t' + \gamma^{-1} r) \le P^{\eta} \left( \sum_{k=1}^{t-1} Y_k \le c' \gamma^{-\delta} t' + \gamma^{-1} r \right) + \sum_{1 \le m \le t-1} P^{\eta}(\mathcal{E}_{m-1}^c) \quad (4.23)
$$

with $(Y_k)_{k \ge 1}$ given by (4.21). One sees that the first of these bounds, valid for $t' \le \gamma^{-1}$, involves two extra terms in comparison with the second one, valid for $t' > \gamma^{-1}$. This comes from the fact that, in the first case, it is not always so that, after a time $\gamma^{-1}(r+(m-1)t)$ (for some $1 \le m \le t-1$), the walker is on a site where we have a control on the environment, while it is always so in the second case (the initial environment is controlled in a box of size $(\gamma^{-\delta}t')^2$).

The bounds (4.22) and (4.23) are shown in an analogous way; as the latter is easier,
we focus on the derivation of (4.22). Let us thus assume $t' \le \gamma^{-1}$. Let us establish that,
for any $m \ge 1$ and any $a \in \mathbb{R}$, we have

$$
\begin{equation}
\begin{aligned}
P^{\eta}(X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}r} \le a) &\le P^{\eta}(X_{\gamma^{-1}(r+(m-1)t)} + Y_m - X_{\gamma^{-1}r} \le a) \\
&\quad + P^{\eta}(X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} \le -\gamma^{-\delta}t | \mathcal{D}_{m-1}, \mathcal{E}_{m-1}) + P^{\eta}(\mathcal{D}_{m-1}^c) + P^{\eta}(\mathcal{E}_{m-1}^c).
\end{aligned}
\tag{4.24}
\end{equation}
$$

Since $t' = r + (t - 1)t$, (4.22) follows from (4.24) by iteration and Fubini theorem. For $m \ge 1$:

$$
\begin{equation}
\begin{aligned}
P^{\eta}(X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}r} \le a) &\le \\
& P^{\eta}(X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} + X_{\gamma^{-1}(r+(m-1)t)} - X_{\gamma^{-1}r} \le a | \mathcal{D}_{m-1}, \mathcal{E}_{m-1}) + P^{\eta}(\mathcal{D}_{m-1}^c) + P^{\eta}(\mathcal{E}_{m-1}^c).
\end{aligned}
\tag{4.25}
\end{equation}
$$

The first term in the right hand side is expressed as

$$
\sum_{z \ge -\gamma^{-\delta} t'} P^{\eta} \left( X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} \le a - z + X_{\gamma^{-1}r} \middle| \mathcal{D}_{m-1}, \mathcal{E}_{m-1}, X_{\gamma^{-1}(r+(m-1)t)} = z \right) \\
P^{\eta} \left( X_{\gamma^{-1}(r+(m-1)t)} = z \middle| \mathcal{D}_{m-1}, \mathcal{E}_{m-1} \right). \quad (4.26)
$$

Our inductive hypothesis at scale *n* and Markov's property imply that

$$
\begin{equation}
\begin{aligned}
P^{\eta} (X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} \le a - z + X_{\gamma^{-1}r} | \mathcal{D}_{m-1}, \mathcal{E}_{m-1}, X_{\gamma^{-1}(r+(m-1)t)} = z) &\le \\
P^{\eta} (Y_m \le a - z + X_{\gamma^{-1}r}) + P^{\eta} (X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} \le -\gamma^{-\delta}t | \mathcal{D}_{m-1}, \mathcal{E}_{m-1}, X_{\gamma^{-1}(r+(m-1)t)} = z).
\end{aligned}
\tag{4.27}
\end{equation}
$$
Inserting (4.27) into (4.26), and then (4.26) into (4.25) leads to (4.24), hence to (4.22).

We now proceed to bound each term in the right hand side of (4.22) and (4.23) separately. Let us start with (4.22). To deal with the first term in the right hand side of (4.22), we define for any integer $1 \le p \le t - 1$, the event

$$A_p = \{\exists 1 \le k_1 < \dots < k_p \le t-1 : Y_{k_j} < 0 \text{ for all } 1 \le j \le p\}.$$

We have

$$P^{\eta}(A_p) \le \left(\frac{t}{t^2}\right)^p = \frac{1}{t^p}.$$

We take $p = 3(q+1)$ and we show that

$$P^{\eta} \left( \sum_{k=1}^{t-1} Y_k \le c' \gamma^{-\delta} t' + \gamma^{-\delta} r \right) \le P^{\eta} \left( \sum_{k=1}^{t-1} Y_k \le c' \gamma^{-\delta} t' + \gamma^{-\delta} r, A_p^c \right) + P^{\eta}(A_p) \le \frac{1}{t^p} \le \frac{1}{(t')^{(q+1)}}, \quad (4.28)$$

provided that $\gamma$ was taken small enough. Indeed, the first term in the right hand side of (4.28) vanishes since, on $A_p^c$, it holds that

$$\sum_{k=1}^{t-1} Y_k \ge c \gamma^{-\delta} t (t-1-p) - p \gamma^{-\delta} t > c' \gamma^{-\delta} t' + \gamma^{-\delta} r,$$

as indeed the last inequality reads $(c-c')t > C(p)$ (which holds true since $c-c' = 2^{-(n+2)}$ while $t \ge e^{c2n}$ for some $c > 0$). To deal with the second term in the right hand side of (4.22), we apply Lemma 4.4:

$$\sum_{1 \le m \le t-1} P^{\eta} \left( X_{\gamma^{-1}(r+mt)} - X_{\gamma^{-1}(r+(m-1)t)} \le -\gamma^{-\delta} t \mid \mathcal{D}_{m-1}, \mathcal{E}_{m-1} \right) \le (t-1)e^{-t^{\delta/2}} \le \frac{1}{(t')^{q+1}}. \quad (4.29)$$

Similarly,

$$\sum_{1 \le m \le t-1} P^{\eta}(\mathcal{D}_{m-1}^c) \le (t-1)e^{-t^{\delta/2}} \le \frac{1}{(t')^{q+1}}. \quad (4.30)$$

Finally, to bound for any $m \ge 0$, $P^{\eta}(\mathcal{E}_m^c)$, we apply Proposition 2.1. The hypothesis reads here $\gamma(\gamma^{-1}(r + mt)) \ge (K \ln(\gamma^{-\delta}t))^3$, and is satisfied since, for $\gamma$ small enough, $r + mt \ge t \ge \ln^4 \gamma^{-1}$. Therefore, taking $K$ large enough,

$$\sum_{1 \le m \le t-1} P^{\eta}(\mathcal{E}_{m-1}^c) \le \sum_{\substack{x \in B(0, (\gamma^{-\delta}t')^2), \\ 1 \le m \le t-1}} P^{\eta} \left( x \notin G(\eta(\gamma^{-1}(r+mt)), K \ln \gamma^{-\delta}t) \right) \\ \le (t-1)(\gamma^{-\delta}t')^2 e^{-cK \ln \gamma^{-\delta}t} \le \frac{1}{(t')^{q+1}}. \quad (4.31)$$

For (4.23), both the equivalent of (4.28) and of (4.31) remain valid. Inserting (4.28-4.31) into (4.22) and then (4.22) into (4.18) for $t' \le \gamma^{-1}$, or inserting the equivalent of (4.28) and (4.31) into (4.23) and then (4.23) into (4.19) for $t' > \gamma^{-1}$, yields the result. $\square$

## 4.6 Conclusion of the proof

*Proof of Theorem 4.1.* If $K$ is large enough, we have, writing simply $\epsilon$ for $\epsilon_{K \ln \gamma^{-\delta}t}$,

$$\begin{align*} \mathbb{P}_{\rho} (\exists x \in B(0, (\gamma^{-\delta}t)^2) : x \notin G(\eta, K \ln(\gamma^{-\delta}t))) &\le \sum_{x \in B(0, (\gamma^{-\delta}t)^2)} \mathbb{P}_{\rho} (x \notin G(\eta, K \ln(\gamma^{-\delta}t))) \\ &\le \sum_{x \in B(0, (\gamma^{-\delta}t)^2)} \sum_{L \ge K \ln(\gamma^{-\delta}t)} \mathbb{P}_{\rho} (\langle \eta \rangle_{x,L} > (1+\epsilon)\rho) \le \sum_{x \in B(0, (\gamma^{-\delta}t)^2)} \sum_{L \ge K \ln(\gamma^{-\delta}t)} e^{-cL\epsilon^2} \\ &\le C(\gamma^{-\delta}t)^2 \epsilon^{-2} e^{-cK \ln(\gamma^{-\delta}t)} \epsilon^2 \le C'(\gamma^{-\delta}t)^2 (\gamma^{-\delta}t)^{-c'K} \le t^{3-c'K} \quad (4.32) \end{align*}$$
once $t$ is large enough. This last term can be bounded by $1/t^2$ that is summable for $K$ large enough. Therefore, since

$$P_0(X_t < \gamma^{-\delta}t/2) \le P_0(\exists x \in B(0, (\gamma^{-\delta}t)^2) : x \notin G(\eta, K \ln(\gamma^{-\delta}t)) \\ + P_0(X_t < \gamma^{-\delta}t/2 | \forall x \in B(0, (\gamma^{-\delta}t)^2) : x \in G(\eta, K \ln(\gamma^{-\delta}t)),$$

it follows from the Borel-Cantelli lemma, from Proposition 4.5 and from (4.32) that, for $K$ large enough, $\delta > 0$ small enough and $\gamma > 0$ small enough,

$$\liminf_{t \to \infty} X_t \ge \frac{\gamma^{-\delta}t}{2} \quad P_0 - a.s. \quad \square$$

# 5 Proof of Theorem 1.1 and Theorem 1.2

Theorem 1.1 is deduced from Proposition 3.3 and Theorem 3.1 exactly in the same way as Theorem 1.2 is deduced from Proposition 4.5 and Theorem 4.1. We only show Theorem 1.1, and so we fix $\gamma$ large enough so that the conclusions of Proposition 3.3 and Theorem 3.1 are in force.

Let us first introduce a few definitions and notations. In Section 1.1, the law $P$ of the environment was built from the exclusion process. In this section, it is more convenient to build it from the interchange process on $\mathbb{Z}$ together with an independent collection of particles of two different types, so that each site is occupied by exactly one particle. We use the following definitions:

1. Let us consider a collection of spatially independent Poisson clocks $(U(t, x))_{t \in \mathbb{R}, x \in \mathbb{Z}}$ with parameter $\gamma$, called updates. We construct a process $(\xi(t, i))_{t \in \mathbb{R}, i \in \mathbb{Z}}$, where, for $i \in \mathbb{Z}$ and $t \in \mathbb{R}$, $\xi(t, i)$ denotes the position at time $t$ of particle $i$: $\xi(0, i) = i$ and, if the clock $x$ rings at time $t$, then the particle at $x-1$ and the particle at $x$ exchange their positions. Remark that the time is indexed by $\mathbb{R}$: it is convenient for technical reasons, although not necessary to define the model, see Lemma 5.2 for example.

2. For $t \ge 0$ and $x \in \mathbb{Z}$, $\mu(t, x)$ is the unique $i$ such that $\xi(t, i) = x$ that is the label of the particle that is in $x$ at time $t$. Note that $\mu$ is a function of $\xi$.

3. We consider also a family of type of particles $(\nu(i))_{i \in \mathbb{Z}}$, which is a product of independent Bernoulli, with parameter $\rho$. Let $\mathbb{P}_2$ be its law.

The environment $\omega$ is viewed as a function of $\xi$ and $\nu$:

$$\omega(\xi, \nu)(t, i) = \begin{cases} \alpha & \text{if } \nu(\mu(t, i)) = 1, \\ \beta & \text{if } \nu(\mu(t, i)) = 0. \end{cases}$$

We let the reader check that the law of the environment $P$ defined in Section 1.1 is the push forward probability of $\mathbb{P}_1 \otimes \mathbb{P}_2$ through this function. We denote the space where lives $\xi$ by $\Xi$, and the set of path that supports the process $X$ by $\mathcal{P}$.

We will use the ellipticity of the environment to control the probability that the walker executes some displacements independently from any information we could have about the environment. Define this minimal probability by

$$\kappa = \min\{\alpha, 1 - \alpha, \beta, 1 - \beta\}. \qquad (5.1)$$

By assumption (1.7), we have $\kappa > 0$.
We now start the proof of Theorem 1.1. Our aim is to construct a renewal structure, i.e. to cut the random path followed by the walker into pieces that are independent under $P_0$ (see [4] for the first use of this method in a similar context, see also [9, 16]). For any time-space point $(t, x) \in \mathbb{R} \times \mathbb{Z}$, we define

$$T_{t,x}^{-} = \{(s, y), s \le t, y \le x + \frac{\nu}{4}(s-t)\}, \qquad (5.2)$$

$$T_{t,x}^{+} = \{(s, y), t \le s, y \ge x + \frac{\nu}{4}(s-t)\}, \qquad (5.3)$$

where $\nu$ is the constant appearing in Proposition 3.3 (see Figure 3). The position of the rightmost visited particle at time $n \ge 0$ is $M(n) := \sup\{\xi(n, \mu), \mu \in \mathcal{V}_n\}$, with $\mathcal{V}_n = \{\mu(i, X_i), i \le n-1\}$ the set of labels of visited particles at time $n$. Our goal is to define a sequence of random times, called renewal times, that satisfy

$$\forall n \le \tau, \quad (n, X_n) \in T_{\tau, X_{\tau}}^{-}, \qquad (5.4)$$

$$M(\tau) < X_{\tau}, \qquad (5.5)$$

$$\forall n \ge \tau, \quad (n, X_n) \in T_{\tau, X_{\tau}}^{+}, \qquad (5.6)$$

$$\forall (n, x) \in T_{\tau, X_{\tau}}^{+}, \quad \xi(\tau, \mu(n, x)) \ge X_{\tau} \qquad (5.7)$$

(see Figure 3). The meaning of (5.4) and (5.6) is clear. Condition (5.5) means that, at time $\tau$, all particles visited by the walker before time $\tau$, are behind the walker. Finally, (5.7) means that all the particles at the left of $X_\tau$ at time $\tau$ will never enter into the cone $T_{\tau, X_\tau}^+$. These four conditions together imply in particular that after the time $\tau$, the walker will only visits particles that have not yet been visited at time $\tau$.

<figure><img src="image_5.png" /><figcaption>Figure 3: Renewal time $\tau$. The slope of the oblique line is $(\nu/4)^{-1}$. Conditions (5.4) and (5.6): the walker (in red) lives in $T_{\tau, X_\tau}^{-}$ before time $\tau$ and in $T_{\tau, X_\tau}^{+}$ after time $\tau$. Conditions (5.4) and (5.7): all particles visited by the walker before time $\tau$ sit at its left at time $\tau$, and no particle at the left of $X_\tau$ at time $\tau$ enters $T_{\tau, X_\tau}^{+}$.</figcaption></figure>
Our goal is to prove that, $P_0$-a.s., there are infinitely many renewal times, and to show that the first and second moments of $\tau$ are finite, from which Theorem 1.1 is readily deduced (see Section 5.5). For this, our first step is to show that, almost surly, there is a positive fraction of the points on the trajectory $(n, X_n)_{n \ge 0}$, called candidates, satisfying the conditions (5.4-5.5) (see Proposition 5.1 below). Since the walker drifts ballistically in a diffusive environment, this claim is surely very reasonable, but it is however not straightforward: While it follows directly form the ballistic behavior that a positive fraction of times satisfy (5.4), it is not obvious to prove that a positive fraction of these times satisfy (5.5). The proof of Proposition 5.1 constitutes the most technical part of the work (see the heuristic considerations below Proposition 5.1), and we stress that this problem could not be solved by the methods of [4, 9, 16]. We next turn to (5.6-5.7). In Section 5.2, we carry over the main computation that allows us to see that these conditions can be satisfied with positive probability (the ellipticity of the walk, $\kappa > 0$, see (5.1), is used here). We are then able to construct an infinite sequence of renewal points (see Sections 5.3-5.4) and, along the way, we show the properties that make the interest of the renewal times (they cut the trajectory into independent pieces). Finally, the moments of $\tau$ are bounded by combining the bounds of Proposition 3.3 and Proposition 5.1 (see Proposition 5.6 in Section 5.5).

## 5.1 Existence of a density of points $(n, X_n)$ satisfying (5.4-5.5)

Given an environment, a point $(n, X_n)$ on a trajectory $(m, X_m)_{m \ge 0}$ is said to be a candidate if it satisfies (5.4) and (5.5):

$$ \forall m \le n, \quad (m, X_m) \in T_{n, X_n}^{-}, \quad \text{and} \quad M(n) < X_n. $$

We prove the existence of a positive fraction of candidate points on $P_0$-almost every trajectory:

**Proposition 5.1.** Let $q \ge 2$. There exists some $c > 0$ such that, for $n$ large enough,

$$ P_0(\#\{i \le n, (i, X_i) \text{ is a candidate}\} \le cn) \le \frac{1}{n^q}. \quad (5.8) $$

In particular, by the Borel-Cantelli lemma,

$$ \liminf_{n \to +\infty} \frac{\#\{i \le n, (i, X_i) \text{ is a candidate}\}}{n} > c, \quad P_0 \text{-a.s.} \quad (5.9) $$

Let us first describe the idea of the proof. For this, we start by introducing a slightly weaker notion than that of candidate. Let $l \ge 1$ and $n \in \mathbb{N}$. Given an environment, a point $(n, X_n)$ on a trajectory $(m, X_m)_{m \ge 0}$ is said to be $l$-good, or simply good, if

$$ \forall m \le n, \quad (m, X_m) \in T_{n, X_n}^{-} \quad (5.10) $$

$$ M(n) < X_n + l. \quad (5.11) $$

We will prove Proposition 5.1 in two steps: we first establish the result with "candidate" replaced by "$l$-good" (for some large enough $l$), and then we show that Proposition 5.1 follows from this intermediate statement (this second step is straightforward and we do not comment upon it here).

Let us take some large integer $n$. On the one hand, by Proposition 3.3, $X_n \ge vn/2$ with high probability, for some $v > 0$. Therefore, it follows from basic geometric considerations that, with the same probability, a positive fraction of the points on the trajectory $(m, X_m)_{0 \le m \le n}$ satisfy (5.10). On the other hand, given a deterministic path $(j, Y_j)_{j \ge 0}$, with $Y_{j+1} - Y_j = \pm 1$, it holds that any given point $(k, Y_k)$ satisfying
(5.10), satisfies also (5.11) with a probability at least $1 - e^{-cl}$, where c is some constant independent from the path and the point (see Lemma 5.2 below). One may therefore try to establish that, with very high probability, any given path $(j, Y_j)_{j \ge 0}$ independent of the environment and having a density of points satisfying (5.10), has also a density of good points. More precisely, since the number of such paths, differing from one another before the time $n$, is roughly bounded by $2^n$, we would need to establish that the probability that a given such path has less than $cn$ good points decays faster to 0 than $2^{-n}$, provided that c has been chosen small enough. If the events that different points on the path are good were independent, we would indeed conclude by the above that this probability decays like $e^{-I(l)n}$, where $I(l)$ grows to infinity as $l$ grows to infinity, so that the result would follow by taking $l$ large enough.

The lack of independence forces us to adapt this strategy. Let us assume that a point $(k, Y_k)$ satisfies (5.10) but not (5.11). We define a random variable $d$ to quantify how much (5.11) failed; roughly, $d$ measures the distance to the right of $Y_k$ travelled by the particles that made (5.11) to fail (see (5.13) for a precise definition). The main observation is that, when considering a next point $(k', Y_{k'})$ satisfying (5.10), with $k' > k$, then, if $(k, Y_k + d) \in T_{k', Y_{k'}}^{-}$, we can estimate the probability that (5.11) is satisfied for $(k', Y_{k'})$, independently of our knowledge about $(k, Y_k)$. This observation is implemented as follows: First, in order to decrease the cardinal of possible paths, we consider paths of blocks of size $l$ instead of paths of points. This helps since, while the number of such paths is now bounded by $2^{n/l}$, the probability that a given block is bad (see (5.12) below) still behaves like $1 - l^2 e^{-cl} \sim 1 - e^{-c'l}$. Then, each time a bad block is seen, we estimate how bad it was, i.e. we estimate $E$, as defined in (5.17) below. The probability that $E$ exceeds a certain amount $k \ge 0$ decays exponentially with $k$ (see Lemma 5.2 below).

Before starting the proof of Proposition 5.1, let us state an elementary result relative to the updates of the environment alone (recall that the updates $U(t, x)$ are defined for all $t \in \mathbb{R}$). Given an environment, we say that a space-time point $(t, x)$ is $l$-bad, or simply bad, if there exists a particle $i \in \mathbb{Z}$ and a time $s \le t$ such that

$$ (s, \xi(s, i)) \in T_{t,x}^{-} \quad \text{and} \quad \xi(t, i) \ge l + x. \qquad (5.12) $$

Remark that, contrary to the notion of good point (see (5.10-5.11)), the notion of bad point does not involve the trajectory of the walker. Given $(t, x)$ a bad point, $A_{t,x}$ denotes the set of particles satisfying (5.12). Given a particle $i \in A_{t,x}$ we define

$$ \begin{aligned} s(i) &= \max\{s \le t : (s, \xi(s, i)) \in T_{t,x}^{-}\}, \\ \lambda(i) &= \min\{k : \text{ for all } s(i) \le s \le t, (s, \xi(s, i)) \in T_{t,x+k}^{-}\}. \end{aligned} $$

Finally we define the variable $d_{t,x}$ by

$$ d_{t,x} = \inf\{\lambda(i), i \in A_{t,x}\} \qquad (5.13) $$

if $(t, x)$ is bad, and $d_{t,x} = 0$ if $(t, x)$ is not bad. We stress that the variables $d_{t,x}$ are deterministically equal at 0 or larger than $l$, measurable with respect to $\xi$, and identically distributed (but off course not independent).

**Lemma 5.2.** There exists $c > 0$ so that, for any $k \ge l$,

$$ \mathbb{P}_1(d_{0,0} \ge k) \le e^{-ck}. \qquad (5.14) $$

*Proof.* We first establish the exponential decay for large $k$. For $k \ge l$, using a union bound,

$$ \mathbb{P}_1(d_{0,0} \ge k) \le \sum_{i \ge l} \mathbb{P}_1(\exists s \le 0 \text{ s.t. } \xi(s, i) \notin T_{0,k-1}^{-}, \exists t \le s \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}). \qquad (5.15) $$
For each $i \ge l$, $(\xi(s, i))_{s \le 0}$ is a simple continuous time random walk so that there exists some constant $c_1 > 0$ so that $P_1(\exists t \le 0 \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}) \le e^{-c_1 i}$. The sum (5.15) is decomposed in two parts. First, there exists $c_2 > 0$ such that, for $k$ large enough,

$$ \sum_{i \ge k} P_1(\exists s \le 0 \text{ s.t. } \xi(s, i) \notin T_{0,k-1}^{-}, \exists t \le s \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}) \le \sum_{i \ge k} P_1(\exists t \le 0 \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}) \le e^{-c_2 k}. $$

Second, let us consider an index $l \le i \le k - 1$. Using Markov's property at the hitting time of the complementary of $T_{0,k-1}^{-}$ together with the fact the interchange process is considered under its invariant measure, we obtain

$$ P_1(\exists s \le 0 \text{ s.t. } \xi(s, i) \notin T_{0,k-1}^{-}, \exists t \le s \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}) \le P_1(\exists t \le 0 \text{ s.t. } \xi(t, k-1) \in T_{0,0}^{-}), $$

so that

$$ \sum_{l \le i \le k-1} P_1(\exists s \le 0 \text{ s.t. } \xi(s, i) \notin T_{0,k-1}^{-}, \exists t \le s \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}) \le k e^{-c_1 k}. $$

We thus obtain (5.14) for $k$ large enough.

As $P_1(d_{0,0} \ge k)$ is non-increasing with $k \ge l$, it remains to prove that $P_1(d_{0,0} \ge l) < 1$ to complete the proof, or equivalently that $P_1(d_{0,0} = 0) > 0$. We already know that for some $K$ large enough $\sum_{i \ge K} P_1(\exists t \le 0 \text{ s.t. } \xi(t, i) \in T_{0,0}^{-}) < 1$. We consider a time $s < 0$ so that $-\frac{\nu}{4}s > K$. Using Markov's property at time $s$ together with the fact the interchange process is considered under its invariant measure, we obtain

$$ \begin{aligned} P_1(d_{0,0} = 0) &\ge P_1(U(s,l) = U(0,l), \{\exists i \ge l \exists t \le s \text{ s.t. } \xi(s,i) \ge l \text{ and } \xi(t,i) \in T_{0,0}^{-}\}^c) \\ &\ge P_1(U(s,l) = U(0,l)) (1 - P_1(\exists i \ge K \exists t \le 0 \text{ s.t. } \xi(t,i) \in T_{0,0}^{-})) > 0, \end{aligned} $$

where $U(s,l) = U(0,l)$ means that the clock between the sites $l-1$ and $l$ has not rung during the time interval $[0, s]$. That concludes the proof. $\square$

**Proof of Proposition 5.1.** The proof is made of two steps.

In a first step, we fix $l \ge 1$ large enough, and we prove that there exists some constant $c_0 > 0$ such that, for all $n$ large enough,

$$ P_0(\#\{i \le n, (i, X_i) \text{ is } l\text{-good}\} < c_0 n) \le \frac{1}{n^{q+1}}, \quad (5.16) $$

with $l$-good as defined in (5.10-5.11). We observe that

$$ P_0(\#\{i \le n, (i, X_i) \text{ is good}\} \le c_0 n) \le P_0\left(\#\{i \le n, (i, X_i) \text{ is good}\} \le c_0 n, X_n \ge \frac{\nu}{2}n\right) + P_0\left(X_n \le \frac{\nu}{2}n\right). $$

By Proposition 3.3, the second term is bounded by $P_0(X_n \le \frac{\nu}{2}n) \le e^{-\phi_n^{1/4}} \le 1/n^{q+2}$, where the second inequality is valid for $n$ large enough. We thus need a bound on the first term.

Let us consider a deterministic trajectory $(j, Y_j)_{0 \le j \le n}$ such that $Y_0 = 0$, $Y_{j+1} - Y_j = \pm 1$ for all $0 \le j \le n-1$, and $Y_n \ge \frac{\nu}{2}n$. We first describe how to create two trajectories of boxes of size $l$, called $\mathcal{R}$ and $\mathcal{T}$ below, starting from the trajectory of points $(j, Y_j)_{0 \le j \le n}$. Our constructions are illustrated on Figure 4. For $j \ge 0$, we define

$$ t_j = \inf \left\{ k \ge 0 \text{ s.t. } Y_k \ge j + \frac{\nu}{4}k \right\}, $$

and we remark that, on the event $\{X_n \ge \frac{\nu}{2}n\}$, $t_i \le n$ for all $i \le \frac{\nu}{4}n$. We define a space-time parallelogram, or box, by its opposite sides,

$$ [(0,0), (n, \frac{\nu}{4}n)] \quad \text{and} \quad [(0, \frac{\nu}{4}n), (n, \frac{\nu}{2}n)], $$
and we cut it into boxes of size $l$: writing $M = \lfloor \frac{n}{l} \rfloor$ and $N = \lfloor \frac{\nu n}{4l} \rfloor$, we consider $M \times N$ boxes $C(i, j)$, with $i \in \{1, \dots, M\}$ and $j \in \{1, \dots, N\}$, where $C(i, j)$ is the box defined by the two opposite sides

$$ \left[ \left( (i-1)l, (j-1)l + \frac{\nu}{4}(i-1)l \right), \left( il, (j-1)l + \frac{\nu}{4}il \right) \right] \quad \text{and} \quad \left[ \left( (i-1)l, jl + \frac{\nu}{4}(i-1)l \right), \left( il, jl + \frac{\nu}{4}il \right) \right]. $$

We denote by $\mathcal{R} \subset \{1, \dots, M\} \times \{1, \dots, N\}$ the subset of indices $(i, j)$, such that $(i, j) \in \mathcal{R}$ if and only if the box $C(i, j)$ contains at least one point $(t_k, X_{t_k})$ for some $k \le \frac{\nu}{4}n$. We observe the following:

1. For any $1 \le j \le N$, there exists at least one $i \in \{1, \dots, M\}$ such that $C(i, j) \in \mathcal{R}$.

2. For any $1 \le i \le M$, there are at most two $j \in \{1, \dots, N\}$ such that $C(i, j) \in \mathcal{R}$, and in that case the two indices $j$ are consecutive.

It makes thus sense to consider the subset $\mathcal{T} \subset \mathcal{R}$ such that $(i, j) \in \mathcal{T}$ if $j$ is odd and if $i$ is the smallest number so that $(i, j) \in \mathcal{R}$. The cardinal of $\mathcal{T}$ is $N/2$ (assuming $N$ even, the other case being analogous) and the set $\mathcal{T}$ can be described as

$$ \mathcal{T} = \{(i_1, 1), (i_2, 3), \dots, (i_{N/2}, N/2)\} \quad \text{with} \quad 1 \le i_1 < i_2 < \dots < i_{N/2} \le M. $$

<figure><img src="image_6.png" /><figcaption>Figure 4: Construction of the trajectories of blocks, $\mathcal{R}$ and $\mathcal{T}$, from a deterministic trajectory $(k, Y_k)_{0 \le k \le n}$ satisfying $Y_0 = 0$ and $Y_n \ge \frac{\nu}{2}n$. The trajectory $\mathcal{R}$ is marked by the shaded boxes, and the trajectory $\mathcal{T} \subset \mathcal{R}$ by the darker boxes. A box $C(i, j)$ is represented by the hatched region.</figcaption></figure>

Recall now the definition (5.12) of bad points. A block $C(i, j)$ is said to be bad if at least one point in $C(i, j)$ is bad. For any block $C(i, j)$, we define the variable $E(i, j)$ by $E(i, j) = 0$ if the block is not bad, and by

$$ E(i, j) = \inf\{m \ge 1 : \exists (t, x) \in C(i, j) \text{ bad s.t. } \exists p \in A_{t,x} \text{ s.t. } x + \lambda(p) \in \tilde{T}_{i,j+m}^{-} \} \quad (5.17) $$
if the block is bad, where

$$ \tilde{T}_{i,j}^{-} = T_{il,jl+\frac{v}{4}il}^{-} $$

We note that $E(i, j) \ge 1$ if and only if the block $C(i, j)$ is bad. The crucial observation is that, for any $m \ge 1$, the event $\{E(i, j) = m\}$ is measurable with respect to

$$ \sigma(U(t,x) : (t,x) \in \tilde{T}_{i,j+m}^{-} \setminus \tilde{T}_{i,j-1}^{-}). \qquad (5.18) $$

Moreover, using a union bound together with (5.14), we get that there exists $c_1 > 0$ such that, for any $m \ge 1$,

$$ \mathbb{P}(E(i, j) \ge m) \le e^{-c_1 ml}. \qquad (5.19) $$

Let us now assume that $0 < c_0 \le \frac{v}{16l}$. We have

$$ \{\#\{i \le n, (i, X_i) \text{ is good}\} \le c_0 n, X_n \ge \frac{v}{2}n\} \subset \{\#\{(i, j) \in \mathcal{T}((i, X_i)_{1\le i \le n}) \text{ s.t. } C(i, j) \text{ is bad}\} \ge \frac{N}{4}\}, $$

where the notation $\mathcal{T}((i, X_i)_{1\le i \le n})$ means that the trajectory of blocks $\mathcal{T}$ is built from the trajectory $(i, X_i)_{1\le i \le n}$. There exists $c_2 > 0$ (independent of $n$) so that the number of $\mathcal{T}$ trajectories is bounded by $e^{c_2 \frac{n}{T}}$. Therefore

$$ P_0 \left( \left\{ \#\{i \le n, (i, X_i) \text{ is good}\} \le c_0 n, X_n \ge \frac{v}{2}n \right\} \right) \\ \le e^{c_2 \frac{n}{T}} \max_{\mathcal{T}} P_0 \left( \#\{(i, j) \in \mathcal{T} \text{ s.t. } C(i, j) \text{ is bad}\} \ge \frac{N}{4} \right), $$

where the maximum runs over all block trajectories $\mathcal{T}$ built from trajectories $(j, Y_j)_{0\le j \le n}$. Moreover, there exists $c_3 > 0$ (independent of $n$) so that, given $\mathcal{T}$, there are at most $e^{c_3 \frac{n}{T}}$ ways to extract half of the blocks of $\mathcal{T}$. Thus

$$ P_0 \left( \#\{(i, j) \in \mathcal{T} \text{ s.t. } C(i, j) \text{ is bad}\} \ge \frac{N}{4} \right) \le e^{c_3 \frac{n}{T}} \max_{\mathcal{T}' \subset \mathcal{T}, \#\mathcal{T}' = N/4} P_0 \left( \forall (i, j) \in \mathcal{T}', C(i, j) \text{ is bad} \right) $$

(we assume that $N/4$ is an integer for the ease of notations, the other cases are analogous).

To get a bound on the maximum in this last expression, we need some extra notations. Let $j_1 < \dots < j_{N/4}$ be the set of points such that $(i, j_k) \in \mathcal{T}'$ for some unique $i$. We denote by $\Phi$ a partition of $\{j_1, \dots, j_{N/4}\}$ in non-empty intervals, by which we mean non-empty sets of the type $[a, b] \cap \{j_1, \dots, j_{N/4}\}$, for $[a, b]$ an interval of $\mathbb{R}$. We denote by $|\Phi|$ the number of sets in $\Phi$, by $\phi_k$ the sets of $\Phi$, by $|\phi_k| \ge 1$ the cardinal of each set, by $l_k$ the smallest integer in the set $\phi_k$, by $r_k$ the largest integer in the set $\phi_k$. Moreover, to lighten the notations, let us simply write $C(j_k)$ (resp. $E(j_k)$) for $C(i(j_k), j_k)$ (resp. $E(i(j_k), j_k)$), where $i(j_k)$ is the number such that $(i(j_k), j_k) \in \mathcal{T}'$ for a given $j_k \in \{j_1, \dots, j_{N/4}\}$. Then

$$ \begin{aligned} \mathbb{P}(\forall (i,j) \in \mathcal{T}', C(i,j) \text{ is bad}) &= \mathbb{P}(C(j_1), \dots, C(j_{N/4}) \text{ are bad}) \\ &\le \sum_{\Phi} \mathbb{P}(r_1 - l_1 + 1 \le E(l_1) \le l_2 - l_1 - 1, r_2 - l_2 + 1 \le E(l_2) \le l_3 - l_2 - 1, \dots, E(l_{|\Phi|}) \ge r_{|\Phi|} - l_{|\Phi|} + 1) \\ &= \sum_{\Phi} \mathbb{P}(r_1 - l_1 + 1 \le E(l_1) \le l_2 - l_1 - 1) \mathbb{P}(r_2 - l_2 + 1 \le E(l_2) \le l_3 - l_2 - 1) \cdots \mathbb{P}(E(l_{|\Phi|})) \ge r_{|\Phi|} - l_{|\Phi|} + 1) \\ &\le \sum_{\Phi} \mathbb{P}(r_1 - l_1 + 1 \le E(l_1)) \mathbb{P}(r_2 - l_2 + 1 \le E(l_2)) \cdots \mathbb{P}(E(l_{|\Phi|})) \ge r_{|\Phi|} - l_{|\Phi|} + 1) \\ &\le \sum_{\Phi} e^{-c_1 l \sum_{i=1}^{|\Phi|} |\phi_i|} \le 2^{N/4} e^{-c_1 l N/4}, \end{aligned} $$
where the equality in front of the third line follows from (5.18), where the inequality in front of the fourth line follows from (5.19) together with the rough estimates $|r_k - l_k + 1| \ge |\phi_k|$ for any $0 \le k \le |\Phi|$, and where the last estimates follows from the fact that the number of partitions $\Phi$ in intervals is bounded by $2^{N/4}$. Since $N \ge c_5 n/l$, we obtain finally that, for some constant $c_6 < +\infty$,

$$P_0(\#\{i \le n, (i, X_i) \text{ is good}\} \le c_0 n, X_n \ge \frac{\nu}{2}n) \le e^{c_6 \frac{n}{l}} e^{-c_5 n}.$$

By taking $l$ large enough, this is bounded by $1/n^{q+2}$ for $n$ large enough, from where (5.16) follows.

We now turn to the second step of the proof, and derive the result from (5.16). Let $g_1$ be the first good time, i.e. the first time such that $(g_1, X_{g_1})$ is good, and define then, by iteration on $i \ge 1$, $g_{i+1}$ as the first good time after $g_i + l$. By (5.16), the sequence $(g_i)_{i \ge 1}$ is almost surely infinite. Remark that $(g_i)_{i \ge 1}$ are stopping times with respect to the filtration

$$\mathcal{F}_k = \sigma((X_i)_{i \le k}, (\xi(u, x))_{u \le k, x \in \mathbb{Z}}), \quad k \ge 1. \qquad (5.20)$$

There exists a constant $\epsilon > 0$ such that, for any $i \ge 1$,

$$P_0(g_i + l \text{ is a candidate} | \mathcal{F}_{g_{i-1}+l}) \\
\ge P_0(U(g_i + l, X_{g_i} + l) = U(g_i, X_{g_i} + l), X_{g_{i+1}} - X_{g_i} = 1, \dots = X_{g_{i+l+1}} - X_{g_i+l} = 1 | \mathcal{F}_{g_{i-1}+l}) \\
\ge \kappa^{l+1} P_0(U(l, 0) = U(0, 0)) \ge \epsilon,$$

where we have used the ellipticity to bound the conditional probability that the walker does $l+1$ steps to the right. Let us denote by $(Z_i)_{i \ge 1}$ a sequence of variables with values in $\{0, 1\}$ such that $Z_i = 1$ if $g_i + l$ is candidate, and $Z_i = 0$ otherwise. The above implies that $P_0(Z_k = 1 | Z_1, \dots, Z_{k-1}) \ge \epsilon$. Therefore, for $c_7 > 0$ small enough, there exists $c_8 > 0$ so that

$$P_0(\#\{n \le g_i + l : (n, X_n) \text{ is candidate}\} \le c_7 i) \le P_0\left(\sum_{k=1}^{i} Z_k \le c_7 i\right) \le e^{-c_8 i}. \quad (5.21)$$

We now compute

$$P_0(\#\{i \le n : (i, X_i) \text{ candidate}\} \le cn) \le P_0(\#\{i \le n : (i, X_i) \text{ candidate}\} \le cn, \#\{i \le n : (i, X_i) \text{ good}\} \ge c_0 n) + P_0(\#\{i \le n : (i, X_i) \text{ good}\} < c_0 n).$$

The second term is bounded by $1/n^{q+1}$ thanks to (5.16). For the first one, we observe that on the event $\#\{i \le n : (i, X_i) \text{ good}\} \ge c_0 n$, there exists $c_9 > 0$ such that $g_{c_9 n} \le n$. Therefore, if $c > 0$ is taken so that $c \le c_7 c_9$, we obtain

$$P_0(\#\{i \le n : (i, X_i) \text{ candidate}\} \le cn, \#\{i \le n : (i, X_i) \text{ good}\} \ge c_0 n) \le P_0(\#\{i \le g_{c_9 n} : (i, X_i) \text{ candidate}\} \le cn) \le e^{-c_8 c_9 n}$$

thanks to (5.21).

□

## 5.2 Proof that $(0, X_0)$ satisfies (5.6-5.7) with positive probability

We prove here that, with positive probability, the walker lives in $T_{0,0}^+$ and does not visit any of the particles that were initially at its left. We introduce

$$D = \inf \left\{ n \ge 0 \text{ s.t. } X_n < X_0 + \frac{\nu}{4} n \right\}, \qquad (5.22)$$

$$F = \inf \left\{ n \ge 0, \text{ s.t. } \exists x \ge X_0 + \frac{\nu}{4} n, \xi(0, \mu(n, x)) < X_0 \right\}, \qquad (5.23)$$
with the convention that $\inf \emptyset = +\infty$. Remark that $F$ is defined as a discrete time and that $D, F$ are stopping times with respect to the filtration $(\mathcal{F}_k)_{k \ge 0}$ defined in (5.20). The variable $D$ can be considered as a function of $X$, and $F$ as a function of $\xi$ and $X_0$ only. Let $H$ be the infimum of these two stopping times:

$$H = D \wedge F.$$

We claim that

$$P_0(H = +\infty) = P_0(D = F = +\infty) > 0. \qquad (5.24)$$

*Proof of (5.24).* In this proof, as $X_0 = 0$ a.s., we consider $F$ as a function of $\xi$ only, i.e. $F = F(\xi, 0)$. As $\liminf X_n/n > \nu P_0$-a.s., we deduce by monotonicity that

$$\lim_{L \to +\infty} P_0 \left( X_n \ge \frac{\nu}{4}(n-L), \forall n \ge 0 \right) = 1. \qquad (5.25)$$

Using the same type of computation as for (5.14), we obtain that

$$P_1(F = +\infty) > 0,$$

and we choose $L$ large enough so that (recall (5.25))

$$P_0 \left( X_n \ge \frac{\nu}{4}(n-L), \forall n \ge 0 \right) > 1 - \frac{P_1(F = +\infty)}{2}. \qquad (5.26)$$

Finally, for $L'$ large enough so that $L' - \nu/4L' \ge L$,

$$\begin{aligned} P_0(H = +\infty) &\ge \mathbb{P} \times P_{0,0}^{\omega}(F = +\infty, X_1 - X_0 = 1, \dots = X_{L'} - X_{L'-1} = 1, X_n \ge \frac{\nu}{4}n, \forall n \ge L') \\ &\ge \mathbb{E} \left( F = +\infty, P_{0,0}^{\omega}(X_1 - X_0 = 1, \dots = X_{L'} - X_{L'-1} = 1) P_{L',L'}^{\omega}(X_n \ge \frac{\nu}{4}(n-L), \forall n \ge 0) \right) \\ &\ge \kappa^{L'} \mathbb{E} \left( F = +\infty, P_{L',L'}^{\omega}(X_n \ge \frac{\nu}{4}(n-L), \forall n \ge 0) \right), \end{aligned}$$

where we have used ellipticity to get the last line, and where $\kappa$ is defined in (5.1). As the law of the environment is invariant by translation, $\mathbb{P} \times P_{L',L'}^{\omega}(X_n \ge \frac{\nu}{4}(n-L), \forall n \ge 0)$ is equal to $P_0(X_n \ge \frac{\nu}{4}(n-L), \forall n \ge 0)$, so that finally, using (5.26),

$$P_0(H = +\infty) \ge \kappa^{L'} \frac{P_1(F = +\infty)}{2} > 0.$$

□

## 5.3 Building the first renewal point

We define, for $n \ge 0$, the shift $\theta_n$ on the space $\Xi \times \mathcal{P}$ by $\theta_n(\xi, x) = (\xi', x')$, where

$$\begin{aligned} \xi'(t, y) &= \xi(t + n, y), \quad (t, y) \in \mathbb{R}^+ \times \mathbb{Z}, \\ x'_i &= x_{n+i}, \quad i \ge 0, \end{aligned}$$

and we consider the increasing sequence of stopping times with respect to the filtration $(\mathcal{F}_k)_{k \ge 1}$ (see (5.20)) defined by

$$\begin{aligned} S_0 &= 1, && \text{and for } k \ge 1, \\ R_k &= \inf\{n \ge S_{k-1} \text{ s.t. } (n, X_n) \text{ is a candidate}\}, \\ S_k &= H \circ \theta_{R_k} + R_k. \end{aligned}$$

Define

$$K = \inf\{k \ge 1 \text{ s.t. } R_k < +\infty \text{ and } S_k = +\infty\}. \qquad (5.27)$$
Random walk driven by the simple exclusion process

We claim that

$$P_0 - a.s., \quad K < +\infty, \qquad (5.28)$$

so that $\tau := R_K$ is well defined and moreover $\tau$ is a renewal time in the sense that it satisfies (5.4)-(5.7).

*Proof of (5.28).* We first deduce from Lemma 5.1 that

$$P_0 - a.s., \quad \forall k \ge 0, \quad \{S_k < +\infty\} \subset \{R_{k+1} < +\infty\},$$

so that

$$P_0(R_{k+1} < +\infty) = P_0(R_k < +\infty) - P_0(R_k < +\infty, S_k = +\infty). \qquad (5.29)$$

To compute the last term of (5.29), we use first that $P^\omega$ is Markovian:

$$P_0(R_k < +\infty, S_k = +\infty) = \sum_{x \in \mathbb{Z}, i \ge 0} P_0(R_k = i, X_{R_k} = x, S_k = +\infty) \qquad (5.30) \\ = \sum_{x \in \mathbb{Z}, i \ge 0} \mathrm{E}_1 \left( \mathrm{E}_2 \left( P_{0,0}^{\omega}(R_k = i, X_{R_k} = x) P_{i,x}^{\omega}(H(\theta_i \xi, X) = +\infty) \right) \right),$$

where $\mathrm{E}_1(\text{resp. } \mathrm{E}_2)$ denote the expectation with respect to $\mathbb{P}_1(\text{resp. } \mathbb{P}_2)$. For any fixed $\xi$, let $V_{i,x}$ be the set of labels of particles that are strictly at the left of $x$ at time $i$, i.e.

$$V_{i,x} = \{\mu(i, y), y < x\}.$$

Note that given $\xi$, $P_{0,0}^{\omega}(R_k = i, X_{R_k} = x)$ is measurable with respect to $\sigma(\nu(\mu), \mu \in V_{i,x})$ while $P_{i,x}^{\omega}(H(\theta_i \xi, X) = +\infty)$ is measurable with respect to $\sigma(\nu(\mu), \mu \notin V_{i,x})$. These two variables are thus independent under $\mathbb{P}_2$:

$$\mathrm{E}_2 \left( P_{0,0}^{\omega}(R_k = i, X_{R_k} = x) P_{i,x}^{\omega}(H = +\infty) \right) = \mathrm{E}_2 \left( P_{0,0}^{\omega}(R_k = i, X_{R_k} = x) \right) \mathrm{E}_2 \left( P_{i,x}^{\omega}(H(\theta_i \xi, X) = +\infty) \right).$$

Finally $\mathrm{E}_2(P_{0,0}^{\omega}(R_k = i, X_{R_k} = x))$ is measurable with respect to $\sigma(U(s, y), s \le i, y \in \mathbb{Z})$ and $\mathrm{E}_2(P_{i,x}^{\omega}(H(\theta_i \xi, X) = +\infty))$ is measurable with respect to $\sigma(U(s, y), s \ge i, y \in \mathbb{Z})$. These two variables are thus independent under $\mathbb{P}_1$ and finally

$$P_0(R_k < +\infty, S_k = +\infty) = \sum_{x \in \mathbb{Z}, i \ge 0} P_0(R_k = i, X_{R_k} = x) P_{i,x}(H(\theta_i \xi, X) = +\infty).$$

As the law of environment is invariant by space-time translation, for all $x \in \mathbb{Z}$ and $i \ge 0$, $P_{i,x}(H(\theta_i \xi, X) = +\infty) = P_0(H = +\infty)$ so that

$$P_0(R_k < +\infty, S_k = +\infty) = P_0(R_k < +\infty)P_0(H = +\infty),$$

and going back to (5.29),

$$P_0(R_{k+1} < +\infty) \le P_0(R_k < +\infty)(1 - P_0(H = +\infty)). \qquad (5.31)$$

By iteration, we conclude the proof of (5.28). □

## 5.4 Defining a sequence of renewal points by iteration

Remark that $\tau_1$ is a function of $X$ and $\xi$ so that, in order to iterate the construction, we study the law of these two processes after a time $\tau_1$. That is the purpose of the next proposition.

**Proposition 5.3.** The process and the environment after the first renewal time, $(X_{\tau_1+n} - X_{\tau_1})_{n \ge 0}$, $(\xi(\tau_1 + t, x))_{t \ge 0, x \in \mathbb{Z}}$, are independent from $(X_{n \wedge \tau_1})_{n \ge 0}$, $(\xi(t \wedge \tau_1, x))_{t \ge 0, x \in \mathbb{Z}}$ and have same law as $(X_n)_{n \ge 0}$, $(\xi(t, x))_{t \ge 0, x \in \mathbb{Z}}$ under $P_0(\cdot | H = +\infty)$.
*Proof.* This type of proof is quite usual (see e.g. [23] for the case of a static environment). We adapt it explicitly to our case in order to be exhaustive. We define

$$ \mathcal{G}_1 = \sigma((X_{n \wedge \tau_1})_{n \ge 0}, (\xi(s, x))_{s \le \tau_1, x \in \mathbb{Z}}). $$

We have to prove that for any bounded functions $\phi_1, \phi_2$,

$$ \begin{aligned} E_0(\phi_1((X_{\tau_1+n} - X_{\tau_1})_{n \ge 0})\phi_2(\xi(\tau_1 + t, x)_{x \in \mathbb{Z}, t \ge 0})|\mathcal{G}_1) \\ = E_0(\phi_1((X_t)_{t \ge 0})\phi_2((\xi(t, x))_{x \in \mathbb{Z}, t \ge 0})|H = +\infty). \end{aligned} \quad (5.32) $$

Consider the variables $\psi_1((X_{n \wedge \tau_1})_{n \ge 0})$ and $\psi_2((\xi(s, x))_{s \le \tau_1, x \in \mathbb{Z}})$, where $\psi_1$ and $\psi_2$ are bounded functions. If $Z$ is some process and $t$ some time (possibly random), the process stopped at time $t$ is denoted $Z^t$: for any $s \ge 0$, $Z_s^t = Z_{s \wedge t}$. Using the same arguments as in the proof (5.30)-(5.31), we deduce that (we write explicitly the arguments of the functions only when they change from line to line)

$$ \begin{aligned} & E_0(\phi_1\phi_2\psi_1\psi_2) \\ &= \sum_{k,x,n} E_0(\phi_1(\theta_n X - X_n)\phi_2(\theta_n \xi)\psi_1(X^n)\psi_2(\xi^n), R_k = n, X_{R_k} = x, H \circ \theta_n = +\infty) \\ &= \sum_{k,x,n} \mathrm{E}^1\left(\phi_2\psi_2\mathrm{E}^2\left[E_{0,0}^{\omega}(\psi_1, R_k = n, X_{R_k} = x)E_{n,x}^{\omega}(\phi_1(X), H(\theta_n\xi, X) = +\infty)\right]\right) \\ &= \sum_{k,x,n} \mathrm{E}^1\left(\psi_2\mathrm{E}^2\left[E_{0,0}^{\omega}(\psi_1, R_k = n, X_{R_k} = x)\right]\phi_2\mathrm{E}^2\left[E_{n,x}^{\omega}(\phi_1(X), H(\theta_n\xi, X) = +\infty)\right]\right) \\ &= \sum_{k,x,n} \mathrm{E}^1\left(\psi_2\mathrm{E}^2\left[E_{0,0}^{\omega}(\psi_1, R_k = n, X_{R_k} = x)\right]\right)\mathrm{E}^1\left(\phi_2\mathrm{E}^2\left[E_{n,x}^{\omega}\left(\left(\phi_1(X), H(\theta_n\xi, X) = +\infty)\right)\right]\right)\right) \\ &= \sum_{k,x,n} \mathrm{E}^1\left(\psi_2\mathrm{E}^2\left[E_{0,0}^{\omega}(\psi_1, R_k = n, X_{R_k} = x)\right]\right)E_{n,x}(\phi_1\phi_2(\theta_n\xi), H(\theta_n\xi, X) = +\infty) \\ &= E_0(\phi_1\phi_2|H = +\infty)\sum_{k,x,n} \mathrm{E}^1\left(\psi_2\mathrm{E}^2\left[E_{0,0}^{\omega}(\psi_1, R_k = n, X_{R_k} = x)\right]\right)P_0(H = +\infty) \\ &= E_0(\phi_1\phi_2|H = +\infty)E(\psi_1(X^{\tau_1})\psi_2(\xi^{\tau_1})), \end{aligned} $$

where the last line is obtained from the previous one by taking $\phi_1 = \phi_2 = 1$ in the same computation. This concludes the proof of (5.32) and thus the proof of Proposition 5.3. $\square$

As $P_0(H = +\infty) > 0$, $\tau$ is also defined and finite a.s. under $P_0(\cdot|H = +\infty)$. We can thus define $\tau_2$, the second renewal time, by $\tau_2 = \tau_1 + \tau_1((X_{n+\tau_1} - X_{\tau_1})_{n \ge 0}, (\xi(n + \tau_1, x))_{t \ge 0, x \in \mathbb{Z}})$ and, by iteration, we define in the same way an increasing sequence of renewal times $(\tau_k)_{k \ge 1}$ that are finite $P_0$-a.s.

The interest of this construction lies in the following

**Proposition 5.4.** Under $P_0$, $((X_{\tau_k+\cdot} - X_{\tau_k})_{0 \le t \le \tau_{k+1}-\tau_k}, \tau_{k+1}-\tau_k)_{k \ge 1}$ are i.i.d. with the same law as $((X_t)_{0 \le t \le \tau_1}, \tau_1)$ under $P_0(\cdot|H = +\infty)$.

The proof follows by induction from Proposition 5.3.

**Corollary 5.5.** Under $P_0$, $(X_{\tau_{k+1}} - X_{\tau_k}, \tau_{k+1} - \tau_k)_{k \ge 1}$ are positive i.i.d. random variables with the same law as $(X_{\tau_1}, \tau_1)$ under $P_0(\cdot|H = +\infty)$.

## 5.5 Control on the moments of $\tau_1$ and conclusion of the proof

**Proposition 5.6.** For $n \ge 0$ large enough,

$$ P_0(\tau_1 > n) \le \frac{1}{n^3}. $$
Random walk driven by the simple exclusion process

In particular, as $P_0(H = +\infty) > 0$, this implies

$$E_0(\tau_1|H = +\infty) < +\infty \quad \text{and} \quad E_0(\tau_1^2|H = +\infty) < +\infty.$$

*Proof.* First observe that for any $n \in \mathbb{N}$,

$$P_0(\tau > n) \le P_0(\tau > n, K < \ln^2 n) + P_0(K \ge \ln^2 n), \quad (5.33)$$

with $K$ defined in (5.27). As $K$ is distributed under $P_0$ like a geometric random variable with success parameter $P_0(H = +\infty) > 0$ (see (5.24)), we obtain that for $n$ large enough

$$P_0(K \ge \ln^2 n) \le \frac{1}{n^4}.$$

In order to deal with the first term in the right had side of (5.33), we decompose

$$P_0(\tau > n, K < \ln^2 t) \le P_0(\tau > n, \{\forall 1 \le k < K, S_k - R_k \le \sqrt{n}\}, K \le \ln^2 n) \\ + P_0(\tau > n, \{\exists 1 \le k < K, S_k - R_k > \sqrt{n}\}, K \le \ln^2 n), \quad (5.34)$$

and again we have to control two terms. For the first one, note that

$$P_0(\tau > n, \{\forall 1 \le k < K, S_k - R_k \le \sqrt{n}\}, K \le \ln^2 n) \le P_0(\#\{i \le n, (i, X_i) \text{ is a candidate}\} \le \sqrt{n} \ln^2 n),$$

so that, using Proposition 5.1, we obtain that for $n$ large enough,

$$P_0(\tau > n, \{\forall 1 \le k < K, S_k - R_k \le \sqrt{n}\}, K \le \ln^2 n) \le \frac{1}{n^4}.$$

For the second term in (5.34), we observe that

$$P_0(\tau > n, \{\exists 1 \le k < K, S_k - R_k > \sqrt{n}\}, K \le \ln^2 n) \le \sum_{k=1}^{\ln^2 n} P_0(R_k < +\infty, \sqrt{n} < S_k - R_k < +\infty).$$

We study each term of the sum in the same way. Fixing some integer $k$ such that $1 \le k \le \ln^2 n$,

$$P_0(R_k < +\infty, \sqrt{n} < S_k - R_k < +\infty) = \sum_{x \in \mathbb{Z}, i \ge 0} P_0(R_k = i, X_{R_k} = x, \sqrt{n} < S_k - R_k < +\infty) \\ = \sum_{x \in \mathbb{Z}, i \ge 0} E_1 \left( E_2 \left( P_{0,0}^{\omega}(R_k = i, X_{R_k} = x) P_{i,x}^{\omega}(\sqrt{n} < H(\theta_i \xi, X) < +\infty) \right) \right).$$

Given $\xi$ and $\nu$, for all $i \ge 0$ and $x \in \mathbb{Z}$,

$$P_{i,x}^{\omega}(\sqrt{n} < H(\theta_i \xi, X) < +\infty) \le P_{i,x}^{\omega}(\sqrt{n} < D < +\infty) \mathbb{1}_{\{F(\theta_i \xi, x) = +\infty\}} + \mathbb{1}_{\{\sqrt{n} < F(\theta_i \xi, x) < +\infty\}}. \quad (5.35)$$

We consider separately these two terms. For the first one, observe that given $\xi$, $P_{0,0}^{\omega}(R_k = i, X_{R_k} = x)$ is measurable with respect to $\sigma(\nu(\mu), \mu \in V_{i,x})$ while $P_{i,x}^{\omega}(\sqrt{n} < D < +\infty)$ is measurable with respect to $\sigma(\nu(\mu), \mu \notin V_{i,x})$. These two variables are thus independent under $P_2$:

$$\begin{aligned} & E_2(P_{0,0}^{\omega}(R_k = i, X_{R_k} = x) P_{i,x}^{\omega}(\sqrt{n} < D < +\infty)) \\ &= E_2(P_{0,0}^{\omega}(R_k = i, X_{R_k} = x)) E_2(P_{i,x}^{\omega}(\sqrt{n} < D < +\infty)). \end{aligned}$$
Random walk driven by the simple exclusion process

Observe that $E_2(P_{0,0}^\omega(R_k = i, X_{R_k} = x))$ is measurable with respect to $\sigma(U(s, y), s \le i, y \in \mathbb{Z})$ and $E_2(P_{i,x}^\omega(\sqrt{n} < D < +\infty)) 1_{\{F(\theta_i \xi, x) = +\infty\}}$ is measurable with respect to $\sigma(U(s, y), s \ge i, y \in \mathbb{Z})$. These two variables are thus independent under $\mathbb{P}_1$ and

$$ \sum_{x \in \mathbb{Z}, i \ge 0} \mathrm{E}_1(\mathrm{E}_2(P_{0,0}^\omega(R_k = i, X_{R_k} = x)) \mathrm{E}_2(P_{i,x}^\omega(\sqrt{n} < D < +\infty)) 1_{\{F(\theta_i \xi, x) = +\infty\}}) \\ = \sum_{x \in \mathbb{Z}, i \ge 0} P_0(R_k = i, X_{R_k} = x) P_{i,x}(\sqrt{n} < D < +\infty, F(\theta_i \xi, x) = +\infty). $$

As the law of environment is invariant by space-time translation, for all $x \in \mathbb{Z}$ and $i \ge 0$,

$$ P_{i,x}(\sqrt{n} < D < +\infty, F(\theta_i \xi, x) = +\infty) = P_0(\sqrt{n} < D < +\infty, F = +\infty), $$

so that

$$ \sum_{x \in \mathbb{Z}, i \ge 0} \mathbb{P} (P_{0,0}^\omega(R_k = i, X_{R_k} = x) P_{i,x}^\omega(\sqrt{n} < H(\theta_i \xi, X) < +\infty)) \\ = P_0(R_k < +\infty) P_0(\sqrt{n} < D < +\infty, F = +\infty). $$

Using Proposition 3.3 and (3.23), we obtain that, for $n$ large enough,

$$ P_0(\sqrt{n} < D < +\infty, F = +\infty) \le P_0(\exists k \ge \sqrt{n}, X_k \le X_0 + \frac{\nu}{4}k) \le \sum_{k=\sqrt{n}}^{+\infty} Ce^{-k^\alpha} + e^{-\phi_k^{1/4}} \le \frac{1}{n^4} $$

We turn to the second term in (5.35). As $1_{\{\sqrt{n}<F(\theta_i \xi, x)<+\infty\}}$ is measurable with respect to $\sigma(U(s, y), s \ge i, y \in \mathbb{Z})$ and $E_2(P_{0,0}^\omega(R_k = i, X_{R_k} = x))$ is measurable with respect to $\sigma(U(s, y), s \le i, y \in \mathbb{Z})$, these two variables are independent. Thus, using also the invariance of $P_0$ under space-time translations,

$$ \sum_{x \in \mathbb{Z}, i \ge 0} \mathrm{E}_1(1_{\{\sqrt{n}<F(\theta_i \xi, x)<+\infty\}}) \mathrm{E}_2(P_{0,0}^\omega(R_k = i, X_{R_k} = x)) = P_0(R_k < +\infty)P_0(\sqrt{n}<F<+\infty) $$

Using the same type of computations as for (5.14), we obtain that, for $n$ large enough,

$$ P_0(\sqrt{n} < F < +\infty) \le \frac{1}{n^4}. $$

That concludes the proof. □

We are now ready to conclude the proof of Theorem 1.1. For random walks in static random environments, it is well-known that the existence of a finite second moment for $\tau_2 - \tau_1$ implies a law of large numbers and an annealed central limit theorem (see [23] and [22]). The proof carries over to our case, and we recall it here for sake of completeness.

We start with the law of large numbers, i.e. point 1 of Theorem 1.1. For $n \ge 0$, $k(n)$ denotes the label of the "renewal slab" that contains $n$, i.e. the unique integer such that $\tau_{k(n)} \le n < \tau_{k(n)+1}$. We can thus control the walker via

$$ \frac{X_{\tau_{k(n)}}}{\tau_{k(n)+1}} \le \frac{X_n}{n} \le \frac{X_{\tau_{k(n)+1}}}{\tau_{k(n)}}. \qquad (5.36) $$

Rewrite the right term as

$$ \frac{X_{\tau_{k(n)+1}}}{\tau_{k(n)}} = \frac{X_{\tau_1} + \sum_{i=2}^{k(n)+1} \Delta_i}{k(n)} \frac{k(n)}{\tau_1 + \sum_{i=2}^{k(n)} (\tau_{i+1} - \tau_i)}, \qquad (5.37) $$
so that, using Proposition 5.4 and the law of large numbers, it is seen to converge $P_0$-a.s. to

$$v(\gamma) = \frac{E_0(X_{\tau_1} | H = +\infty)}{E_0(\tau_1 | H = +\infty)}, \qquad (5.38)$$

which is always well defined and positive thanks to (5.24) and Proposition 5.6. Using the same decomposition as in (5.37) to study the left term in (5.36), we obtain the law of large numbers stated in point 1 of Theorem 1.1.

We turn to the proof of point 2 of Theorem 1.1, mainly following [22]. For $j \ge 1$, define

$$Z_j = X_{\tau_{j+1}} - X_{\tau_j} - (\tau_{j+1} - \tau_j)v(\gamma).$$

These variables are i.i.d (Proposition 5.3), centered, (5.38) and admit a finite second moment (Proposition 5.6). It thus follows from Donsker's theorem that

$$\left( \frac{\sum_{i=1}^{\lfloor nt \rfloor} Z_j}{\sqrt{n}} \right)_{t \ge 0} \qquad (5.39)$$

converges in law to a Brownian motion with variance $E_0(Z_1^2)$, that is positive as $Z_1$ is not $P_0$-a.s. constant. As a consequence of Proposition 5.4, the law of large numbers and Dini's theorem,

$$P_0 - \text{a.s., } \forall T > 0, \quad \sup_{0 \le t \le T} \left| \frac{k(\lfloor tn \rfloor)}{n} - \frac{t}{E_0(\tau_2 - \tau_1)} \right|.$$

Therefore, we deduce from (5.39) that

$$\left( \frac{\sum_{i=1}^{k(\lfloor nt \rfloor)} Z_j}{\sqrt{n}} \right)_{t \ge 0} \qquad (5.40)$$

converges in law to a Brownian motion with variance $E_0((Z_1)^2)/E_0(\tau_2 - \tau_1)$. Finally, observe that $P_0$-a.s., for all $T > 0$,

$$\sup_{0 \le t \le T} \left| \frac{X_{nt} - ntv(\gamma)}{\sqrt{n}} - \frac{\sum_{j=1}^{k(\lfloor nt \rfloor)} Z_j}{\sqrt{n}} \right| \le (v(\gamma) + 1) \max_{0 \le k \le \lfloor nt \rfloor} \frac{\tau_{k+1} - \tau_k}{\sqrt{n}},$$

with the convention $\tau_0 = 0$. Let us prove that the right hand side converges to 0 as $n \to \infty$ in probability, using Proposition 5.4 and Proposition 5.6. Indeed, for any $\epsilon > 0$,

$$P_0 \left( \max_{0 \le k \le \lfloor nT \rfloor} \tau_{k+1} - \tau_k \ge \epsilon \sqrt{n} \right) \le P_0 (\tau_1 \ge \epsilon \sqrt{n}) + (nT+1) P_0 (\tau_2 - \tau_1 \ge \epsilon \sqrt{n}) \\ \le P_0 (\tau_1 \ge \epsilon \sqrt{n}) + \frac{nT+1}{\epsilon^3 n^{3/2}}$$

and the right hand side converges to 0 when $n$ goes to $+\infty$. We have thus proven that the Skorohod distance between $(\frac{X_{nt}-ntv(\gamma)}{\sqrt{n}})_{t \ge 0}$ and $(\frac{\sum_{i=1}^{k(\lfloor nt \rfloor)} Z_j}{\sqrt{n}})_{t \ge 0}$ goes to 0 in $P_0$-probability. We deduce from the convergence in law of the latter that

$$\left( \frac{X_{nt} - ntv(\gamma)}{\sqrt{n}} \right)_{t \ge 0}$$

converges in law to a Brownian motion with variance $\sigma^2 := E_0((X_{\tau_2} - X_{\tau_1})^2)/E_0(\tau_2 - \tau_1)$.
References

[1] R. Arratia: Symmetric exclusion processes: a comparison inequality and a large deviation result. *Annals of Probability* **13**(1), (1985), 53–61. MR-0770627

[2] L. Avena: Random Walks in Dynamic Random Environments. PhD thesis, 2010, http://www catalogus.leidenuniv.nl.

[3] L. Avena, F. den Hollander and F. Redig: Law of Large Numbers for a Class of Random Walks in Dynamic Random Environments. *Electronic Journal of Probability* **16**, (2011), 587–617. MR-2786643

[4] L. Avena, R. dos Santos and F. Völlering: A transient random walk driven by an exclusion process: regenerations, limit theorems and an Einstein relation. *ALEA* **10 (2)**, (2013), 693–709. MR-3108811

[5] L. Avena and P. Thomann: Continuity and Anomalous Fluctuations in Random Walks in Dynamic Random Environments: Numerics, Phase Diagrams and Conjectures. *Journal of Statistical Physics* **147 (6)**, (2012), 1041–1067. MR-2949519

[6] U. Basu, C. Maes: Mobility transition in a dynamic environment. *Journal of Physics A: Mathematical and General* **47**, (2014), 255003. MR-3224111

[7] O. Bénichou et al.: Geometry-Induced Superdiffusion in Driven Crowded Systems. *Physical Review Letters* **111**, (2013), 260601.

[8] J. Bricmont and A. Kupiainen: Random walks in asymmetric random environments. *Communications in Mathematical Physics* **142 (2)**, (1991), 345–420. MR-1137068

[9] J. Bérard, A. F. Ramirez: Fluctuations of the front in a one dimensional model for the spread of an infection. arXiv:1210.6781, 2012.

[10] J. Bricmont and A. Kupiainen: Random Walks in Space Time Mixing Environments. *Journal of Statistical Physics* **134 (5-6)**, (2009), 979–1004. MR-2518978

[11] F. Comets and O. Zeitouni: A law of large numbers for random walks in random mixing environments. *Annals of Probability* **32 (1B)**, (2004), 880–914. MR-2039946

[12] F. den Hollander, H. Kesten, V. Sidoravicius: Random walk in a high density dynamic random environment. to appear in Indagationes Mathematicae, arXiv:1305.0923, 2013. MR-3217035

[13] D. Dolgopyat, G. Keller and C. Liverani: Random walk in Markovian environment. *Annals of Probability* **36 (5)**, (2008), 1611–1998. MR-2440920

[14] R. dos Santos: Non-trivial linear bounds for a random walk driven by a simple symmetric exclusion process. *Electronic Journal of Probability* **19 (49)**, (2014), 1–18. MR-3217337

[15] T.E. Harris: Additive set-valued Markov processes and graphical methods. *Annals of Probability* **6 (3)**, (1978), 355–378. MR-0488377

[16] M. Hilário, F. den Hollander, V. Sidoravicius, R. S. dos Santos and A. Teixeira: Random Walk on Random Walks. arXiv:1401.4498, 2014.

[17] S. A. Kalikow: Generalized random walk in a random environment. *Annals of Probability*, 1981, 9 (5), 753-768. MR-0628871

[18] H. Kesten, M.V. Kozlov, F. Spitzer: A limit law for random walk in a random environment. *Compositio Mathematica* **30 (2)**, (1975), 145–168. MR-0380998

[19] T. M. Liggett: Interacting particle systems. Reprint of the 1985 Edition, Springer-Verlag, Berlin, 2005. MR-0776231

[20] F. Rassoul-Agha: The point of view of the particle on the law of large numbers for random walks in a mixing random environment. *Annals of Probability* **31 (3)**, (2003), 1441–1463. MR-1989439

[21] F. Redig and F. Völlering: Random walks in dynamic random environments: A transference principle. *Annals of Probability* **41 (5)**, (2013), 3157–3180. MR-3127878

[22] A.-S. Sznitman: Slowdown Estimates and Central Limit Theorem for Random Walks in Random Environment. *J. Eur. Math. Soc. (JEMS)* **2 (2)**, (2000), 93–143. MR-1763302

[23] A.-S. Sznitman and M. Zerner: A law of large numbers for random walks in random environment. *Annals of Probability* **27 (4)**, (1999), 1851–1869. MR-1742891
Random walk driven by the simple exclusion process

[24] O. Zeitouni: Random walks in random environment. pp. 189-312 in Lectures on Probability Theory and Statistics, Lecture Notes in Mathematics 1837, 2004. MR-2071631

**Acknowledgments.** F.H. acknowledges the grant ANR-EDNHS for financial support.