# Mixing time of random walk on dynamical random cluster

Andrea Lelli111Most of this work was done while the author was affiliated with
the University of Bath, Department of Mathematical Sciences, supported by a
scholarship from the EPSRC Centre for Doctoral Training in Statistical Applied
Mathematics at Bath (SAMBa), under the project EP/L015684/1. Alexandre
<EMAIL_ADDRESS>University of Bath, Department of
Mathematical Sciences, supported by EPSRC Fellowship EP/N004566/1.

###### Abstract

We study the mixing time of a random walker who moves inside a dynamical
random cluster model on the $d$-dimensional torus of side-length $n$. In this
model, edges switch at rate $\mu$ between _open_ and _closed_ , following a
Glauber dynamics for the random cluster model with parameters $p,q$. At the
same time, the walker jumps at rate $1$ as a simple random walk on the torus,
but is only allowed to traverse open edges. We show that for small enough $p$
the mixing time of the random walker is of order $n^{2}/\mu$. In our proof we
construct of a non-Markovian coupling through a multi-scale analysis of the
environment, which we believe could be more widely applicable.

##  1 Introduction

We study the mixing time of a random walk on a dynamical random cluster model
in $\mathbb{T}_{n}^{d}$, the $d$-dimensional torus of side-length $n$. In this
model, each edge of $\mathbb{T}_{n}^{d}$ can be in either of two states:
_open_ or _closed_. At time $0$, we take the state of the edges to be
distributed according to the random cluster measure with parameters
$p\in(0,1)$ and $q>0$. That is, for any subset of edges $\omega\subset
E(\mathbb{T}_{n}^{d})$, with $E(\mathbb{T}_{n}^{d})$ denoting the set of edges
of the torus, the probability that the set of open edges at time $0$ is equal
to $\omega$ is

$\upsilon(\omega)=\frac{1}{Z}p^{|\omega|}(1-p)^{|E(\mathbb{T}_{n}^{d})\setminus\omega|}q^{\kappa(\omega)},$
(1.1)

where $\kappa(\omega)$ is the number of connected components obtained in the
graph with vertex set $\mathbb{T}_{n}^{d}$ and edge set $\omega$, and
$Z=Z(d,p,q)>0$ is just a normalizing constant so that the above is a
probability measure. Instead of representing the state of the edges by the set
$\omega$ of open edges, we will often represent it by an element
$\eta\in\left\\{0,1\right\\}^{E(\mathbb{T}_{n}^{d})}$, with $\eta(e)=0$
meaning that the edge $e\in E(\mathbb{T}_{n}^{d})$ is closed and $\eta(e)=1$
meaning that $e$ is open. Thus, given $\eta$, we have $\omega=\left\\{e\in
E(\mathbb{T}_{n}^{d})\colon\eta(e)=1\right\\}$.

From time $0$, edges change their state following a continuous-time Glauber
dynamics. Thus, given a parameter $\mu>0$, each edge $e\in
E(\mathbb{T}_{n}^{d})$ has a Poisson clock of rate $\mu$, and when the clock
of $e$ rings, the state of $e$ is resampled (open or closed) according to the
conditional probability obtained from $\upsilon$ in (1.1) conditioned on the
states of all the other edges. This resampling can be easily described: if the
clock of $e$ rings at time $t$, then the probability that $e$ becomes open at
time $t$ is equal to

$\begin{array}[]{rl}p,&\text{ if $e$ is not a \emph{cut-edge} at time
$t-$},\\\ \frac{p}{p+(1-p)q},&\text{ if $e$ is a \emph{cut-edge} at time
$t-$},\end{array}$ (1.2)

where an edge $e$ is called a _cut-edge_ if modifying the state of $e$ (while
keeping the state of the other edges unaltered) causes a change in the number
of connected components in the configuration. Note that whether an edge $e$ is
a cut-edge for a configuration $\eta$ is, in fact, independent of $\eta(e)$.
We let $\eta_{t}\in\left\\{0,1\right\\}^{E(\mathbb{T}_{n}^{d})}$ denote the
configuration that gives the state of the edges at time $t$.

On top of this dynamic environment we place a random walker which starts from
the origin of $\mathbb{T}_{n}^{d}$ and has a Poisson clock of rate $1$. When
the clock of the walker rings, the walker chooses an edge uniformly at random
from the set of edges that are adjacent to its current location, regardless of
their states. If the chosen edge is open at that time, then the walker
traverses the edge, otherwise the walker stays put. We denote by
$X_{t}\in\mathbb{T}_{n}^{d}$ the position of the walker at time $t$, and let

$\\{M_{t}\\}_{t\geq 0}=\\{X_{t},\eta_{t}\\}_{t\geq 0},$

denote the _full system_ composed of the walker $\left\\{X_{t}\right\\}_{t\geq
0}$ and the environment $\left\\{\eta_{t}\right\\}_{t\geq 0}$. We note that
$\left\\{M_{t}\right\\}_{t\geq 0}$ and $\left\\{\eta_{t}\right\\}_{t\geq 0}$
are Markov chains, while $\left\\{X_{t}\right\\}_{t\geq 0}$ is not.

One can check (for example, by reversibility) that if $\pi$ denotes the
uniform probability measure on $\mathbb{T}_{n}^{d}$ then $\pi\times\upsilon$
is the unique stationary distribution of $\left\\{M_{t}\right\\}_{t}$.

Let $T_{\mathrm{mix}}$ denote the mixing time of the full system, starting
from the worst-case initial state. In other words, given
$x\in\mathbb{T}_{n}^{d}$ and
$\xi\in\left\\{0,1\right\\}^{E(\mathbb{T}_{n}^{d})}$, let
$T_{\mathrm{mix}}^{x,\xi}$ be the smallest $t$ such that, starting from
$M_{0}=(x,\xi)$, the total variation distance between the distribution of
$M_{t}$ and $\pi\times\upsilon$ is smaller than a given constant, which for
concreteness we take to be $1/4$. Then
$T_{\mathrm{mix}}=\min_{x,\xi}T_{\mathrm{mix}}^{x,\xi}$.

Our main result establishes that the mixing time is of order $n^{2}/\mu$ for
all small enough $p$. We remark that $p$ and $q$ are considered to be
constants independent of $n$, while $\mu$ may depend on $n$; in particular, a
natural case in the context of dynamic networks is that $\mu\to 0$ as
$n\to\infty$.

######  Theorem 1.1.

Given any $q>0$ and any dimension $d\geq 1$, there exists a positive $p_{0}>0$
so that for all $p\in(0,p_{0})$ there exists
$C_{1}=C_{\ref*{cte:thmmain}}(d,p,q)>0$ for which

$T_{\mathrm{mix}}\leq C_{\ref*{cte:thmmain}}\frac{n^{2}}{\mu},\quad\text{for
all $\mu=\mu(n)>0$ and all $n\geq 1$}.$

The proof of Theorem 1.1 goes via the construction of a _non-Markovian_
coupling using a multi-scale analysis of the environment. We believe this idea
can be more widely applicable to analyze the mixing time of random walks on
particle systems, and we regard it as one of our main contributions. Another
main contribution of our work is to initiate the analysis of the mixing time
of a random walk in a dynamic environment where edge updates are not
independent of one another; see the related works in Section 1.2. We will
employ a multi-scale analysis exactly to control the evolution of the
environment. We will give a thorough description of the main ideas of the
proof in Section 1.4, since first, in Section 1.3, we will need to introduce
an auxiliary process.

###  1.1 Lower bounds on the mixing time

We also derive matching lower bounds on the mixing time. We start by stating a
straightforward generalization of the lower bound from [11].

We consider a larger class of models, which we refer to as _continuous-time
random walks on general dynamical percolation_ , where the word general is to
mean that the percolation process may not be independent. Let
$\left\\{X_{t},\eta_{t}\right\\}_{t\geq 0}$ be a continuous-time Markov chain
where the walker $X_{t}$ jumps at rate $1$ and can only traverse open edges of
$\mathbb{T}_{n}^{d}$, and the environment $\left\\{\eta_{t}\right\\}_{t}$ is a
Markov chain on $\left\\{0,1\right\\}^{E(\mathbb{T}_{n}^{d})}$ where edges
refresh their state at rate $\mu$ independently of the walker. As usual $\mu$
may depend on $n$. Let $\pi$ be the uniform distribution on
$\mathbb{T}_{n}^{d}$ and let $\nu$ be the stationary distribution of the
Markov chain $\left\\{\eta_{t}\right\\}_{t}$.

We recall some fundamental definitions. The _spectral gap_ $\gamma$ of a
reversible Markov chain is defined as

$\gamma=\inf_{f}\frac{\mathcal{E}(f,f)}{\mathrm{Var}(f)},$

where the infimum is over all functions $f$ from the state space to
$\mathbb{R}$ with $\mathrm{Var}(f)\neq 0$, the variance $\mathrm{Var}(f)$
being with respect to the stationary distribution of the chain, and
$\mathcal{E}(f,f)$ is the so-called Dirichlet form. The _relaxation time_ of
the said Markov chain is defined as

$T_{\mathrm{rel}}=\gamma^{-1}.$

Given a time interval $I\subset\mathbb{R}_{+}$, we say that an edge is
$I$-open, if it is open at some time during $I$. Then, for any vertex
$x\in\mathbb{T}_{n}^{d}$ and any time interval $I\subset\mathbb{R}_{+}$, we
let $\mathcal{C}_{x}(I)$ denote the connected component of $I$-open edges from
$x$. Finally, given a subset $S\subset\mathbb{T}_{n}^{d}$, let
$\mathrm{diam}(S)=\max_{x,y\in S}\|x-y\|_{1}$ be the diameter of $S$, where
$\|x-y\|_{1}$ is the $L_{1}$ distance (or, equivalently, the length of the
shortest path) between $x$ and $y$ in $\mathbb{T}_{n}^{d}$. We require the
following two assumptions from the process
$\left\\{X_{t},\eta_{t}\right\\}_{t\geq 0}$:

$\pi\times\nu\text{ is the stationary distribution of
$\left\\{X_{t},\eta_{t}\right\\}_{t\geq 0}$},$ (1.3)

and

$\text{$\exists\delta>0$ and $C_{\ref*{cte:assump2}}>0$ such that for any
$x\in\mathbb{T}_{n}^{d}$ we have
$\mathbb{E}_{\nu}\left(D_{x,\delta}^{2}\right)\leq C_{\ref*{cte:assump2}}$},$
(1.4)

where
$D_{x,\delta}=\mathrm{diam}\left(\mathcal{C}_{x}\left([0,\delta]\right)\right)$
and $\mathbb{E}_{\nu}$ denotes the expectation with respect to the stationary
measure of the environment. The assumption in (1.3) just says that the
stationary measure of the walker is uniform, while (1.4) gives that the
environment is strictly subcritical.

######  Theorem 1.2.

Let $\left\\{X_{t},\eta_{t}\right\\}_{t\geq 0}$ be a random walk in a general
dynamical percolation satisfying (1.3) and (1.4) above. Then, there exist a
constant $C_{3}>0$ depending only on $d$ such that

$T_{\mathrm{rel}}\geq\frac{C_{\ref*{cte:lb}}\delta
n^{2}}{C_{\ref*{cte:assump2}}}.$

A natural setting is when the environment starts from its stationary
distribution. For this, let $\upsilon_{t}$ stand for the distribution of
$(X_{t},\eta_{t})$ where the walker starts from the origin and the environment
starts from stationarity (that is, $\eta_{0}$ is distributed as $\nu$). Then,
$\|\upsilon_{t}-\pi\times\nu\|_{\mathrm{TV}}$ is the total variation distance
between $\upsilon_{t}$ and the stationary measure of
$\left\\{X_{t},\eta_{t}\right\\}_{t}$.

######  Theorem 1.3.

Let $\left\\{X_{t},\eta_{t}\right\\}_{t\geq 0}$ be a random walk in a general
dynamical percolation satisfying (1.3) and (1.4) above. Then, there exists a
constant $C_{4}>0$ depending only on $d$ such that, for any $\epsilon>0$,

if
$t\leq\tfrac{C_{\ref*{cte:lb2}}}{C_{\ref*{cte:assump2}}}\epsilon^{\frac{d+2}{d}}\delta
n^{2}$ then $\|\upsilon_{t}-\pi\times\nu\|_{\mathrm{TV}}\geq 1-\epsilon$.

Moreover, there exists a constant $C_{5}>0$ depending only on $d$ such that,
for any $t\geq\delta$,

$\mathbb{E}_{\upsilon_{t}}\left(\|X_{t}-X_{0}\|_{1}^{2}\right)\leq
C_{\ref*{cte:sqd}}C_{\ref*{cte:assump2}}\frac{t}{\delta},$

where $\mathbb{E}_{\upsilon_{t}}$ stands for the expectation with respect to
$\upsilon_{t}$.

The proofs of Theorems 1.2 and 1.3 are identical to the ones for random walk
on dynamical percolation from [11]. For the sake of completeness, we add the
proofs in Section 8.

We want to apply the above theorems to derive lower bounds on the mixing time
of a random walk in dynamical random cluster. It is clear that (1.3) holds in
this case. We will show in Section 9 that (1.4) also holds, obtaining the
corollary below. For any $q$, let $p_{\mathrm{c}}^{q}$ be the critical
probability for the appearance of an infinite cluster in the random cluster
model on $\mathbb{Z}^{d}$.

######  Corollary 1.4.

If $\left\\{X_{t},\eta_{t}\right\\}_{t\geq 0}$ is a random walker in the
dynamic random cluster model, then for any $q\geq 1$ and any
$p<p_{\mathrm{c}}^{q}$, there exists a constant $c=c(d,q,p)>0$ such that the
relaxation time of the full system and the mixing time starting from a
stationary environment is at least $cn^{2}/\mu$. If $q<1$, then for all small
enough $p$ the same conclusion holds.

The proof of the lower bound is much simpler than that of the upper bound,
allowing us to derive it in the whole subcritical regime when $q\geq 1$. In
fact, when $q\geq 1$, the proof follows by using a sprinkling lemma to compare
two random clusters configurations with densities $p<p^{\prime}$ (Lemma 9.1),
and the exponential decay of cluster sizes in the subcritical regime. When
$q<1$, exponential decay of cluster sizes is only known for small enough $p$,
preventing us to establish (1.4) in the whole subcritical regime.

We expect the upper bound of order $n^{2}/\mu$ to hold in the whole
subcritical regime as well, however our proof technique requires the
percolation process to be a small perturbation of subcritical independent
percolation, in a sense that we better explain in Remark 1.5, after
introducing the $\star$-process.

###  1.2 Related works

We will restrict our discussion to works dealing with the mixing time of
random walks on _dynamic_ environments, as otherwise there is simply a
plethora of works. We also remark that, if the environment is allowed to
evolve in an arbitrary fashion (for example, by taking any sequence of graphs
on a fixed vertex set), then several problems may arise. For example, there
may not be a stationary distribution for the walker. Moreover, even if there
is a stationary distribution, the distribution of the walker may not converge
to stationarity, or the total variation distance to stationarity may not be
monotone in time.

_Random walk on dynamical percolation on $\mathbb{T}_{n}^{d}$._ This model is
equivalent to the model we described restricted to $q=1$. This special case is
already quite challenging but some results have been obtained recently. First
note that, when $q=1$, the two probabilities in (1.2) become equal, and when
an edge updates, it does so _independently_ of the other edges, becoming open
with probability $p$ or closed with probability $1-p$. Though in this case
edges evolve independently of one another, there are strong dependences
between the location of the walker and the state of the edges (especially if
$\mu\to 0$ as $n\to\infty$, since edges update very slowly in comparison to
the rate of jump of the walker).

The random walk on dynamical percolation model was introduced by Peres,
Stauffer and Steif [11], where it is shown that, in the whole subcritical
regime333That is, for any $p<p_{\mathrm{c}}$ with
$p_{\mathrm{c}}=p_{\mathrm{c}}(d)$ being the critical probability for the
existence of an infinite cluster in percolation in $\mathbb{Z}^{d}$, the
mixing time is of order $n^{2}/\mu$. We remark that in [11] both upper and
lower bounds of order $n^{2}/\mu$ were derived for $T_{\mathrm{mix}}$. Recall
that $n^{2}$ is the order of the mixing time of a simple random walk on the
_static_ torus (that is, where all edges are open at all times). So, in a
subcritical dynamical percolation, the walker is delayed by a factor of
$1/\mu$, which is the expected time that a single edge takes to refresh.

Later, Peres, Sousi and Steif [10] analyzed the supercritical regime and
showed that, for $p$ large enough, the mixing time is at most $(\log
n)^{a}\left(n^{2}+\frac{1}{\mu}\right)$ for some constant $a>0$. Their upper
bound is not believed to be tight: one expects that, in the whole
supercritical regime, the mixing time is of order $n^{2}+\frac{1}{\mu}$. This
remains an interesting open problem. Their proof makes strong use of
isoperimetric properties of the infinite cluster of supercritical percolation,
which are only known for $q=1$. With regard to the _critical_ regime, the only
known result is that the mixing time is of order at most $\frac{n^{2}}{\mu}$,
which is the mixing time in the subcritical regime [7]. It is not
inconceivable that the mixing time in the critical case is in fact of smaller
order than $\frac{n^{2}}{\mu}$.

_Random walk on dynamical percolation on other graphs._ Sousi and Thomas [14]
studied the case where the torus is replaced by the _complete graph_. This is
a simpler case due to the lack of an underlying geometry, but for which a more
detailed analysis can be carried out. They established the order of the mixing
time in that case, and also the occurrence of a cut-off phenomenon. We remark
that if the walker is at some vertex $v$ and we know that an edge incident to
$v$ is updating to open, but we refrain from observing which of the edges
incident to $v$ is updating, then the other endpoint of this edge is uniformly
at random among all vertices (but $v$). So, by traversing this edge (call it
$e$), after one additional step, the walker can find itself in a location that
is essentially uniformly at random, so very close to stationarity. Though
suggestive, this is not enough to establish the mixing time, as one still
needs to control that the walker “forgets” that $e$ is now open (that is, the
walker may be close to stationarity, but the full system is not). Still, this
illustrates the kind of simplification that the lack of an underlying geometry
brings.

The last work we mention for the random walk on dynamical percolation model is
a recent result by Hermon and Sousi [7]. They developed a comparison principle
and showed that, for _any_ graph $G$, the so-called _spectral profile mixing
time_ for the random walk on dynamical percolation on $G$ is at most
$\frac{1}{\mu}$ times the spectral profile mixing time of simple random walk
on (the static graph) $G$.

