# Collisions of several walkers in recurrent random environments

Alexis Devulder, Nina Gantert, Françoise Pene

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

## To cite this version:

Alexis Devulder, Nina Gantert, Françoise Pene. Collisions of several walkers in recurrent random environments. Electronic Journal of Probability, 2018, 23, 10.1214/18-ejp192. hal-01500123v3

HAL Id: hal-01500123

https://hal.science/hal-01500123v3

Submitted on 20 Nov 2020

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_2.png" /></figure>

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

Electron. J. Probab. 23 (2018), no. 90, 1–34.
ISSN: 1083-6489 https://doi.org/10.1214/18-EJP192

# Collisions of several walkers in recurrent random environments*

Alexis Devulder†

Nina Gantert‡

Françoise Pène§

## Abstract

We consider $d$ independent walkers on $\mathbb{Z}$, $m$ of them performing simple symmetric random walk and $r = d - m$ of them performing recurrent RWRE (Sinai walk), in $I$ independent random environments. We show that the product is recurrent, almost surely, if and only if $m \le 1$ or $m = d = 2$. In the transient case with $r \ge 1$, we prove that the walkers meet infinitely often, almost surely, if and only if $m = 2$ and $r \ge I = 1$. In particular, while $I$ does not have an influence for the recurrence or transience, it does play a role for the probability to have infinitely many meetings. To obtain these statements, we prove two subtle localization results for a single walker in a recurrent random environment, which are of independent interest.

**Keywords:** random walk; random environment; collisions; recurrence; transience.

**AMS MSC 2010:** 60K37; 60G50.

Submitted to EJP on December 5, 2017, final version accepted on July 3, 2018.

## 1 Introduction and statement of the main results

Recurrence and transience of products of simple symmetric random walks on $\mathbb{Z}^d$ is well-known since the works of Pólya [30]. If the product of several walks is transient, one may ask if they meet infinitely often. It is also well-known and goes back to Dvoretzky and Erdös, see ([15], p. 367) that 3 independent simple symmetric random walks (SRW) in dimension 1 meet infinitely often almost surely while 4 walks meet only finitely often, almost surely. In fact, Pólya's original interest in recurrence/transience of simple random walk came from a question about collisions of two independent walkers on the same grid, see [31], “Two incidents”.

<footnote>*Supported by ANR MEMEMO 2 (ANR-10-BLAN-0125).</footnote>

<footnote>†Laboratoire de Mathématiques de Versailles, UVSQ, CNRS, Université Paris-Saclay, 78035 Versailles, France. E-mail: devulder@math.uvsq.fr</footnote>

<footnote>‡Technische Universität München, Fakultät für Mathematik, 85748 Garching, Germany. E-mail: gantert@ma.tum.de</footnote>

<footnote>§Université de Brest and Institut Universitaire de France, LMBA, UMR CNRS 6205, 29238 Brest cedex, France. E-mail: francoise.pene@univ-brest.fr</footnote>
The classical topic of meetings/collisions of two or more walkers walking on the same graph has found recent interest, see [26], [3], where the grid is replaced by more general graphs. It is well-known that if a graph is recurrent for simple random walk, two independent walkers do not necessarily meet infinitely often, see [26]. Since on a *transitive* recurrent graph, two independent walkers do meet infinitely often, almost surely, see [26], the “infinite collision property” describes how far the recurrent graph is from being transitive. For motivation from physics, see [6].

We investigate this question for products of recurrent random walks in random environment (RWRE) and of simple symmetric random walks on $\mathbb{Z}$. It is known already that, for any $n$, a product of $n$ independent RWRE in $n$ i.i.d. recurrent random environments is recurrent, see [36], and that $n$ independent walkers in the same recurrent random environment meet infinitely often in the origin, see [18]. Here, we consider several walkers each one performing either a Sinai walk or a simple symmetric random walk, with the additional twist that not all Sinai walkers are necessarily using the same environment.

Let $d, m, r$ be nonnegative integers such that $m + r = d \ge 1$. We consider $d$ walkers, $m$ of them performing SRW $S^{(1)}, \dots, S^{(m)}$ and the $r$ others performing random walks $Z^{(1)}, \dots, Z^{(r)}$ in $I$ independent random environments, with $I \le r$. More precisely, we consider $r$ collections of i.i.d. random variables $\omega^{(1)} := (\omega_x^{(1)})_{x \in \mathbb{Z}}, \dots, \omega^{(r)} := (\omega_x^{(r)})_{x \in \mathbb{Z}}$, taking values in $(0, 1)$ and defined on the same probability space $(\Omega, \mathcal{F}, \mathbf{P})$, such that $\omega^{(1)}, \dots, \omega^{(I)}$ are independent and such that the others are exact copies of some of these $I$ collections, i.e., for every $j \in \{I+1, \dots, r\}$, there exists an index $J_j \in \{1, \dots, I\}$ such that $\omega^{(j)} \equiv \omega^{(J_j)}$. A realization of $\omega := (\omega^{(1)}, \dots, \omega^{(r)})$ will be called an *environment*. Recall that we denote by

P the law of the environment $\omega$.

We set

$$Y_n := (S_n^{(1)}, \dots, S_n^{(m)}, Z_n^{(1)}, \dots, Z_n^{(r)}), \quad n \in \mathbb{N},$$

and make the following assumptions. Given $\omega = (\omega^{(1)}, \dots, \omega^{(r)})$ and $x \in \mathbb{Z}^d$, under $P_\omega^x$, $S^{(1)}, \dots, S^{(m)}, Z^{(1)}, \dots, Z^{(r)}$ are independent Markov chains such that $P_\omega^x(Y_0 = x) = 1$ and for all $y \in \mathbb{Z}$ and $n \in \mathbb{N}$,

$$P_{\omega}^{x}[S_{n+1}^{(i)} = y + 1|S_{n}^{(i)} = y] = \frac{1}{2} = P_{\omega}^{x}[S_{n+1}^{(i)} = y - 1|S_{n}^{(i)} = y], \quad i \in \{1, \dots, m\}, \quad (1.1)$$

$$P_{\omega}^{x}[Z_{n+1}^{(j)} = y + 1|Z_{n}^{(j)} = y] = \omega_{y}^{(j)} = 1 - P_{\omega}^{x}[Z_{n+1}^{(j)} = y - 1|Z_{n}^{(j)} = y], \quad j \in \{1, \dots, r\}. \quad (1.2)$$

We set $S^{(i)} := (S_n^{(i)})_n$ and $Z^{(j)} := (Z_n^{(j)})_n$ for every $i \in \{1, \dots, m\}$ and every $j \in \{1, \dots, r\}$. Note that, for every $j$, $Z^{(j)} = (Z_n^{(j)})_n$ is a random walk on $\mathbb{Z}$ in the environment $\omega^{(j)}$, and that the $S^{(i)}$'s are independent SRW, independent of the $Z^{(j)}$'s and of their environments. We call $P_\omega := P_\omega^0$ the *quenched law*. Here and in the sequel we write $0$ for the origin in $\mathbb{Z}^d$. We also define the *annealed law* as follows:

$$P[\cdot] := \int P_{\omega}[\cdot]P(d\omega).$$

Setting $\rho_k^{(j)} := \frac{1-\omega_k^{(j)}}{\omega_k^{(j)}}$ for $j \in \{1, \dots, r\}$ and $k \in \mathbb{Z}$, we assume moreover that there exists $\varepsilon_0 \in (0, 1/2)$ such that for every $j \in \{1, \dots, r\}$,

$$P[\omega_0^{(j)} \in [\varepsilon_0, 1-\varepsilon_0]] = 1, \quad E[\log \rho_0^{(j)}] = 0, \quad \sigma_j^2 := E[(\log \rho_0^{(j)})^2] > 0, \quad (1.3)$$

where $E$ is the expectation with respect to $P$. Under these assumptions, the $Z^{(j)}$ are RWRE, often called *Sinai's walks* due to the famous result of [33]. Solomon [34] proved the recurrence of $Z^{(j)}$ for $P$-almost every environment. We stress in particular that the
assumption $\sigma_j^2 > 0$ excludes the case of deterministic environments, hence when we say "Sinai's walk", we always refer to a random walk in a "truly" random environment.

Our first result concerns the recurrence/transience of $Y := (Y_n)_n$. Recurrence of $Y$ means that $S^{(1)}, \dots, S^{(m)}, Z^{(1)}, \dots, Z^{(r)}$ meet simultaneously at 0 infinitely often. As explained previously, this result is known for SRW (i.e. if $m = d$) since [30] and more recently for RWRE (i.e. if $r = d$, that is, if $m = 0$) in the case where the environments $\omega^{(j)}$ are independent (i.e. $I = r = d$, see [36, 18]) and in the case where the environment $\omega^{(j)}$ is the same for all the RWRE (i.e. $r = d, I = 1$, see [18]). See also [17] for related results.

**Theorem 1.1 (Recurrence/transience).** If $m \le 1$, or if $m = d = 2$, then, for P-almost every $\omega$, the random walk $Y$ is recurrent with respect to $P_\omega^0$. Otherwise, for P-almost every $\omega$, the random walk $Y$ is transient with respect to $P_\omega^0$.

In particular, a product of two recurrent RWRE and one SRW is recurrent, while a product of two SRW and one recurrent RWRE is transient.

When $Y$ is transient, a natural question is the study of the simultaneous meetings (i.e., collisions) of $S^{(1)}, \dots, S^{(m)}, Z^{(1)}, \dots, Z^{(r)}$. That is, we would like to extend the results of [30, 15] to the case in which some of the random walks are in random environments (when $r \ge 1$). We recall that when $r = 0$, the number of collisions is, by [30, 15], almost surely infinite if $m \le 3$ and almost surely finite when $m \ge 4$. Interestingly, compared to Theorem 1.1, the behaviour depends on whether $I = 1$ (when the RWRE are all in the same environment) or $I \ge 2$ (at least two RWRE are in independent environments).

**Theorem 1.2 (Collisions).** We distinguish the 3 following different cases.

(i) If $m \ge 3$ and $r \ge 1$, then, for P-almost every environment $\omega$,

$$P_{\omega}^{0}[S_{n}^{(1)} = S_{n}^{(2)} = S_{n}^{(3)} = Z_{n}^{(1)} \text{ infinitely often}] = 0,$$

i.e. almost surely, the walks $S^{(1)}, S^{(2)}, S^{(3)}, Z^{(1)}$ meet simultaneously only a finite number of times. A fortiori, $S^{(1)}, \dots, S^{(m)}, Z^{(1)}, \dots, Z^{(r)}$ also meet simultaneously only a finite number of times.

(ii) If $m = 2$ and $r \ge I = 1$, then for P-almost every environment $\omega$,

$$P_{\omega}^{0}[S_{n}^{(1)} = S_{n}^{(2)} = Z_{n}^{(1)} = \dots = Z_{n}^{(r)} \text{ infinitely often}] = 1,$$

i.e. almost surely, the walks $S^{(1)}, S^{(2)}, Z^{(1)}, \dots, Z^{(r)}$ meet simultaneously infinitely often.

(iii) If $m = 2$ and $r \ge I \ge 2$, then for P-almost every environment $\omega$,

$$P_{\omega}^{0}[S_{n}^{(1)} = S_{n}^{(2)} = Z_{n}^{(1)} = Z_{n}^{(2)} \text{ infinitely often}] = 0,$$

i.e. almost surely, the walks $S^{(1)}, S^{(2)}, Z^{(1)}, Z^{(2)},$ and a fortiori the walks $S^{(1)}, S^{(2)}, Z^{(1)}, \dots, Z^{(r)}$, meet simultaneously only a finite number of times.

This last result can be summarized in the following manner. Assume that $r \ge 1$ and that $Y$ is transient (i.e. $m \ge 2$ and $r \ge 1$), then $S^{(1)}, \dots, S^{(m)}, Z^{(1)}, \dots, Z^{(r)}$ meet simultaneously infinitely often if and only if $m = 2$ and $I = 1$. Hence our results cover collisions of an arbitrary number of random walks in equal or independent random (or deterministic) recurrent environments.

**Remark 1.3.** The results of Theorem 1.2 remain true if the simple random walks are replaced by random walks on $\mathbb{Z}$ with i.i.d. centered increments with finite and strictly positive variance. However, we write the proof of this theorem only in the case of SRW to keep the proof more readable and less technical.
The case of transient RWRE in the same subballistic random environment is investigated in [13] (in preparation).

In order to demonstrate Theorem 1.2, we prove the two following propositions. The first one deals with two independent recurrent RWRE in two independent environments.

**Proposition 1.4.** Assume $r \ge I \ge 2$. For every $\varepsilon > 0$, $P[Z_n^{(1)} = Z_n^{(2)}] = O((\log n)^{-2+\varepsilon})$.

The second proposition deals with $r$ independent recurrent RWRE in the same environment.

**Proposition 1.5.** Assume $r > I = 1$. For P-almost every $\omega$, there exists $c(\omega) > 0$ such that, for every $(y_1, ..., y_r) \in [(2Z)^r \cup (2Z + 1)^r]$, we have

$$ \limsup_{N \to +\infty} \frac{1}{\log N} \sum_{n=1}^{N} \frac{1}{n} \sum_{k \in \mathbb{Z}} \prod_{j=1}^{r} P_{\omega}^{y_j}[Z_n^{(j)} = k] \ge c(\omega). $$

These two propositions are based on two new localization results for recurrent RWRE, which are of independent interest. These two localization results use the potential of the environment (see (2.2)) and its valleys, these quantities were introduced by Sinai in [33] and are crucial for the investigation of the RWRE.

In the first one, stated in Proposition 4.5 and used to prove Proposition 1.4, we localize a recurrent RWRE at time $n$ with (annealed) probability $1 - (\log n)^{-2+\varepsilon}$ for $\varepsilon > 0$, whereas previous localization results for such RWRE were with probability $1 - o(1)$ (see [33], [19], [23], [4] and [16]), or with probability $1 - C(\frac{\log \log \log n}{\log \log n})^{1/2}$ for some $C > 0$ (see [1], eq. (2.23)), and they localize the RWRE inside one valley. In order to get our more precise localization probability, which is necessary to apply the Borel-Cantelli lemma in the proof of Item (iii) of Theorem 1.2, we localize the RWRE in an area of low potential defined with several valleys instead of just one. To this aim, we study and describe typical trajectories of the recurrent RWRE into these different valleys.

In our second localization result, stated in Proposition 5.1 and used to prove Proposition 1.5, we prove that for large $N \in \mathbb{N}$, with high probability on $\omega$ (for P), the quenched probability $P_{\omega}[Z_n = b(N)]$ is larger than a positive constant, uniformly for any even $n \in [N^{1-\varepsilon}, N]$ for some $\varepsilon > 0$, where $b(N)$ is the (even) bottom of some valley of the potential $V$ of a recurrent RWRE $Z$ (defined in (5.17)). In order to get this uniform probability estimate, we use a method different from that of previous localization results, based on a coupling between recurrent RWRE.

The article is organized as follows. In Section 2, we give an estimate on the return probability of recurrent RWRE, see Proposition 2.1, which is of independent interest. Our main results for direct products of walks are proved in Section 3. The proofs concerning the simultaneous meetings of random walks are based on the above-mentioned two key localization results for recurrent RWRE, proved in Sections 4 and 5.

## 2 A return probability estimate for the RWRE

We consider a recurrent one dimensional RWRE $Z = (Z_n)_n$ in the random environment $\omega = (\omega_x)_{x \in \mathbb{Z}}$, where the $\omega_x \in (0, 1)$, $x \in \mathbb{Z}$, are i.i.d. (that is, $Z_0 = 0$ and (1.2) is satisfied with $Z$ and $\omega$ instead of $Z^{(j)}$ and $\omega^{(j)}$). We assume the existence of $\varepsilon_0 \in (0, 1/2)$ such that

$$ P[\omega_0 \in [\varepsilon_0, 1 - \varepsilon_0]] = 1, \quad E[\log \rho_0] = 0, \quad E[(\log \rho_0)^2] > 0, \quad (2.1) $$

where $\rho_k := \frac{1-\omega_k}{\omega_k}$, $k \in \mathbb{Z}$. The following result completes [18, Theorem 1.1] which says that, for every $0 \le \vartheta < 1$, we have for P-almost every environment $\omega$,

$$ \sum_{n \ge 1} \frac{P_{\omega}^{0}[Z_n = 0]}{n^{\vartheta}} = \infty. $$
**Proposition 2.1.** For P-almost every environment $\omega$,

$$ \sum_{n \ge 1} \frac{P_{\omega}^{0}[Z_n = 0]}{n} < \infty. $$

Before proving this result, we introduce some more notations. First, let

$$ \tau(x) := \inf\{n \ge 1 : Z_n = x\}, \quad x \in \mathbb{Z}. $$

In words, $\tau(x)$ is the hitting time of the site $x$ by the RWRE $Z$. As usual, we consider the potential $V$, which is a function of the environment $\omega$ and is defined on $\mathbb{Z}$ as follows:

$$ V(x) := \begin{cases} \sum_{i=1}^{x} \log \frac{1-\omega_i}{\omega_i} & \text{if } x > 0, \\ 0 & \text{if } x = 0, \\ -\sum_{i=x+1}^{0} \log \frac{1-\omega_i}{\omega_i} & \text{if } x < 0. \end{cases} \quad (2.2) $$

The potential is useful since it relates to the description of the RWRE as an electric network. It can be used to estimate ruin probabilities for the RWRE. In particular, we have (see e.g. [36, (2.1.4)] and [12, Lemma 2.2] coming from [36, p. 250]),

$$ P_{\omega}^{b}[\tau(c) < \tau(a)] = \left(\sum_{j=a}^{b-1} e^{V(j)}\right) \left(\sum_{j=a}^{c-1} e^{V(j)}\right)^{-1}, \quad a < b < c \quad (2.3) $$

and, recalling $\varepsilon_0$ from (1.3) and (2.1), for $a < b < c$,

$$ E_{\omega}^{b}[\tau(a) \wedge \tau(c)] \le \varepsilon_{0}^{-1}(c-a)^{2} \exp \left[ \max_{a \le l \le k \le c-1; k \ge b} (V(k) - V(l)) \right], \quad (2.4) $$

where $E_{\omega}^{b}$ denotes the expectation with respect to $P_{\omega}^{b}$ and $u \wedge v := \min(u, v)$, $(u, v) \in \mathbb{R}^2$. For symmetry reasons, we also have for $a < b < c$,

$$ E_{\omega}^{b}[\tau(a) \wedge \tau(c)] \le \varepsilon_{0}^{-1}(c-a)^{2} \exp \left[ \max_{a \le l \le k \le c-1, l \le b-1} (V(l) - V(k)) \right]. \quad (2.5) $$

Moreover, we have, for $k \ge 1$ (see Golosov [19], Lemma 7)

$$ P_{\omega}^{b}[\tau(c) < k] \le k \exp \left( \min_{l \in [b, c-1]} V(l) - V(c-1) \right), \quad b < c, \quad (2.6) $$

and by symmetry, we get (similarly as in Shi and Zindy [32], eq. (2.5) but with some slight differences for the values of $l$)

$$ P_{\omega}^{b}[\tau(a) < k] \le k \exp \left( \min_{l \in [a, b-1]} V(l) - V(a) \right), \quad a < b. \quad (2.7) $$

**Lemma 2.2.** Let $\gamma > 0$. For P-almost every $\omega$, there exists $N(\omega)$ such that for every $n \ge N(\omega)$,

$$ n^{\frac{1}{2}-\gamma} \le \max_{k \in \{0, \dots, n\}} V(k) \le n^{\frac{1}{2}+\gamma}, \quad -n^{\frac{1}{2}+\gamma} \le \min_{k \in \{0, \dots, n\}} V(k) \le -n^{\frac{1}{2}-\gamma}, $$

and such that the same inequalities hold with $\{-n, \dots, 0\}$ instead of $\{0, \dots, n\}$.

**Proof of Lemma 2.2.** Observe that it is enough to prove that P-almost surely,

$$ n^{\frac{1}{2}-\gamma} \le \max_{1 \le k \le n} V(k) \le n^{\frac{1}{2}+\gamma} \quad (2.8) $$

if $n$ is large enough (up to a change of $\log \rho_i$ in $-\log \rho_i$, in $\log \rho_{1-i}$ or in $-\log \rho_{1-i}$). The first inequality of (2.8) is given by [20, Theorem 2]. The second inequality of (2.8) is a consequence of the law of iterated logarithm for $V$, as explained in ([9], end of p. 248). $\square$
Proof of Proposition 2.1. Let $\eta \in (0, 1)$ and $n \ge 2$. We define

$$z_+ := \inf\{y \ge 1 : V(y) \le -(\log n)^{1-\eta}\}, \quad z_- := \sup\{y \le -1 : V(y) \le -(\log n)^{1-\eta}\}.$$

Due to the previous lemma, choosing $\gamma$ small enough, we have that P-almost surely, if $n$ is large enough, the following inequalities hold:

