T_{k}(\tau)$ and $s_{1}\leq(\tau+1)t_{k}$. If $\Phi_{t}$ does not change
during $t\in[s_{1},s_{2}]$ and

$\eta_{s_{1}}^{\star}(e)=\overline{\eta}_{s_{1}}^{\star}(\Phi_{s_{1}}(e))\text{
for all $e\in E(S_{k}(i))$},$

then $\eta_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Phi_{t}(e))$ for all
$e\in E(S_{k}^{\mathrm{inn}}(i))$ and all $t\in[s_{1},s_{2}]$.

###### Proof.

For $k=1$ the lemma is obvious, since for any $e\in E(S_{k}(i))$, $e$ only
receives $\star$-updates during $T_{k}(\tau)$. Therefore,
$\eta_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Phi_{t}(e))$ for all
$t\in[s_{1},s_{2}]$. For $k\geq 2$, assume the lemma holds up to scale $k-1$.
Let

$\mathcal{T}=\left\\{\tau^{\prime}\colon
T_{k-1}(\tau^{\prime})\cap[s_{1},s_{2}]\neq\emptyset\text{ and
}T_{k-1}(\tau^{\prime})\subset T_{k}(\tau)\right\\}.$

Let $\tau_{1}=\min\mathcal{T}$. Note that either

$s_{1}\in T_{k-1}^{\mathrm{core}}(\tau_{1})\quad\text{or}\quad s_{1}\in
T_{k-1}^{\mathrm{core}}(\tau_{1}-1),$ (5.7)

where the latter happens when $s_{1}$ is near the starting time of
$T_{k}(\tau)$. Because $s_{1}$ cannot be near the ending time of $T_{k}(\tau)$
due to the condition $s_{1}\leq(\tau+1)t_{k}$, we obtain that $\mathcal{T}$ is
not empty. We will first show that

$S_{k-1}^{\mathrm{inn}}(j)$ is coupled during $[s_{1},s_{2}]$ for all $j$ such
that $S_{k-1}(j)\subset S_{k}(i)$ $\displaystyle\text{and for which
$R_{k-1}(j,\tau^{\prime})$ is good for all $\tau^{\prime}\in\mathcal{T}$}.$
(5.8)

To see this, let $r_{1}=\sup T_{k-1}(\tau_{1})$ and note that $r_{1}\geq
s_{1}+t_{k-1}$ because of (5.7). Now, induction gives that
$S_{k-1}^{\mathrm{inn}}(j)$ remains coupled up to time $r_{1}$. We would like
to reapply the induction hypothesis on the box $S_{k-1}(j)$ in the next time
step, but for this we need $S_{k-1}(j)$ to be coupled, not only
$S_{k-1}^{\mathrm{inn}}(j)$. Thus, we first apply Lemma 5.3 from time
$r_{1}-2\overline{t}_{k-1}$ to obtain that there exists a time
$r_{1}^{\prime}\in[r_{1}-2\overline{t}_{k-1},r_{1}]$ for which the whole of
$S_{k-1}(j)$ is coupled. Let $\tau_{2}$ be such that $r_{1}^{\prime}\in
T_{k-1}^{\mathrm{core}}(\tau_{2})$ and note that $\tau_{2}\geq\tau_{1}+1$.
Thus, we repeat the induction hypothesis and the application of Lemma 5.3 to
obtain a sequence of $\tau_{\iota}$, $r_{\iota}$ and $r_{\iota}^{\prime}$
until a certain value
$r_{\iota}^{\prime}\in[s_{2}-2\overline{t}_{k-1},s_{2}]$. At that time, the
induction hypothesis gives that $S_{k-1}^{\mathrm{inn}}(j)$ is coupled at time
$s_{2}$, establishing (5.8).

Now we turn to establish the lemma. If $R_{k}(i,\tau)$ has no bad $(k-1)$-box
intersecting the time interval $[s_{1},s_{2}]$, then (5.8) and the fact that
$(k-1)$-boxes overlap give that $\bigcup_{j\colon S_{k-1}(j)\subset
S_{k}(i)}S_{k-1}^{\mathrm{inn}}(j)\supset S_{k}^{\mathrm{inn}}(i)$ is coupled
during $[s_{1},s_{2}]$.

Now assume that $R_{k}(i,\tau)$ contains bad $(k-1)$-boxes that intersect
$[s_{1},s_{2}]$. From Remark 2.17, there exists
$R_{k-1}(i^{\prime},\tau^{\prime})$ so that all $(k-1)$-bad boxes contained in
$R_{k}(i,\tau)$ are contained in
$R_{k-1}^{\mathrm{enl1}}(i^{\prime},\tau^{\prime})$. Let

$\mathcal{J}=\left\\{j\colon S_{k-1}(j)\subset S_{k}(i)\text{ and
}S_{k-1}(j)\not\subset S_{k-1}^{\mathrm{enl1}}(i^{\prime})\right\\},$

and note that $R_{k-1}(j,\tau^{\prime\prime})$ is good for all
$j\in\mathcal{J}$ and $\tau^{\prime\prime}\in\mathcal{T}$. Therefore, (5.8)
gives that $S_{k-1}^{\mathrm{inn}}(j)$ is coupled during $[s_{1},s_{2}]$ for
all $j\in\mathcal{J}$. The remaining of the proof is split into two cases.
First assume that $S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ is separated from
infinity by $\mathcal{J}$, which means that any path from
$S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ to the outside of $S_{k}(i)$ must enter
$S_{k-1}^{\mathrm{core}}(j)$ for some $j\in\mathcal{J}$. In fact, letting

$\mathcal{J}^{\prime}=\left\\{j\in\mathcal{J}\colon
S_{k-1}^{\mathrm{core}}(j)\subset
S_{k-1}^{\mathrm{enl1}}(i^{\prime})\right\\},$

we get that the path must enter $S_{k-1}^{\mathrm{core}}(j)$ for some
$j\in\mathcal{J}^{\prime}$. Besides, Lemma 5.4 gives that for all
$v\in\mathcal{S}_{k-1}^{\mathrm{inn}}(\mathcal{J})$ and all $s\in
T_{k-1}^{\mathrm{enl1}}(\tau^{\prime})$ we have that the connected component
of $v$ is contained in $B_{5\ell_{k-1}/m}^{\infty}(v)$. Therefore, all
connected components intersecting $S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ must
be contained in $\bigcup_{v\in
S_{k-1}^{\mathrm{enl1}}(i^{\prime})}B_{5\ell_{k-1}/m}^{\infty}(v)$, which is a
spatial region contained in the interior of
$\mathcal{S}_{k}^{\mathrm{inn}}(J^{\prime})$. Therefore, since
$\mathcal{S}_{k-1}^{\mathrm{inn}}(J)\supset\mathcal{S}_{k-1}^{\mathrm{inn}}(J^{\prime})$
remains coupled throughout $[s_{1},s_{2}]$ by (5.8), non-$\star$ updates
inside $S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ cannot uncouple the graph.

Turning to the second case, we assume that
$S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ is not separated from infinity by
$\mathcal{J}$. This means that $S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ is so
close to the boundary of $S_{k}(i)$ that it does not intersect
$S_{k}^{\mathrm{inn}}(i)$. More formally, for any $v\in
S_{k-1}^{\mathrm{enl1}}(i)$ we have that $B_{10\ell_{k-1}}^{\infty}(v)$ cannot
be contained in $S_{k}(i)$. But this implies that any $i^{\prime\prime}$ with
$S_{k-1}^{\mathrm{core}}(i^{\prime\prime})\subset
S_{k-1}^{\mathrm{enl1}}(i^{\prime})$ we have that
$S_{k-1}^{\mathrm{enl2}}(i^{\prime\prime})\not\subset
S_{k}^{\mathrm{inn}}(i)$. Therefore, applying (5.8) to the boxes in
$\mathcal{J}$ already gives that $S_{k}^{\mathrm{inn}}(i)$ is coupled during
$[s_{1},s_{2}]$. ∎

###  5.4 Identity coupling

We prove that, by doing identity coupling, as long as the particle $X_{t}$ is
in a point $(v,t)\in\mathbb{T}_{n}^{d}\times\mathbb{R}^{+}$ in space-time that
is part of a $1$-box $R_{1}(\cdot,\cdot)$ that is good, it is always possible
to keep the distance between $X_{t}$ and $\overline{X}_{t}$ constant. Recall
the event $\mathcal{B}^{\prime}_{t}$ from (5.3), the event $\mathcal{B}_{t}$
from (4.1), and the definition of the spatial core of a box in (2.10). We will
need a weaker version of $\mathcal{B}^{\prime}_{t}$ which we define as

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

Recall that in the second phase we assume that $R_{0}(0,0)$ is a
$k_{\mathrm{max}}$-great box and $\mathcal{B}_{0}$ holds; we do not restate
these conditions on the lemmas.

######  Lemma 5.6 (Identity coupling succeeds in good boxes).

Let $s_{1}$ be a time so that $\mathcal{B}_{s_{1}}^{\prime\prime}$ holds and
$(X_{s_{1}},s_{1})\in R_{1}^{\mathrm{s\mathchar 45\relax core}}(i,\tau)$ with
$R_{1}(i,\tau)$ being a good box. Let $s_{2}\in T_{1}(\tau)$, $s_{2}\geq
s_{1}$. If we attempt to do identity coupling for the entire time interval
$[s_{1},s_{2}]$, then the coupling succeeds and $\Psi_{s_{1}}\equiv\Psi_{t}$
for all $t\in[s_{1},s_{2}]$.

###### Proof.

Let $B$ be the $L_{\infty}$ ball of radius $\ell/3$ around $X_{s_{1}}$; $B$ is
a fixed region in space, not changing in time. The edges in $E(B)$ are coupled
at time $s_{1}$ since $\mathcal{B}^{\prime\prime}_{s_{1}}$ holds. By Lemma
2.22 the walker never leaves $S_{1}(i)\subset B$ during the time interval
$[s_{1},s_{2}]$; if $s_{1}\leq\overline{t}_{1}$, then we know that the
component of the walker is at most $\log^{2}\ell$ since $\mathcal{B}_{0}$
holds and the box $R_{1}(0,0)$ is $k_{\mathrm{max}}$-great by the properties
of the second phase. Since there is no non-$\star$ update in $E(B)$ during
$[s_{1},s_{2}]$, $B$ remains coupled throughout and identity coupling is
successful. ∎

The lemma below is a composition of the previous lemma when the walker
traverses a sequence of good $1$-boxes. We assume that the stronger event
$\mathcal{B}_{t}^{\prime}$ holds at the start time to be able to guarantee
that $\mathcal{B}_{t}^{\prime\prime}$ holds during the entire time interval
covered by the lemma.

######  Lemma 5.7 (Identity coupling succeeds in sequences of good boxes).

Let $s_{1}$ be a time so that $\mathcal{B}_{s_{1}}^{\prime}$ holds. Let
$s_{2}>s_{1}$ be such that during $[s_{1},s_{2}]$ the walker only traverses
$1$-boxes that are good. Then, if we attempt to do identity coupling for the
entire time interval $[s_{1},s_{2}]$, the coupling succeeds,
$\mathcal{B}^{\prime\prime}_{t}$ holds and $\Psi_{s_{1}}\equiv\Psi_{t}$ for
all $t\in[s_{1},s_{2}]$. Moreover, $\mathcal{B}^{\prime}_{t}$ holds for all
$t\in[s_{1}+2\overline{t}_{1},s_{2}]$.

###### Proof.