In all the above results, it was crucial that when $q=1$ edges update
independently of one another. The main objective of our work is to develop a
technique that can go beyond the dynamical percolation case and which can deal
with environments whose edge updates may depend on one another, including the
case of unbounded dependences such as in the dynamical random cluster.

_Other models._ We end this section by mentioning two lines of work. In the
first one, Avena et al. [1, 2] studied a different dynamic on the environment,
where instead of dynamical percolation one has a _dynamic configuration
model_. This model has some intuitive similarities with the dynamical
percolation on the _complete graph_ , in the sense that it also lacks an
underlying geometry. They studied the mixing time and the occurrence of a cut-
off phenomenon in this setting, but restricted to a random walker that is non-
backtracking. This helps the walker to move away from its current location,
strongly reducing dependences between the walker and the environment.

Finally, the second line of work we mention is that of [12, 13]. They
considered the case of a discrete-time random walk on a graph with a fixed set
of vertices, but which evolves over time by means of an arbitrary sequence of
graphs on that vertex set. The goal of their work is much different than ours;
for example, they want to understand which conditions on the sequence of
graphs one can impose to guarantee that the mixing time is polynomial. They
also derive results for the hitting time and cover time. We refer to [12, 13]
and references therein for a list of known results on dynamic graphs that go
beyond the mixing time. We also refer the reader to [4] for results on a model
similar to random walks on dynamical percolation on the complete graph.

###  1.3 The $\star$-process: retaining some randomness

Before giving the ideas of our proof, we need to describe a different
representation of the full system, which is inspired by [11]. Recall that each
edge has a Poisson clock of rate $\mu$ associated to it, which gives the times
at which the edge is updated. To each update of an edge, we can decide whether
the edge becomes open or closed by sampling an independent random variable $U$
with a uniform distribution in $(0,1)$, and then making the edge open if and
only if the edge is not a cut-edge and $U<p$ or the edge is a cut-edge and
$U<\frac{p}{p+(1-p)q}$. Now, let

$p_{\mathrm{min}}=\min\left\\{p,\frac{p}{p+(1-p)q}\right\\}\quad\text{and}\quad
p_{\mathrm{max}}=\max\left\\{p,\frac{p}{p+(1-p)q}\right\\};$

thus, $p_{\mathrm{min}}=\frac{p}{p+(1-p)q}$ if $q>1$ and $p_{\mathrm{min}}=p$
if $q<1$. Note that if $U$ turns out to be in the interval
$(0,p_{\mathrm{min}})\cup(p_{\mathrm{max}},1)$ the outcome of the update
(i.e., whether the edge becomes open or closed) is determined regardless of
whether or not the edge is a cut-edge. In other words, the update is
_oblivious_ to the current configuration, and we will refer to those updates
as _$\star$ -updates_. We then let

$p_{\star}=p_{\mathrm{min}}+1-p_{\mathrm{max}}\in(0,1)$

be the probability that a given update is a $\star$-update.

We now define the update of an edge $e$ in two stages. First, we sample an
independent random variable $U_{\star}$, which is uniformly at random in
$(0,1)$, so that if $U_{\star}<p_{\star}$, then the update is a
$\star$-update, otherwise it is not a $\star$-update. Next, we use the random
variable $U$ to determine whether $e$ updates to open or closed. More
precisely, in the case of a $\star$-update, we make $e$ open if
$U<\frac{p_{\min}}{p_{\star}}$, otherwise $e$ becomes closed. In the case of a
non-$\star$-update, we need to inspect the current configuration to see
whether $e$ is a cut-edge or not. In particular, we need to perform what we
call an _exploration of $e$_, which means that we perform a local search from
the endpoints of $e$ that traverses only open edges in order to determine what
are the open clusters of the endpoints of $e$. Hence, each update of $e$ will
be represented by a tuple $(s,U_{\star},U)$, where $s>0$ is the time at which
the update occurs, $U_{\star}\in(0,1)$ is the variable used to decide whether
the update is a $\star$-update, and $U\in(0,1)$ is the random variable
governing whether the edge is to be updated open or closed.

We use this to introduce another Markov process which we denote by
$\\{{M}^{\star}_{t}\\}_{t\geq
0}=\left\\{X_{t},{\eta}_{t}^{\star}\right\\}_{t\geq 0}$, and which we refer to
as the _$\star$ -process_. This process will retain more randomness than
$\\{M_{t}\\}_{t\geq 0}$ and its state space will be

$\Omega^{\star}=\left\\{(v,{\eta^{\star}})\in\mathbb{T}_{n}^{d}\times\\{0,1,\star\\}^{E(\mathbb{T}_{n}^{d})}\colon{\eta^{\star}}(e)\in\\{0,1\\}\text{
for each edge }e\text{ adjacent to }v\right\\}.$

So an edge will be allowed to be in an additional state, called $\star$, which
means that in its last update the edge underwent a $\star$-update. However, we
do not allow that edges adjacent to the walker are in state $\star$.

The $\star$-process evolves as follows. If the Poisson clock of an edge $e$
rings, we look at the variable $U_{\star}$ associated with this update and
determine whether the update is a $\star$-update. If the update is a
$\star$-update and if $e$ is not currently adjacent to the walker, then we
make the state of $e$ equal to $\star$. If $e$ is adjacent to the walker, then
we look at the variable $U$ associated with this update and determine whether
$e$ is open or closed. Finally, if the update is not a $\star$-update, then we
perform an exploration of $e$ as mentioned above. The difference is that, in
such an exploration, we may run into edges that are in state $\star$. For each
such edge, we immediately sample whether that edge is open or closed by using
the random variable $U$ associated with its last update. We proceed in this
way until the exploration ends and we have fully determined the cluster of
each endpoint of $e$. At this moment, we know whether or not $e$ is a cut-
edge, and we can use the random variable $U$ associated to the update of $e$
to determine whether $e$ is to be made open or closed. There is still one
final case to be described: when it is the clock of the walker that rings.
Suppose this happens and the walker jumps from a vertex $v$ to a vertex $w$.
Then, if there are edges adjacent to $w$ at state $\star$ we sample the state
of such edges (using the random variables $U$ associated to their last update)
and switch them to open or closed, appropriately.

Note that, conditioned on the position of the walker and on the state $0$, $1$
or $\star$ of each edge, we gain no information concerning whether the edges
in state $\star$ are open or closed. In particular, each such edge is open
with probability $\frac{p_{\mathrm{min}}}{p_{\star}}$ (which is the
probability that the random variable $U$ associated to their last update is at
most $\frac{p_{\mathrm{min}}}{p_{\star}}$). Therefore, we do not need to keep
track of the variables $U$ related to the last $\star$-update of each edge,
since we can sample $U$ whenever needed independently of the whole trajectory
of the process. The $\star$-process is thus a Markov process.

######  Remark 1.5.

When $q=1$, we have $p_{\mathrm{min}}=p_{\mathrm{max}}$, and so $p_{\star}=1$:
all updates are $\star$-updates, as in this case the random cluster model
reduces to dynamical percolation. If $q\neq 1$, then as $p\to 0$ we have that
$p_{\mathrm{max}}-p_{\mathrm{min}}\to 0$ and so $p_{\star}\to 1$. Therefore,
for any fixed $q$ and all small enough $p$, the dynamic random cluster model
can be viewed as a small perturbation of dynamical percolation. We also obtain
that edges of state $\star$ are open with probability
$\frac{p_{\mathrm{min}}}{p_{\star}}<p_{\mathrm{c}}$, so they form a
subcritical percolation process as well. Those are the properties that play an
essential role in the constructions of the multi-scale analysis and the
coupling used to establish the upper bound on the mixing time (Theorem 1.1).

###  1.4 Proof overview

We will only give an overview of the upper bound, which is our main result and
by far the most involved proof. We start recalling the proof in [11] for the
subcritical regime when $q=1$. There they also define the $\star$-process
(which they denote by $\tilde{M}_{t}$). Recall that, when $q=1$, we have
$p_{\star}=1$, so all updates are $\star$-updates. With this, they define a
stopping time $\tau_{0}$ as the first time at which

all edges adjacent to the walker are closed, and all remaining edges are in
state $\star$. (1.5)

Then, one can define a sequence of times $\tau_{1},\tau_{2},\ldots$ so that
$\tau_{i}$ is the first time after $\tau_{i-1}+C/\mu$, for some fixed constant
$C>0$, at which the event in (1.5) happens. These are regeneration times in
the sense that the evolution of the full system from $\tau_{i}$ does not
depend on what happened before $\tau_{i}$. Once the full system is at a
regeneration time $\tau_{i}$, with positive probability the following sequence
of events happen within time $\tau_{i}+C/\mu$:

  1. (i)

an edge $e$ adjacent to the walker opens

  2. (ii)

when the walker jumps to the other endpoint of $e$, all the adjacent edges
(which are in state $\star$) are sampled closed

  3. (iii)

$e$ remains open for some time of order $1/\mu$

  4. (iv)

$e$ closes before any of the other edges adjacent to $e$ open, thereby locking
the walker in one of $e$’s endpoints, and

  5. (v)

the edges adjacent to the other endpoint of $e$ (i.e., opposite to the
location of the walker) refresh before the edges adjacent to the walker
refresh.

When these events occur, the walker does nothing more than a jump to a
uniformly random neighbor, and immediately gets back to a regeneration time
(so $\tau_{i+1}=\tau_{i}+C/\mu$); such a regeneration time is then called a
_simple random walk regeneration_ since, at the end, what the walker did was
just one step of a simple random walk in $\mathbb{T}_{n}^{d}$.

The proof in [11] then goes by showing that the $\tau_{i+1}-\tau_{i}$ are of
order $\frac{1}{\mu}$. Therefore, after time $\frac{n^{2}}{\mu}$, the walker
underwent an order of $n^{2}$ regeneration times, a positive fraction of which
being simple random walk regeneration. So it is possible to couple the full
system with another copy of the full system so that, whenever the walker does
a simple random walk regeneration, we employ one of the standard couplings of
simple random walks on the torus. On the other hand, if the regeneration time
is not a simple random walk regeneration, we couple the motion of the two
walkers from one regeneration time to the next identically, so that the
distance between the walkers does not change. Since an order of $n^{2}$ steps
is necessary to couple two simple random walks on $\mathbb{T}_{n}^{d}$, we get
that performing an order of $n^{2}$ simple random walk regenerations is enough
to couple the two processes, which translates to a mixing time of order
$n^{2}/\mu$.

If we try to mimic the steps above for the case $q\neq 1$, we immediately run
into the issue that the event (1.5) now occurs very rarely. In fact, since
non-$\star$-updates occur with positive probability, we will typically have a
positive density of non-$\star$-edges. Therefore, it will take an exponential
amount of time to reach a regeneration time as in (1.5), rendering this
strategy useless.

We will devise a different strategy. We will, as before, construct a coupling
between two copies of the full-system, where we see the edges “from the point
of view of the walker” in the sense that whenever the edge $X_{t}+e$ updates
at time $t$, where $X_{t}$ is the position of the walker in the first copy,
then in the second copy we will do the same update to the edge
$\overline{X}_{t}+e$, where $\overline{X}_{t}$ is the location of the walker
in the second copy. Note that to establish the mixing time of the full system
we need to couple the environments and the walkers. For simplicity, we
concentrate our discussion here in the coupling of the walkers (which is the
most delicate bit), and assume for now that somehow we managed to couple the
two environments: that is, the two copies are coupled modulo a translation of
the walkers. Note that, from this moment, if we were to employ the _identity
coupling_ (that is, the second copy mimics all the edge updates and jumps of
the walker from the first copy) we would get that the environments will remain
coupled (from the point of view of the walkers) but the distance between the
walkers will not change, thereby not allowing the walkers to couple.

Our idea is to observe “a bit” the environment and, whenever the environment
looks “favorable enough”, we attempt to do a coupling that could bring the
walkers closer together, which will be a standard coupling of simple random
walks. We will refer to such moments as _simple random walk moments_ , as an
allusion to the simple random walk regenerations described above, but with the
fundamental difference that they will not be regeneration times. On the other
hand, when the environment is not favorable enough, then doing a simple random
walk moment is a bit too risky, so instead we resort to the identity coupling
as a means to keeping the distance between the walkers unchanged and not
spoiling the work done during the favorable regions of the environments.

But what does it mean for the environment to look favorable enough? In short
terms, it will mean that the event (1.5) occurs _locally_. That is, at such
times, all edges adjacent to the walkers will be closed and all edges in a
small region around the walkers will be $\star$ (for example, all edges inside
a ball of radius 3 around the walkers, excluding the edges adjacent to the
walkers). At such a time, with positive probability, the sequence of events
described above for the simple random walk regeneration occurs, and therefore
we could attemp to perform one of the standard couplings of simple random
walks. However, there are two important caveats.

The first caveat is that if we succeed in doing a simple random walk moment
with a coupling of simple random walks, then the distance between the walkers
will change. This means that the translation that maps the location of one
walker to the location of the second walker will change, and this map is what
we use to match the edges of the first copy to the edges of the second copy,
when we view the edges from the point of view of the walkers. As a
consequence, the environments will immediately _decouple_. Of course, if we
only had $\star$-edges (besides the ones adjacent to the walkers, as in the
case $q=1$), then the environments would not decouple since despite the change
in the translation map, we would still match $\star$-edges in the first copy
to $\star$-edges in the second copy, so we can easily maintain the
environments coupled. But, since $q\neq 1$ implies a density of non-$\star$
edges, the environments will necessarily decouple. Moreover, if we decide to
just wait the environments to recouple completely, this would take a time of
order $\frac{\log n}{\mu}$, which is just too long: it will lead to an upper
bound on the mixing time of $\frac{n^{2}\log n}{\mu}$. So we will not recouple
the environments completely, but will work with partially coupled
environments.

The second caveat is that a simple random walk moment occurs with _positive_
probability, so it is also possible that it turns out that a simple random
walk moment does not take place. Then, what could happen in this case? If the
environments were completely coupled, then we are guaranteed that we can
perform identity coupling and keep the distance between the walkers unchanged.
But we have just seen that the environments will typically not be fully
coupled. Yet, if we knew that the environments are coupled in a neighborhood
around the walkers and that the walkers will not exit this neighborhood, then
identity coupling is still doable. That will be our strategy, but to implement
it we will require a more delicate definition of what a favorable enough
environment means.

We will use a multi-scale analysis to control the environment. This will
reveal _future information_ regarding the environment; that is, we will
observe some information about the environment from time $0$ to some time $t$,
and then decide how to couple the walkers from time $0$. Therefore, this
construction will lead to a non-Markovian coupling.

A good picture to have in mind is that the environment is a process in space-
time, where some regions are classified as favorable and others as
unfavorable. We observe these regions from time $0$ to time $t$, and then
start observing the walkers which are paths in space-time that start growing
from time $0$. Whenever we see that the walkers are passing through a
favorable part of the environment, where favorable will also imply that the
walkers will not move outside some neighborhood around their current
locations, we will try to do a simple random walk moment. If successful, the
distance between the walkers may change and the environments may decouple, but
still using (the yet-to-be-defined properties of) favorability we will be able
to recouple the environments within a neighborhood around the walkers. If,
instead, the simple random walk moment is not successful, then the walkers may
move more than just one step of a simple random walk, but favorability will
also imply that the walkers will not move too far away, in particular they
will remain within a region where we know the environments were coupled. This
will translate to a successful application of the identity coupling.

On the other hand, if we see that the walkers are approaching an unfavorable
region of the environment, then we will want to do identity coupling but we
will need to start preparing ourselves beforehand. The problem is that such an
unfavorable region could be of an arbitrarily large scale, and the larger its
size is, the earlier we need to start preparing for it. So when we see that in
space-time the path of the walker is getting dangerously near an unfavorable
region, we stop doing simple random walk moments even if in a smaller scale
around the walkers the environment looks favorable. By switching off the
simple random walk moments, we only apply identity coupling until the walkers
reach the unfavorable region or are again far enough from any unfavourable
region. We can show that such identity couplings will succeed and, since the
translation map from one walker to the next will not change during this
period, it will give enough time for the environments to couple in a region
around the walkers that is as large as needed to contain the scale of the
unfavorable region that the walkers are approaching. Then, with the
environments properly coupled, if the walkers do enter the unfavorable region,
they can move as wildly as the environment there allows because we can perform
identity coupling throughout the unfavorable region. So the walkers survive
the traversal of the unfavorable region without changing their distance.

Then one can imagine that the proof ends by showing that $n^{2}$ instances of
a simple random walk moment are enough to guarantee that we can couple the
walkers. This is partially true. The fact is that, as mentioned above, we need
to observe future information to carry out this coupling strategy. But in
order to establish that the mixing time is at most $t$, we need to show that
with a large enough probability the two copies of the full system are coupled
at time $t$ without revealing any information that goes beyond time $t$. So
our strategy to finalize the proof is to choose an appropriate time
$t^{\prime}\in(0,t)$, reveal the information up to time $t$ and do the
coupling described above up to time $t^{\prime}$, showing that within
$t^{\prime}$ we have carried out an order of $n^{2}$ simple random walk
moments, and that we coupled the walkers at time $t^{\prime}$ (the
environments may, and typically will, be uncoupled except for a small region
around the walkers). The whole analysis will be split into three phases, and
the above will be carried out in the first two phases. We will be able to show
that these first two phase succeed with positive probability.

Next, the goal is to try to do identity coupling from time $t^{\prime}$ to $t$
in a similar manner as we were doing when approaching an unfavorable region.
In this second phase, identity coupling can only fail due to information that
we have not observed because we are limited to observe the environment up to
time $t$. We will show that, with positive probability, identity coupling will
indeed succeed from $t^{\prime}$ to $t$, leading to a coupling of the full
system at time $t$. This is the content of the third phase. If any of the
three phases fail, then we just restart from scratch. We only need to repeat
the phases a constant number of times to guarantee that the whole coupling
succeeds with probability at least $3/4$.

###  1.5 Organization of the paper

In Section 2.1 we will introduce the multi-scale analysis that will allow to
control the favorable regions of the environment. Then in Section 3 we will
give an more thorough overview of the three phases of the proof of the upper
bound, which will better explain the constructions from the tessellation of
Section 2.1. Then in Sections 4, 5 and 6 we will give the three phases of the
coupling, with the second phase in Section 5 being the most delicate part
where the non-Markovian coupling is developed. Then in Section 7 we put all
phases together to complete the proof of the upper bound (Theorem 1.1). In
Section 8 we establish the general lower bounds from Theorems 1.2 and 1.3, but
which are essentially the same proofs as in [11]; this section is added for
the sake of completeness. Finally, in Section 9 we apply these theorems to
derive the lower bounds on the mixing time and relaxation time of random walks
on the dynamical random cluster model (Corollary 1.4).

##  2 Multi-scale setup