$$|z_{\pm}| \le \frac{(\log n)^{2-\eta}}{2} \quad \text{and} \quad \max_{z_{-} \le i, j \le z_{+}} (V(i) - V(j)) \le (\log n)^{1-\eta/10}. \qquad (2.9)$$

We have by the strong Markov property,

$$P_{\omega}^{0}[Z_{n} = 0] \le P_{\omega}^{0}[\tau(z_{+}) > n, \tau(z_{-}) > n] + \sum_{k=0}^{n} P_{\omega}^{0}[\tau(z_{+}) = k] P_{\omega}^{z_{+}}[Z_{n-k} = 0] \\ + \sum_{k=0}^{n} P_{\omega}^{0}[\tau(z_{-}) = k] P_{\omega}^{z_{-}}[Z_{n-k} = 0]. \quad (2.10)$$

Recall that, given $\omega$, the Markov chain $Z$ is an electrical network where, for every $x \in \mathbb{Z}$, the conductance of the bond $(x, x+1)$ is $C_{(x,x+1)} = e^{-V(x)}$ (in the sense of Doyle and Snell [14]). In particular, the reversible measure $\mu_{\omega}$ (unique up to a multiplication by a constant) is given by

$$\mu_{\omega}(x) := e^{-V(x)} + e^{-V(x-1)}, \quad z \in \mathbb{Z}. \qquad (2.11)$$

So we have

$$P_{\omega}^{z_{\pm}}[Z_{n-k} = 0] = P_{\omega}^{0}[Z_{n-k} = z_{\pm}] \frac{\mu_{\omega}(0)}{\mu_{\omega}(z_{\pm})} \le \frac{\mu_{\omega}(0)}{\mu_{\omega}(z_{\pm})} = \frac{e^{-V(0)} + e^{-V(-1)}}{e^{-V(z_{\pm})} + e^{-V(z_{\pm}-1)}} \\ \le \frac{e^{-V(0)} + e^{-V(-1)}}{e^{-V(z_{\pm})}} \le (e^{-V(0)} + e^{-V(-1)}) \exp[-(\log n)^{1-\eta}].$$

Hence,

$$\sum_{k=0}^{n} P_{\omega}^{0}[\tau(z_{\pm}) = k] P_{\omega}^{z_{\pm}}[Z_{n-k} = 0] \le (e^{-V(0)} + e^{-V(-1)}) \exp[-(\log n)^{1-\eta}]. \quad (2.12)$$

Moreover we have due to (2.4) and to Markov's inequality,

$$P_{\omega}^{0}[\tau(z_{+}) > n, \tau(z_{-}) > n] \le n^{-1} E_{\omega}^{0}[\tau(z_{+}) \wedge \tau(z_{-})] \\ \le n^{-1} \varepsilon_{0}^{-1} (z_{+} - z_{-})^{2} \exp \left[ \max_{z_{-} \le l \le k \le z_{+}-1} [V(k) - V(l)] \right].$$

Now using (2.9), P-almost surely, we have

$$P_{\omega}^{0}[\tau(z_{+}) > n, \tau(z_{-}) > n] \le \varepsilon_{0}^{-1} n^{-1} (\log n)^{4-2\eta} \exp[(\log n)^{1-\eta/10}].$$

for every $n$ large enough. This combined with (2.10), (2.12) and $e^{-V(-1)} \le \varepsilon_0^{-1}$ gives P-almost surely for large $n$

$$P_{\omega}^{0}[Z_{n} = 0] \le 5\varepsilon_{0}^{-1} \exp[-(\log n)^{1-\eta}].$$

Consequently, $\sum_{n \ge 1} \frac{P_{\omega}^{0}[Z_{n}=0]}{n} < \infty$ P-almost surely, which ends the proof of Proposition 2.1. $\square$
### 3 Direct product of walks

We start with a proof of Theorem 1.1. With a slight abuse of notation, we will write 0 for the origin in $\mathbb{Z}^k$, whatever $k$ is.

**Proof.** 1. If $m \ge 1$ and $r = 0$, then $(Y_n)_n$ is a product of $m$ independent simple random walks on $\mathbb{Z}$. It is well-known that it is recurrent if $m \in \{1, 2\}$, and transient if $m \ge 3$. This follows from elementary calculations and the crucial fact that for any irreducible Markov chain $(G_n)_n$,

$$ (G_n)_n \text{ is recurrent if and only if } \sum_{n \ge 0} P^x[G_n = 0] = \infty, \qquad (3.1) $$

where $x$ is one of the states of the Markov chain.

2. If $m \ge 3$ and $r \ge 1$, then the 3-tuple of the three first coordinates of $(Y_n)_n$ is $(S_n^{(1)}, S_n^{(2)}, S_n^{(3)})_n$ which is a product of 3 independent simple random walks on $\mathbb{Z}$, hence is transient. So $(Y_n)_n$ is transient for P-almost every $\omega$.

3. If $m = 2$ and $r \ge 1$, then applying the local limit theorem (see e.g. Lawler and Limic [27, Prop. 2.5.3]) for $S^{(1)}$ and $S^{(2)}$ for $n \in \mathbb{N}^*$,

$$ P_{\omega}^{0}[Y_n = 0] = \prod_{i=1}^{2} P[S_n^{(i)} = 0] \prod_{j=1}^{r} P_{\omega^{(j)}}^{0}[Z_n^{(j)} = 0] \le \frac{c}{n} P_{\omega^{(1)}}^{0}[Z_n^{(1)} = 0], $$

where $c > 0$ is a constant. This and Proposition 2.1 yield $\sum_{n=0}^{\infty} P_{\omega}^{0}[Y_n = 0] < \infty$ for P-almost $\omega$. Hence, (using the Borel-Cantelli Lemma or (3.1)), $(Y_n)_n$ is P-almost surely transient.

4. We now assume $m \in \{0, 1\}$. We choose some $\delta \in (0, 1/5)$ such that $3\delta r < \frac{1-2\delta}{2}$. We denote by $\lfloor x \rfloor$ the integer part of $x$ for $x \in \mathbb{R}$. For $L \in \mathbb{N}$, we have

$$ \begin{aligned} \sum_{n \ge 0} P_{\omega}^{0}[Y_n = 0] & \ge \sum_{n = \lfloor \frac{e^{(1-2\delta)L}}{2} \rfloor + 1}^{\lfloor e^{(1-2\delta)L} \rfloor} P_{\omega}^{0}[Y_{2n} = 0] \\ & = \sum_{n = \lfloor \frac{e^{(1-2\delta)L}}{2} \rfloor + 1}^{\lfloor e^{(1-2\delta)L} \rfloor} P[S_{2n} = 0]^{m} \prod_{j=1}^{r} P_{\omega^{(j)}}^{0}[Z_{2n}^{(j)} = 0]. \end{aligned} $$

Due to [18] (Propositions 3.2, 3.4 and (3.22)), since $\delta \in (0, 1/5)$, there exist $C(\delta) > 0$ and a sequence $(\Gamma(L, \delta))_{L \in \mathbb{N}}$ of elements of $\mathcal{F}$ (that is, depending only on $\omega$) such that

$$ P \left[ \bigcap_{N \ge 0} \bigcup_{L \ge N} \Gamma(L, \delta) \right] = 1 \qquad (3.2) $$

and such that, for every $L \in \mathbb{N}$, on $\Gamma(L, \delta)$, we have

$$ \forall i \in \{1, \dots, r\}, \forall k_i \in \{\lfloor e^{3\delta L} \rfloor + 1, \dots, \lfloor e^{(1-2\delta)L} \rfloor\}, \quad P_{\omega^{(i)}}^{0}[Z_{2k_i}^{(i)} = 0] \ge C(\delta) e^{-3\delta L}. \qquad (3.3) $$

Due to the local limit theorem, this gives on $\Gamma(L, \delta)$, for large $L$ so that $\frac{e^{(1-2\delta)L}}{2} \ge e^{3\delta L}$,

$$ \sum_{n \ge 0} P_{\omega}^{0}[Y_n = 0] \ge \frac{e^{(1-2\delta)L}}{3} \left( \frac{c}{e^{(1-2\delta)L/2}} \right)^{m} \left( \frac{C(\delta)}{e^{3\delta L}} \right)^{r} \ge c_1(\delta) e^{\left[ \frac{(1-2\delta)}{2} - 3\delta r \right] L}, $$

which goes to infinity as $L$ goes to infinity due to our choice of $\delta$, $c_1(\delta)$ being a positive constant. Thanks to (3.2), this gives $\sum_{n \ge 0} P_{\omega}^{0}[Y_n = 0] = +\infty$ for P-almost all $\omega$. Consequently, due to (3.1), $(Y_n)_n$ is recurrent for P-almost every environment $\omega$. $\square$
**Remark 3.1.** Recall that Sinai [33] (see also Golosov [19]) proved the convergence in distribution of $(Z_n^{(i)}/(\log n)^2)_n$. Recall also that, due to de Moivre's theorem, $(S_n^{(i)}/\sqrt{n})_n$ converges in distribution. Due to Theorem 1.1, $Y$ is recurrent iff $\sum_n 1/(n^{\frac{m}{2}}((\log n)^2)^r) = \infty$, where $n^{\frac{m}{2}}((\log n)^2)^r$ is the product of the normalizations of the coordinates of $Y$ under the (non Markovian) annealed law $\mathbb{P}$.

Note also that Theorem 1.2 and the previous paragraph lead to the following statement (only for $r \ge 1$): if $\sum_{n \ge 1} \frac{1}{n^{m/2}(\log n)^{2l-2}} < \infty$, then almost surely, the random walks $S^{(1)}, \dots, S^{(m)}, Z^{(1)}, \dots, Z^{(r)}$ meet simultaneously only a finite number of times; otherwise, they almost surely meet simultaneously infinitely often.

Now we will start to prove Theorem 1.2. Note that the case $m \le 1$ is already treated in Theorem 1.1 which says that in this case the random walks meet infinitely often at 0.

*Proof of Theorem 1.2.* Let $A_n := \{S_n^{(1)} = \dots = S_n^{(m)} = Z_n^{(1)} = \dots = Z_n^{(r)}\}$ for $n \ge 0$.

*Proof of (i).* Assume $m = 3$ and $r = 1$. Observe that for large $n$,

$$ \begin{aligned} \mathbb{P}_{\omega}^{0}[A_n] &= \sum_{k \in \mathbb{Z}} \mathbb{P}_{\omega}^{0}[Z_n^{(1)} = k] (\mathbb{P}[S_n^{(1)} = k])^3 \\ &\le C \sum_{k \in \mathbb{Z}} \frac{\mathbb{P}_{\omega}^{0}[Z_n^{(1)} = k]}{n\sqrt{n}} = \frac{C}{n\sqrt{n}} \end{aligned} $$

for some $C > 0$ since for every $k \in \mathbb{Z}$ and $n \in \mathbb{N}$, $\mathbb{P}[S_{2n}^{(1)} = k] \le \mathbb{P}[S_{2n}^{(1)} = 0] \sim_{n \to +\infty} (\pi n)^{-1/2}$ due to the local limit theorem. Hence $\sum_n \mathbb{P}_{\omega}^{0}[S_n^{(1)} = S_n^{(2)} = S_n^{(3)} = Z_n^{(1)}] < \infty$ and (i) follows by the Borel-Cantelli lemma in this case and a fortiori when $m \ge 3$ and $r \ge 1$.

*Proof of (ii).* Assume $m = 2$ and $r \ge I = 1$. Since $I = 1$, all the RWRE are in the same environment, which is necessary to apply Proposition 1.5, which is essential to prove (ii). We use the generalization of the second Borel Cantelli lemma due to Kochen and Stone [24] combined with a result by Doob. To simplify notations, we also write $\omega$ for $\omega^{(1)}$, so $\omega^{(i)} = \omega$ for every $1 \le i \le r$.

We first prove that $\sum_n \mathbb{P}_{\omega}[A_n] = \infty$ a.s. More precisely, we fix an initial condition $x = (x_1, x_2, y_1, \dots, y_r) \in (2\mathbb{Z})^{2r} \cup (2\mathbb{Z} + 1)^{2r}$. We have for all $n$ and $\omega$,

$$ P_{\omega}^{x}[A_n] = \sum_{k \in \mathbb{Z}} \mathbb{P}[x_1 + S_n^{(1)} = k] \mathbb{P}[x_2 + S_n^{(2)} = k] \prod_{j=1}^{r} P_{\omega}^{y_j}[Z_n^{(j)} = k]. $$

Notice that, for every $i \in \{1, 2\}$, due to the de Moivre-Laplace theorem (see e.g. [27, Prop. 2.5.3 and Corollary 2.5.4]),

$$ \sup_{k \in (x_i + n + 2\mathbb{Z}), \ |k| \le (\log n)^3} \left| \mathbb{P}[x_i + S_n^{(i)} = k] - \frac{\sqrt{2}}{\sqrt{\pi n}} e^{-(k-x_i)^2/(2n)} \right| = o(n^{-1/2}). $$

Consequently for large even $n$, for every $\omega$,

$$ P_{\omega}^{x}[A_n] \ge \sum_{|k| \le (\log n)^3, k - (x_1 + n) \in (2\mathbb{Z})} \frac{1}{\pi n} \prod_{j=1}^{r} P_{\omega}^{y_j}[Z_n^{(j)} = k] = \frac{1}{\pi n} \sum_{|k| \le (\log n)^3} \prod_{j=1}^{r} P_{\omega}^{y_j}[Z_n^{(j)} = k]. $$

This remains true for large odd $n$. Hence for large $n$,

$$ P_{\omega}^{x}[A_n] \ge \frac{1}{\pi n} P_{\omega}^{y_1, \dots, y_r}[Z_n^{(1)} = \dots = Z_n^{(r)}] - \frac{1}{\pi n} P_{\omega}^{y_1}[|Z_n^{(1)}| > (\log n)^3]. \quad (3.4) $$
Recall that $(Z_n^{(1)}/(\log n)^3)_n$ converges almost surely to 0 with respect to the annealed law (see [10] Theorem 4, or more recently [21] Theorem 3). This holds also true for $P_\omega^{y_1}$ for P-almost every $\omega$, so the last probability in (3.4) goes to 0 as $n \to +\infty$, which yields $\lim_{N \to +\infty} \frac{1}{\log N} \sum_{n=1}^N \frac{1}{n} P_\omega^{y_1} [|Z_n^{(1)}| > (\log n)^3] = 0$. Hence for P-almost every $\omega$,

$$ \limsup_{N \to +\infty} \frac{1}{\log N} \sum_{n=1}^{N} P_{\omega}^{x}[A_n] \geq \frac{c(\omega)}{\pi}, \quad (3.5) $$

with $c(\omega) := \inf_{(y_1, \dots, y_r) \in [(2Z)^r \cup (2Z+1)^r]} \limsup_{N \to +\infty} \frac{1}{\log N} \sum_{n=1}^N \frac{1}{n} P_\omega^{(y_1, \dots, y_r)} [Z_n^{(1)} = \dots = Z_n^{(r)}]$. If $r=1$, then $c(\omega) = 1$. If $r > 1$, due to Proposition 1.5, $c(\omega) > 0$ for P-almost every environment $\omega$. This implies that

$$ \sum_{n \ge 1} P_{\omega}^{x}[A_n] = +\infty. \quad (3.6) $$

Moreover, let $C > 0$ be such that for all $n \ge 1$ and $k \in \mathbb{Z}$, $P[S_{2n}^{(1)} = k] \le Cn^{-1/2}$, which exists e.g. since $P[S_{2n}^{(1)} = k] \le P[S_{2n}^{(1)} = 0] \sim_{n \to +\infty} (\pi n)^{-1/2}$ by the local limit theorem. So for $1 \le n < m$, we have by Markov property,

$$ \begin{aligned} P_{\omega}^{x}[A_n \cap A_m] &= \sum_{(k,l) \in \mathbb{Z}^2} P_{\omega}^{(y_1, \dots, y_r)}[Z_n^{(1)} = \dots = Z_n^{(r)} = k, Z_m^{(1)} = \dots = Z_m^{(r)} = l] \\ & \quad \times P[x_1 + S_n^{(1)} = k] P[x_2 + S_n^{(2)} = k] (P[S_{m-n}^{(1)} = l-k])^2 \\ & \le \sum_{k \in \mathbb{Z}} P_{\omega}^{(y_1, \dots, y_r)}[Z_n^{(1)} = \dots = Z_n^{(r)} = k] P_{\omega}^{(k, \dots, k)}[Z_{m-n}^{(1)} = \dots = Z_{m-n}^{(r)}] \frac{C^4}{n(m-n)} \\ & \le \frac{C^4}{n(m-n)}. \end{aligned} $$

Consequently, for large $N$,

$$ \sum_{1 \le n, m \le N, m \ne n} P_{\omega}^{x}[A_n \cap A_m] \le 2 \sum_{n=1}^{N} \frac{C^4}{n} \sum_{\ell=1}^{N-n} \frac{1}{\ell} \le 3C^4(\log N)^2. $$

Applying this and (3.5) we get for P-almost every $\omega$, for every initial condition $x \in (2\mathbb{Z})^{2+r} \cup (2\mathbb{Z} + 1)^{2+r}$,

$$ \limsup_{N \to +\infty} \frac{\left( \sum_{n=1}^{N} P_{\omega}^{x}[A_n] \right)^2}{\sum_{1 \le n, m \le N} P_{\omega}^{x}[A_n \cap A_m]} \ge \frac{(c(\omega))^2}{3\pi^2 C^4}. \quad (3.7) $$

Due to the Kochen and Stone extension of the second Borel-Cantelli lemma (see Item (iii) of the main theorem of [24] applied with $X_n = \sum_{i=1}^n 1_{A_i}$, or [35, p. 317]), (3.7) and (3.6) imply that $P_\omega^x[A_n \text{ i.o.}] = P_\omega^x[\cap_{N \ge 0} \cup_{n \ge N} A_n] \ge (c(\omega))^2/(3\pi^2 C^4) > 0$, where i.o. means infinitely often.

Now for P-almost every $\omega$, due to a result by Doob (see for example Proposition V-2.4 in [28]), since $E := \{A_n \text{ i.o.}\} = \cap_{N \ge 0} \cup_{n \ge N} A_n$ is invariant (with respect to the shifts of the sequence $(Y_0, Y_1, Y_2, \dots)$), for every $x \in (2\mathbb{Z})^{2+r} \cup (2\mathbb{Z}+1)^{2+r}$, $(P_\omega^{(S_n^{(1)}, S_n^{(2)}, Z_n^{(1)}, \dots, Z_n^{(r)})}[E])_n$ converges $P_\omega^x$-almost surely to $1_E$.

But $\inf_{x \in (2\mathbb{Z})^{2+r} \cup (2\mathbb{Z}+1)^{2+r}} P_\omega^x[E] \ge (c(\omega))^2/(3\pi^2 C^4) > 0$, so we conclude that $1_E = 1$ $P_\omega^x$-almost surely, thus $P_\omega^x(E) = 1$, for P-almost every environment $\omega$.
Proof of (iii). Assume $m = 2$ and $r = I = 2$. We have

$$ 
\begin{aligned}
\mathbb{P}^0[A_n] &= \sum_{k \in \mathbb{Z}} \mathbb{P}[Z_n^{(1)} = Z_n^{(2)} = k] (\mathbb{P}[S_n^{(1)} = k])^2 \\
&\leq \frac{C^2}{n} \mathbb{P}[Z_n^{(1)} = Z_n^{(2)}] = O(n^{-1}(\log n)^{-3/2}),
\end{aligned}
$$

due to Proposition 1.4 and the local limit theorem. Hence $\sum_n \mathbb{P}^0[A_n] < \infty$ and (iii) follows due to the Borel-Cantelli lemma. $\square$

So there only remains to prove Propositions 1.4 and 1.5.

# 4 Probability of meeting for two independent recurrent RWRE in independent environments

The aim of this section is to prove Proposition 1.4, which is a key result in the proof of case (iii) of Theorem 1.2.

Let $Z^{(1)}$ and $Z^{(2)}$ be two independent recurrent RWRE in independent environments $\omega^{(1)}$ and $\omega^{(2)}$ satisfying (2.1).

The main idea of the proof is that $Z_n^{(1)}$ and $Z_n^{(2)}$ are localized with high (annealed) probability in two areas (depending on the environments, see Proposition 4.5) which have no common point with high probability (see Lemma 4.6). Due to [33], we know that, with high probability, $Z_n^{(i)}$ is close to the bottom $B_n^{(i)}$ of some valley (containing 0 and of height larger than $\log n$) for the potential $V^{(i)}$. Here and in the following, $V^{(i)}$ denotes the potential corresponding to $\omega^{(i)}$, defined as in (2.2) with $\omega$ replaced by $\omega^{(i)}$. An intuitive idea to prove Proposition 1.4 should then be that $p_n := \mathbb{P}[\max_{i=1,2} |Z_n^{(i)} - B_n^{(i)}| \geq |B_n^{(1)} - B_n^{(2)}|/2]$ is very small. More precisely we would like to prove that $p_n = O((\log n)^{-1-\epsilon})$. (In view of the proof of (iii) above, it would suffice to show that $\sum_n \frac{p_n}{n} < \infty$). However, this seems difficult to prove and we are not even sure that it is true. Indeed, in view of Lemma 4.4 below (proved for a continuous approximation $W^{(i)} \approx V^{(i)}$), we think that with probability greater than $1/\log n$, 0 belongs to a valley of height between $\log n - 2\log \log n$ and $\log n$ and that the annealed probability that $Z_n^{(i)}$ is close to the bottom of this valley (which is not $B_n^{(i)}$) should be greater than $1/\log n$. Hence, to prove Proposition 1.4, we will work with several valleys instead of a single one.