Let $R_{1}(i,\tau)$ be the box the walker is in its core at time $s_{1}$.
Since $R_{1}(i,\tau)$ is a good box, Lemma 5.6 gives that identity coupling
works up to the end of $T_{1}(\tau)$ and Lemma 5.3 gives that $S_{1}(i)$
couples at some time during $[s_{1},s_{1}+2\overline{t}_{1}]$. Moreover, for
any $t\in[s_{1},s_{1}+2\overline{t}_{1}]$, $\mathcal{B}_{t}^{\prime\prime}$
holds since $\mathcal{B}_{s_{1}}^{\prime}$ holds. For $t\in
T_{1}(\tau)\cap[s_{1}+2\overline{t}_{1},\infty)$ we have that
$\mathcal{B}^{\prime}_{t}\subset\mathcal{B}^{\prime\prime}_{t}$ holds by Lemma
5.5. Hence, if $R_{1}(i^{\prime},\tau^{\prime})$ is the box whose core the
walker is in when exitting $R_{1}(i,\tau)$, we can apply Lemma 5.6 again to
show that identity coupling succeeds. Repeating this argument over and over
again establishes the lemma. ∎

Now we analyze what happens in the neighborhood around a bad $1$-box,
supposing that the walker enters the 2-enlargement of that box. Two things can
happen, either the walker enters the 2-enlargement of the box from the space
boundary $\partial_{\mathrm{s}}R_{1}^{\mathrm{enl2}}(\cdot,\cdot)$ or it
enters from the time boundary
$\partial_{\mathrm{t}}^{-}R_{1}^{\mathrm{enl2}}(\cdot,\cdot)$. If it is from
the space boundary, then the walker does not get too close to the bad box and
$\mathcal{B}_{t}^{\prime}$ would still be verified for all $t$. Moreover, as
long as the walker is in the 2-enlargement, identity coupling can be applied
successfully. In the other case, if the walker enters from the time boundary,
then it could eventually reach the bad box but the environment in the
2-enlargement of the bad box will be coupled before that. In particular, the
environments will be coupled at all times in
$T_{1}^{\mathrm{enl1}}(\cdot,\cdot)$ thanks to the abundance of
$\star$-updates in $T_{1}^{\mathrm{enl2}}(\cdot,\cdot)\setminus
T_{1}^{\mathrm{enl1}}(\cdot,\cdot)$. This reasoning gives that the relative
distance between the walkers does not change and the graphs remain coupled in
$E(S_{1}^{\mathrm{enl2}}(i))$ when the walker cross a bad box of scale $1$.

In the lemma below we will require $m$ to be large enough so that the
following holds:

For any $(k,i,\tau)$ and any $(i^{\prime},\tau^{\prime})$ so that
$R_{k+1}^{\mathrm{core}}(i^{\prime},\tau^{\prime})$ intersects $R_{k}(i,\tau)$
we obtain that $R_{k+1}(i^{\prime},\tau^{\prime})$ contains all $k$-boxes that
intersects $R_{k}^{\mathrm{enl2}}(i,\tau)$, and
$S_{k+1}^{\mathrm{inn}}(i^{\prime})$ contains $S_{k}^{\mathrm{enl2}}(i)$.
(5.10)

######  Lemma 5.8 (Identity coupling in enlargement of bad boxes).

Let $m$ be large enough so that (5.10) holds. Let $R_{k}(i,\tau)$ be a bad box
of scale $k$ such that $R_{k+1}(i^{\prime},\tau^{\prime})$ is good for some
$(k+1)$-box for which $R_{k+1}^{\mathrm{core}}(i^{\prime},\tau^{\prime})\cap
R_{k}(i,\tau)\neq\emptyset$. Denote with $\tau_{k}^{+}=\max
T_{k}^{\mathrm{enl2}}(\tau)$, and with $\tau_{k}^{-}=\min
T_{k}^{\mathrm{enl2}}(\tau)$. Let $s_{c}$ be a time at which the walker enters
$R_{k}^{\mathrm{enl2}}(i,\tau)$ so $X_{s_{c}}\in S_{k}^{\mathrm{enl2}}(i)$ but
$X_{s_{c}-}\not\in S_{k}^{\mathrm{enl2}}(i)$ or $s_{c}=\tau_{k}^{-}$. Let
$s_{e}=\inf\\{t\in(s_{c},\tau_{k}^{+}]\colon X_{t}\notin
S_{k}^{\mathrm{enl2}}(i)\\}$ the first time the walker exits
$R_{k}^{\mathrm{enl2}}(i,\tau)$ after $s_{c}$; we take the convention that
$s_{e}=\tau_{k}^{+}$ if $X_{t}\in S_{k}^{\mathrm{enl2}}(i)$ for all
$t\in[s_{c},\tau_{k}^{+}]$. Thus

$\text{if $\mathcal{B}_{s_{c}}^{\prime}$ holds, then for all
$t\in[s_{c},s_{e}]$ $\Psi_{t}$ remains unchanged and
$\mathcal{B}^{\prime\prime}_{t}$ holds};$ (5.11)

consequently, identity coupling succeeds during $[s_{c},s_{e}]$. Moreover,

$\text{if $s_{c}>\tau_{k}^{-}$, the walker does not enter
$R_{k}^{\mathrm{enl1}}(i,\tau)$}.$ (5.12)

Ultimately, letting $\mathcal{J}=\left\\{j\colon S_{k}(j)\cap
S_{k}^{\mathrm{enl2}}(i)\neq\emptyset\right\\}$,

$\displaystyle\text{if $s_{c}=\tau_{k}^{-}$, then
}\eta_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Phi_{t}(e))\text{ for all
$e\in E(\mathcal{S}_{k}^{\mathrm{inn}}(J))$}$ $\displaystyle\text{and all
$t\in[s_{c},s_{e}]$ with $t\geq\min T_{k}^{\mathrm{enl1}}(\tau)$}.$ (5.13)

The proof uses induction on $k$, so we treat the case $k=1$ separately.

###### Proof of Lemma 5.8 for $k=1$.

We start with the case $s_{c}>\tau_{1}^{-}$, meaning that the walker entered
the $2$-enlargement of the bad box from
$\partial_{\mathrm{s}}R_{1}^{\mathrm{enl2}}(i,\tau)$. We need to establish
(5.11) and (5.12) in this case. We establish (5.12) by showing that the walker
never gets closer than $12\ell$ from $S_{1}^{\mathrm{enl1}}(i)$. To see this,
from (5.10) we have that $R_{2}(i^{\prime},\tau^{\prime})$ contains the
$2$-enlargement of $R_{1}(i,\tau)$, and $R_{2}(i^{\prime},\tau^{\prime})$ is a
good box. Moreover, Remark 2.17 gives that the $1$-enlargement of
$R_{1}(i,\tau)$ contains all bad $1$-boxes inside
$R_{2}(i^{\prime},\tau^{\prime})$, and Lemma 2.23 gives that the distance
between the walker and $S_{1}^{\mathrm{enl1}}(i)$ is at least $12\ell$,
establishing (5.12). To establish (5.11), note that the walker only traverses
good boxes during $[s_{c},s_{e}]$, so (5.11) follows from 5.7.

Now we consider the case $s_{c}=\tau_{1}^{-}$, and need to establish (5.11)
and (5.13). The idea in this case is to use the time interval between $s_{c}$
and $\min T_{1}^{\mathrm{enl1}}(\tau)$, which is large enough for the graphs
to couple. In fact, applying Lemma 5.3 to the box
$R_{2}(i^{\prime},\tau^{\prime})$ from time $s_{c}$, we obtain a time
$s\in[s_{c},s_{c}+2\overline{t}_{2}]$ so that $S_{2}(i^{\prime})$ is coupled.
From this time onwards Lemma 5.5 gives that
$S_{2}^{\mathrm{inn}}(i^{\prime})\supset S_{1}^{\mathrm{enl2}}(i)$ remains
coupled up to time $s_{e}$. From Lemma 2.22 we know that the walker does not
leave $S_{2}^{\mathrm{inn}}(i^{\prime})$ during $[s_{c},s_{e}]$. So if
identity coupling succeeds up to time $s_{c}+2\overline{t}_{2}$, then it
succeeds up to time $s_{e}$. Moreover, note that
$2\overline{t}_{2}=12t_{2}/m=12t_{1}$ is smaller than the distance between
$s_{c}$ and $\min T_{1}^{\mathrm{enl1}}(\tau)$, which is $15t_{1}$. So
$S_{2}^{\mathrm{inn}}(i^{\prime})$ couples before the walker can enter
$R_{1}^{\mathrm{enl1}}(i,\tau)$ and (5.13) is established.

It remains to show that the coupling succeeds and
$\mathcal{B}_{t}^{\prime\prime}$ holds for all
$t\in[s_{c},s_{c}+2\overline{t}_{2}]$, completing the proof of (5.11). For
this, we only need to note that during this time interval the walker only
traverses good $1$-boxes, so (5.11) follows from Lemma 5.7. ∎

###### Proof of Lemma 5.8 for $k\geq 2$.

We have already established the case $k=1$. Now we proceed via induction.
Assume all claims of the lemma are proved up to scale $k-1$. Let
$R_{k}(i,\tau)$ be a bad box and $R_{k+1}(i^{\prime},\tau^{\prime})$ as in the
statement of the lemma be a good box. All bad boxes in
$R_{k+1}(i^{\prime},\tau^{\prime})$ are contained in
$R_{k}^{\mathrm{enl1}}(i,\tau)$.

We first prove the case $s_{c}>\tau_{k}^{-}$, which requires establishing
(5.11) and (5.12). In this case we use the same argument as in the case $k=1$;
that is, (5.12) follows from Lemma 2.23. To show that identity coupling can be
performed and $\mathcal{B}_{t}^{\prime\prime}$ holds, notice that if at time
$s_{c}$ the walker is inside a bad box
$R_{k^{\prime\prime}}(i^{\prime\prime},\tau^{\prime\prime})$ for some
$k^{\prime\prime}<k$, then since $R_{1}(0,0)$ is $k_{\mathrm{max}}$-great, we
have that in a previous time the walker was in the boundary of
$R_{k^{\prime\prime}}^{\mathrm{enl2}}(i^{\prime\prime},\tau^{\prime\prime})$.
If there are more than one tuple
$(k^{\prime\prime},i^{\prime\prime},\tau^{\prime\prime})$ satisfying the
property above, we take the one with the largest $k^{\prime\prime}$ (breaking
ties arbitrarily if there still are more than one such tuples). Since the
walker must have entered the $2$-enlargement
$R_{k^{\prime\prime}}^{\mathrm{enl2}}(i^{\prime\prime},\tau^{\prime\prime})$
at some time $s_{c}^{\prime\prime}$, we obtain by induction that while
traversing the bad box
$R_{k^{\prime\prime}}(i^{\prime\prime},\tau^{\prime\prime})$ identity coupling
is successful and $\mathcal{B}^{\prime}_{t}$ holds up to the end of
$T_{k^{\prime\prime}}(\tau^{\prime\prime})$, since (5.13) implies
$\mathcal{B}^{\prime}_{t}$. Therefore, when the walker leaves
$R_{k^{\prime\prime}}(i^{\prime\prime},\tau^{\prime\prime})$, we can apply the
induction hypothesis again if the walker is inside another bad box. It remains
to check that identity coupling can be performed while the walker passes
through space-time locations that belong to good boxes at all scale, in
particular, while the walker passes through good $1$-boxes. But since
$\mathcal{B}^{\prime}_{t}$ holds at that time, identity coupling succeeds by
Lemma 5.7, concluding the proof of (5.11).