We start defining a multi-scale tessellation of $\mathbb{T}_{n}^{d}$, which
will consist of partitioning $\mathbb{T}_{n}^{d}$ into boxes and defining the
event that boxes are _good_ or _bad_. Those events will be then used to define
the favorable parts of the environment.

###  2.1 Tessellation

Let

$\ell=p^{-\frac{1}{3d}},$ (2.1)

and $m$ be a sufficiently large integer. For each $k\geq 1$ we tessellate
$\mathbb{T}_{n}^{d}$ into cubes of length $\ell_{k}$ where

$\ell_{1}=\ell\quad\text{ and }\quad\ell_{k+1}=mk^{2}\ell_{k}.$ (2.2)

The cubes will be indexed by integer vectors $i\in\mathbb{Z}^{d}$, and denoted
$S_{k}^{\mathrm{core}}(i)\subset\mathbb{T}_{n}^{d}$ with

$S_{k}^{\mathrm{core}}(i)=i\ell_{k}+[0,\ell_{k})^{d}.$

We will consider a tiling of $\mathbb{T}_{n}^{d}$ with a hierarchy as each
cube of scale $k$ is contained inside a unique cube of scale $k+1$. For
simplicity we will assume $\ell_{k}$ divides $n$ for all $k$ we will
consider444If that were not the case, one could consider for each $k$ some
cubes to have length between $\ell_{k}$ and $2\ell_{k}$ to fully tessellate
the torus.. Moreover for any subset $V$ of the vertices of
$\mathbb{T}_{n}^{d}$, we denote by

$E(V)=\\{(v_{1},v_{2})\in E(\mathbb{T}_{n}^{d}):v_{1},v_{2}\in V\\}$

the set of all edges incident only to vertices in $V$.

Now we define a multi-scale tessellation of time. At scale 1, we tessellate
$\mathbb{R}$ into intervals of length $t_{1}=\frac{\sqrt{\ell}}{\mu}$ and
then, for higher scales, we define

$t_{k+1}=mk^{2}t_{k},\quad k\geq 1.$

We index the time intervals by $\tau\in\mathbb{Z}$ and denote them by
$T_{k}^{\mathrm{core}}(\tau)$, where

$T_{k}^{\mathrm{core}}(\tau)=\left[\tau t_{k},\,(\tau+1)t_{k}\right).$

Now for any $i\in\mathbb{Z}^{d}$, $k\geq 1$, and $\tau\in\mathbb{Z}$, we
define the core of the space-time $k$-box by

$R_{k}^{\mathrm{core}}(i,\,\tau)=S_{k}^{\mathrm{core}}(i)\times
T_{k}^{\mathrm{core}}(\tau).$

For any subset of $A\subset\mathbb{Z}^{d}$, we let $\partial A$ denote its
inner boundary. Then, in space-time, we define the spatial boundary of
$R_{k}^{\mathrm{core}}(i,\tau)$ by

$\partial_{\mathrm{s}}R_{k}^{\mathrm{core}}(i,\tau)=\partial
S_{k}^{\mathrm{core}}(i)\times T_{k}^{\mathrm{core}}(\tau).$ (2.3)

For the time dimension, we define two time boundaries, the boundary
$\partial_{\mathrm{t}}^{+}$ corresponding to the largest unit of time in the
box and the boundary $\partial_{\mathrm{t}}^{-}$ corresponding to the smallest
unit of time in the box:

$\displaystyle\partial_{\mathrm{t}}^{+}R_{k}^{\mathrm{core}}(i,\tau)=S_{k}^{\mathrm{core}}(i)\times\sup\left\\{T_{k}^{\mathrm{core}}(\tau)\right\\}=S_{k}^{\mathrm{core}}(i)\times\left\\{(\tau+1)t_{k}\right\\},\text{
and}$
$\displaystyle\partial_{\mathrm{t}}^{-}R_{k}^{\mathrm{core}}(i,\tau)=S_{k}^{\mathrm{core}}(i)\times\inf\left\\{T_{k}^{\mathrm{core}}(\tau)\right\\}=S_{k}^{\mathrm{core}}(i)\times\left\\{\tau
t_{k}\right\\}.$ (2.4)

For $k\geq 2$, each box $R_{k}^{\mathrm{core}}(i,\tau)$ will be the central
part of a larger box

$R_{k}(i,\,\tau)=\bigcup_{(j,\tau^{\prime})\in\\{-1,0,+1\\}^{d+1}}R_{k}^{\mathrm{core}}(i+j,\tau+\tau^{\prime})=S_{k}(i)\times
T_{k}(\tau),$

where we let

$S_{k}(i)=\bigcup_{j\in\\{-1,0,+1\\}^{d}}S_{k}^{\mathrm{core}}(i+j),\quad\text{and}\quad
T_{k}(\tau)=\bigcup_{\tau^{\prime}\in\\{-1,0,+1\\}}T_{k}^{\mathrm{core}}(\tau+\tau^{\prime}).$
(2.5)

In words $R_{k}(i,\,\tau)$ is composed of a cube in space of side length
$3\ell_{k}$ and a time interval of length $3t_{k}$, and it has
$R_{k}^{\mathrm{core}}(i,\,\tau)$ as its central part (see Figure 1).

Figure 1: On the left a space-time box $R_{k+1}(i,\tau)$ represented by a blue
square, its core highlighted in yellow, its partition into cores of scale
$k+1$ represented by solid black lines, and its partition into cores of scale
$k$ in dashed lines. The horizontal axis represents space and the vertical
axis represents time. On the right a space-time box of scale 1 (highlighted in
blue), and space-time cores of level $1$ in dashed lines.

For scale $k=1$, we will need a small intersection between the time dimension.
For this, let

$\overline{t}_{1}=\frac{\log^{2}\ell}{\mu},$ (2.6)

and set for each $\tau\in\mathbb{Z}$

$T_{1}(\tau)=\left[\tau t_{1}-\overline{t}_{1},\,(\tau+1)t_{1}\right].$

With $S_{1}$ defined as in (2.5) we can define $R_{1}(i,\tau)=S_{1}(i)\times
T_{1}(\tau)$. We then define the space and time boundaries of $R_{k}(i,\tau)$
for each $k,i,\tau$ analogously to (2.3) and (2.4).

Finally we denote by $S_{1}^{\mathrm{inn}}(i)$ the _inner part_ of $S_{1}(i)$
which is obtained by removing all the vertices within distance
$\frac{\gamma}{6}\log^{2}\ell$ from the boundary of $S_{1}(i)$ ($\gamma$ is a
constant that will be clarified later in the definition); in symbols,

$S_{1}^{\mathrm{inn}}(i)=\left\\{v\in
S_{1}(i)\colon\|v-w\|_{1}>\frac{\gamma}{6}\log^{2}\ell\text{ for all
}w\in\partial S_{1}(i)\right\\}.$ (2.7)

###  2.2 Good boxes at scale 1

######  Definition 2.1.

We say that an event $A$ is restricted to a region $R\subset
V(\mathbb{T}_{n}^{d})$ and a time interval $[s_{0},s_{1}]$ if $A$ is
measurable with respect to the $\sigma$-algebra generated by the updates of
the edges from $E(R)$ from time $s_{0}$ to $s_{1}$, together with the random
variables $U,U^{\prime}$ associated to such updates.

Denote with $\mathcal{C}_{x}(t)$ the connected component of open edges
containing vertex $x\in V$ at time $t$. Given a time interval
$[s,s^{\prime}]$, we say that an edge is $[s,s^{\prime}]$-open if there is at
least one time during $[s,s^{\prime}]$ at which this edge is open. Then, we
denote with $\mathcal{C}_{x}(s,s^{\prime})$ the connected component of
$[s,s^{\prime}]$-open edges that contains $x$. If we denote
$I=[s,s^{\prime}]$, then we employ the shorter notation $\mathcal{C}_{x}(I)$.
Below we split the time interval of a box into two sets of sub-intervals, and
then introduce the definition of _good boxes_.

######  Definition 2.2.

Recall that $\overline{t}_{1}=\frac{\log^{2}\ell}{\mu}$. We define two other
tessellations of disjoint time intervals. The first one has length
$\frac{\log^{2}\ell}{\mu}$:

$\overline{T}_{1}(j)=[j\overline{t}_{1},(j+1)\overline{t}_{1}),\quad\text{ for
$j\in\mathbb{Z}_{+}$}.$

Moreover, we fix a constant $\gamma=\gamma(p,q,d)>0$ such that
$\frac{p_{\mathrm{min}}}{p_{\star}}+\gamma<p_{\mathrm{c}}$, where
$p_{\mathrm{c}}$ is the critical probability for independent bond percolation
on $\mathbb{Z}^{d}$, and introduce a tessellation of time of length
$\frac{\gamma}{\mu}$:

$\overline{\overline{T}}_{1}(j)=\left[j\tfrac{\gamma}{\mu},(j+1)\tfrac{\gamma}{\mu}\right),\quad\text{
for $j\in\mathbb{Z}_{+}$}.$

We assume throughout this paper that $\overline{t}_{1}$ divides $t_{1}$ and
that $\gamma/\mu$ divides $\overline{t}_{1}$, so that
$\overline{\overline{T}}_{1}$ is a finer tessellation than $\overline{T}_{1}$,
which in turn is a finer tessellation than $T_{1}^{\mathrm{core}}$.

######  Remark 2.3.

Note that the larger $p$ is (that is, the closer $p$ is to $p_{\mathrm{c}}$)
the smaller we need to take $\gamma$. However, as we will need to take $p$
small enough in several places in the proof, we will set $\gamma$ first (for
example, it is enough to take $\gamma=\frac{1}{100}$). Then we make $p$ small
enough so that the condition on $\gamma$ is satisfied.

The definition of good boxes will be done in steps. First we define some
fundamental events that we will require from good boxes.

  1. ($\mathcal{G}_{1}^{\prime}$)

Given a box $R_{1}(i,\tau)$, let $\mathcal{G}_{1}^{\prime}(i,\tau)$ be the
event that, for any $e\in E(S_{1}(i))$, there are no non-$\star$ update on $e$
during $T_{1}(\tau)\cap[0,\infty)$.

  2. ($\mathcal{G}_{2}^{\prime}$)

For each $j\in\mathbb{Z}_{+}$ and each spatial box $S_{1}(i)$, define
$\mathcal{G}_{2}^{\prime}(i,j)$ the event that, for any $e\in E(S_{1}(i))$,
during $\overline{T}_{1}(j)$ edge $e$ never gets a $\star$-update to become
open.

  3. ($\mathcal{G}_{3}^{\prime}$)

For each $j\in\mathbb{Z}_{+}$ and each spatial box $S_{1}(i)$, let
$\mathcal{G}_{3}^{\prime}(i,j)$ be the event that, for each $e\in
E(S^{\mathrm{core}}_{1}(i))$, the number of $\star$-updates on edge $e$ during
$\overline{T}_{1}(j)$ is at least $\frac{1}{2}p_{\star}\log^{2}\ell$ (for the
values of $\ell$ and $p$ we will consider this will always be at least 1).

  4. ($\mathcal{G}_{4}^{\prime}$)

For any $j\in\mathbb{Z}_{+}$ take the unique $\tau$ such that
$\overline{\overline{T}}_{1}(j)\subset T_{1}^{\mathrm{core}}(\tau)$. For any
site $x$ on the torus, if we regard all edges closed at time $\tau t_{1}$ and
we only consider $\star$-updates disregarding all non-$\star$-updates, then
let $\mathcal{G}_{4}^{\prime}(x,j)$ be the event that
$\left|\mathcal{C}_{x}\left(\overline{\overline{T}}_{1}(j)\right)\right|<\log^{2}(\ell).$

Now for a box $R_{1}(i,\tau)$, define

$j(\tau)\text{ the value $j$ such that }\min\overline{T}_{1}(j)=\tau
t_{1}-\overline{t}_{1};$ (2.8)

in other words, it is the value such that $\overline{T}_{1}(j(\tau))$ starts
at the initial time of $R_{1}(i,\tau)$. Note that both
$\overline{T}_{1}(j(\tau))$ and $\overline{T}_{1}(j(\tau+1))$ are contained in
$T_{1}(\tau)$.

The event that a box $R_{1}(i,\tau)$ is good will be composed of four events,
which we denote by $\mathcal{G}_{1}(i,\tau)$, $\mathcal{G}_{2}(i,\tau)$,
$\mathcal{G}_{3}(i,\tau)$ and $\mathcal{G}_{4}(i,\tau)$. The first event
regards only non-$\star$ updates and is simply

$\mathcal{G}_{1}(i,\tau)=\mathcal{G}_{1}^{\prime}(i,\tau).$

The second event regards the time intervals $\overline{T}_{1}(j(\tau))$ and
$\overline{T}_{1}(j(\tau+1))$, and is defined as

$\mathcal{G}_{2}(i,\tau)=\mathcal{G}_{2}^{\prime}(i,j(\tau))\cap\mathcal{G}_{2}^{\prime}(i,j(\tau+1))\bigcap_{{\begin{subarray}{c}i^{\prime}\colon
S_{1}^{\mathrm{core}}(i^{\prime})\subset
S_{1}(i)\end{subarray}}}\mathcal{G}_{3}^{\prime}(i^{\prime},j(\tau))\cap\mathcal{G}_{3}^{\prime}(i^{\prime},j(\tau+1)).$

The next two events are confined to the time interval
$\mathbb{T}_{1}^{\mathrm{core}}(\tau)\setminus T_{1}(\tau+1)$:

$\mathcal{G}_{3}(i,\tau)=\bigcap_{\begin{subarray}{c}i^{\prime}\colon
S_{1}^{\mathrm{core}}(i^{\prime})\subset S_{1}(i)\\\
j\colon\overline{T}_{1}(j)\subset\left(T_{1}^{\mathrm{core}}(\tau)\setminus
T_{1}(\tau+1)\right)\end{subarray}}\mathcal{G}_{3}^{\prime}(i^{\prime},j)$

and

$\mathcal{G}_{4}(i,\tau)=\bigcap_{\begin{subarray}{c}x\in
S_{1}^{\mathrm{inn}}(i)\\\
j\colon\overline{\overline{T}}_{1}^{j}(\tau)\subset\left(T_{1}^{\mathrm{core}}(\tau)\setminus
T_{1}(\tau+1)\right)\end{subarray}}\mathcal{G}_{4}^{\prime}(x,j).$

For convenience, we write

$\mathcal{G}_{12}(i,\tau)=\mathcal{G}_{1}(i,\tau)\cap\mathcal{G}_{2}(i,\tau)\quad\text{and}\quad\mathcal{G}_{34}(i,\tau)=\mathcal{G}_{3}(i,\tau)\cap\mathcal{G}_{4}(i,\tau)$

######  Lemma 2.4.

The family of events $\left\\{\mathcal{G}_{1}(i,\tau)\right\\}_{(i,\tau)}$,
$\left\\{\mathcal{G}_{2}(i,\tau)\right\\}_{(i,\tau)}$ and
$\left\\{\mathcal{G}_{34}(i,\tau)\right\\}_{(i,\tau)}$ are independent of one
another.

###### Proof.

The events $\mathcal{G}_{1}(\cdot,\cdot)$ depend only on non-$\star$ updates,
so it is independent of $\mathcal{G}_{2}(\cdot,\cdot)$,
$\mathcal{G}_{3}(\cdot,\cdot)$ and $\mathcal{G}_{4}(\cdot,\cdot)$, which only
regard $\star$-updates. Then, note that $\mathcal{G}_{2}(\cdot,\cdot)$ are
events about $\star$-updates during $\bigcup_{\tau}\overline{T}_{1}(j(\tau))$,
while $\mathcal{G}_{3}(\cdot,\cdot)$ and $\mathcal{G}_{4}(\cdot,\cdot)$ regard
$\star$-updates during $\bigcup_{\tau}T_{1}^{\mathrm{core}}(\tau)\setminus
T_{1}(\tau+1)$. Since these two time intervals are disjoint, independence is
obtained from standard properties of Poisson processes. ∎

######  Lemma 2.5.

Let $R_{1}(i,\tau)$ be any box of scale $1$. There exist constants
$c,c^{\prime}>0$ so that for all small enough $p$ we obtain

$\mathbb{P}\left(\mathcal{G}_{12}^{\mathrm{c}}(i,\,\tau)\right)\leq
c\ell^{d+\frac{1}{2}}p_{\mathrm{max}}.$

and

$\mathbb{P}\left(\mathcal{G}_{34}^{\mathrm{c}}(i,\tau)\right)\leq\exp\left(-c^{\prime}\log^{2}\ell\right).$

###### Proof.

We start with event $\mathcal{G}_{34}(i,\tau)$. For a given edge, an update
that is not $\star$ occurs at rate $(1-p_{\star})\mu$, a $\star$-update occurs
at rate $p_{\star}\mu$, and a $\star$-update that opens an edge occurs at rate
$p_{\star}\frac{p_{\mathrm{min}}}{p_{\star}}\mu=p_{\mathrm{min}}\mu$.
Moreover, there are at most $2d\,3^{d}\ell^{d}$ edges in $E(S_{1}(i))$.

For $\mathcal{G}_{3}$, note that for a given edge $e\in S_{1}(i)$ and a given
$j$, the number of $\star$-updates on $e$ during $\overline{T}_{1}(j)$ is a
Poisson random variable of mean $p_{\star}\log^{2}\ell$. Therefore, using a
standard Chernoff bound for Poisson random variables and the union bound over
the edges in $S_{1}(i)$ and over the values of $j$, we obtain a constant
$c_{1}>0$ such that

$\displaystyle\mathbb{P}\left(\mathcal{G}_{3}^{\mathrm{c}}(i,\tau)\right)\leq$
$\displaystyle
2d3^{d}\ell^{d}\,\frac{(t_{1}-\overline{t}_{1})\mu}{\log^{2}\ell}\exp\left(-c_{1}p_{\star}\log^{2}\ell\right).$

Note that as $p$ decreases to $0$ we have that $p_{\star}$ increases to $1$
and $\ell$ increases to $\infty$. So for all small enough $p$ we obtain

$\displaystyle\mathbb{P}(\mathcal{G}_{3}^{\mathrm{c}}(i,\tau))\leq$
$\displaystyle\exp\left(-c_{2}\log^{2}\ell\right),$