## 4.1 Proof of Proposition 1.4

In this subsection, we use a Brownian motion $W^{(i)}$, approximating the potential $V^{(i)}$, to build a localization domain $\Xi_n(W^{(i)})$ for $Z_n^{(i)}$, $i \in \{1, 2\}$. This localization is stated in Proposition 4.5 and is crucial to prove Proposition 1.4.

In order to construct our localization domain $\Xi_n(W^{(i)})$, we use the notion of h-extrema, defined as follows.

**Definition 4.1** ([29]). If $w: \mathbb{R} \to \mathbb{R}$ is a continuous function and $h > 0$, we say that $y_0 \in \mathbb{R}$ is an h-minimum for w if there exist real numbers a and c such that $a < y_0 < c$, $w(y_0) = \inf_{[a,c]} w$, $w(a) \geq w(y_0) + h$ and $w(c) \geq w(y_0) + h$. We say that $y_0$ is an h-maximum for w if $y_0$ is an h-minimum for $-w$. In any of these two cases, we say that $y_0$ is an h-extremum for w.

We also use the following notation.

**Definition 4.2.** As in [7], we denote by $\mathcal{W}$ the set of functions $w: \mathbb{R} \to \mathbb{R}$ such that the three following conditions are satisfied: (a) w is continuous on $\mathbb{R}$; (b) for every $h > 0$, the set of h-extrema of w can be written $\{x_k(w, h), k \in \mathbb{Z}\}$, with $(x_k(w, h))_{k \in \mathbb{Z}}$ strictly
increasing, unbounded from below and above, and with $x_0(w, h) \le 0 < x_1(w, h)$, notation
that we use in the rest of the paper on $\mathcal{W}$; (c) for all $k \in \mathbb{Z}$ and $h > 0$, $x_k(w, h)$ is an
$h$-minimum for $w$ if and only if $x_{k+1}(w, h)$ is an $h$-maximum for $w$.

We now introduce, for $w \in \mathcal{W}$, $i \in \mathbb{Z}$ and $h > 0$,

$$
b_i(w, h) := \begin{cases} x_{2i}(w, h) & \text{if } x_0(w, h) \text{ is an } h\text{-minimum,} \\ x_{2i+1}(w, h) & \text{otherwise.} \end{cases}
$$

As a consequence, the $b_i(w, h)$ are the $h$-minima of $w$. We denote by $M_i(w, h)$ the unique $h$-maximum of $w$ between $b_i(w, h)$ and $b_{i+1}(w, h)$. That is, $M_i(w, h) = x_{j+1}(w, h)$ if $b_i(w, h) = x_j(w, h)$.

For $w \in \mathcal{W}, h > 0$ and $i \in \mathbb{Z}$, the restriction of $w - w(x_i(w, h))$ to $[x_i(w, h), x_{i+1}(w, h)]$
is denoted by $T_i(w, h)$ and is called an $h$-slope, as in [7]. If $x_i(w, h)$ is an $h$-minimum
(resp. $h$-maximum), then $T_i(w, h)$ is a nonnegative (resp. nonpositive) function, and its
maximum (resp. minimum) is attained at $x_{i+1}(w, h)$. We also introduce, for each slope
$T_i(w, h)$, its height $H(T_i(w, h)) := |w(x_{i+1}(w, h)) - w(x_i(w, h))| \ge h$, and its excess height
$e(T_i(w, h)) := H(T_i(w, h)) - h \ge 0$.

When $x_i(w, h)$ is an $h$-minimum, the restriction of $w$ to $[x_{i-1}(w, h), x_{i+1}(w, h)]$ will
sometimes be called valley of height at least $h$ and of bottom $x_i(w, h)$. The height of
this valley is defined as $\min\{w(x_{i-1}(w, h)), w(x_{i+1}(w, h))\} - w(x_i(w, h))$, which can also
be rewritten $\min\{H(T_{i-1}(w, h)), H(T_i(w, h))\}$.

These $h$-extrema are useful to localize RWRE and diffusions in a random potential.
Indeed, a diffusion in a two-sided Brownian potential $W$ (resp. in a $(-\kappa/2)$-drifted
Brownian potential $W_\kappa$ with $0 < \kappa < 1$) is localized at large time $t$ with high probability
in a small neighborhood of $b_0(W, \log t)$ (resp. some of the $b_i(W_\kappa, \log t - \sqrt{\log t})$, $i \ge 0$) see
e.g. [7] and [8] (resp. [2]). For some applications to recurrent RWRE, see e.g. [4] and
[12].

Let $C_1 > 2$ and $\alpha > 2$. Define $\log^{(2)} x = \log \log x$ for $x > 1$. As in [12], we use the
Komlós-Major-Tusnády almost sure invariance principle [25], which ensures that:

**Lemma 4.3.** Up to an enlargement of $(\Omega, \mathcal{F}, \mathcal{P})$, there exist two independent two-sided Brownian motions $(W^{(i)}(s), s \in \mathbb{R})$ $(i \in \{1, 2\})$ with $\mathbb{E}[(W^{(i)}(1))^2] = \mathbb{E}[(V^{(i)}(1))^2] = \sigma_i^2$ and a real number $\tilde{C}_1 > 0$ such that for all $n$ large enough,

$$
\mathbb{P} \left[ \sup_{|t| \le (\log n)^\alpha} \left| V^{(i)}(\lfloor t \rfloor) - W^{(i)}(t) \right| > \tilde{C}_1 \log^{(2)} n \right] \le (\log n)^{-C_1}, \quad i \in \{1, 2\}.
$$

Proof. Notice that $V^{(1)}$ and $V^{(2)}$ are independent, since $\omega^{(1)}$ and $\omega^{(2)}$ are independent.
Due to ([25], Thm. 1), there exist positive constants $a, b$ and $c$ such that for $N \in \mathbb{N}$, up to
an enlargement of $(\Omega, \mathcal{F}, \mathcal{P})$, there exist two independent two-sided Brownian motions
$(W^{(i)}(s), s \in \mathbb{R})$ $(i \in \{1, 2\})$ on $(\Omega, \mathcal{F}, \mathcal{P})$ with $\mathbb{E}[(W^{(i)}(1))^2] = \mathbb{E}[(V^{(i)}(1))^2] = \sigma_i^2$ such that

$$
\forall x \in \mathbb{R}, \forall i \in \{1, 2\}, \quad \mathbb{P} \left[ \sup_{|k| \le N} \left| V^{(i)}(k) - W^{(i)}(k) \right| > a \log N + x \right] \le be^{-cx}. \quad (4.1)
$$

Applying this result to $N := \lfloor (\log n)^\alpha \rfloor + 1$ and $x := (\log(2b) + C_1 \log^{(2)} n)/c$ and taking
$\tilde{C}_1 > 2 (a\alpha + \frac{C_1}{c})$, we obtain that

$$
\mathbb{P} \left[ \sup_{|k| \le \lfloor (\log n)^\alpha \rfloor + 1} \left| V^{(i)}(k) - W^{(i)}(k) \right| > \frac{\tilde{C}_1}{2} \log^{(2)} n \right] \le \frac{1}{2} (\log n)^{-C_1}, \quad (4.2)
$$

for all *n* large enough. Moreover, for every *n* large enough,
$$
\begin{align*}
& \mathbf{P} \left[ \sup_{|t| \le (\log n)^\alpha} |W^{(i)}(t)| - W^{(i)}(t)| > \frac{\tilde{C}_1}{2} \log^{(2)} n \right] \\
& \le 3(\log n)^\alpha \mathbf{P} \left[ \sup_{0 \le t < 1} |W^{(i)}(t)| > \frac{\tilde{C}_1}{2} \log^{(2)} n \right] \le 6(\log n)^\alpha \mathbf{P} \left[ |W^{(i)}(1)| > \frac{\tilde{C}_1}{2} \log^{(2)} n \right] \\
& \le 6(\log n)^\alpha \frac{2}{\sqrt{2\pi}} e^{-\frac{(\tilde{C}_1)^2}{8\sigma_i^2} (\log^{(2)} n)^2} = \frac{12}{\sqrt{2\pi}} (\log n)^{\alpha - \frac{(\tilde{C}_1)^2}{8\sigma_i^2} \log^{(2)} n} \le \frac{1}{2} (\log n)^{-C_1},
\end{align*}
$$

since $\sup_{[0,1]} W^{(i)} =_{law} |W^{(i)}(1)|$. This combined with (4.2) proves the lemma. $\square$

In the rest of the paper, we use the $W^{(i)}$ introduced in Lemma 4.2. We will use the
valleys for the $W^{(i)}$. Fix some $C_2 \ge 2\alpha + 2 + 10 \tilde{C}_1$. Let

$$
h_n := \log n - 5C_2 \log^{(2)} n. \tag{4.3}
$$

We know from ([7], Lemma 8) that $W^{(i)} \in W$ almost surely (recall definition 4.2).
Moreover, using [21, Th 2.1] with $0 < a = b$, we have

$$
\mathbf{P} \left[ \sup_{0 \le s \le t} \left[ |W^{(i)}(s) - \underline{W}^{(i)}(s)| \right] < b \right] \le (4/\pi) \exp[-\pi^2 \sigma_i^2 t / (8b^2)],
$$

where $\underline{W}^{(i)}(s) := \inf_{[0,s]} W^{(i)}$. Applying this several times to $W^{(i)}$ and $-W^{(i)}$ with $t = (\log n)^\alpha/10$ and $b = h_n$, the following holds with a probability $1 - o((\log n)^{-2})$ (since $\alpha > 2$),

$$
\forall i \in \{1, 2\}, \quad -(\log n)^\alpha \le b_4(W^{(i)}, h_n) \le M_3(W^{(i)}, h_n) \le (\log n)^\alpha. \quad (4.4)
$$

The following lemma shows that Proposition 1.4 is more subtle than it may seem at
first sight.

**Lemma 4.4.** Let $W$ be a two-sided standard Brownian motion and $\sigma > 0$. Then, for every $n$ large enough,

$$
\mathbf{P}[H(T_0(\sigma W, h_n)) \le \log n] \ge C_2(\log^{(2)} n)(\log n)^{-1}, \quad (4.5)
$$