We now prove the case $s_{c}=\tau_{k}^{-}$, which requires establishing (5.11)
and (5.13). Assume that $s_{e}\geq\min T_{k}^{\mathrm{enl1}}(\tau)$, otherwise
(5.11) follows from the same argument above and (5.13) is irrelevant. We can
do the same argument as for $k=1$; i.e., we show that the time interval
between $s_{c}$ and $\min T_{k}^{\mathrm{enl1}}(\tau)$ is large enough for the
graphs to couple. By Lemma 5.3 we obtain a time
$s\in[s_{c},s_{c}+2\overline{t}_{k+1}]$ so that $S_{k+1}(i^{\prime})$ is
coupled and, by Lemma 5.5, $S_{k+1}^{\mathrm{inn}}(i^{\prime})\supset
S_{k}^{\mathrm{enl2}}(i)$ remains coupled until $s_{e}$. Since Lemma 2.22
gives that the walker does not leave $S_{k+1}^{\mathrm{inn}}(i^{\prime})$
during $[s_{c},s_{e}]$, if identity coupling succeeds up to time
$s_{c}+2\overline{t}_{k+1}$, then it succeeds up to time $s_{e}$. Besides,
$2\overline{t}_{k+1}=12\frac{t_{k+1}}{k^{2}m}=12t_{k}$ is smaller than the
distance between $s_{c}$ and $\min T_{k}^{\mathrm{enl1}}(\tau)$, which is
$15t_{k}$. So $S_{k+1}^{\mathrm{inn}}(i^{\prime})$ couples before the walker
can enter $R_{k}^{\mathrm{enl1}}(i,\tau)$ and (5.13) is established. To
establish (5.11), we need to show that $\mathcal{B}_{t}^{\prime\prime}$ holds
for all $t\in[s_{c},s_{c}+2\overline{t}_{k+1}]$, but during this time the
walker only traverses good $1$-boxes, so (5.11) follows from Lemma 5.7. ∎

######  Remark 5.9.

The 2-enlargement of a bad box is chosen so that whenever the walker crosses
it, by doing identity coupling the two processes have time to couple the
environment before the walker crosses the bad box. For this exact reason we
want the first box whose core the walker is at, at the beginning of the second
phase, to be $k_{\mathrm{max}}$-great, so we know that the walker does not
start inside the enlargement of a bad box, meaning that if the walker
encountersa bad box during the second phase, it must first traverse its
enlargement.

###  5.5 Simple random walk moment

Now we handle the case when the walker traverses great boxes, during which we
do not perform identity coupling but try a different coupling. This coupling
will be based on what we call _a simple random walk moment_ (SRWM), which is a
given condition of the evolution of the environment that makes the walker
performs a simple random walk step.

######  Definition 5.10 (Simple random walk moment).

Let $R_{1}(i,\tau)$ be a great box such that $(X_{\tau t_{1}},\tau t_{1})\in
R_{1}^{\mathrm{core}}(i,\tau)$. We consider three consecutive intervals
$I_{1},I_{2},I_{3}$ of lengths

$|I_{1}|=\frac{t_{1}}{2}\quad\text{and}\quad|I_{2}|=|I_{3}|=\frac{1}{\mu},$

such that $I_{1}$ begins at time $\tau t_{1}=\min
T_{1}^{\mathrm{core}}(\tau)$; note that $\tau
t_{1}+\sum_{j=1}^{3}|I_{j}|<(\tau+2)t_{1}=\max T_{1}^{\mathrm{core}}(\tau)$.
Let $v\in S_{1}(i)$ be the position of the walker $X_{\tau t_{1}}$; note that
since $R_{1}(i,\tau)$ is a good box then all edges adjacent to $v$ at time
$\tau t_{1}$ are closed. All the events below consider only $\star$-updates
during $I_{1}\cup I_{2}\cup I_{3}$, ignoring all non-$\star$ updates. Then, a
_simple random walk moment_ (SRWM) is said to occur in $R_{1}(i,\tau)$ if the
following events happen consecutively:

  1. ($E_{1}$)

During $I_{1}$, one of the edges adjacent to $v$, say $e=(v,u)$, receives an
update to become open, and the edges adjacent to $u$ with status $\star$ are
sampled closed. Moreover, the other edges adjacent to $v$ or $u$ do not open
during $I_{1}$, and after $e$ opens, $e$ does not close for at least time
$\frac{C_{11}}{\mu}$.

  2. ($E_{2}$)

During $I_{2}$, edge $e$ closes and does not open, while the edges adjacent to
$e$, that were closed, do not open; note that at the end of $I_{2}$, the
walker is in either $u$ or $v$.

  3. ($E_{3}$)

During $I_{3}$, the edges adjacent to $u$ or $v$ do a $\star$-update, and the
edges adjacent to the walker do not open.

See Figure 4 for an illustrative realization of a simple random walk moment.
Define

$\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}\text{ be the indicator for the
event that SRWM occurs in $R_{1}(i,\tau)$.}$ (5.14)

######  Remark 5.11.

Given $v$, the position of the walker at time $\tau t_{1}$, the event SRWM
depends only on the updates in $E(S_{1}(i))$ during the time interval
$I_{1}\cup I_{2}\cup I_{3}$. In particular, it does not depend on the jumps of
the walkers during $I_{1}\cup I_{2}\cup I_{3}$, and does not depend on
non-$\star$ updates that could occur during $I_{1}\cup I_{2}\cup I_{3}$.

Figure 4: A possible realization of SRWM in a $k_{\mathrm{max}}$-great box.
(a) configuration at time $\tau t_{1}-\overline{t}_{1}$, with dashed lines
representing closed edges, solid lines representing open edges, and the black
ball representing the walker. (b) During $[\tau t_{1}-\overline{t}_{1},\tau
t_{1}]$ all edges close, trapping the walker in a vertex $v$. (c) During
$I_{1}$, edge $(u,v)$ adjacent to the walker opens, edges adjacent to $u$ are
closed, and the other edges receive a $\star$-update. Blue lines represent
edges that are updated $\star$. (d) Edge $(u,v)$ closes at some time during
$I_{2}$, trapping the walker in one of its endpoints, in this case endpoint
$u$. (e) During $I_{3}$ all edges adjacent to $v$ receive a $\star$-update,
while the edges adjacent to the walker do not open.

Note that from $\tau t_{1}$ to time $\tau t_{1}+|I_{1}\cup I_{2}\cup I_{3}|$
the walker essentially performed a simple random walk step since the edge $e$
adjacent to $v$ that is chosen to open during $I_{1}$ is a uniformly random
edge. Now assume that the walker enters $R_{1}^{\mathrm{core}}(i,\tau)$ with
$R_{1}(i,\tau)$ being a $k_{\mathrm{max}}$-great box; i.e., $(X_{\tau
t_{1}},\tau t_{1})\in R_{1}^{\mathrm{core}}(i,\tau)$. We define the coupling
we employ in this situation.

######  Definition 5.12 (Coupling on great boxes).

At time $\tau t_{1}$ both walkers are trapped at some vertices $v=X_{\tau
t_{1}}\in S_{1}^{\mathrm{core}}(i)$ and $\overline{v}=\Phi_{\tau t_{1}}(v)$.
Then we perform the following steps.

  1. 1.

Sample whether a simple random walk moment occurs in $R_{1}(i,\tau)$. If not,
sample the updates of the edges in $S_{1}(i)$ during $I_{1}\cup I_{2}\cup
I_{3}$ from the distribution conditioned on
$\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=0$, apply the coupling of the
graphs from Section 5.2.1 and apply identity coupling for the walkers.
Identity coupling succeeds since the graphs are coupled inside $S_{1}(i)$ and
we obtain that $\Phi_{t}$ does not change during $I_{1}\cup I_{2}\cup I_{3}$.
This concludes the coupling when
$\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=0$.

  2. 2.

If $\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1$, choose a coordinate
$j\in\left\\{1,2,\ldots,d\right\\}$ and a sign $s\in\left\\{-1,+1\right\\}$
uniformly at random. If $v$ and $\overline{v}$ agree in that coordinate, let
$e=(v,v+se_{j})$ and $\overline{e}=(\overline{v},\overline{v}+se_{j})$ be the
edges chosen to open during $I_{1}$ in the configurations $\eta^{\star}$ and
$\overline{\eta}^{\star}$, respectively, where $e_{1},e_{2},\ldots,e_{d}$
stands for the standard basis of $\mathbb{Z}^{d}$. In this case, during
$I_{2}$, we let the walkers perform the same jumps across $e$ and
$\overline{e}$ (i.e., we perform identity coupling), and note that $\Phi_{t}$
maps $e$ into $\overline{e}$ during this time. Then we couple the graphs using
$\Phi_{t}$, as described in Section 5.2.1, until the end of $I_{3}$. In this
case, the map $\Phi_{t}$ does not change during $I_{1}\cup I_{2}\cup I_{3}$.

  3. 3.

If $\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1$, and $v$ and
$\overline{v}$ do not agree in the $j$th coordinate, we set $e=(v,v+se_{j})$
and $\overline{e}=(\overline{v},\overline{v}-se_{j})$. This is the most
delicate case as we will need to change the coupling of the graphs from the
time $e$ opens to the end of $I_{1}\cup I_{2}\cup I_{3}$. For this, we will
use the map $\tilde{\Phi}$ which maps $v$ to $\overline{v}$ and is a
translation map in all coordinates but the $j$th one, where it is a reflection
map around $e$. In particular, $\tilde{\Phi}$ maps $e$ onto $\overline{e}$.
Then the graphs will be coupled as in Remark 5.2; that is, the graphs are
coupled as in Section 5.2.1 but using the map $\tilde{\Phi}$ instead of
$\Phi_{t}$. Note that any update to $e$ translates to an update of
$\overline{e}$, so they open at the same time and close at the same time. Let
$\zeta$ be the time that $e$ and $\overline{e}$ open for the first time during
$I_{1}$. Then, they remain open during $[\zeta,\zeta+C_{\ref*{cte:i1}}/\mu]$
since $\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1$. We couple the
position of the walkers at time $\zeta+C_{\ref*{cte:i1}}/\mu$ as follows. Let
$\delta$ be the probability that $X_{\zeta+C_{\ref*{cte:i1}}/\mu}=v$ and
$1-\delta$ be the probability that $X_{\zeta+C_{\ref*{cte:i1}}/\mu}=u$. Then
we make
$X_{\zeta+C_{\ref*{cte:i1}}/\mu}=\overline{X}_{\zeta+C_{\ref*{cte:i1}}/\mu}$
with probability $\min\left\\{\delta,1-\delta\right\\}$; otherwise, we sample
them accordingly. Then, we let the graph and the walkers evolve up to the end
of the interval $I_{1}\cup I_{2}\cup I_{3}$, coupling the jumps of the walkers
so that they jump at the same times after time $\zeta+C_{\ref*{cte:i1}}/\mu$;
note that the walkers do not move after $e$ and $\overline{e}$ close for the
first time after $\zeta+C_{\ref*{cte:i1}}/\mu$.