for some constant $c_{2}$. Regarding $\mathcal{G}_{4}(i,\tau)$, for any $j\geq
0$ with $\overline{\overline{T}}_{1}(j)\subset
T_{1}^{\mathrm{core}}(\tau)\setminus T_{1}(\tau+1)$ and any edge $e$, note
that the probability that $e$ is open at the beginning of the interval
$\overline{\overline{T}}_{1}(j)$, given that we only consider $\star$-updates
and consider that all edges are closed at $\tau t_{1}$, is at most
$\frac{p_{\mathrm{min}}}{p_{\star}}$, since this is the probability that the
last $\star$-update of $e$ (if there was any) made $e$ open. Thus, using that
$1-\exp\left(-p_{\star}\gamma\right)$ is the probability that $e$ has a
$\star$-update during $\overline{\overline{T}}_{1}^{j}$, we obtain that the
probability that $e$ is $\overline{\overline{T}}_{1}^{j}$-open under the above
assumptions is at most

$\frac{p_{\mathrm{min}}}{p_{\star}}+1-\exp\left(-p_{\star}\gamma\right)\leq\frac{p_{\mathrm{min}}}{p_{\star}}+p_{\star}\gamma<p_{\mathrm{c}}.$

In other words, the set of $\overline{\overline{T}}_{1}^{j}$-open edges (under
the above assumptions) forms a subcritical percolation cluster. Therefore,
using the exponential decay of cluster size for subcritical percolation,
together with the union bound over all sites and values of $j$, we obtain a
constant $c^{\prime\prime}$ such that

$\displaystyle\mathbb{P}(\mathcal{G}_{4}^{\mathrm{c}}(i,\tau))\leq\ell^{d}\frac{t_{1}\mu}{\gamma}\exp\left(-c_{3}\log^{2}\ell\right).$

We note that $c_{3}$ increases as $p$ decreases. So the bound on
$\mathbb{P}\left(\mathcal{G}_{34}^{\mathrm{c}}(i,\tau)\right)$ follows by
taking $p$ small enough.

Now we turn to $\mathcal{G}_{12}(i,\tau)$. From the above considerations we
obtain

$\displaystyle\mathbb{P}(\mathcal{G}_{12}^{\mathrm{c}}(i,\tau))$
$\displaystyle\leq
1-\exp\left(-2d3^{d}\ell^{d}\left((1-p_{\star})\mu\left(t_{1}+\overline{t}_{1}\right)+p_{\mathrm{min}}\log^{2}\ell\right)\right)+2d3^{d}\ell^{d}\,2\exp\left(-c_{1}p_{\star}\log^{2}\ell\right),$

where the term $1-\exp(\cdot)$ comes from $\mathcal{G}_{1}^{\prime}$ and
$\mathcal{G}_{2}^{\prime}$, while the last term comes from
$\mathcal{G}_{3}^{\prime}$ as in the case of $\mathcal{G}_{3}$ above. Using
that $t_{1}+\overline{t}_{1}\leq 2t_{1}$ and that $e^{-x}\geq 1-x$ for all
$x\in\mathbb{R}$, we obtain

$\displaystyle\mathbb{P}(\mathcal{G}_{12}^{\mathrm{c}}(i,\tau))$
$\displaystyle\leq
2d3^{d}\ell^{d}\left((1-p_{\star})2\sqrt{\ell}+p_{\mathrm{min}}\log^{2}\ell+2\exp\left(-c_{1}p_{\star}\log^{2}\ell\right)\right)$
$\displaystyle\leq 4d3^{d}\ell^{d+\frac{1}{2}}(1-p_{\star}+p_{\mathrm{min}})$
$\displaystyle=4d3^{d}\ell^{d+\frac{1}{2}}(1-p_{\star}+p_{\mathrm{min}})=4d3^{d}\ell^{d+\frac{1}{2}}p_{\mathrm{max}},$

where we use that $\sqrt{\ell}$ is the term that dominates inside the
parenthesis as $p$ is made small enough (hence, $\ell$ is made large enough).
So we can take $p$ small enough so that
$p_{\mathrm{min}}\log^{2}\ell+2\exp\left(-c_{1}p_{\star}\log^{2}\ell\right)\leq
2p_{\mathrm{min}}\log^{2}\ell\leq 2p_{\mathrm{min}}\sqrt{\ell}$. ∎

We need one more step to define good boxes of scale $1$. Using a standard
result for percolation with bounded dependences [8], we will replace
$\mathcal{G}_{34}(i,\tau)$ by a collection of i.i.d. Bernoulli random
variables.

######  Lemma 2.6.

There exists a constant $C_{6}=C_{\ref*{cte:bblss}}(d)>0$ such that letting
$\left\\{\widehat{\mathcal{G}}_{34}(i,\tau)\right\\}_{(i,\tau)}$ be a
collection of i.i.d. Bernoulli random variables of parameter
$1-\exp\left(-C_{\ref*{cte:bblss}}\log^{2}\ell\right)$, Then for any $p$ small
enough we obtain that $\left\\{\mathcal{G}_{34}(i,\tau)\right\\}_{(i,\tau)}$
stochastically dominates
$\left\\{\widehat{\mathcal{G}}_{34}(i,\tau)\right\\}_{(i,\tau)}$.

###### Proof.

First note that if we fix $i$, then $\mathcal{G}_{34}(i,\tau)$ forms a
collection of independent random variables as $\tau$ varies. So
$\mathcal{G}_{34}(i,\tau)$ depends only on events
$\mathcal{G}_{34}(i^{\prime},\tau)$ such that $S_{1}(i)\cap
S_{1}(i^{\prime})\neq\emptyset$. Note that this is true even for the events
$\mathcal{G}_{4}^{\prime}$ since for $x\in S_{1}^{\mathrm{inn}}(i)$, the event
that the component of $x$ is of length $\log^{2}\ell$ is measurable with
respect to the edges in $S_{1}(i)$. Given $i$, the number of $i^{\prime}$ such
that $S_{1}(i)\cap S_{1}(i^{\prime})\neq\emptyset$ is strictly smaller than
$\Delta=5^{d}$. Then, from Lemma 2.5 we obtain that by taking $p$ small enough
the marginal probability
$w=\mathbb{P}\left(\mathcal{G}_{34}^{\mathrm{c}}(i,\tau)\right)$ can be made
smaller than $\frac{(\Delta-1)^{\Delta-1}}{\Delta^{\Delta}}$, and so we can
apply [8, Theorem 1.3] to deduce that the family
$\mathcal{G}_{34}(\cdot,\cdot)$ stochastically dominates a set of i.i.d.
Bernoulli random variables with parameter

$\displaystyle\rho$
$\displaystyle=\left(1-\frac{w^{1/\Delta}}{(\Delta-1)^{1-1/\Delta}}\right)\left(1-\left(w(\Delta-1)\right)^{1/\Delta}\right)$
$\displaystyle\geq
1-\frac{w^{1/\Delta}}{(\Delta-1)^{1-1/\Delta}}-\left(w(\Delta-1)\right)^{1/\Delta}$
$\displaystyle=1-w^{1/\Delta}\left(\frac{\Delta}{(\Delta-1)^{1-1/\Delta}}\right).$

Applying Lemma 2.5 for the value of $w$ completes the proof since
$w^{1/\Delta}\left(\frac{\Delta}{(\Delta-1)^{1-1/\Delta}}\right)\leq\exp(-C_{\ref*{cte:bblss}}\log^{2}\ell)$
for some constant $C_{\ref*{cte:bblss}}>0$. ∎

Now we are ready to define good boxes at scale $1$.

######  Definition 2.7 (Good boxes of scale 1).

Let $i\in\mathbb{Z}^{d}$ and $\tau\geq 0$. A box $R_{1}(i,\,\tau)$ is said to
be _good_ if the following event happens

$\mathcal{G}(i,\tau)=\mathcal{G}_{12}(i,\tau)\cap\widehat{\mathcal{G}}_{34}(i,\tau).$

For convenience, we assume that for $\tau<0$ then $\mathcal{G}(i,\tau)$ holds
for all $i\in\mathbb{Z}^{d}$. We also couple
$\left\\{\widehat{\mathcal{G}}_{34}(i,\tau)\right\\}_{(i,\tau)}$ with
$\left\\{\mathcal{G}_{34}(i,\tau)\right\\}_{(i,\tau)}$ so that,

for each $(i,\tau)$, whenever $\widehat{\mathcal{G}}_{34}(i,\tau)$ holds, so
does $\mathcal{G}_{34}(i,\tau)$. (2.9)

The following lemma bounds the probability that a box is bad, and follows
directly from the previous lemmas.

######  Lemma 2.8.

Let $R_{1}(i,\tau)$ be any box of scale $1$. There exists a constant $C_{7}>0$
so that for all small enough $p$ we obtain

$\mathbb{P}\left(\mathcal{G}^{\mathrm{c}}(i,\,\tau)\right)\leq
C_{\ref*{cte:badbox}}\ell^{d+\frac{1}{2}}p_{\mathrm{max}}.$

###### Proof.

This follows from Lemmas 2.5 and 2.6 ∎

######  Remark 2.9.

Note that the event $\\{R_{1}(i,\tau)\text{ is good}\\}$ is restricted to the
cube $S_{1}(i)$ and the interval $T_{1}(\tau)$. In fact, that is why in
$\mathcal{G}_{4}^{\prime}$ we assume that all edges are closed at time $\tau
t_{1}$, the initial time of the core $T_{1}^{\mathrm{core}}(\tau)$; note that
the fact that all edges are closed at time $\tau t_{1}$ is implied by
$\mathcal{G}_{2}$, but by explicitly adding the assumption in
$\mathcal{G}_{4}^{\prime}$ we make $\mathcal{G}_{2}(i,\tau)$ and
$\mathcal{G}_{4}(i,\tau)$ independent of each other. Note also that the
decision of whether a box is good is completely independent of the walker, it
only depends on the updates of the dynamical random cluster process.

Recall that $X_{t}$ denotes the position of the random walker at time $t$. In
the lemma below, we will show that if the walker happens to be inside a good
box, then it cannot move very quickly. This will allow us to have a better
control on where the walker can be.

######  Lemma 2.10.

Let $t\geq 0$ be any given time and suppose $(X_{t},t)\in
R_{1}^{\mathrm{core}}(i,\tau)$, where $R_{1}(i,\tau)$ is a good box. Then,

$\sup_{\begin{subarray}{c}s\geq t\\\ s\in
T_{1}(\tau)\end{subarray}}\|X_{t}-X_{s}\|_{1}\leq|\mathcal{C}_{X_{t}}(t)|+\left\lceil\frac{(\tau+1)t_{1}-t}{\gamma/\mu}\right\rceil\log^{2}\ell,$

In particular, if $\tau>0$ then

$\sup_{\begin{subarray}{c}s\geq t\\\ s\in
T_{1}(\tau)\end{subarray}}\|X_{t}-X_{s}\|_{1}\leq\log^{2}\ell+\left\lceil\frac{(\tau+1)t_{1}-t}{\gamma/\mu}\right\rceil\log^{2}\ell\leq\log^{2}\ell+\frac{\sqrt{\ell}}{\gamma}\log^{2}\ell\leq\frac{\ell}{10},$

where the last inequality holds for all $p$ small enough (thus, $\ell$ large
enough) and where $\|x-y\|_{1}$ denotes the $L^{1}$ distance in the torus
between the positions $x,y\in\mathbb{T}_{n}^{d}$; in particular, $\|x-y\|_{1}$
does not depend on whether edges are open or closed.

###### Proof.

This is a direct consequence of the event $\mathcal{G}_{4}^{\prime}$ from the
definition of good boxes, and the fact that good boxes do not have
non-$\star$-updates. There is just one caveat. The event
$\mathcal{G}_{4}^{\prime}$ is not enforced in time intervals
$\overline{T}_{1}(j)$ where $j=j(\tau)$ for some $\tau$; recall the definition
of $j(\tau)$ from (2.8). So for example, $\mathcal{G}_{4}(i,\tau)$ does not
include the event $\mathcal{G}^{\prime}_{4}(j)$ for $j$ such that
$\overline{T}_{1}(j)=T_{1}(\tau)\cap T_{1}(\tau+1)$, which is the only time
interval of the type $\overline{T}_{1}(\cdot)$ inside $T_{1}(\tau)$. However,
for such a $j$, we know that the connected components inside
$\overline{T}_{1}(j-1)$ are of size at most $\log^{2}\ell$, and
$\mathcal{G}_{2}(i,\tau)$ implies that during $\overline{T}_{1}(j)$ no edge of
$S_{1}(i)$ gets an update to open. Therefore, the size of the connected
components can only decrease during $\overline{T}_{1}(j)$ and the result
follows. ∎

###  2.3 Good boxes at larger scales

In this section we define the concept of good and bad boxes of scale larger
than 1, but first we define a slightly relaxed version of _intersection_ of
boxes.

######  Definition 2.11.

Since boxes are defined by semi-open intervals, we will consider boxes that
are barely non-intersecting as intersecting. That is, we consider two boxes
$R_{k}(i,\tau)$ and $R_{k}(i^{\prime},\tau^{\prime})$ as _non-intersecting_ if
and only if

$\inf_{\begin{subarray}{c}(j,s)\in R_{k}(i,\tau)\\\ (j^{\prime},s^{\prime})\in
R_{k}(i^{\prime},\tau^{\prime})\end{subarray}}\|(j,s)-(j^{\prime},s^{\prime})\|_{1}\geq
2.$

######  Definition 2.12.

A $k$-box $R_{k}(i,\,\tau)$ with $k\geq 2$ is said to be _bad_ if it contains
at least two non-intersecting bad boxes of scale $k-1$. Otherwise,
$R_{k}(i,\,\tau)$ is called _good_.

######  Remark 2.13.

The event $\\{R_{k}(i,\tau)\text{ is bad}\\}$ is strictly restricted to the
cube $S_{k}(i)$ and the time interval $T_{k}(\tau)$. Moreover, by translation
invariance, for any pair $(i,\tau),\,(i^{\prime},\tau^{\prime})$ and any scale
$k$ we have $\mathbb{P}(R_{k}(i,\,\tau)\text{ is
bad})=\mathbb{P}(R_{k}(i^{\prime},\,\tau^{\prime})\text{ is bad})$. Therefore
if $R_{k}(i,\tau)$ and $R_{k}(i^{\prime},\tau^{\prime})$ are two non-
intersecting boxes then

$\mathbb{P}(R_{k}(i,\,\tau)\text{ and }R_{k}(i^{\prime},\,\tau^{\prime})\text{
are bad})=\mathbb{P}(R_{k}(i,\,\tau)\text{ is bad})^{2}.$

######  Definition 2.14.

Define $\rho_{k}$ as the probability that a $k$-box $R_{k}(i,\,\tau)$ is bad,
that is,

$\rho_{k}=\mathbb{P}\left(R_{k}(i,\,\tau)\text{ is bad}\right).$

As noted in Remark 2.13, this probability does not depend on $(i,\tau)$.

Recall that $m$ is the variable that appears in the definition of $\ell_{k}$
from (2.2).

######  Lemma 2.15.

For any $m>0$, by setting $p$ small enough we obtain

$\rho_{k}\leq\rho_{1}^{2^{k-2}}$

###### Proof.

We prove the lemma in a slightly stronger version: we prove that we can set
values $c_{k}$, satisfying $c_{k}\geq\frac{1}{2}$ for all $k$, so that

$\rho_{k}\leq\rho_{1}^{c_{k}2^{k-1}}.$

We prove this by induction. For $k=1$ the statement is trivially satisfied by
setting $c_{1}=1$. Assume the statement is true up to $k$. Now, by the
definition of bad box we have

$\displaystyle\rho_{k+1}$
$\displaystyle\leq\left(\left(\frac{3\ell_{k+1}}{\ell_{k}}\right)^{d}\frac{3t_{k+1}}{t_{k}}\right)^{2}\rho_{k}^{2}$
$\displaystyle=3^{2d+2}(mk^{2})^{2d+2}\rho_{k}^{2}$ $\displaystyle\leq
3^{2d+2}(mk^{2})^{2d+2}\left(\rho_{1}^{c_{k}2^{k-1}}\right)^{2}$
$\displaystyle=3^{2d+2}(mk^{2})^{2d+2}\rho_{1}^{(c_{k}-c_{k+1})2^{k}}\rho_{1}^{c_{k+1}2^{k}}.$

Setting $c_{k+1}=c_{k}-\frac{1}{10k^{2}}$ gives that

$3^{2d+2}(mk^{2})^{2d+2}\rho_{1}^{(c_{k}-c_{k+1})2^{k}}=3^{2d+2}(mk^{2})^{2d+2}\rho_{1}^{\frac{2^{k}}{10k^{2}}}\leq
1,$

for all $k\geq 1$, provided $\rho_{1}$ is small enough with respect to $m$.
Given $m$, $\rho_{1}$ can be made small enough by setting $p$ small enough, as
in Lemma 2.8. Notice that
$c_{k}>c_{1}-\sum_{i=1}^{\infty}\frac{1}{10i^{2}}\geq\frac{1}{2}$, which
proves the lemma. ∎

###  2.4 Enlargement of boxes

As we discussed in the proof overview, whenever the walkers are in a favorable
region of the environment, we will try to use a simple random walk coupling to
bring the walkers together. However, when the walkers are in an unfavorable
region of the environment, which essentially means that the walkers are
approaching a bad box (at some scale), then we will have to refrain from doing
this simple random walk coupling, and will just do a naïve identity coupling
in order to let the environments couple around the walkers before they can
reach the bad box. Here we will define two types of enlargements of boxes so
that it is when the walker enters the enlargement of a bad box that we will
need to stop doing the simple random walk coupling.

######  Definition 2.16 (1-enlargement).

The _1-enlargement_ of a box $R_{k}(i,\,\tau)$ of scale $k$, is the set of
boxes

$R_{k}^{\mathrm{enl1}}(i,\,\tau)=\bigcup_{(j,\beta)\in\\{-3,-2,\dots,3\\}^{d+1}}R_{k}(i+j,\tau+\beta).$

We also denote

$S_{k}^{\mathrm{enl1}}(i)=\bigcup_{j\in\\{-3,-2,\dots,3\\}^{d}}S_{k}(i+j),\quad\text{and}\quad
T_{k}^{\mathrm{enl1}}(\tau)=\bigcup_{\beta\in\\{-3,-2,\dots,3\\}}T_{k}(\tau+\beta).$

Note that $R_{k}^{\mathrm{enl1}}(i,\tau)$ is a parallelogram of spatial length
$9\ell_{k}$ and time length $9t_{k}$ for $d\geq 2$ and
$7t_{1}+\overline{t}_{1}$ for $d=1$.

######  Remark 2.17.