$$
\begin{align}
& \mathbf{P}[\#\{j \in \{-5, \dots, 5\}, H(T_j(\sigma W, h_n - 2C_2 \log^{(2)} n)) \le \log n + C_2 \log^{(2)} n\} \ge 2] \tag{4.6} \\
&= O((\log^{(2)} n)^2 (\log n)^{-2}), \nonumber
\end{align}
$$

$$
\begin{align}
& \mathbf{P}[\exists j \in \{-5, \dots, 5\}, H(T_j(\sigma W, h_n - 2C_2 \log^{(2)} n)) \le \log n + C_2 \log^{(2)} n] \tag{4.7} \\
&= O((\log^{(2)} n)(\log n)^{-1}). \nonumber
\end{align}
$$

In particular, the probability that the height of the central valley for $W^{(i)}$ is less than $\log n$ is not negligible. However, with large enough probability, all the valleys close to 0 except maybe one are large, with height greater than $\log n + C_2 \log^{(2)} n$.

Proof of Lemma 4.4. Let $\tilde{h}_n := h_n - 2C_2 \log^{(2)} n$. First, due to ([29], Prop. 1, see also [7] eq. (8)), $e(T_i(\sigma W, \tilde{h}_n))/\tilde{h}_n$ is for $i \neq 0$ an exponential random variable with mean 1. Consequently, for $i \neq 0$ and large $n$,

$$
\mathbf{P}[H(T_i(\sigma W, \tilde{h}_n)) \le \log n + C_2 \log^{(2)} n] = \mathbf{P}[e(T_i(\sigma W, \tilde{h}_n)) \le 8C_2 \log^{(2)} n] \le \frac{9C_2 \log^{(2)} n}{\log n}.
$$

Observe that $e(T_0(\sigma W, \tilde{h}_n))/\tilde{h}_n$ is by scaling equal in law to $e(T_0(W, 1))$, which has a
density equal to $(2x + 1)e^{-x}1_{(0,\infty)}(x)/3$ due to ([7], formula (11)). Hence for large $n$,

$$
\begin{align*}
C_2(\log^{(2)} n)(\log n)^{-1} &\le \mathbf{P}[e(T_0(\sigma W, \tilde{h}_n)) \le 5C_2 \log^{(2)} n] \\
&\le \mathbf{P}[e(T_0(\sigma W, \tilde{h}_n)) \le 8C_2 \log^{(2)} n] \\
&\le 9C_2(\log^{(2)} n)(\log n)^{-1}.
\end{align*}
$$
This remains true if $\tilde{h}_n$ is replaced by $h_n$. These inequalities already prove (4.5) and (4.7). Moreover, due to ([29], Prop. 1), the slopes $T_i(\sigma W, \tilde{h}_n)$, $i \in \mathbb{Z}$ are independent, up to their sign, so the random variables $H(T_i(\sigma W, \tilde{h}_n))$, $i \in \mathbb{Z}$ are independent. This and the previous inequalities lead to (4.6). □

Because of (4.5), it seems reasonable to consider strictly more than one valley of height at least $h_n$ if we want to localize a recurrent RWRE with probability $\ge 1 - (\log n)^{-2+\epsilon}$ for $\epsilon > 0$.

We first introduce some notation. Let, for $i \in \{1, 2\}$, $j \in \mathbb{Z}$ and $n \ge 3$,

$$ \Xi_{n,j}(W^{(i)}) := \{x \in [M_{j-1}(W^{(i)}, h_n), M_j(W^{(i)}, h_n)], W^{(i)}(x) \le W^{(i)}(b_j(W^{(i)}, h_n)) + C_2 \log^{(2)} n\}. $$

Loosely speaking, $\Xi_{n,j}(W^{(i)})$ is the set of points with low potential in the $j$-th valley for $W^{(i)}$. We also define

$$ \Xi_n(W^{(i)}) := \bigcup_{j=-2}^{2} \Xi_{n,j}(W^{(i)}). $$

In Proposition 4.5 (proved in Section 4.2), we localize the RWRE $Z^{(i)}$ in a set of points which are close to the $b_j(.)$ "vertically", instead of "horizontally" as in Sinai's theorem (see [33]).

**Proposition 4.5.** Let $\epsilon > 0$ and $i \in \{1, 2\}$. For all $n$ large enough, we have

$$ \mathbb{P}[Z_n^{(i)} \notin \Xi_n(W^{(i)})] \le q_n := (\log n)^{-2+\epsilon}. $$

Proposition 1.4 is then an easy consequence of Proposition 4.5 and of the following estimate on the environments.

**Lemma 4.6.** Let $\epsilon > 0$. For large $n$,

$$ \mathbb{P}[\Xi_n(W^{(1)}) \cap \Xi_n(W^{(2)}) \neq \emptyset] \le (\log n)^{-2+\epsilon}. $$

*Proof of Lemma 4.6.* First, let $k \in \Xi_n(W^{(i)})$ for some $i \in \{1, 2\}$ and $n \ge 3$. Hence $k \in [M_{j-1}(W^{(i)}, h_n), M_j(W^{(i)}, h_n)]$ and $W^{(i)}(k) \le W^{(i)}(b_j(W^{(i)}, h_n)) + C_2 \log^{(2)} n$ for some $j \in \{-2, -1, 0, 1, 2\}$. By definition of $h_n$-minima, we notice that the two Brownian motions $(W^{(i)}(x+k) - W^{(i)}(k), x \ge 0)$ and $(W^{(i)}(-x+k) - W^{(i)}(k), x \ge 0)$ hit $h_n - C_2 \log^{(2)} n$ before $-2C_2 \log^{(2)} n$. By independence, it follows that, for $n$ large enough, for every $k \in \mathbb{Z}$ and $i \in \{1, 2\}$,

$$ \begin{aligned} \mathbb{P}[k \in \Xi_n(W^{(i)})] & \le \mathbb{P}[T_{(i)}^+(h_n - C_2 \log^{(2)} n) < T_{(i)}^+(-2C_2 \log^{(2)} n)] \\ & \quad \times \mathbb{P}[|T_{(i)}^-(h_n - C_2 \log^{(2)} n)| < |T_{(i)}^-( -2C_2 \log^{(2)} n)|] \\ & \le O((\log^{(2)} n)/\log n)^2, \end{aligned} $$

where $T_{(i)}^+(z) := \inf\{x > 0 : W^{(i)}(x) = z\}$ and $T_{(i)}^-(z) := \sup\{x < 0 : W^{(i)}(x) = z\}$.

Consequently, since $W^{(1)}$ and $W^{(2)}$ are independent, we have uniformly on $k \in \mathbb{Z}$,

$$ \begin{aligned} \mathbb{P}[k \in \Xi_n(W^{(1)}) \cap \Xi_n(W^{(2)})] & = \mathbb{P}[k \in \Xi_n(W^{(1)})] \mathbb{P}[k \in \Xi_n(W^{(2)})] \\ & \le O((\log^{(2)} n)^4/(\log n)^4). \end{aligned} \quad (4.8) $$

Finally, (4.4) applied with $2 + \epsilon > 2$ instead of $\alpha$ and (4.8) lead to

$$ \begin{aligned} & \mathbb{P}[\Xi_n(W^{(1)}) \cap \Xi_n(W^{(2)}) \neq \emptyset] \\ & \le o((\log n)^{-2}) + \sum_{k=-\lfloor (\log n)^{2+\epsilon} \rfloor}^{\lfloor (\log n)^{2+\epsilon} \rfloor} \mathbb{P}[k \in \Xi_n(W^{(1)}) \cap \Xi_n(W^{(2)})] \end{aligned} $$
$$ \leq O((\log^{(2)} n)^4 (\log n)^{-2+\epsilon}) \leq (\log n)^{-2+2\epsilon}, $$

for every $n$ large enough. Since this is true for every $\epsilon > 0$, this proves the lemma. $\square$

**Proof of Proposition 1.4.** We have for large $n$, due to Proposition 4.5,

$$ \begin{aligned} \mathbb{P}[Z_n^{(1)} = Z_n^{(2)}] &\le \mathbb{P}[Z_n^{(1)} = Z_n^{(2)}, Z_n^{(1)} \in \Xi_n(W^{(1)}), Z_n^{(2)} \in \Xi_n(W^{(2)})] \\ &\quad + \mathbb{P}[Z_n^{(1)} \notin \Xi_n(W^{(1)})] + \mathbb{P}[Z_n^{(2)} \notin \Xi_n(W^{(2)})] \\ &\le \mathbb{P}[\Xi_n(W^{(1)}) \cap \Xi_n(W^{(2)}) \ne \emptyset] + 2q_n. \end{aligned} $$

This and Lemma 4.6 prove Proposition 1.4. $\square$

## 4.2 Proof of Proposition 4.5

We fix $i \in \{1, 2\}$. To simplify notations we write $V$ for $V^{(i)}$, $Z_n$ for $Z_n^{(i)}$ and $W$ for $W^{(i)}$.

The difficulty of this proof is that we have to localize $Z_n$ with probability $1 - (\log n)^{-2+\epsilon}$ instead of $1 - o(1)$ as Sinai did in [33]. For this reason we need to take into account some cases which are usually considered to be negligible. In order to prove Proposition 4.5, we first build a set $G_n$ of good environments, having high probability. We prove that on such a good environment, the RWRE $Z = (Z_n)_n$ will reach quickly the bottom $b_{\mathcal{I}_1}$ of one of the two valleys of $W$ surrounding $0$. We need to consider these two valleys because we cannot neglect the case in which $0$ is close to the maximum of the potential between these two valleys.

Also, we cannot exclude that the valley surrounding $b_{\mathcal{I}_1}$ is “small”, that is, its height is close to $\log n$. Then, we have to consider two situations. If the height of this valley is quite larger than $\log n$, then with large probability, $Z$ stays in this valley up to time $n$ (see Lemma 4.9). Otherwise (in the most difficult case, Lemma 4.11), $Z$ can escape the valley surrounding $b_{\mathcal{I}_1}$ before time $n$, and in this case, with large probability, it reaches before time $n$ the bottom $b_{\mathcal{I}_2}$ of a neighbouring valley and stays in this valley up to time $n$. In both situations, we prove that $Z_n$ is localized in $\Xi_n(W)$, and more precisely in the deepest places of the last valley visited before time $n$. In order to prove this localization, we use the invariant measure of a RWRE in our environment, started at $b_{\mathcal{I}_1}$ or $b_{\mathcal{I}_2}$.

We fix $\epsilon > 0$. Recall (4.3). We introduce for $j \in \mathbb{Z}$,

$$ x_j := \lfloor x_j(W, h_n) \rfloor, \quad b_j := \lfloor b_j(W, h_n) \rfloor, \quad M_j := \lfloor M_j(W, h_n) \rfloor. $$

We denote by $G_n$ the set of **good environments** $\omega$ satisfying (4.4) together with the following properties (see Figure 1):

$$ \sup_{|t| \le (\log n)^\alpha} |V(\lfloor t \rfloor) - W(t)| \le \tilde{C}_1 \log^{(2)} n, \quad (4.9) $$

$$ \#\{j \in \{-5, \dots, 5\}, H(T_j(W, h_n - 2C_2 \log^{(2)} n)) \le \log n + C_2 \log^{(2)} n\} \le 1, \quad (4.10) $$

with $h_n$ defined in (4.3). For every $n$ large enough, we have

$$ \mathbb{P}[(G_n)^c] \le (\log n)^{-2+\epsilon}, \quad (4.11) $$

due to (4.4) and to Lemmas 4.3 and 4.4, since $C_1 > 2$.

We now consider $\omega \in \mathcal{G}_n^+$ where $\mathcal{G}_n^+ := \mathcal{G}_n \cap \{x_1(W, h_n)\}$ is an $h_n$-minimum, that is,

$$ b_{-1}(W, h_n) = x_{-1}(W, h_n) < x_0(W, h_n) = M_{-1}(W, h_n) \le 0 < b_0(W, h_n) = x_1(W, h_n). $$

Indeed, the other case, that is, $x_0(W, h_n)$ is an $h_n$-minimum, or equivalently $\omega \in \mathcal{G}_n^-$ with $\mathcal{G}_n^- := \mathcal{G}_n^- \setminus \mathcal{G}_n^+$, is similar by symmetry.
<figure><img src="image_4.png" /><figcaption>Figure 1: Pattern of W for a good environment $\omega \in \mathcal{G}_n$ and representation of different quantities.</figcaption></figure>

Proof of Proposition 4.5. Let us see how we can derive Proposition 4.5 from (4.11) and from Lemmas 4.7, 4.9 and 4.11 below. Applying Lemma 4.7 with $y = 0$ and $j = -1$ on $\mathcal{G}_n^+$, the random walk $Z$ goes quickly to $b_{-1}$ or $b_0$ with high probability. More precisely, setting $E_1 := \{\tau(b_{-1}) \wedge \tau(b_0) \le n(\log n)^{-3C_2}\}$, there exists $\tilde{n}_0 \in \mathbb{N}$ such that, for every $n \ge \tilde{n}_0$,

$$ \forall \omega \in \mathcal{G}_n^+, \quad P_\omega(E_1) \ge 1 - (\log n)^{-2}. \qquad (4.12) $$

Due to Lemmas 4.9 and 4.11, there exists $\tilde{n}_1 \in \mathbb{N}$ such that, for every $n \ge \tilde{n}_1$,

$$ \forall \omega \in \mathcal{G}_n^+, \quad P_\omega[E_1, Z_n \notin \Xi_n(W)] \le 11(\log n)^{-2} $$

and so, using (4.12),

$$ \forall n \ge \max(\tilde{n}_0, \tilde{n}_1), \quad \forall \omega \in \mathcal{G}_n^+, \quad P_\omega[Z_n \notin \Xi_n(W)] \le 12(\log n)^{-2}. $$

By symmetry, this remains true with $\mathcal{G}_n^+$ replaced by $\mathcal{G}_n^-$. Therefore, due to (4.11), for every $n$ large enough,

$$ \mathbb{P}[Z_n \notin \Xi_n(W)] \le \int_{\mathcal{G}_n} P_\omega[Z_n \notin \Xi_n(W)] \mathbb{P}(d\omega) + \mathbb{P}[(\mathcal{G}_n)^c] \le 2(\log n)^{-2+\varepsilon}. $$

Since this is true for every $\varepsilon > 0$, this proves Proposition 4.5. $\square$

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

We will use the following property. For $j \in \mathbb{Z}$, let

$$ \begin{aligned} \hat{\mu}_j(x) &:= \exp[-(V(x) - V(b_j))] + \exp[-(V(x-1) - V(b_j))] \\ &= \exp[V(b_j)]\mu_\omega(x), \quad x \in \mathbb{Z}, \end{aligned} $$

with reversible measure $\mu_\omega$ defined in (2.11). It follows from reversibility that

$$ \forall k \in \mathbb{N}, \forall x \in \mathbb{Z}, \forall b \in \mathbb{Z}, \quad P_\omega^b[Z_k = x] = \frac{\mu_\omega(x)}{\mu_\omega(b)} P_\omega^x[Z_k = b] \le \frac{\mu_\omega(x)}{\mu_\omega(b)} \le \exp[V(b)]\mu_\omega(x). \qquad (4.13) $$

In particular,

$$ \forall j \in \mathbb{Z}, \forall k \in \mathbb{N}, \forall x \in \mathbb{Z}, \quad P_\omega^{b_j}[Z_k = x] \le \hat{\mu}_j(x). \qquad (4.14) $$
**Lemma 4.7.** There exists $n_0 \in \mathbb{N}$ such that, for every $n \ge n_0$, every $\omega \in \mathcal{G}_n$, every $j \in \{-2, ..., 1\}$ and every integer $y \in ]b_j, b_{j+1}$[,

$$P_{\omega}^{y}[\tau(b_j) \wedge \tau(b_{j+1}) > n(\log n)^{-3C_2}] \le (\log n)^{-2}. \quad (4.15)$$

*Proof.* Let $j \in \{-2, ..., 1\}$ and $\omega \in \mathcal{G}_n$. Assume for example that $y \in [M_j, b_{j+1}$[, the proof being symmetric in the case when $y \in ]b_j, M_j]$.

$$A_j^+ := \min(b_{j+1}, \inf\{k \ge M_j : W(k) \le W(M_j(W, h_n)) - h_n - C_2 \log^{(2)} n\}),$$

$$A_j^- := \max(b_j, \sup\{k \le M_j : W(k) \le W(M_j(W, h_n)) - h_n - C_2 \log^{(2)} n\}).$$

1. If $y \in [M_j, A_j^+[$, due to (2.4), (4.4) and (4.9), applying Markov's inequality, we get

$$\begin{aligned} P_{\omega}^{y} \left[ \tau(A_{j}^{-}) \wedge \tau(A_{j}^{+}) > \frac{e^{h_{n}+2C_{2} \log^{(2)} n}}{2} \right] & \le \frac{2\varepsilon_{0}^{-1}[b_{j+1}-b_{j}]^{2}}{e^{h_{n}+2C_{2} \log^{(2)} n}} \exp \left[ \max_{[b_{j},b_{j+1}]} V - \min_{[A_{j}^{-},A_{j}^{+}]} V \right] \\ & \le \frac{2\varepsilon_{0}^{-1}[M_{2}-b_{-2}]^{2}}{e^{h_{n}+2C_{2} \log^{(2)} n}} e^{\left(W(M_{j}(W,h_{n}))+\tilde{C}_{1} \log^{(2)} n\right)-\left(W(M_{j}(W,h_{n}))-h_{n}-C_{2} \log^{(2)} n-\tilde{C}_{1} \log^{(2)} n-\log \varepsilon_{0}^{-1}\right)} \\ & \le \frac{8\varepsilon_{0}^{-1}(\log n)^{2\alpha} e^{h_{n}+(C_{2}+2\tilde{C}_{1})\log^{(2)} n+\log \varepsilon_{0}^{-1}}}{e^{h_{n}+2C_{2} \log^{(2)} n}} \le 8\varepsilon_{0}^{-2}(\log n)^{2\alpha+2\tilde{C}_{1}-C_{2}} \le \frac{1}{3}(\log n)^{-2} \end{aligned}$$

for every $n$ large enough, where we used $\sup_{[b_j(W,h_n),b_{j+1}(W,h_n)]} W = W(M_j(W, h_n))$ and $V(A_j^+) \ge V(A_j^+ \mp 1) - \log \frac{1-\varepsilon_0}{\varepsilon_0}$ in the second line and $C_2 > 2\alpha + 2\tilde{C}_1 + 2$ in the last one. Hence by the strong Markov property, for $n$ large enough, for every $y \in [M_j, A_j^+]$,

$$\begin{aligned} P_{\omega}^{y} \left[ \tau(b_j) \wedge \tau(b_{j+1}) > e^{h_n + 2C_2 \log^{(2)} n} \right] & \\ \le \frac{1}{3}(\log n)^{-2} + P_{\omega}^{A_j^{-}} \left[ \tau(b_j) > e^{h_n + 2C_2 \log^{(2)} n / 2} \right] + P_{\omega}^{A_j^{+}} \left[ \tau(b_{j+1}) > e^{h_n + 2C_2 \log^{(2)} n / 2} \right]. \end{aligned} \quad (4.16)$$

2. Assume now that $y \in [A_j^+, b_{j+1}$[ (and so $A_j^+ < b_{j+1}$). Observe that $W$ admits no $h_n$-maximum in the interval $]M_j(W, h_n), b_{j+1}(W, h_n]$) by definition of $M_j(.)$, so

$$\max_{M_j(W,h_n) \le u \le v \le b_{j+1}(W,h_n)} (W(v) - W(u)) < h_n.$$

Hence due to (2.4), (4.4), (4.9), and to Markov's inequality, we have

$$\begin{aligned} P_{\omega}^{y} \left[ \tau(M_j) \wedge \tau(b_{j+1}) > e^{h_n + 2C_2 \log^{(2)} n / 2} \right] & \\ \le \frac{2[M_2 - b_{-2}]^2}{\varepsilon_0 e^{h_n + 2C_2 \log^{(2)} n}} \exp \left[ \max_{M_j \le l \le k \le b_{j+1}} (V(k) - V(l)) \right] & \\ \le \frac{8\varepsilon_0^{-1}(\log n)^{2\alpha} e^{h_n + 2\tilde{C}_1 \log^{(2)} n}}{e^{h_n + 2C_2 \log^{(2)} n}} & \\ \le \frac{1}{6}(\log n)^{-2} \end{aligned} \quad (4.17)$$

for every $n$ large enough, since $2C_2 > 2\alpha + 2\tilde{C}_1 + 2$. Moreover, due to (2.3), (4.4) and (4.9), and since there is no $h_n$-maximum in $[A_j^+, b_{j+1}]$ and so $\sup_{[A_j^+, b_{j+1}]} W < W(A_j^+) + h_n$,

$$\begin{aligned} P_{\omega}^{y}[\tau(M_j) < \tau(b_{j+1})] & \le \left(\sum_{\ell=A_j^+}^{b_{j+1}-1} e^{V(\ell)}\right) \left(\sum_{\ell=M_j}^{b_{j+1}-1} e^{V(\ell)}\right)^{-1} \\ & \le [b_{j+1} - A_j^+] \exp \left(\max_{\ell \in \{A_j^+, \dots, b_{j+1}\}} V(\ell)\right) \exp(-V(M_j)) \end{aligned}$$
$$
\begin{align}
&\le 2(\log n)^\alpha \exp [W(A_j^+) + h_n - W(M_j(W, h_n)) + 2\tilde{C}_1 \log^{(2)} n] \nonumber \\
&\le 2(\log n)^{\alpha-C_2+2\tilde{C}_1} \le \frac{1}{6}(\log n)^{-2} \tag{4.18}
\end{align}
$$

for every $y \in [A_j^+, b_{j+1}]$ for all $n$ large enough, since $C_2 > \alpha + 2\tilde{C}_1 + 2$. Gathering (4.17) and (4.18), we get, for all $n$ large enough, for every $y \in [A_j^+, b_{j+1}]$, uniformly on $G_n$ as the previous inequalities,

$$
P_{\omega}^{y}[\tau(b_{j+1}) > n(\log n)^{-3C_2/2}] = P_{\omega}^{y}[\tau(b_{j+1}) > e^{h_n+2C_2 \log^{(2)} n}/2] \le \frac{1}{3}(\log n)^{-2}, \quad (4.19)
$$

recalling (4.3). This already proves (4.15) for $y \in [A_j^+, b_{j+1}]$.

3. For symmetry reasons, we also get that, for every $n$ large enough, for every $y \in ]b_j, A_j^-[$,

$$
P_{\omega}^{y}[\tau(b_j) > e^{h_n+2C_2 \log^{(2)} n}/2] \le \frac{1}{3}(\log n)^{-2}. \quad (4.20)
$$

Finally, combining (4.16) with (4.19) and (4.20) proves (4.15) for $y \in [M_j, A_j^+[$. Hence, (4.15) is true for $y \in [M_j, b_{j+1}[ \text{ thanks to 2., and for } y \in ]b_j, M_j]$ by symmetry. This proves the lemma. $\square$

We consider $\mathcal{I}_1 \in \{-1, 0\}$ such that $\tau(b_{\mathcal{I}_1}) = \tau(b_{-1}) \wedge \tau(b_0)$. Recall that $E_1 = E_1(n) := \{\tau(b_{\mathcal{I}_1}) \le \alpha_n\}$, where we set

$$
\alpha_n := n(\log n)^{-3C_2}. \tag{4.21}
$$

We already saw in (4.12) that, thanks to Lemma 4.7 with $y=0$ and $j=-1$, we have

$$
\forall \omega \in \mathcal{G}_n^+, \quad P_\omega(E_1) \ge 1 - (\log n)^{-2}.
$$

We consider the event $E_2 = E_2(n)$ on which $Z$ first goes to the bottom of a "deep" valley:

$$
E_2^+(j) := \{W[M_j(W, h_n)] - W[b_j(W, h_n)] > \log n + C_2 \log^{(2)} n\}, \quad j \in \mathbb{Z},
$$

$$
E_2^-(j) := \{W[M_{j-1}(W, h_n)] - W[b_j(W, h_n)] > \log n + C_2 \log^{(2)} n\}, \quad j \in \mathbb{Z},
$$

$$
E_2 := E_2^+(\mathcal{I}_1) \cap E_2^-(\mathcal{I}_1).
$$

Notice that this event depends on $\omega$ but also on the first steps of $Z$ up to time $\tau(b_{I_1})$. Similarly as in (4.7), this event happens with probability $1 - O((\log n)^{-1} \log^{(2)} n)$, so we cannot neglect $E_2^c$. We will treat separately the two events $E_2$ and $E_2^c$ (the study of $E_2^c$ being more complicated). Before considering these two events, we state the following useful result. We introduce for $j \in \mathbb{Z}$,

$$
M_j^+ := b_{j+1} \wedge \inf\{k \ge M_j, W(k) \le W(b_j(W, h_n)) + C_2 \log^{(2)} n\}, \quad (4.22)
$$

$$
M_j^- := b_{j-1} \vee \sup\{k \le M_{j-1}, W(k) \le W(b_j(W, h_n)) + C_2 \log^{(2)} n\}, \quad (4.23)
$$

where $u \vee v := \max(u, v)$, $(u, v) \in \mathbb{R}^2$, so that

$$
\forall k \in ]M_j^-, M_{j-1}] \cup [M_j, M_j^+[, \quad W(k) > W(b_j(W, h_n)) + C_2 \log^{(2)} n. \quad (4.24)
$$

**Lemma 4.8.** For every $n$ large enough,

$$
\forall \omega \in \mathcal{G}_n, \forall j \in \{-2, \dots, 2\}, \quad \sup_{k \ge 0} P_{\omega}^{b_j} (Z_k \in [M_j^-, M_j^+] \setminus \Xi_n(W)) \le (\log n)^{-2}. \quad (4.25)
$$
**Proof.** We claim that due to (4.9) and (4.4),

$$V(x) \geq W(b_j(W, h_n)) + C_2 \log^{(2)} n - \tilde{C}_1 \log^{(2)} n - \log \varepsilon_0^{-1}$$

for every integer $x \in ([M_j^-, M_j^+] \setminus \Xi_{n,j}(W))$ for $j \in \{-2, \dots, 2\}$. This follows from the definition of $\Xi_{n,j}(W)$ if $x \in [M_{j-1}, M_j]$, and from (4.24) and the fact that $|V(y) - V(y-1)| \le \log \frac{1-\varepsilon_0}{\varepsilon_0}$ otherwise. So, due to (4.14), (4.4) and (4.9), for large $n$, for all $\omega \in \mathcal{G}_n$ and $j \in \{-2, \dots, 2\}$,

$$ \begin{aligned} & \sup_{k \ge 0} P_{\omega}^{b_j}(Z_k \in [M_j^-, M_j^+] \setminus \Xi_n(W)) \\ & \le \sum_{x=M_j^-}^{M_j^+} 1_{\Xi_n(W)^c}(x) \hat{\mu}_j(x) \\ & \le \sum_{x=M_j^-}^{M_j^+} 1_{\Xi_{n,j}(W)^c}(x) e^{V(b_j)} [e^{-V(x)} + e^{-V(x)+\log \frac{1-\varepsilon_0}{\varepsilon_0}}] \\ & \le 2(\log n)^{\alpha} \varepsilon_0^{-1} e^{(W(b_j(W,h_n))+\tilde{C}_1 \log^{(2)} n) - (W(b_j(W,h_n))+(C_2-\tilde{C}_1) \log^{(2)} n - \log \varepsilon_0^{-1})} \\ & = 2\varepsilon_0^{-2}(\log n)^{\alpha+2\tilde{C}_1-C_2} \le (\log n)^{-2}, \end{aligned} $$

$$\text{since } C_2 \ge 2\alpha + 2 + 10 \tilde{C}_1.$$

□

In the next lemma, we consider the case where $Z$ goes quickly in a deep valley.

**Lemma 4.9 (Simplest case).** There exists $n_1 \in \mathbb{N}$ such that for all $n \ge n_1$,

$$\forall \omega \in \mathcal{G}_n^+, \quad P_{\omega}(E_1, E_2, Z_n \notin \Xi_n(\omega)) \le 3(\log n)^{-2}.$$

**Proof.** Due to (2.6), (4.4) and (4.9), we have for large $n$, for all $\omega \in \mathcal{G}_n^+$ and all $j \in \{-2, \dots, 2\}$ uniformly on $E_2^+(j)$,

$$ \begin{aligned} P_{\omega}^{b_j}[\tau(M_j) < n] &\le ne^{\min_{[b_j, M_{j-1}]} V-V(M_{j-1})} \le ne^{V(b_j)-V(M_{j-1})} \\ &\le n \exp \left[ (W(b_j(W,h_n)) + \tilde{C}_1 \log^{(2)} n) - (W(M_j(W,h_n)) - \tilde{C}_1 \log^{(2)} n - \log \varepsilon_0^{-1}) \right] \\ &\le ne^{-(\log n+C_2 \log^{(2)} n)+2\tilde{C}_1 \log_2 n+\log \varepsilon_0^{-1}} = \varepsilon_0^{-1}(\log n)^{2\tilde{C}_1-C_2} \le (\log n)^{-2}, \quad (4.26) \end{aligned} $$

since $C_2 \ge 2\alpha + 2 + 10 \tilde{C}_1$. Similarly, using (2.7) instead of (2.6), we have for large $n$, for all $\omega \in \mathcal{G}_n^+$ and all $j \in \{-2, \dots, 2\}$, uniformly on $E_2^-(j)$,

$$P_{\omega}^{b_j}[\tau(M_{j-1}) < n] \le (\log n)^{-2}. \quad (4.27)$$

Let

$$\tau(x, y) := \inf\{k \ge 0, Z_{\tau(x)+k} = y\}, \quad x \in \mathbb{Z}, y \in \mathbb{Z}.$$

In particular, on $E_1 \cap E_2 \cap \{\tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1-1}) \ge n\} \cap \{\tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1}) \ge n\}$, recalling (4.21),

$$\tau(b_{\mathcal{I}_1}) \le \alpha_n \le n \le \tau(b_{\mathcal{I}_1}) + \tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1-1}) \wedge \tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1}),$$

and so $Z_n \in [M_{\mathcal{I}_1-1}, M_{\mathcal{I}_1}] \subset [M_{\mathcal{I}_1}^-, M_{\mathcal{I}_1}^+]$. Applying (4.26) and (4.27) combined with the strong Markov property at time $\tau(b_{\mathcal{I}_1})$, and then (4.25), we get for large $n$, for every $\omega \in \mathcal{G}_n^+$,

$$ \begin{aligned} & P_{\omega}[E_1, E_2, Z_n \notin \Xi_n(W)] \\ & \le P_{\omega}[E_1, E_2, Z_n \notin \Xi_n(W), \tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1-1}) \ge n, \tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1}) \ge n] \end{aligned} $$
Collisions of several walkers in recurrent random environments

$$
\begin{align}
&+P_{\omega}[E_2, \tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1-1}) < n] + P_{\omega}[E_2, \tau(b_{\mathcal{I}_1}, M_{\mathcal{I}_1}) < n] \nonumber \\
&\le E_{\omega}[1_{E_1} P_{\omega}^{b_{\mathcal{I}_1}}(Z_{n-k} \in [M_{\mathcal{I}_1-1}, M_{\mathcal{I}_1}] \setminus \Xi_n(W))_{|k=\tau(b_{\mathcal{I}_1})}] + 2(\log n)^{-2} \nonumber \\
&\le 3(\log n)^{-2}. \tag{4.28}
\end{align}
$$