Now, let $s=\tau t_{1}+|I_{1}\cup I_{2}\cup I_{3}|$ be the end time of the
simple random walk moment. Note that if SRWM occurs then
$\|X_{s}-\overline{X}_{s}\|_{1}$ may differ from $\|X_{\tau t_{1}}^{1}-X_{\tau
t_{1}}^{2}\|_{1}$, and as a result the translation map $\Phi_{s}$ may be
different from $\Phi_{\tau t_{1}}$ as well. So it could be the case that an
edge that was coupled before the simple random walk moment (in the sense that
${\eta}_{\tau t_{1}}(e^{\prime})=\overline{\eta}_{\tau t_{1}}(\Phi_{\tau
t_{1}}(e^{\prime}))$) may get uncoupled because the map $\Phi$ changes. On the
other hand, after $I_{1}$ all the edges in the box receive a $\star$ update.
So at the end of the SRWM, all edges in $S_{1}(i)$ are $\star$ with the only
exception being the edges adjacent to the walker which are closed. So the
configurations are coupled locally, in particular, $\mathcal{B}_{s}^{\prime}$
holds. Moreover, as $R_{1}(i,\tau)$ is great (so it is also good) the
particles will stay in $S_{1}(i)$ for the whole time interval $T_{1}(\tau)$.
In other words we obtain that the edges in $S_{1}(i)$, where the random walk
moment is occurring, are coupled after the simple random walk moment ends.

More formally, we will implement this by assigning a “hidden” random variable
to each $1$-box, which tells whether the box will undergo a SRWM should the
walker pass there. We will not try the above coupling at each great box the
walker enters, since we do need a bit of time separation between two simple
random walk moments because of the overlapping of the boxes. But whenever we
decide to attempt a simple random walk moment inside a great box the walker is
in, the hidden random variable will tell whether SRWM will occurs. The main
point is that we can obtain a lower bound on
$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\right)$ that
is uniform on the location of the walker at time $\tau t_{1}$. Because of this
uniform bound, we can couple the outcome of the hidden variable with the
evolution of the processes ${M}_{t}^{\star}$ and $\overline{M}_{t}^{\star}$ so
that the simple random walk moment takes place, regardless of the location of
the walker within the box. The content of the hidden variable is just a
Bernoulli random variable of parameter
$C_{\ref*{cte:srwm}}p^{\frac{6d-1}{6d}}$, which is the bound we derive in
Lemma 5.14 below, so the event of successfully performing a SRWM
stochastically dominates the hidden variable. Whenever we decide to look at
the hidden variable of a box, we perform the coupling described above.
Otherwise, we just do identity coupling.

Before establishing a bound on
$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\right)$ we
need to show that the environments recouple locally after a SRWM.

######  Lemma 5.13 (Recoupling the graphs after SRWM).

Let $R_{1}(i,\tau)$ be a $k_{\mathrm{max}}$-great box such that $X_{\tau
t_{1}}\in S_{1}^{\mathrm{core}}(i)$ and $\mathcal{B}^{\prime\prime}_{\tau
t_{1}}$ holds. Suppose the walkers perform successfully a simple random walk
moment. Then

$\eta_{t}^{\star}(e)=\overline{\eta}_{t}^{\star}(\Phi_{t}(e))\text{ for all
$e\in E(S_{1}^{\mathrm{enl2}}(i))$ and all $t\in[s,(\tau+1)t_{1}],$}$

where $s=\tau t_{1}+|I_{1}\cup I_{2}\cup I_{3}|+\overline{t}_{1}$.

###### Proof.

$R_{1}(i,\tau)$ is $k_{\mathrm{max}}$-great, and in particular $1$-great.
Thus, every $1$-box $R(j,\tau)$ such that $S_{1}(j)\cap
S_{1}^{\mathrm{enl2}}(i)\neq\emptyset$ is good. After $s-\overline{t}_{1}=\tau
t_{1}+|I_{1}\cup I_{2}\cup I_{3}|$, we have that the edges in $S_{1}(i)$ are
coupled and we start performing identity coupling of the walkers. The coupling
is succeessful so $\Phi_{t}$ does not change from that moment onwards and all
edges in $S_{1}(j)$ with $S_{1}(j)\cap S_{1}^{\mathrm{enl2}}(i)\neq\emptyset$
receives a $\star$-update and couples. ∎

Now we bound the probability of a SRWM. Recall from Definition 2.7 that the
event that a box $R_{1}(i,\tau)$ is good is based on events
$\mathcal{G}_{12}(i,\tau)$ and $\widehat{\mathcal{G}}_{34}(i,\tau)$. Define
$\mathcal{J}$ to be the set of all tuples $(i,\tau)$ such that $R_{1}(i,\tau)$
is a box of the tessellation of the second phase. Let
$\Sigma=\\{0,1\\}^{2\mathcal{J}}$ be the set of all possible assignments of
occurrence or non occurrence to the events $\mathcal{G}_{12}(i,\tau)$ and
$\widehat{\mathcal{G}}_{34}(i,\tau)$. Then for each $\sigma\in\Sigma$ and each
$(i,\tau)$, the values $\sigma_{12}(i,\tau)$ and $\sigma_{34}(i,\tau)$ will be
used to specify whether the events $\mathcal{G}_{12}(i,\tau)$ and
$\widehat{\mathcal{G}}_{34}(i,\tau)$ occur, respectively. In this way, given
$\sigma\in\Sigma$, we abuse notation and denote by $\sigma$ the event that the
realizations of $\mathcal{G}_{12}(i,\tau)$ and
$\widehat{\mathcal{G}}_{34}(i,\tau)$ match the values of $\sigma_{12}(i,\tau)$
and $\sigma_{34}(i,\tau)$ for each $(i,\tau)\in\mathcal{J}$, and write
$\mathbb{P}(\cdot\mid\sigma)$ for the corresponding conditional probability.
More precisely,

$\mathbb{P}\left(\cdot\mid\sigma\right)=\mathbb{P}\left(\cdot\,\middle|\,\bigcap_{(i,\tau)\in\mathcal{J}}\left\\{\sigma_{12}(i,\tau)=\text{$\mathbbm{1}$}\left(\mathcal{G}_{12}(i,\tau)\right)\right\\}\cap\left\\{\sigma_{34}(i,\tau)=\text{$\mathbbm{1}$}\left(\widehat{\mathcal{G}}_{34}(i,\tau)\right)\right\\}\right).$

Note that once we condition on some $\sigma\in\Sigma$, then which boxes of all
scales are good or bad is a deterministic function of $\sigma$. Let
$\mathcal{F}_{t}$ be the $\sigma$-algebra generated by the trajectory of the
walker $X_{s}$ and the value of the map $\Psi_{s}$, $s\in[0,t]$, and all the
updates of the graph up to time $t$. Let $\Sigma_{i,\tau}\subset\Sigma$ be the
set of assignments $\sigma$ for which $R_{1}(i,\tau)$ is a
$k_{\mathrm{max}}$-great box.

######  Lemma 5.14.

Let $(i,\tau)$ be such that $R(i,\tau)$ is a $k_{\mathrm{max}}$-great box.
There exists $p_{0}>0$ and $C_{12}>0$ such that for all $p<p_{0}$, for all
$\sigma\in\Sigma_{i,\tau}$, and all $F\in\mathcal{F}_{\tau t_{1}}$ for which
$\mathbb{P}\left(\sigma\cap F\right)>0$, then the probability of performing a
simple random walk moment in $R_{1}(i,\,\tau)$ is

$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\mid
F\cap\sigma\right)\geq C_{\ref*{cte:srwm}}p^{\frac{6d-1}{6d}}.$ (5.15)

###### Proof.

Start with the following simplification of $\sigma$. Recall the definition of
$j(\tau)$ from (2.8). So $j(\tau)$ and $j(\tau+1)$ are the first and last
interval of the type $\overline{T}_{1}(\cdot)$ inside $T_{1}(\tau)$. Recall
that $\sigma_{34}(\cdot,\cdot)$ correspond to the events
$\widehat{\mathcal{G}}_{34}(\cdot,\cdot)$, which are i.i.d. events coupled
with the events $\mathcal{G}_{34}(\cdot,\cdot)$. Since
$\mathcal{G}_{34}(\cdot,\cdot)$ are independent of
$\mathcal{G}_{12}(\cdot,\cdot)$ by Lemma 2.4, we have that also
$\widehat{\mathcal{G}}_{34}(\cdot,\cdot)$ are independent of
$\mathcal{G}_{12}(\cdot,\cdot)$. Moreover, for any $x$, we have that
$\mathcal{G}_{34}(i^{\prime},\tau)$ is independent of $\mathcal{F}_{\tau
t_{1}}$ since $\mathcal{G}_{34}(i^{\prime},\tau)$ only considers updates on
the edges during the interval $T_{1}^{\mathrm{core}}(\tau)\setminus
T_{1}(\tau+1)$. Since for any fixed $x$ we have that
$\mathcal{G}_{34}(i^{\prime},\tau^{\prime})$ are independent for different
$s$, we have that $\widehat{\mathcal{G}}_{34}(i^{\prime},\tau)$ is independent
of $\mathcal{F}_{\tau t_{1}}$. So now we collect in $\mathcal{J}_{34}$ all
tuples from $\mathcal{J}$ for which
$\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}$ depend on
$\sigma_{34}(\cdot,\cdot)$:

$\mathcal{J}_{34}=\left\\{(i^{\prime},\tau)\colon S_{1}(i^{\prime})\cap
S_{1}(i)\neq\emptyset\right\\}\quad\text{and}\quad\mathcal{J}^{\prime}=\mathcal{J}\setminus\mathcal{J}_{34}.$

We will not need to split $\sigma_{12}(\cdot,\cdot)$ into two groups since
those events are already independent of
$\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}$.

For any $\sigma\in\Sigma$ denote

$\displaystyle\mathcal{S}$
$\displaystyle=\mathcal{S}(\sigma)=\bigcap_{(i^{\prime},\tau^{\prime})\in\mathcal{J}}\sigma_{12}(i^{\prime},\tau^{\prime})\bigcap_{(i^{\prime},\tau^{\prime})\in\mathcal{J}^{\prime}}\sigma_{34}(i^{\prime},\tau^{\prime})$
$\displaystyle\mathcal{S}_{34}$
$\displaystyle=\mathcal{S}_{34}(\sigma)=\bigcap_{(i^{\prime},\tau^{\prime})\in\mathcal{J}_{34}}\sigma_{34}(i^{\prime},\tau^{\prime}).$

Then,

$\displaystyle\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\mid
F\cap\sigma\right)$
$\displaystyle=\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,F\cap\mathcal{S}\cap\mathcal{S}_{34}\right)$
$\displaystyle\geq\frac{\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,F\cap\mathcal{S}\right)-\mathbb{P}\left(\mathcal{S}_{34}^{\mathrm{c}}\,\middle|\,F\cap\mathcal{S}\right)}{\mathbb{P}\left(\mathcal{S}_{34}\,\middle|\,F\cap\mathcal{S}\right)}$
$\displaystyle\geq\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,F\cap\mathcal{S}\right)-\mathbb{P}\left(\mathcal{S}_{34}^{\mathrm{c}}\,\middle|\,F\cap\mathcal{S}\right).$

Note that $T_{1}^{\mathrm{core}}(\tau)\setminus T_{1}(\tau+1)\supset I_{1}\cup
I_{2}\cup I_{3}$, so $\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}$ does not
depend on $F\cap\mathcal{S}$ given the position of the walker at time $\tau
t_{1}$. Letting $S_{1}^{\prime}(i)=\bigcup_{u\in
S_{1}^{\mathrm{core}}(i)}B_{\log^{2}\ell}^{\infty}(u)$, which are the places
where the walker can be at time $\tau t_{1}$, we write