The 1-enlargement is a $(d+1)$-dimensional parallelogram centered in
$R_{k}(i,\tau)$ defined to obtain the following property. Let $R_{k}(i,\tau)$
be a bad box, whose whole 1-enlargement $R_{k}^{\mathrm{enl1}}(i,\tau)$ is
contained inside a good box of scale $k+1$. Then, we know that the only boxes
of scale $k$ inside the $(k+1)$-box that can be bad are those intersecting
$R_{k}(i,\tau)$. Let $I$ be the set of tuples $(i^{\prime},\tau^{\prime})$
such that $R_{k}(i,\tau)\cap R_{k}(i^{\prime},\tau^{\prime})\neq\emptyset$.
Note that $R_{k}(i^{\prime},\tau^{\prime})\subset
R_{k}^{\mathrm{enl1}}(i,\tau)$ for all $(i^{\prime},\tau^{\prime})\in I$.
Moreover, the property that we get is that
$\bigcup_{(i^{\prime},\tau^{\prime})\in
I}R_{k}^{\mathrm{core}}(i^{\prime},\tau^{\prime})$ does not exhaust
$R_{k}^{\mathrm{enl1}}(i,\tau)$ in the sense that
$\bigcup_{(i^{\prime},\tau^{\prime})\in
I}R_{k}^{\mathrm{core}}(i^{\prime},\tau^{\prime})$ is separated from the
outside of $R_{k}^{\mathrm{enl1}}(i,\tau)$ by at least one layer of cores. We
define this layer of cores as

$R_{k}^{\partial\mathrm{enl1}}(i,\tau)=R_{k}^{\mathrm{enl1}}(i,\tau)\setminus\left(\bigcup_{(i^{\prime},\tau^{\prime})\in
I}R_{k}^{\mathrm{core}}(i^{\prime},\tau^{\prime})\right).$

######  Definition 2.18 (2-enlargement).

The _2-enlargement_ of a box $R_{k}(i,\,\tau)$ of scale $k$ is the set of
boxes

$R_{k}^{\mathrm{enl2}}(i,\,\tau)=\bigcup_{\begin{subarray}{c}j\in\\{-20,-19,\dots,20\\}^{d},\\\
\beta\in\\{-18,-17,\dots,3\\}\end{subarray}}R_{k}(i+j,\tau+\beta),$

and we also denote

$S_{k}^{\mathrm{enl2}}(i)=\bigcup_{j\in\\{-20,-19,\dots,20\\}^{d}}S_{k}(i+j),\quad\quad
T_{k}^{\mathrm{enl2}}(\tau)=\bigcup_{\beta\in\\{-18,-17,\dots,3\\}}T_{k}(\tau+\beta).$

Note that the 2-enlargement is a larger $(d+1)$-dimensional parallelogram
centered in $R_{k}(i,\tau)$ so that
$\sup\left\\{T_{k}^{\mathrm{enl1}}(\tau)\right\\}=\sup\left\\{T_{k}^{\mathrm{enl2}}(\tau)\right\\}$;
See Figure 2.

Figure 2: In black a box $R_{k}(i,\tau)$, with its 1-enlargement in blue and
its 2-enlargement in purple. The figure is not to scale and illustrates the
case $k\geq 2$; recall that the time intervals are defined differently at
scale $1$.

We will require a different type of boundary for the second enlargement.

######  Definition 2.19 (2-enlargement boundary).

We define
$\partial_{\mathrm{s}}^{\mathrm{enl2}}R_{k}^{\mathrm{enl2}}(i,\tau)$, the
2-enlargement boundary of $R_{k}^{\mathrm{enl2}}(i,\tau)$, as the set of
space-time points $(x,s)\in R_{k}^{\mathrm{enl2}}(i,\tau)$ such that $(x,s)\in
R_{k}^{\mathrm{core}}(i^{\prime},\tau^{\prime})$ for some
$(i^{\prime},\tau^{\prime})$ with $R_{k}(i^{\prime},\tau^{\prime})\subset
R_{k}^{\mathrm{enl2}}(i,\tau)$ and
$R_{k}(i^{\prime},\tau^{\prime})\cap\partial_{\mathrm{s}}R_{k}^{\mathrm{enl2}}(i,\tau)\neq\emptyset$.

###  2.5 Feasible Paths

In this subsection we introduce the concept of feasible paths. For any graph
$G=(V,E)$, we denote the neighbors of a vertex $v\in V$ by
$\mathcal{N}_{G}(v)=\\{w\in V:(v,w)\in E\\}$. A path
$\mathcal{P}:\mathbb{R}^{+}\to V$ on a graph $G=(V,E)$ is a càdlàg function of
time such that for any $s\in\mathbb{R}^{+}$, if we take $s^{\prime}$ to be the
smallest value that is larger than $s$ and such that
$\mathcal{P}(s^{\prime})\neq\mathcal{P}(s)$ then
$\mathcal{P}(s^{\prime})\in\mathcal{N}_{G}(\mathcal{P}(s))$. Note that a path,
as defined above, does not consider whether edges are open or closed and is
thus allowed to jump across closed edges. The same is true in the definition
below. Recall the definition of the time intervals
$\overline{\overline{T}}_{1}^{j}$ from Definition 2.2 and the inner part
$S_{1}^{\mathrm{inn}}(i)$ of box $i$ from (2.7).

######  Definition 2.20 (Feasible path).

A path $\mathcal{P}$ is said to be _feasible_ if for any times $s,s^{\prime}$
with $s,s^{\prime}\in\overline{\overline{T}}_{1}^{j}(\tau)\subset
T_{1}^{\mathrm{core}}(\tau)$ for some $j$ and $\tau>0$, and such that
$\mathcal{P}(s)\in S_{1}^{\mathrm{inn}}(i)$ for some $i\in\mathbb{Z}^{d}$ for
which $R_{1}(i,\tau)$ is a good box, then

$\|\mathcal{P}(s^{\prime})-\mathcal{P}(s)\|_{1}<\log^{2}{\ell}.$

Intuitively, a feasible path can move at most $\log^{2}\ell$ during any
interval $\overline{\overline{T}}_{1}^{j}$ in which it is inside good boxes.
Even though the definition of feasible paths does not consider whether edges
are open or closed, this is aligned with the fact that in good boxes the
clusters are of size at most $\log^{2}\ell$.

We will refer to a path that leaves the box $R_{k}(i,\tau)$ from the time
boundary as a path $\mathcal{P}$ such that $(\mathcal{P}(s),s)\in
R_{k}^{\mathrm{core}}(i,\tau)$ for some $s\geq 0$ and if $s^{\prime}>s$ is the
smallest value such that $(\mathcal{P}(s^{\prime}),s^{\prime})\notin
R_{k}(i,\tau)$ then $\mathcal{P}(s^{\prime})\in S_{k}(i)$. In other words, it
is a path that exits $R_{k}(i,\tau)$ through
$\partial_{\mathrm{t}}^{+}R_{k}(i,\tau)$. In the following two lemmas we will
prove that a feasible path always leaves good boxes from the time boundary.
Recall the definition of $\mathcal{C}_{x}(I)$, the connected component of $x$
during a time interval $I$, from the paragraph preceding Definition 2.2.

We define the _spatial core_ of a box as follows:

$R_{k}^{\mathrm{s\mathchar 45\relax
core}}(i,\tau)=S_{k}^{\mathrm{core}}(i)\times T_{k}(\tau).$ (2.10)

######  Lemma 2.21.

For all $p$ small enough (hence, $\ell$ large enough) the following holds. Let
$(i,\tau)$ be such that $R_{1}(i,\tau)$ is a good box. Let $\mathcal{P}$ be a
feasible path such that $(\mathcal{P}(s),s)\in R_{1}^{\mathrm{s\mathchar
45\relax core}}(i,\tau)$ for some $s$. Assume that either
$s\geq\overline{t}_{1}$ or
$|\mathcal{C}_{\mathcal{P}(s)}(s)|\leq\sqrt{\ell}\log^{2}\ell$. Then,
$\mathcal{P}$ leaves $R_{1}(i,\tau)$ from the time boundary and

$\sup_{s^{\prime}\in\left[s,\max
T_{1}(\tau)\right]}\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq\sqrt{\ell}\log^{3}\ell.$

###### Proof.

For any $(v,s)\in R_{1}^{\mathrm{s\mathchar 45\relax core}}(i,\tau)$ and any
$(v^{\prime},s^{\prime})\in\partial_{\mathrm{s}}R_{1}(i,\tau)$,
$\|v-v^{\prime}\|_{1}\geq\ell$ as well as $|s^{\prime}-s|\leq 3t_{1}$. Recall
that $T_{1}(\tau)$ is split into intervals
$\overline{\overline{T}}_{1}^{j}(\tau)$ of length $\frac{\gamma}{\mu}$. Assume
first that $s\geq\overline{t}_{1}$. Then the subinterval
$\overline{T}_{1}^{j}(\tau)$ containing $s$ consists only of positive times;
hence, $\mathcal{C}_{\mathcal{P}(s)}(s)$ has cardinality at most
$\log^{2}\ell$. From the definition of feasible paths we obtain

$\sup_{s^{\prime}\in\left[s,\max
T_{1}(\tau)\right]}\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq\frac{3t_{1}\mu}{\gamma}\log^{2}\ell.$

For all small enough $p$ we have
$\frac{3t_{1}\mu}{\gamma}\log^{2}\ell=\frac{3\sqrt{\ell}}{\gamma}\log^{2}\ell\leq\ell\log^{3}\ell$,
recalling that $\gamma$ is set before we take $p$ small enough as in Remark
2.3.

If $s\in[0,\overline{t}_{1})$ then $s\in\overline{T}_{1}^{1}(0)\subset
T_{1}(0)$ and we use that during $T_{1}^{1}(0)$ no edge in $S_{1}(i)$ opens.
Therefore,

$\sup_{s^{\prime}\in\left[s,\max
T_{1}(\tau)\right]}\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq|\mathcal{C}_{\mathcal{P}(s)}(s)|+\frac{3t_{1}\mu}{\gamma}\log^{2}\ell\leq\sqrt{\ell}\log^{3}\ell.$

∎

The next lemma is the analogous of Lemma 2.21 for higher scales.

######  Lemma 2.22.

For all $m$ large enough and all $p$ small enough with respect to $m$, the
following holds. Let $k\geq 2$ and let $(i,\tau)$ be such that $R_{k}(i,\tau)$
is a good box. Let $\mathcal{P}$ be a feasible path such that
$(\mathcal{P}(s),s)\in R_{k}^{\mathrm{s\mathchar 45\relax core}}(i,\tau)$ for
some $s$. Assume that either $s\geq\overline{t}_{1}$ or
$|\mathcal{C}_{\mathcal{P}(s)}(s)|\leq\sqrt{\ell}\log^{2}\ell$. Then
$\mathcal{P}$ leaves $R_{k}(i,\tau)$ from the time boundary. Moreover, while
the path is inside the box, from time $s$ up to time $(\tau+2)t_{k}$, the path
must be within distance $\ell_{k}/9$ from $\mathcal{P}(s)$.

###### Proof.

For any $(v,s)\in R_{k}^{\mathrm{s\mathchar 45\relax core}}(i,\tau)$ and any
$(v^{\prime},s^{\prime})\in\partial_{\mathrm{s}}R_{k}(i,\tau)$,
$\|v-v^{\prime}\|_{1}\geq\ell_{k}$ as well as $|s^{\prime}-s|\leq 3t_{k}$. We
do a proof by induction on $k$. The case $k=1$ is be a direct consequence of
Lemma 2.21. We will actually assume a slightly stronger induction hypothesis.
Take $c_{1}=\frac{1}{100}$, $c_{2}=\frac{1}{10}$ and, for $j\geq 2$, set
$c_{j+1}=c_{j}+\frac{11}{mj^{2}}$. We take $m$ large enough so that
$c_{j}\leq\frac{1}{9}$ for all $j\geq 1$. Now, for a scale $k$, assume that if
$\mathcal{P}(s)\in R_{k}^{\mathrm{s\mathchar 45\relax core}}(i,\tau)$ for some
$(i,\tau)$ and some $s$ as in the statement of the lemma, then
$\sup_{s^{\prime}\in\left[s,(\tau+2)t_{k}\right]}\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq
c_{k}\ell_{k}$. We want to prove the above for scale $k+1$.

We split into two cases, starting with $k\geq 2$ (thus, $k+1\geq 3$). Let now
$\mathcal{P}$ be a feasible path such that $(\mathcal{P}(s),s)\in
R_{k+1}^{\mathrm{s\mathchar 45\relax core}}(i,\tau)$, and $R_{k+1}(i,\tau)$ is
a good box. Thus there are no pairs of non intersecting bad boxes of scale $k$
inside $R_{k+1}(i,\tau)$. By Remark 2.17, if $R_{k+1}(i,\tau)$ contains at
least one bad box $R_{k}(i^{\prime},\tau^{\prime})$, then all bad boxes
contained in $R_{k+1}(i,\tau)$ are contained in
$R_{k}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$. Inside
$R_{k}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$ a feasible path has no
restriction on how quickly it can move and it could potentially traverse
$S_{k}^{\mathrm{enl1}}(i^{\prime})$ instantaneously. The remaining boxes of
scale $k$ that are in $R_{k+1}(i,\tau)$ are good and by the inductive
hypothesis we can use that in these ones the maximum displacement of the path
is bounded above by $c_{k}\ell_{k}$, so for $k\geq 2$ it follows that

$\displaystyle\sup_{s^{\prime}\in\left[s,(\tau+2)t_{k+1}\right]}\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq$
$\displaystyle 9\ell_{k}+\left(12+\frac{2t_{k+1}}{2t_{k}}\right)c_{k}\ell_{k}$
$\displaystyle\leq$ $\displaystyle
9\ell_{k}+\left(12+k^{2}m\right)c_{k}\ell_{k}$ $\displaystyle=$
$\displaystyle\left(\frac{9}{mk^{2}}+\frac{12c_{k}}{mk^{2}}+c_{k}\right)\ell_{k+1}$
$\displaystyle\leq c_{k+1}\ell_{k+1}.$

The term $\left(12+\frac{2t_{k+1}}{2t_{k}}\right)$ accounts for the following
boxes. Each time the path $\mathcal{P}$ finds itself at the starting time of a
$k$-core, it spends at least time $2t_{k}$ inside the corresponding $k$-box,
and after that amount of time finds itself at the starting time of another
$k$-core. This gives at most $\frac{2t_{k+1}}{2t_{k}}$ $k$-cores for which we
can apply the induction hypothesis. There are situations, however, that we
cannot guarantee that the path $\mathcal{P}$ is at the _starting_ time of a
$k$-core. One first situation is the very first box. We can still apply the
induction hypothesis in such cases, since the hypothesis requires only that
the path is inside the spatial core, regardless of it being the starting time
of a core or not, but can give rise to at most $12$ additional boxes to the
counting: the first box, the boxes right before and after
$R_{k}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$, and the $9$ time intervals
contained in $R_{k}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$.

Now we turn to the last case, which is $k=1$ (that is, $k+1=2$). We proceed in
the same way as before, but taking care of the fact that boxes at scale $1$
have a different length in the time dimension. We have

$\displaystyle\sup_{s^{\prime}\in\left[s,(\tau+2)t_{2}\right]}\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq$
$\displaystyle 9\ell_{1}+\left(12+\frac{2t_{2}}{t_{1}}\right)c_{1}\ell_{1}$
$\displaystyle\leq$ $\displaystyle 9\ell_{1}+\left(12+2m\right)c_{1}\ell_{1}$
$\displaystyle=$
$\displaystyle\left(\frac{9}{m}+\frac{12c_{1}}{m}+2c_{1}\right)\ell_{2}$
$\displaystyle\leq c_{2}\ell_{2}.$

The proof is concluded by taking $m$ large enough to guarantee that
$c_{k+1}=\frac{1}{100}+\frac{1}{10}+\frac{20}{m}\sum_{i=2}^{k}\frac{1}{i^{2}}<\frac{1}{9}$
for all $k$. ∎

Next we will prove that if a feasible path enters the 2-enlargement of a box
$R_{k}(i,\tau)$ from its spatial boundary, and all the $k$-boxes inside
$R_{k}^{\mathrm{enl2}}(i,\tau)\setminus R_{k}^{\mathrm{enl1}}(i,\tau)$ are
good, then the path remains far from the box $R_{k}(i,\tau)$. For this lemma,
recall the definition of
$\partial_{\mathrm{s}}^{\mathrm{enl2}}R_{k}^{\mathrm{enl2}}(i,\tau)$ the
2-enlargement boundary of $R_{k}(i,\tau)$ from Definition 2.19.

######  Lemma 2.23.

Let $\mathcal{P}$ be a feasible path such that
$(\mathcal{P}(s),s)\in\partial_{\mathrm{s}}^{\mathrm{enl2}}R_{k}^{\mathrm{enl2}}(i,\tau)$
for some $(i,\tau)$ and $s\geq 0$. Assume that either $s\geq\overline{t}_{1}$
or $|\mathcal{C}_{\mathcal{P}(s)}(s)|\leq\sqrt{\ell}\log^{2}\ell$. Assume also
that $R_{k}(i^{\prime},\tau^{\prime})$ is good for all
$R_{k}(i^{\prime},\tau^{\prime})\subset R_{k}^{\mathrm{enl2}}(i,\tau)\setminus
R_{k}^{\mathrm{enl1}}(i,\tau)$. Then,

$\inf_{\begin{subarray}{c}v\in S_{k}^{\mathrm{enl1}}(i)\\\ s^{\prime}\geq
s,\;s^{\prime}\in
T_{k}^{\mathrm{enl2}}(\tau)\end{subarray}}\|\mathcal{P}(s^{\prime})-v\|_{1}\geq
12\ell_{k}.$

###### Proof.

By hypothesis every box $R_{k}(\cdot,\cdot)\subset
R_{k}^{\mathrm{enl2}}(i,\tau)\setminus R_{k}^{\mathrm{enl1}}(i,\tau)$ is good.
For any $s^{\prime}\in T_{k}^{\mathrm{enl2}}(\tau)$, $|s-s^{\prime}|\leq
24t_{k}$. Assume without loss of generality that during $[s,s^{\prime}]$ the
path never visits a box $R_{k}(\cdot,\cdot)$ which is not contained in
$R_{k}^{\mathrm{enl2}}(i,\tau)$; otherwise we can carry out the proof
separately to each portion of the path that only traverses boxes
$R_{k}(\cdot,\cdot)$ contained in $R_{k}^{\mathrm{enl2}}(i,\tau)$. Let
$(i^{\prime},\tau^{\prime})$ be such that $(\mathcal{P}(s),s)\in
R_{k}^{\mathrm{core}}(i^{\prime},\tau^{\prime})$. Since
$R_{k}(i^{\prime},\tau^{\prime})$ is a good box, letting
$s^{\prime\prime}=\sup\left\\{T_{k}(\tau^{\prime})\right\\}$ we have that
$\|\mathcal{P}(s)-\mathcal{P}(s^{\prime\prime})\|_{1}\leq\frac{\ell_{k}}{9}$
by Lemma 2.22. If $s^{\prime\prime}<s^{\prime}$, we can iterate the above
argument obtaining that $\|\mathcal{P}(s)-\mathcal{P}(s^{\prime})\|_{1}\leq
24\frac{\ell_{k}}{9}$, where $24$ amounts for the largest number of
iterations. Since boxes have length $2t_{k}$ in the time dimension, it would
be enough to replace $24$ by $12$ for $k\geq 2$, but we just use the larger
bound $24$ to accommodate also the $k=1$ case, for which the length of a box
in the time dimension is smaller.