This proves the lemma.

□

For the event $E_2^c$, we will use the following lemma, which is actually true for any Markov chain.

**Lemma 4.10.** Let $a \neq b$. We have,

$$
\forall k \in \mathbb{N}, \quad P_{\omega}^{b}[\tau(a) = k] \leq P_{\omega}^{b}[\tau(a) < \tau(b)].
$$

*Proof.* Let $k \in \mathbb{N}^*$. We have, by the Markov property,

$$
\begin{align*}
P_{\omega}^{b}[\tau(a) = k] &= \sum_{n=0}^{k} P_{\omega}^{b}[\tau(a) = k, Z_n = b, \forall n < \ell \le k, Z_{\ell} \ne b] \\
&\le \sum_{n=0}^{k} P_{\omega}^{b}[Z_n = b] P_{\omega}^{b}[\tau(a) = k - n, \tau(a) < \tau(b)] \\
&\le P_{\omega}^{b}[\tau(a) \in [0, k], \tau(a) < \tau(b)] \\
&\le P_{\omega}^{b}[\tau(a) < \tau(b)],
\end{align*}
$$

where we used $P_{\omega}^{b}[Z_n = b] \le 1$ in the second inequality.

□

**Lemma 4.11 (Most difficult case).** There exists $n'_1 \in \mathbb{N}$ such that for all $n \ge n'_1$,

$$
\forall \omega \in \mathcal{G}_n^+, \quad P_\omega(E_1, E_2^c, Z_n \notin \Xi_n(\omega)) \le 8(\log n)^{-2}.
$$

*Proof.* An essential remark is that if we are on $E_2^c$ with $\omega \in \mathcal{G}_n^+$, then, due to (4.10), either we are on $E_2^-(\mathcal{I}_1) \setminus E_2^+(\mathcal{I}_1)$ or on $E_2^+(\mathcal{I}_1) \setminus E_2^-(\mathcal{I}_1)$. In the first case we set

$$
\mathcal{I}_2 := \mathcal{I}_1 + 1, A := M_{\mathcal{I}_1}^{+}, B := M_{\mathcal{I}_1}(W, h_n) \text{ and } D := M_{\mathcal{I}_1}^{-}.
$$

whereas in the second case we set

$$
\mathcal{I}_2 := \mathcal{I}_1 - 1, A := M_{\mathcal{I}_1}^{-}, B := M_{\mathcal{I}_1-1}(W, h_n) \text{ and } D := M_{\mathcal{I}_1}^{+}.
$$

Loosely speaking, with large probability, $b_{\mathcal{I}_2}$ is the bottom of the second valley reached by $Z$, and $Z$ can reach it before time $n$ or not, so we have to consider both cases.

$$
\text{We introduce } \tau'(A, b_{\mathcal{I}_2}) := \inf\{k \ge 0, Z_{\tau(b_{\mathcal{I}_1})+\tau(b_{\mathcal{I}_1},A)+k} = b_{\mathcal{I}_2}\} \text{ and}
$$