$\displaystyle\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,F\cap\mathcal{S}\right)$
$\displaystyle=\sum_{v\in
S_{1}^{\prime}(i)}\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,F\cap\mathcal{S}\cap\left\\{X_{\tau
t_{1}}=v\right\\}\right)\mathbb{P}\left(X_{\tau
t_{1}}=v\,\middle|\,F\cap\mathcal{S}\right)$ $\displaystyle=\sum_{v\in
S_{1}^{\prime}(i)}\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,X_{\tau
t_{1}}=v\right)\mathbb{P}\left(X_{\tau
t_{1}}=v\,\middle|\,F\cap\mathcal{S}\right)$

We are left with the following lower bound on
$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\mid
F\cap\sigma\right)$:

$\displaystyle\sum_{v\in
S_{1}^{\prime}(i)}\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,X_{\tau
t_{1}}=v\right)\mathbb{P}\left(X_{\tau
t_{1}}=v\,\middle|\,F\cap\mathcal{S}\right)-\mathbb{P}\left(\mathcal{S}_{34}^{\mathrm{c}}\,\middle|\,F\cap\mathcal{S}\right)$
$\displaystyle\geq\inf_{v\in
S_{1}^{\prime}(i)}\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,X_{\tau
t_{1}}=v\right)-\mathbb{P}\left(\mathcal{S}_{34}^{\mathrm{c}}\,\middle|\,F\cap\mathcal{S}\right).$
(5.16)

We start with the first term in (5.16); that is, we derive a lower bound on
$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,X_{\tau
t_{1}}=v\right)$ that is uniform in $v$. Since
$\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}$ is composed of the events
$E_{1}$, $E_{2}$ and $E_{3}$, which are independent of one another since they
involve disjoint time intervals, we will derive a lower bound for each of
them. For the event $E_{1}$, we will require that an edge adjacent to $v$
(call it $e$) opens during the first half of $I_{1}$, so that $e$ has time to
remains open for time $C_{\ref*{cte:i1}}/\mu$ during $I_{1}$. Recall that
$I_{1}$ has length $t_{1}/2$, so its first half has length $t_{1}/4$, and the
rate at which an edge opens due to a $\star$-update is $\mu
p_{\star}\frac{p_{\mathrm{min}}}{p_{\star}}=\mu p_{\mathrm{min}}$, and the
rate at which an edge close due to a $\star$-update is $1-p_{\mathrm{max}}$.
We obtain

$\displaystyle\mathbb{P}\left(E_{1}\,\middle|\,X_{\tau
t_{1}}=v\right)=\left(1-e^{-2d\mu
p_{\mathrm{min}}\frac{t_{1}}{4}}\right)\left(\frac{1-p_{\mathrm{max}}}{p_{\star}}\right)^{2d-1}e^{-(4d-2)\mu
p_{\mathrm{min}}\frac{t_{1}}{2}}e^{-\mu(1-p_{\mathrm{max}})\frac{C_{\ref*{cte:i1}}}{\mu}}.$

In the product above, the first term corresponds to an edge adjacent to the
walker (call it $e$) opening during the first half of $I_{1}$, the second term
is the probability that all $2d-1$ edges adjacent to $e$ are closed at that
time, the third term is the probability that none of the $4d-2$ edges adjacent
to $e$ open until the end of $I_{1}$, and the fourth term is the probability
that $e$ remains open for at least time $C_{\ref*{cte:i1}}/\mu$. Recalling
that $t_{1}=\frac{\sqrt{\ell}}{\mu}$ and that $\ell=p^{-\frac{1}{3d}}$ we
obtain

$\displaystyle\mathbb{P}\left(E_{1}\,\middle|\,X_{\tau
t_{1}}=v\right)=\left(1-e^{-dp_{\mathrm{min}}\frac{\sqrt{\ell}}{2}}\right)\left(\frac{1-p_{\mathrm{max}}}{p_{\star}}\right)^{2d-1}e^{-(2d-1)p_{\mathrm{min}}\sqrt{\ell}}e^{-C_{\ref*{cte:i1}}(1-p_{\mathrm{max}})}.$

Using that $p_{\star}\leq 1$ in the second term,
$p_{\mathrm{min}}\in\left[\frac{p}{1+q},p\right]$ in the first and third
terms, and $p_{\mathrm{max}}\geq 0$ in the fourth term, and then making $p$
small enough so that $p_{\mathrm{min}}\leq p_{\mathrm{max}}\leq\frac{1}{2}$
and $e^{-d\frac{p}{1+q}\frac{\sqrt{\ell}}{2}}\leq
1-\frac{dp\sqrt{\ell}}{4(1+q)}$ we obtain

$\displaystyle\mathbb{P}\left(E_{1}\,\middle|\,X_{\tau t_{1}}=v\right)$
$\displaystyle\geq\left(1-e^{-d\frac{p}{1+q}\frac{\sqrt{\ell}}{2}}\right)\left(1-p_{\mathrm{max}}\right)^{2d-1}e^{-(2d-1)p\sqrt{\ell}}e^{-C_{\ref*{cte:i1}}}$
$\displaystyle\geq\frac{dp\sqrt{\ell}}{4(1+q)}2^{-2d+1}e^{-(2d-1)p\sqrt{\ell}}e^{-C_{\ref*{cte:i1}}}$
$\displaystyle=\frac{e^{-C_{\ref*{cte:i1}}}d}{2^{2d+1}(1+q)}p\sqrt{\ell}e^{-(2d-1)p\sqrt{\ell}}.$

Now note that $p\sqrt{\ell}=p^{1-\frac{1}{6d}}$ goes to $0$ as $p\to 0$. Thus,
we can take $p$ small enough so that
$p\sqrt{\ell}e^{-(2d-1)p\sqrt{\ell}}\geq\frac{p\sqrt{\ell}}{2}$ to otain

$\displaystyle\mathbb{P}\left(E_{1}\,\middle|\,X_{\tau
t_{1}}=v\right)\geq\frac{e^{-C_{\ref*{cte:i1}}}d}{2^{2d+2}(1+q)}p\sqrt{\ell}=\frac{e^{-C_{\ref*{cte:i1}}}d}{2^{2d+2}(1+q)}p^{1-\frac{1}{6d}}.$
(5.17)

Event $E_{1}$ is the main one governing the probability that SRWM occurs,
since it involves the opening of an edge, which has small probability. For
$E_{2}$ and $E_{3}$ we will just derive simple bounds that will not go to $0$
as $p\to 0$. Recall that $I_{2}$ and $I_{3}$ are time intervals of length
$1/\mu$, so

$\mathbb{P}\left(E_{2}\,\middle|\,X_{\tau
t_{1}}=v\right)=\left(1-e^{-\mu(1-p_{\mathrm{max}})\frac{1}{\mu}}\right)e^{-\mu
p_{\mathrm{min}}\frac{1}{\mu}}e^{-(4d-2)\mu p_{\mathrm{min}}\frac{1}{\mu}},$

where the first term is the probability that $e$ has a $\star$-update to
close, the second term is the probability that $e$ does not get a
$\star$-update to open, and the final term is the probability that all $4d-2$
edges adjacent to $e$ do not receive a $\star$-update to open. Recall that
$p_{\mathrm{min}}$ and $p_{\mathrm{max}}$ both go to $0$ as $p\to 0$, so we
obtain that

$\displaystyle\mathbb{P}\left(E_{2}\,\middle|\,X_{\tau t_{1}}=v\right)\geq
1-\frac{1}{2e}.$ (5.18)

Regarding $E_{3}$, we obtain

$\displaystyle\mathbb{P}\left(E_{3}\,\middle|\,X_{\tau
t_{1}}=v\right)=\left(1-e^{-(2d-1)\mu p_{\star}\frac{1}{\mu}}\right)e^{-2d\mu
p_{\mathrm{min}}\frac{1}{\mu}}\geq 1-\frac{1}{2e^{2d-1}},$ (5.19)

where the inequality follows for all small enough $p$ since $p_{\star}\to 1$
and $p_{\mathrm{min}}\to 0$ as $p\to 0$. Putting (5.17), (5.18) and (5.19)
together we have a constant $c=c(d,q)$ so that for all small enough $p$ we
obtain

$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\,\middle|\,X_{\tau
t_{1}}=v\right)\geq cp^{1-\frac{1}{6d}}.$

Plugging the bound above into (5.16), we obtain

$\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\mid
F\cap\sigma\right)\geq
cp^{1-\frac{1}{6d}}-\mathbb{P}\left(\mathcal{S}_{34}^{\mathrm{c}}\,\middle|\,F\cap\mathcal{S}\right).$
(5.20)

Now as we explained in the beginning of the proof, $\mathcal{S}_{34}$ is
independent of $\mathcal{F}_{\tau t_{1}}$ and of $\mathcal{S}$. Moreover,
$\mathcal{S}_{34}$ is composed of an intersection of independent events
$\widehat{\mathcal{G}}_{34}(\cdot,\tau)$ since $\sigma\in\Sigma_{i,\tau}$ so
that $R_{1}(i,\tau)$ is $k_{\mathrm{max}}$-great. Therefore,

$\displaystyle\mathbb{P}\left(\mathbb{I}_{(i,\tau)}^{{\scalebox{0.7}{SRWM}}}=1\mid
F\cap\sigma\right)$ $\displaystyle\geq
cp^{1-\frac{1}{6d}}-\mathbb{P}\left(\bigcup_{(i^{\prime},\tau)\in\mathcal{J}_{34}}\widehat{\mathcal{G}}^{\mathrm{c}}_{34}(i^{\prime},\tau)\right)$
$\displaystyle\geq
cp^{1-\frac{1}{6d}}-\sum_{(i^{\prime},\tau)\in\mathcal{J}_{34}}\mathbb{P}\left(\widehat{\mathcal{G}}^{\mathrm{c}}_{34}(i^{\prime},\tau)\right)$
$\displaystyle\geq
cp^{1-\frac{1}{6d}}-5^{d}\exp\left(-C_{\ref*{cte:bblss}}\log^{2}\ell\right),$

where the last inequality follows from Lemma 2.6. Since as $p\to 0$ the second
term is much smaller than the first one, the lemma follows. ∎

###  5.6 Concluding the second phase

Recall that for simplicity we are assuming that $(X_{0},0)=(0,0)$, and recall
the value of $\Delta_{2}$ from (5.2). Denote with $I_{d}:V\to V$ the identity
map, then we define

$F_{2}=\\{(0,0)\text{ is
$k_{\mathrm{max}}$-great}\\}\cap\\{\Phi_{\Delta_{2}}=I_{d}\\}\cap\mathcal{B}_{\Delta_{2}}^{\prime}.$
(5.21)

If $F_{2}$ is verified, the second phase is successful and the third phase can
start, otherwise we let the two processes evolve independently until the end
of _phase 3_ , and only then restart the coupling from phase 1.

######  Lemma 5.15.

Assume $F_{1}$ is verified at time $0$. For any $\delta>0$ and for all $p$
small enough, there exists
$C_{\ref*{cte:delta2}}=C_{\ref*{cte:delta2}}(d,p,\delta)>0$ in the definition
of $\Delta_{2}$ and $n_{0}<\infty$ such that for all $n>n_{0}$

$\mathbb{P}(F_{2})\geq 1-\delta.$

###### Proof.

Let $\mathcal{P}$ be any feasible path and consider