Now since $\frac{24\ell_{k}}{9}$ is smaller than $13\ell_{k}$, which is the
distance between $\mathcal{P}(s)$ and the spatial boundary of
$S_{k}^{\mathrm{enl1}}(i)$ enlarged by all boxes $R_{k}(\cdot,\cdot)$ that
intersects it, the path can only traverse good $k$-boxes while inside
$R_{k}^{\mathrm{enl2}}(i,\tau)$. In addition, for any $v\in
S_{k}^{\mathrm{enl1}}(i)$ one has

$\|v-\mathcal{P}(s^{\prime})\|_{1}\geq\|v-\mathcal{P}(s)\|_{1}-\frac{24\ell_{k}}{9}\geq
15\ell_{k}-\frac{24\ell_{k}}{9}\geq 12\ell_{k}.$

∎

###  2.6 Great Boxes

We will need a stroger notion for boxes of scale $1$, which we will call
_great_ boxes.

######  Definition 2.24.

A box $R_{1}(i,\tau)$ is said to be $k$-great if for all $k^{\prime}\leq k$,
for all $R_{k^{\prime}}(i^{\prime},\tau^{\prime})$ such that
$R_{k^{\prime}}^{\mathrm{enl2}}(i^{\prime},\tau^{\prime})$ intersects
$R_{1}(i,\tau)$ then $R_{k^{\prime}}(i^{\prime},\tau^{\prime})$ is good.
Moreover, we define

$G_{k}=\\{(i,\tau):R_{1}(i,\tau)\text{ is }k\text{-great}\\}$

to be the set of $k$-great boxes.

Later we will see that the walker has to traverse a feasible path. The next
lemma will be used to say that if the walker traverses a $k$-box that is good
with a large neighborhood of good $k$-boxes, then it is necessarily the case
that the walker has to traverse enough $k$-great boxes. Such great boxes will
be the places where we will attemp a simple random walk coupling later.

######  Lemma 2.25.

Let $\mathcal{P}$ be a feasible path such that $(\mathcal{P}(\tau t_{k}),\tau
t_{k})\in\partial_{\mathrm{t}}^{-}R_{k}^{\mathrm{core}}(i,\tau)$ for some
$(i,\tau)$. Assume that either $\tau>0$ or $|\mathcal{C}_{\mathcal{P}(\tau
t_{k})}(\tau t_{k})|\leq\sqrt{\ell}\log^{2}\ell$. Then there exists $C_{8}>0$
such that letting $r=C_{\ref*{cte:gbc}}\frac{t_{k}}{t_{1}}$ we can find times
$s_{1}<\dots<s_{r}$ and distinct space-time indices
$(i_{1},\tau_{1}),\dots,(i_{r},\tau_{r})$ such that the following all hold:

  * •

For all $j$,
$(\mathcal{P}(s_{j}),s_{j})\in\partial_{\mathrm{t}}^{-}R_{1}^{\mathrm{core}}(i_{j},\tau_{j})$
and $\mathcal{P}$ exits $R_{1}(i_{j},\tau_{j})$ from the time boundary.

  * •

$R_{1}(i_{j},\tau_{j})\subset R_{k}(i,\tau)$ are $k$-great for all $j$.

  * •

$\tau_{1}t_{1}\geq\tau t_{k}$ and $\tau_{j}\geq\tau_{j-1}+2$ for all
$j\in\left\\{2,3,\ldots,r\right\\}$.

###### Proof.

First, note that if a box $R_{1}(\tilde{i},\tilde{\tau})$ is $(k-1)$-great and
is contained in $R_{k}(i,\tau)$ then it is also $k$-great. We will prove the
statement of the lemma replacing $C_{\ref*{cte:gbc}}$ with $c_{k}$, some
function of $k$. Then the lemma follows by showing that there is a universal
value $C_{\ref*{cte:gbc}}$ such that $0<C_{\ref*{cte:gbc}}\leq c_{k}$ for all
$k$. We will do a proof by induction on $k$. Case $k=1$ is trivially verified
by choosing $c_{1}=1$ because in this case $r=c_{1}=1$ and we take
$(i_{1},\tau_{1})=(i,\tau)$.

Now, for $k\geq 2$, assume the lemma is true up to scale $k-1$ and consider a
feasible path that at time $\tau t_{k}$ is inside
$\partial_{\mathrm{t}}^{-}R_{k}^{\mathrm{core}}(i,\tau)$ such that every box
of scale $k$ whose $2$-enlargement intersects $R_{k}(i,\tau)$ is good. By
Remark 2.17, the bad boxes of scale $k-1$ inside $R_{k}(i,\tau)$ (if there are
any) are all contained in $R_{k-1}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$
for some $i^{\prime},\tau^{\prime}$. We then regard all boxes of scale $1$
which are in at least one of the $2$-enlargement of the boxes contained in
$R_{k-1}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$ as potentially not
$(k-1)$-great. By Lemma 2.22 we know that $\mathcal{P}$ crosses
$\partial_{\mathrm{t}}^{+}R_{k}(i,\tau)$ before
$\partial_{\mathrm{s}}R_{k}(i,\tau)$. In words the path stays for time at
least $2t_{k}$ in the box $S_{k}(i)$.

Since the path starts from
$\partial_{\mathrm{t}}^{-}R_{k}^{\mathrm{core}}(i,\tau)$, it starts on
$\partial_{\mathrm{t}}^{-}R_{k-1}^{\mathrm{core}}(i^{\prime\prime},\tau^{\prime\prime})$
for some $i^{\prime\prime}$ and $\tau^{\prime\prime}$. In this $(k-1)$-box we
can apply the inductive hypothesis, so after time $2t_{k-1}$ the path has gone
through at least $c_{k-1}\frac{t_{k-1}}{t_{1}}$ distinct $(k-1)$-great boxes.
Since this path remains inside $R_{k}(i,\tau)$, we immediately obtain that
such boxes are all $k$-great boxes. When the path reaches
$\partial_{\mathrm{t}}^{+}R_{k-1}(i^{\prime\prime},\tau^{\prime\prime})$ we
have that the path is now on
$\partial_{\mathrm{t}}^{-}R_{k-1}^{\mathrm{core}}(i^{\prime\prime}+j,\tau^{\prime\prime}+2)\subset
R_{k}(i,\tau)$ for some $j\in\mathbb{Z}^{d}$ and from here we can reapply the
inductive hypothesis. So it remains to count how many times we can iterate
this procedure before $2t_{k}$ amount of time has passed.

To do this, we first count how much time the path can spend inside the
$2$-enlargement of a bad $(k-1)$-box. It suffices to count how much time is
spanned by the boxes whose $2$-enlargements intersect
$R_{k-1}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$, which is
$|T_{k-1}^{\mathrm{enl1}}(\cdot)|+2|T_{k-1}^{\mathrm{enl2}}(\cdot)|=57t_{k-1}$.
Hence, the number of times the above procedure can be iterated is at least

$\frac{2t_{k}-57t_{k-1}}{2t_{k-1}}=\frac{t_{k}}{t_{k-1}}\left(1-\frac{57}{2m(k-1)^{2}}\right).$

From the inductive hypothesis, the path will traverse at least

$\frac{t_{k}}{t_{k-1}}\left(1-\frac{57}{2m(k-1)^{2}}\right)c_{k-1}\frac{t_{k-1}}{t_{1}}=c_{k}\frac{t_{k}}{t_{1}}$

$(k-1)$-great boxes, by setting
$c_{k}=\left(1-\frac{57}{2m(k-1)^{2}}\right)c_{k-1}$. These boxes are
$k$-great by the properties of $R_{k}(i,\tau)$. The lemma is then concluded by
setting

$C_{\ref*{cte:gbc}}=\lim_{k\to\infty}c_{k}=\prod_{i=1}^{\infty}\left(1-\frac{57}{2mi^{2}}\right)>0.$

∎

##  3 Overview of the Proof

In this section we give a high-level description of the proof. Consider two
processes $\\{M_{t}^{\star}\\}_{t\geq 0}=\\{X_{t},\eta_{t}^{\star}\\}_{t\geq
0}$ and $\\{\overline{M}_{t}^{\star}\\}_{t\geq
0}=\\{\overline{X}_{t},\overline{\eta}_{t}^{\star}\\}_{t\geq 0}$ with starting
states $M_{0}^{\star},\overline{M}_{0}^{\star}\in\Omega^{\star}$. We will
construct a coupling of the two processes so that for some time
$T=\Delta_{1}+\Delta_{2}+\Delta_{3}$ of order $\frac{n^{2}}{\mu}$ the two
configurations agree with positive probability. Since $\\{M_{t}\\}_{t\geq 0}$
can be recovered from $\\{M_{t}^{\star}\\}_{t\geq 0}$, by sampling
independently the edges with status $\star$, we will obtain our result.

The coupling will consist of three different phases which we will describe in
a high level way below. The coupling of each phase will have a small, albeit
positive, probability of failing. If the coupling of a phase fails, we declare
the whole three-phase procedure to have failed, let the two processes evolve
arbitrarily until time $T$ and restart everything again from phase 1. The
detailed analysis of each phase will be given in sections 4, 5 and 6. Then in
section 7, we will put all phases together and complete the proof of Theorem
1.1.

###  3.1 First phase: the local coupling

During the first phase we let the two processes evolve _independently_ , and
wait for the first time the graphs of the two processes agree on a ball of
radius $2\ell$ around the walkers, that is, we wait for a time $t$ such that

$\eta_{t}^{\star}(X_{t}+e)=\overline{\eta}_{t}^{\star}(\overline{X}_{t}+e),$

for all edges $e\in E(B_{2\ell}^{\infty}(0))$, where $B_{r}^{\infty}(x)$ is
the vertices inside the $L_{\infty}$ ball of radius $r$ around $x$. We will
show in Lemma 4.1 that this will happen within time $\Delta_{1}$ with large
enough probability, where $\Delta_{1}$ has order $\frac{\log^{2}n}{\mu}$. This
is the shortest of the three phases.

If the first phase does not end within time $\Delta_{1}$, we declare the whole
three-phase procedure to have failed. This phase will be handled in section 4.

###  3.2 Second phase: the non-Markovian coupling of the walkers

This is the most involved phase. After the first phase has been completed
successfully, the graphs of the two processes are the same on a ball of radius
$2\ell$ around the walkers. Then, in the second phase we wish to couple the
motion of the walkers. We use the tessellation to decide when to couple the
walkers identically (so that they jump in the same way) and when to perform a
better coupling aiming to decrease the distance between the walkers.

Intuitively, whenever the walkers are passing through a “bad” region of the
environment (which in our case will be the 2-enlargement of a bad box) we will
just do the identity coupling to make sure the distance between the walkers
does not increase. In fact, we will only be able to do the identity coupling
because we will use the annulus between the 2-enlargement of the bad box and
the bad box itself (which is composed of good boxes) to give time for the
graphs around the walkers to get coupled in both configurations, allowing the
identity coupling to be carried out. If instead the two walkers are in a great
box, then we try to do a better coupling, which we shall refer to as a _simple
random walk moment_.

More precisely, translate time so that the second phase starts from time $0$.
Then, we create the multi-scale tessellation describe in Section 2.1 up to
time $\Delta_{2}+\Delta_{3}$ where $\Delta_{2}$ and $\Delta_{3}$ are of order
$\frac{n^{2}}{\mu}$. We will fix a largest scale $k_{\mathrm{max}}$ and will
look at how many times the walkers enter $k_{\mathrm{max}}$-great boxes.

When the walkers are in great boxes, Lemma 5.14 will give that the environment
is favourable enough so that with positive probability the displacement of the
walkers will have the same distribution as that of a simple random walk on
$\mathbb{T}_{n}^{d}$ (i.e., where all edges are open). Phase 2 ends at time
$\Delta_{2}$ where we check whether the walkers are coupled and the graphs are
coupled on a ball of radius $2\ell$ around the walkers.

Lemma 2.25 says that the walkers will cross an order of $n^{2}$ great boxes
during $[0,\Delta_{2}]$ and, therefore, by time $\Delta_{2}$ the walkers are
expected to have done an order of $n^{2}$ simple random walk steps. Since two
simple random walkers on $\mathbb{T}_{n}^{d}$ can be coupled in a way that
they coalesce after a time of order $n^{2}$, we can ensure that with high
probability phase 2 ends successfully. The details are carried out in section
5.

###  3.3 Third phase: the coupling of the graphs

The third phase starts are time $\Delta_{2}$; as before we translate time so
that the second phase starts at time 0. At the beginning of the third phase
the walkers are coupled and the graphs are coupled as well on a ball of radius
$2\ell$ around them. The idea of this phase is to keep performing identity
coupling until the graphs couple together everywhere. We will show that this
simple idea works.

There is one tricky issue. During the second phase, we needed to construct the
tessellation all the way to time $\Delta_{2}+\Delta_{3}$, while the second
phase ends already at time $\Delta_{2}$. The reason for this is that, in order
to know whether we can perform a simple random walk moment, we need to observe
a little bit of future information about the environment. Therefore, as we
performed the second phase, we observed some information from the updates
after the end of phase two.

So the goal of the third phase is simply to let time pass until we get to a
point where no information regarding future times has been observed, meanwhile
doing identity coupling. With this, during the third phase we aim to keep the
walkers coupled at all times, while we finish to couple the graphs before time
$\Delta_{2}+\Delta_{3}$.

We do not use any further information from the tessellation than what we
already observed for phase 2. The delicate point is that in order to apply
identity coupling of the walkers, as we explained in the second phase, we have
to ensure that the graphs around the walkers are coupled. How large a region
we require to be coupled depend on the environment of good and bad boxes that
is ahead of the walker, but now we cannot observe anything beyond what we have
already observed in phase two; otherwise we would keep observing future
information.

As hinted above, we just proceed with the identity coupling “blindly”. That
is, we perform identity coupling up to time $\Delta_{2}+\Delta_{3}$ assuming
that any information that we have not yet observed is “good”, and simply “hope
for the best”. It will turn out that this procedure succeeds with large
probability leaving the two processes completely coupled (both the graphs and
the walkers) by time $\Delta_{2}+\Delta_{3}$. The details of this phase are
given in Section 6.

###  3.4 What if a phase fails?

If any of the three phases does not successfully end, we let the two processes
run independently (modulo what has already been observed) until the end of the
third phase. This is needed as we might have observed some information about
the environment up to that time. After that, we repeat the procedure from
phase $1$. Since the three phases succeed with positive probability, we only
need to repeat the whole procedure a constant number of times. The end of the
proof of the upper bound is given in section 7.

##  4 First Phase

During the first phase we let the processes
$M_{t}^{\star}=(X_{t},\eta_{t}^{\star})$ and
$\overline{M}_{t}^{\star}=(\overline{X}_{t},\overline{\eta}_{t}^{\star})$
evolve independently. Let $\Psi_{t}:V\to V$ be the translation that maps
$X_{t}$ into $\overline{X}_{t}$; we will abuse notation and use the same
$\Psi_{t}$ to denote the corresponding translation map $E\to E$ of the edges.
For any $i\in\mathbb{Z}_{+}\cup\left\\{\infty\right\\}$, we define

$E(B_{r}^{i}(v))=\\{(v_{1},v_{2})\in E:v_{1},v_{2}\in
B^{i}_{r}(v)\\}\quad\text{and}\quad B^{i}_{r}(v)=\\{v_{1}\in
V:\|v-v_{1}\|_{i}\leq r\\};$

thus $E(B_{r}^{i}(v))$ is the set of edges in the ball of radius $r$ around
$v$ according to the norm $L_{i}$. We omit $i$ from the superscript whenever
$i=1$. Define the event

$\displaystyle\mathcal{B}_{t}=$ $\displaystyle\left\\{\forall e\in
E\left(B_{1}(X_{t})\right),\,{\eta}_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}\left(\Psi_{t}(e)\right)=0\right\\}$
$\displaystyle\cap\left\\{\forall e\in E(B_{2\ell}^{\infty}(X_{t}))\setminus
E(B_{1}(X_{t})),\,{\eta}_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Psi_{t}(e))=\star\right\\}$
(4.1)

that the edges in a $L_{\infty}$ ball of radius $2\ell$ around the walkers are
all $\star$ at time $t$, except for the ones adjacent to the walkers which are
closed; recall that $\ell$ is the size of the core of boxes of scale $1$,
whose value is given in (2.1). Let

$\tau_{B}=\inf\left\\{t\geq 0:\mathcal{B}_{t}\text{ holds}\right\\}.$ (4.2)

Note that $\tau_{B}$ is a stopping time. Define
$\Delta_{1}=\frac{C_{{9}}\log^{2}n}{\mu}$, for some constant
$C_{\ref*{cte:p1}}(p)>0$, and define the event

$F_{1}=\\{\tau_{B}<\Delta_{1}\\},$ (4.3)

which we shall take as the event that phase 1 succeeds. This event is a bit
more restricted than the one announced in the previous section, but this will
be convenient for us in the next phase.

We then run phase 1 until $\tau_{B}$ or $\Delta_{1}$, whichever occurs first.
If it turns out that $F_{1}$ does not occur, phase 1 is then stopped at time
$\Delta_{1}$ and we declare the whole procedure to have failed at time
$\Delta_{1}$. In this case, we do not proceed to the second phase, and define
$\Delta_{1}$ as the _failing time_ of the procedure and, as we will explain
more thoroughly in Section 7, we will restart from phase 1 from $\Delta_{1}$.

The following lemma establishes the probability that the first phase is
successful.

######  Lemma 4.1 (Phase 1 success probability).

For any $\delta>0$, there exists $p_{0}=p_{0}(d,\delta)>0$ such that for any
$p<p_{0}$, there exists $C_{\ref*{cte:p1}}(p,d,\delta)>0$ in the definition of
$\Delta_{1}$ so that for any initial configurations
${\eta}_{0}^{\star},\overline{\eta}_{0}^{\star}\in\Omega^{\star}$ we obtain

$\mathbb{P}\left(F_{1}^{c}\right)\leq\delta$

for all large enough $n$.