$$
E_3 := \{\tau(b_{\mathcal{I}_1}) + \tau(b_{\mathcal{I}_1}, A) < n - 2n(\log n)^{-6C_2}\} \cap \{\tau'(A, b_{\mathcal{I}_2}) \le n(\log n)^{-6C_2}\},
$$

$$
E_4 := \{\tau(b_{\mathcal{I}_1}) + \tau(b_{\mathcal{I}_1}, A) \in [n - 2n(\log n)^{-6C_2}, n]\},
$$

$$
E_5 := \{\tau(b_{\mathcal{I}_1}) + \tau(b_{\mathcal{I}_1}, A) > n\} \cap \{\tau(b_{\mathcal{I}_1}, D) > n\},
$$

$$
E_6 := \{\tau(b_{\mathcal{I}_1}, D) \le n\},
$$

$$
E_7 := \{\tau'(A, b_{\mathcal{I}_2}) \ge n(\log n)^{-6C_2}\}.
$$

Notice that

$$
E_2^c \subset E_3 \cup E_4 \cup E_5 \cup E_6 \cup E_7. \tag{4.29}
$$
• Control on $E_6$. First, $E_2^c \cap \{\mathcal{I}_2 = \mathcal{I}_1 + 1\} \subset E_2^-(\mathcal{I}_1)$, so by (4.27) and since $D = \overline{M_{\mathcal{I}_1}^-} < M_{\mathcal{I}_1-1} < b_{\mathcal{I}_1}$ when $\mathcal{I}_2 = \mathcal{I}_1 + 1$, we have for large $n$ for every $\omega \in \mathcal{G}_n^+$,

$$ P_{\omega}(E_2^c \cap \{\mathcal{I}_2 = \mathcal{I}_1 + 1\} \cap E_6) \le E_{\omega}[1_{E_2^-(\mathcal{I}_1)} P_{\omega}^{b_{\mathcal{I}_1}}(\tau(M_{\mathcal{I}_1-1}) < \tau(D) \le n)] \le (\log n)^{-2}. \quad (4.30) $$

The case $\mathcal{I}_1 = \mathcal{I}_2 - 1$ follows similarly from (4.26), and so

$$ P_{\omega}(E_2^c \cap E_6) \le 2(\log n)^{-2} $$

for large $n$ for every $\omega \in \mathcal{G}_n^+$.

• Control on $E_4$. We start by proving that for every $n$ large enough, for every $\omega \in \mathcal{G}_n^+$, uniformly on $E_2^c$,

$$ \forall x \in \mathbb{N}, \quad P_{\omega}^{b_{\mathcal{I}_1}}[\tau(A) \in [n - 2n(\log n)^{-6C_2} - x, n - x]] \le (\log n)^{-2}. \quad (4.31) $$

Using Lemma 4.10 and then (2.3), we obtain on $E_2^-(\mathcal{I}_1) \setminus E_2^+(\mathcal{I}_1)$, since $b_{\mathcal{I}_1} < M_{\mathcal{I}_1} < A$,

$$ \begin{aligned} P_{\omega}^{b_{\mathcal{I}_1}}[\tau(A) = \ell] & \le P_{\omega}^{b_{\mathcal{I}_1}}[\tau(A) < \tau(b_{\mathcal{I}_1})] = \omega_{b_{\mathcal{I}_1}} P_{\omega}^{b_{\mathcal{I}_1}+1}[\tau(A) < \tau(b_{\mathcal{I}_1})] \\ & \le e^{V(b_{\mathcal{I}_1}) - V(M_{\mathcal{I}_1})} \le e^{W[b_{\mathcal{I}_1}(W,h_n)] - W[M_{\mathcal{I}_1}(W,h_n)] + 2\tilde{C}_1 \log^{(2)} n} \\ & \le e^{-h_n + 2\tilde{C}_1 \log^{(2)} n} = (\log n)^{5C_2 + 2\tilde{C}_1}/n \\ & \le (\log n)^{-2}/(3n(\log n)^{-6C_2}), \end{aligned} $$

for every $\ell \in \mathbb{N}$ and $\omega \in \mathcal{G}_n^+$ for every $n$ large enough, since $C_2 \ge 2\alpha + 2 + 10\tilde{C}_1$. Summing over $\ell$ proves (4.31) in this case, the other case $E_2^+(\mathcal{I}_1) \setminus E_2^-(\mathcal{I}_1)$ being very similar.

Due to (4.31), for large $n$, for every $\omega \in \mathcal{G}_n^+$, by the strong Markov property,

$$ \begin{aligned} P_{\omega}(E_2^c \cap E_4) &= E_{\omega}[1_{E_2^c} P_{\omega}^{b_{\mathcal{I}_1}}(\tau(A) \in [n - 2n(\log n)^{-6C_2} - x, n - x])]_{|x=\tau(b_{\mathcal{I}_1})}] \\ &\le (\log n)^{-2}. \end{aligned} \quad (4.32) $$

• Control on $E_7$. Let us prove that for $n$ large enough,

$$ \forall \omega \in \mathcal{G}_n^+, \quad P_{\omega}(E_2^c \cap E_7) \le (\log n)^{-2}. \quad (4.33) $$

Due to the strong Markov property, it is enough to prove that for large $n$, for every $\omega \in \mathcal{G}_n^+$, uniformly on $E_2^c$,

$$ P_{\omega}^{A}[\tau(b_{\mathcal{I}_2}) \ge n(\log n)^{-6C_2}] \le (\log n)^{-2}. \quad (4.34) $$

Recall that $h_n$-extrema are a fortiori $(h_n - 2C_2 \log^{(2)} n)$-extrema. Let us observe that due to (4.10) and since $W(B) - W(b_{\mathcal{I}_1}(W, h_n)) \le \log n + C_2 \log^{(2)} n$, the only possible slope $T_j[W, h_n - 2C_2 \log^{(2)} n]$, $-5 \le j \le 5$ with height $\le \log n + C_2 \log^{(2)} n$ is $[B, b_{\mathcal{I}_1}(W, h_n)]$ (or $[b_{\mathcal{I}_1}(W, h_n), B]$) so $W(B) - W(b_{\mathcal{I}_2}(W, h_n)) > \log n + C_2 \log^{(2)} n$. For the same reason, there is no $(h_n - 2C_2 \log^{(2)} n)$-extrema between $B$ and $b_{\mathcal{I}_2}(W, h_n)$, and so

$$ \sup_{B \le u \le v \le b_{\mathcal{I}_2}(W, h_n)} (W(v) - W(u)) < h_n - 2C_2 \log^{(2)} n $$

in the case $\mathcal{I}_2 = \mathcal{I}_1 + 1$. Hence in this case, due to (2.4), (4.4), (4.9) and to Markov's inequality, and since $[B] = M_{\mathcal{I}_1} < A < b_{\mathcal{I}_2}$,
$$
\begin{align*}
P_{\omega}^{A}[\tau(\lfloor B \rfloor) \wedge \tau(b_{\mathcal{I}_2}) \ge n(\log n)^{-6C_2}] &\le \frac{\varepsilon_0^{-1} 4(\log n)^{2\alpha} e^{h_n - 2C_2 \log^{(2)} n + 2\tilde{C}_1 \log^{(2)} n}}{n(\log n)^{-6C_2}} \\
&\le \varepsilon_0^{-1} 4(\log n)^{2\alpha - C_2 + 2\tilde{C}_1} \\
&\le \frac{1}{2}(\log n)^{-2}, \tag{4.35}
\end{align*}
$$

for every $n$ large enough since $C_2 \ge 2\alpha + 2 + 10 \tilde{C}_1$. This is also true in the case $\mathcal{I}_2 = \mathcal{I}_1 - 1$ by (2.5).

Moreover in the case $\mathcal{I}_2 = \mathcal{I}_1 + 1$, we have

$$
\begin{align*}
\max_{[A, b_{\mathcal{I}_2}]} V &\le \sup_{[M_{\mathcal{I}_1}^+, b_{\mathcal{I}_2}(W, h_n)]} W + \tilde{C}_1 \log^{(2)} n \\
&\le W(M_{\mathcal{I}_1}^+) + (h_n - 2C_2 \log^{(2)} n) + \tilde{C}_1 \log^{(2)} n
\end{align*}
$$

due to the previous remark, (4.4) and (4.9). Also,

$$
W(M_{\mathcal{I}_1}^{+}) \le W(b_{\mathcal{I}_1}(W, h_n)) + C_2 \log^{(2)} n
$$

by (4.22), otherwise we would have $M_{\mathcal{I}_1}^+ = b_{\mathcal{I}_1+1}$ and $W(b_{\mathcal{I}_1+1}) \ge W(b_{\mathcal{I}_1}(W, h_n)) + C_2 \log^{(2)} n \ge W(M_{\mathcal{I}_1}(W, h_n)) - \log n$ due to our hypothesis in this case $\mathcal{I}_2 = \mathcal{I}_1 + 1$, which in turn would give $W(M_{\mathcal{I}_1}(W, h_n)) - W(b_{\mathcal{I}_1+1}(W, h_n)) \le \log n + 2\tilde{C}_1 \log^{(2)} n$, which contradicts (4.10) since $2\tilde{C}_1 < C_2$. So by (2.3), (4.4) and (4.9), recalling that $W(b_{\mathcal{I}_1}(W, h_n)) + h_n \le W(M_{\mathcal{I}_1}(W, h_n))$ and $B = M_{\mathcal{I}_1}$, we get

$$
\begin{align*}
& P_{\omega}^{A}[\tau(\lfloor B \rfloor) < \tau(b_{\mathcal{I}_2})] \\
\le {} & (b_{\mathcal{I}_2} - A) \exp \left[ \max_{[A, b_{\mathcal{I}_2}]} V - V(B) \right] \\
\le {} & 2(\log n)^{\alpha} e^{(W(b_{\mathcal{I}_1}(W, h_n)) + h_n + (\tilde{C}_1 - C_2) \log^{(2)} n) - (W(M_{\mathcal{I}_1}(W, h_n)) - \tilde{C}_1 \log^{(2)} n)} \\
\le {} & 2(\log n)^{\alpha + 2\tilde{C}_1 - C_2} \le (\log n)^{-2/2} \tag{4.36}
\end{align*}
$$

for every $n$ large enough since $C_2 \ge 2\alpha + 2 + 10 \tilde{C}_1$. We prove similarly (4.36) in the case $\mathcal{I}_2 = \mathcal{I}_1 - 1$. Then, (4.35) and (4.36) prove (4.34). Finally, (4.34) combined with the strong Markov property lead to (4.33).

• Control on $E_5$. On $E_1 \cap E_2^c \cap E_5$, we have $\tau(b_{\mathcal{I}_2}) \le n \le \tau(b_{\mathcal{I}_1}) + \tau(b_{\mathcal{I}_1}, A) \wedge \tau(b_{\mathcal{I}_1}, D)$ and in particular $Z_n \in [A \wedge D, A \vee D] = [M_{\mathcal{I}_1}^-, M_{\mathcal{I}_1}^+]$. Applying (4.25) as in the simplest case, we get for large $n$, for all $\omega \in \mathcal{G}_n$,

$$
\begin{align*}
& P_{\omega}(E_1 \cap E_2^c \cap E_5, Z_n \notin \Xi_n(W)) \\
\le {} & E_{\omega}[1_{\{\tau(b_{\mathcal{I}_1}) \le \alpha_n\}} P_{\omega}^{b_{\mathcal{I}_1}}(Z_{n-k} \in [M_{\mathcal{I}_1}^-, M_{\mathcal{I}_1}^+] \setminus \Xi_n(W))|_{k=\tau(b_{\mathcal{I}_1})}] \\
\le {} & (\log n)^{-2}. \tag{4.37}
\end{align*}
$$

• Control on $E_3$. On $E_1 \cap E_2^c \cap E_3$, we have $\tau(b_{\mathcal{I}_2}) \le \tau(b_{\mathcal{I}_1}) + \tau(b_{\mathcal{I}_1}, A) + \tau'(A, b_{\mathcal{I}_2}) < n$. Moreover, the height of the valley $[M_{\mathcal{I}_2-1}(W, h_n), M_{\mathcal{I}_2}(W, h_n)]$ is at least $\log n + C_2 \log^{(2)} n$ on $E_2^c$ due to (4.10), that is, we are on $E_2^-(\mathcal{I}_2) \cap E_2^+(\mathcal{I}_2)$. Also we get $P_{\omega}^{b_{\mathcal{I}_2}}[\tau(M_{\mathcal{I}_2-1}) \wedge \tau(M_{\mathcal{I}_2}) < n] \le 2(\log n)^{-2}$ by (4.26) and (4.27) uniformly on $E_2^c \cap \mathcal{G}_n^+$ for large $n$. Using (4.25) and $[M_{\mathcal{I}_2-1}, M_{\mathcal{I}_2}) \subset [M_{\mathcal{I}_2}^-, M_{\mathcal{I}_2}^+]$, this gives for large $n$ for every $\omega \in \mathcal{G}_n^+$,

$$
\begin{align*}
& P_{\omega}(E_1 \cap E_2^c \cap E_3, Z_n \notin \Xi_n(W)) \\
\le {} & E_{\omega}[1_{\{\tau(b_{\mathcal{I}_2}) < n\}} P_{\omega}^{b_{\mathcal{I}_2}}(Z_{n-k} \in [M_{\mathcal{I}_2}^-, M_{\mathcal{I}_2}^+] \setminus \Xi_n(W))|_{k=\tau(b_{\mathcal{I}_2})}] \\
& \quad + E_{\omega}[1_{E_2^c} P_{\omega}^{b_{\mathcal{I}_2}}[\tau(M_{\mathcal{I}_2-1}) \wedge \tau(M_{\mathcal{I}_2}) < n]] \\
\le {} & 3(\log n)^{-2}. \tag{4.38}
\end{align*}
$$
Finally, (4.29) and the controls on $E_i$, $3 \le i \le 7$ prove Lemma 4.11, which ends the proof of Proposition 4.5. □

# 5 Probability of simultaneous meeting of independent recurrent RWRE in the same environment

This section is devoted to the proof of Proposition 1.5, which is a consequence of the following proposition whose proof is deferred.

Let $r > 1$ and let $Z^{(1)}, ..., Z^{(r)}$ be $r$ independent recurrent RWRE in the same environment $\omega$ satisfying (2.1).

**Proposition 5.1.** Let $\delta \in (0, 1)$. There exist events $\Delta_N(\delta)$, $N \ge 1$ and $\hat{b}(N) \in 2\mathbb{Z}$ depending only on the environment $\omega$, and constants $c(\delta) > 0$, $\varepsilon(\delta) \in (0, 1)$, with

$$ \liminf_{N \to +\infty} \mathbf{P}[\Delta_N(\delta)] \ge 1 - \delta, \qquad (5.1) $$

such that

$$ \begin{gathered} \forall (y_1, \dots, y_r) \in (2\mathbb{Z})^r, \exists N_1 \in \mathbb{N}, \forall N \ge N_1, \forall \omega \in \Delta_N(\delta), \forall j \in \{1, \dots, r\}, \\ \forall n \in [N^{1-\varepsilon(\delta)}, N] \cap (2\mathbb{N}), \quad P_{\omega}^{y_j}[Z_n^{(j)} = \hat{b}(N)] \ge c(\delta). \end{gathered} \qquad (5.2) $$

This remains true if $(2\mathbb{Z})^r$ and $2\mathbb{N}$ are replaced respectively by $(2\mathbb{Z} + 1)^r$ and $2\mathbb{N} + 1$.

**Proof of Proposition 1.5.** Let $\delta \in (0, 1)$. First, notice that by (5.1),

$$ \begin{aligned} \mathbf{P}[\limsup_{N \to +\infty} \Delta_N(\delta)] &= \mathbf{P}\left[\bigcap_{N \in \mathbb{N}} \bigcup_{n \ge N} \Delta_n(\delta)\right] = \lim_{N \to +\infty} \mathbf{P}\left[\bigcup_{n \ge N} \Delta_n(\delta)\right] \\ &\ge \liminf_{N \to +\infty} \mathbf{P}[\Delta_N(\delta)] \ge 1 - \delta. \end{aligned} \qquad (5.3) $$

Now, let $(y_1, \dots, y_r) \in (2\mathbb{Z})^r$. There exists $N_1 \in \mathbb{N}$ such that for every $N \ge N_1$, on $\Delta_N(\delta)$,

$$ \sum_{n=1}^{N} \frac{1}{n} \sum_{k \in \mathbb{Z}} \prod_{j=1}^{r} P_{\omega}^{y_j}[Z_n^{(j)} = k] \ge \sum_{n=N^{1-\varepsilon(\delta)}}^{N} \frac{1_{2\mathbb{N}}(n)}{n} [c(\delta)]^r \ge [c(\delta)]^r \frac{\varepsilon(\delta)}{4} \log N $$

if $N$ is large enough. Consequently, we have on $\limsup_{N \to +\infty} \Delta_N(\delta) = \{\omega \in \Delta_N(\delta) \text{ i.o.}\}$,

$$ \limsup_{N \to +\infty} \frac{1}{\log N} \sum_{n=1}^{N} \frac{1}{n} \sum_{k \in \mathbb{Z}} \prod_{j=1}^{r} P_{\omega}^{y_j}[Z_n^{(j)} = k] \ge [c(\delta)]^r \frac{\varepsilon(\delta)}{4} > 0. $$

This and (5.3) prove Proposition 1.5 in the case $(y_1, \dots, y_r) \in (2\mathbb{Z})^r$. The proof in the case $(y_1, \dots, y_r) \in (2\mathbb{Z} + 1)^r$ is similar. □

Now, it remains to prove Proposition 5.1.

## 5.1 Main idea of the proof of Proposition 5.1

Let $Z$ be a RWRE as in Section 2. In order to prove that $Z_n$ is localized at $\hat{b}(N)$ with a quenched probability $P_{\omega}^{y_j}$ greater than a positive constant, we use a coupling argument between a copy of $Z$ starting from $\hat{b}(N)$ and a RWRE $\hat{Z}$ reflected in some valley around $\hat{b}(N)$, under its invariant probability measure. To this aim, we approximate the potential $V$ by a Brownian motion $W$, use $W$ to build the set of good environments $\Delta_N(\delta)$ and estimate its probability $\mathbf{P}[\Delta_N(\delta)]$, and then define $\hat{b}(N)$.
We build $\Delta_N$ as the intersection of 7 events $\Delta_N^{(i)}$, $i = 0, \dots, 6$. First, $\Delta_N^{(0)}$ gives an approximation of $V$ by $W$. Loosely speaking $\Delta_N^{(1)}$ guarantees that the central valley (containing the origin) of height $\log n$ has a height much larger than $\log n$, so that $Z$ will not escape this valley before time $n$ (see Lemma 5.6). $\Delta_N^{(1)}$ also ensures that this central valley does not contain sub-valleys of height close to $\log n$, so that with high quenched probability, $Z$ reaches quickly the bottom of this valley without being trapped in such subvalleys (see Lemma 5.5). To this aim, we also need that the bottom of this valley is not too far from 0, which is given by $\Delta_N^{(3)}$, and that the value of the potential between 0 and the bottom of this valley is low enough, which is given by $\Delta_N^{(4)}$ and $\Delta_N^{(2)}$. Additionally, $\Delta_N^{(5)}$ is useful to provide estimates for the invariant probability measure $\hat{\nu}$, and is useful to prove that the coupling occurs quickly (Lemma 5.9, using Lemmas 5.7 and 5.8). Finally, $\Delta_N^{(6)}$ says that $\hat{\nu}(\hat{b}(N))$, which is roughly the invariant probability measure at the bottom of the central valley, is larger than a positive constant.

## 5.2 Construction of $\Delta_N(\delta)$

Let $\delta \in (0, 1)$. The aims of this section are the construction of the set of environments $\Delta_N(\delta)$ satisfying (5.1) and (5.2), and the proof of (5.1). We will construct $\Delta_N(\delta)$ as an intersection

$$ \Delta_N(\delta) := \bigcap_{i=0}^{6} \Delta_N^{(i)}, \qquad (5.4) $$

where the sets $\Delta_N^{(i)}$, defined below, also depend on $\delta$. In what follows, $\epsilon_i$ is for $i > 0$ a positive constant depending on $\delta$ and used to define the set $\Delta_N^{(i)}$. As in the previous section, we will approximate the potential $V$ by a two-sided Brownian motion $W$ such that $\mathrm{Var}(W(1)) = \mathrm{Var}(V(1))$ (see Figure 2 for patterns of the potential $V$ and of $W$ in $\Delta_N(\delta)$). We start with $\Delta_N^{(1)}, \dots, \Delta_N^{(5)}$ which are $W$-measurable. Using the same notation as before for $h$-extrema, for a two-sided Brownian motion $W$, we define

$$ \Delta_N^{(1)} := \{W \in \mathcal{W}\} \cap \bigcap_{i=-1}^{1} \{H[T_i(W, (1-2\epsilon_1) \log N)] \ge (1+2\epsilon_1) \log N\}, \quad (5.5) $$

$$ \Delta_N^{(R)} := \{x_1(W, (1-2\epsilon_1) \log N) \text{ is a } ((1-2\epsilon_1) \log N)\text{-minimum for } W\}, \quad (5.6) $$

and $\Delta_N^{(L)} := [\Delta_N^{(R)}]^c$, where $R$ stands for right and $L$ for left, $\Delta_N^{(2)} := \Delta_N^{(2,R)} \cup \Delta_N^{(2,L)}$ with

$$ \Delta_N^{(2,R)} := \left\{ \max_{[0, x_1(W, (1-2\epsilon_1) \log N)]} W < W(x_0(W, (1-2\epsilon_1) \log N)) - \epsilon_2 \log N \right\} \cap \Delta_N^{(R)}, \quad (5.7) $$

$$ \Delta_N^{(2,L)} := \left\{ \max_{[x_0(W, (1-2\epsilon_1) \log N), 0]} W < W(x_1(W, (1-2\epsilon_1) \log N)) - \epsilon_2 \log N \right\} \cap \Delta_N^{(L)}; \quad (5.8) $$

$$ \Delta_N^{(3)} := \left\{ -\epsilon_3^{-1}(\log N)^2 \le x_{-1}[W, (1-2\epsilon_1) \log N] \le x_2[W, (1-2\epsilon_1) \log N] \le \epsilon_3^{-1}(\log N)^2 \right\}; \quad (5.9) $$

$$ \Delta_N^{(4)} := \bigcap_{i=0}^{1} \{|W(x_i(W, (1-2\epsilon_1) \log N))| > \epsilon_4 \log N\} \quad (5.10) $$

and $\Delta_N^{(5)} := \Delta_N^{(5,R)} \cup \Delta_N^{(5,L)}$, where

$$ \Delta_N^{(5,L)} := \left\{ \min_{[0, x_1(W, (1-2\epsilon_1) \log N)]} W > W(x_0(W, (1-2\epsilon_1) \log N)) + \epsilon_5 \log N \right\} \cap \Delta_N^{(L)}, \quad (5.11) $$

$$ \Delta_N^{(5,R)} := \left\{ \min_{[x_0(W, (1-2\epsilon_1) \log N), 0]} W > W(x_1(W, (1-2\epsilon_1) \log N)) + \epsilon_5 \log N \right\} \cap \Delta_N^{(R)}. \quad (5.12) $$
**Lemma 5.2.** Let W be a two-sided Brownian motion such that Var(W(1)) = Var(V(1)). There exist $(\varepsilon_1, \varepsilon_2, \varepsilon_3, \varepsilon_4, \varepsilon_5) \in (0, 1/10)^4$ with $\varepsilon_5 = \varepsilon_2$ such that, for every $i \in \{1, ..., 5\}$, $P[\Delta_N^{(i)}] > 1 - \delta/10$.

<figure><img src="image_6.png" /><figcaption>Figure 2: Pattern of the potential V and of W for $\omega \in \Delta_N \cap \Delta_N^{(R)}$, where $x_i$ denotes $x_i(W, (1 - 2\varepsilon_1) \log N)$.</figcaption></figure>

*Proof.* First, by the same arguments as in the proof of Lemma 4.4, there exists $\varepsilon_1 \in (0, 1/10)$ such that $P[\Delta_N^{(1)}] \ge 1 - \delta/10$.

We now introduce $\tilde{W}_N(x) := W(x(\log N)^2)/\log N$, which has the same law as W by scaling. We notice that $x_0(\tilde{W}_N, 1 - 2\varepsilon_1)$ is a local extremum for $\tilde{W}_N$, so $P[x_0(\tilde{W}_N, 1 - 2\varepsilon_1) = 0] = 0$. Hence we have $x_0(\tilde{W}_N, 1 - 2\varepsilon_1) < 0 < x_1(\tilde{W}_N, 1 - 2\varepsilon_1)$ a.s.

We start with the case where $x_1(\tilde{W}_N, 1 - 2\varepsilon_1)$ is a $(1 - 2\varepsilon_1)$-minimum for $\tilde{W}_N$, that is, the bottom $b_0(W, (1 - 2\varepsilon_1) \log N)$ of the central valley of depth at least $(1 - 2\varepsilon_1) \log N$ for W is on the right. That is, we assume we are on $\Delta_N^{(R)} \cap W$.

Since $\tilde{W}_N$ is continuous on $[0, x_1(\tilde{W}_N, 1 - 2\varepsilon_1)]$, $\tilde{W}_N$ attains its maximum on this interval at some $y \in [0, x_1(\tilde{W}_N, 1 - 2\varepsilon_1)]$. So, $\tilde{W}_N(y) \in [0, \tilde{W}_N(x_0(\tilde{W}_N, 1 - 2\varepsilon_1))]$, since $\max_{[x_0(\tilde{W}_N, 1 - 2\varepsilon_1), x_1(\tilde{W}_N, 1 - 2\varepsilon_1)]} \tilde{W}_N = \tilde{W}_N(x_0(\tilde{W}_N, 1 - 2\varepsilon_1))$. If $\tilde{W}_N(y) = \tilde{W}_N(x_0(\tilde{W}_N, 1 - 2\varepsilon_1))$, then $y$ would be a $(1 - 2\varepsilon_1)$-maximum for $\tilde{W}_N$, with $x_0(\tilde{W}_N, 1 - 2\varepsilon_1) < y < x_1(\tilde{W}_N, 1 - 2\varepsilon_1)$, which is not possible on $W$. So, $\tilde{W}_N(y) = \max_{[0, x_1(\tilde{W}_N, 1 - 2\varepsilon_1)]} \tilde{W}_N < \tilde{W}_N(x_0(\tilde{W}_N, 1 - 2\varepsilon_1))$. Consequently, there exists $\varepsilon_2 \in (0, 1/10)$ such that

$$P\left[ \left[ 0, x_1(\tilde{W}_N, 1 - 2\varepsilon_1) \right] \max_{\tilde{W}_N < \tilde{W}_N(x_0(\tilde{W}_N, 1 - 2\varepsilon_1)) - \varepsilon_2} \Delta_N^{(R)} \right] \ge 1 - \frac{\delta}{10},$$

and the same is true if we exchange $x_0$ and $x_1$ by symmetry (and then $[0, x_1(...)]$ is replaced by $[x_0(...), 0]$, and $\Delta_N^{(R)}$ by $\Delta_N^{(L)}$). Hence $P[\Delta_N^{(2)}] \ge 1 - \delta/10$ by scaling.
Moreover, there exists $\varepsilon_3 \in (0, 1/10)$ such that $P[\Delta_N^{(3)}] = P[-\varepsilon_3^{-1} \le x_{-1}[\tilde{W}_N, 1-2\varepsilon_1] \le x_2[\tilde{W}_N, 1-2\varepsilon_1] \le \varepsilon_3^{-1}] \ge 1-\delta/10$, where we get the first equality by scaling.

Finally, there exists $\varepsilon_4 \in (0, 1/10)$ such that $P[\Delta_N^{(4)}] \ge 1 - \delta/10$, by scaling, since $|\tilde{W}_N(x_i(\tilde{W}_N, 1-2\varepsilon_1))| > 0$ a.s. for $i \in \{0, 1\}$. Indeed, $x_0(\tilde{W}_N, 1-2\varepsilon_1) < 0$, so $\tilde{W}_N(x_0(\tilde{W}_N, 1-2\varepsilon_1)) = \max_{[x_0(\tilde{W}_N, 1-2\varepsilon_1), 0]} \tilde{W}_N > 0$ a.s. on $\Delta_N^{(R)} \cap W$, and $\tilde{W}_N(x_0(\tilde{W}_N, 1-2\varepsilon_1)) = \min_{[x_0(\tilde{W}_N, 1-2\varepsilon_1), 0]} \tilde{W}_N < 0$ a.s. on $\Delta_N^{(L)} \cap W$, so $|\tilde{W}_N(x_0(\tilde{W}_N, 1-2\varepsilon_1))| > 0$ a.s. $|\tilde{W}_N(x_1(\tilde{W}_N, 1-2\varepsilon_1))| > 0$ a.s.

Replacing $W$ by $-W$ in $\Delta_N^{(2)}$ proves that with $\varepsilon_5 := \varepsilon_2 > 0$, the event $\Delta_N^{(5)}$ satisfies $P[\Delta_N^{(5)}] = P[\Delta_N^{(2)}] \ge 1 - \delta/10$. $\square$

From now on, $\varepsilon_1, \dots, \varepsilon_5$ are the ones given by Lemma 5.2. Let

$$ \varepsilon := \min(\varepsilon_1, \dots, \varepsilon_5)/9. \qquad (5.13) $$

**Lemma 5.3.** Up to an enlargement of $(\Omega, \mathcal{F}, P)$, there exist a two-sided Brownian motion $(W(s), s \in \mathbb{R})$ defined on $\Omega$ such that $\mathrm{Var}(W(1)) = \mathrm{Var}(V(1))$ and a real number $\xi > 0$ such that

$$ P\left[ \sup_{|t| \le 2\varepsilon_3^{-1}(\log N)^2} |V(\lfloor t \rfloor) - W(t)| > \varepsilon \log N \right] = O(N^{-\xi}). $$

*Proof.* Due to (4.1) (applied with $N$ replaced by $2\varepsilon_3^{-1}(\log N)^2$ and $x = (\varepsilon/2) \log N - a \log[2\varepsilon_3^{-1}(\log N)^2]$), there exists for $N$ large enough, possibly on an enlarged probability space, a Brownian motion $(W(s), s \in \mathbb{R})$ such that

$$ P\left[ \sup_{|k| \le 2\varepsilon_3^{-1}(\log N)^2} |V(k) - W(k)| > \frac{\varepsilon}{2} \log N \right] \le N^{-c \frac{\varepsilon}{10}} $$

and such that $\mathrm{Var}(W(1)) = \mathrm{Var}(V(1))$. Moreover,

$$ P\left[ \sup_{|t| \le 2\varepsilon_3^{-1}(\log N)^2} |W(t) - W(\lfloor t \rfloor)| > \frac{\varepsilon}{2} \log N \right] \le 5\varepsilon_3^{-1}(\log N)^2 P\left[ \sup_{|t| \le 1} |W(t)| > \frac{\varepsilon}{2} \log N \right] \\ = O((\log N)^2 \exp[-\varepsilon^2(\log N)^2/(8\sigma^2)]). $$

Combining these two inequalities proves the lemma. $\square$

Recall (5.4): it remains to define $\Delta_N^{(0)}$ and $\Delta_N^{(6)}$, see (5.14) and (5.16) below, and then we claim

**Lemma 5.4.** For large $N$, $P[\Delta_N(\delta)] \ge 1 - \delta$. Hence (5.1) holds true.

*Proof.* From now on, $W$ is the Brownian motion $W$ coming from Lemma 5.3 and $\Delta_N^{(1)}, \dots, \Delta_N^{(5)}$ are the corresponding events defined in (5.5)–(5.12). We set

$$ \Delta_N^{(0)} := \left\{ \sup_{|t| \le 2\varepsilon_3^{-1}(\log N)^2} |V(\lfloor t \rfloor) - W(t)| \le \varepsilon \log N \right\}. \qquad (5.14) $$

For $N$ large enough, $P[\Delta_N^{(0)}] > 1 - \delta/10$ by Lemma 5.3. In particular on the event $\Delta_N^{(0)} \cap \Delta_N^{(3)}$, we can apply the inequalities of $\Delta_N^{(0)}$ to any $t \in [x_{-1}(W, (1-2\varepsilon_1)\log N), x_2(W, (1-2\varepsilon_1)\log N)]$, since those $t$ satisfy $|t| \le \varepsilon_3^{-1}(\log N)^2$. We now introduce (here this is for $V$ directly, not for $W$)

$$ \theta_N^{(R)} := \inf \left\{ i \in \mathbb{N} \mid V(i) - \min_{0 \le j \le i} V(j) \ge (1 + \varepsilon_1) \log N \right\}, $$
$$ \beta_N^{(R)} := \sup \left\{ i < \theta_N^{(R)}, V(i) = \min_{0 \le j \le \theta_N^{(R)}} V(j) \right\}, $$

$$ \theta_N^{(L)} := \sup \left\{ i \in (-\mathbb{N}), V(i) - \min_{i \le j \le 0} V(j) \ge (1 + \varepsilon_1) \log N \right\}, $$

$$ \beta_N^{(L)} := \inf \left\{ i > \theta_N^{(L)}, V(i) = \min_{\theta_N^{(L)} \le j \le 0} V(j) \right\}. $$

By ([11], eq. (4.33)), there exists $\varepsilon_6 > 0$ such that if $N$ is large enough, $P[\Delta_N^{(6,R)}] \ge 1 - \delta/10$, where

$$ \Delta_N^{(6,R)} := \left\{ \sum_{i=0}^{\theta_N^{(R)}-1} e^{-[V(i)-V(\beta_N^{(R)})]} \le \varepsilon_6^{-1} \right\}, \quad \Delta_N^{(6,L)} := \left\{ \sum_{i=\theta_N^{(L)}}^{-1} e^{-[V(i)-V(\beta_N^{(L)})]} \le \varepsilon_6^{-1} \right\}. \qquad (5.15) $$

Replacing $V(.)$ by $V(-.)$ gives $P[\Delta_N^{(6,L)}] \ge 1 - \delta/10$. Consequently, $P[\Delta_N^{(6)}] \ge 1 - 2\delta/10$, where

$$ \Delta_N^{(6)} := \Delta_N^{(6,R)} \cap \Delta_N^{(6,L)}. \qquad (5.16) $$

This, combined with Lemma 5.2 and $P[\Delta_N^{(0)}] > 1 - \delta/10$, proves the lemma. $\square$

### 5.3 Random walk in an environment $\omega \in \Delta_N(\delta)$

The aim of this subsection is to prove Proposition 5.1 with the $\Delta_N(\delta)$ constructed in the previous subsection, see (5.4)-(5.12), (5.14) and (5.16). Let $\delta \in (0,1)$. We write $\Delta_N$ for $\Delta_N(\delta)$. We also fix $(y_1, \dots, y_r) \in (2\mathbb{Z})^r$. There exists $N_2 \in \mathbb{N}$ such that for $N \ge N_2$, $P[\Delta_N] \ge 1 - \delta$ (due to Lemma 5.4), $a_0 \le \varepsilon \log N$, and $\max_{1 \le j \le r} |y_j| < \min(\varepsilon_2, \varepsilon_4)(\log N)/(4a_0)$, where we set $a_0 := \log((1 - \varepsilon_0)/\varepsilon_0)$.

We introduce, recalling (5.6),

$$ \hat{b}(N) := 2\lfloor\beta_N^{(R)}/2\rfloor \mathbf{1}_{\Delta_N^{(R)}} + 2\lfloor\beta_N^{(L)}/2\rfloor \mathbf{1}_{\Delta_N^{(L)}}, \qquad (5.17) $$

We will carry out the proof in the case $\omega \in \Delta_N \cap \Delta_N^{(R)}$. The case $\omega \in \Delta_N \cap \Delta_N^{(L)}$ is similar by symmetry. We define $\hat{x}_i := \lfloor x_i(W, (1 - 2\varepsilon_1) \log N) \rfloor$, and

$$ D_N^{(1)} := \{ \tau(\hat{b}(N)) < \tau(\hat{x}_0) \}, \quad D_N^{(2)} := \{ \tau(\hat{x}_0) \wedge \tau(\hat{b}(N)) \le N^{1-\varepsilon_1} \}. $$

We sometimes write $x_i$ instead of $x_i(W, (1 - 2\varepsilon_1) \log N)$ in the following.

In the following lemma, we prove that $Z$ goes quickly to $\hat{b}(N)$, which is nearly the bottom of the potential $V$ in the central valley $[\hat{x}_0, \hat{x}_2]$, with large probability under $P_\omega^{y_j}$, uniformly on $\Delta_N \cap \Delta_N^{(R)}$ and $j$.

**Lemma 5.5.** There exists $N_3 \in \mathbb{N}$ such that for all $N \ge N_3$,

$$ \forall \omega \in \Delta_N \cap \Delta_N^{(R)}, \forall j \in \{1, \dots, r\}, \quad P_\omega^{y_j}[D_N^{(1)}] \ge 1 - N^{-(\varepsilon_1 \wedge \varepsilon_2)/4}, \quad P_\omega^{y_j}[D_N^{(2)}] \ge 1 - N^{-\varepsilon_1/4}. $$

*Proof.* Let $N \ge N_2$, $\omega \in \Delta_N \cap \Delta_N^{(R)}$ and $j \in \{1, \dots, r\}$. First, notice that $W(x_2) - W(x_1) = H[T_1(W, (1 - 2\varepsilon_1) \log N)] \ge (1 + 2\varepsilon_1) \log N$ because $\omega \in \Delta_N^{(1)}$. This gives, recalling (5.13)

$$ V(\hat{x}_2) - V(\hat{x}_1) \ge W(x_2) - W(x_1) - 2\varepsilon \log N \ge (1 + \varepsilon_1) \log N \qquad (5.18) $$

since $\omega \in \Delta_N^{(3)} \cap \Delta_N^{(0)}$ (see (5.14) and the remark after it). Hence,

$$ 0 \le \hat{b}(N) \le \beta_N^{(R)} \le \theta_N^{(R)} \le \hat{x}_2 \le \varepsilon_3^{-1} (\log N)^2. $$

Now, assume that $\theta_N^{(R)} < x_1$. Since $V(\theta_N^{(R)}) - V(\beta_N^{(R)}) \ge (1 + \varepsilon_1) \log N$, the previous inequalities would give, on $\Delta_N^{(0)} \cap \Delta_N^{(3)}$, $W(\theta_N^{(R)}) - W(\beta_N^{(R)}) \ge (1 + \varepsilon_1 - 2\varepsilon) \log N \ge$
(1 − 2 ε$_{1}$ ) log N . So, recalling that W ( x$_{1}$ ) = min$_{[0}$$_{,x}$$_{1}$$_{]}$ W , there would exist a ((1 − 2 ε$_{1}$ ) log N )-maximum for W in ]0 , x$_{1}$ [, which is not possible. Hence,

$x_1 \le \theta_N^{(R)}.$

So, V ( β ( R ) N ) ≤ V ( ̂ x$_{1}$ ) ≤ W ( x$_{1}$ )+ ε log N < − 8 ε$_{4}$ (log N ) / 9 because ω ∈ Δ (0) N ∩ Δ (3) N ∩ Δ (4) N . If y$_{j}$ > 0, then min$_{[0}$$_{,y}$$_{j}$$_{]}$ V ≥ − | y$_{j}$ | a$_{0}$ ≥ − ε$_{4}$ (log N ) / 4 > V ( β ( R ) N ) + 2 a$_{0}$ , because N ≥ N$_{2}$ . Since similarly, max$_{[0}$$_{,y}$$_{j}$$_{]}$ V ≤ ε$_{4}$ (log N ) / 4 and ε$_{4}$ < 1, we get successively y$_{j}$ ≤ θ ( R ) N and y$_{j}$ ≤ β ( R ) N − 2 ≤ ̂ b ( N ) − 1. If y$_{j}$ < 0, we prove similarly that ̂ x$_{0}$ < y$_{j}$ since V ( ̂ x$_{0}$ ) ≥ 8 ε$_{4}$ (log N ) / 9. Hence in every case,

$$
\hat{x}_0 < y_j < \hat{b}(N).
$$

We now prove that

$$
\max_{[y_j, \hat{b}(N)]} V - V(\hat{x}_0) \le -[(\varepsilon_1 \wedge \varepsilon_2)/2] \log N. \quad (5.19)
$$

To this aim, notice that

$$
\max_{[0, \hat{x}_1]} V - V(\hat{x}_0) \le -\varepsilon_2(\log N)/2
$$

since ω ∈ Δ (2 ,R ) N ∩ Δ (0) N ∩ Δ (3) N , and that if y$_{j}$ < 0, we have

$$
\max_{[y_j, 0]} V - V(\hat{x}_0) \le |y_j| a_0 - (8/9) \varepsilon_2 \log N \le -\varepsilon_2(\log N)/2
$$

since W ( x$_{0}$ ) ≥ ε$_{2}$ log N on Δ (2 ,R ) N and so V ( ̂ x$_{0}$ ) ≥ (8 / 9) ε$_{2}$ log N . This gives (5.19) when ̂ b ( N ) ≤ ̂ x$_{1}$ .

Assume now ̂ x$_{1}$ < ̂ b ( N ) . We have seen after (5.18) that 0 ≤ ̂ b ( N ) ≤ θ ( R ) N ≤ ̂ x$_{2}$ , moreover, V ( ̂ b ( N )) ≤ V ( β ( R ) N ) + a$_{0}$ and we have proved that V ( β ( R ) N ) ≤ V ( ̂ x$_{1}$ ) , so we obtain

$$
V(\hat{b}(N)) - \varepsilon \log N - a_0 \le V(\hat{x}_1) - \varepsilon \log N \le W(x_1) \le W(\hat{b}(N)) \le V(\hat{b}(N)) + \varepsilon \log N
$$

since W ( x$_{1}$ ) = min$_{[}$$_{x}$$_{0}$$_{,x}$$_{2}$$_{]}$ W and ω ∈ Δ (3) N ∩ Δ (0) N , so that

$$
|W(x_1) - V(\hat{b}(N))| \le \varepsilon \log N + a_0 \le 2\varepsilon \log N \le 2 \min(\varepsilon_1, \varepsilon_2)(\log N)/9. \quad (5.20)
$$

Moreover there is no ((1 − 2 ε$_{1}$ ) log N )-maximum for W in ( x$_{0}$, x$_{2}$ ), therefore,

$$
\max_{[x_1, \hat{b}(N)]} W < W(\hat{b}(N)) + (1 - 2\epsilon_1) \log N \le W(x_1) + (1 - 2\epsilon_1 + 3\epsilon_1/9) \log N, \quad (5.21)
$$

by Δ (0) N applied to ̂ b ( N ) followed by (5.20). Since V ( ̂ x$_{0}$ ) ≥ V ( ̂ x$_{1}$ ) + (1 + ε$_{1}$ ) log N on Δ (1) N ∩ Δ (0) N ∩ Δ (3) N , this gives max$_{[}$$_{̂}$ x$_{1}$$_{,}$$_{̂}$ b ( N $^{]}$V − V ( ̂ x$_{0}$ ) ≤ − ε$_{1}$ log N (since ω ∈ Δ (0) N ∩ Δ (3) N ). Recapitulating all this gives (5.19) also when ̂ x$_{1}$ < ̂ b ( N ).

So by (2.3) and (5.19), we get uniformly on Δ$_{N}$ ∩ Δ ( R ) N and j for large N ,

$$
P_{\omega}^{y_j} [(D_N^{(1)})^c] \leq [\hat{b}(N) - y_j] \exp \left[ \max_{[y_j, \hat{b}(N)]} V - V(\hat{x}_0) \right] \leq \frac{2\epsilon_3^{-1}(\log N)^2}{N(\epsilon_1 \wedge \epsilon_2)/2} \leq N^{-(\epsilon_1 \wedge \epsilon_2)/4},
$$

where we used ω ∈ Δ (3) N and ̂ x$_{0}$ < y$_{j}$ < ̂ b ( N ) < ̂ x$_{2}$ . This proves the first inequality of the lemma.
We now turn to $D_N^{(2)}$. Notice that $|\hat{b}(N) - \hat{x}_0| \le |\hat{x}_2 - \hat{x}_0| \le 3\epsilon_3^{-1}(\log N)^2$ on $\Delta_N$ since $0 \le \hat{b}(N) \le \hat{x}_2$ as proved after (5.18). Moreover, there is no $((1 - 2\epsilon_1) \log N)$-maximum for $W$ in $(x_0, x_1)$, so

$$ \max_{x_0 \le u \le v \le x_1} (W(v) - W(u)) < (1 - 2\epsilon_1) \log N. $$

Also if $x_1 < \hat{b}(N)$, $\min_{[x_0, \hat{b}(N)]} W = W(x_1)$ and (5.21) lead to $\max_{x_1 \le u \le v \le \hat{b}(N)} (W(v) - W(u)) \le (1 - 2\epsilon_1 + 3\epsilon_1/9) \log N$. Since $\omega \in \Delta_N^{(0)} \cap \Delta_N^{(3)}$, this gives

$$ \max_{\hat{x}_0 \le l \le k \le \hat{b}(N)} (V(k) - V(l)) \le (1 - 13\epsilon_1/9) \log N. \quad (5.22) $$

Hence, we have by (2.4),

$$ E_{\omega}^{y_j} [\tau(\hat{x}_0) \wedge \tau(\hat{b}(N))] \le \frac{|\hat{b}(N) - \hat{x}_0|^2}{\epsilon_0} \exp \left[ \max_{\hat{x}_0 \le l \le k \le \hat{b}(N)} (V(k) - V(l)) \right] \le \frac{9(\log N)^4 N^{1-\frac{13\epsilon_1}{9}}}{\epsilon_0 \epsilon_3^2}. $$

So due to Markov's inequality, $P_{\omega}^{y_j} [(D_N^{(2)})^c] \le N^{-\epsilon_1/4}$, uniformly in $\omega \in \Delta_N \cap \Delta_N^{(R)}$ and $j$, for large $N$. $\square$

In the following lemma, we prove that with large quenched probability, uniformly on $\Delta_N \cap \Delta_N^{(R)}$, after first hitting $\hat{b}(N)$, the random walk $Z$ stays in the central valley $[\hat{x}_0, \hat{x}_2]$ at least up to time $N$. To this aim, we now define

$$ D_N^{(3)} := \{ \forall k \in [\tau(\hat{b}(N)), \tau(\hat{b}(N)) + N - 1], \hat{x}_0 < Z_k < \hat{x}_2 \}. $$

**Lemma 5.6.** We have for large $N$,

$$ \forall \omega \in \Delta_N \cap \Delta_N^{(R)}, \forall j \in \{1, \dots, r\}, \quad P_{\omega}^{y_j} [D_N^{(3)}] = P_{\omega}^{\hat{b}(N)} [\tau(\hat{x}_0) \wedge \tau(\hat{x}_2) \ge N] \ge 1 - 2e^{2a_0 N^{-\epsilon_1}}. $$

*Proof.* Let $\omega \in \Delta_N \cap \Delta_N^{(R)}$. We recall that $|V(k) - V(k-1)| \le a_0$ for every $k \in \mathbb{Z}$. We have, since $x_1 \le \theta_N^{(R)}$ and so $V(\beta_N^{(R)}) \le V(\hat{x}_1)$, and by (5.18),

$$ V(\hat{b}(N)) - V(\hat{x}_2) \le V(\hat{x}_1) + a_0 - V(\hat{x}_2) \le a_0 - (1 + \epsilon_1) \log N. \quad (5.23) $$

Similarly,

$$ V(\hat{b}(N)) - V(\hat{x}_0) \le a_0 - (1 + \epsilon_1) \log N. \quad (5.24) $$

Hence (2.6) and (2.7) lead respectively to

$$ P_{\omega}^{\hat{b}(N)}(\tau(\hat{x}_2) < N) \le N \exp \left( \min_{[\hat{b}(N), \hat{x}_2-1]} V - V(\hat{x}_2-1) \right) \le N e^{2a_0 - (1+\epsilon_1) \log N} \le e^{2a_0} N^{-\epsilon_1}, $$

$$ P_{\omega}^{\hat{b}(N)}(\tau(\hat{x}_0) < N) \le N \exp \left( \min_{[\hat{x}_0, \hat{b}(N)-1]} V - V(\hat{x}_0) \right) \le N e^{2a_0 - (1+\epsilon_1) \log N} \le e^{2a_0} N^{-\epsilon_1}. $$

These two inequalities yield $P_{\omega}^{\hat{b}(N)} [\tau(\hat{x}_0) \wedge \tau(\hat{x}_2) < N] \le 2e^{2a_0} N^{-\epsilon_1}$, uniformly on $\Delta_N \cap \Delta_N^{(R)}$, which proves the lemma. $\square$

Now, similarly as in Brox [5] for diffusions in random potentials (see also [2, p. 45]), we introduce a coupling between $Z$ (under $P_{\omega}^{\hat{b}(N)}$) and a reflected random walk $\hat{Z}$ defined below. More precisely, we define, for fixed $N$, $\hat{\omega}_{\hat{x}_0} := 1$, $\hat{\omega}_x := \omega_x$ if $\hat{x}_0 < x < \hat{x}_2$, and $\hat{\omega}_{\hat{x}_2} := 0$. We consider a random walk $(\hat{Z}_n)_n$ in the environment $\hat{\omega}$, starting from $x \in [\hat{x}_0, \hat{x}_2]$, and denote its law by $P_{\hat{\omega}}^x$. That is, $\hat{Z}$ satisfies (1.2) with $\hat{\omega}$ instead of $\omega$ and
$\omega^{(j)}$ and $\hat{Z}$ instead of $Z^{(j)}$. In words, $\hat{Z}$ is a random walk in the environment $\omega$, starting from $x \in [\hat{x}_0, \hat{x}_2]$, and reflected at $\hat{x}_0$ and $\hat{x}_2$. Also, let

$$ \hat{\mu}(\hat{x}_0) := e^{-V(\hat{x}_0)}, \quad \hat{\mu}(\hat{x}_2) := e^{-V(\hat{x}_2-1)}, \quad \hat{\mu}(x) := e^{-V(x)} + e^{-V(x-1)}, \quad \hat{x}_0 < x < \hat{x}_2, $$

and $\hat{\mu}(x) = 0$ if $x \notin [\hat{x}_0, \hat{x}_2]$. Notice that $\hat{\mu}(.)/\hat{\mu}(Z)$ is an invariant probability measure for $\hat{Z}$. As a consequence,

$$ \hat{\nu}(x) := \hat{\mu}(x) \mathbf{1}_{2Z}(x) / \hat{\mu}(2Z), \quad x \in \mathbb{Z}, \qquad (5.25) $$

is an invariant probability measure for $(\hat{Z}_{2n})_n$ for fixed $\hat{\omega}$. That is, $P_{\hat{\omega}}^{\hat{\nu}}(\hat{Z}_{2k} = x) = \hat{\nu}(x)$ for every $x \in \mathbb{Z}$ and $k \in \mathbb{N}$, where $P_{\hat{\omega}}^{\hat{\nu}}(.) := \sum_{x \in \mathbb{Z}} \hat{\nu}(x) P_{\hat{\omega}}^{x}(.)$. Notice that $\hat{\nu}$ and $\hat{\mu}$ depend on $N$ and $\omega$.

We can now, again for fixed $N$ and $\omega$, build a coupling $Q_\omega$ of $Z$ and $\hat{Z}$, such that

$$ Q_{\omega}(\hat{Z} \in .) = P_{\hat{\omega}}^{\hat{\nu}}(\hat{Z} \in .), \quad Q_{\omega}(Z \in .) = P_{\omega}^{b(N)}(Z \in .), \qquad (5.26) $$

such that under $Q_\omega$, these two Markov chains move independently until

$$ \tau_{\hat{Z}=Z} := \inf \{ k \ge 0, \hat{Z}_k = Z_k \}, $$

which is their first meeting time, then $\hat{Z}_k = Z_k$ for every $\tau_{\hat{Z}=Z} \le k < \tau_{exit}$, where $\tau_{exit}$ is the next exit time of $Z$ from the central valley $[\hat{x}_0, \hat{x}_2]$, that is,

$$ \tau_{exit} := \inf \{ k > \tau_{\hat{Z}=Z}, Z_k \notin [\hat{x}_0, \hat{x}_2] \}, $$

and then $\hat{Z}$ and $Z$ move independently again after $\tau_{exit}$.

Now, we would like to prove that under $Q_\omega$, $Z$ and $\hat{Z}$ collide quickly, that is, $\tau_{\hat{Z}=Z}$ is very small compared to $N$. To this aim, we introduce

$$ \hat{L}^{-} := \sup\{k \le \hat{b}(N), V(k) - V(\hat{b}(N)) \ge (1 - \varepsilon_1) \log N\}, $$

$$ \hat{L}^{+} := \inf\{k \ge \hat{b}(N), V(k) - V(\hat{b}(N)) \ge (1 - \varepsilon_1) \log N\}. $$

Let $u \vee v := \max(u, v)$. We have the following:

**Lemma 5.7.** We have for large $N$, $\tau(.)$ denoting hitting times by $Z$ as before,

$$ \forall \omega \in \Delta_N \cap \Delta_N^{(R)}, \quad Q_\omega[\tau(\hat{L}^{-}) \vee \tau(\hat{L}^{+}) > N^{1-\varepsilon_1/2}] \le 4N^{-\varepsilon_1/4}. $$

*Proof.* Let $N \ge N_2$ and $\omega \in \Delta_N \cap \Delta_N^{(R)}$. Notice that similarly as after (5.18),

$$ \hat{x}_0 \le \hat{L}^{-} < \hat{b}(N) < \hat{L}^{+} \le \theta_N^{(R)} \le \hat{x}_2. $$

Because $\omega \in \Delta_N^{(5,R)} \cap \Delta_N^{(0)} \cap \Delta_N^{(3)}$ and due to (5.20), we have since $\varepsilon_5 = \varepsilon_2$,

$$ \forall k \in [\hat{x}_0, -1], \quad V(k) - V(\hat{b}(N)) \ge W(x_1) + (\varepsilon_5 - \varepsilon) \log N - V(\hat{b}(N)) \ge (\varepsilon_5/2) \log N. \quad (5.27) $$

Moreover, recalling $a_0 = \log((1-\varepsilon_0)/\varepsilon_0)$, we have $\min_{[0,\theta_N^{(R)}]} V = V(\beta_N^{(R)}) \ge V(\hat{b}(N)) - a_0$, so

$$ \min_{[\hat{x}_0, \hat{L}^+]} V \ge \min_{[\hat{x}_0, \theta_N^{(R)}]} V \ge V(\hat{b}(N)) - a_0. $$

Notice also for further use that, for every $k \in [\theta_N^{(R)}, \hat{x}_2]$, we have

$$ V(\theta_N^{(R)}) - V(k) \le W(\theta_N^{(R)}) - W(k) + 2\varepsilon \log N < (1 - 2\varepsilon_1 + 2\varepsilon) \log N $$
since $\omega \in \Delta_N^{(0)} \cap \Delta_N^{(3)}$ and because there is no $((1 - 2\varepsilon_1) \log N)\text{-maximum for } W$ in $(\hat{x}_1, \hat{x}_2)$ and $\hat{x}_1 \le \theta_N^{(R)} \le k \le \hat{x}_2$, as proved after (5.18). Since $V(\theta_N^{(R)}) - V(\hat{b}(N)) \ge (1 + \varepsilon_1) \log N - a_0$, this gives

$$ \begin{aligned} \forall k \in [\theta_N^{(R)}, \hat{x}_2], \quad V(k) - V(\hat{b}(N)) &= V(k) - V(\theta_N^{(R)}) + V(\theta_N^{(R)}) - V(\hat{b}(N)) \\ &\ge 2\varepsilon_1 \log N. \end{aligned} \quad (5.28) $$

Putting together these inequalities gives in particular $\min_{[\hat{x}_0, \hat{x}_2]} V \ge V(\hat{b}(N)) - a_0$. Furthermore,

$$ \max_{[\hat{b}(N), \hat{L}^+]} V \le V(\hat{b}(N)) + (1 - \varepsilon_1) \log N + a_0. \quad (5.29) $$

Hence,

$$ \max_{\hat{x}_0 \le l \le k \le \hat{L}^+ - 1, k \ge \hat{b}(N)} [V(k) - V(l)] \le \max_{[\hat{b}(N), \hat{L}^+]} V - \min_{[\hat{x}_0, \hat{L}^+]} V \le (1 - \varepsilon_1) \log N + 2a_0. $$

This, (2.4), Markov's inequality and $\omega \in \Delta_N^{(3)}$ give

$$ P_{\omega}^{\hat{b}(N)}[\tau(\hat{x}_0) \wedge \tau(\hat{L}^+) > N^{1-\varepsilon_1/2}] \le N^{-(1-\varepsilon_1/2)} \varepsilon_0^{-1} 4\varepsilon_3^{-2} (\log N)^4 N^{1-\varepsilon_1} e^{2a_0} \le N^{-\varepsilon_1/4} $$

uniformly for large $N$. Moreover by (2.3), (5.24), (5.29) and since $\omega \in \Delta_N^{(3)}$,

$$ P_{\omega}^{\hat{b}(N)}[\tau(\hat{x}_0) < \tau(\hat{L}^+)] \le (\hat{L}^+ - \hat{b}(N)) \exp \left[ \max_{[\hat{b}(N), \hat{L}^+]} V - V(\hat{x}_0) \right] \le \frac{(\log N)^2 e^{2a_0}}{\varepsilon_3 N^{2\varepsilon_1}} \le \frac{1}{N^{\varepsilon_1/4}} $$

uniformly for large $N$. Consequently,

$$ \begin{aligned} Q_{\omega}[\tau(\hat{L}^+) > N^{1-\varepsilon_1/2}] &= P_{\omega}^{\hat{b}(N)}[\tau(\hat{L}^+) > N^{1-\varepsilon_1/2}] \\ &\le P_{\omega}^{\hat{b}(N)}[\tau(\hat{x}_0) \wedge \tau(\hat{L}^+) > N^{1-\varepsilon_1/2}] + P_{\omega}^{\hat{b}(N)}[\tau(\hat{x}_0) < \tau(\hat{L}^+)] \\ &\le 2N^{-\varepsilon_1/4}. \end{aligned} $$

We prove similarly that $Q_{\omega}[\tau(\hat{L}^-) > N^{1-\varepsilon_1/2}] \le 2N^{-\varepsilon_1/4}$ uniformly for large $N$, using (2.5) and (5.23) instead of (2.4) and (5.24) respectively, and because $\min_{[\hat{x}_0, \hat{x}_2]} V \ge V(\hat{b}(N)) - a_0$ which we proved after (5.28). This proves Lemma 5.7. $\square$

**Lemma 5.8.** For large $N$,

$$ \forall \omega \in \Delta_N \cap \Delta_N^{(R)}, \quad \hat{\nu}([\hat{x}_0, \hat{L}^-]) + \hat{\nu}([\hat{L}^+, \hat{x}_2]) \le N^{-\varepsilon_1/4}. $$

*Proof.* Let $N \ge N_2$ and $\omega \in \Delta_N \cap \Delta_N^{(R)}$. Recall that $\hat{x}_0 \le \hat{L}^- < \hat{b}(N) < \hat{L}^+ \le \hat{x}_2$, which is proved before (5.27). Notice that $\hat{L}^- \le x_1 \le \hat{L}^+$, which is proved similarly as $x_1 \le \theta_N^{(R)}$ after (5.18). Using the same method as for (5.28) with $\hat{L}^+$ instead of $\theta_N^{(R)}$, we get $V \ge V(\hat{b}(N)) + (\varepsilon_1/3) \log N$ on $[\hat{L}^+, \hat{x}_2]$. Also, $V(\hat{L}^+ - 1) \ge V(\hat{b}(N)) + (\varepsilon_1/3) \log N$. Since $\hat{\mu}(2\mathbb{Z}) \ge e^{-V(\hat{b}(N))}$, this leads to

$$ \hat{\nu}([\hat{L}^+, \hat{x}_2]) \le [\hat{x}_2 - \hat{L}^+ + 2] e^{-V(\hat{b}(N))} N^{-\varepsilon_1/3} / \hat{\mu}(2\mathbb{Z}) \le 3\varepsilon_3^{-1} (\log N)^2 N^{-\varepsilon_1/3} \le N^{-\varepsilon_1/4} / 2 $$

uniformly for large $N$, where we used $\omega \in \Delta_N^{(3)}$. We prove similarly that $\hat{\nu}([\hat{x}_0, \hat{L}^-]) \le N^{-\varepsilon_1/4} / 2$ uniformly for large $N$, which ends the proof of the lemma. $\square$

**Lemma 5.9.** There exists $N_4 \in \mathbb{N}$ such that for $N \ge N_4$ for every $\omega \in \Delta_N \cap \Delta_N^{(R)}$,

$$ Q_{\omega}[\tau_{\hat{Z}=Z} > N^{1-\varepsilon_1/2}] \le 5N^{-\varepsilon_1/4} \quad (5.30) $$

and

$$ Q_{\omega}[\tau_{exit} \le N] \le Q_{\omega}[\tau(\hat{x}_0) \wedge \tau(\hat{x}_2) < N] = P_{\omega}^{\hat{b}(N)}[\tau(\hat{x}_0) \wedge \tau(\hat{x}_2) < N] \le 2e^{2a_0} N^{-\varepsilon_1}. \quad (5.31) $$
**Proof.** Due to Lemma 5.7, we have for large N for all $\omega \in \Delta_N \cap \Delta_N^{(R)}$,

$$
\begin{align*}
& Q_{\omega}[\tau_{\hat{Z}=Z} > N^{1-\varepsilon_1/2}] \\
\le {}& Q_{\omega}[\tau(\hat{L}^-) \lor \tau(\hat{L}^+) < \tau_{\hat{Z}=Z}] + Q_{\omega}[\tau(\hat{L}^-) \lor \tau(\hat{L}^+) > N^{1-\varepsilon_1/2}] \\
\le {}& Q_{\omega}[\tau(\hat{L}^-) < \tau_{\hat{Z}=Z}, \hat{Z}_0 < \hat{b}(N)] + Q_{\omega}[\tau(\hat{L}^+) < \tau_{\hat{Z}=Z}, \hat{Z}_0 \ge \hat{b}(N)] + 4N^{-\varepsilon_1/4}.
\end{align*}
$$

Notice that under $Q_\omega$, $Z_0 = \hat{b}(N) \in (2\mathbb{Z})$ by (5.26) and (5.17), and $\hat{Z}_0 \in (2\mathbb{Z})$ by (5.26) and (5.25). So the process $(\hat{Z}_k - Z_k)_{k \in \mathbb{N}}$ starts at $(\hat{Z}_0 - \hat{b}(N)) \in (2\mathbb{Z})$ and only makes jumps belonging to $\{-2, 0, 2\}$, and thus up to time $\tau_{\hat{Z}=Z} - 1$ it is $< 0$ (resp. $> 0$) on $\{\hat{Z}_0 < \hat{b}(N)\}$ (resp. $\{\hat{Z}_0 \ge \hat{b}(N)\}$), and in particular at time $\tau(\hat{L}^-)$ on $\{\tau(\hat{L}^-) < \tau_{\hat{Z}=Z}, \hat{Z}_0 < \hat{b}(N)\}$ (resp. at time $\tau(\hat{L}^+)$ on $\{\tau(\hat{L}^+) < \tau_{\hat{Z}=Z}, \hat{Z}_0 \ge \hat{b}(N)\}$). This gives for large N for all $\omega \in \Delta_N \cap \Delta_N^{(R)}$,

$$
\begin{align*}
& Q_{\omega}[\tau_{\hat{Z}=Z} > N^{1-\varepsilon_1/2}] \\
\le {}& Q_{\omega}[\tau(\hat{L}^-) < \tau_{\hat{Z}=Z}, \hat{Z}_{\tau(\hat{L}^-)} < \hat{L}^-] + Q_{\omega}[\tau(\hat{L}^+) < \tau_{\hat{Z}=Z}, \hat{Z}_{\tau(\hat{L}^+)} > \hat{L}^+] + 4N^{-\varepsilon_1/4} \\
\le {}& Q_{\omega}[\tau(\hat{L}^-) < \tau_{\hat{Z}=Z}, \hat{Z}_{2[\tau(\hat{L}^-)/2]} \le \hat{L}^-] + Q_{\omega}[\tau(\hat{L}^+) < \tau_{\hat{Z}=Z}, \hat{Z}_{2[\tau(\hat{L}^+)/2]} \ge \hat{L}^+] \\
& + 4N^{-\varepsilon_1/4} \\
\le {}& \hat{\nu}([\hat{x}_0, \hat{L}^-]) + \hat{\nu}([\hat{L}^+, \hat{x}_2]) + 4N^{-\varepsilon_1/4},
\end{align*}
$$

where the last inequality comes from the fact that $Q_\omega(\hat{Z}_{2k} = x) = P_\omega^{\hat{\nu}}(\hat{Z}_{2k} = x) = \hat{\nu}(x)$ for every $x \in \mathbb{Z}$ and every (deterministic) $k \in \mathbb{N}$ as explained after (5.25), and from the independence of $\hat{Z}$ with $Z$ and then $\tau(\cdot)$ up to $\tau_{\hat{Z}=Z}$. Now, applying Lemma 5.8, this gives (5.30) for large N for every $\omega \in \Delta_N \cap \Delta_N^{(R)}$.

Due to (5.26) and Lemma 5.6, for large N for every $\omega \in \Delta_N \cap \Delta_N^{(R)}$, (5.31) holds. $\square$

**Proof of Proposition 5.1.** Recall that we have fixed $\delta \in (0, 1)$ and that (5.1) comes from Lemma 5.4. Let us prove (5.2). To this aim, we fix $(y_1, \dots, y_r) \in (2\mathbb{Z})^r$. Let $N_1 \in \mathbb{N}$ be such that $N_1 \ge \max(N_2, N_3, N_4)$ and such that for every $N \ge N_1$,

$$
\begin{align*}
& \varepsilon_3^{-1} (\log N)^2 [N^{-\varepsilon_5/2} + 2N^{-2\varepsilon_1}] \le \varepsilon_6^{-1}, \quad N^{-(\varepsilon_1 \wedge \varepsilon_2 \wedge \varepsilon_4)/4} \le 1/8, \\
& N^{1-\varepsilon_1/3} \ge N^{1-\varepsilon_1} + N^{1-\varepsilon_1/2}, \quad \text{and} \quad 5N^{-\varepsilon_1/4} + 2e^{2a_0} N^{-\varepsilon_1} \le \varepsilon_6 e^{-a_0/6},
\end{align*}
$$

recalling $a_0 = \log((1 - \varepsilon_0)/\varepsilon_0)$.

Now, we would like to give a lower bound for $P_\omega^{y_j}[Z_n = \hat{b}(N)]$ for $n$ even. Recall (5.4) and (5.6). Let $N \ge N_1$, $\omega \in \Delta_N \cap \Delta_N^{(R)}$, $j \in \{1, \dots, r\}$, and $n \in (2\mathbb{N})$, with $n \in [N^{1-\varepsilon_1} + N^{1-\varepsilon_1/2}, N]$. We have by the strong Markov property,

$$
\begin{align*}
& P_{\omega}^{y_j}[Z_n = \hat{b}(N)] \\
\ge {}& P_{\omega}^{y_j}[Z_n = \hat{b}(N), \tau(\hat{b}(N)) \le N^{1-\varepsilon_1}] \\
= {}& E_{\omega}^{y_j}[\mathbf{1}_{\{\tau(\hat{b}(N)) \le N^{1-\varepsilon_1}\}} P_{\omega}^{\hat{b}(N)}(Z_k = \hat{b}(N))_{|k=n-\tau(\hat{b}(N))}] \\
\ge {}& P_{\omega}^{y_j}[\tau(\hat{b}(N)) \le N^{1-\varepsilon_1}] \inf_{k \in [N^{1-\varepsilon_1/2}, N] \cap (2\mathbb{N})} P_{\omega}^{\hat{b}(N)}(Z_k = \hat{b}(N)) \\
\ge {}& \left(1 - N^{-(\varepsilon_1 \wedge \varepsilon_2)/4} - N^{-\varepsilon_1/4}\right) \inf_{k \in [N^{1-\varepsilon_1/2}, N] \cap (2\mathbb{N})} P_{\omega}^{\hat{b}(N)}(Z_k = \hat{b}(N)) \tag{5.32}
\end{align*}
$$

because $\hat{b}(N)$ and $y_j$ are even (see (5.17)) and then $\tau(\hat{b}(N))$ is also even under $P_\omega^{y_j}$, and where we used Lemma 5.5 in the last line. Moreover, for $k \in [N^{1-\varepsilon_1/2}, N] \cap (2\mathbb{N})$,

$$
\begin{align*}
P_{\omega}^{\hat{b}(N)}(Z_k = \hat{b}(N)) &= Q_{\omega}(Z_k = \hat{b}(N)) \\
&\ge Q_{\omega}(Z_k = \hat{b}(N), \tau_{\hat{Z}=Z} \le N^{1-\varepsilon_1/2}, \tau_{exit} > N)
\end{align*}
$$
Collisions of several walkers in recurrent random environments

$$
\begin{align}
&= Q_{\omega}(\hat{Z}_k = \hat{b}(N), \tau_{\hat{Z}=Z} \le N^{1-\epsilon_1/2}, \tau_{exit} > N) \nonumber \\
&\ge Q_{\omega}(\hat{Z}_k = \hat{b}(N)) - Q_{\omega}(\tau_{\hat{Z}=Z} > N^{1-\epsilon_1/2}) - Q_{\omega}(\tau_{exit} \le N) \nonumber \\
&\ge \hat{\nu}(\hat{b}(N)) - 5N^{-\epsilon_1/4} - 2e^{2a_0}N^{-\epsilon_1}, \tag{5.33}
\end{align}
$$

where we used (5.26) in the first and last line, $Z_k = \hat{Z}_k$ for $k \in [\tau_{\hat{Z}=Z}, \tau_{exit})$ under $Q_\omega$ in the third line, and $Q_\omega(\hat{Z}_k = x) = P_\omega^{\hat{Z}}(\hat{Z}_k = x) = \hat{\nu}(x)$ since $k$ is even, (5.30) and (5.31) in the last line since $N \ge N_4$.

Notice that $\hat{\mu}(2\mathbb{Z}) = e^{-V(\hat{b}(N))} \sum_{i=\hat{x}_0}^{\hat{x}_2-1} e^{-[V(i)-V(\hat{b}(N))]}$, with

$$
\sum_{i=\hat{x}_0}^{-1} e^{-[V(i)-V(\hat{b}(N))]} \le |\hat{x}_0| N^{-\epsilon_5/2} \le \epsilon_3^{-1} (\log N)^2 N^{-\epsilon_5/2} \le \epsilon_6^{-1}
$$

since $N \ge N_1$, $\omega \in \Delta_N^{(3)}$ and thanks to (5.27).

Moreover, by (5.28), $\sum_{i=\theta_N^{(R)}}^{\hat{x}_2-1} e^{-[V(i)-V(\hat{b}(N))]} \le 2\epsilon_3^{-1}(\log N)^2 N^{-2\epsilon_1} \le \epsilon_6^{-1}$ because
$N \ge N_1$. Finally, $\sum_{i=0}^{\theta_N^{(R)}-1} e^{-[V(i)-V(\beta_N^{(R)})]} \le \epsilon_6^{-1}$ since $\omega \in \Delta_N^{(6,R)}$ (see (5.15)). Moreover,
$|V(\hat{b}(N)) - V(\beta_N^{(R)})| \le a_0$. Hence,

$$
\hat{\mu}(2\mathbb{Z}) \leq 3\epsilon_6^{-1}e^{a_0}e^{-V(\hat{b}(N))}.
$$

Moreover, $\hat{\mu}(\hat{b}(N)) \ge e^{-V(\hat{b}(N))}$ since $\hat{x}_0 < \hat{b}(N) < \hat{x}_2$, and $\hat{b}(N)$ is even by (5.17), so by
(5.25), $\hat{\nu}(\hat{b}(N)) = \hat{\mu}(\hat{b}(N))/\hat{\mu}(2\mathbb{Z}) \ge \epsilon_6 e^{-a_0}/3$. This, (5.32) and (5.33) give for $N \ge N_1$,

$$
\forall \omega \in \Delta_N \cap \Delta_N^{(R)}, \forall n \in [N^{1-\epsilon_1/3}, N] \cap (2N), \forall j \in \{1, \dots, r\}, P_{\omega}^{y_j}[Z_n = \hat{b}(N)] \ge \epsilon_6 e^{-a_0/8}.
$$

The proof is similar for $\omega \in \Delta_N \cap \Delta_N^{(L)}$ by symmetry. This, combined with Lemma 5.4, ends (5.2) with $c(\delta) = \epsilon_6 e^{-a_0}/8 > 0$ and $\epsilon(\delta) = \epsilon_1/3$. To prove that this remains true if $(2\mathbb{Z})^r$ and $2\mathbb{N}$ are replaced respectively by $(2\mathbb{Z} + 1)^r$ and $2\mathbb{N} + 1$, we just condition $P_{\omega}^{y_j}[Z_n = \hat{b}(N)]$ by $Z_1$, and apply the Markov property and (5.2) to $(y_1 \pm 1, \dots, y_r \pm 1)$. $\square$

References

[1] Andreoletti, P.: Alternative proof for the localization of Sinai's walk. J. Stat. Phys. **118**, (2005), 883–933. MR-2130643

[2] Andreoletti, P. and Devulder, A.: Localization and number of visited valleys for a transient diffusion in random environment. Electron. J. Probab. **20**, no 56, (2015), 1–58. MR-3354616

[3] Barlow, M., Peres, Y. and Sousi, P.: Collisions of random walks. Ann. Inst. H. Poincaré Probab. Stat. **48**, no 4, (2012), 922–946. MR-3052399

[4] Bovier, A. and Faggionato, A.: Spectral analysis of Sinai's walk for small eigenvalues. Ann. Probab. **36**, (2008), 198–254. MR-2370603

[5] Brox, Th.: A one-dimensional diffusion process in a Wiener medium. Ann. Probab. **14**, (1986), 1206–1218. MR-0866343

[6] Campari, R. and Cassi, D.: Random collisions on branched networks: How simultaneous diffusion prevents encounters in inhomogeneous structures. Physical Review E **86.2**, (2012), 021110.

[7] Cheliotis, D.: Diffusion in random environment and the renewal theorem. Ann. Probab. **33**, (2005), 1760–1781. MR-2165578

[8] Cheliotis, D.: Localization of favorite points for diffusion in a random environment. Stoch. Proc. Appl. **118**, (2008), 1159–1189. MR-2428713

[9] Chung, K. L.: A course in probability theory. Academic Press, Inc., San Diego, Third edition, 2001. xviii+419 pp. MR-1796326
[10] Deheuvels, P. and Révész, P.: Simple random walk on the line in random environment. *Probab. Theory Related Fields* **72**, (1986), 215–230. MR-0836276

[11] Dembo, A., Gantert, N., Peres, Y. and Shi, Z.: Valleys and the maximum local time for random walk in random environment. *Probab. Theory Related Fields* **137**, (2007), 443–473. MR-2278464

[12] Devulder, A.: Persistence of some additive functionals of Sinai's walk. *Ann. Inst. H. Poincaré Probab. Stat.* **52**, (2016), 1076–1105. MR-3531701

[13] Devulder, A., Gantert, N. and Pène, F.: Arbitrary many walkers meet infinitely often in a subballistic random environment. In preparation, (2018+).

[14] Doyle, P. G. and Snell, E. J.: Probability: Random walks and Electrical Networks. *Carus Math. Monographs* **22**, Math. Assoc. Amer., Washington DC, 1984. xiv+159 pp. MR-0920811

[15] Dvoretzky, A. and Erdös, P.: Some problems on random walk in space, *Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability*, 1950, University of California Press, Berkeley and Los Angeles, (1951), 353–367. MR-0047272

[16] Freire, M.V.: Application of moderate deviation techniques to prove Sinai theorem on RWRE. *J. Stat. Phys.* **160** (2), (2015), 357–370. MR-3360463

[17] Gallesco, C.: Meeting time of independent random walks in random environment. *ESAIM Probab. Stat.* **17**, (2013), 257–292. MR-3021319

[18] Gantert, N., Kochler M. and Pène, F.: On the recurrence of some random walks in random environment. *ALEA Lat. Am. J. Probab. Math. Stat.* **11**, (2014), 483–502. MR-3274642

[19] Golosov, A. O.: Localization of random walks in one-dimensional random environments. *Commun. Math. Phys.* **92**, (1984), 491–506. MR-0736407

[20] Hirsch, W. M.: A strong law for the maximum cumulative sum of independent random variables. *Comm. Pure Appl. Math.* **18**, (1965), 109–127. MR-0179828

[21] Hu, Y. and Shi, Z.: The limits of Sinai's simple random walk in random environment. *Ann. Probab.* **26**, (1998), 1477–1521. MR-1675031

[22] Hu, Y. and Shi, Z.: Moderate deviations for diffusions with Brownian potentials. *Ann. Probab.* **32**, (2004), 3191–3220. MR-2094443

[23] Kawazu, K., Tamura, Y. and Tanaka, H.: Limit theorems for one-dimensional diffusions and random walks in random environments. *Probab. Theory Related Fields* **80**, (1989), 501–541. MR-0980686

[24] Kochen, S. P. and Stone C. J.: A note on the Borel-Cantelli lemma. *Illinois J. Math.* **8**, (1964), 248–251. MR-0161355

[25] Komlós, J., Major, P. and Tusnády, G.: An approximation of partial sums of independent RV's and the sample df. I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete **32**, (1975), 111–131. MR-0375412

[26] Krishnapur, M. and Peres, Y.: Recurrent graphs where two independent random walks collide finitely often. *Electron. Comm. Probab.* **9**, (2004), 72–81. MR-2081461

[27] Lawler, G. F. and Limic, V.: Random walk: a modern introduction, *Cambridge Studies in Advanced Mathematics* **123**, Cambridge University Press, Cambridge, 2010. xii+364 pp. MR-2677157

[28] Neveu, J.: Bases mathématiques du calcul des probabilités. *Masson et Cie, Éditeurs*, Paris, 1964. xiii+203 pp. MR-0198504

[29] Neveu J. and Pitman J.: Renewal property of the extrema and tree property of the excursion of a one-dimensional Brownian motion. *Séminaire de Probabilités XXIII*, (1989) 239–247, Lecture Notes in Math., Springer, Berlin, 1372. MR-1022914

[30] Pólya, G.: Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz. *Math. Ann.* **84**, (1921), 149–160. MR-1512028

[31] Pólya, G.: Collected papers, Vol IV. Probability; combinatorics; teaching and learning in mathematics. Edited by Gian-Carlo Rota, M. C. Reynolds and R. M. Shortt. *MIT Press*, Cambridge, Massachusetts, 1984. ix+642 pp. MR-0758990

[32] Shi, Z. and Zindy, O.: A weakness in strong localization for Sinai's walk. *Ann. Probab.* **35**, (2007), 1118–1140. MR-2319717
Collisions of several walkers in recurrent random environments

[33] Sinai, Ya. G.: The limit behavior of a one-dimensional random walk in a random environment. *Teor. Veroyatnost. i Primenen* **27**, (1982), 247–258. MR-0657919

[34] Solomon, F.: Random walks in a random environment. *Ann. Probab.* **3**, (1975), 1–31. MR-0362503

[35] Spitzer, F.: Principles of random walk, Graduate Texts in Mathematics, Vol. 34, Second edition. Springer-Verlag, New York-Heidelberg, 1976. xiii+408 pp. MR-0388547

[36] Zeitouni, O.: Random walks in random environment. École d'été de probabilités de Saint-Flour 2001. Lecture Notes in Math. **1837** 189–312. Springer, Berlin, 2004. MR-2071631

**Acknowledgments.** A part of this work was done while AD and NG were visiting Brest. We thank ANR MEMEMO 2 (ANR-10-BLAN-0125) and the LMBA, University of Brest for its hospitality. We are grateful to an anonymous referee for comments which helped improve the presentation of the paper.