$\displaystyle\Upsilon_{1}^{\mathcal{P}}$
$\displaystyle=\inf\left\\{\tau>0\colon(\mathcal{P}(\tau t_{1}),\tau t_{1})\in
R_{1}^{\mathrm{core}}(i,\tau)\text{ where $R_{1}(i,\tau)$ is a
$k_{\mathrm{max}}$-great box}\right\\},$
$\displaystyle\Upsilon_{j}^{\mathcal{P}}$
$\displaystyle=\inf\left\\{\tau>\Upsilon_{j-1}^{\mathcal{P}}\colon(\mathcal{P}(\tau
t_{1}),\tau t_{1})\in R_{1}^{\mathrm{core}}(i,\tau)\text{ where
$R_{1}(i,\tau)$ is a $k_{\mathrm{max}}$-great box}\right\\},$

for $j\geq 2$. For any feasible path $\mathcal{P}$ we let
$\kappa_{\mathcal{P}}$ be the largest value such that
$\Upsilon_{\kappa_{\mathcal{P}}}^{\mathcal{P}}\leq\frac{\Delta_{2}}{t_{1}}-2$.
Recall that $\Sigma$ represents the set of all possible realizations of
occurrences and non occurrences for the events $\mathcal{G}_{12}(\cdot,\cdot)$
and $\widehat{\mathcal{G}}_{34}(\cdot,\cdot)$, so the good and bad boxes at
all scales are deterministic functions of $\sigma$. Let $\mathfrak{F}(\sigma)$
be the set of all feasible paths for a given $\sigma$. Given the uniform bound
from Lemma 5.14, we let $Y_{1},Y_{2},\ldots$ be a sequence of i.i.d. Bernoulli
random variables of parameter $C_{\ref*{cte:srwm}}p^{\frac{6d-1}{6d}}$ where
$Y_{j}$ gives whether the $j$th SRWM will succeed when we try to perform it
during the coupling. Let

$\zeta=\frac{C_{\ref*{cte:gbc}}C_{\ref*{cte:delta2}}}{4\sqrt{\ell}}n^{2}=\frac{C_{\ref*{cte:gbc}}}{4t_{1}}\Delta_{2},$
(5.22)

where $C_{\ref*{cte:gbc}}$ is from Lemma 2.25 and $C_{\ref*{cte:delta2}}$ from
the definition of $\Delta_{2}$ in (5.2). Define the following events

$\displaystyle E_{1}=\left\\{\sum\nolimits_{j=1}^{\zeta}Y_{j}\geq
c_{0}n^{2}\right\\},\text{ with $c_{0}$ to be chosen later, and}$
$\displaystyle E_{2}=\left\\{\kappa_{\mathcal{P}}\geq\zeta\text{ for all
feasible paths $\mathcal{P}\in\mathfrak{F}(\sigma)$}\right\\}.$

In this stage we want to couple the position of the walkers. From Lemma 5.8,
by doing identity coupling whenever the walkers are not in a great box, their
relative distance does not change. Their relative distance changes only when
they are in a great box and a simple random walk moment is successfully
performed. Let
$E_{\mathrm{coup}}=\\{\Phi_{\Delta_{2}}=I_{d}\\}\cap\mathcal{B}_{\Delta_{2}}^{\prime}$.
Hence

$\displaystyle\mathbb{P}(F_{2}^{c})$
$\displaystyle\leq\mathbb{P}\left((0,0)\text{ is not
$k_{\mathrm{max}}$-great}\right)+\mathbb{P}\left(E_{1}\cap E_{2}\cap
E_{\mathrm{coup}}^{c}\right)+\mathbb{P}\left(E_{1}^{c}\right)+\mathbb{P}\left(E_{2}^{c}\right).$

We start by bounding the first term. Notice that $\left\\{(0,0)\text{ is not
$k_{\mathrm{max}}$-great}\right\\}$ does not depend on the configuration at
time 0. Moreover, at time 0, the walkers are stuck in a vertex, so $X_{s}$ has
to leave $R_{1}(0,0)$ from the time boundary if $R_{1}(0,0)$ is a good box.
Using Lemmas 2.8 and 2.15 to bound $\rho_{j}$, we obtain

$\displaystyle\mathbb{P}\left((0,0)\text{ is not
$k_{\mathrm{max}}$-great}\right)\leq
c_{d}\sum_{j=1}^{k_{\mathrm{max}}}\rho_{j}\leq
c_{d}\left(\rho_{1}+\sum_{j=2}^{k_{\mathrm{max}}}\rho_{1}^{2^{k-2}}\right)\leq
3c_{d}\rho_{1}\leq\frac{\delta}{4},$

where $c_{d}$ is a constant that counts the number of boxes whose
2-enlargement intersects $R_{1}(0,0)$, and the last inequality follows for all
$p$ small enough. Next we bound

$\mathbb{P}\left(E_{1}\cap E_{2}\cap
E_{\mathrm{coup}}^{c}\right)\leq\frac{\delta}{4}.$

Under $E_{1}\cap E_{2}$, we know we performed at least $c_{0}n^{2}$ simple
random walk moments. So, $\mathbb{P}\left(E_{1}\cap
E_{\mathrm{coup}}^{c}\right)$ can be bounded by the probability that two
random walkers performing SRW on $\mathbb{T}_{n}^{d}$ are not coupled after
$c_{0}n^{2}$ steps. Taking $c_{0}=c_{0}(d,\delta)$ large enough we obtain that
they have coupled with probability at least $1-\frac{\delta}{4}$.

Next, we bound $\mathbb{P}\left(E_{2}^{c}\right)$. From Lemma 5.1, with
probability at least $1-\rho_{1}^{2^{k_{\mathrm{max}}-3}}$, all
$k_{\mathrm{max}}$-boxes in the tessellation are good. Thus, Lemma 2.25 gives
that while traversing the first good $k_{\mathrm{max}}$-great box any feasible
paths will traverse at least

$C_{\ref*{cte:gbc}}\frac{t_{k_{\mathrm{max}}}}{t_{1}}$

$k_{\mathrm{max}}$-great $1$-boxes. After the feasible path exits the first
$k_{\mathrm{max}}$-great box, it enters into another one and we obtain again
another set of $k_{\mathrm{max}}$-great $1$-boxes. The total number of steps
we can iterate this procedure up to reaching time $\Delta_{2}$ is
$\frac{\Delta_{2}}{2t_{k_{\mathrm{max}}}}-1\geq\frac{\Delta_{2}}{4t_{k_{\mathrm{max}}}}$.
Therefore, any feasible path must traverse at least

$C_{\ref*{cte:gbc}}\frac{t_{k_{\mathrm{max}}}}{t_{1}}\frac{\Delta_{2}}{4t_{k_{\mathrm{max}}}}=C_{\ref*{cte:gbc}}\frac{\Delta_{2}}{4t_{1}}=\zeta$

$k_{\mathrm{max}}$-great boxes. Hence,

$\mathbb{P}\left(E_{2}^{c}\right)\leq\rho_{1}^{2^{k_{\mathrm{max}}-3}}\leq\frac{\delta}{4},$

by simply having $n$ large enough.

Finally we bound $\mathbb{P}\left(E_{1}^{\mathrm{c}}\right)$. This is a simple
Chernoff bound for the sum of independent Bernoulli random variables, where
$\mathbb{P}(Y_{j})=C_{\ref*{cte:srwm}}p^{\frac{6d-1}{6d}}$. Since

$\mathbb{E}\left(\sum_{j=1}^{\zeta}Y_{j}\right)=C_{\ref*{cte:srwm}}p^{\frac{6d-1}{6d}}\zeta=\frac{C_{\ref*{cte:gbc}}C_{\ref*{cte:delta2}}C_{\ref*{cte:srwm}}}{4}\frac{p^{\frac{6d-1}{6d}}}{\sqrt{\ell}}n^{2}=\frac{C_{\ref*{cte:gbc}}C_{\ref*{cte:delta2}}C_{\ref*{cte:srwm}}}{4}p^{\frac{1}{6d}+\frac{6d-1}{6d}}n^{2}=\frac{C_{\ref*{cte:gbc}}C_{\ref*{cte:delta2}}C_{\ref*{cte:srwm}}}{4}pn^{2}.$

Now we take $C_{\ref*{cte:delta2}}$ large enough so that the above is larger
than $2c_{0}n^{2}$, which gives a constant $c$ so that

$\mathbb{P}\left(E_{1}^{\mathrm{c}}\right)\leq\exp\left(-c\mathbb{E}\left(\sum_{j=1}^{\zeta}Y_{j}\right)\right)\leq\exp\left(-c2c_{0}n^{2}\right)\leq\frac{\delta}{4},$

where the last inequality follows by taking $n$ large. ∎

To conclude the second phase, once the walkers are coupled after one SRWM, we
just perform identity coupling up to time $\Delta_{2}$. If $t$ is a time where
a SRWM ended, notice that Lemma 5.13 gives that $\mathcal{B}_{t}^{\prime}$
holds. So we succeed performing identity coupling up to $\Delta_{2}$ by Lemmas
5.6, 5.7 and 5.8.

##  6 Third Phase

The third phase starts at time $\Delta_{2}$, at which time the walkers are
coupled and $\mathcal{B}_{\Delta_{2}}^{\prime}$ holds. During the third phase
we let $\overline{M}_{t}^{\star}$ mimic the evolution of ${M}_{t}^{\star}$ by
doing identity coupling on both the motion of the walkers and the updates of
the edges. We now check whether the processes are fully coupled by time
$\Delta_{3}=\Delta_{2}+\frac{n^{2}}{\mu}$.

Define

$F_{3}=\left\\{X_{\Delta_{3}}=\overline{X}_{\Delta_{3}}\text{ and
}{\eta}_{\Delta_{3}}^{\star}(e)=\overline{\eta}_{\Delta_{3}}^{\star}(e)\,\forall
e\in E(\mathbb{T})_{n}^{d}\right\\}.$ (6.1)

If $F_{3}$ is not verified, we restart the coupling at time $\Delta_{3}$ from
phase 1.

######  Lemma 6.1.

For any $\delta>0$, if $p$ is small enough and $n$ large enough, we obtain

$\mathbb{P}\left(F_{3}\right)\geq 1-\delta.$ (6.2)

###### Proof.

Recall that boxes contained in $[0,\Delta_{3}]$ have been sampled as good or
bad during the second phase. By Lemmas 5.6, 5.7 and 5.8, identity coupling is
successful provided we cannot enter a bad box without first entering its
2-enlargement. Therefore, for the walkers to get uncoupled during
$[\Delta_{2},\Delta_{3}]$, it must so happen that the walkers entered a bad
box of some scale $k$ whose $2$-enlargement intersects $[0,\Delta_{2}]$ and
which was not observed during the second phase because it is not contained in
$[0,\Delta_{3}]$. We now count the number of such boxes.

We start by deriving bounds on $\ell_{k}$ and $t_{k}$, the size of the boxes
of scale $k$, for which the above can happen. When $k\geq k_{\mathrm{max}}$,
we can choose $n$ large enough so that for any $m,\ell$ fixed

$\displaystyle 2\ell k^{2k}\leq\ell_{k}$
$\displaystyle=m^{k}(k!)^{2}\ell\leq\ell k^{3k},$ $\displaystyle
2\sqrt{\ell}k^{2k}\leq\mu t_{k}$
$\displaystyle=m^{k}(k!)^{2}\sqrt{\ell}\leq\sqrt{\ell}k^{3k}.$