Before showing that phase 1 succeeds with good probability, we need to
establish a simple result on percolation. We then prove Lemma 4.1 in Section
4.2.

###  4.1 Percolation on cylinders and open upwards paths

Let $G=(V,E)$ be a finite graph whose maximum degree is $d_{\mathrm{max}}$; in
our case, it would be enough to take $G$ to be the $d$-dimensional torus
$\mathbb{T}_{n}^{d}$ of side length $n$, where nearest-neighbors are defined
according to the $\ell_{\infty}$ norm. We consider the discrete cylinder
$V_{\mathrm{cyl}}=V\times\mathbb{Z}_{+}$ and define a site percolation process
on $V_{\mathrm{cyl}}$ with parameter $\varrho>0$. In other words, we declare
each site of $V_{\mathrm{cyl}}$ to be _open_ with probability $\varrho$,
independently of one another; a vertex that is not open is said to be
_closed_. For two vertices of $x,y\in V$, we write $x\sim y$ to denote that
the graph distance between $x$ and $y$ is at most $1$ in $G$; thus, for
example, $x\sim x$ for all $x\in V$.

######  Definition 4.2 (open upwards path).

An _open upwards path_ in $V_{\mathrm{cyl}}$ is a sequence of sites
$(i_{0},\tau_{0}),(i_{1},\tau_{1}),(i_{2},\tau_{2}),\ldots,(i_{r},\tau_{r})$
such that $i_{j}\in V$, $\tau_{j}\in\mathbb{Z}_{+}$, $i_{j}\sim i_{j+1}$ and
the following holds for all $j$. If $(i_{j},\tau_{j})$ is open, then
$\tau_{j+1}=\tau_{j}+1$; otherwise,
$\tau_{j+1}-\tau_{j}\in\left\\{0,1\right\\}$. In other words, the path is
compelled to move “upwards” in the cylinder when it visits open sites.

Note that an open upwards path is allowed to visit a vertex more than once. We
say that an open upwards path
$(i_{0},\tau_{0}),(i_{1},\tau_{1}),(i_{2},\tau_{2}),\ldots,(i_{r},\tau_{r})$
_traverses $m$ levels_ if $\tau_{r}-\tau_{0}=m$. When $\varrho$ is close to
$1$, an open upwards path cannot visit too many closed sites. This is
quantified in the next lemma.

######  Lemma 4.3 (Open upwards path).

Let $(i_{0},0)\in V_{\mathrm{cyl}}$ be fixed. For any $\alpha>0$, there exists
$\varrho^{\prime}=\varrho^{\prime}(\alpha,d_{\mathrm{max}})\in(0,1)$ such that
if $\varrho>\varrho^{\prime}$ then the probability that there exists an open
upwards path from $(i_{0},0)$ that traverses $m$ levels and visits at least
$\alpha m$ distinct closed sites is at most $e^{-cm}$ for some constant
$c=c(\alpha,d_{\mathrm{max}})>0$.

Before proving the above result, we need the following estimate in the number
of subgraphs of $G$ that contain a given vertex.

######  Lemma 4.4.

Given a vertex $v\in V$, let $A_{r}$ be the number of induced connected
subgraphs of $V$ containing $v$ and having $r$ vertices. There exists a
constant $c=c(d_{\mathrm{max}})>0$ such that $A_{r}\leq e^{cr}$ for all $r$.

###### Proof.

This proof is quite standard and a version for the lattice can be found in [6,
Proof of Theorem 4.20]; we include a proof here for the sake of completeness.
Let $A_{r,s}$ be the number of induced connected subgraphs of $V$ containing
$v$ and having $r$ vertices and $s$ boundary vertices, where a boundary vertex
is a vertex that does not belong to the subgraph but has a neighbor who does.
Hence, $A_{r}=\sum_{s}A_{r,s}$. Note that for any $\varrho\in(0,1)$, if we
perform percolation on $V$, we obtain

$\sum_{r,s}A_{r,s}\varrho^{r}(1-\varrho)^{s}=1.$ (4.4)

For any vertex $u\in V$ denote $d(u)$ its degree in $G$. Let $S\in V$ be one
subgraph counted in $A_{r,s}$, denote $m(S)$ the number of edges between
vertices of $S$ and $\partial S$ the number of edges between vertices in $S$
and vertices in $V\setminus S$. Then,

$d_{\mathrm{max}}r\geq\sum_{u\in S}d(u)=2m(S)+\partial S\geq
2\left(r-1\right)+s.$

Thus, $s\leq\left(d_{\mathrm{max}}-2\right)r+2$. Plugging this result into
(4.4) and taking $\varrho=\frac{1}{2}$ we obtain

$1\geq\sum_{r,s}A_{r,s}\varrho^{r}(1-\varrho)^{\left(d_{\mathrm{max}}-2\right)r+2}=\sum_{r,s}A_{r,s}2^{-\left(d_{\mathrm{max}}-1\right)r-2}=\sum_{r}A_{r}2^{-\left(d_{\mathrm{max}}-1\right)r-2}.$

Thus, $A_{r}\leq 2^{\left(d_{\mathrm{max}}-1\right)r+2}$ for each $r$. ∎

###### Proof of Lemma 4.3.

Let $m$ be an integer and, for convenience, set $\tau_{0}=0$. Consider an open
upwards path
$(i_{0},\tau_{0}),(i_{1},\tau_{1}),(i_{2},\tau_{2}),\ldots,(i_{r},\tau_{r})$
such that $\tau_{r}-\tau_{0}=m$; that is, the path traverses $m$ levels. Let
$s_{1}$ be the number of distinct closed sites visited by the path before it
traverses $1$ level, and for $j\geq 2$ let $s_{j}$ be the number of distinct
closed sites visited by the path after having traversed $j-1$ levels and
before traversing $j$ levels. So $\sum_{j=1}^{m}s_{j}$ is the total number of
distinct closed sites visited by the path. Note that, the sites counted in
each $s_{j}$ must be of the form $(\cdot,j-1)$ and must form a connected set
with respect to the relation $\sim$ over $G$. Using Lemma 4.4, given
$s_{1},s_{2},\ldots,s_{m}$, the number of possibles ways to pick the set of
distinct sites within $(i_{0},\tau_{0}),(i_{1},\tau_{1}),\ldots$ is

$\left(d_{\mathrm{max}}+1\right)^{m}\prod_{j=1}^{m}s_{j}e^{c^{\prime}s_{j}},$

where $c^{\prime}$ is the constant from Lemma 4.4, and the term $s_{j}$ in the
product counts the number of sites at level $j$ that can be selected to be the
last vertex visited by the path before going to level $j+1$. Then,
$\left(d_{\mathrm{max}}+1\right)^{m}$ accounts for the number of ways to
choose the first site at level $j$ given the last site at level $j-1$; this
amounts to at most $d_{\mathrm{max}}+1$ choices per level. If we fix
$\sum_{j=1}^{m}s_{j}=S$, the number of ways to select the $s_{j}$ is
$\binom{S+m-1}{S}$. Finally, given all sites in the path with $s_{j}$ as
defined above, the probability that this path is an open upwards path is at
most $\prod_{j=1}^{m}(1-\varrho)^{s_{j}}$ since each site counted in the
$s_{j}$ must be closed. Therefore, the expected number of open upwards paths
that traverse $m$ levels and visit at least $\alpha m$ closed sites is at most

$\displaystyle\sum_{S\geq\alpha
m}\binom{S+m-1}{S}\left(d_{\mathrm{max}}+1\right)^{m}\prod_{j=1}^{m}e^{c^{\prime}s_{j}}s_{j}(1-\varrho)^{s_{j}}$
$\displaystyle=\left(d_{\mathrm{max}}+1\right)^{m}\sum_{S\geq\alpha
m}\binom{S+m-1}{S}\left(c^{\prime\prime}e^{c^{\prime\prime}}(1-\varrho)\right)^{S},$

where we used that given $c$ there exists a constant $c^{\prime\prime}$ such
that $ze^{c^{\prime}z}\leq c^{\prime\prime}e^{c^{\prime\prime}z}$ for all $z$.
It is enough to use the trivial bound $\binom{S+m-1}{S}\leq 2^{S+m-1}$ in the
above expression to obtain the upper bound

$\left(2(d_{\mathrm{max}}+1)\right)^{m}\sum_{S\geq\alpha
m}\left(2c^{\prime\prime}e^{c^{\prime\prime}}(1-\varrho)\right)^{S}\leq
2\left(2(d_{\mathrm{max}}+1)\right)^{m}\left(2c^{\prime\prime}e^{c^{\prime\prime}}(1-\varrho)\right)^{\alpha
m},$

with the inequality hold whenever $\varrho$ is close enough to $1$ so that
$2c^{\prime\prime}e^{c^{\prime\prime}}(1-\varrho)\leq\frac{1}{2}$. Then the
lemma holds by setting $\varrho$ further closer to $1$ so that
$4(d_{\mathrm{max}}+1)\left(2c^{\prime\prime}e^{c^{\prime\prime}}(1-\varrho)\right)^{\alpha}\leq
e^{-c}$. ∎

By using a result by Liggett, Schonmann and Stacey [8], the above result can
be extended to percolation on $\mathbb{T}_{d}\times\mathbb{Z}_{+}$ with
bounded dependences.

######  Lemma 4.5.

Let $C\geq 1$ be a constant. Consider a site percolation process on
$\mathbb{T}_{d}\times\mathbb{Z}_{+}$ where the probability that a given site
is open depends on at most $C$ other sites. Then Lemma 4.3 holds with the
lower bound on $\varrho$ depending on $C$.

###### Proof.

For any $\tilde{\varrho}$, provided $\varrho$ is large enough we can apply
Liggett, Schonmann and Stacey [8, Theorem 0.0] to obtain that the dependent
site percolation process stochastically dominates an independent site
percolation process of parameter $\tilde{\varrho}$. The lemma then follows by
applying Lemma 4.3 to this independent site percolation process. ∎

###  4.2 Proof of Lemma 4.1

Now we are in a position to establish the occurence of the first phase.

###### Proof of Lemma 4.1.

Let $\tau_{B}^{\prime}$ be the first time $t\geq t_{1}$ such that $X_{t}$ and
$\overline{X}_{t}$ are both isolated, meaning that all edges adjacent to them
are closed. We will show that $\tau_{B}^{\prime}$ occurs before time
$\Delta_{1}-t_{1}+\overline{t}_{1}$.

For each process $M_{t}^{\star}$ and $\overline{M}_{t}^{\star}$ we create a
tessellation of $\mathbb{T}_{n}^{d}\times[0,\Delta_{1}]$ into boxes of scale
$1$ using the values for $\ell$ and $t_{1}$ from Section 2.1. The event that a
given box is good is defined as in Definition 2.7. We let $M_{t}^{\star}$ and
$\overline{M}_{t}^{\star}$ evolve independently of one another until a
stopping time $st_{1}$ where $X_{st_{1}}$ and $\overline{X}_{st_{1}}$ are both
in good boxes and $s\geq 1$. Note that good $1$-boxes form a dependent site
percolation process on $\mathbb{T}^{d}_{n}\times\mathbb{Z}_{+}$ so that we can
apply Lemma 4.5. Let $(i_{0},1)$ and $(\overline{i}_{0},1)$ be the boxes
visited by $X_{t}$ and $\overline{X}_{t}$ at time $t=t_{1}$. Now, since random
walks must traverse a feasible path, and since feasible paths leave good boxes
from the time boundary (cf. Lemma 2.21), we obtain that from $(i_{0},1)$ and
$(\overline{i}_{0},1)$ the random walks $X_{t}$ and $\overline{X}_{t}$ must
traverse an open upwards path. Therefore, the probability that up to level
$m=\Delta_{1}/t_{1}-1$ we have that $X_{t}$ and $\overline{X}_{t}$ each
visited more than $\frac{m}{3}$ bad $1$-boxes is at most $2e^{-cm}$ provided
$p$ is small enough (which makes the probability that a $1$-box being good
large enough). Under this event, there must exist $\frac{m}{3}$ instances of
time $s\leq m$ at which $X_{st_{1}}$ and $\overline{X}_{st_{1}}$ are both in
good $1$-boxes. when this happens, at time $st_{1}+\overline{t}_{1}$ both
$X_{st_{1}+\overline{t}_{1}}$ and $\overline{X}_{st_{1}+\overline{t}_{1}}$ are
isolated in a vertex (i.e., all edges adjacent to them are closed). Therefore,

$\mathbb{P}\left(\tau_{B}^{\prime}\geq\Delta_{1}-t_{1}+\overline{t}_{1}\right)\leq
n^{2d}\mathbb{P}\left(s>m\right)\leq 2ne^{-cm},$

where the term $n^{2d}$ accounts for the number of choices for $i_{0}$ and
$\overline{i}_{0}$.

Now let $\mathcal{F}$ be the $\sigma$-algebra generated by $M_{t}^{\star}$ and
$\overline{M}_{t}^{\star}$ during $t\in[0,\tau_{B}^{\prime}]$. We want to
establish a lower bound on the probability that
$\mathcal{B}_{\tau_{B}^{\prime}+\overline{t}_{1}}$ given $\mathcal{F}$. Since
$X_{t}$ and $\overline{X}_{t}$ are isolated in $t=\tau_{B}^{\prime}$, it is
enough to compute the probability that all edges inside a $L_{\infty}$ ball of
radius $2\ell$ around the walkers do a $\star$-update but no non-$\star$
update, and the edges adjacent to the walkers do not open or do a non
$\star$-update during
$[\tau_{B}^{\prime},\tau_{B}^{\prime}+\overline{t}_{1}]$. This probability is

$\exp\left(-\overline{t}_{1}\mu(1-p_{\star})2\left(4\ell\right)^{d}\right)\left(1-\exp\left(-\overline{t}_{1}\mu
p_{\star}\right)\right)^{2\left(4\ell\right)^{d}}\exp\left(-\overline{t}_{1}\mu
p_{\mathrm{min}}4d\right),$

where the first term is the probability that no edge in the $L_{\infty}$ ball
of radius $2\ell$ around the walkers does a non $\star$-update, the second
term is the probability that those edges do a $\star$-update and the last term
is the probability that the edges adjacent to the walkers do not open.
Therefore,

$\displaystyle\mathbb{P}\left(F_{1}^{\mathrm{c}}\right)$ $\displaystyle\leq
2ne^{-cm}+1-\exp\left(-\overline{t}_{1}\mu(1-p_{\star})2\left(4\ell\right)^{d}-\overline{t}_{1}\mu
p_{\mathrm{min}}4d\right)\left(1-\exp\left(-\overline{t}_{1}\mu
p_{\star}\right)\right)^{2\left(4\ell\right)^{d}}$ $\displaystyle\leq
2ne^{-cm}+1-\exp\left(-\overline{t}_{1}\mu(1-p_{\star})2\left(4\ell\right)^{d}-\overline{t}_{1}\mu
p_{\mathrm{min}}4d\right)-2\left(4\ell\right)^{d}\exp\left(-\overline{t}_{1}\mu
p_{\star}\right).$

Recall that $\Delta_{1}=\frac{C_{\ref*{cte:p1}}\log^{2}n}{\mu}$,
$\overline{t}_{1}=\frac{\log^{2}\ell}{\mu}$ and
$t_{1}=\frac{\sqrt{\ell}}{\mu}$, where $\ell$ is just a large enough constant
that is set before letting $p$ be small enough. Now we show that we can make
the above smaller than $\delta$. We start with the term
$2\left(4\ell\right)^{d}\exp\left(-\overline{t}_{1}\mu p_{\star}\right)$,
which can be made, say, smaller than $\frac{\delta}{3}$. We will do this by
adjusting $\ell$ only, but this term involves also $p$ though $p_{\star}$.
However, note that $p_{\star}$ goes to $1$ as $p$ goes to $0$. So, since
$\overline{t}_{1}\mu$ is of order $\log^{2}\ell$, we can choose $\ell$ large
enough so that $2\left(4\ell\right)^{d}\exp\left(-\overline{t}_{1}\mu
p_{\star}\right)\leq\frac{\delta}{3}$ for all $p$ so that
$p_{\star}\geq\frac{1}{2}$. After fixing $\ell$, we can take $p$ close enough
to $0$, which makes $p_{\mathrm{min}}$ goes to $0$ and $p_{\star}$ goes to
$1$, so that
$\exp\left(-\overline{t}_{1}\mu(1-p_{\star})2\left(4\ell\right)^{d}-\overline{t}_{1}\mu
p_{\mathrm{min}}4d\right)\geq 1-\frac{\delta}{3}$. Finally, after fixing
$\ell$ and $p$, we can take $n$ large enough so that
$2ne^{-cm}\leq\frac{\delta}{3}$ since $m=\frac{\Delta_{1}}{t_{1}}-1$ is of
order $\log^{2}n$ as a function of $n$. This concludes the first phase.

∎

##  5 The Second Phase: non Markovian Coupling

To describe the coupling during the second phase we will use the full multi-
scale space-time tessellation described in section 2.1. For simplicity, we
translate time so that this phase starts at time $0$ and that $X_{0}$ is at
the origin. Hence, $\overline{X}_{0}$ can be arbitrary, and $\eta_{0}^{\star}$
and $\overline{\eta}_{0}^{\star}$ can be any configuration for which the event
$\mathcal{B}_{0}$ from (4.1) holds.

###  5.1 Largest scale

We begin by creating the multi-scale space-time tessellation of
$\mathbb{T}_{n}^{d}\times[0,\Delta_{2}]$ and with largest scale

$k_{\mathrm{max}}=\log_{2}\log{n}.$ (5.1)

We consider a positive constant $C_{10}(p)>0$ to be chosen later so that
$t_{k_{\mathrm{max}}}$ divides $C_{\ref*{cte:delta2}}\frac{n^{2}}{\mu}$, and
define

$\Delta_{3}=\Delta_{2}+\frac{n^{2}}{\mu}\quad\text{and}\quad\Delta_{2}=C_{\ref*{cte:delta2}}\frac{n^{2}}{\mu}.$
(5.2)

The following Lemma shows that with large probability there are no bad boxes
of scale $k_{\mathrm{max}}$ or larger. This will allow us to restrict our
analysis to boxes of scale at most $k_{\mathrm{max}}$. We will consider all
the boxes contained into the tessellation
$\mathbb{T}_{n}^{d}\times[0,\Delta_{3}]$, which in particular are all the
boxes intersecting the tessellation of
$\mathbb{T}_{n}^{d}\times[0,\Delta_{2}]$.

######  Lemma 5.1.

For any $\delta>0$, there exists $p_{0}=p_{0}(\delta,d)>0$ such that for all
$p<p_{0}$ and $n$ large enough

$\mathbb{P}\left(R_{k}(i,\tau)\text{ is bad}\text{ for some
}R_{k}(i,\tau)\subset\mathbb{T}_{n}^{d}\times[0,\Delta_{3}],\text{ with }k\geq
k_{\mathrm{max}}\right)\leq\rho_{1}^{2^{k_{\mathrm{max}}-3}}.$

###### Proof.

The number $\zeta_{k}$ of boxes of scale $k$ in
$\mathbb{T}_{n}^{d}\times[0,\Delta_{3}]$ is trivially bounded as

$\displaystyle\zeta_{k}\leq$
$\displaystyle\left(\frac{n}{\ell_{k}}\right)^{d}\frac{\Delta_{3}}{t_{k}}\leq(C_{\ref*{cte:delta2}}+1)n^{d+2}.$

Using Lemma 2.15 the probability that there exists a box of scale
$k_{\mathrm{max}}$ or bigger that is bad is bounded above by

$\sum_{k\geq
k_{\mathrm{max}}}\zeta_{k}\rho_{k}\leq(C_{\ref*{cte:delta2}}+1)n^{d+2}\sum_{k\geq
k_{\mathrm{max}}}\rho_{1}^{2^{k-2}}\leq
2(C_{\ref*{cte:delta2}}+1)n^{d+2}\rho_{1}^{2^{k_{\mathrm{max}}-2}}.$

Using the value of $k_{\mathrm{max}}$ and the fact that $\rho_{1}$ can be made
arbitrarily small by taking $p$ small concludes the proof. ∎

###  5.2 The coupling

Recall the map $\Psi_{t}$ introduced in Section 4 which maps $X_{t}$ into
$\overline{X}_{t}$. In order to define the coupling of the two processes, we
will use a different map $\Phi_{t}$. The idea is that our new map will be
equal to $\Psi_{t}$ in good parts of the environment, but when the walker
enters the enlargement of a bad box, we will stop changing $\Phi_{t}$ and will
keep it “frozen” until the walkers exit the enlargements of all bad boxes. The
idea is that in the enlargement of bad boxes we want to couple the graphs in a
large region around the walkers so that if the walkers enter a bad box, then
they do so with their graphs coupled within the box. We stop updating
$\Phi_{t}$ because when $\Phi_{t}$ changes many edges uncouple.

More precisely, given a time $t$, denote with

$\overline{s}_{t}=\sup\\{s\leq t\,:\,(X_{s},s)\text{ is inside a
$k_{\mathrm{max}}$-great box}\\}$

the last time before $t$ the walker is in a $k_{\mathrm{max}}$ great box. We
will consider the new map $\Phi_{t}$ defined as

$\Phi_{t}=\Psi_{\overline{s}_{t}}.$

We will show that this change of map actually will not create any problems; in
fact, we will show that $\Phi_{t}\equiv\Psi_{t}$ for all $t$ because in the
way we construct the coupling, when the walkers are in the enlargement of a
bad box, we will succeed in applying identity coupling, hence the translation
map remains constant. So, the introduction of $\Phi_{t}$ here is a formalism
so that the coupling procedure is well defined. This will imply that our
application of identity coupling later on will be successful, which in turn
implies that $\Phi_{t}\equiv\Psi_{t}$.

As soon as the second phase begins we check whether the box $R_{1}(i,0)$, such
that $(X_{0},0)\in R_{1}^{\mathrm{core}}(i,0)$, is $k_{\mathrm{max}}$-great
(the reason we do this will be clarified later, see Remark 5.9). If that is
the case then we can begin the coupling procedure relative to the second
phase. The coupling is composed of two parts: the coupling of the graphs (that
is, the coupling of $\eta_{t}^{\star}$ and $\overline{\eta}_{t}^{\star}$) and
the coupling of the walkers.

####  5.2.1 Coupling of the graphs

We let the process $\\{\eta_{t}^{\star}\\}_{t\geq 0}$ evolve. Denote with
$\mathcal{C}_{v}(t)$ (resp., $\overline{\mathcal{C}}_{v}(t)$) the cluster that
contains vertex $v$ at time $t$ in the process $\eta^{\star}_{t}$ (resp.,
$\overline{\eta}^{\star}_{t}$). When an update $(s,U^{\prime},U)$ occurs at an
edge $e$ in $\eta_{s}^{\star}$ we update the process
$\overline{\eta}^{\star}_{s}$ as follows.

  * •

If the update is a $\star$-update we refrain from looking at $U$ and instead
simply set $\eta^{\star}_{s}(e)=\star$ and
$\overline{\eta}^{\star}_{s}(\Phi_{s}(e))=\star$.

  * •

If the update is not a $\star$-update we must check in both configurations
$\eta^{\star}_{s}$ and $\overline{\eta}^{\star}_{s}$ whether $e$ is a cut-edge
or not. We do this by looking at the connected components of the endpoints
$v_{1},v_{2}$ of the edge $e$. If an edge $e^{\prime}$ is such that
$\eta^{\star}_{s}(e^{\prime})=\star$ and $e^{\prime}$ is incident to a vertex
in $\mathcal{C}_{v_{1}}(s)\cup\mathcal{C}_{v_{2}}(s)$, we sample its current
status, open or closed, according to its last update. Note that this last
update is itself a tuple $(\overline{s},\overline{U}^{\prime},\overline{U})$,
so this step boils down to checking the value of $\overline{U}$. If
$\overline{\eta}^{\star}_{s}(\Phi_{s}(e^{\prime}))=\star$ we set
$\overline{\eta}^{\star}_{s}(\Phi_{s}(e^{\prime}))=\eta^{\star}_{s}(e^{\prime})$
as well. We continue this procedure until the components of $v_{1}$ and
$v_{2}$ have been fully explored in $\eta^{\star}_{s}$ and proceed analogously
for the process $\overline{\eta}^{\star}_{s}$ until the components of
$\Phi_{s}(v_{1})$ and $\Phi_{s}(v_{2})$ have been fully explored. A potential
disagreement $\eta^{\star}_{s}(e)\neq\overline{\eta}^{\star}_{s}(\Phi_{s}(e))$
can happen only if, by revealing the components of $v_{1}$, $v_{2}$,
$\Phi_{s}(v_{1})$ and $\Phi_{s}(v_{2})$, we find that $e$ is a cut-edge in
$\eta^{\star}_{s}$ but $\Phi_{s}(e)$ is not a cut-edge in
$\overline{\eta}^{\star}_{s}$, or vice-versa.

In this way edges whose status is $\star$ can always be coupled equivalently
whereas non $\star$-updates cause the reveal of the status of other edges,
potentially creating disagreements between the two configurations.

######  Remark 5.2 (Momentaneous change of coupling).

At some times we will carry out a different coupling of the environment. This
will be done by simply introducing another map $\tilde{\Phi}$ of the
environments, and the coupling of the graphs will go as described above with
$\Phi_{t}$ replaced with $\tilde{\Phi}$ until we specify that $\Phi_{t}$ is
again the map to be used.

####  5.2.2 Coupling of the walkers

During this discussion the reader should refer to Figure 3.

Figure 3: In red the bad boxes, in blue their enlargement, in black the
tessellation and the walker’s trajectory. In bad boxes there is no control
over the displacement of the walker, whereas in good boxes, the walker always
leaves the box from its time boundary. Whenever the walker enters the
enlargement of a bad box we start doing identity coupling, otherwise, in great
boxes, if a SRWM occurs we do a simple random walk coupling, if not we keep
doing identity coupling.

Our goal is to define a coupling that can bring the walkers together. For this
we will use the multi-scale tessellation. The coupling of the walkers will be
composed of two different couplings. When the walker $X_{s}$ enters the core
of a great box $R_{1}^{\mathrm{core}}(i,\tau)$, we will try to take advantage
of the nice environment that a great box provides to perform a coupling that
we refer to as a simple random walk moment. This coupling aims to change the
distance between the walkers, so that eventually the walkers may find
themselves at the same site.

On the other hand, whenever $X_{s}$ is not in a great box, then we do not have
a good enough control on the environment around the walker to do a simple
random walk moment. In such cases, we will just resort to a simple identity
coupling that keeps the distance between the walkers unchanged. An identity
coupling will only be able to be performed if the environment around the
walkers are the same. For this, we define the following event:

$\mathcal{B}_{t}^{\prime}=\left\\{\forall e\in
E(B_{\ell/2}^{\infty}(X_{t})),\,{\eta}_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Phi_{t}(e))\right\\}.$
(5.3)

If $B_{s}^{\prime}$ holds for all $s\in(s_{1},s_{2})$, then in this time
interval the walkers can perform the same jumps and not change their relative
distance. In other words, we identity coupling is successful. In fact if the
environment around the walkers is the same (as a matter of fact we only need
the environments to agree on a ball of radius $1$ around the walkers), by
doing identity coupling the walkers are able to perform the same jumps.

So the proof is now split into three steps. Since $\Phi_{t}$ does not change
when the walker enters the $2$-enlargement of a bad box, we will show in
Section 5.3 that when $\Phi_{t}$ does not change the graph couples. Next, we
deal with showing that identity coupling can be successfully implemented as
the walker enters the $2$-environment of a bad box (i.e., when the walker is
not in a great box). This is carried out in Section 5.4. Then in Section 5.5
we deal with the simple random walk moments.

###  5.3 Coupling of the graphs with $\Phi_{t}$ unchanged

Given $I\subset\mathbb{Z}^{d}$ and $k\geq 1$, let

$\mathcal{S}_{k}(I)=\bigcup_{i\in
I}S_{k}(i)\quad\text{and}\quad\mathcal{S}_{k}^{\diamond}(I)=\bigcup_{i\in
I}S_{k}^{\diamond}(i),$

for any
$\diamond\in\left\\{\mathrm{core},\mathrm{enl1},\mathrm{enl2}\right\\}$.
Recall the value $m$ in the definition of $\ell_{k}$ in (2.2). Recall also
$\overline{t}_{k}$ from (2.6). Then, for $k\geq 2$, we define

$\overline{t}_{k}=\frac{6t_{k}}{(k-1)^{2}m}.$ (5.4)

We start this section showing that the graph gets coupled in regions of good
boxes if $\Phi_{t}$ does not change.

######  Lemma 5.3 (Graphs couple in good boxes).

Let $m$ be large enough, and then let $\ell$ be large enough with respect to
$m$. Let $R_{k}(i,\tau)$ be a good box, and let $s_{1}$ be any time instance
so that $[s_{1},s_{1}+2\overline{t}_{k}]\subset T_{k}(\tau)$. If $\Phi_{t}$
does not change during $[s_{1},s_{1}+2\overline{t}_{k}]$, then

$\text{there exists $t\in[s_{1},s_{1}+2\overline{t}_{k}]$ such that
}\eta_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Phi_{t}(e))\text{ for all
$e\in S_{k}(i)$}.$ (5.5)

###### Proof.

If $k=1$ then the proof follows since each edge of $S_{k}(i)$ receives only
$\star$-updates and gets updated at least once during
$[s_{1},s_{1}+2\overline{t}_{k}]$. For $k\geq 2$, we assume that the statement
of the lemma holds up to scale $k-1$. Let $s_{2}=\max T_{k}(\tau)$. Let
$\tau^{\prime}$ be the first time index such that
$\tau^{\prime}t_{k-1}\in[s_{1},s_{2}]$ and all boxes
$R_{k-1}(\cdot,\tau^{\prime})\subset R_{k}(i,\tau)$ are good. Let $I$ be the
set of indices containing all $(k-1)$-boxes that are inside $S_{k}(i)$; more
precisely,

$I=\left\\{i^{\prime}\colon S_{k-1}(i^{\prime})\subset S_{k}(i)\right\\}.$

Then, by induction, by time $\tau^{\prime}t_{k-1}+2\overline{t}_{k-1}$ we
obtain that $\mathcal{S}_{k-1}(I)=S_{k}(i)$ has been coupled.

Now it remains to show that $\tau^{\prime}t_{k-1}+2\overline{t}_{k-1}\leq
s_{1}+2\overline{t}_{k}$. Note that since $R_{k}(i,\tau)$ is a good box, there
exists $\widehat{\imath},\widehat{\tau}$ such that all $(k-1)$-bad boxes
contained in $R_{k}(i,\tau)$ are contained in
$R_{k-1}^{\mathrm{enl1}}(\widehat{\imath},\widehat{\tau})$. Since the amount
of time spanned by the enlargement at scale $k-1$ is $9t_{k-1}$, we obtain
that $\tau^{\prime}t_{k-1}\leq s_{1}+9t_{k-1}+t_{k-1}$, where the last
$t_{k-1}$ is to account for the possibility that $s_{1}$ is not a multiple of
$t_{k-1}$. Hence, using the notation $a_{+}=\max\left\\{a,1\right\\}$ for
consistency with the case $k=2$, and noting that
$\overline{t}_{1}\leq\frac{6t_{1}}{(k-2)^{2}_{+}m}$ provided $\ell$ is made
large enough once $m$ has been fixed, we have

$\displaystyle\tau^{\prime}t_{k-1}+2\overline{t}_{k-1}$ $\displaystyle\leq
s_{1}+10t_{k-1}+2\overline{t}_{k-1}$ $\displaystyle\leq
s_{1}+t_{k-1}\left(10+2\frac{6}{(k-2)^{2}_{+}m}\right)$
$\displaystyle=s_{1}+\frac{t_{k}}{m(k-1)^{2}}\left(10+\frac{12}{(k-2)^{2}_{+}m}\right)$
$\displaystyle=s_{1}+\frac{\overline{t}_{k}}{6}\left(10+\frac{12}{(k-2)^{2}_{+}m}\right)$
$\displaystyle\leq s_{1}+2\overline{t}_{k}.$

∎

Recall the definition of $S_{1}^{\mathrm{inn}}(i)$ from (2.7). For $k\geq 2$,
define

$S_{k}^{\mathrm{inn}}(i)=\bigcup_{j\colon S_{k-1}^{\mathrm{enl2}}(i)\subset
S_{k}(j)}S^{\mathrm{core}}_{k-1}(j).$ (5.6)

For a set of indices $I$, we write

$\mathcal{S}_{k}^{\mathrm{inn}}(I)=\bigcup_{j\in I}S_{k}^{\mathrm{inn}}(j).$

Note that by taking $m$ large enough, then
$\mathcal{S}_{k}^{\mathrm{core}}(I)\subset\mathcal{S}_{k}^{\mathrm{inn}}(I)\subset\mathcal{S}_{k}(I)$.
We start with a simple result about the connected component of a vertex.

######  Lemma 5.4.

Let $m\geq 2$ and let $\ell$ be large enough with respect to $m$. Let
$I\subset\mathbb{Z}^{d}$ be a set of indices, $k\geq 1$ a scale and $\tau\geq
1$ a time index such that $R_{k}(i,\tau)$ is a good box for all $i\in I$.
Then, for any $v\in\mathcal{S}_{k}^{\mathrm{inn}}(I)$ and any $t\in
T_{k}(\tau)$, the connected component of $v$ is contained in
$B_{5\ell_{k}/m}^{\infty}(v)$, where we recall that $B^{\infty}_{r}(v)$ is the
$L_{\infty}$ ball of radius $r$ around $v$.

###### Proof.

For $k=1$, the result follows by the fact that components have size at most
$\log^{2}\ell$ in good $1$-boxes when $\tau\geq 1$, and $\ell$ is large enough
so $\log^{2}\ell\leq 5\ell/m$. For $k\geq 2$, let $(i^{\prime},\tau^{\prime})$
be such that $v\in S_{k-1}^{\mathrm{core}}(i^{\prime})$ and $t\in
T_{k-1}(\tau^{\prime})\subset T_{k}(\tau)$; there could be more than one
choice for $\tau^{\prime}$, it is irrelevant which one we pick. Note that
since $v\in\mathcal{S}_{k}^{\mathrm{inn}}(I)$

$S_{k-1}(i^{\prime})\subset S_{k-1}^{\mathrm{enl2}}(i^{\prime})\subset
S_{k}(i)\text{ for some $i\in I$}.$

If $R_{k-1}(i^{\prime},\tau^{\prime})$ is good, then the connected component
of $v$ is contained in $B_{5\ell_{k-1}/m}(v)\subset B_{5\ell_{k}/m}(v)$ by
applying the induction hypothesis at scale $k-1$ and set of indices
$\left\\{i^{\prime}\right\\}$. Otherwise, note that by Remark 2.17 we have
that $R_{k-1}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$ contains all bad
boxes in $R_{k}(i,\tau)$. If the connected component of $v$ is contained in
$S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ then it is contained in
$B_{5\ell_{k-1}}(v)\supset S_{k-1}^{\mathrm{enl1}}(i^{\prime})$. Since
$5\ell_{k-1}=5\frac{\ell_{k}}{m(k-1)^{2}}\leq\frac{5\ell_{k}}{m}$ the lemma
holds on this case as well. In the final case, when the connected component of
$v$ is not contained in $S_{k-1}^{\mathrm{enl1}}(i^{\prime})$, it may sound
contradictory but we can get an even smaller bound for the component of $v$.
The reason is that there must exist $i^{\prime\prime}$ such that $v$ is at the
same component of a vertex $u$ with $u\in
S_{k-1}^{\mathrm{core}}(i^{\prime\prime})$ and
$S_{k-1}^{\mathrm{core}}(i^{\prime\prime})\cap
S_{k-1}^{\mathrm{enl1}}(i^{\prime})=\emptyset$ but
$S_{k-1}(i^{\prime\prime})\cap
S_{k-1}^{\mathrm{enl1}}(i^{\prime})\neq\emptyset$. But since $(u,t)$ is in the
box $R_{k-1}(i^{\prime\prime},\tau^{\prime})$, and
$S_{k-1}(i^{\prime\prime})\subset S_{k-1}^{\mathrm{enl2}}(i^{\prime})\subset
S_{k}(i)$, we have that $R_{k-1}(i^{\prime\prime},\tau^{\prime\prime})$ is a
good box. Thus, by induction we obtain that the connected component of $v$ is
inside $B_{5\ell_{k-1}/m}(u)\subset B_{10\ell_{k-1}/m}(v)$. Since
$10\frac{\ell_{k-1}}{m}=10\frac{\ell_{k}}{m^{2}(k-1)^{2}}\leq\frac{5\ell_{k}}{m}$
for all $k$ as long as $m\geq 2$, the proof is completed. ∎

With the help of the above lemma, we can show that the graph cannot uncouple
in regions surrounded by good boxes.

######  Lemma 5.5 (Graphs remain coupled if $\Phi_{t}$ does not change).

Let $m$ be large, and let $\ell$ be large enough with respect to $m$. Let
$R_{k}(i,\tau)$ be a good box, and let $s_{1}<s_{2}$ with $s_{1},s_{2}\in