Recall that $k_{\mathrm{max}}=\log_{2}\log n$ from (5.1). Then, $\mu
t_{k_{\mathrm{max}}}\leq\sqrt{\ell}k_{\mathrm{max}}^{3\log_{2}\log n}$ is much
smaller than a polynomial in $n$. Therefore, any box whose enlargement
intersects $[0,\Delta_{2}]$ and is not contained in $[0,\Delta_{3}]$ must be
of scale larger than $k_{\mathrm{max}}$. So

$\displaystyle\mathbb{P}\left(F_{3}\right)$ $\displaystyle\geq
1-\mathbb{P}\left(\exists\,k>k_{\mathrm{max}}\colon R_{k}(i,\tau)\text{ is bad
and }\Delta_{3}\in T_{k}^{\mathrm{enl2}}(\tau)\right).$

Next, using the bounds we derived above for $\ell_{k}$ and $t_{k}$, the number
$\zeta_{k}$ of boxes of scale $k$ that intersect
$\mathbb{T}_{n}^{d}\times\Delta_{3}$ is bounded above and below by

$\displaystyle\zeta_{k}\geq$
$\displaystyle\left(\frac{n}{3\ell_{k}}\right)^{d}24\geq\frac{24n^{d}}{3^{d}\ell^{d}k^{3dk}},$
$\displaystyle\zeta_{k}\leq$ $\displaystyle
1+24\left(\frac{n}{\ell_{k}}\right)^{d}\leq
1+\frac{24n^{d}}{\ell^{d}k^{2dk}}.$

In the upper bound of $\zeta_{k}$ we add a $1$ to the fraction to consider the
case when $k$ is so large that we cannot find a box all contained in the
tessellation. 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\sum_{k\geq
k_{\mathrm{max}}}\zeta_{k}\rho_{1}^{2^{k-2}},$

moreover using the inequalities above for $\zeta_{k}$ it is easy to see that,
for any $k\geq k_{\mathrm{max}}$,

$\sum_{k\geq k_{\mathrm{max}}}\zeta_{k}\rho_{k}\leq
2\zeta_{k_{\mathrm{max}}}\rho_{1}^{2^{k_{\mathrm{max}}-2}}.$

Since $2^{k_{\mathrm{max}}}=\log n$, by taking $p$ small enough we make
$\rho_{1}$ small enough, which gives that

$\displaystyle\mathbb{P}(F_{3})\geq 1-\delta.$

∎

##  7 Completing the proof of Theorem 1.1

###### Proof of Theorem 1.1.

Let $\\{{M}_{t}^{\star}\\}_{t\geq 0}$ and
$\\{\overline{M}_{t}^{\star}\\}_{t\geq 0}$ denote two copies of the process,
each starting from an arbitrary configuration in
$\mathbb{T}_{n}^{d}\times\\{0,1\\}^{E(\mathbb{T}_{n}^{d})}$. Recall the events
$F_{1}$, $F_{2}$ and $F_{3}$ from (4.3), (5.21) and (6.1). If the three events
hold then $X_{\Delta_{3}}=\overline{X}_{\Delta_{3}}$ and
$\eta_{\Delta_{3}}^{\star}\equiv\overline{\eta}_{\Delta_{3}}$. So from
$\Delta_{3}$ onwards we can keep the processes coupled. We can now set
$\delta=\frac{1}{12}$ so that $F_{1}\cap F_{2}\cap F_{3}$ all hold with
probability at least $\frac{3}{4}$. If any of the above fails, we just let the
processes evolve independently up to time $\Delta_{3}$ and restart from
scratch. Since $\Delta_{3}$ is of order $n^{2}/\mu$ from (5.2), we obtain that
the mixing time is of order $n^{2}$ concluding the proof. ∎

##  8 Proof of the lower bound (Theorems 1.2 and 1.3)

The proof of the lower bounds are identical to the ones in [11]. We add them
here for completion.

###### Proof of Theorem 1.2.

First we introduce a discrete time Markov chain
$\tilde{M}_{k}=(\tilde{X}_{k},\tilde{\eta}_{k})$ which is defined by sampling
the continuous time chain $M_{t}=(X_{t},\eta_{t})$ on intervals of length
$\delta$; that is,

$\tilde{X}_{k}=X_{k\delta}\quad\text{and}\quad\tilde{\eta}_{k}=\eta_{k\delta},$

where $\delta$ is given from (1.4). Let
$\tilde{\gamma}=\tilde{\gamma}(\tilde{M})$ and $\gamma=\gamma(M)$ be the
spectral gaps of the discrete time and continuous time chain, respectively. We
obtain

$1-\tilde{\gamma}=\exp\left(-\delta\gamma\right).$

For all $\tilde{\gamma}\leq 1/2$ we simply use the bound
$\gamma\leq\frac{2\tilde{\gamma}}{\delta}$. The lower bound on the relaxation
time follows by taking the function $f(x,\xi)=d(x,0)$, so $f(X_{t},\eta_{t})$
is the distance between the walker and the origin of $\mathbb{T}_{n}^{d}$.
Since the stationary distribution of the walker is uniform by (1.3), it
follows that $\mathrm{Var}(f)\geq cn^{2}$ for some constant $c>0$. Moreover,
from (1.4), we have

$\displaystyle\mathcal{E}(f,f)$
$\displaystyle=\frac{1}{2}\sum_{x,\xi}\pi(x)\nu(\xi)\sum_{x^{\prime},\xi^{\prime}}P((x,\xi),(x^{\prime},\xi^{\prime}))\left(d(x,0)-d(x^{\prime},0)\right)^{2}$
$\displaystyle\leq\frac{1}{2}\mathbb{E}_{x\sim\pi}\left(D_{x,\delta}^{2}\right)\leq\frac{1}{2}C_{\ref*{cte:assump2}},$

where $\mathbb{E}_{x\sim\pi}$ denotes the expectation where $x$ is a random
variable sampled according to $\pi$, the uniform measure on
$\mathbb{T}_{n}^{d}$. From the above we obtain

$\tilde{\gamma}\leq\frac{C_{\ref*{cte:assump2}}}{2cn^{2}}.$

If the above is at most $1/2$ we obtain

$\gamma\leq\frac{C_{\ref*{cte:assump2}}}{cn^{2}\delta}.$

Otherwise, if $\tilde{\gamma}\geq 1/2$ we obtain that $\gamma$ is of order
$1/\delta$. The above establishes the relaxation time of the chain. ∎

###### Proof of Theorem 1.3.

We use the following nice result from [9], which appeared implicitly already
in [3].

######  Lemma 8.1.

Let $\left\\{Y_{k}\right\\}_{k\in\mathbb{Z}}$ be a discrete-time, stationary,
reversible Markov chain with finite state space $\mathcal{S}$, and let
$h\colon S\to\mathbb{R}^{m}$ for some $m\in\mathbb{Z}_{+}$. Then, for each
$k\geq 0$

$\mathbb{E}\left(\|h(Y_{k})-h(Y_{0})\|_{L_{2}}^{2}\right)\leq
k\mathbb{E}\left(\|h(Y_{1})-h(Y_{0})\|_{L_{2}}^{2}\right),$

where $\|\cdot\|_{L_{2}}$ denotes the Euclidean norm on $\mathbb{R}^{m}$.

Letting $g_{n}\colon\mathbb{T}_{n}^{d}\to\mathbb{R}^{2d}$ the function

$g_{n}(x_{1},x_{2},\ldots,x_{d})=\left(n\cos\left(2\pi
x_{1}/n\right),n\sin\left(2\pi x_{1}/n\right),\ldots,n\cos\left(2\pi
x_{d}/n\right),n\sin\left(2\pi x_{d}/n\right)\right).$

For $x\in\mathbb{T}_{n}^{d}$ and
$\xi\in\left\\{0,1\right\\}^{E\left(\mathbb{T}_{n}^{d}\right)}$ we let
$h(x,\xi)=g_{n}(x)$. Then, noting that $g_{n}$ is bi-Lipschitz with some
constant $c$ we have

$\displaystyle\mathbb{E}_{\pi\times\nu}\left(\|\tilde{X}_{k}-\tilde{X}_{0}\|_{1}^{2}\right)$
$\displaystyle\leq
c^{2}\mathbb{E}_{\pi\times\nu}\left(\left(g_{n}(\tilde{X}_{k})-g_{n}(\tilde{X}_{0})\right)^{2}\right)$
$\displaystyle\leq
c^{2}k\mathbb{E}_{\pi\times\nu}\left(\left(g_{n}(\tilde{X}_{1})-g_{n}(\tilde{X}_{0})\right)^{2}\right)$
$\displaystyle\leq
c^{4}k\mathbb{E}_{\pi\times\nu}\left(\|\tilde{X}_{1}-\tilde{X}_{0})\|_{2}^{2}\right)\leq
c^{4}k\mathbb{E}_{\pi\times\nu}\left(D_{\tilde{X}_{0},\delta}^{2}\right)\leq
c^{4}C_{\ref*{cte:assump2}}k.$

Hence for any $t\geq\delta$ we have

$\mathbb{E}_{\pi\times\nu}\left(\|X_{t}-X_{0}\|_{1}^{2}\right)\leq
c^{4}C_{\ref*{cte:assump2}}\left\lceil\tfrac{t}{\delta}\right\rceil\leq
2c^{4}C_{\ref*{cte:assump2}}\frac{t}{\delta}.$

Now for the total variation starting from a stationary environment, we simply
make

$\displaystyle\|\upsilon_{t}-\pi\times\nu\|_{\mathrm{TV}}$
$\displaystyle\geq\mathbb{P}\left(\|X_{t}-X_{0}\|_{1}\leq\epsilon^{1/d}n\right)\left(1-\frac{2\epsilon}{3}\right)$
$\displaystyle=\left(1-\mathbb{P}\left(\|X_{t}-X_{0}\|_{1}\leq\epsilon^{1/d}n\right)\right)\left(1-\frac{2\epsilon}{3}\right)$
$\displaystyle\geq\left(1-\frac{\mathbb{E}\left(\|X_{t}-X_{0}\|_{1}^{2}\right)}{\epsilon^{2/d}n^{2}}\right)\left(1-\frac{2\epsilon}{3}\right)$
$\displaystyle\leq\left(1-\frac{2c^{4}C_{\ref*{cte:assump2}}t}{\delta\epsilon^{2/d}n^{2}}\right)\left(1-\frac{2\epsilon}{3}\right).$

Therefore, if $t\leq\frac{\epsilon^{\frac{2+d}{d}}\delta
n^{2}}{6c^{4}C_{\ref*{cte:assump2}}}$ we have that
$\|\upsilon_{t}-\pi\times\nu\|_{\mathrm{TV}}\geq 1-\epsilon$. ∎

##  9 Proof of Corollary 1.4

In order to apply the above to the random walk on dynamical random cluster
model, we first need a certain sprinkling lemma for the random cluster model.
Given $q\geq 1$ and $p>0$, let $\nu_{p,q}$ be the measure of a random cluster
model with parameters $p,q$. Let $\eta$ be a configuration sampled from
$\nu_{p,q}$. We construct a sprinkling by associating to each edge $e$ an
independent Bernoulli random variable $Z(e)$ of parameter $\epsilon$. Define
the configurations

$\left(\eta+Z\right)(e)=\text{$\mathbbm{1}$}\left(\eta(e)+Z(e)\geq
1\right)\text{ for $e\in E(\mathbb{T}_{n}^{d})$}$

and

$\left(\eta-Z\right)(e)=\text{$\mathbbm{1}$}\left(\eta(e)(1-Z(e))=1\right)\text{
for $e\in E(\mathbb{T}_{n}^{d})$}.$

So $\eta+Z$ (resp., $\eta-Z$) is the configuration obtained from $\eta$ by
opening (resp., closing) all edges $e$ with $Z(e)=1$. Given two elements
$\xi,\xi^{\prime}$ of $\left\\{0,1\right\\}^{E(\mathbb{T}_{n}^{d})}$ we say
that $\xi\leq\xi^{\prime}$ if $\xi(e)\leq\xi^{\prime}(e)$ for all $e\in
E(\mathbb{T}_{n}^{d})$.

######  Lemma 9.1 (Sprinkling lemma).

Let $q\geq 1$, $0<p<p^{\prime}<1$ and $\epsilon>0$ be fixed. Let
$\left\\{Z(e)\colon e\in E(\mathbb{T}_{n}^{d})\right\\}$ be a collection of
i.i.d. Bernoulli random variables of parameter $\epsilon$. Let $\eta$ and
$\eta^{\prime}$ be random configurations with distributions $\nu_{p,q}$ and
$\nu_{p^{\prime},q}$, respectively. If

$\epsilon+(1-\epsilon)p\leq
p^{\prime}\quad\text{and}\quad\epsilon+(1-\epsilon)\frac{p}{p+(1-p)q}\leq\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}$
(9.1)

then there exists a coupling between $\nu,\nu^{\prime},Z$ such that
$\left(\eta+Z\right)\leq\eta^{\prime}$. Similarly, if

$(1-\epsilon)p^{\prime}\geq
p\quad\text{and}\quad(1-\epsilon)\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}\geq\frac{p}{p+(1-p)q}$
(9.2)

then there exists a coupling between $\nu,\nu^{\prime},Z$ such that
$\left(\eta^{\prime}-Z\right)\geq\eta$.

###### Proof.

Let $\left\\{\eta_{t}\right\\}_{t}$ and
$\left\\{\eta^{\prime}_{t}\right\\}_{t}$ be the single-site Glauber dynamics
Markov chains on the random cluster model with parameters $(p,q)$ and
$(p^{\prime},q)$, respectively. Let $\left\\{Z_{t}\right\\}_{t}$ be a Glauber
dynamics Markov chain on the state space
$\left\\{0,1\right\\}^{E(\mathbb{T}_{n}^{d})}$ with stationary distribution
given by a product of Bernoulli measures with parameter $\epsilon$. Start with
arbitrary configurations such that $\eta_{0}\equiv\eta^{\prime}_{0}$ and
$Z_{0}(e)=0$ for all $e\in E(\mathbb{T}_{n}^{d})$. Assume that
$\eta_{t}+Z_{t}\leq\eta^{\prime}_{t}$ at some time $t$. We will show that we
can couple the next transition of the chains so that
$\eta_{t+1}+Z_{t+1}\leq\eta^{\prime}_{t+1}$. This establishes the lemma. For
any edge $e$ and configuration $\eta$, let

$\alpha(e,\eta)=\text{$\mathbbm{1}$}\left(\text{$e$ is a cut-edge in
$\eta$}\right).$

In the coupling we will choose the same edge to be updated in all chains. Let
$e$ be such an edge. Then, note that

$\displaystyle\mathbb{P}\left(\left(\eta_{t+1}+Z_{t+1}\right)(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right)$
$\displaystyle=\epsilon+(1-\epsilon)\left(\alpha(e,\eta_{t})\frac{p}{p+(1-p)q}+\left(1-\alpha(e,\eta_{t})\right)p\right).$

Since $\eta_{t}\leq\eta^{\prime}_{t}$ we have that
$\alpha(e,\eta_{t})\geq\alpha(e,\eta_{t}^{\prime})$. So if
$\alpha(e,\eta_{t})=0$ we have that $\alpha(e,\eta^{\prime}_{t})=0$, which
gives

$\displaystyle\mathbb{P}\left(\left(\eta_{t+1}+Z_{t+1}\right)(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right)=\epsilon+(1-\epsilon)p\leq
p^{\prime}=\mathbb{P}\left(\eta_{t+1}^{\prime}(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right),$

where in the first inequality we used (9.1). If $\alpha(e,\eta_{t})=1$, then
we use the second part of (9.1) and that
$\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}\leq p^{\prime}$ to write

$\displaystyle\mathbb{P}\left(\left(\eta_{t+1}+Z_{t+1}\right)(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right)$
$\displaystyle=\epsilon+(1-\epsilon)\frac{p}{p+(1-p)q}$
$\displaystyle\leq\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}$
$\displaystyle\leq\alpha(e,\eta_{t}^{\prime})\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}+\left(1-\alpha(e,\eta_{t}^{\prime})\right)p^{\prime}$
$\displaystyle=\mathbb{P}\left(\eta_{t+1}^{\prime}(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right).$

Therefore, it follows that we can couple the next transition of the Markov
chains so that
$\eta_{t+1}\leq\left(\eta_{t+1}+Z_{t+1}\right)\leq\eta_{t+1}^{\prime}$.
Consequently, we can couple the stationary measures of such chains to obtain
that $\left(\eta+Z\right)\leq\eta^{\prime}$.

For the second part of the lemma, we use the same strategy and analyze the
transition probabilities for $\eta_{t}^{\prime}-Z_{t}$. We have

$\displaystyle\mathbb{P}\left(\left(\eta^{\prime}_{t+1}-Z_{t+1}\right)(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right)$
$\displaystyle=(1-\epsilon)\left(\alpha(e,\eta_{t}^{\prime})\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}+\left(1-\alpha(e,\eta_{t}^{\prime})\right)p^{\prime}\right).$

If $\alpha(e,\eta_{t}^{\prime})=1$ then $\alpha(e,\eta_{t})=1$, yielding

$\displaystyle\mathbb{P}\left(\left(\eta^{\prime}_{t+1}-Z_{t+1}\right)(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right)=(1-\epsilon)\frac{p^{\prime}}{p^{\prime}+(1-p^{\prime})q}$
$\displaystyle\geq\frac{p}{p+(1-p)q}$
$\displaystyle=\mathbb{P}\left(\eta_{t+1}=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right).$

If $\alpha(e,\eta_{t}^{\prime})=0$ then

$\displaystyle\mathbb{P}\left(\left(\eta^{\prime}_{t+1}-Z_{t+1}\right)(e)=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right)=(1-\epsilon)p^{\prime}$
$\displaystyle\geq p$
$\displaystyle\geq\alpha(e,\eta_{t})\frac{p}{p+(1-p)q}+\left(1-\alpha(e,\eta_{t})\right)p$
$\displaystyle=\mathbb{P}\left(\eta_{t+1}=1\mid\eta_{t},\eta^{\prime}_{t},Z_{t}\right).$

Therefore, there exists a coupling such that
$\eta_{t+1}\leq\left(\eta_{t+1}^{\prime}-Z_{t+1}\right)$ and we obtain
$\left(\eta^{\prime}-Z\right)\geq\eta$. ∎

###### Proof of Corollary 1.4.

We only need to check that assumptions (1.3) and (1.4) hold for the random
walk on dynamical random cluster model. For any $q,p$ we have that (1.3)
holds. For $q\geq 1$, (1.4) holds for all $p<p_{\mathrm{c}}^{q}$ using the
following argument. Take
$p^{\prime}=\frac{p+p_{\mathrm{c}}^{q}}{2}\in(p,p_{\mathrm{c}}^{q})$. Take
$\epsilon>0$ small enough so that (9.1) is satisfied. We choose
$\delta=\epsilon/\mu$ and take $\eta$ to be a random cluster configuration of
parameters $p,q$. Note that the probability that a given edge gets refreshed
during $[0,\delta]$ is

$1-e^{-\mu\delta}=1-e^{-\epsilon}\leq\epsilon.$

Therefore, if $Z(e)$ is a Bernoulli random variable of parameter of parameter
$\epsilon$, we can couple $Z(e)$ with the refresh clocks of the dynamical
random cluster so that if $e$ gets refreshed during $[0,\delta]$ then
$Z(e)=1$. Therefore, this coupling gives that $\mathcal{C}_{x}([0,\delta])$ is
contained in the cluster of $x$ inside the configuration $\eta+Z$, which by
Lemma 9.1 is contained inside $\eta^{\prime}$, a random cluster configuration
with parameters $p^{\prime},q$. Then it follows by the sharpness of the phase
transition [5] that the cluster of $x$ in $\eta^{\prime}$ has an exponential
decay, establishing (1.4) and allowing us to obtain the conclusions of
Theorems 1.2 and 1.3 for the random cluster model with $q\geq 1$.

Regarding the case $q<1$, one can deduce the exponential decay of the cluster
$\eta+Z$ only when $p$ is small enough. This becames rather trivial as
regardless of the state of the other edges, we obtain that an edge $e$ is open
during $[0,\delta]$ with probability at most

$\max\left\\{\frac{p}{p+(1-p)q},p\right\\}+\epsilon=\frac{p}{p+(1-p)q}+\epsilon$

which for small enough $p$ can be made smaller than $p_{\mathrm{c}}$, the
critical probability for independent percolation. ∎

## References

  * [1] Luca Avena, Hakan Güldas, Remco van der Hofstad, and Frank den Hollander.  Mixing times of random walks on dynamic configuration models.  Ann. Appl. Probab., 28(4):1977–2002, 08 2018.
  * [2] Luca Avena, Hakan Güldas, Remco van der Hofstad, and Frank den Hollander.  Random walks on dynamic configuration models: a trichotomy.  Stochastic Processes and their Applications, 129(9):3360 – 3375, 2019.
  * [3] K. Ball.  Markov chains, Riesz transforms and Lipschitz maps.  Geometric and Functional Analysis, 2(2):137–172, June 1992.
  * [4] Leran Cai, Thomas Sauerwald, and Luca Zanetti.  Random Walks on Randomly Evolving Graphs.  In Structural Information and Communication Complexity, pages 111–128. Springer, Cham, Switzerland, July 2020.
  * [5] Hugo Duminil-Copin, Aran Raoufi, and Vincent Tassion.  Sharp phase transition for the random-cluster and Potts models via decision trees.  Ann. Of Math., 189(1):75–99, 2019.
  * [6] Geoffrey R Grimmett.  Percolation.  Springer Berlin, Heidelberg, 1999.
  * [7] Jonathan Hermon and Perla Sousi.  A comparison principle for random walk on dynamical percolation.  The Annals of Probability, 48(6):2952 – 2987, 2020.
  * [8] T. M. Liggett, R. H. Schonmann, and A. M. Stacey.  Domination by product measures.  The Annals of Probability, 25(1):71 – 95, 1997.
  * [9] Assaf Naor, Yuval Peres, Oded Schramm, and Scott Sheffield.  Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces.  Duke Math. J., 134(1):165–197, July 2006.
  * [10] Yuval Peres, Perla Sousi, and Jeff Steif.  Mixing time for random walk on supercritical dynamical percolation.  Probability theory and related fields, 176:809–849, 2020.
  * [11] Yuval Peres, Alexandre Stauffer, and Jeffrey E Steif.  Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times.  Probability Theory and Related Fields, 162(3-4):487–530, 2015.
  * [12] Thomas Sauerwald and Luca Zanetti.  Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 93:1–93:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [13] Nobutaka Shimizu and Takeharu Shiraga.  Reversible Random Walks on Dynamic Graphs.  arXiv, February 2021.
  * [14] Perla Sousi and Sam Thomas.  Cutoff for random walk on dynamical Erdős-Rényi graph.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 56(4):2745 – 2773, 2020.