Lower bounding the invariant measure

Let us rearrange weights in the product (5.31) to obtain ratios that involve vertices
in the same small-range component. Let $x \in \mathcal{V}$ and $(x_i)_{i=1}^k$ be the unique sequence of
centers joining $O$ to $x$, possibly empty. Then set

$$
Z'(x) := \prod_{i=1}^{k-1} \frac{\pi_P(\eta(x_{i+1}))q(\eta(x_{i+1}), x_{i+1})}{\pi_P(x_i)q(x_i, \eta(x_i))}. \qquad (5.33)
$$

taking by convention empty products to be equal to 1. By construction

$$
Z(x) = \frac{\pi_P(\eta(x_1))q(\eta(x_1), x_1)}{\pi_P(x_k)q(x_k, \eta(x_k))} Z'(x) \quad (5.34)
$$

Thus to lower bound $Z(x)$ is essentially suffices to bound $Z'(x)$. The idea now is that
the process $Z'(x)$ can be described as a branching random walk on $\mathbb{R}_+^*$ with symmetric
increments. We do not need to dive to much into the theory of branching random
walks, so we only define a branching random walk informally as a Markov field defined
on a Galton-Watson tree.

In our case, the underlying tree $\mathcal{T}$ can be obtained by collapsing all vertices of a
small-range component into one node and keeping only long-range edges. We call this
tree the skeleton tree of $\mathcal{G}$. This tree has naturally a root which identifies with $O$ in $\mathcal{G}$,
while other vertices identify with centers. Thanks to this identification, $Z'$ can be seen
as a random field on $\mathcal{T}$. Write $\mathcal{T}_O$ for the subtree of $\mathcal{T}$ spanned by centers of $\mathcal{G}_O$.

**Lemma 5.10.** Suppose $P$ satisfies (H4') with constant $l \ge 1$. Then for all realization of $\mathcal{G}$ there exists a connected subgraph $\mathcal{G}' \subset \mathcal{G}_O$ containing $\eta(O)$ such that

(i) all vertices of $\mathcal{G}'$ are at $\mathcal{P}$-distance at most $2l$ from their center,

(ii) $Z'(x) = \Theta(1)$ for every center $x \in \mathcal{G}'$,

(iii) with probability $\Theta(1)$, any reversible chain with underlying graph $\mathcal{G}'$ has uniformly lower bounded escape probabilities.

*Proof.* The starting point is that the tree $\mathcal{T}$ and the identification with centers of the quasi-tree can be generated in two steps. Suppose for instance that $P_1$ and $P_2$ are irreducible. Then all small-range components of $\mathcal{G}$ are isomorphic to the unique communicating class of either $P_1$ or $P_2$, so the tree $\mathcal{T}$ is just a $n$-regular tree. In general the tree $\mathcal{T}$ can be described as a two-type Galton-Watson tree. For $i = 1, 2$ and $k \ge 0$, let $M_i(k)$ be the number of communicating classes in $V_i$ with exactly $k$ vertices. The tree $\mathcal{T}$ has the law of the random tree where every vertex of type $i \in \{1, 2\}$ gives rise to $k-1$ children with probability $kM_i(k)/n$, all of types $\bar{i}$, where $\bar{i} = 2$ if $i = 1$ and vice
versa. By Assumption (H3), $M_1(1) = M_1(2) = M_2(1) = 0$, so $\mathcal{T}$ always contains the deterministic tree that alternates between degree 2 and degree 3 vertices.

Suppose now $\mathcal{T}$ is a tree generated according to the previous law. Suppose the type of the root is fixed, which determines the types of all other vertices. Then assign labels to edges of $\mathcal{T}$, consisting of pairs $(u, v)$ such that: $v \in B_P^+(u, \infty)$, $v \neq u$. They need to satisfy the two constraints: 1. the labels on edges incident to a same vertex $x$ share the same first coordinate; 2. if this coordinate is $u$, then for all $v \in B_P^+(u, \infty)$, $v \neq u$ there is an edge incident to $x$ with label $(u, v)$. Because of the first constraint, we extend labels to vertices, calling $u$ the label of $x$. In addition, call the label $(u, v)$ a backbone label if $d_{\text{SR}}(u, v) \le 2$ or $d_{\text{SR}}(v, u) \le 2$, which is symmetric in $(u, v)$. Remark that every vertex $x$ has always one backbone label, nay two if $x$ has type $i=1$. If $\mathcal{T}$ is a tree with such a labelling of the edges, we can construct a quasi-tree $\mathcal{G}$ such that $\mathcal{T}$ is the skeleton tree of $\mathcal{G}$: labels of vertices define the type $\iota$ of centers, while labels of edges detail how the corresponding small-range components are linked to each other. Backbone labels correspond to vertices which are close to their center: if $d_{\text{SR}}(u, v) \le 2$ then (H4') implies that $d_{\text{SR}}(v, u) \le 2l$ so $u, v$ are at bounded distance from each other in both directions.

We then define weights on labelled edges. If $e$ has label $(u, v)$, set

$$b_e = b_{(u,v)} := \frac{\pi_P(v)q(v, \eta(v))}{\pi_P(u)q(u, \eta(u))}. \qquad (5.35)$$

Note that $b_{(u,v)} = b_{(v,u)}^{-1}$. Given a vertex $x \in \mathcal{T}$, we have by construction that $Z'(x) := \prod_{i=1}^k b_{e_i}$ where $(e_i)_{i=1}^k$ is the unique path of edges from the root to $x$ and empty product is equal to 1. From what precedes, if $(u, v)$ is a backbone label then $P(u, v)^k > 0$ for some $k \in [1, 2l]$. Recall that from Assumption (H1) and (H2) there is a constant lower bound $\delta$ on all transition probabilities. Thus

$$b_{(u,v)} \ge \delta^{2l+1} := b_{\min}$$

is bounded below uniformly in $n$, using that $\pi_P(v) \ge \pi_P(u)P^k(u, v)$. Consequently backbone labels imply bounded weights uniformly in $n$.

Now labels can be assigned randomly: suppose $x \in \mathcal{T}$ has type $i \in \{1, 2\}$ and $k-1$ vertices descendant vertices. Pick a communicating class $\mathcal{C}$ of size $k$ in $V_i$ uniformly at random, pick a uniform $u \in \mathcal{C}$ and distribute labels $((u, v))_{v \in \mathcal{C} \setminus \{u\}}$ uniformly over the descendant edges of $x$. With this procedure, the quasi-tree obtained from the random labels has the distribution of $\mathcal{G}$. Furthermore, labels are independent over edges that are not incident to a same vertex.

In particular $Z'_x$ is a product of independent weights over the path from the root to $x$. Furthermore, since every choice in this construction is uniform, the labels are
also uniform over all possible pairs $(u, v)$. In particular an edge is given a label $(u, v)$ or $(v, u)$ with the same probability, which implies it is given a weight $b_{(u,v)}$ or $b_{(v,u)}$ with same probability. Since the latter are inverse of each other we deduce that the distribution of the weight assigned to an edge is symmetric, that is $b_e$ has the same law as $b_e^{-1}$. Then for all $x \in \mathcal{T}$, $Z'_x$ needs also be symmetric as it is a product of independent weights.

We conclude the proof by a comparison with a branching process. We can reason conditional on $\mathcal{T}$, so only labels and the associated weights are random. Consider the power tree $\mathcal{T}_O^{(4)}$ as defined in Proposition 5.6. By definition an edge of $\mathcal{T}_O^{(4)}$ identifies to a 4-tuple of edges in $\mathcal{T}_O$. Let $\mathcal{T}''$ be the tree defined as the connected component of $\eta(O)$ of all edges in $\mathcal{T}_O^{(4)}$ which identify to 4-tuple of edges with backbone labels, and such that the product of weights is above 1. What precedes shows that except $\eta(O)$, every vertex in $\mathcal{T}_O^{(4)}$ has always 4 edges with backbone labels, and the product of weights is above 1 with probability $1/2$. Thus the tree $\mathcal{T}''$ dominates stochastically a Galton Watson tree whose offspring law is binomial $\text{Bin}(4, 1/2)$ and is thus supercritical. This gives back a subtree $\mathcal{T}' \subset \mathcal{T}_O$ of the original tree, which is the one we are looking for. The labels on these edges give rise to a set of vertices which span the desired graph $\mathcal{G}'$. Since all labels on $\mathcal{T}'$ are backbone labels, these vertices are all at distance at most $2l$ from their center, and $Z'(x) \ge b_{\min}^4$ for all $x \in \mathcal{T}'$. It remains to prove the last statement. This is the consequence of the arguments used in the reversible model: from the above comparison with a supercritical Galton-Watson tree, if the latter is infinite, which occurs with probability $\Theta(1)$, then the skeleton tree $\mathcal{T}'$ is sufficiently branching to make any reversible chain on $\mathcal{G}'$ have uniformly lower bounded escape probabilities by Remark 5.12. $\square$

*Proof of Lemma 5.6 with assumption (H4')*. By (5.29), it suffices to bound the Green function $\mathcal{G}_{P_0}$ at $O$. The measure $\nu$ is easily tweaked to give an invariant measure for $P_0$: the graph $\mathcal{G}_O^*$ is still a quasi-tree which can be seen as having $C_O := \{O\} \cup \text{SR}(\eta(O))$ as the small-range component of the root. Then replace $\pi_P$ locally on that small-range component by the invariant measure $\pi_P^*$ of $C_O$. This modification does not affect the field $Z'(x)$ (5.33) thus from (5.34) $Z(x)$ gets only modified by one factor. In the end we obtain an invariant measure $\nu_0$ for $P_0$ given by $\nu_O(x) := \pi_P^*(x)$ if $x \in C_O$ and otherwise

$$ \nu_0(x) := \frac{\pi_P^*(\eta(x_1))q(\eta(x_1), x_1)}{\pi_P(x_k)q(x_k, \eta(x_k))} Z'(x)\pi_P(x) $$

if $(x_i)_{i=1}^k$ is the sequence of centers from $O$ to $x$. In particular, $\eta(x_1) \in C_O$ and $x_k \in B_{\text{SR}}(x, +\infty)$. Consider now the graph $\mathcal{G}' = (\mathcal{V}', \mathcal{E}')$ of Lemma 5.10. For all $x \in \mathcal{V}', Z'(x) \ge c$ and all vertices of $\mathcal{V}'$ are at bounded distance from their centers. As was
argued in the proof of Lemma 5.10, this implies that the ratios between the measures of vertices inside the same small-range component can be bounded uniformly in $n$. Thus

$$ \frac{\pi_P^*(\eta(x_1))}{\nu_0(O)} \frac{\pi_P(x)}{\pi_P(x_k)} = \Theta(1). $$

Since the invariant measure is defined up to multiplicative constant, let us suppose $\pi_P^*$ was taken in order to have $\nu_0(O) = 1$. Using also the fact that the probabilities $q$ are bounded by (H2), we deduce that there exist a constant $c$ independent of $n$ such that for all $x \in \mathcal{V}'$

$$ \nu_0(x) \geq c. $$

On the other hand, let $K$ denote the transition kernel of the simple random walk on $\mathcal{G}'$. The measure $\mu$ defined by $\mu(x) := \deg_{\mathcal{G}'}(x)$ for all $x \in \mathcal{V}'$ is an invariant measure for $K$. Since the graph $\mathcal{G}$ has degrees bounded by $\Delta$, the entries of both $K$ and $\mu$ can be lower bounded by a constant depending only on $\Delta$. We can thus bound

$$ \sup_{x \in \mathcal{V}'} \mu(x)/\nu_0(x) \leq C $$

for some other constant $C > 0$ independent of $n$. Consider now the transition kernels $\bar{P} := (I + \mathcal{P}_0)^{l+1}/2^{l+1}$ and $\bar{K} := (1 - \frac{1}{2C}\frac{\mu}{\nu_0})I + \frac{1}{2C}\frac{\mu}{\nu_0}K$, where $l$ is given by the assumption (H4'). The measure $\nu_0$ is still invariant for $\bar{P}$ but now one also has that $\bar{K}$ is reversible with respect to $\nu_0$.

Let $z \in (0, 1)$. We apply Lemma 5.8 to operators $T_1 := (I - z\bar{K})$ and $T_2 := (I - z\bar{P})$ on the Hilbert space

$$ \ell^2(\mathcal{V}') := \{f : \mathcal{V}' \to \mathbb{R} \mid \langle f, f \rangle_{\nu_0} < \infty\}, \quad \langle f, g \rangle_{\nu_0} := \sum_{x \in \mathcal{V}'} \nu_0(x)f(x)g(x). $$

By (H4') every small-range edge of $\mathcal{G}'$, regardless of the orientation, has positive transition probability under $\bar{P}$, bounded below by $(\delta/2)^{l+1}$. Similarly, if $x, y \in \mathcal{V}'$ and $P(\eta(x), y) > 0$, then $\bar{P}(x, \eta(x)) \geq 2^{-l-1}\mathcal{P}_0(x, y)\mathcal{P}_0(y, \eta(x)) \geq (\delta/2)^{l+1}$ so long-range edges too have a lower bounded probability. Thus for all $x, y \in \mathcal{V}'$

$$ \bar{P}(x, y) \geq \epsilon \bar{K}(x, y) $$

for some constant $\epsilon$. As a consequence $\frac{1}{1-\epsilon}(\bar{P} - \epsilon\bar{K})$ defines a transition kernel with invariant measure $\nu_0$. This defines thus a contracting operator on $\ell^2(\mathcal{V}')$, which implies

$$ \langle (\bar{P} - \epsilon \bar{K}) f, f \rangle_{\nu_0} \leq (1 - \epsilon) \langle f, f \rangle_{\nu_0} $$

and

$$ \langle T_2 f, f \rangle_{\nu_0} \geq \epsilon \langle T_1 f, f \rangle_{\nu_0} $$
for all $f \in \ell^2(\mathcal{V}')$. The reversibility of $\bar{K}$ implying also the self-adjointness of $T_2$ all the assumptions of Lemma 5.8 are satisfied, hence

$$ \langle T_2^{-1} f, f \rangle_{\nu_0} \le \epsilon^{-1} \langle T_1^{-1} f, f \rangle_{\nu_0}. $$

Taking $f$ as the indicator function at $O \in \mathcal{V}'$ we obtain

$$ G_{\bar{P}}(O, O | z) \le \epsilon^{-1} G_{\bar{K}}(O, O | z) $$

with $G_{\bar{P}}(O, O | z) = \sum_{t \ge 0} \bar{P}^t(O, O)z^t$ and similarly for $\bar{K}$. Take the limit $z \to 1$ from below to obtain

$$ G_{\bar{P}}(O, O) \le \epsilon^{-1} G_{\bar{K}}(O, O) $$

Now we claim that Green functions of $\bar{P}$ and $\mathcal{P}_0$ can be related as

$$ G_{\mathcal{P}_0}(O, O) \le 2^{l-1}(l+1) G_{\bar{P}}(O, O). $$

Indeed, $\bar{P}$ is obtained by applying the successive operations of "lazification" and taking the power $l+1$. It can be checked that the "lazification" multiplies the Green function by 2. Then let $(\mathcal{Y}_t)_{t \ge 0}$ be the lazy chain with matrix $(I + \mathcal{P}_0)/2$. Taking the power $l+1$ of this chain comes down to consider the chain only at times which are a multiple of $l+1$. Now for all $m \in [0, l]$, for all $t \ge 1$, laziness implies

$$ \mathbb{P}_O[\mathcal{Y}_{(l+1)t} = O] \ge \mathbb{P}_O[\mathcal{Y}_{(l+1)t-m} = O]/2^m $$

so we can average and get

$$ \mathbb{P}_O[\mathcal{Y}_{(l+1)t} = O] \ge \sum_{m=0}^{l} \frac{1}{2^m(l+1)} \mathbb{P}_O[\mathcal{Y}_{(l+1)t-m} = O] $$

Then summing over $t$ yields:

$$ \begin{aligned} G_{\bar{P}}(O, O) &\ge \sum_{m=0}^{l} \frac{1}{2^m(l+1)} \sum_{t=-m \bmod l+1}^{l} \mathbb{P}_O[\mathcal{Y}_t = O] \\ &\ge \frac{1}{2^l(l+1)} G_{(l+\mathcal{P}_0)/2}(O, O) \\ &= \frac{1}{2^{l-1}(l+1)} G_{\mathcal{P}_0}(O, O). \end{aligned} $$

Finally it remains to upper bound the Green function of $\bar{K}$. Since it is a reversible chain, Point (iii) of Lemma 5.10 shows there is an event of probability $\Theta(1)$ on which it has uniformly lower bounded escape probabilities which from (5.29) implies its Green function is uniformly upper bounded at the root. $\square$
### 5.5.4 General case: $o(n)$ transient or close to transient states

We now consider the general case where we suppose only (H4). In this case there can be $o(n)$ vertices around which it not possible to revert the transitions in $l$ steps. Transient states are such vertices, so we call these vertices close to transient. There are two issues that prevent the previous proof to apply directly: first if $P$ contains transient states, $\pi_P$ takes the value 0 so the measure $\nu$ as defined in Lemma 5.9 cannot be invariant, and the chain $(\mathcal{X}_t)_{t \ge 0}$ is incidentally not irreducible. This problem is fixed by the fact that we need only a "sub-invariant" measure, satisfying $\nu P \le \nu$, to apply the comparison argument, which allows for a loss of mass at transient states. Secondly, even without genuine transient states, the comparison with a reversible chain fails at close to transient states. We will argue that since these are in number $o(n)$, they are sufficiently rare to be discarded.

**Quasi-stationary measures and transient classes** Our goal is to define a sub-invariant measure which puts mass on transient states if there are any. We call such measures quasi-stationary, by analogy to classical quasi-stationary measures, which describe the limiting behaviour of absorbing Markov chains before absorption. Transitioning along a non-backtracking edge, that is an edge that can only be crossed in one direction, is indeed very similar to absorption.

Let $(Y_t)_{t \ge 0}$ be a Markov chain on a countable state space $W$ with transition kernel $Q$. A set $A \subset W$ is called absorbing if for all $x \in A$, $Q(x, A) = 1$. Suppose the chain contains a non-empty absorbing set $A$ and write $B$ for its complement. A measure $\mu$ on $B$ is called quasi-stationary if for all $t \ge 0$, for all $y \in B$,

$$ \mu(y) = \sum_{x \in B} \mu(x) \mathbb{P}_x [Y_t = y, \tau_A > t] $$

As for classical stationary measures, quasi-stationary measures can be obtained from the Perron-Frobenius theorem. Let $Q_B$ the restriction of $Q$ to $B$: this is a sub-stochastic matrix, with non-negative entries, hence it admits a maximal positive eigenvalue $\lambda \le 1$, which in turn admits left and right eigenvectors with all positive entries. Since $Q_B^t(x, y) = \mathbb{P}_x [Y_t = y, \tau_A > t]$, we deduce that left eigenvectors $\mu$ with positive entries define quasi-stationary measures on $B$. Note also that $\mu Q_B = \lambda \mu \le \mu$ is a sub-invariant measure.

*Remark 5.13.* Our notion of quasi-stationary measures differs slightly from the classical one which not only intersects but conditions by the event that $\tau_A > t$.

Now, if we suppose that $W$ contains transient and recurrent states, the latter form an absorbing set. A quasi-stationary measure in this setting consists thus of a quasi-
stationary measure on the set of transient states, with respect to the set of recurrent states.

**Escape probability** Let us move back to lower bounding the escape probability. We can in fact prove a slightly stronger result, namely allowing for a positive fraction $\alpha n$ of close to transient states, with $\alpha$ small enough. $P$ contains in particular at most $\alpha n$ genuine transient states. If there are such transient states, there exist edges $(x, y)$ between the transient and recurrent classes such that $P(x, y) > 0$ but $P^k(y, x) = 0$ for all $k \ge 0$. Call these non-backtracking edges. Non-backtracking edges in $G$ obviously give non-backtracking edges in $G'$. We apply the argument with a version of the Green function $G_{P_0}$ (5.29) killed at non-backtracking edges. Les $G'$ denote the connected component of the root in $G$ after deletion of the non-backtracking edges and consider the transition kernel $P'_0$ given by the restriction of $P_0$ to $G'$, which is a sub-Markov operator. The corresponding Green function $G_{P'_0}(O, O)$ counts the average number of visits to $O$ before crossing a non-backtracking edge. Crossing a non-backtracking edge of $G'_O$ obviously prevents the chain from going back to $O$, hence the number of visits to $O$ remains a geometric variable of parameter $q_{\text{Esc}}(\eta(O))$ and thus $q_{\text{Esc}}(\eta(O)) = G_{P'_0}(O, O)^{-1}$.

We thus aim to upper bound this Green function uniformly in $n$. After truncation, the remaining long-range edges in $G'$ connect small-range components which are either both isomorphic to a communicating class of $G$, or the component furthest from the root is isomorphic to a transient class. We can apply the same idea as in Lemma 5.9 to find a sub-invariant measure, considering quasi-stationary measures on transient classes. Let $\pi_P$ be a positive combination, with bounded coefficients, of invariant measures on communicating classes and quasi-stationary measures on transient states. Then the exact same formula as in Lemma 5.9 yields a sub-invariant measure.

Next we truncate $G'$ a second time to get rid of close to transient states as well. Let $G''$ be the subgraph of $G'$ spanned by the set $V''$ of vertices which do not identify under $\iota$ to such states. By construction, the operator $(I + P')^l/2^l$ can be compared edge-wise with the simple random walk on $G''$. We can thus apply Lemma 5.8 provided we have a comparison between sub-invariant measures. This can be done similarly by studying the random field $Z$, the only difference with the previous section is that we need we only look at vertices in $V''$. This can be done by modifying the definition of the "backbone labels" in the proof of Lemma 5.10, adding the requirement that a label $(u, v)$ is a backbone label only if $u$ and $v$ are not close to transient. Provided $\alpha$ is small enough, the expected number of backbone labels can be made strictly larger than one, so that the comparison with a supercritical Galton-Watson tree still holds. One last
think to be aware of is that we want a result conditional on $\iota(\eta(O))$, which can be
close to transient and thus $\eta(O) \notin G''$. In this case the argument is to be applied to
another subquasi-tree of $G_O$ at bounded distance from $\eta(O)$.

## 5.6 Analysis on the quasi-tree II: Markovian regeneration structure

Proposition 5.5 implies in particular that the Markov chain ($\mathcal{X}_t$)$_{t \ge 0}$ is almost surely transient. As a consequence, the shortest path from $O$ to $\mathcal{X}_t$ eventually has to go through a unique sequence of long-range edges ($\xi_i$)$_{i=1}^\infty$, which is called the *loop-erased chain*. Among the edges of the loop-erased chain, some have the property to be crossed only once. Thanks to this property, these so-called *regeneration edges* yield a Markov decomposition of the quasi-tree which we will use in the next section to prove concentration of the drift and entropy of the harmonic measure. The regeneration process will also be used later to compute the approximate invariant measure $\hat{\pi}$.

### 5.6.1 Markov renewal processes

We start with general results about Markov renewal processes that will be necessary
in the sequel. The theory of Markov renewal processes is certainly not new, however
we could not find references proving the results established in this section.

**Definition 5.5.** Let $S$ be a countable state space and $E$ a Polish space. Consider a process $(Y, Z) = (Y_k, Z_k)_{k \ge 0}$ taking values in $S \times E$, satisfying for all $k \ge 1$, $x, y \in S$, $z \in E$,

$$ \mathbb{P}[Y_k = y, Z_k = z \mid Y_{k-1} = x, Z_{k-1}, \dots, Y_0, Z_0] = \mathbb{P}[Y'_1 = y, Z'_1 = z \mid Y_0 = x], \quad (M1) $$

where $(Y'_1, Z'_1)$ is an independent copy of $(Y_1, Z_1)$. This process is thus a Markov chain with a stronger Markov property that the usual one, in that the time dependence occurs only through the $Y$-coordinate. In particular $Y = (Y_k)_{k \ge 0}$ is a Markov chain on $S$.

A Markov renewal process is a process $(Y_k, T_k)_{k \ge 0}$ is a process taking values in $S \times \mathbb{N}$ such that $(Y_k, T_k - T_{k-1})_{k \ge 0}$ satisfies (M1) and $T_k - T_{k-1} \ge 1$ a.s. for all $k \ge 1$, taking $T_{-1} := 0$. The delay $T_0$ can have arbitrary distribution. We call transition kernels of $(Y, T)$ the family of kernels $(Q_t)_{t \ge 1}$, where for each $t \ge 1$,

$$ Q_t(x, y) := \mathbb{P}[Y_1 = y, T_1 = t \mid Y_0 = x, T_0 = 0] = \mathbb{P}[Y_1 = y, T_1 - T_0 = t \mid Y_0 = x]. $$

Notice then that $Y$ has transition kernel $Q := \sum_{t \ge 1} Q_t$.
Remark 5.14. If $(Y, Z)$ satisfies (M1), the initial pair $(Y_0, Z_0)$ can an have arbitrarily law. As usual, if $\nu$ is a probability measure on $S \times E$ we write

$$ \mathbb{P}_{\nu} := \sum_{y \in S} \int \mathbb{P}[\cdot | Y_0 = y, Z = z] \nu(y, dz). $$

On the other hand, the (M1) implies that $(Y_k, Z_k)_{k \ge 1}$ conditional on $Y_0$ is independent of $Z_0$. Thus if we are interested in a quantity that is measureable only with respect to $(Y_k, Z_k)_{k \ge 1}$, we will slightly abuse notation by writing $\mathbb{P}_u := \mathbb{P}[\cdot | Y_0 = u]$ (and write similarly for expectation), and by extension $\mathbb{P}_{\mu} := \sum_{y \in S} \mu(y) \mathbb{P}_y$ for a measure $\mu$ on $S$. In particular, note that if $\mu$ is an invariant measure for $Y$, the process $(Y_k, Z_k)_{k \ge 1}$ becomes stationary under $\mathbb{P}_{\mu}$. In the sequel if $Y$ is positive recurrent, we only consider invariant measures which are probability distributions.

**Lemma 5.11.** Let $S$ be a countable set and consider a process $(Y_k, Z_k)_{k \ge 0}$ taking values in $S \times \mathbb{R}_+$ which satisfies (M1). Suppose there exists $\alpha \in (0, 1], \theta > 0$ such that $\mathbb{E}[e^{\theta Z_0^\alpha}] < \infty$ and $\max_{u \in S} \mathbb{E}_u[e^{\theta Z_1^\alpha}] < \infty$. Then for all $k \ge 0$,

$$ \mathbb{E}[e^{\theta(\sum_{i=0}^k Z_i)^\alpha}] \le \left( \max_{u \in S} \mathbb{E}_u[e^{\theta Z_1^\alpha}] \right)^k. \quad (5.36) $$

As a consequence, there exists $C, C' > 0$ depending on $\theta$, $\mathbb{E}[e^{\theta Z_0^\alpha}]$ and $\max_{u \in S} \mathbb{E}_u[e^{\theta Z_1^\alpha}]$ such that for all $k \ge 0$,

$$ \mathbb{P}\left[\sum_{i=0}^{k} Z_i > Ck^{1/\alpha}\right] \le e^{-C'k}. \quad (5.37) $$

*Proof.* Let $\alpha \in (0, 1], \theta > 0$ such that $\mathbb{E}[e^{\theta Z_0^\alpha}] < \infty$ and $\max_{u \in S} \mathbb{E}_u[e^{\theta Z_1^\alpha}] < \infty$. Let $(\mathcal{F}_k)_{k \ge 0}$ denote the standard filtration of $(Y, Z)$. Since $\alpha \le 1$, $(x+y)^\alpha \le x^\alpha + y^\alpha$ for all $x, y \ge 0$. Consequently Markov's property used with (M1) implies

$$ \begin{aligned} \mathbb{E}[e^{\theta(\sum_{i=0}^k Z_i)^\alpha}] &= \mathbb{E}[e^{\theta(\sum_{i=0}^{k-1} Z_i)^\alpha} \mathbb{E}[e^{\theta Z_k^\alpha} | \mathcal{F}_{k-1}]] \\ &= \mathbb{E}[e^{\theta(\sum_{i=0}^{k-1} Z_i)^\alpha} \mathbb{E}_{Y_{k-1}}[e^{\theta(Z_1')^\alpha}]] \end{aligned} $$

where $Z_1'$ denotes an independent copy of $Z_1$. Thus

$$ \mathbb{E}[e^{\theta(\sum_{i=0}^k Z_i)^\alpha}] \le \max_{u \in S} \mathbb{E}_u[e^{\theta Z_1^\alpha}] \mathbb{E}[e^{\theta(\sum_{i=0}^{k-1} Z_i)^\alpha}] $$

from which the first inequality follows by induction. The second is an application of Chernoff's bound. $\square$

The next results specify to the setting where the process $Z$ takes integer values. In particular we state analogs of classical renewal theorems in the context of a Markov renewal process $(Y, T)$. The following generalizes the so-called elementary renewal theorem.
**Proposition 5.7.** Let $(Y, T)$ be a Markov renewal process with state space $S$ such that $\max_{u \in S} \mathbb{E}_u [T_1] < \infty$ and $Y$ is positive recurrent with stationary distribution $\mu$. Given $t \ge 0$ let

$$N_t := \sup\{k \ge 0, T_k \le t\}.$$

Then a.s.

$$\lim_{k \to \infty} \frac{T_k}{k} = \mathbb{E}_{\mu}[T_1] \qquad (5.38)$$

and

$$\lim_{t \to \infty} \frac{N_t}{t} = \frac{1}{\mathbb{E}_{\mu}[T_1]} \qquad (5.39)$$

*Proof of Proposition 5.7.* The laws of large numbers are consequences of the ergodic theorem applied to two different Markov chains.

For $T_k$, consider the pair $(Y_k, T_k - T_{k-1})_{k \ge 0}$, with $T_{-1} := 0$, which by definition satisfies (M1). It was noted in Remark 5.14 that $\mathbb{P}_\mu$ is a stationary distribution for this chain. Hence the law of large numbers follows from the ergodic theorem applied to the ergodic averages of the projection onto the second coordinate.

Let us move to $N_t$. Consider the Markov chain $(U_k)_{k \ge 0}$ on $S \times \mathbb{N}$ defined by the transition probabilities

$$K((x, 0), (y, t-1)) = Q_t(x, y) \qquad K((x, t), (x, t-1)) = 1$$

for all $t \ge 1$ and $x, y \in S$. This chain can be thought of as representing $Y$ together with the waiting time until the next renewal: letting $\tau_k$ be the $k$-th successive hitting time of $S \times \{0\}$, the $S$-coordinate of $(U_{\tau_k})_{k \ge 1}$ has the distribution of $(Y_k)_{k \ge 0}$, given $Y_0 = U_0$. The number of jumps $N_t$ made before time $t \ge 0$ is thus the number of such hitting times that occurred before $t$. By the ergodic theorem for Markov chains, one immediately gets

$$\lim_{t \to \infty} \frac{N_t}{t} = \tilde{\mu}(S \times \{0\})$$

where $\tilde{\mu}$ is the unique stationary measure of the Markov chain $(U_k)_{k \ge 0}$. As can be checked easily, it is given by:

$$\tilde{\mu}(x, t) = \frac{\mathbb{P}_{\mu}[X_1 = y, T_1 > t]}{\mathbb{E}_{\mu}[T_1]} \qquad (5.40)$$

for all $x \in S, t \ge 0$. In particular $\tilde{\mu}(S \times \{0\}) = \mathbb{E}_{\mu}[T_1]^{-1}$. $\square$

The two following Propositions establish mixing results for a Markov renewal process $(Y, T)$. These are not necessary for the asymptotic analysis on the quasi-tree but will be used to essentially compute the annealed laws of $\mathcal{X}$ and $X$ and obtain the value of the limiting measure $\hat{\pi}$. Proposition 5.9 is an analog of the classical renewal theorem. With a quantitative bound on the speed of convergence. To prove it, we establish first
a stronger result in Proposition 5.8, namely a mixing property for the whole process $(Y, T)$, where $T$ is allowed here to take negative values. Since $T$ is unbounded mixing is here understood as the fact that the process forgets about its starting state.

**Proposition 5.8.** Let $(Y_k, T_k - T_{k-1})_{k \ge 0}$ satisfy (M1), with $T_{-1} := 0$ and $T_k - T_{k-1} \in \mathbb{Z}$ a.s. for all $k \ge 0$. Suppose $Y$ is positive recurrent, irreducible and aperiodic. Let $Q_t(x, y) := \mathbb{P}[Y_1 = y, T_1 - T_0 = t | Y_0 = x]$ for all $t \in \mathbb{Z}$ and

$$ \alpha := \min_{x \in S} \sum_{\substack{t \in \mathbb{Z} \\ y \in S}} (Q_t(x, y) \wedge Q_{t+1}(x, y)). $$

Consider two starting probability distributions $\nu_1, \nu_2$ on $S \times \mathbb{Z}$. Given $\varepsilon \in (0, 1)$, let $t_{\text{mix}}^{(Y)}(\varepsilon)$ denote the $\varepsilon$-mixing time of $(Y_k)_{k \ge 0}$ and $K(\varepsilon) \ge 0$ be the minimal integer such that

$$ \sup_{\nu} \mathbb{P}_{\nu} [|T_0 - T'_0| > K(\varepsilon)] \le \varepsilon, $$

where the supremum is over all couplings $((Y_0, T_0), (Y'_0, T'_0))$ of $\nu_1$ and $\nu_2$. Then for all $\varepsilon \in (0, 1)$, there exists $C(\varepsilon) \ge 0$ such that

$$ \| \mathbb{P}_{\nu_1} [(Y_k, T_k) = \cdot] - \mathbb{P}_{\nu_2} [(Y_k, T_k) = \cdot] \|_{\text{TV}} \le \varepsilon $$

for all

$$ k \ge \frac{C(\varepsilon)}{\alpha} \left( t_{\text{mix}}^{(Y)}(\varepsilon) \max_{u \in S} \mathbb{E}_u |T_1| + K(\varepsilon) \right)^2. \quad (5.41) $$

*Proof of Proposition 5.8.* The proof is based on coupling arguments. If the $Y_k$ are iid, $T_k$ becomes the sum of iid random variables on $\mathbb{Z}$, ie a random walk on $\mathbb{Z}$. Two random walks on $\mathbb{Z}$ identically distributed but started apart from a distance $A$ can be coupled to meet at a random time $\tau$ which satisfies $\mathbb{P}[\tau > k] \le CA/\sqrt{k}$ for some constant $C > 0$. The argument can be found in [120] and [119][II.14], where the coupling is called Mineka coupling. In the general case where $Y_k$ are not iid, the idea is to first couple the chains $Y_k$ started at different states to make them coincide, after which one can adapt the Mineka coupling to make the subsequent variables $T_k$ coalesce.

Suppose $((Y, T), (Y', T'))$ is a coupling of two versions of the process $(Y_k, T_k)_{k \ge 0}$ started at $\nu_1$ and $\nu_2$ respectively. Let $\tau := \inf\{k \ge 0 : (Y_k, T_k) = (Y'_k, T'_k)\}$. If the coupling is such that the two processes coincide after the coalescence time $\tau$, one has

$$ \| \mathbb{P}[(Y_k, T_k) = \cdot] - \mathbb{P}[(Y'_k, T'_k) = \cdot] \|_{\text{TV}} \le \mathbb{P}[\tau > k]. $$

We now precise such a coupling. Let $\varepsilon \in (0, 1)$ and $k_0 := t_{\text{mix}}^{(Y)}(\varepsilon)$. The coupling is actually started at $k_0$: couple $(Y_{k_0}, T_{k_0})$ and $(Y'_{k_0}, T'_{k_0})$ in order to have an optimal coupling of $Y_{k_0}$ and $Y'_{k_0}$. Thus

$$ \mathbb{P}[Y_{k_0} \ne Y'_{k_0}] = \| \mathbb{P}[Y_{k_0} = \cdot] - \mathbb{P}[Y'_{k_0} = \cdot] \|_{\text{TV}} \le 2 \| \mathbb{P}[Y_{k_0} = \cdot] - \mu \|_{\text{TV}} \le 2\varepsilon, \quad (5.42) $$
where $\mu$ is the stationary measure of $Y$. Then for all $k \ge k_0$, conditional on $Y_k = Y'_k$ draw $Y_{k+1}, Y'_{k+1}, S_{k+1}, S'_{k+1}$ according to the distribution:

$$ \mathbb{P}[Y_{k+1} = Y'_{k+1} = y, S_{k+1} = t-1, S'_{k+1} = t \mid Y_k = Y'_k = x] = \alpha_{t-1}(x, y) $$

$$ \mathbb{P}[Y_{k+1} = Y'_{k+1} = y, S_{k+1} = t, S'_{k+1} = t-1 \mid Y_k = Y'_k = x] = \alpha_{t-1}(x, y) $$

$$ \mathbb{P}[Y_{k+1} = Y'_{k+1} = y, S_{k+1} = t, S'_{k+1} = t \mid Y_k = Y'_k = x] = Q_t(x, y) - \alpha_{t-1}(x, y) - \alpha_t(x, y) $$

writing $\alpha_t(x, y) := Q_t(x, y) \wedge Q_{t+1}(x, y)$. It is readily seen that

$$ \mathbb{P}_x[Y_{k+1} = y, S_{k+1} = t \mid Y_k = x] = Q_t(x, y) = \mathbb{P}_x[Y'_{k+1} = y, S'_{k+1} = t \mid Y'_k = x]. $$

Therefore if $Y_k = Y'_k$ setting $T_{k+1} := T_k + S_{k+1}$, $T'_{k+1} := T'_k + S'_{k+1}$ yields a coupling of $(Y_{k+1}, T_{k+1}), (Y'_{k+1}, T'_{k+1})$ with $Y_{k+1} = Y'_{k+1}$. Consequently, this can be used to couple the two processes $(Y, T), (Y', T')$ for every step after the coalescence of $Y$ and $Y'$, so that the $Y$-coordinate stays identical. Once the $T$-coordinate coalesce, we couple the two processes so that they coincide indefinitely. We now bound the tail of the stopping time $\tau$ under this coupling.

Let $\tau_1 := \inf\{k \ge k_0 : Y_k = Y'_k\}$ and for all $k \ge 0$, $Z_k := \sum_{i=\tau_1}^k S_k - S'_k$. Observe that $(Y_{\tau_1+k}, Z_k - Z_{k-1})_{k \ge 0}$ (with $Z_{-1} := 0$) satisfies the (M1) property. In addition, for every $k \ge 0$, conditional on $Y_{\tau_1+k} = x$, $Z_{k+1} - Z_k$ has symmetric distribution in $\{-1, 0, 1\}$ a.s. and

$$ \mathbb{P}[Z_{k+1} - Z_k = 1 \mid Y_k = x] = \sum_{t \ge 1} \sum_{y \in S} \alpha_t(x, y) \ge \alpha. \quad (5.43) $$

On the event $\{\tau_1 = k_0\}$, for all $k \ge 0$ we can decompose

$$ T_{k_0+k} - T'_{k_0+k} = T_{k_0} - T'_{k_0} + Z_k $$

which implies that $\tau = k_0 + \inf\{k \ge 0 : Z_k = T'_{k_0} - T_{k_0}\}$. Letting $\tilde{\tau}_a$ be the hitting time of $a \in \mathbb{Z}$ by the process $Z$, we deduce from Markov's property that for all $k \ge 0$ and $A > 0$,

$$ \mathbb{P}[\tau > k_0 + k] \le \mathbb{P}[Y_{k_0} \ne Y'_{k_0}] + \mathbb{P}[|T_{k_0} - T'_{k_0}| > A] + \max_{a \in [-A, A]} \max_{u \in S} \mathbb{P}_{(u, 0)}[\tilde{\tau}_a > k]. $$

By (5.42) the first term is smaller than $2\varepsilon$. For the second term, bound

$$ \mathbb{P}[|T_{k_0} - T'_{k_0}| > K(\varepsilon) + A] \le \mathbb{P}[|T_0 - T'_{0}| > K(\varepsilon)] + \mathbb{P}[|(T_{k_0} - T_0) - (T'_{k_0} - T'_{0})| > A]. $$

By definition of $K(\varepsilon)$ the first term is bounded by $\varepsilon$. The second can be bounded by triangle inequality and Markov's inequality to obtain

$$ \mathbb{P}[|T_{k_0} - T'_{k_0}| > K(\varepsilon) + A] \le \varepsilon + \frac{2k_0 \max_{u \in S} \mathbb{E}_u [T_1]}{A} \le 2\varepsilon $$

for $A := 2k_0 \max_{u \in S} \mathbb{E}_u [T_1]/\varepsilon$. The last term is bounded as follows. First, notice that since the variables $Z_k$ are bounded by 1 in absolute value, the maximal probability is
obtained for $a = \pm A$, and from the symmetry of $Z_{k+1} - Z_k$ we can suppose $a = A$. Then we claim that there exists a constant $C \ge 1$, such that for all $k \ge 0$

$$ \max_{u \in S} \mathbb{P}_{(u,0)} [\tilde{\tau}_A > k] \le \frac{CA}{\sqrt{\alpha k}}. $$

Provided the claim holds, we get that the right-hand side is below $\epsilon$ for $k \ge C^2 A^2 / (\alpha \epsilon^2)$. Combining with the previous choices of $k_0$ and $A$, this yields eventually that

$$ \| \mathbb{P}[(Y_k, T_k) = \cdot] - \mathbb{P}[(Y'_k, T'_k) = \cdot] \|_{\text{TV}} \le 5\epsilon $$

for

$$ k \ge t_{\text{mix}}^{(Y)}(\epsilon) + \frac{C^2(K(\epsilon) + 2t_{\text{mix}}^{(Y)}(\epsilon) \max_{u \in S} \mathbb{E}_u [T_1])^2}{\alpha \epsilon^4}, $$

proving the result.

Let us now prove the claim: for all $k \ge 1$, let $N_k := |\{i \le k : Z_i - Z_{i-1} \ne 0\}|$ and define $\tilde{Z}_k$ as the sum of the first $k$ non zero variables $Z_i - Z_{i-1}$. By (5.43), for all $u \in S$, $N_k$ dominates stochastically a binomial random variable $\text{Bin}(k, 2\alpha)$ and from the symmetry of the increments the process $\tilde{Z}$ is the simple random walk on $\mathbb{Z}$. Letting $\tau_A^{(\text{SRW})}$ denote the hitting time of $A$ by $\tilde{Z}$, [71][III 7.5] shows

$$ \mathbb{P}_0[\tau_A^{(\text{SRW})} = k] = \frac{A}{n} \left(\frac{k}{A+k/2}\right) 2^{-k} \le C \frac{A}{k^{3/2}}, $$

for some constant $C > 0$ independent of $k$ and $A$. Summing over $k$ implies

$$ \mathbb{P}_0[\tau_A^{(\text{SRW})} > k] \le \frac{C'A}{\sqrt{k}} $$

for some other constant $C' > 0$. Thus

$$ \begin{aligned} \mathbb{P}_{(u,0)}[\tilde{\tau}_A > k] &\le \mathbb{P}_u[\tilde{\tau}_A > k, N_k \ge \alpha k] + \mathbb{P}_u[N_k < \alpha k] \\ &\le \mathbb{P}_0[\tau_A^{(\text{SRW})} > [\alpha k]] + \mathbb{P}[|\text{Bin}(k, 2\alpha) - 2\alpha k| > \alpha k] \\ &\le \frac{C'A}{\sqrt{\alpha k}} + \frac{2(1-2\alpha)}{\alpha k} \end{aligned} $$

using Chebychev's inequality, which proves the claim. $\square$

**Proposition 5.9.** Let $(Y, T)$ be a Markov renewal process with state space $S$, such that $\max_{u \in S} \mathbb{E}_u [T_1] < \infty$ and $Y$ is positive recurrent with stationary distribution $\mu$, irreducible and aperiodic. Let $\alpha$ be as in Proposition 5.8 and suppose that $\alpha > 0$. For all probability distribution $\nu$ on $S \times \mathbb{N}$,

$$ \sum_{y \in S} \left| \mathbb{P}_{\nu} [\exists k \ge 0 : Y_k = y, T_k = t] - \frac{\mu(y)}{\mathbb{E}_{\mu}[T_1]} \right| \xrightarrow{t \to \infty} 0. \qquad (5.44) $$
More precisely, given $\varepsilon \in (0, 1)$, let $K_\nu(\varepsilon)$ be the minimal integer such that

$$ \mathbb{P}_{\nu}[T_0 > K_{\nu}(\varepsilon)] \leq \varepsilon. $$

There exists $C(\varepsilon) > 0$ such that for all probability distribution $\nu$ on $S \times \mathbb{N}$,

$$ \sum_{y \in S} \left| \mathbb{P}_{\nu}[\exists k \geq 0 : Y_k = y, T_k = t] - \frac{\mu(y)}{\mathbb{E}_{\mu}[T_1]} \right| \leq \varepsilon $$

for all

$$ t \geq \frac{C(\varepsilon)}{\alpha} \left( t_{\text{mix}}^{(Y)}(\varepsilon) \max_{u \in S} \mathbb{E}_u [T_1] + K_{\nu}(\varepsilon) + \frac{\mathbb{E}_{\mu}[T_1^2]}{\mathbb{E}_{\mu}[T_1]} \right)^2 \max_v \mathbb{E}_v [T_1] \quad (5.45) $$

where $t_{\text{mix}}^{(Y)}(\varepsilon)$ denotes the $\varepsilon$-mixing time of $Y$.

*Proof of Proposition 5.9.* Consider the Markov chain $(U_k)_{k \geq 0}$ on $S \times \mathbb{N}$ considered in the proof of Proposition 5.7. Then for all starting measure $\nu$ and $t \geq 0$

$$ u_t(\nu, y) := \mathbb{P}_{\nu}[\exists k \geq 0 : Y_k = y, T_k = t] = \mathbb{P}_{\nu}[U_t = (y, 0)] \quad (5.46) $$

It was proved in the proof of Proposition 5.7 that $U$ has unique invariant measure given by $\tilde{\mu}(x, t) = \mathbb{P}_{\mu}[Y_1 = y, T_1 > t] / \mathbb{E}_{\mu}[T_1]$. Thus if one can prove that $U$ is aperiodic, the convergence theorem for Markov chains directly implies that $u_t(\nu, y) \to \tilde{\mu}(y, 0) = \mu(y) / \mathbb{E}_{\mu}[T_1]$. It is easily proved that $U$ is aperiodic from the assumptions that $Y$ converges to $\mu$ and $\alpha > 0$. Actually, we do not need even to check aperiodicity. The coupling argument that we use afterwards implies the convergence, which implies in turn aperiodicity.

Let $\varepsilon \in (0, 1)$. Let $k_0 = k_0(\varepsilon)$ be the right-hand side of 5.41. By Proposition 5.8 there exists a coupling of two versions of $(Y, T)$ started at $\nu$ and $\tilde{\mu}$, with coalescence time $\kappa$ such that

$$ \mathbb{P}[\kappa > k_0] \leq \varepsilon. $$

These processes can in turn be coupled in an obvious way with two versions $U^{(\nu)}$, $U^{(\tilde{\mu})}$ of $U$ started with distributions $\nu$ and $\tilde{\mu}$ respectively. Then notice that the two processes $U^{(\nu)}$, $U^{(\tilde{\mu})}$ coincide after time $T_{\kappa}$, therefore $T_{\kappa}$ is a coupling time and we deduce

$$ \| \mathbb{P}_{\nu}[U_t = \cdot] - \tilde{\mu} \|_{\text{TV}} \leq \mathbb{P}[T_{\kappa} > t]. $$

Since the sequence $(T_i)_{i \geq 0}$ is increasing, the previous tail probability can be bounded as

$$ \mathbb{P}[T_{\kappa} > t] \leq \mathbb{P}[\kappa > k_0] + \mathbb{P}_{\nu}[T_{k_0} > t]. $$
The first term is bounded by $\epsilon$. The second term can be bounded by Markov's inequality as

$$ \mathbb{P}_{\nu}[T_{k_0} > t] \leq \frac{k_0 \max_{u \in S} \mathbb{E}_u[T_1]}{t} \leq \epsilon $$

for $t \geq k_0 \max_{u \in S} \mathbb{E}_u[T_1]/\epsilon$. Let us now explicit the value of $k_0$. We first bound for the worst possible coupling of $\nu$ and $\tilde{\mu}$,

$$ \begin{aligned} \mathbb{P}[|T_0 - T'_0| > K_{\nu}(\epsilon) + k] &\leq \mathbb{P}_{\nu}[T_0 > K_{\nu}(\epsilon)] + \mathbb{P}_{\tilde{\mu}}[T_0 > k] \\ &\leq \epsilon + \mathbb{E}_{\mu}[(T_1 - k - 1)_+] / \mathbb{E}_{\mu}[T_1] \end{aligned} $$

using the definition of $K_{\nu}(\epsilon)$ and the expression of $\tilde{\mu}$. Then by Markov's inequality

$$ \begin{aligned} \mathbb{E}_{\mu}[(T_1 - k - 1)_+] &= \sum_{t \geq k+1} \mathbb{P}_{\mu}[T_1 > t] \\ &\leq \sum_{t \geq k+1} \frac{\mathbb{E}_{\mu}[T_1^2]}{t^2} \leq \frac{C \mathbb{E}_{\mu}[T_1^2]}{k} \end{aligned} $$

for some constant $C > 0$. Thus $\mathbb{P}[|T_0 - T'_0| > K_{\nu}(\epsilon) + k] \leq 2\epsilon$ for all $k \geq C \mathbb{E}_{\mu}[T_1^2]/(\mathbb{E}_{\mu}[T_1]\epsilon)$, which gives the value of $K_{\nu}(\epsilon)$ in (5.41) and

$$ k_0 \leq \frac{C(\epsilon)}{\alpha} \left( t_{\text{mix}}^{(Y)}(\epsilon) \max_{u \in S} \mathbb{E}_u |T_1| + K_{\nu}(\epsilon) + \frac{\mathbb{E}_{\mu}[T_1^2]}{\mathbb{E}_{\mu}[T_1]} \right)^2 $$

We deduce eventually that taking $t$ as (5.45) yields

$$ \| \mathbb{P}_{\nu}[U_t = \cdot] - \tilde{\mu} \|_{\text{TV}} \leq \epsilon $$

for large enough $C(\epsilon)$. Finally using (5.46) yields

$$ \frac{1}{2} \sum_{y \in S} \left| u_t(\nu, y) - \frac{\mu(y)}{\mathbb{E}_{\mu}[T_1]} \right| \leq \epsilon. $$

□

The last tool we introduce about Markov renewal processes is a variance bound that uses spectral arguments. Let us gather a few known facts about spectral theory for Markov chains. Consider a Markov chain $Y = (Y_k)_{k \geq 0}$ on countable state space $Y$ with transition kernel $Q$, which is irreducible, positive recurrent with stationary distribution $\mu$.

Let $\ell^2(\mu)$ be the Hilbert space of real-valued functions on $S$ which are square-integrable with respect to the measure $\mu$, equipped with the inner product

$$ \langle f, g \rangle_{\mu} := \sum_{x \in S} \mu(x) f(x) g(x). $$
$Q$ defines a contracting linear operator on $\ell^2(\mu)$ by $Qf(x) := \sum_{y \in S} Q(x, y)f(y)$. Its spectrum is defined as

$$ \mathrm{Spec}(Q) := \{ \lambda \in \mathbb{C} \mid \lambda I - Q \text{ is not invertible as a bounded linear operator} \}. $$

The adjoint operator of $Q^*$ is given by

$$ Q^*(y, x) = \frac{\mu(x)Q(x, y)}{\mu(y)} $$

for all $x, y \in S$. Reversibility of $Q$ with respect to $\mu$ is equivalent to self-adjointness of $Q$. In this case, the spectrum of $Q$ is included the interval $[-1, 1]$. Writing $\mathbb{1}$ for the constant function equal to 1, the fact that $\mu$ is a probability measure implies that $\mathbb{1} \in \ell^2(S)$ and is an eigenvector of $Q$ associated with the eigenvalue 1. The absolute spectral gap of $Q$ is then defined as

$$ \gamma := 1 - \sup\{|\lambda|, \lambda \in \mathrm{Spec}(Q), \lambda \neq 1\} $$

if the eigenvalue 1 has multiplicity 1 and $\lambda := 0$ otherwise. It is well known that the absolute spectral gap is related to mixing properties of $Y$, see for instance [117, Chap. 12]. In the non-reversible case, spectral arguments can be applied by considering reversibilizations of the chain. From a theoretical point of view, the optimal parameter to consider is the so-called *pseudo spectral gap*, defined as

$$ \gamma_{ps} := \max_{k \ge 1} \left\{ \frac{\gamma((Q^*)^k Q^k)}{k} \right\}. $$

If $Q$ is reversible obviously $\gamma_{ps} = \gamma^2$. The pseudo spectral gap is a rather natural quantity introduced in [145] but it may have appeared before-hand in other places under different names. In [31], the quantity $1 - \gamma_{ps}$ is considered under the name singular radius.

As for the classical spectral gap, the pseudo spectral gap is intimately related with the mixing properties of the chain, as shown by the following proposition.

**Proposition 5.10** ([145, Prop. 3.4]). Let $(Y_k)_{k \ge 0}$ be an irreducible, positive recurrent Markov chain on a countable state space $S$, with stationary distribution $\mu$ and $\varepsilon$-mixing time $t_{\mathrm{mix}}(\varepsilon)$. Suppose it is uniformly ergodic, in the sense that there exists $C > 0$ and $\rho \in (0, 1)$ such that

$$ \sup_{x \in S} \| \mathbb{P}_x [Y_t = \cdot] - \mu \|_{\mathrm{TV}} \le C \rho^t. $$

Then for all $\varepsilon \in [0, 1)$,

$$ \gamma_{ps} \ge \frac{1 - \varepsilon}{t_{\mathrm{mix}}(\varepsilon)}. \qquad (5.47) $$
Furthermore if S is finite,

$$t_{\text{mix}}(\varepsilon) \le \frac{1 + 2 \log((2\varepsilon)^{-1}) + \log(\mu_{\min}^{-1})}{\gamma_{ps}} \quad (5.48)$$

where $\mu_{\min} := \min_{x \in S} \mu(x)$.

The pseudo spectral gap can also be used to precisely handle correlations between different steps of a Markov chains. Thus we obtain the following variance bound for Markov processes with the (M1) Markov property.

**Proposition 5.11.** Let S be countable and E a Polish space. Let $(Y_k, Z_k)_{k \ge 0}$ be a process on $S \times E$ satisfying (M1). Suppose that Y is irreducible, positive recurrent, with invariant measure $\mu$ and pseudo spectral gap $\gamma_{ps}$. Let $(f_i)_{i \ge 1}$ be a family of functions such that for all $i \ge 1$, $f_i : S \times E \to \mathbb{R}$ and $\max_{u \in S} \mathbb{E}_u [f_i(Y_1, Z_1)^2] < \infty$. Then for all $k \ge 1$

$$\mathrm{Var}_{\mu} \left[ \sum_{i=1}^{k} f_i(Y_i, Z_i) \right] \le \frac{6}{\gamma} \sum_{i=1}^{k} \mathrm{Var}_{\mu} [f_i(Y_1, Z_1)]. \quad (5.49)$$

The previous result can be applied to the case of a Markov renewal process $(Y_k, T_k)_{k \ge 0}$, to get that

$$\mathrm{Var}_{\mu}[T_k] \le \frac{6}{\gamma_{ps}} k \mathrm{Var}_{\mu}[T_1]. \quad (5.50)$$

for all $k \ge 1$.

*Proof.* First, observe that if $(Y, Z)$ satisfies (M1) so does $(Y, (Y, Z))$. Thus up to changing the second coordinate of the process considered it suffices to prove the result for functions $f_i$ of $Z_i$ only.

We use the same arguments as in [145]. Let $Q$ denote the transition kernel of the chain Y and given $i \in [m]$, $x, y \in S$ let

$$Q_i(x, y) := \mathbb{E}_x [f_i(Z_1) 1_{Y_1=y}].$$

Using matrix notations, for all $i \in [m]$, $x \in S$, $Q_i 1(x) = \sum_{y \in S} Q_i(x, y) = \mathbb{E}_x [f_i(Z_1)]$. We can suppose without generality that $\mathbb{E}_\mu [f_i(Z_i)] = \mathbb{E}_\mu [f_i(Z_1)] = 0$, which can be written matricially as

$$\mu Q_i 1 = 0. \quad (5.51)$$

The random variable $\sum_{i=1}^m f_i(Z_i)$ is thus also centered and from stationarity one has

$$\mathrm{Var}_{\mu} \left[ \sum_{i=1}^{m} f_i(Z_i) \right] = \sum_{i,j=1}^{m} \mathbb{E}_{\mu} [f_i(Z_i) f_j(Z_j)] \\ = \sum_{i,j=1}^{m} \mathbb{E}_{\mu} [f_i(Z_1) f_j(Z_{|j-i|+1})].$$
For any $l \ge 1$

$$
\begin{align*}
\mathbb{E}_{\mu}[f_i(Z_1)f_j(Z_{l+1})] &= \sum_{x,y \in S} \mu(x)Q_i(x,y)\mathbb{E}_y[f_j(Z_{l+1})] \\
&= \sum_{x,y,z \in S} \mu(x)Q_i(x,y)Q^l Q_j(y,z) \\
&= \langle Q_i Q^l Q_j 1, 1 \rangle_{\mu} \\
&= \langle Q_i (Q^l - 1\mu) Q_j 1, 1 \rangle_{\mu}
\end{align*}
$$

where in the last line we used (5.51). For any $l \ge 1$, since $\mu$ is stationary one has
$Q^l - 1\mu = (Q - 1\mu)^l$, thus by Cauchy-Schwarz inequality

$$
\begin{align*}
\langle Q_i (Q - 1\mu)^l Q_j 1, 1 \rangle_{\mu} &= \langle (Q - 1\mu)^l Q_j 1, Q_i^* 1 \rangle_{\mu} \\
&\le \|(Q - 1\mu)^l\| \|Q_j 1\| \|Q_i^* 1\|.
\end{align*}
$$

Then by Jensen’s inequality,

$$
\|Q_j 1\|^2 = \sum_{x \in S} \mu(x) |\mathbb{E}_x[f_j(Z_1)]|^2 \le \mathbb{E}_\mu [f_j(Z_1)^2] = \mathrm{Var}_\mu(f_j(Z_1)).
$$

Similarly,

$$
Q_i^* 1(y) = \sum_{x \in S} \frac{\mu(x) Q_i(x, y)}{\mu(y)} = \mathbb{E}_{\mu} [f_i(Z_1) \mid Y_1 = y]
$$

so

$$
\| Q_i^* 1 \|^2 \le \sum_{y \in S} \mu(y) \mathbb{E}_{\mu} [f_i(Z_1)^2 \mid Y_1 = y] = \mathbb{E}_{\mu} [f_i(Z_1)^2] = \mathrm{Var}_{\mu} [f_i(Z_1)^2].
$$

Hence

$$
\begin{align*}
\mathbb{E}_{\mu}[f_i(Z_1)f_j(Z_{l+1})] &\le \|(Q - 1\mu)^l\| \mathrm{Var}_{\mu}[f_i(Z_1)]^{1/2} \mathrm{Var}_{\mu}[f_j(Z_1)]^{1/2} \\
&\le \frac{1}{2} \|(Q - 1\mu)^l\| (\mathrm{Var}_{\mu}[f_i(Z_1)] + \mathrm{Var}_{\mu}[f_j(Z_1)]).
\end{align*}
$$

It remains to sum over $i, j$. Let $k \ge 1$ be such that $\gamma(Q^k(Q^k)^*) = \gamma_{ps}k$. Then by
observing that $\|(Q - 1\mu)^k\|^2 = 1 - \gamma(Q^k(Q^k)^*)$ one can deduce

$$
\begin{align*}
\|(Q - 1\mu)^l\| &\le \|(Q - 1\mu)^k\|^{l/k} \\
&= (1 - k\gamma_{ps})^{l/k}/2
\end{align*}
$$
Consequently

$$
\begin{align*}
\sum_{i \neq j=1}^{m} \mathbb{E}_{\mu} [f_i(Z_1) f_j(Z_{|j-i|+1})] &\le \frac{1}{2} \sum_{i \neq j=1}^{m} \|(Q - 1\mu)^{|j-i|-1}\| (\mathrm{Var}_{\mu}[f_i(Z_1)] + \mathrm{Var}_{\mu}[f_j(Z_1)]) \\
&\le 2 \sum_{i=1}^{m} \sum_{l=0}^{\infty} \|(Q - 1\mu)^l\| \mathrm{Var}_{\mu}[f_i(Z_1)] \\
&\le 2 \sum_{i=1}^{m} \mathrm{Var}_{\mu}[f_i(Z_1)] \sum_{l=0}^{\infty} (1 - k\gamma_{ps})^{[l/k]/2} \\
&\le 4 \sum_{i=1}^{m} \mathrm{Var}_{\mu}[f_i(Z_1)] \sum_{l=0}^{\infty} (1 - k\gamma_{ps})^{[l/k]} \\
&= \frac{4}{\gamma_{ps}} \sum_{i=1}^{m} \mathrm{Var}_{\mu}[f_i(Z_1)]
\end{align*}
$$

and combining with the diagonal terms $i = j$ the result follows as $\gamma_{ps} \le 2$. $\square$

### 5.6.2 Regeneration structure

Let us come back to the setting of quasi-trees.

**Definition 5.6.** A time $t \in \mathbb{N}/2$ is called a regeneration time if $(\mathcal{X}_{t-1/2}, \mathcal{X}_t)$ is a long-range edge crossed for the first and last time at time $t$.

**Lemma 5.12.** A.s. there exists an infinity of regeneration times.

The proof is similar to that of Lemma 3.3 in [127]. It can also be deduced from the tail estimates proved later on.

Frow now on, let $T_0 := 0$, $Y_0 := \iota(O)$, $L_0 := 0$ and $(T_k)_{k \ge 1}$ be the sequence of successive regeneration times of $\mathcal{X}$. For all $k \ge 1$, define

$$Y_k = \iota(\mathcal{X}_{T_k-1/2}) \quad L_k := d(O, \mathcal{X}_{T_k}).$$

$(Y_k)_{k \ge 1}$ is the Markov chain that dictates the law of the environments between successive regeneration times. To describe this Markov chain, introduce the measures

$$\mathbb{Q}_u = \mathbb{P}[\cdot \mid \mathcal{X}_{1/2} = \eta(O), \tau_O = \infty, \iota(O) = u] \quad (5.52)$$

for all $u \in V$.

**Remark 5.15.** By Lemma 5.6, there exists a constant $q_0 > 0$ such that for all $u \in V$,

$$\mathbb{P}[\tau_O = \infty \mid \mathcal{X}_{1/2} = \eta(O), \iota(O) = u] \ge \mathbb{E}[q_{\mathrm{Esc}}(\eta(O)) \mid \iota(O) = u] \ge q_0.$$

which implies

$$\mathbb{P}[\cdot, \tau_O = \infty \mid \mathcal{X}_{1/2} = \eta(O), \iota(O) = u] \le \mathbb{Q}_u[\cdot] \le q_0^{-1} \mathbb{P}[\cdot \mid \mathcal{X}_{1/2} = \eta(O), \iota(O) = u].$$
Consequently the laws of the quasi-tree $\mathcal{G}$ under $\mathbb{P}[\cdot | \iota(O) = u]$ and $\mathbb{Q}_u$ are within constant factors of each other for events that do not contradict $\tau_O = \infty$. In particular, up to a change of constant the uniform lower bounds of Proposition 5.4 and 5.5 for the random variables $q_{\text{Esc}}(O), q_{\text{Esc}}(\eta(O))$ also hold under the probability $\mathbb{Q}_u$, for any $u \in V$. Furthermore, the law of the centers added to the quasi-trees remains essentially uniform in the sense that for all $v \in V$ such that $V(v) \neq V(u)$

$$ \mathbb{Q}_u[\iota(\eta(O)) = v] = \Theta(1/n). \qquad (5.53) $$

Indeed by what precedes

$$ \mathbb{Q}_u[\iota(\eta(O)) = v] \leq q_0^{-1} \mathbb{P}[\eta(O) = v | \iota(O) = u] = q_0^{-1}/n $$

and

$$ \begin{aligned} \mathbb{Q}_u[\iota(\eta(O)) = v] &\geq \mathbb{E}[1_{\iota(\eta(O))=v} 1_{\tau_O=\infty} | \iota(O) = u, \chi_{1/2} = \eta(O)] \\ &\geq \mathbb{E}[1_{\iota(\eta(O))=v} \mathbb{E}[q_{\text{Esc}}(\eta(O)) | \iota(O), \iota(\eta(O))] | \iota(O) = u] \\ &\geq q_0/n. \end{aligned} $$

*Remark 5.16.* Section 5.6.1 only considered integer valued processed for the time component of Markov renewal processes. To apply the results of this section we will thus implicitly identify regeneration times with an integer-valued process.

The following lemma is the analog of Lemma 3.6 in [92] and is proved in a similar way.

**Lemma 5.13.** • The sequences $(Y_k, T_k)_{k \geq 1}$ and $(Y_k, L_k)_{k \geq 1}$ are Markov renewal processes.

* The sequence $(Y_{k+1}, \mathcal{G}_{\mathcal{X}_{T_k}} \setminus \mathcal{G}_{\mathcal{X}_{T_{k+1}}}, (\mathcal{X}_t)_{T_k \leq t < T_{k+1}})_{k \geq 0}$ is a Markov chain whose transition probabilities only depend on the first coordinate $Y_k$, ie the law of this triplet at time $k+1$ conditional on time $k$ is only measurable with respect to $Y_k$.

* For all $k \geq 1$, conditional on $Y_k$, the pair $(\mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t \geq T_k})$ has the law of $(\mathcal{G}_O, \mathcal{X})$ under the probability $\mathbb{Q}_{Y_k}$.

*Remark 5.17.* Note that although $(Y, T)$ starts at time 0, it is a Markov renewal process from time 1, and the delay is thus $T_1$. However by the lemma, under the measure $\mathbb{Q}_u$, for any $u \in V$, $T_1$ has distribution given by a transition probability and thus $(Y, T)$ becomes a Markov renewal process already from time 0, with 0 delay. We will use this observation often in the sequel.
Proof. Let

$$
E := \{(g, (x_i)_{i \in \mathbb{N}/2}) \mid g \text{ quasi-tree, } (x_i)_{i \in \mathbb{N}/2} \text{ path in } g\},
$$

where paths refer here to potential trajectories of the chain $(\mathcal{X}_t)_{t \in \mathbb{N}/2}$. Let $k \ge 1$ and $A, B \subset E$ two possible events for $(\mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t \ge T_k})$. For all $x \in \mathcal{V}$ let $\tau_x^{(s)} := \inf\{t \ge s \mid \mathcal{X}_t \notin \mathcal{G}_x\}$. Notice that

$$
\begin{align*}
& \mathbb{P} \left[ (\mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t \ge T_k}) \in A, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t < T_k}) \in B \right] \\
&= \sum_{s \ge 0} \mathbb{P} \left[ T_k = s, (\mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t \ge s}) \in A \cap \{\tau_{\mathcal{X}_{s-1/2}} = \infty\}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t < s}) \in B \right]
\end{align*}
$$

Call a time $t \ge 0$ fresh if $(\mathcal{X}_{t-1/2}, \mathcal{X}_t)$ is a long-range edge visited for the first time at time $t$, and let $A_{k,s}$ be the event that there are $k$ regeneration times before time $s$. Using the dependence properties between subquasi-trees and their complement described in Section 5.2.6,

$$
\begin{align*}
& \mathbb{P}[T_k = s, (\mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t \ge s}) \in A \cap \{\tau_{\mathcal{X}_{s-1/2}} = \infty\}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t < s}) \in B] \\
&= \mathbb{P}[s \text{ fresh}, A_{k-1,s}, (\mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t \ge s}) \in A \cap \{\tau_{\mathcal{X}_{s-1/2}} = \infty\}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t < s}) \in B] \\
&= \mathbb{P}[s \text{ fresh}, A_{k-1,s}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t < s}) \in B] \\
& \quad \times \mathbb{P}\left[(\mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t \ge s}) \in A \cap \{\tau_{\mathcal{X}_{s-1/2}}^{(s)} = \infty\} \mid s \text{ fresh}, A_{k-1,s}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t < s}) \in B\right] \\
&= \mathbb{P}[s \text{ fresh}, A_{k-1,s}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t < s}) \in B] \\
& \quad \times \mathbb{P}\left[(\mathcal{G}_{O'}, (\mathcal{X}'_t)_{t \ge 1/2}) \in A \cap \{\tau_{O'} = \infty\} \mid \mathcal{X}'_{1/2} = \eta(O'), \iota(O') = \iota(\mathcal{X}_{s-1/2})\right]
\end{align*}
$$

where $(\mathcal{G}', O', \mathcal{X}')$ is an independent copy of $(\mathcal{G}, O, \mathcal{X})$. Also

$$
\begin{align*}
& \mathbb{P}[s \text{ fresh}, A_{k-1,s}, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t<s}) \in B] = \frac{\mathbb{P}[T_k = s, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t<s}) \in B]}{\mathbb{P}[\tau_{\mathcal{X}_{s-1/2}}^{(s)} = \infty \mid \mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}]} \\
& = \frac{\mathbb{P}[T_k = s, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_s}, (\mathcal{X}_t)_{t<s}) \in B]}{\mathbb{P}[\tau_{O'} = \infty \mid \mathcal{X}'_{1/2} = \eta(O'), \iota(O') = \iota(\mathcal{X}_{s-1/2})]}
\end{align*}
$$

Summing over $s \ge 0$ yields eventually

$$
\begin{align*}
& \mathbb{P} \left[ (\mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t \ge T_k}) \in A, (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t < T_k}) \in B \right] \\
&= \mathbb{P}_{Y_k} \left[ (\mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t \ge T_k}) \in A \right] \mathbb{P} \left[ (\mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_{T_k}}, (\mathcal{X}_t)_{t < T_k}) \in B \right].
\end{align*}
$$

□

A non-negative random variable $Z$ has *stretched exponential tail* if there exists $\alpha \in (0, 1)$ such that $\mathbb{E}[\exp Z^\alpha] < \infty$. A stretched exponential tail implies the existence of polynomial moments of all orders.

**Lemma 5.14.** For all $u \in V$, under both measures $\mathbb{Q}_u$ and $\mathbb{P}_O[\cdot | \iota(O) = u]$:
• $L_1$ has exponential tail,

• $T_1$ has stretched exponential tail.

Furthermore, given $L, t \ge 0$, let $\tilde{T}_1^{(L)}$ denote the first time a regeneration occurs outside the ball $B_{LR}(O, L)$ and $U_t(L) = \sum_{s \le t} 1_{X_s \in B_{LR}(O, L)}$ the total time spent by the chain in $B_{LR}(O, L)$ before $t$. There exists $\alpha \in (0, 1]$ such that for all $L, m, k \in \mathbb{N}, m \ge 1$, for all $x \in B_{LR}(O, L)$ such that $d_{LR}(O, x) = L$, conditional on either $X_0 = x$ or $X_{1/2} = x$

$$ \mathbb{P}[\tilde{T}_1^{(L)} > k + m \mid B_{LR}(O, L), U_{k+m}(L) \le m] \le e^{-k^\alpha}. $$

*Remark 5.18.* Proposition 2.2 in [2] shows that in the case of a randomly biased random walk on a Galton-Watson tree, stretched exponential can be the right order of magnitude for the tail of the first regeneration time. From the proof, it can be seen that this slowdown is precisely caused by the same trapping phenomenon as mentioned in Remark 5.8, when the walk can move from a part of the tree where it goes very fast to infinity to a part where it tends to go back to the root. This suggests that for some choices $P_1, P_2$ and $p$, stretched exponential tails give the right tail for the regeneration times in our model too.

*Proof.* For the tails, Remark 5.15 shows it suffices to prove the result for the law $\mathbb{P}_O[\cdot | \iota(O)]$. Suppose $\iota(O)$ is fixed. The proof of the exponential tail for regeneration levels is taken from that of Lemma 4.2 in [52]. It actually proves exponential tails for a stronger notion of regeneration, which looks at times when a long-range distance is reached for the first and last time. Namely let

$$ \tilde{T}_1 := \inf\{t \in \mathbb{N}/2 \mid \forall s < t : d_{LR}(O, \mathcal{X}_s) < d_{LR}(O, \mathcal{X}_t), \forall s \ge t : d_{LR}(O, \mathcal{X}_s) \ge d_{LR}(O, \mathcal{X}_t)\}. $$

and $\tilde{L}_1 := d_{LR}(O, \mathcal{X}_{\tilde{T}_1})$. Obviously $T_1 \le \tilde{T}_1$ and $L_1 \le \tilde{L}_1$, so it suffices to prove an exponential tail for $\tilde{L}_1$.

Suppose the chain is started at $O$. Consider the "ladder times" $(S_i)_{i=0}^K$, where $K \in \mathbb{N} \cup \{\infty\}$ is a random integer, possibly infinite, defined recursively as follows. Let $S_0 := 0$, and define $\tau_0$ as the first return time to $O$. If $\tau_0 = \infty$ set $K := 0$. Otherwise, let $M_0 := \max\{d_{LR}(O, \mathcal{X}_t), 0 \le t \le \tau_0\}$ be the maximal distance reached until $\tau_0$ and $S_1 := \min\{t \in \mathbb{N}/2 : d_{LR}(0, \mathcal{X}_t) > M_0\}$. Define the rest of the sequence recursively: let $\tau_i$ the first return time to level $d_{LR}(0, \mathcal{X}_{S_i}) - 1$. If $\tau_i = \infty$, $K := i$, and $S_j := \infty$ for all $j \ge i + 1$, otherwise set $M_i := \max\{d_{LR}(O, \mathcal{X}_t), 0 \le t \le \tau_i\}$ and $S_{i+1} := \min\{t \in \mathbb{N}/2 : d_{LR}(O, \mathcal{X}_t) > M_i\}$. Notice that $S_K = \tilde{T}_1$ if $K \in (0, \infty)$ and $\tilde{T}_1 = 1/2$ if $K = 0$.
Consequently for any $C > 0$, if $l \ge 1$ is large enough,

$$
\begin{align*}
\mathbb{P}_O[\tilde{L}_1 > Cl \mid \iota(O)] &\le \mathbb{P}_O[K < \infty, d(O, \mathcal{X}_{S_K}) > Cl \mid \iota(O)] \\
&= \mathbb{P}_O\left[K < \infty, \sum_{i=1}^K (d_{LR}(O, \mathcal{X}_{S_i}) - d_{LR}(0, \mathcal{X}_{S_{i-1}})) > Cl \mid \iota(O)\right] \\
&= \sum_{k=1}^\infty \mathbb{P}_O\left[\sum_{i=1}^k (d_{LR}(O, \mathcal{X}_{S_i}) - d_{LR}(0, \mathcal{X}_{S_{i-1}})) > Cl, \{\tau_i < \infty\}_{i=1}^{k-1}, \tau_k = \infty \mid \iota(O)\right] \\
&\le \mathbb{P}_O[K > l \mid \iota(O)] + \mathbb{P}_O\left[\sum_{i=0}^{l-1} Z_i > Cl \mid \iota(O)\right].
\end{align*}
$$

where we write $Z_0 := d_{LR}(O, \mathcal{X}_{S_1})1_{\tau_0<\infty}$, $Z_i := (d_{LR}(O, \mathcal{X}_{S_{i+1}}) - d_{LR}(0, \mathcal{X}_{S_i}))1_{\tau_i<\infty}$ for all $i \ge 1$. To prove this is exponentially small in $l$, it thus suffices to establish that $K$ has exponential tail and that for fixed $l \ge 1$, the second probability in the right-hand side is also exponentially small in $l$.

It was already observed in Remark 5.15 that $\mathbb{P}[\tau_O = \infty | \mathcal{X}_{1/2} = \eta(O), \iota(O)] = \Theta(1)$. We deduce that $K$ is stochastically dominated by a geometric variable of constant parameter and thus has exponential tail, even conditional on $\iota(O)$.

On the other hand, by construction, for all $i \ge 1$ if $S_i < \infty$ the trajectory $(\mathcal{X}_i)_{S_i \le t < \tau_i}$ is entirely contained in the subquasi-tree $\mathcal{G}_{\mathcal{X}_{S_i}}$. Furthermore, $d_{LR}(O, \mathcal{X}_{S_{i+1}}) = M_i + 1$ is determined by this trajectory. Thus for $i \ge 1$, $Z_i = (M_i - M_{i-1})1_{\tau_i < \infty}$ depends only on $\eta(\mathcal{X}_{S_{i-1/2}})$ and $\mathcal{G}_{\mathcal{X}_{S_i}}$. Letting $\tilde{Y}_i := \iota(\eta(\mathcal{X}_{S_{i-1/2}}))$ for $i \ge 0$, we can deduce that if $i \ge 1, l \ge 1$ and $S_i < \infty$,

$$
\begin{align*}
\mathbb{P}_O[Z_i = l | \mathcal{G} \setminus \mathcal{G}_{\mathcal{X}_{S_i}}, (\mathcal{X}_s)_{s \le S_i}] \\
= \mathbb{P}[\tau_{O'} < \infty, M_0' = l | \mathcal{X}_{1/2} = \eta(O'), \iota(O') = \tilde{Y}_i]
\end{align*}
$$

with $(\mathcal{G}', O', M_0')$ an independent copy of $(\mathcal{G}, O, M_0)$. We do not prove this in detail, which can be established as Lemma 5.13. See also the proof of Lemma 4.4 of [52]. If we extend the process $(\tilde{Y}, Z)$ by considering that $\tilde{Y}_i$ takes an arbitrary value $\dagger$ if $S_i = \infty$ and consider that $Z_{i+1} = 0$ a.s. given $\tilde{Y}_i = \dagger$, the previous equation implies in particular that $(\tilde{Y}_i, Z_i)_{i \ge 0}$ is a Markov chain that satisfies the (M1) property. Furthermore for all $l \ge 1$,

$$
\begin{align*}
\mathbb{P}[\tau_O < \infty, M_0 \ge l \mid \mathcal{X}_{1/2} = \eta(O), \iota(O)] \\
\le \mathbb{P}[\exists t > s \ge l : d_{LR}(\eta(O), \mathcal{X}_s) = l - 1, \mathcal{X}_t = O \mid \mathcal{X}_{1/2} = \eta(O), \iota(O)].
\end{align*}
$$

This is an annealed probability of backtracking over a long-range distance $L$. Let us here anticipate on the sequel and use Lemma 5.18 which will prove this probability is exponentially small in $L$. With what precedes, this proves that there exists constants $C', \theta > 0$ such that for any possible state $u$ of the chain $\tilde{Y}$, $\mathbb{E}[e^{\theta Z_1} | \tilde{Y}_0 = u] < C'$.
Exponential moments of $Z_0$ can be bounded similarly. The reader will then have recognized the condition to apply Lemma 5.11, which proves that for some constant $C > 0$, $\mathbb{P}_O[\sum_{i=0}^{l-1} Z_i > Cl | \iota(O)]$ is exponentially small in $l$, with all constants being independent of $n$.

Let us move to the proof of stretched exponential tails for $T_1$. It is inspired from the proof of Prop. 2.2 in [2]. For ease of notation we will here keep the conditionning by $\iota(O)$, but all probabilities below should be considered conditionning on it. Given $k, t \ge 0$, let $\tau_k$ denote the hitting time of level $k$ and $K_t$ denote the time spent before $t$ at a center, at half-integer times steps. For any $C > 0$ and $k \ge 0$,

$$ \mathbb{P}_O[T_1 > Ck^3] \le \mathbb{P}_O[T_1 > \tau_k] + \mathbb{P}_O[Ck^3 < T_1 \le \tau_k] \\ \le \mathbb{P}_O[T_1 > \tau_k] + \mathbb{P}_O[K_{Ck^3} \le k^3] + \mathbb{P}_O[K_{\tau_k} > k^3]. $$

The first term can be rewritten as $\mathbb{P}[T_1 > \tau_k] = \mathbb{P}[L_1 > k]$ which is exponentially small by the first part. For the second term, note that when the chain is at a non-center vertex $x$ at integer times, it has probability $\Theta(1)$ to go to the center $\eta(x)$ by (H2). Thus the first hitting time time of a center is stochastically dominated by a geometric variable, even under the quenched law. In turn we deduce

$$ \mathbf{P}_O[K_{Ck^3} \le k^3] \le \mathbb{P}\left[\sum_{i=1}^{k^3} Z_i \ge Ck^3\right], $$

where the $Z_i$ are independent geometric variables of positive constant parameter. By Chernoff's inequality, the right-hand side is exponentially small in $k^3$ for a good choice of $C > 0$. The third term can be further decomposed as follows. Given a center $x \in \mathcal{V}$, let $N(x)$ denote the number of visits to $x$ at half-integer times. Given $i \ge 1$, write $z_i$ for the $i$-th distinct center visited by the chain and $M_i$ for the number of distinct centers visited in $\mathcal{V}_i$ at half-integer times. Then

$$ \mathbb{P}_O[K_{\tau_k} > k^3] \le \mathbb{P}_O \left[ \begin{array}{l} \text{more than } k^2 \text{ distinct centers are visited} \\ \text{before } \tau_k \text{ at half-integer times} \end{array} \right] \\ + \mathbb{P}_O[\exists i \le k^2 : N(z_i) > k]. $$

By union bound

$$ \mathbb{P}_O \left[ \begin{array}{l} \text{more than } k^2 \text{ distinct centers are visited} \\ \text{before } \tau_k \text{ at half-integer times} \end{array} \right] \le \sum_{i=1}^{k} \mathbb{P}_O[M_i \ge k]. $$

Let $\tau_k^{(i)}$ denote here the hitting time of the $k$-th distinct center of $\mathcal{V}_i$. By the strong Markov property

$$ \mathbf{P}_O[M_i \ge k] = \mathbf{P}_O[\tau_k^{(i)} < \infty] \\ \le \mathbf{E}_O \left[ \mathbb{1}_{\tau_{k-1}^{(i)} < \infty} (1 - q_{\text{Esc}}(\mathcal{X}_{\tau_{k-1}^{(k)}})) \right]. $$
Since the centers visited at $\tau_{k-1}^{(i)}$ and $\tau_k^{(i)}$ are distinct and at the same level, their subtrees are disjoint and independent. Hence

$$ \mathbb{P}_O[M_i \ge k] \le \mathbb{E}\left[\mathbf{P}_O\left[\tau_{k-1}^{(i)} < \infty\right] \left(1 - \min_{u,v} \mathbb{E}\left[q_{\text{Esc}}(\eta(O')) \mid \iota(O') = u, \iota(\eta(O') = v)\right]\right)\right], $$

where $(\mathcal{G}', O')$ is as usual an independent copy of $(\mathcal{G}, O)$ and $V(u) \neq V(v)$. By Lemma 5.6, the expected escape probability can be lower bounded by some constant $q_0 \in (0, 1]$ hence by induction

$$ \mathbb{P}[M_i \ge k] \le (1 - q_0)^{k-1} $$

and

$$ \mathbb{P}_O\left[ \begin{array}{c} \text{more than } k^2 \text{ distinct centers are visited} \\ \text{before } \tau_k \text{ at half-integer times} \end{array} \right] \le k(1 - q_0)^{k-1} $$

is exponentially small in $k$.

To bound the last term, let

$$ q'_{\text{Esc}}(x) := \mathbf{P} \left[ \tau_x = \tau_{\eta(x)} = \infty \mid \chi_{1/2} = x \right]. $$

for all center $x \in \mathcal{V}$. Like $q_{\text{Esc}}(x)$, this quantity depends only on $\mathcal{G}_x$ and $\eta(x)$. Furthermore, if $y$ is a vertex at small-range distance 1 from $x$, then

$$ \begin{aligned} q'_{\text{Esc}}(x) &\ge p(x, \eta(x)) P(x, y) q_{\text{Esc}}(y) \\ &\ge \delta q_{\text{Esc}}(y), \end{aligned} $$

thus lower bounding $q'_{\text{Esc}}$ is essentially the same as lower bounding $q_{\text{Esc}}$. For all $i \ge 1$,

$$ \begin{aligned} \mathbf{P}_O[N(z_i) > k] &= \sum_{x \in \mathcal{V}} \mathbf{E}[1_{z_i=x, N(x)>k}] \\ &\le \sum_{x \in \mathcal{V}} \mathbf{E}[1_{z_i=x} (1 - q'_{\text{Esc}}(x))^k] \\ &= \sum_{x \in \mathcal{V}} \mathbf{P}_O[z_i=x] (1 - q'_{\text{Esc}}(x))^k \end{aligned} $$

To average over the environment, use the "Ulam labelling" of Section 5.2.6:

$$ \mathbb{P}_O[N(z_i) > k] \le \sum_{x \in \mathcal{V}} \mathbb{E}[1_{x \in \mathcal{V}} \mathbf{P}_O[z_i = x]] \mathbb{E}[(1 - q'_{\text{Esc}}(x))^k \mid x \in \mathcal{V}, \mathcal{G} \setminus \mathcal{G}_x] $$

From Proposition 5.4, one can easily obtain that

$$ \max_{x \in \mathcal{V}} \mathbb{E} \left[ (1 - q'_{\text{Esc}}(x))^k \mid x \in \mathcal{V}, \mathcal{G} \setminus \mathcal{G}_x \right] \le e^{-k^c} $$

for some constant $c > 0$, hence by union bound

$$ \mathbb{P}_O[\exists i \le k^2 : N(z_i) > k] \le k^2 e^{-k^c}, $$
which is stretched exponential, as desired.

Finally, for the last statement note that if the chains is started precisely at the boudnary of the ball $B_{LR}(O, L)$, then a regeneration can occur within a number of steps which is bounded in $L$, thus from the lower bound on escape probabilities (Lemma 5.6) it is easy to lower bound $\mathbb{P}_x[U_{k+m}(L) \le m | B_{LR}(O, L)]$ uniformly in $n, L, m$. Thus the conditioning by $U_{k+m}(L) \le m$ only modifies upper bounds under the usual law of the quasi-tree by a factor of constant order. The upper bound for the conditional probability then follows from the same arguments as above. $\square$

### 5.6.3 Mixing of the regeneration chain

We now investigate the mixing properties of the Markov chain $Y$ underlying the regeneration process, which we call the regeneration chain. Lemma 5.15 below will establish that $Y$ has constant mixing time, allowing us later to get moment bounds similar to the iid case. The lemma actually proves a stronger mixing property of both the chain $Y$ and the time process $T$ that will be used to derive approximation of the invariant measure on $X$.

**Lemma 5.15.** Let $(Q_t)_{t \ge 1}$ denote the transition kernels of the Markov renewal process $(Y, T)$ and $Q := \sum_{t \ge 1} Q_t$, after identification of $T$ with a process in $\mathbb{N}$. Recall that from Hypothesis (H4)) there exists a constant $l \ge 1$ such that the set

$$S = S(l) := \{x \in V \mid \forall y \in V : P(x, y) > 0 \Leftrightarrow (I + P)^l(y, x) > 0\}.$$

$$\text{satisfies } |S| = 2n - o(n).$$

(i) For all $u \in V$ and $v \in S$,

$$Q(u, v) = \Theta(1/n). \qquad (5.54)$$

As a consequence for all $\varepsilon \in (0, 1)$, the chain $Y$ has mixing time $O_\varepsilon(1)$ as $n \to \infty$.

(ii) for all $u \in V$,

$$\sum_{t \ge 1} \sum_{v \in V} Q_t(u, v) \wedge Q_{t+1}(u, v) = \Theta(1). \qquad (5.55)$$

*Proof of Lemma 5.15.* Let $\varepsilon \in (0, 1)$. The statement about the mixing time of $Y$ is easily deduced from (5.54) and the fact that $|S| = 2n - o(n)$. Summing on $v$ yields the following Doeblin's condition for $Y$: there exists a constant $c > 0$ such that

$$\|Q(u, \cdot) - Q(u', \cdot)\|_{\text{TV}} \le 1 - c - o(1),$$

for all $u, u' \in V$. It is then easy to obtain from Doeblin's condition that $Y$ has mixing time $t_{\text{mix}}^{(Y)}(\varepsilon) \le (c^{-1} + o(1)) \log \varepsilon^{-1}$.
<figure><img src="image_15.png" /><figcaption>Figure 5.2: Argument of the proof of Lemma 5.15</figcaption></figure>

Let us now prove (5.54). Consider $u, v \in V$ with $v \in S$. By definition for all $t \ge 1$

$$Q_t(u, v) = Q_u[Y_1 = v, T_1 = t] = \mathbb{P}[T_1 = t, \iota(\mathcal{X}_{t-1/2}) = v \mid \tau_O = \infty, \iota(O) = u, \mathcal{X}_{1/2} = \eta(O)].$$

Probabilistic statements below will thus be made with respect to $Q_u$ unless stated otherwise.

Observe that if $V(u) \neq V(v)$, it is possible to realize $Y_1 = v$ with regeneration occurring at the first long-range edge crossed by the chain, which can be reached in half a step from $\eta(O)$ by Assumption (H3). Let $w \in V$ such that $P(w, v) > 0$. From Remark 5.15, $Q_u[\iota(\eta(O)) = w] = \Theta(1/n)$. Using that transition probabilities are bounded uniformly in $n$ by (H1), (H2), we deduce that $Q_u[Y_1 = v] \ge \Theta(1/n)$. On the other hand, if $V(u) = V(v)$ the alternation between $V_1$ and $V_2$ forbids a regeneration at the first long-range edge. This is why we need to suppose $v \in S$ to make sure the chain can backtrack and prevent regeneration at the first long-range. Since $S$ occurs with probability $1-o(1)$ under the uniform law on $V$, centers of the quasi-tree $\mathcal{G}_O$ also have probability $\Theta(1)$ to be in $S$ under $Q_u$. Thus using the above arguments we can lower bound by $\Theta(1/n)$ the probability that the chain goes from $\eta(O)$ to a vertex $y$ with $\iota(y) = v$ using one long-range edge, comes back to $\eta(O)$, which ensures no regeneration occurred on the long-range edge, and returns to $y$, all that within a bounded number of steps. The chain can then escape in $\mathcal{G}_y$ with probability $\Theta(1)$ by Lemma 5.6, which will imply $Y_1 = v$.

The proof of (5.55) is similar but requires taking time into account. Suppose $u \in V_1$ and let $v \in S \cap V_2$. Our argument is illustrated in Figure 5.2. The idea is to use an intermediary component of $V_1$ to make the regeneration time shift by 1. Consider the
set

$$S_1 := \{x \in V \cap S \mid \exists y \neq x \in V, s \leq l : P^2(x, y) > 0 \text{ and } P^s(y, x) > 0\}.$$

From Assumption (H3), $n-o(n)$ vertices of $S \cap V_1$ are recurrent and contained in a communicating class of size at least 3. Consequently if $x \in S \cap V_1$, either there exists $y \neq x$ on a loop around $x$ of length less than $l$ such that $P^2(x, y) > 0$, in which case $x \in S_1$, or $x$ is in a communicating class $\{x, y, z\}$ of size exactly 3 with $P^2(x, x) = 1$. However in that case $P^2(y, z), P^2(z, y) > 0$, so $y, z \in S_1$. Thus $S_1$ has size at least $2n/3 - o(n)$ and probability $\Theta(1)$ under the uniform law on $V_1$ or $Q_w$ for any $w \in V_2$.

For any realization of $\mathcal{G}$, there exists a path $(\eta(O), x, \eta(x), y, \eta(y), z)$ with two long-range edges $(x, \eta(x))$ and $(y, \eta(y))$ whereas $(\eta(O), x), (\eta(x), y), (\eta(y), z)$ are small-range edges with distinct endpoints. If $\iota(\eta(O)) \in S$, which occurs with probability $\Theta(1)$, we can suppose that $x$ was chosen so that $P^{s_1}(\iota(x), \iota(x)) > 0$, for some $s_1 \le l+1$. Similarly, $\iota(\eta(x)) \in S_1$ with probability $\Theta(1)$, in which case we can suppose $y$ was chosen so that there exists a path between $y$ and $\eta(x)$ of length $s_2 \le l$ and a vertex $y' \neq x$ on this path with $P^2(\iota(\eta(x)), \iota(y')) > 0$. Then if $v \in S$ there exists $w \in V_2$ such that $P(w, v) > 0$ and $P(v, w)^{s_3} > 0$ for some $s_3 \le l$. Conditional on the previous values of $\iota, \iota(\eta(y)) = w$ with probability at least $\Theta(1/n)$. Gathering what precedes, make the following observation: from $\eta(O)$ the chain can go to $x$ in half a step and then to $z$ in two more steps, after which it can come back to $x$ in $s_3 + s_2 + s_1$ steps going through $y'$, to eventually return at $z$ in two steps and escape to infinity through $\eta(z)$. We will then have $Y_1 = v, T_1 = t + 1/2$ with $t = 4 + s_1 + s_2 + s_3$.

Now instead of $y$, we can apply the same arguments with $y'$, supposing that the chain reaches a vertex $z'$ with $\iota(\eta(y')) = w$ and $\iota(z') = v$. By construction $z'$ is reachable in just one more step from $x$, but the loop around $x$ which passes through $z'$ takes the same number of steps. Thus the previous argument can be applied similarly with just one time step difference to obtain $Y_1 = v, T_1 = t + 1 + 1/2$. Summing on the values of $\iota(\eta(O)), \iota(\eta(x))$, we obtain that

$$\sum_{t \ge 1} Q_t(u, v) \wedge Q_{t+1}(u, v) \ge \Theta(1/n).$$

The case where $u \in V_2$ is similar, with one less necessary long-range edge to cross to reach a component of $V_1 \cap S_1$, hence the bound applies to all $u \in V$. Then as $|V_2 \cap S| = n - o(n)$ summing over $v \in V_2 \cap S$ yields (5.55). $\square$

Let $\mu$ denote the stationary distribution of the Markov chain $(Y_k)_{k \ge 0}$

$$\mathbb{Q}_{\mu} := \sum_{u \in V} \mu(u) Q_{u}.$$

In the sequel $\mathbb{E}_{\mathbb{Q}_{\mu}}$ denotes the expectation with respect to $\mu$. We use similar notations for variance, covariance, etc.
The fact that $Y$ mixes in $O(1)$ steps will be sufficient for the rest of the analysis of the quasi-tree. Point (ii) in Lemma 5.15 will then be used to obtain the expression of the approximate invariant measure in (5.20).

**Proposition 5.12.** Let $\nu$ be the law of $\iota(\eta(O))$ under $\mathbb{Q}_\mu$. For all $v \in V$,

$$ \nu(v) = \Theta(1/n). \qquad (5.56) $$

Furthermore given $L, t \ge 0$, let $U_t(L) = \sum_{s \le t} \mathbb{1}_{\mathcal{X}_s \in B_{LR}(O, L)}$ denote the total time spent by the chain in $B_{LR}(O, L)$ before $t$. Consider here $\tilde{T}_1 = \tilde{T}_1(L)$ to be the first regeneration time outside $B_{LR}(O, L)$, while for $k \ge 2$, let $\tilde{T}_k$ be the first regeneration time after $\tilde{T}_{k-1}$. For all $\varepsilon \in (0, 1)$ there exists $C(\varepsilon)$ such that for all $L, m \ge 0$ and $t \in \mathbb{N}/2$, for all $x \in B_{LR}(O, L)$, $d_{LR}(O, x) = L$, if $t \ge C(\varepsilon)m^2$ then

$$ \sum_{v \in V} \left| \mathbb{P}_x \left[ \exists k \ge 0 : \tilde{T}_k = t, \iota(\mathcal{X}_t) = v \mid B_{LR}(O, L), U_t(L) \le m \right] - \frac{\nu(v)}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} \right| \le \varepsilon. $$

and

$$ \sum_{v \in V} \left| \mathbb{P} \left[ \exists k \ge 0 : \tilde{T}_k = t, \iota(\mathcal{X}_t) = v \mid \mathcal{X}_{1/2} = x, B_{LR}(O, L), U_t(L) \le m \right] - \frac{\nu(v)}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} \right| \le \varepsilon. $$

*Proof.* The first statement is a direct consequence of (5.53).

Let us prove the second statement. Let $\varepsilon \in (0, 1)$, $m, t \ge 1$. For all $k \ge 1$ let $\tilde{Y}_k := \iota(\mathcal{X}_{\tilde{T}_{k-1/2}})$. Apply Proposition 5.9 with the Markov renewal process of regeneration times considered here. Note that by the Markov property of $(Y, T)$ conditioning by $B_{LR}(O, L), U_t(L) \le m$ yields the same transition kernels as $(Y, T)$ and only affects the law of $(\tilde{Y}_1, \tilde{T}_1)$. Lemmas 5.15 and 5.14 imply that the two quantities $\alpha$ and $\max_{u \in S} \mathbb{E}_u [T_1]$ in this Proposition are bounded uniformly in $n$, as is the mixing time $t_{\text{mix}}^{(Y)}(\varepsilon)$ of $Y$ for all $\varepsilon \in (0, 1)$. Finally, the last statement of Lemma 5.14 implies that

$$ \mathbb{P}_x \left[ \tilde{T}_1 \ge m + C_1(\varepsilon) \mid B_{LR}(O, L), U_{m+C_1(\varepsilon)}(L) \le m \right] \le \varepsilon $$

for some $C_1(\varepsilon) > 0$. This gives the value of the quantity $K_\nu(\varepsilon)$ considered in Proposition 5.9, which thus proves that there exists $C(\varepsilon)$ such that for $t \ge C(\varepsilon)m^2$,

$$ \sum_{u \in V} \left| \mathbb{P}_x \left[ \exists k \ge 0 : \tilde{T}_k = t - 1/2, \tilde{Y}_k = u \mid B_{LR}(O, L), U_t(L) \le m \right] - \frac{\mu(u)}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} \right| \le \varepsilon. $$

Then note that conditional on $\tilde{T}_k = t - 1/2, \tilde{Y}_k = u, \iota(\mathcal{X}_t)$ is distributed as $\iota(\eta(O))$ under $\mathbb{Q}_u$. Finally the arguments apply in the same way if the chain is started at time $x$ at time $1/2$ instead of 0. $\square$
## 5.7 Analysis on the quasi-tree III: concentration of drift and entropy

In this section we establish "nice properties" for the chain $\mathcal{X}$, proving in particular concentration of the drift and entropy.

### 5.7.1 Typical paths in quasi-trees

We start with the following lemma, which will basically ensure the chain $\mathcal{X}$ only visits typical vertices by time $t = O(\log n)$, allowing to use the uniform lower bound on escape probabilities.

**Lemma 5.16.** Let $\mathcal{A}$ be a measurable set of quasi-trees. For all $t \ge 0$,

$$ \begin{aligned} & \max_{u,v \in V} \mathbb{P}_O \left[ \bigcup_{s \le t} \{ \mathcal{G}_{\mathcal{X}_s} \in \mathcal{A} \} \mid \iota(O) = u, \iota(\eta(O)) = v \right] \\ & \le t \max_{u,v \in V} \mathbb{P}_O \left[ \mathcal{G}_O \in \mathcal{A} \mid \iota(O) = u, \iota(\eta(O)) = v \right]. \end{aligned} $$

*Proof.* Fix the types of $O, \eta(O)$. Let $z_0 := O$ and for $i \ge 1$ let $z_i$ be the $i$-th distinct vertex visited by the chain. There are at most $t$ distinct vertices visited up to time $t$, hence

$$ \begin{aligned} \mathbb{P}_O \left[ \bigcup_{s \le t} \{ \mathcal{G}_{\mathcal{X}_s} \in \mathcal{A} \} \mid O, \eta(O) \right] &\le \mathbb{P} \left[ \bigcup_{i \le t} \{ \mathcal{G}_{z_i} \in \mathcal{A} \} \mid O, \eta(O) \right] \\ &\le t \max_{i \ge 0} \mathbb{P} \left[ \mathcal{G}_{z_i} \in \mathcal{A} \mid O, \eta(O) \right]. \end{aligned} $$

Note that for $x \in \mathcal{W}$ the probability $\mathbb{P}_O[z_i = x]$ is measurable with respect to $\mathcal{G} \setminus \mathcal{G}_x$. Thus for all $i \ge 0$,

$$ \begin{aligned} \mathbb{P}_O[\mathcal{G}_{z_i} \in \mathcal{A} \mid \iota(O), \iota(\eta(O))] &= \sum_{x \in \mathcal{W}} \mathbb{P}_O[z_i = x, \mathcal{G}_x \in \mathcal{A} \mid O, \eta(O)] \\ &= \sum_{x \in \mathcal{W}} \mathbb{E}[\mathbb{P}_O[z_i = x] \mathbb{P}_O[\mathcal{G}_x \in \mathcal{A} \mid \mathcal{G} \setminus \mathcal{G}_x] \mid O, \eta(O)]. \end{aligned} $$

Now the second factor in this sum can be bounded as

$$ \mathbb{P}_O[\mathcal{G}_x \in \mathcal{A} \mid \mathcal{G} \setminus \mathcal{G}_x] \le \max_{u,v \in V} \mathbb{P}[\mathcal{G}_{O'} \in \mathcal{A} \mid \iota(O') = u, \iota(\eta(O')) = v] $$

with $(\mathcal{G}', O')$ an independent copy of $(\mathcal{G}, O)$. The remaining terms then sum up to 1, yielding the result. $\square$

The previous Lemma will be combined with the following.
**Lemma 5.17.** Given $\alpha, q_0 \in (0, 1]$ and $l \ge 0$, let $\mathcal{A}_l = \mathcal{A}_l(q_0, \alpha)$ be the set of quasi-trees for which every path of length $l$ starting from $O$ contains a proportion at least $\alpha$ of vertices $x$ satisfying $q_{\text{Esc}}(x) \ge q_0$. There exists a constant $C$ such that for all $l \ge 0$, on the event $\{\mathcal{G} \in \mathcal{A}_l\}$,

$$ \mathbf{P}_O [\exists t > s \ge 0 : \mathcal{X}_s \in \mathcal{G}_x, d_{\text{LR}}(O, \mathcal{X}_s) \ge l, d_{\text{LR}}(O, \mathcal{X}_t) = 0] \le e^{-Cl} \\ \mathbf{P}_O [\exists t \ge 0 : d_{\text{SR}}(O, \mathcal{X}_t) \ge l] \le e^{-Cl}. $$

Similarly, for all $x \in \mathcal{V}$, on the event $\{\mathcal{G}_x \in \mathcal{A}_l\}$,

$$ \mathbf{P}_x [\exists t > s \ge 0 : \mathcal{X}_s \in \mathcal{G}_x, d_{\text{LR}}(x, \mathcal{X}_s) \ge l, d_{\text{LR}}(x, \mathcal{X}_t) = 0] \le e^{-Cl} \\ \mathbf{P}_x [\exists t \ge 0 : \mathcal{X}_t \in \mathcal{G}_x, d_{\text{SR}}(\mathcal{X}_t^\circ, \mathcal{X}_t) \ge l] \le e^{-Cl}. $$

*Proof.* Given $q_0 > 0$, consider the set $\text{Esc} = \text{Esc}(q_0) := \{x \in \mathcal{V} \mid q_{\text{Esc}}(x) \ge q_0\}$. For all $x \in \mathcal{G} \cap \text{Esc} \setminus \{O\}$, $\mathbf{P}_x [\tau_O < \infty] \le 1 - q_{\text{Esc}}(x) < 1 - q_0$.

Let $l \ge 0$ and $\tau_l$ be the first time $t \in \mathbb{N}$ such that $d(O, \mathcal{X}_t) = l$ and $\tau_O$ the hitting time of $O$. By strong Markov's property,

$$ \mathbf{P}_O [\exists t > s \ge 0 : d_{\text{LR}}(O, \mathcal{X}_s) \ge l, d_{\text{LR}}(O, \mathcal{X}_t) = 0] = \mathbf{E}_O [\mathbb{1}_{\tau_l < \infty} \mathbf{P}_{\mathcal{X}_{\tau_l}} [\tau_O < \infty]] \\ \le \max_{x_1:d_{\text{LR}}(O,x_1)=l} \mathbf{P}_{x_1} [\tau_O < \infty]. $$

Let $\tau_{\text{Esc}}^{(k)}$ be the $k$-th hitting time of $\text{Esc} \setminus \{O\}$ and suppose $x_1 \in \mathcal{G}$ is at long-range distance $l$ from $O$. Then $x_1$ must also be at $\mathcal{P}$-distance at least $l$ from $O$, thus if $\mathcal{G} \in \mathcal{A}_l$ and $\mathcal{X}_0 = x_1$ it is impossible that $\tau_O < \tau_{\text{Esc}}^{(\lfloor \alpha l \rfloor)}$ as this would imply the existence of a path contradicting the definition of $\mathcal{A}_l$. Thus when $\mathcal{G} \in \mathcal{A}_l$, applying Strong Markov's property at the successive stopping times $\tau_{\text{Esc}}^{(k)}$ yields

$$ \mathbf{P}_{x_1} [\tau_O < \infty] = \mathbf{P}_{x_1} [\tau_{\text{Esc}}^{(\lfloor \alpha l \rfloor)} \le \tau_O < \infty] \\ \le (1 - q_0)^{\lfloor \alpha l \rfloor}. $$

The argument for the second bound is similar. Let $\tau_{\text{Esc}}^{(k)}$ be now the $k$-th hitting time of $\text{Esc}$, so we do not discard $O$ anymore, and let $\tau_l$ denote now the hitting time of $B_{\text{SR}}(O, l)$. As before, observe it is impossible to have $\tau_l < \tau_{\text{Esc}}^{(\lfloor \alpha l \rfloor)}$ if $\mathcal{G} \in \mathcal{A}_l$. However, to reach $B_{\text{SR}}(O, l)$ there must be no escape to infinity before $\tau_l$. Hence on the event $\{\mathcal{G} \in \mathcal{A}_l\}$,

$$ \mathbf{P}_O [\exists t \ge 0 : d_{\text{SR}}(O, \mathcal{X}_t) \ge l] = \mathbf{P}_O [\tau_l < \infty] \\ = \mathbf{P}_O [\tau_{\text{Esc}}^{(\lfloor \alpha l \rfloor)} \le \tau_l < \infty] \\ \le (1 - q_0)^{\lfloor \alpha l \rfloor}, $$
the last line being obtained by applying the strong Markov property at times $\tau_{\text{Esc}}^{(k)}$.

Finally the two last statements for a starting state $x \in \mathcal{V}$ are proved with the exact same reasoning. $\square$

We now establish an analog of Lemma 5.3 in the quasi-tree setting.

**Lemma 5.18.** Let $\Gamma(R, L, M)$ denote the set of paths $p$ in $\mathcal{G}$ such that $p$ does not deviate from a small-range distance more than $R$, backtrack over a long-range distance $L$ or contain a subpath of length $M$ without a regeneration edge. There exists $C > 0$ and $\alpha \in (0, 1]$ such that for all $R, L, M \ge 0$, for all $t \ge 0$, for any types of $O, \eta(O)$,

$$ \mathbb{P}_O[\mathcal{X}_s \cdots \mathcal{X}_{s+t} \notin \Gamma(R, L, M) \mid O, \eta(O)] \le (s+t)e^{-C(R^\alpha L^\beta M^\alpha)}. $$

*Proof.* Fix $R, L, M$, $s, t \ge 0$ and the types of $O, \eta(O)$. Let us start with the deviation property:

$$ \begin{aligned} \mathbb{P}_O[\exists t' \in [s, s+t]: &d_{\text{SR}}(\mathcal{X}_{t'}^{\circ}, \mathcal{X}_{t'}) \ge R \mid O, \eta(O)] \\ &\le \mathbb{P}_O[\exists t' \le s+t: d_{\text{SR}}(O, \mathcal{X}_{t'}) \ge R \mid O, \eta(O)] \\ &+ \mathbb{P}[\exists t_1 \le t_2 \le s+t: \mathcal{X}_{t_2} \in \mathcal{G}_{\mathcal{X}_{t_1}}, d_{\text{SR}}(\mathcal{X}_{t_2}^{\circ}, \mathcal{X}_{t_2}) \ge R \mid O, \eta(O)] \end{aligned} \quad (5.57) $$

Given $q_0 > 0$, $\alpha \in (0, 1)$, let $\mathcal{A}_R = \mathcal{A}_R(q_0, \alpha)$ be the set of quasi-trees, for which every path of length $R$ starting from $O$ contains a proportion at least $\alpha$ of vertices $x$ such that $q_{\text{Esc}}(x) \ge q_0$. Then the first term can be bounded as

$$ \mathbb{P}_O[\exists t' \le s+t: d_{\text{SR}}(O, \mathcal{X}_{t'}) \ge R \mid O, \eta(O)] \le \mathbb{P}[\mathcal{G} \notin \mathcal{A}_R \mid O, \eta(O)] \\ + \mathbb{E}[1_{\mathcal{G} \in \mathcal{A}_R} \mathbf{P}_O[\exists t' \le s+t: d_{\text{SR}}(O, \mathcal{X}_{t'}) \ge R \mid O, \eta(O)]. $$

By Proposition 5.5 there exist constants $q_0, \alpha > 0$ such that the first term can be made exponentially small in $R$, while Lemma 5.17 shows the second term is also exponentially small. The second term of (5.57) can be bounded similarly:

$$ \begin{aligned} & \mathbb{P}[\exists t_1 \le t_2 \le s+t: \mathcal{X}_{t_2} \in \mathcal{G}_{\mathcal{X}_{t_1}}, d_{\text{SR}}(\mathcal{X}_{t_2}^{\circ}, \mathcal{X}_{t_2}) \ge R \mid O, \eta(O)] \\ & \le \mathbb{P}[\exists t_1 \le s+t: \mathcal{G}_{\mathcal{X}_{t_1}} \notin \mathcal{A}_R \mid O, \eta(O)] \\ & + \sum_{t_1 \le s+t} \mathbb{E}[1_{\mathcal{G}_{\mathcal{X}_{t_1}} \in \mathcal{A}_R} \mathbf{P}_{\mathcal{X}_{t_1}}[\exists t_2 \ge 0: \mathcal{X}_{t_2} \in \mathcal{G}_{\mathcal{X}_{t_1}}, d_{\text{SR}}(\mathcal{X}_{t_2}^{\circ}, \mathcal{X}_{t_2}) \ge R \mid O, \eta(O)] \\ & \le (s+t)e^{-CR} \end{aligned} $$

for some constant $C > 0$, using Lemma 5.16 and Proposition 5.5 to bound the first term and Lemma 5.17 for the second.
The probability that the trajectory backtrack over a long-range distance $L$ between $s$ and $s+t$ is established with the same arguments. It then remains to handle the regeneration requirement. By union bound for all $t \ge 0$ and $u \in V$

$$ \begin{aligned} \mathbb{P}_O [ \exists s' \in [s, s+t] : [s', s' + M] \cap \{T_k, k \ge 1\} = \emptyset | O, \eta(O) ] & \\ \le \mathbb{P}_O [ \exists k \le s + t : T_{k+1} - T_k \ge M | O, \eta(O) ] & \\ \le (s+t) \max_{k \le s+t} \mathbb{P}_O [ T_{k+1} - T_k \ge M | O, \eta(O) ]. \end{aligned} $$

The stretched exponential tails of regeneration times (Lemma 5.14) conclude the proof.

□

## 5.7.2 Concentration of the drift

**Proposition 5.13.** Let $d := \frac{\mathbb{E}_{\mathbb{Q}_\mu}[L_1]}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]}$. Then for all $s \ge 0$, a.s.

$$ \frac{d_{\text{LR}}(\mathcal{X}_s, \mathcal{X}_{s+t})}{t} \xrightarrow{t \to \infty} d. \qquad (5.58) $$

Furthermore, there exists $\alpha > 0$ for which the following holds. For all $\varepsilon > 0$ there exists $C = C(\varepsilon)$ such that for all $s, t \ge 0$, for all types of $O, \eta(O)$,

$$ \mathbb{P}_O \left[ |d_{\text{LR}}(\mathcal{X}_s, \mathcal{X}_{s+t}) - dt| > C\sqrt{t} \mid O, \eta(O) \right] \le \varepsilon + C\sqrt{s}e^{-t^\alpha}. \qquad (5.59) $$

*Proof.* For notational simplicity we omit writing the conditionning by $\iota(O)$ and $\iota(\eta(O))$. As can be checked this conditionning does not affect the proof as the technical results that will be used hold even conditional on the long-range edge at the root. For all $t \ge 0$, let

$$ N_t := \max\{k \ge 0 \mid T_k \le t\}. $$

Then

$$ L_{N_t} \le d_{\text{LR}}(O, \mathcal{X}_t) \le L_{N_t} + T_{N_t+1} - T_{N_t}. $$

It is easy to prove that $(T_{N_t+1} - T_{N_t})/t \to 0$, hence the law of large numbers (5.58) follows from Lemma 5.13 and Proposition 5.7 which prove $N_t/t \xrightarrow{t \to \infty} 1/\mathbb{E}_\mu[T_1]$ and $L_k/k \xrightarrow{k \to \infty} \mathbb{E}_\mu[L_1]$ a.s..

Then we establish (5.59) in the case $s = 0$. It suffices to prove that for all $\varepsilon > 0$ there exists $C > 0$ such that for all $t, k \ge 0$

$$ \mathbb{P}_O \left[ \left| N_t - \frac{t}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} \right| > C\sqrt{t} \right] \le \varepsilon \qquad (5.60) $$

$$ \mathbb{P}_O \left[ \left| L_k - \mathbb{E}_{\mathbb{Q}_\mu}[L_1] k \right| > C\sqrt{k} \right] \le \varepsilon. $$
Indeed if this holds using that regeneration levels are non-decreasing we deduce that $|L_{N_t} - dt| > C\sqrt{t}$ with probability at most $\varepsilon$ for some $C = C(\varepsilon)$, whereas union bound and Markov's inequality show that for all $C' > 0$

$$ \begin{aligned} & \mathbb{P}_O \left[ T_{N_t+1} - T_{N_t} > C' \sqrt{t}, \left| N_t - \frac{t}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} \right| \le C \sqrt{t} \right] \\ & \le \mathbb{P}_O \left[ \exists k : \left| k - \frac{t}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} \right| \le C \sqrt{t}, T_{k+1} - T_k > C' \sqrt{t} \right] \\ & \le 2C \sqrt{t} \frac{\max_{u \in V} \mathbb{E}_{\mathbb{Q}_u}[T_1] \lor \mathbb{E}_O[T_1]}{C' \sqrt{t}} \\ & \le \varepsilon \end{aligned} $$

for large enough $C' = C'(\varepsilon)$, using also Lemma 5.14 to argue the expectations are $O(1)$.

Let us now prove the claim. We only prove the upper tail of the first inequality as the other bounds are established similarly. Let

$$ k = \left[ \frac{t}{\mathbb{E}_{\mathbb{Q}_\mu}[T_1]} + C\sqrt{t} \right]. $$

The objective is to apply the Bienaymé Chebychev inequality with the variance bound for Markov chains (5.50), which is valid only when started at equilibrium. Let $\varepsilon \in (0, 1/2)$ and $t_0 = t_{\text{mix}}^{(Y)}(\varepsilon)$ be the mixing time of $(Y_l)_{l \ge 0}$, then decompose $T_k = Z_1 + Z_2$ with $Z_1 = \sum_{i=1}^{t_0} T_i - T_{i-1}$ and $Z_2 = \sum_{i=t_0+1}^{k} T_i - T_{i-1}$.

We write further $Z'_2 := Z_2 - \mathbb{E}_{\mathbb{Q}_\mu}[Z_2]$. Stationarity implies $\mathbb{E}_{\mathbb{Q}_\mu}[Z_2] = (k-t_0)\mathbb{E}_{\mathbb{Q}_\mu}[T_1]$ hence

$$ \begin{aligned} \mathbb{P}_O[N_t > k] &= \mathbb{P}[T_k < t] \\ &= \mathbb{P}_O[Z_1 + Z'_2 < t - (k - t_0)\mathbb{E}_{\mathbb{Q}_\mu}[T_1]] \\ &\le \mathbb{P}_O[Z_1 + Z'_2 < z] \end{aligned} $$

where

$$ z := (t_0 + 1)\mathbb{E}_{\mathbb{Q}_\mu}[T_1] - C\mathbb{E}_{\mathbb{Q}_\mu}[T_1]\sqrt{t}. $$

By Lemmas 5.14 and 5.15, $t_0$ and the expectation above can be bounded by constants independent of $n$. Thus for some constant $C' > 0$,

$$ \begin{aligned} \mathbb{P}_O[Z_1 + Z'_2 < z] &\le \mathbb{P}_O[|Z_1 + Z'_2| > 2C'\sqrt{t}] \\ &\le \mathbb{P}_O[Z_1 > C'\sqrt{t}] + \mathbb{P}_O[|Z'_2| > C'\sqrt{t}]. \end{aligned} $$

From Lemma 5.15 and the fact that $t_0 = O(1)$, we also deduce that $\mathbb{E}_O[Z_1] = O(1)$ so Markov's inequality ensures the first term is smaller than $\varepsilon$ for all $t$ by taking the
constant $C'$ large enough. For the second term, since $t_0 = t_{\text{mix}}^{(Y)}(\varepsilon)$

$$ \begin{aligned} \mathbb{P}_{O} [|Z'_{2}| > C' \sqrt{t}] &= \sum_{y} \mathbb{P}_{O} [Y_{t_0} = y] \mathbb{Q}_{y} [|T_{k-t_0} - \mathbb{E}_{\mathbb{Q}_{\mu}} [T_{k-t_0}]| > C' \sqrt{t}] \\ &\le \|Y_{t_0} - \mu\|_{\text{TV}} + \mathbb{Q}_{\mu} [|T_{k-t_0} - \mathbb{E}_{\mathbb{Q}_{\mu}} [T_{k-t_0}]| > C' \sqrt{t}] \\ &\le \varepsilon + \mathbb{Q}_{\mu} [|T_{k-t_0} - \mathbb{E}_{\mathbb{Q}_{\mu}} [T_{k-t_0}]| > C' \sqrt{t}]. \end{aligned} $$

Using the Bienaymé-Chebychev inequality with (5.50), we deduce

$$ \mathbb{Q}_{\mu} [|T_{k-t_0} - \mathbb{E}_{\mathbb{Q}_{\mu}} [T_{k-t_0}]| > C' \sqrt{t}] \le \frac{\text{Var}_{\mathbb{Q}_{\mu}} (T_{k-t_0})}{(C')^2 t} \le \frac{C''(k-t_0) \text{Var}_{\mathbb{Q}_{\mu}} [T_1]}{(C')^2 t}, $$

for some constant $C'' > 0$, as the regeneration chain has constant mixing time by Lemma 5.15. By Lemma 5.14, the variance of $T_1$ is of constant order while $k = O(t)$, hence the probability above can be made smaller than $\varepsilon$ for all $t$ by taking $C'$ large enough.

For the general case $s \ge 0$, we apply the previous arguments with a shifted version of the processes. For $s \ge 0$ fixed, consider

$$ T_k^{(s)} := T_{N_s+k-s}, \quad L_k^{(s)} := L_{N_s+k} - d_{\text{LR}}(O, \mathcal{X}_s) $$

if $k \ge 1$ and $T_0^{(s)} := 0$, $L_0^{(s)} := 0$. Then let

$$ N_t^{(s)} := \max\{k \ge 0 \mid T_k^{(s)} \le t\}. $$

Notice that

$$ L_{N_t^{(s)}}^{(s)} \le d_{\text{LR}}(\mathcal{X}_s, \mathcal{X}_{s+t}) \le L_{N_t^{(s)}}^{(s)} + T_{N_t^{(s)}+1}^{(s)} - T_{N_t^{(s)}}^{(s)}. $$

These processes still satisfy the conclusions of Lemma 5.13 and have the same increments as the usual regeneration times. Thus the only thing to be careful when applying the above arguments is the law of the first regeneration time that now depends on $s$. Using the concentration (5.60) for $N_s$, union bound and Lemma 5.14, we can see that for all $m \ge 0$,

$$ \begin{aligned} \mathbb{P}[T_1^{(s)} > m] &= \sum_{k \ge 0} \mathbb{P}[N_s = k, T_{k+1} - s > m] \\ &\le \mathbb{P}[|N_s - s/\mathbb{E}_{\mathbb{Q}_{\mu}}[T_1]| > C\sqrt{s}] + \mathbb{P}[\exists k : |k - s/\mathbb{E}_{\mathbb{Q}_{\mu}}[T_1]| \le C\sqrt{s}, T_{k+1} - T_k > m] \\ &\le \varepsilon + 2C\sqrt{s}e^{-m^{\alpha}}. \end{aligned} $$

Taking $m = \sqrt{t}$ yields the stretched exponential term of (5.59). Then for higher regeneration times $(T_k^{(s)})_{k \ge 2}$, the above arguments apply. $\square$
### 5.7.3 Concentration of the entropy

The concentration of the entropy in Proposition 5.2 is based on the convergence of the entropy for the loop-erased chain in the quasi-tree, that is the convergence of $-\log \mathbf{P}[\xi'_k = \xi_k | \xi]/k$ towards a constant, the entropic rate of the chain. Such convergence is well-known in the contest of groups or random walks on Galton-Watson trees, see [102, 126]. We will however not prove this result but establish concentration directly for a notion of weights similar to those of (5.16). Of course, these are designed to mimick the law of the loop-erased chain, so the argument is similar. In fact the first step is to prove the convergence and concentration of the loop-erased chain when restricted to regeneration steps.

**Lemma 5.19.** Let $\xi'$ be an independent copy of the loop-erased chain $\xi$. There exists $h' = \Theta(1)$ such that

$$ \lim_{k \to \infty} \frac{-\log \mathbf{P}[\xi'_{L_k} = \xi_{L_k} | \mathcal{X}]}{k} = h'. \qquad (5.61) $$

Furthermore, for all $\varepsilon > 0$, there exists $C(\varepsilon) > 0$ such that for all $k, l \ge 1$,

$$ \begin{aligned} & \mathbb{P}[|-\log \mathbf{P}[\xi'_{L_k} = \xi_{L_k} | \mathcal{X}] - h'k| > C(\varepsilon)\sqrt{k} \mid O, \eta(O)] \le \varepsilon, \\ & \mathbb{P}[|-\log \mathbf{P}[\xi'_{L_{k+l}} = \xi_{L_{k+l}} | \mathcal{X}, \xi'_{L_k} = \xi_{L_k}] - h'l| > C\sqrt{l} \mid O, \eta(O)] \le \varepsilon. \end{aligned} \qquad (5.62) $$

*Proof.* Again let us omit the conditioning by $O, \eta(O)$ which does not affect the argument. Given $k \ge 1$, we write $\mathcal{G}(k) := \mathcal{G}_{\mathcal{X}_{T_k}}$, to simplify notations. Given $u \in V$ and $g$ a possible realization of the subquasi-tree $\mathcal{G}_O$, let

$$ \mathbf{Q}_{u,g} := \mathbb{P}[\cdot \mid \mathcal{X}_{1/2} = \eta(O), \tau_O = \infty, \iota(O) = u, \mathcal{G}_O = g]. $$

Finally let $\xi'(k)$ denote a loop-erased chain on $\mathcal{G}(k-1)$, started at $\mathcal{X}_{T_{k-1}}$, independent of $\mathcal{X}$. Having $\xi'_{L_k} = \xi_{L_k}$ implies $\xi_{L_m} \in \xi'$ for all $m \le k$. Thus for $k \ge 2$

$$ \begin{aligned} \mathbf{P}[\xi_{L_k} \in \xi' | \mathcal{X}] &= \mathbf{E}[1(\xi'_{L_{k-1}} = \xi_{L_{k-1}}) \mathbf{P}[\xi'_{L_k} = \xi_{L_k} | \mathcal{X}, (\xi'_i)_{i \le L_{k-1}}] | \mathcal{X}] \\ &= \mathbf{E}[1(\xi'_{L_{k-1}} = \xi_{L_{k-1}}) \mathbf{Q}_{Y_{k-1}, \mathcal{G}(k-1)}[\xi_{L_k} \in \xi'(k) | (\mathcal{X}_t)_{t \ge T_{k-1}}] | \mathcal{X}] \\ &= \mathbf{P}[\xi'_{L_{k-1}} = \xi_{L_{k-1}} | \mathcal{X}] \mathbf{Q}_{Y_{k-1}, \mathcal{G}(k-1)}[\xi_{L_k} \in \xi'(k) | (\mathcal{X}_t)_{t \ge T_{k-1}}]. \end{aligned} $$

Letting $Z_1 := -\log \mathbf{P}[\xi'_{L_1} = \xi_{L_1} | \mathcal{X}]$ and

$$ Z_i := -\log \mathbf{Q}_{Y_{i-1}, \mathcal{G}(i-1)}[\xi_{L_i} \in \xi'(i) | (\mathcal{X}_t)_{t \ge T_{i-1}}] $$

for $i \ge 2$, we just proved that

$$ -\log \mathbf{P}[\xi'_{L_k} = \xi_{L_k} | \mathcal{X}] = \sum_{i=1}^{k} Z_i $$
and

$$-\log \mathbf{P}[\xi'_{L_{k+l}} = \xi_{L_{k+l}} | \mathcal{X}, \xi'_{L_k}] = \sum_{i=k+1}^{k+l} Z_i.$$

Under $\mathbb{Q}_\mu$, the sequence $(Y_k)_{k \ge 1}$ is stationary. Lemma 5.13 then shows that $(Z_i)_{i \ge 2}$ is stationary as well. Provided $Z_1 < \infty$ a.s., $\mathbb{E}_O[Z_1] < \infty$ and $\mathbb{E}_{\mathbb{Q}_\mu}[|Z_1|] < \infty$, which is proved afterwards, Birkhoff's ergodic theorem implies the law of large numbers (5.61).

Let us now show that for all $l \ge 1$, there exists a constant $C_l \ge 0$ such that

$$\mathbb{E}_O[|Z_1|^l] < C_l$$

and for all $i \ge 2$ and $u \in V$

$$\mathbb{E}_{\mathbb{Q}_u}[|Z_i|^l] \le C_l. \qquad (5.63)$$

This is sufficient to justify that $Z_1 < \infty$ a.s., $\mathbb{E}_{\mathbb{Q}_\mu}|Z_i| < \infty$ and will be used to prove (5.62). We only treat the case $i \ge 2$ as the case $i = 1$ is similar. Let $l \ge 1$ and $u \in V$. Let us identify here a long-range edge $(\eta(x), x)$ with its center vertex $x$. By Lemma 5.13

$$\begin{aligned} \mathbb{E}_{\mathbb{Q}_u}[|Z_i|^l] &= \mathbb{E}_{\mathbb{Q}_u} \left[ \sum_{x \in \mathcal{V}} \mathbf{Q}_{u,\mathcal{G}}[\mathcal{X}_{T_i} = x] (-\log \mathbf{Q}_{Y_{i-1},\mathcal{G}(i-1)}[x \in \xi'(i)])^l \right] \\ &= \sum_{v \in \mathcal{V}} \mathbb{Q}_v[Y_{i-1} = v] \mathbb{E}_{\mathbb{Q}_v} \left[ \sum_{x \in \mathcal{V}} \mathbf{Q}_{v,\mathcal{G}}[\mathcal{X}'_{T_1} = x] (-\log \mathbf{Q}_{v,\mathcal{G}}[x \in \xi'])^l \right] \end{aligned}$$

where $\mathcal{X}'$ is an independent copy of $\mathcal{X}$ under the law $\mathbf{Q}_{v,\mathcal{G}}$, $\xi'$ is its loop-erased trace and $T_1'$ its first regeneration time. Thus it suffices to prove the upper bound

$$\max_{u \in \mathcal{V}} \mathbb{E}_{\mathbb{Q}_u} \left[ \sum_{x \in \mathcal{V}} \mathbf{Q}_{u, \mathcal{G}}[\mathcal{X}_{T_1} = x] (-\log \mathbf{Q}_{u, \mathcal{G}}[x \in \xi])^l \right] \le C_l.$$

Fix $u \in V$. For all $k \ge 1$, if $d_P(\eta(O), x) = k$, the chain goes from $\eta(O)$ to $x$ with probability at least $\delta^k$, after which it escapes to infinity in $\mathcal{G}_x$ with probability $q_{\text{Esc}}(x)$, hence

$$\sum_{x \in \mathcal{V}} \mathbf{Q}_{u, \mathcal{G}}[\mathcal{X}_{T_1} = x] (-\log \mathbf{Q}_{u, \mathcal{G}}[x \in \xi])^l \le \sum_{k \ge 1} \mathbf{Q}_{u, \mathcal{G}}[d_P(\eta(O), \mathcal{X}_{T_1}) = k] k^l (-\log \delta)^l \\ + \sum_{x \in \mathcal{V}} \mathbf{Q}_{u, \mathcal{G}}[\mathcal{X}_{T_1} = x] (-\log q_{\text{Esc}}(x))^l$$

Averaging on the environment yields

$$\mathbb{E}_{\mathbb{Q}_u} \left[ \sum_{x \in \mathcal{V}} \mathbf{Q}_{u, \mathcal{G}}[\mathcal{X}_{T_1} = x] (-\log \mathbf{Q}_{u, \mathcal{G}}[x \in \xi])^l \right] \le (-\log \delta)^l \mathbb{E}_{\mathbb{Q}_u} \left[ d_P(\eta(O), \mathcal{X}_{T_1})^l \right] \\ + \mathbb{E}_{\mathbb{Q}_u} \left[ (-\log q_{\text{Esc}}(\mathcal{X}_{T_1}))^l \right]$$

Now for any $k \ge 1$,

$$\mathbb{Q}_u [d_P(\eta(O), \mathcal{X}_{T_1}) \ge k] \le \mathbb{Q}_u [T_1 \ge k]$$
which is stretched exponential by Lemma 5.14, hence $\mathbb{E}_{\mathbb{Q}_u}[d_{\mathcal{P}}(\eta(O), \mathcal{X}_{T_1})^l] = O(1)$. On the other hand

$$ \mathbb{E}_{\mathbb{Q}_u} [(-\log q_{\text{Esc}}(\mathcal{X}_{T_1}))^l] = \sum_{v \in V} \mathbb{Q}_u [Y_1 = v] \mathbb{E}_{\mathbb{Q}_v} [(-\log q_{\text{Esc}}(\eta(O)))^l]. $$

By Proposition 5.4 and Remark 5.15, $\mathbb{E}_{\mathbb{Q}_v} [(-\log q_{\text{Esc}}(\eta(O)))^l] = O(1)$ for any $v \in V$, hence $\mathbb{E}_u [(-\log q_{\text{Esc}}(\mathcal{X}_{T_1}))^l] = O(1)$ as well and we deduce (5.63) for some constant $C_l$.

To establish (5.62), we argue as in the end of the proof of Proposition 5.13 for the drift. The bound is eventually proved using the Bienaymé-Chebychev inequality. Since $Y$ mixes in constant time $t_0$ by Lemma 5.15, separating the sum $\sum_{i=1}^k Z_i$ into two sums corresponding respectively to regeneration times before or after $t_0$ shows that it suffices to establish the variance bound $\text{Var}_{\mathbb{Q}_\mu} [\sum_{i=2}^k Z_i] = O(k)$ under the stationary measure. Let us modify the definition of $Z_1$, setting $Z_1 := -\log \mathbf{Q}_{\iota(O), \mathcal{G}_O} [\xi_{L_1} \in \xi' | \mathcal{X}]$ so that the whole sequence $(Z_i)_{i \ge 1}$ is stationary. It then suffices to prove that for all $k \ge 1$, $\text{Cov}_{\mathbb{Q}_\mu}(Z_1, Z_k)$ is stretched exponential in $k$.

Let $k > 1$. Let $\tau'_{k-1}$ be the first time the chain $\mathcal{X}'$ reaches the $L_{k-1}$-th level, and consider the loop-erased trace $\xi'(1, k)$ obtained from observing $\mathcal{X}'$ up to time $\tau'_{k-1}$. Define $W_1 := \exp(-Z_1)$, $W_{1k} := \mathbf{Q}_{\iota(O), \mathcal{G}_O} [\xi_{L_1} \in \xi'(1, k) | \mathcal{X}]$, $Z_{1,k} := -\log W_{1k}$. By the inequality $|\log x - \log y| \le |x - y|/(x \wedge y)$,

$$ |Z_1 - Z_{1,k}| \le \frac{|W_1 - W_{1k}|}{W_1 \wedge W_{1k}} $$

Observe that if $\xi_{L_1}$ is exclusively in one of the two paths $\xi'(1, k)$, $\xi'$ then the chain $\mathcal{X}'$ backtracks from the $L_{k-1}$-th level to the $(L_1 - 1)$-th. Letting $A'$ denote this event, we thus have

$$ |W_1 - W_{1k}| \le \mathbf{Q}_{\iota(O), \mathcal{G}_O} [A' | \mathcal{X}]. $$

Let $\mathcal{A}_k(q_0, \alpha)$ be the set of quasi-trees for which every length $k$ path from the root contains a proportion at least $\alpha > 0$ of vertices $x$ such that $q_{\text{Esc}}(x) \ge q_0 > 0$. For some constants $q_0, \alpha, \varepsilon \in (0, 1)$ and $C_1 > 0$ to determine, consider the events

$$ E_0 := \{\mathcal{G}_O \in \mathcal{A}_k(q_0, \alpha)\} \cap \{q_{\text{Esc}}(\xi_{L_1}) \ge \varepsilon^k\} $$

$$ E_1 = \{d_{\mathcal{P}}(O, \mathcal{X}_{T_1}) \le k/C_1\} $$

If $\mathcal{G}_O \in \mathcal{A}_k(q_0, \alpha)$, Lemma 5.17 implies $\mathbf{Q}_{\iota(O), \mathcal{G}_O} [A' | \mathcal{X}]$ is exponentially small in $k$. On $E_1$, the chain $\mathcal{X}'$ goes from $O$ to $\xi_{L_1}$ with probability at least $\delta^{k/C_1}$, after which $\xi_{L_1} \in \xi' = \xi'(1, k)$ if the chain $\mathcal{X}'$ escapes to infinity. Thus on the event $E_0 \cap E_1$,

$$ W_1 \wedge W_{1k} \ge \delta^{k/C_1} \varepsilon^k, $$
hence choosing the constant $C_1$ large enough and $\varepsilon$ close enough to 1 yields eventually

$$|Z_1 - Z_{1,k}| 1_{E_0 \cap E_1} \le e^{-c_1 k}$$

for some constant $c_1 > 0$. Next we claim that given this choice of $C_1$ and $\varepsilon$, there is an appropriate choice of the remaining parameters that ensures

$$\mathbb{Q}_{\mu}[E_0^c] \le e^{-c_2 k}, \quad \mathbb{Q}_{\mu}[E_1^c] \le e^{-c_2 k^{\beta}}$$

for some $c_2 > 0$ and $\beta \in (0, 1]$. By Remark 5.15 and Proposition 5.5 there exist $q_0, \alpha > 0$ such that $\mathcal{G}_O \notin \mathcal{A}_k(q_0, \alpha)$ has exponentially small probability, whereas Proposition 5.4 implies $q_{\text{Esc}}(\xi_{L_1}) < \varepsilon^k$ with doubly exponentially small probability. For $E_1$ observe $d_{\mathcal{P}}(O, \mathcal{X}_{T_1}) > k/C_1$ implies $T_1 > k/C_1$ which has stretched exponentially small probability by Lemma 5.14. Then by the moment bounds (5.63) for some $c_3 > 0$,

$$
\begin{align*}
\mathrm{Cov}_{\mathbb{Q}_{\mu}}(Z_1, Z_{2k}) &= \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_1 - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_1])(Z_{2k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}])1_{E_1}] + O(e^{-c_3 k^{\beta}}) \\
&= \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_1 - Z_{1,k})Z_{2k}1_{E_1}] - \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_1 - Z_{1,k})1_{E_1}]\mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}] \\
&\quad + \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_{1,k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_1])(Z_{2k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}])1_{E_1}] + O(e^{-c_3 k^{\beta}}) \\
&= \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_1 - Z_{1,k})Z_{2k}1_{E_0 \cap E_1}] - \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_1 - Z_{1,k})1_{E_0 \cap E_1}]\mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}] \\
&\quad + \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_{1,k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_1])(Z_{2k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}])1_{E_1}] + O(e^{-c_3 k^{\beta}}) \\
&= \mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_{1,k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_1])(Z_{2k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}])1_{E_1}] + O(e^{-c_3 k^{\beta}}).
\end{align*}
$$

Note that by construction $Z_{1,k}1_{E_1}$ is measurable with respect to $\mathcal{G} \setminus \mathcal{G}(k)$ and $(\mathcal{X}_t)_{t \le T_{k-1}}$, whereas $Z_{2k}$ is measurable with respect to $\mathcal{G}(2k-1)$ and $(\mathcal{X}_t)_{T_{2k-1} \le t}$ only. Thus by conditioning on $\{Y_{k-1}, Y_{2k-1}\}$ Markov's property implies

$$\mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_{1,k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_1])(Z_{2k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}])1_{E_1}] \\
= \mathrm{E}_{\mathbb{Q}_{\mu}}[\mathrm{E}_{\mathbb{Q}_{\mu}}[(Z_{1,k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_1])1_{E_1} | Y_{k-1}]\mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k} - \mathrm{E}_{\mathbb{Q}_{\mu}}[Z_{2k}] | Y_{2k-1}]]$$

The right-hand side can be written as $\mathrm{E}_{\mathbb{Q}_{\mu}}[f(Y_{k-1})g(Y_{2k-1})]$ for some functions $f, g$. From the proof of Proposition 5.11, this expectation is exponentially small in $k$, provided $f$ and $g$ have finite moments. This is the direct consequence of (5.63) for $g$, while for $f$ we need moment bounds on $Z_{1k}$. These can be established with the same arguments as above. $\square$

To relate the previous concentration with the weights (5.16), we define similar weights in the quasi-tree. Let $\tau_l$ denote here the first time $t$ such that $d_{\text{LR}}(\mathcal{X}_0, \mathcal{X}_t) = l$. For all long-range edge $e \in \mathcal{G}$, write $\mathcal{G}_e$ for the subquasi-tree at any endpoint of $e$ (they give the same quasi-tree). Given $R, L \ge 0$, $x \in \mathcal{V}$ and a long-range edge $e$ at long-range
distance 0 from $x$

$$ 
\begin{aligned}
w_{x,R,L}(e) &:= \mathbf{P}_x \left[ \mathcal{X}_{\tau_L} \in \mathcal{G}_e, \tau_L < \tau_{\text{SR}}^{(R)} \right] \\
w_{R,L}(e \mid x) &:= \mathbf{P} \left[ \mathcal{X}_{\tau_L} \in \mathcal{G}_e, \tau_L < \tau_{\text{SR}}^{(R)} \mid \mathcal{X}_{1/2} = x, \tau_L < \tau_{\eta(x)} \right]
\end{aligned} 
\qquad (5.64) $$

Then if $e = (e_i)_{i=1}^k$ is a long-range non-backtracking path starting from $B_{LR}(x, 0)$, set

$$ w_{x,R,L}(e) := w_{x,R,L}(\xi_1) \prod_{i=2}^{k} w_{R,L}(\xi_i | \xi_{i-1}^{+}) $$

where the product if taken equal to 1 if empty.

In the proof of Lemma 5.19, we introduced the measure

$$ \mathbf{Q}_{u,g} := \mathbb{P}[\cdot \mid \mathcal{X}_{1/2} = \eta(O), \iota(O) = u, \tau_O = \infty, \mathcal{G}_O = g]. $$

where $u \in V$ and $g$ is a possible realization of the subquasi-tree $\mathcal{G}_O$. We use a notation which may be reminiscent of (5.19) as these two measures are very similar, although note that here $u$ is not the type of the starting state of the chain but its long-range neighbour. There should be no risk of confusion as the measure of (5.19) will not be used until Section 5.9. Using the same arguments as for the lemma, we can see that

$$ \mathbf{P}_x[\xi_1 = e_1, \dots, \xi_k = e_k] = \mathbf{P}_x[\xi_1 = e_1] \prod_{i=2}^{k} \mathbf{Q}_{\iota(e_{i-1}^{+}), \mathcal{G}_{e_{i-1}}} [\xi_1 = e_i]. \qquad (5.65) $$

The following Lemma establishes thus a bound on individual weights.

**Lemma 5.20.** There exist constants $C, C_0, C_1, C_2 > 0$ such that for all $R, L > 0$ the following holds:

(i) with probability at least $1 - e^{-C(R \wedge L)}$, for all long-range edge $e$ such that $d_{\text{SR}}(O, e^-) < R$,

$$ |\log w_{O,R,L}(e) - \log \mathbf{P}_O[\xi_1 = e]| \le C_0 e^{-C_1 L + C_2 R}, $$

(ii) for all $x \in V$, with probability at least $1 - e^{-C(R \wedge L)}$ conditional on $\mathcal{G} \setminus \mathcal{G}_x$, for all long-range edge $e$ of $\mathcal{G}_x$ such that $d_{\text{SR}}(x, e^-) < R$

$$ |\log w_{R,L}(e \mid x) - \log \mathbf{Q}_{\iota(e^+), \mathcal{G}_e}[\xi_1 = e]| \le C_0 e^{-C_1 L + C_2 R}. $$

*Proof.* We prove the first bound in detail. Given $k \ge 1$, let $\mathcal{A}_k = \mathcal{A}_k(q_0, \alpha)$ be the set of quasi-trees for which every path of length $k$ starting from the root contains a proportion at least $\alpha$ of vertices $x$ such that $q_{\text{Esc}}(x) \ge q_0$. Let

$$ E_0 := \{ \mathcal{G}_O \in \mathcal{A}_R \cap \mathcal{A}_L \} \cap \{ \forall x \in B_{\text{SR}}(O, R) : q_{\text{Esc}}(x) \ge c_0 e^{-c_1 R} \}. $$

We claim the event $E_0^c$ occurs with exponentially small probability in $R \wedge L$ for an appropriate choice of parameters. First there exist $q_0, \alpha > 0$ such that $\mathcal{G} \notin \mathcal{A}_R \cap \mathcal{A}_L$ with
exponentially small probability by Proposition 5.5. Next, Proposition 5.4 implies there exists $c \in (0, 1)$ such that for a fixed $x \in B_{SR}(O, R)$, $q_{Esc}(x) < c\delta^{4R}$ with probability at most $c^{2R}$. However there are $O(\Delta^R)$ vertices in this ball, hence the claim by union bound.

Notice then that to have one of the two events $e \in \xi$ or $\mathcal{X}_{\tau_L} \in \mathcal{G}_e$ realized exclusively, the chain needs to backtrack from level $L$ to level 0. On $E_0$, this occurs with probability exponentially small in $L$ by Lemma 5.17. Thus on $E_0$

$$|w_{O,R,L}(e) - \mathbf{P}_O[\xi_1 = e]| \le \mathbf{P}_O[\tau_{SR}^{(R)} \wedge \tau_{NB}^{(L)} < \infty] \le e^{-C'(R \wedge L)}$$

for some constant $C' > 0$. On the other hand, on $E_0$

$$w_{O,R,L}(e) \wedge \mathbf{P}_O[\xi_1 = e] \ge \delta^R q_0$$

as the right-hand side is a lower bound on the probability to go from $O$ to $e$ and then escape to infinity, which forces both $e \in \xi$ and $\mathcal{X}_{\tau_L} \in \mathcal{G}_e$. Using $|\log x - \log y| \le |x - y|/(x \wedge y)$, we deduce that on $E_0$,

$$|\log w_{O,R,L}(e) - \log \mathbf{P}_O[\xi_1 = e]| \le C_0 e^{-C_1 L + C_2 R}$$

for some constants $C_0, C_1, C_2 > 0$.

The second bound is proved similarly conditional on $\mathcal{G} \setminus \mathcal{G}_x$. The main difference is the additional conditioning by either $\tau_L < \tau_{\eta(x)}$ or $\tau_{\eta(x)} = \infty$. Since the differences implies backtracking, these can be controlled using the same arguments as above and Proposition 5.4. $\square$

**Lemma 5.21.** There exist constants $C, C_1, \dots, C_3 > 0$ and $\beta \ge 1$ such that the following holds. For all $\varepsilon > 0$ there exist $C_0 = C_0(\varepsilon)$, $C_h = C_h(\varepsilon)$ such that for all $s, t \ge 0$, for all $R, L > 0$, with probability at least $1 - \varepsilon - 2(s+t)e^{-C(R \wedge L)}$ conditional on $O$ and $\eta(O)$,

$$|-\log w_{\mathcal{X}_s, R, L}(\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})) - ht| \le C_h \sqrt{t} + C_0 t e^{-C_1 L + C_2 R} + C_3 R L^{\beta+1}. \quad (5.66)$$

*Proof.* Fix $R, L$ for the rest of the proof. For notational simplicity, we drop subscripts $R, L$ from the weights. Recall $\mathcal{G}^{(R)}$ is the quasi-tree truncated at the $R$-boundary of small-range components. Note that that weights are positive only for edges in $\mathcal{G}^{(R)}$.

Given $t \ge 0$, let

$$N_t := \max\{k \ge 0 \mid T_k \le t\}.$$

We first argue there exists a constant $C_3 > 0$ such that for all $s, t \ge 0$ if $\mathcal{X}_0 \cdots \mathcal{X}_{s+t}$ is included in $\mathcal{G}^{(R)}$ then

$$|\log w_{\mathcal{X}_s}(\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})) - \log w(\xi_{L_{N_s+2}} \cdots \xi_{L_{N_s+1}} | \xi_{L_{N_s+1}})| \le C_0 R L (T_{N_s+2} - T_{N_s} + T_{N_{s+t+1}} - T_{N_{s+t}}). \quad (5.67)$$
Note first that $\xi_{L_{N_{s+1}}} \cdots \xi_{L_{N_{s+t}}}$ is necessarily part of the path $\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})$. Since weights are below one, we can easily lower bound

$$-\log w_{\mathcal{X}_s}(\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})) \geq -\log w(\xi_{L_{N_{s+2}}} \cdots \xi_{L_{N_{s+t}}}|\xi_{L_{N_{s+1}}}).$$

On the other hand the path $\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})$ contains at most $T_{N_{s+2}} - s \leq T_{N_{s+2}} - T_{N_s}$ edges until it reaches $\xi_{L_{N_{s+2}}}$ and similarly it contains at most $T_{N_{s+t+1}} - T_{N_{s+t}}$ after it leaves $\xi_{L_{N_{s+t}}}$. Then we bound the weights of these edges. If $x \in \mathcal{V}$ and $e$ is a long-range edge such that $d_{\text{SR}}(x, e^{-}) < R$, $\delta^R$ lower bounds the probability the chain goes from $x$ to $e$ and leaves by this edge. As small-range components have size at least 2 (H3), $\delta^{RL}$ lower bounds the probability that the chain goes from $x$ to $e^+$ and reaches long-range distance $L$ before coming back to $e^-$. Consequently, for some constant $C_3 > 0$, we can always bound $-\log w_x(e) \leq C_3 RL$ for all $x, e$ in $\mathcal{G}^{(R)}$, for any realization of the quasi-tree. We deduce that

$$-\log w_{\mathcal{X}_s}(\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})) + \log w_{\mathcal{X}_s}(\xi_{L_{N_{s+2}}} \cdots \xi_{L_{N_{s+t}}}) \leq C_3 RL (T_{N_{s+2}} - T_{N_s} + T_{N_{s+t+1}} - T_{N_{s+t}}).$$

Next fix $\varepsilon \in (0, 1)$ and let $s, t \geq 0$. Let $\mathcal{A}$ be the set of quasi-trees for which every long-range edge $e$ such that $d_{\text{SR}}(O, e^{-}) < R$ satisfies the bounds of Lemma 5.20 for some $C_0, C_1, C_2 > 0$. Consider the following events:

$$E_0 := \{\mathcal{G} \in \mathcal{A}\} \cap \bigcap_{s' \leq s+t} \{\mathcal{G}_{\mathcal{X}_s'}, \in \mathcal{A}\},$$

$$E_1 := \{\tau_{\text{SR}}^{(R)} > s + t\}$$

$$E_2 := \{|L_{N_{s+t}} - L_{N_s} - dt| \leq C_{\text{LR}}\sqrt{t}\}$$

with $C_{\text{LR}} = C_{\text{LR}}(\varepsilon) > 0$ to determine, and write $E := E_0 \cap E_1 \cap E_2$. By Lemmas 5.20 and 5.16, $C_0, C_1, C_2$ can be chosen so that $\mathbb{P}_O[E_0^c | O, \eta(O)] \leq (s+t)e^{-C_4(R^\wedge L)}$ for some $C_4 > 0$. By Lemma 5.18 there exists $C_5 > 0$ such that $\mathbb{P}_O[E_1^c | O, \eta(O)] \leq (s+t)e^{-C_5 R}$. Finally from the proof of Proposition 5.13, $C_{\text{LR}}(\varepsilon)$ can be taken so that $\mathbb{P}_O[E_2^c | O, \eta(O)] \leq \varepsilon$. Hence $\mathbb{P}_O[E^c | O, \eta(O)] \leq \varepsilon + (s+t)e^{-C(R^\wedge L)}$, for some constant $C > 0$.

Then let $l_+ := [dt + C_{\text{LR}}\sqrt{t}]$. On the event $E$, using (5.65)

$$\left| \log w(\xi_{L_{N_{s+2}}} \cdots \xi_{L_{N_{s+t}}}| \xi_{L_{N_{s+1}}} - \log \mathbf{P} \left[ \xi_{L_{N_{s+2}}} \cdots \xi_{L_{N_{s+t}}} \in \xi' \mid \mathcal{X}, \xi'_{L_{N_{s+1}}} = \xi_{L_{N_{s+1}}} \right] \right| \leq l_+ e^{-C_1 L + C_2 R}.$$

Letting $h'$ be the constant of Lemma 5.19, we claim then that for $h = h'/\mathbb{E}_{\mathbb{Q}_\mu[T_1]}$ and some constant $C_h = C_h(a, \varepsilon)$

$$\left| -\log \mathbf{P} \left[ \xi_{L_{N_{s+2}}} \cdots \xi_{L_{N_{s+t}}} \in \xi' \mid \mathcal{X}, \xi'_{L_{N_{s+1}}} = \xi_{L_{N_{s+1}}} \right] - ht \right| \leq C_h \sqrt{t}$$
with probability at least $\varepsilon$. This can be done using the same arguments as in the proof of Proposition 5.13, combining the fluctuations for $N_{s+t}$ (5.60) established in the said proof with Lemma 5.19.

Finally, we are left with bounding the right hand side of (5.67). Using again the fluctuations for $N_{s+t}$ (5.60) with the stretched exponential tail of regeneration times, there exists $\beta \ge 1$ and $C_6 > 0$ such that

$$ \mathbb{P}[T_{N_{s+1}} - T_{N_s} + T_{N_{s+t+1}} - T_{N_{s+t}} > L^\beta] \le \varepsilon + \sqrt{s+t}e^{-C_6L}. $$

All in all, up to changing the value of $C$ we have thus proved that with probability at least $1 - 2\varepsilon - (s+t)e^{-C(R^\wedge L)}$,

$$ |\log w_{\mathcal{X}_s}(\xi(\mathcal{X}_s \cdots \mathcal{X}_{s+t})) - ht| \le C_h \sqrt{t} + C_0 l_+ e^{-C_1 L + C_2 R} + C_3 R L^{\beta+1}. $$

Since $l_+ = O_\varepsilon(t)$ this proves the result. $\square$

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

## 5.8 First steps towards nice paths

We now come back to the finite setting. The goal of this section is to prove Lemmas 5.2, 5.3 and Proposition 5.1, which will be used in the next section to justify the chain is likely to follow a nice trajectory.

### 5.8.1 The case of typical starting states

We start with the case of typical starting states, for which there is little left to prove.

*Proof of (i) in Lemma 5.3.* This is essentially a matter of checking definitions. For fixed $x \in V$, the choice of $s, t = O(\log n)^a, a \ge 1$, Lemma 5.1 ensures the finite chain $X$ and the chain $\mathcal{X}$ on the quasi-tree can be coupled until time $s+t$ with annealed probability $1-o(n^{-\varepsilon})$ for some $\varepsilon > 0$. Provided the coupling succeeds, the property of backtracking or hitting the boundary of a small-range ball coincides for both chains, while the regeneration times of $\mathcal{X}$ obviously give regeneration edges for the finite chain. Thus from Lemma 5.1 and Lemma 5.18 we deduce

$$ \mathbb{P}_x[(X_s \cdots X_{s+t} \cdots \in \Gamma(R, L, M))] \le (s+t)e^{-C(R^\wedge L^\wedge M^\wedge)} + o(n^{-\varepsilon}) \quad (5.68) $$

Since $s, t = (\log n)^a$, for any $b > 0$ the choice of $R, L = O(\log \log n)$ with large enough implicit constants depending on $a, b$ and $M = (\log \log n)^{2/\alpha}$ makes the right hand side $o((\log n)^{-b})$. The first moment argument (5.4) implies (i) in Lemma 5.3. $\square$

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

We can repeat the same kind of arguments for point (i) in Proposition 5.1 however we obtain for the time being a slightly weaker statement that the one expected. Because
of the dependance in $\epsilon$ in the annealed probability of (5.59) and (5.66), applying the first moment arguments will not establish the concentration property with high probability but only $1-\epsilon-o(1)$. To obtain a high probability result we need to apply a higher order Markov's inequality, which is also the key argument to obtain the uniform statements.

### 5.8.2 Bootstrapping annealed bounds with parallel chains

Arguments used so far above establish errors on annealed error in $o(1)$, nay in $\epsilon+o(1)$. Following ideas from [28, 29], one strategy to improve these error bounds consists in using higher order moments in Markov's inequality, which leads to an argument of "parallelizing chains" on the same environment. Namely for all $\epsilon > 0$ and $k \ge 1$, for any trajectorial event A

$$ \forall x \in V : \mathbb{P}[\mathbf{P}_x[A] > \epsilon] \le \frac{\mathbb{P}_x[A]^k}{\epsilon^k} = \epsilon^{-k} \mathbb{P}_x\left[\bigcap_{i=1}^k \{X^{(i)} \in A\}\right] \quad (5.69) $$

and

$$ \mathbb{P}\left[\max_{x \in V} \mathbf{P}_x[A] > \epsilon\right] \le \frac{1}{\epsilon^k} \mathbb{E}\left[\sum_{x \in V} \mathbf{P}_x[A]^k\right] \\ \le \frac{n}{\epsilon^k} \max_{x \in V} \mathbb{P}_x\left[\bigcap_{i=1}^k \{X^{(i)} \in A\}\right], \quad (5.70) $$

where $X^{(1)}, \dots, X^{(k)}$ are $k$ versions of the chain $X$ generated independently conditional on the same environment. These $k$ trajectories can be generated sequentially with the environment, sampling the environment only when exploring parts of the environment not already visited by the previous chains. The idea will then be to argue that the chains are unlikely to follow each other, so they end up exploring disjoint parts of the environments. If the event $A$ depends only on what happens after the trajectories separate from each other (hence the consideration of shifted trajectories), we can then expect the annealed probability to decouple and become $\mathbb{P}[A]^k$. If the event $A$ has probability below $f(\epsilon)$ for some function $f$, this can be sufficient to beat the $\epsilon^{-k}$ or $\epsilon^{-kn}$ factor.

As an example of application, we can start proving point (i) in Proposition 5.1, which also illustrates some of the arguments used in the sequel.

*Proof of (i) in Proposition 5.1.* Let $\epsilon > 0$, $t = O(\log n)$ and $x \in V$. For $C_{LR} = C_{LR}(\epsilon)$ and $C_h = C_h(\epsilon) > 0$ to determine, consider the set of paths

$$ \Gamma_{\text{Ent}} := \left\{ \mathfrak{p} \left| \begin{array}{l} \|\xi(\mathfrak{p})\| - d|\mathfrak{p}| \le C_{\text{LR}}\sqrt{|\mathfrak{p}|} \\ |-\log w_{\text{p}_0, R, L}(\xi(\mathfrak{p})) - h|\mathfrak{p}| \le C_h\sqrt{|\mathfrak{p}|} \end{array} \right. \right\} \quad (5.71) $$
which can be paths either in $G^*$ or $G$. The goal is thus to show $\mathbb{P}_x[(X_0)\cdots X_t \notin \Gamma_{\text{Ent}}] = o(1)$. Consider $k$ versions $X^{(1)}, \dots, X^{(k)}$ of the chain $X$ generated independently conditional on the same environment, with $k \gg 1$, $k = O(\log \log n)$. Then using the same coupling as in Section 5.2.7 these can be coupled with $k$ versions $\mathcal{X}^{(1)}, \dots, \mathcal{X}^{(k)}$ of the chain $\mathcal{X}$. For $j \in [k]$ let $\mathcal{G}(j,t)$ denote the union of the first $j$ trajectories up to time $t$, along with their long-range neighbourhoods up to depth $L$. Compared to the case of a single chain, the number of visited vertices gets multiplied by $k$ at most, so the proof of Lemma 5.1 shows the chains $X^{(1)}, \dots, X^{(k)}$ can be coupled with high probability, along with their long-range neighbourhood up to length $L = O(\log \log n)$, up to time $t = O(\log n)$, to coincide with $\mathcal{G}(k, s+t)$. Now the definitions of the long-range distance and of weights ((5.16) and (5.64)), which are measurable with respect to this neighbourhood, were exactly made to coincide in the finite and quasi-tree settings. Thus if the coupling succeeds $(X_0\cdots X_t) \in \Gamma_{\text{Ent}}$ if and only in $\mathcal{X}_0\cdots \mathcal{X}_t \in \Gamma_{\text{Ent}}$. Letting for $j \in [k]$:

$$B_j := \bigcap_{i=1}^{j} \{ \mathcal{X}_0^{(i)} \cdots \mathcal{X}_t^{(i)} \notin \Gamma_{\text{Ent}} \}$$

(5.69) and the coupling imply

$$\mathbb{P}_x[X_0 \cdots X_t \notin \Gamma_{\text{Ent}}] \le \varepsilon^{-k} \mathbb{P}[B_k \mid \iota(O) = x] + o(1),$$

so it suffices to show $\mathbb{P}_O[B_k \mid \iota(O) = x] = o(\varepsilon^k)$. We consider in fact a slightly modified event. Let $l := (\log \log n)^3$ and consider the set of quasi-trees $\mathcal{A}_l = \mathcal{A}_l(\alpha, q_0)$ for which every length $l$ path from the root contains a proportion at least $\alpha$ of vertices for which the probability to escape to infinity outside $\mathfrak{p}$ is lower bounded by $q_0$. Recalling Proposition 5.5 and Remark 5.10, Lemma 5.16 implies the existence of constants $q_0, \alpha > 0$ and $C > 0$ such that all vertices in $\mathcal{G}(j,t)$ have their subquasi-tree in $\mathcal{A}_l$ with probability at least $1 - t e^{-Cl}$. Since $t = O(\log n)$ and $l = (\log \log n)^3$ this probability is $1-o(1)$. Thus we can suppose that the event $B_j$ also contains the event that all vertices of $\mathcal{G}(j,t)$ have their subquasi-tree in $\mathcal{A}_l$. Secondly, consider the $l$-th regeneration time $T_l^{(i)}$ of the $i$-th chain. By the stretched exponential tails of regeneration times 5.14 and Chernoff's bound, there exist constants $\alpha \in (0,1]$ and $C > 0$ such that for all $i \le k$

$$\mathbb{P}_O[T_l^{(i)} > t_0 \mid \iota(O) = x] \le e^{-t_0^\alpha + Cl}$$

Thus considering $t_0 := (\log \log n)^\beta$, for $\beta > 3/\alpha$ large enough makes the right hand side $o(k^{-1})$. Consequently by union bound we obtain that $\mathbb{P}_O[\exists i \le k : T_l^{(i)} > t_0] = o(1)$, so we can also incorporate to the events $B_j$ the event that $T_l^{(i)} \le t_0$ for $i \le j$.

Next we claim that $\mathbb{P}_O[B_1 \mid \iota(O) = x] \le \varepsilon/2 + o(1)$ and $\mathbb{P}_O[B_j \mid \iota(O) = x, B_{j-1}] \le \varepsilon/2 + o(1)$ for all $j \in [2, k]$. Noting that

$$\mathbb{P}_O[B_k \mid \iota(O) = x] = \mathbb{P}_O[B_1 \mid \iota(O) = x] \prod_{j=2}^{k} \mathbb{P}_O[B_j \mid \iota(O) = x, B_{j-1}],$$
the claims imply that $\mathbb{P}[B_k | \iota(O) = x] = (\varepsilon/2 + o(1))^k = o(\varepsilon^k)$ as desired.

Let us prove the claims. The first claim is the consequence of Proposition 5.13 and Lemma 5.21, provided the constants $C_{LR}, C_h$ are chosen adequately. To prove the second claim, let $j \ge 2$ and suppose $B_{j-1}$ holds. We argue that $\mathcal{X}^{(j)}$ has quenched probability at least $1 - o(1)$ to exit $\mathcal{G}(j-1, t)$ for the last time by time $t_0$. Consider then the loop-erased chain $(\xi_m^{(j)})_m$ obtained from $\mathcal{X}^{(j)}$. Thanks to the first event we added to $B_{j-1}$, for any long-range path $\zeta$ of length $l$ contained in $\mathcal{G}(j-1, t)$,

$$ \mathbf{P}_O[\xi_l^{(j)} = \zeta_l \mid B_{j-1}] \le e^{-Cl} $$

for some constant $C > 0$. Since $\mathcal{G}(j-1, t)$ is made of the long-range neighbourhood of the first $j-1$ trajectories, it contains at most $kt\Delta^{R(L+1)}$ long-range paths of length $l$. Thus by union bound

$$ \mathbf{P}_O[\xi_l^{(j)} \in \mathcal{G}(j-1, s+t) \mid B_{j-1}] \le kt\Delta^{R(L+1)}e^{-Cl} = e^{-C(\log \log n)^3 + O(\log \log n)^2} = o(1). $$

On the other hand, the second event added to $B_j$ implies that $T_l^{(j)} \le t_0$ so the chain must in particular have made the first $l$ steps of its loop-erased trace before time $t_0$. Combined with what precedes we deduce that conditional on $B_{j-1}$, the chain $\mathcal{X}^{(j)}$ leaves the graph $\mathcal{G}(j-1, t)$ before time $t_0$ with probability $1-o(1)$.

Let $L^{(j)}$ denote now this last exit time. Conditional on $L^{(j)}$ and $\mathcal{X}_{L^{(j)}} = u$, the quasi-tree that contains the subsequent trajectory needs then to be generated according to the measure $\mathbb{Q}_u$ (5.52). Using Remark 5.15 upper bounds under this law only differ by a constant factor from upper bounds with the usual law. We can thus apply Proposition 5.13 and Lemma 5.21 conditional on $L_j$ to obtain that

$$ \mathbb{P}_O[(X_{L_j}^{(j)}...X_{L_{j+t}}^{(j)}) \notin \Gamma_{\text{Ent}} \mid B_{j-1}, \iota(O) = x] \le \varepsilon/2 + o(1). $$

Now by what precedes $d_{LR}(\mathcal{X}_0^{(j)}, \mathcal{X}_{L_j}^{(j)}) \le l$ with probability $1-o(1)$ conditional on $B_{j-1}$, hence

$$ d_{LR}(\mathcal{X}_0^{(j)}, \mathcal{X}_t^{(j)}) \in [dt - C_{LR}\sqrt{t}, dt - C_{LR}\sqrt{t} + l] $$

and

$$ -\log w_{\chi_{0,R,L}}(\xi(\mathcal{X}_0^{(j)}...\mathcal{X}_t^{(j)})) \in [ht - C_h\sqrt{t}, ht + C_h\sqrt{t} + lw_{\max}], $$

where $w_{\max}$ denotes an upper bound on all the weights contained in $\mathcal{G}(j-1, t)$. For any realization of the quasi-tree we can bound $w_{\max} \le O(RL)$ as in the proof of Lemma 5.21. All in all, since $lw_{\max} = o(\sqrt{t})$, this ensures $(\mathcal{X}_0^{(j)}, \mathcal{X}_t^{(j)}) \in \Gamma_{\text{Ent}}$ with probability $1 - \varepsilon/2 - o(1)$, proving the claim. $\square$
### 5.8.3 From $o(1)$ to $o(1/n)$ bounds

#### Quasi-tree with a cycle

The rest of this section will now be devoted to the proof of the uniform, worst-case statements. The main ideas are the same as those used above. From (5.70), we only need to push them yet a little further to make error bounds on annealed probabilities $o(1/n)$. From the proof of (i) in Proposition 5.1 two arguments require a modification: the coupling with the a quasi-tree and the use of escape probabilities.

Let us focus on the first point. It seems quite obvious that the coupling with quasi-trees cannot be improved beyond to a $o(1/n)$ error as some vertices do not have a quasi-tree like neighbourhood. However from the proof of Lemma 5.1 this error can be achieved allowing just one cycle. We are thus led to consider a modified quasi-tree model which contains at most one long-range cycle.

Let $(u_i)_{i=0}^l, (v_i)_{i=0}^l, l \ge 0$ be two sequences of vertices in $V$ such that $u_{i+1} \in B_{SR}^+(v_i, \infty)$ for all $i \in [0, l-1]$ and $B_{SR}^+(v_l, R) \cap B_{SR}^-(u_0, R) \neq \emptyset$. For every $i$ and vertex $z \in B_{SR}^+(u_i, \infty) \setminus \{u_i, v_i\}$, add an edge $(z, \eta(z))$ and grow a one-sided quasi-tree rooted at $\eta(z)$. We call the oriented graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ obtained a quasi-tree with a cycle $((u_i, v_i))_{i=0}^l$. As a usual quasi-tree, it is given by maps $\iota, \eta$ such that $\iota$ identifies vertices of $\mathcal{V}$ with vertices in $V$, while $\eta: \mathcal{V} \to \mathcal{V}$ is an involution. Here $\eta$ is obtained by the corresponding maps in the quasi-trees outside the cycle whereas for the cycle we set $\eta(u_i) := v_{i+1}$ for all $i = 0, \dots, l-1$. A root $O$ can be chosen, which does not to be on the cycle. The definition of the Markov chain $\mathcal{X}$ (5.10) extends directly to this setting.

The coupling of Section 5.2.7 gives a natural way to couple $\mathcal{X}$ on a random realization of $\mathcal{G}$ with the Markov chain $X$: the rejection scheme is used until the first occurrence of a cycle, after which cycles are ignored in the construction of $\mathcal{G}$. The stochastic comparison in the proof of Lemma 5.1 still holds, but using now that

$$ \mathbb{P}[Z \ge 2] \le \frac{m^4 \Delta^{2R}}{n^2} \qquad (5.72) $$

if $Z$ is a binomial $\text{Bin}(m, m\Delta^R/n)$, we deduce that for $t = n^{o(1)}$, the chains $X$ and $\mathcal{X}$ can be coupled so that the chains coincide and $B_{LR}(X_s, L)$ and $B_{LR}(\mathcal{X}_s, L)$ are isomorphic for all $s \le t$ with probability $1-o(1/n)$.

More generally, let $k \ge 1$ and $X^{(1)}, \dots, X^{(k)}$, resp. $\mathcal{X}^{(1)}, \dots, \mathcal{X}^{(k)}$, $k$ versions of the chain $X$, resp. $\mathcal{X}$ generated independently conditional on the same environment. Letting $G^*(k, t), \mathcal{G}(k, t)$ be the environments explored by these trajectories up to time $t$ along with their $L$-long-range neighbourhoods, the same arguments as above implies
that

$$ \mathbb{P} \left[ \begin{array}{l} G^*(k,t) \text{ and } \mathcal{G}(k,t) \text{ are isomorphic} \\ \quad \forall i \in [1,k], \forall s \le t : X_s^{(i)} = \iota(\mathcal{X}_s^{(i)}) \end{array} \right] = 1 - o((kt)^4/n^{7/4}) = o(\varepsilon^k/n) \quad (5.73) $$

if for instance $k = [\log n/2 \log \varepsilon^{-1}]$.

### An essentially uniform bound on escape probabilities

The second argument that needs to be adapted is the use of escape probabilities, which can be expected to of constant order only for typical states. Consider $\mathcal{G}$ to be a random realization of a quasi-tree with a cycle as described above and $\mathcal{X}$ the associated Markov chain. Conditional on the cycle, the quasi-trees that are added to it are generated according to the model studied in Sections 5.5 - 5.7, therefore the asymptotic analysis of the chain $\mathcal{X}$ directly extends to that case, conditional on the cycle. The chain ultimately leaves the cycle, after which it stays in a genuine quasi-tree. Given a vertex $x$ which is not on the cycle, let $q_{\text{Esc}}(x)$ denote the probability to escape in the corresponding quasi-tree. If $x$ is on the cycle, there is no quasi-tree at $x$, so let $q_{\text{Esc}}(x)$ denote the probability of escaping through one of the vertices that are in the same component as $x$. Using that components of $V_1$ have size at least 3 (H3), these escape probabilities can be bounded exactly as in Section 5.5, up to a change of constants, conditional on the cycle. Thus from Proposition 5.4, there exists $\beta \ge 1$ such that for all $u \in \mathcal{V}$ not on the cycle,

$$ \mathbb{P} \left[ q_{\text{Esc}}(u) < \frac{1}{(\log n)^\beta} \mid \mathcal{G} \setminus \mathcal{G}_u \right] = O(1/n^2). \quad (5.74) $$

Combined with Lemma 5.16, we see that on a time scale $t = O((\log n)^a)$, $a \ge 1$, the probability that the chain $\mathcal{X}$ meets a vertex which does not satisfy the lower bound on escape probability above is still $o(1/n)$. This makes the chain sufficiently unlikely to meet such vertices that the chain $X$ cannot reach such quasi-tree-like neighbourhoods either, thanks to the coupling described above. Informally, this allows us to proceed as if escape probabilities were everywhere lower bounded by $1/(\log n)^\beta$ and reason conditional on the environment. In the reversible model, Proposition 5.3 shows we can directly work with a uniformly lower bounded escape probability.

### 5.8.4 Nice paths from arbitrary states

A first application of these uniform lower bounds is the following.

*Proof of Lemma 5.2.* We prove the first point. Let $L = C_L \log \log n$ for a fixed constant $C_L > 0$, $t \ll n^{1/16}$ and $x \in V$. By Remark 5.4 it suffices to consider the case of
$s = C(\log n)^a$ for some $a > 0$ to determine. Using the coupling described above (with only one chain here, ie $k = 1$) we can couple the trajectory of $X$ and its whole $L$ long-range neighbourhood with that of $\mathcal{X}$. By (5.73) the coupling succeeds up to time $s+t$ with probability $1-o(1/n)$, hence for $u \in V$

$$ \mathbb{P}_u [ \exists s' \in [s, s+t] : B_{LR}(X_{s'}, L) \text{ is not quasi-tree-like} ] \\ = \mathbb{P}_O [ \exists s' \in [s, s+t] : \mathcal{X}_{s'} \text{ is at distance less than } L \text{ from the cycle } | \iota(O) = u ] + o(1/n). $$

Now let $\beta \ge 1$ be as in (5.74) and consider the set

$$ \mathrm{Esc} := \{ x \in \mathcal{G} \mid q_{\mathrm{Esc}}(x) \ge (\log n)^{-\beta} \}. $$

Write $\tau_{Esc^c}$ for the hitting time of the complement set of Esc. The number of vertices in the $L$ long-range neighbourhood of the trajectory being bounded by $O(s+t)\Delta^{R(L+1)} = O(n^{1/16})$, union bound and (5.74) imply

$$ \mathbb{P}_O [ \tau_{Esc^c} \le s + t \mid \iota(O) = u ] = o(1/n). $$

We are being a bit sketchy here, but the argument can be formalized using the Ulam labelling. On the other hand, when the chain is at a vertex of Esc its long-range distance to the cycle has a quenched probability at least $(\log n)^{-\beta}$ to increase by 1 indefinitely. Thus if we consider the sequence of times $(S_k)_{k \ge 1}$ at which this happens, for all $x \in \mathcal{V}, s \ge 0$,

$$ \mathbf{P}_x [ \tau_{Esc^c} \ge s + t, S_1 > s ] \le e^{-s/(\log n)^\beta}. $$

Consequently by union bound and Strong Markov's property

$$ \mathbf{P}_x [ \exists s' \in [s, s+t] : \mathcal{X}_{s'} \text{ is at distance less than } L \text{ from the cycle, } \tau_{Esc^c} > s+t ] \\ \le \mathbf{P}_x [ S_L > s, \tau_{Esc^c > s+t} ] \le L e^{-s/L(\log n)^\beta}. $$

Since $s = (\log n)^a$, choosing $a > \beta+1$ makes these two bounds $o(1/n)$. The first moment argument (5.70) concludes the proof of the first point in the general case.

For the reversible model, escape probabilities are $\Theta(1)$ conditional on the environment by Proposition 5.3. Hence $S_L$ is always stochastically dominated by the sum of $L$ geometric random variables with constant parameter. From Chernoff's bound we deduce that for some constant $C > 0$, $S_L > CL$ with exponentially small probability, thus we can take $s = \Theta(L) = \Theta(\log \log n)$.

Finally point (ii) can be proved with similar arguments.

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

It remains to prove (ii) in Lemma 5.3 and Proposition 5.1. The argument is similar and uses the same ideas as above.
Proof of (ii) in Lemma 5.3 and Proposition 5.1. Consider the concentration of the drift and entropy. Let $x \in V$, $\varepsilon > 0$ and $k := [\log n/2 \log \varepsilon^{-1}]$. As for point (i) we combine the higher Markov inequalities (5.70) and the coupling with $k$ chains on a quasi-tree with a cycle. As a cycle is allowed the error due to the coupling is $o(1/n)$ by (5.73) so we need only focus on the infinite setting: letting

$$B_j := \bigcap_{i=1}^{j} \{ \mathcal{X}_s^{(i)} \cdots \mathcal{X}_{s+t}^{(i)} \notin \Gamma_{\text{Ent}} \}.$$

for $j \in [k]$, with $\Gamma_{\text{Ent}}$ as in (5.71) it suffices to prove $\mathbb{P}_O[B_k | \iota(O) = x] = o(\varepsilon^k/n)$. Then we claim that $\mathbb{P}_O[B_1 | \iota(O) = x] \le \varepsilon^3/2 + o(1)$ and $\mathbb{P}_O[B_j | \iota(O) = u, B_{j-1}] \le \varepsilon^3/2 + o(1)$ for all $j \in [2, k]$. With our choice of $k$ this will imply $\mathbb{P}_O[B_k | \iota(O) = x] = (\varepsilon^3/2 + o(1))^k = o(\varepsilon^k/n)$ as needed.

As we mentioned already, results proved for genuine quasi-trees extend to the case where an additional cycle is present. In particular, the first regeneration time and level, defined to occur outside the cycle, have stretched exponential or exponential tail respectively, conditional on the cycle, while the remaining regenerations occurs on genuine quasi-trees. This is sufficient to establish that Proposition 5.13 and Lemma 5.21 still hold in this case, implying that $\mathbb{P}[B_1 | \iota(O) = u] \le \varepsilon^3/2$ for a good choice of $C_h, C_{LR}(\varepsilon)$.

For the second claim, we argue as for (i) by showing the chains are unlikely follow each other. Let $\beta \ge 1$ be as in (5.74), consider the set

$$\text{Esc} := \{x \in \mathcal{G} \mid q_{\text{Esc}}(x) \ge (\log n)^{-\beta}\}.$$

and let $\tau_{\text{Esc}^c}$ be the first exit time by any of the chains. As we argued above in the proof of Lemma 5.2, $\mathbb{P}_O[\tau_{\text{Esc}^c} \le s + t | \iota(O) = u] = o(1/n)$. On the other hand, while on this set the chains have a quenched probability at least $(\log n)^\beta$ to have their long-range distance increased by 1 permanently, hence for any $j \in [k]$, letting $(S_k^{(j)})_k$ be the sequence of times at which this occurs for the $j$-th chain,

$$\mathbf{P}_O [S_l^{(j)} > s, \tau_{\text{Esc}^c} > s + t] \le l e^{-C_1 s / l (\log n)^\beta} \quad (5.75)$$

for some constant $C_1 > 0$. Taking $a > 1 + 2\beta$ in $s = (\log n)^s$ and $l = (\log n)^\beta (\log \log n)^3$ the right hand side is $o(1)$.

Consider now the loop-erased chain $(\xi_m^{(j)})_m$ obtained from $\mathcal{X}^{(j)}$. If all vertices visited by the chain are in Esc, and using that components of $V_1$ have size at least 3, the probability to follow a given path is exponentially small in the length. Since $\mathcal{G}(j-1, s+t)$ contains at most one long-range cycle this subgraph contains at most $2k(s+t)\Delta^{R(L+1)}$ long-range paths, so by union bound

$$\mathbf{P}_O [\xi_l^{(j)} \in \mathcal{G}(j-1, s+t), \tau_{\text{Esc}^c} > s+t] \le 2k(s+t)\Delta^{R(L+1)} e^{-C_2 l / (\log n)^\beta}.$$
for some constant $C_2 > 0$. For $l = (\log n)^\beta (\log \log n)^3$ this is $o(1)$.

Combining the two previous observations, we deduce that conditional on $B_{j-1}$, the last exit of $\mathcal{G}(j-1, s+t)$ by the trajectory $(\mathcal{X}_{t'}^{(j)})_{t' \le s+t}$ occurs before $s$, leaving at least $t$ subsequent steps. Letting $L^{(j)}$ denote this last exit time, we can reason conditional on $L_j$ and use Proposition 5.13 and Lemma 5.21 about shifted trajectories to deduce the claim.

The proof for the reversible case is similar, with the difference that escape probabilities are $\Theta(1)$ so we can deduce it $O(\log \log n)$ steps are enough for the $k$ trajectories to split apart. Finally, the proof of Lemma 5.3 uses the same arguments, considering the set of paths $\Gamma(R, L, M)$ instead of $\Gamma_{\text{Ent}}$. $\square$

## 5.9 Approximation by nice paths: proof of Proposition 5.2

We now move to the second part of the proof of Theorem 5.1: the approximation of the Markov kernel by restricting to the consideration of nice paths only. For earlier works that used this argument, see for instance [19, 28].

### 5.9.1 Forward neighbourhood

Nice paths between $x$ and $y$ will have their first steps and last steps contained respectively in some quasi-tree-like neighbourhoods of $x$ and $y$. We define here the forward neighbourhood of $x$.

Let $x \in V$, $l \ge 1$ an integer and $w_{\min} \ge 0$. From Lemma 5.1, long-range balls of radius $O(\log \log n)$ are likely to be tree-like but this is not true as the radius grow towards $\log n$. The forward graph $K(x, l, w_{\min})$ is thus designed essentially as a "spanning quasi-tree" of the ball $B_{LR}(x, l)$, obtained by exploring this ball algorithmically, pretty much as explained in Section 5.2.7, but giving priority to paths with large weights and truncating whenever cycles are encountered. This process will thus build iteratively a sequence $(K_m)_{m=0}^\tau$ of subsets of $B_{LR}(x, l)$, until it stops at a random time $\tau$ to yield $K(x, l, w_{\min}) := K_\tau$. Unless the procedure is initiated at a vertex $x$ whose ball $B_{LR}(x, L)$ is not quasi-tree-like, $K_m$ remains at all time quasi-tree-like. In this case for every long-range edge $e \in E_m$ there exists a unique long-range path $\xi(e)$ from $x$ to $e$ contained in $K_m$. If $e$ has its $L$ long range neighbourhood entirely contained in $K_m$, define the cumulative weight as $\hat{w}(e) := w_x(\xi(e))$, which can be computed from $K_m$. Because weights require the knowledge of $(L-1)$-neighbourhoods, the exploration queue will consist in subsets $E_m$ of long-range edges for which the whole long-range $(L-1)$-neighbourhood is contained in $K_m$. Finally, a constraint of minimal weights is added during the procedure, in order to keep the number of vertices explored as $o(n)$.
**Exploration of the forward neighbourhood** The procedure is initiated with $K_0 := B_{LR}(x, L)$. If $K_0$ contains a long-range cycle, $E_0 := \emptyset$ and the procedure stops. Otherwise let $E_0$ be the set of long-range edges at distance 0 from $x$. Then for all $m \ge 0$ the $(m+1)$-th step goes as follows:

1. Among all long-range edges $e$ in $E_m$ at long-range depth at most $l$ from $x$ in $K_m$ and such that $\hat{w}(e) \ge w_{\min}$, pick the edge $e_{m+1}$ with maximal cumulative weight, using an arbitrary ordering of the vertices to break ties. If there is no such edge, the procedure stops.

2. Explore the depth-$L$ neighbourhood of $e_{m+1}$: for each descendant $z \in \partial K_m$ at long-range distance $L-1$ from $e_{m+1}$, sample $\eta(z)$. This exploration phase stops if a revealed edge violates the quasi-tree structure: this occurs if for some $z$ the small-range ball $B_{SR}(\eta(z), R)$ has a non-empty intersection with $K_m$ or one of the previously revealed balls.

3. If the previous exploration phase stopped because of intersecting small-range balls, then $E_{m+1} := E_m \setminus \{e_{m+1}\}$ and $K_{m+1} := K_m$. If it stopped because of an intersection with $K_m$, let $Z_m$ be this intersection. Then $E_{m+1}$ is obtained by deleting from $E_m$ every long-range edge which has either a descendant or an ancestor in $Z_m$, as well as the edge $e_{m+1}$, and set $K_{m+1} := K_m$. Finally, if the exploration ended without a violation of the quasi-tree structure, add the subsequent long-range edges of $e_{m+1}$ to $E_{m+1}$, whereas the newly revealed vertices are added to $K_{m+1}$.

When the procedure ends, the set $E_\tau$ consists by construction of edges at long-range distance $l-L$ from $x$, which contain no long-range cycles in their $(L-1)$-neighbourhood and whose weights are measurable with respect to $K(x, l, w_{\min})$.

**Lemma 5.22.** Let $\kappa_m$ denote the number of long-range edges revealed during the first $m$ steps $m$ and $\kappa(x, l, w_{\min}) := \kappa_\tau$ the total number of long-range edges revealed during the construction of $K(x, l, w_{\min})$. Suppose $B_{LR}(x, L)$ is quasi-tree-like so that $\tau \ge 1$. There exists a constant $C > 0$ such that for all $m \in [1, \tau]$

$$ \hat{w}(e_m) \le C \frac{l \Delta^{RL}}{\kappa_m}. \qquad (5.76) $$

In particular

$$ \kappa(x, l, w_{\min}) \le C \frac{l \Delta^{RL}}{w_{\min}}. \qquad (5.77) $$

*Proof.* The set $E_{\le m} := \bigcup_{k \le m} E_k$ is the set of all long-range edges contained in $K_m$ which have their $L$ long-range neighbourhood contained in $K_m$. Furthermore, at time $m$ the
procedure did not explore beyond long-range distance (L - 1) from these edges. Since long-range balls of radius L contain $O(\Delta^{R(L+1)})$ vertices, one has $\kappa_m \le C|E_{\le m}|\Delta^{RL}$ for some constant $C > 0$.

The quasi-tree structure implies the set E can be arranged as a rooted tree, where long-range edges are linked to a same vertex if they are at long-range distance 0 from each other. The set $E_m$ is the set of edges furthest from the root, that is edges that lead to leaves. For every $e \in E_m$, there is a unique shortest path from the root to e, and conversely every edge is on such a path. These paths correspond to long-range paths in $K_m$ from x to e, which have long-range length at most l, so we can deduce $|E_{\le m}| \le l|E_m|$.

On the other hand, the sum of weights over all shortest long-range paths from the root to $E_m$ is bounded by 1. Furthermore, the choice of a maximal weight in step 1 ensures that the weights consecutively chosen are non-increasing. Therefore every shortest path from the root to $E_m$ has weight at least $\hat{w}(e_m)$, so we deduce $|E_m|\hat{w}(e_m) \le 1$. All in all this shows $\kappa_m \le Cl\Delta^{RL}/\hat{w}(e_m)$. Finally, $\hat{w}(e_m) \ge w_{\min}$ for all m, in particular when the procedure stops at $m = \tau$, hence the bound on $\kappa_\tau = \kappa(x, l, w_{\min})$. $\square$

The following Lemma bounds the probability to exit $K(x, l, w_{\min})$ at an edge where the quasi-tree structure was violated.

**Lemma 5.23.** If $m > \tau$, let cycle($e_{m+1}$) be the event that the exploration of the $(L+1)$ neighbourhood of the long-range edge $e_{m+1} \in E_m$ considered at the $(m+1)$-th step revealed a cycle. Let $\varepsilon \in (0,1)$ and consider the following process. If $B_{LR}(x, L)$ is not quasi-tree-like, let $W_m := 1$ for all $m \ge 0$, otherwise set $W_0 := 0$ and for all $m \ge 0$ define

$$W_{m+1} := W_m + (\hat{w}(e_{m+1}) \wedge \varepsilon/2) \mathbb{1}_{m<\tau} \mathbb{1}_{\text{cycle}(e_{m+1})}.$$

This is the total cumulative weight of edges that violated the quasi-tree structure at step $m+1$ and that are below $\varepsilon/2$. Suppose $l = O(\log n)$, $R, L = O(\log \log n)$ and that $w_{\min} \ge e^{(\log \log n)^3}/n$. Then for all $s = s(n)$, with high probability, for all $x \in V$,

$$W_{\tau} \le W_s + \varepsilon. \qquad (5.78)$$

*Proof.* Fix $\varepsilon \in (0,1)$, $x \in V$ and $s = s(n)$. Suppose $B_{LR}(x, L)$ is quasi-tree-like, otherwise the result is trivial. Let $(\mathcal{F}_m)_{m \ge 0}$ be the standard filtration of the random graphs $(K_m)_m$. The choice of the edge $e_{m+1}$ is $\mathcal{F}_m$-measurable. Averaging conditional on $\mathcal{F}_m$, the generation of the $L+1$ long-range neighbourhood of the edge $e_{m+1}$ requires the sampling of at most $\Delta^{RL}$ long-range edges. For the first edge, there are exactly $n - \kappa_m$ possibilities. The quasi-tree structure is violated if an edge is sampled whose endpoint
is at small-range distance at most $R$ from a previous ball explored in the same phase or from $K_m$. In this case it is necessarily at small-range distance at most $R$ from a long-range edge of $K_m$. Hence the conditional probability of cycle($e_{m+1}$) is upper bounded by $\Delta^R(\Delta^{RL} + \kappa_m)/(n - \kappa_m - \Delta^{RL})$. Since $K_0 := B_{LR}(x, L)$ and the sets $K_m$ are increasing, $\kappa_m \ge \Delta^{RL}$ thus we can bound the conditional probability

$$ \mathbb{P}[\text{cycle}(e_{m+1}) | \mathcal{F}_m] \le \frac{2\Delta^{R(L+1)}\kappa_m}{n - 2\kappa_m} $$

Since

$$ \mathbb{E}[W_{m+1} - W_m | \mathcal{F}_m] = \mathbb{1}_{m<\tau} \hat{w}(e_m) \mathbb{P}[\text{cycle}(e_{m+1}) | \mathcal{F}_m] $$

(5.76) implies for some constant $C > 0$

$$ \begin{aligned} \mathbb{E}[W_{m+1} - W_m | \mathcal{F}_m] &\le \mathbb{1}_{m<\tau} \frac{Cl\Delta^{R(2L+1)}}{n - 2\kappa_\tau}, \\ \mathbb{E}[(W_{m+1} - W_m)^2 | \mathcal{F}_m] &\le \mathbb{1}_{m<\tau} \frac{Cl^2\Delta^{R(3L+1)}}{\kappa_m(n - 2\kappa_\tau)} \end{aligned} $$

Furthermore, since every iteration of the procedure reveals at least one long-range edge, $\kappa_m \ge \Delta^{RL} + m$, in particular $\tau \le \kappa_\tau$, hence summing over $m$ yields

$$ \begin{aligned} a &:= \sum_{m=s}^{\tau-1} \mathbb{E}[W_{m+1} - W_m | \mathcal{F}_m] \le C' \kappa_\tau \frac{l\Delta^{R(2L+1)}}{n - 2\kappa_\tau}, \\ b &:= \sum_{m=s}^{\tau-1} \mathbb{E}[(W_{m+1} - W_m)^2 | \mathcal{F}_m] \le C' \log(\kappa_\tau) \frac{l^2 \Delta^{R(3L+1)}}{n - 2\kappa_\tau} \end{aligned} $$

for some other constant $C' > 0$. Using (5.77), the assumptions made on the different parameters imply that $a = o(1)$ and $b = n^{-1+o(1)}$. Consider now the martingale $M_k$ defined by

$$ M_k := \frac{2}{\varepsilon} \left( W_k - W_s - \sum_{m=s}^{k-1} \mathbb{E}[W_{m+1} - W_m | \mathcal{F}_m] \right). $$

Its increments are bounded by 1 and by construction $W_\tau - W_s = \frac{\varepsilon}{2}M_\tau + a$. Since $a = o(1)$, we infer that for large enough $n$

$$ \mathbb{P}[W_\tau - W_s > 2\varepsilon] \le \mathbb{P}[M_\tau > 2] \le \mathbb{P}[\exists k > 0 : M_k > 2]. $$

Thus we can apply Theorem 1.6 of [74] to bound

$$ \mathbb{P}[\exists k > 0 : M_k > 2] \le e^2 \left( \frac{4b/\varepsilon}{2 + 4b/\varepsilon} \right)^{2+4b/\varepsilon} \le (2b\varepsilon^{-2})^2. $$

Since $b = n^{-1+o(1)}$, the right hand side is $o(1/n)$. $\square$

<figure><img src="image_19.png" /></figure>
5.9.2 Nice paths: definition

We now define nice paths in order to prove Proposition 5.2. For the rest of this section set

$$
R := C_R \log \log n, \quad C_L := C_L \log \log n, \quad M := (\log \log n)^\kappa.
$$

where $C_R, C_L > 0$ and $\kappa \ge 1$ are constants chosen large enough so that the conclusion of Lemma 5.3 holds. By the second point of Lemma 5.2, there exists a constant $\alpha > 0$ such that with high probability, from any starting point the chain has $\mathcal{P}$ quasi-tree-like neighbourhood of radius $[\alpha \log n]$ after $\log n/2h$ steps. Fix $\epsilon \in (0, 1)$ for the rest of this section. In the sequel, we consider several constant $C_0, \dots, C_5$, defined in terms of the constants $C_{LR}(\epsilon), C_h(\epsilon), C'_{LR}(\epsilon)$ of Proposition 5.1 which can in particular depend on $\epsilon$. They are indexed in the reverse order in which they are fixed, so $C_0$ is chosen after $C_1$, which is chosen after $C_2$, etc. Let

$$
\begin{equation} \tag{5.79}
\begin{split}
t &:= \left\lfloor \frac{\log n}{h} + C_0 \sqrt{\log n} \right\rfloor, & s &:= \left\lfloor \alpha \log n \right\rfloor \wedge \left\lfloor \frac{\log n}{10h} \right\rfloor, & l_1 &:= d(t-s) - C_4 \sqrt{t} \\
w_{\min} &:= e^{-h(t-s)-C_h \sqrt{t}} & w_{\max} &:= e^{-ht+C_1 \sqrt{t}}.
\end{split}
\end{equation}
$$

Given $r \in \mathbb{N}/2$, $L \le r \le M$ and $l_3 \in [\ell s - C_5\sqrt{s}, \ell s + C_5\sqrt{s}]$, consider the following three-stage generation of the environment:

1. Explore $K = K(x_0, l_1, w_{\min})$ as explained in the previous section. Let $E := E_{\tau}$ be the set of long-range edge remaining in the exploration queue at the end of the procedure, and consider the set $E'$ of boundary vertices at long-range distance $l_1$ from $x_0$, whose image under $\eta$ is yet to determine.

2. The backward neighbourhood is $B = B(r, r + s, l_3) := B_{\mathcal{P}}^{-}(y, r + s) \cap B_{\text{LR}}^{-}(y, l_3)$.

3. Finally, reveal everything else.

It will be crucial in the sequel to control the numbers $N_1, N_2$ of long-range edges
revealed during the two first stages. By definition $N_1 := \kappa(x, l_1, w_{\min})$. Observe then
that if $\varepsilon' \in (0, h/10 \log \Delta)$, then $h(t-s) < (1-\varepsilon') \log n$. Thus by (5.77),

$$
N_1 = O(l_1 \Delta^{RL} e^{h(t-s)+C_h \sqrt{t}}) = O(\log n \Delta^{C_R C_L (\log \log n)^2} n^{1-\varepsilon'} e^{C \sqrt{\log n}})
$$

for some constant $C$. The cardinality of $B$ is bounded by that of $B_{\mathcal{P}}^{-}(y, r + s)$, which is $O(\Delta^{r+s}) = O(n^{2/10})$ by choice of $r \le M$ and $s$. All in all, for any $\varepsilon' \in (0, h/10 \log \Delta)$,

$$
\begin{equation} \tag{5.80}
\begin{split}
N_1 &= O(n^{1-\epsilon'}), \\
N_2 &= O(n^{1/10}).
\end{split}
\end{equation}
$$

Let $\mathcal{F}_{r,l}$ be the $\sigma$-algebra generated by the long-range edges revealed during the two first stages. Since $K$ is quasi-tree-like, a non-backtracking long-range path $\xi$ from $x$
to $E'$ entirely contained in $K$ must cross a unique edge of $E$. Let $\xi_E$ denote this edge and define $w_E(\xi) := w_{x,R,L}(\xi_1 \cdots \xi_E)$. This is essentially the weight $w(\xi)$, but where last steps of the path were truncated to keep a weight that is $\mathcal{F}_{r,l}$-measurable.

In $B$, let $F'$ be the set of boundary vertices which are at long-range distance exactly $l$ from $y$, for which the shortest long-range path to $y$ is unique and has a tree-like neighbourhood in $B_{\mathcal{P}}(y, r+s)$, that is $B \cap B_{LR}(z, L)$ contains no long-range cycle for all vertex $z$ on this path. Consider now the set $F$ of long-range edges in $B$ that are at long-range distance $L-1$ from $F'$. If $\xi$ is a non-backtracking long-range path from $F'$ to $y$, let $\xi_F$ denote the unique edge of $F$ crossed by $\xi$ and $\xi_{F+1}$ the subsequent edge. Set $w_F(\xi) := w_{\xi_F^+, R, L}(\xi_{F+1} \cdots \xi_{|\xi|-L+1})$, where $\xi_F^+$ is the endpoint of $\xi_F$ closest from $y$. Here we truncate the path at both ends: the first steps to have a $\mathcal{F}_{r,l}$-measurable weight but also the last steps, as the trajectories considered afterwards end at $y$.

**Definition 5.7.** Given $r \in \mathbb{N}/2$, $r \le M$ and $l \in [\ell s - C_5\sqrt{\log n}, \ell s + C_5\sqrt{\log n}]$ let $\mathfrak{N}_{r,l}^t(x, y)$ be the set of length $t$ paths $\mathfrak{p}$ between $x$ and $y$ such that

(i) $\mathfrak{p} \in \Gamma(R, L, M)$

(ii) $\mathfrak{p}$ can be decomposed as the concatenation $\mathfrak{p} = \mathfrak{p}_1\mathfrak{p}_2\mathfrak{p}_3$ of three paths such that: $\mathfrak{p}_1$ is a path from $x$ to $E'$ entirely contained in $K(x, l_1)$, whose endpoint is the only vertex of $E'$ it contains (which implies that it starts and ends with a long-range step),

(iii) $\mathfrak{p}_2$ is a path between $E'$ and $F'$ which starts with a small-range step but ends with a long-range step such that

$$C_3\sqrt{\log n} \le |\mathfrak{p}_2| \le C_2\sqrt{\log n}.$$

for some $C_2, C_3$. In addition, $\mathfrak{p}_2$ contains a regeneration edge outside $K(x, l_1, w_{\min})$ before step $ML$, and the endpoint of $\mathfrak{p}_2$ is the only vertex of $B(y, r+s, l)$ it contains.

(iv) $\mathfrak{p}_3$ is a path of length $r+s$ from $F'$ to $y$ entirely contained in $B(y, r+s, l)$, which starts and ends with a small-range step and does not contains any regeneration edge in its first $r$ steps,

(v) $w_E(\xi(\mathfrak{p}_1))w_F(\xi(\mathfrak{p}_3)) \le w_{\max}$.

In the sequel we consider

$$\mathcal{P}_{r,l}^t(x, y) := \sum_{\mathfrak{p} \in \mathfrak{N}_{r,l}^t(x, y)} \mathcal{P}(\mathfrak{p}).$$
The complete set of nice paths is obtained by taking the union over parameters $r, l$, namely

$$ \mathfrak{N}^t(x, y) := \bigcup_{r \le M} \bigcup_{l=\ell s - C_5 \sqrt{s}}^{\ell s + C_5 \sqrt{s}} \mathfrak{N}_{r,l}(x, y). $$

and the total probability of nice paths by $\mathcal{P}_{\mathfrak{N}}^t(x, y) := \sum_{\mathfrak{p} \in \mathfrak{N}^t(x, y)} \mathcal{P}(\mathfrak{p})$.

Conditions (i) and (ii) allow to relate the probability of following a nice path with the weight constraint (v): thanks to the tree structure of $K(x, l_1)$, each vertex in $E'$ has a unique ancestor edge in $E$. Given $e \in E$, let $E'(e)$ denote the set of vertices in $E'$ with ancestor $e$ and recall $\xi(e)$ is the unique non-backtracking long-range path from $x$ to $e$. Similarly for $f \in F$, let $F'(f)$ be the set of vertices of $F'$ from which the unique non-backtracking long-range path to $y$ goes through $f$ and $\xi(f)$ the unique non-backtracking long-range path from $f^+$ to $y$ (which thus does not include $f$). Then for a fixed total long-range length $l$:

$$ \sum_{\substack{\mathfrak{p}:\xi(\mathfrak{p}_1)_{E}=e \\ \xi(\mathfrak{p}_3)_{F}=f \\ |\xi(\mathfrak{p})|=l}} \mathcal{P}(\mathfrak{p}) \le \sum_{\substack{\xi:\xi_E=e \\ \xi_F=f, \\ |\xi|=l}} \mathbf{P}_x[\xi(X_0 \cdots X_{\tau_l})_{\le l-L+1} = \xi, (X_0 \cdots X_{\tau_l}) \in \Gamma(R, L, M)] \\ \le \sum_{\substack{\xi:\xi_E=e \\ \xi_F=f, \\ |\xi|=l}} w_{x,R,L}(\xi). $$

by Lemma 5.4. For each $\xi$ in the sum,

$$ \begin{aligned} w_{x,R,L}(\xi) &= w_{x,R,L}(\xi_1 \cdots \xi_E) w_{\xi_E^+, R,L}(\xi_{E+1} \cdots \xi_F) w_{\xi_F^+, R,L}(\xi_{F+1} \cdots \xi_{l-L+1}) \\ &= w_E(\xi_1 \cdots \xi_E) w_{\xi_E^+, R,L}(\xi_{E+1} \cdots \xi_F) w_F(\xi_{F+1} \cdots \xi_{l-L+1}) \end{aligned} $$

Observe now that for fixed $e$ and $f$ the first and third factors are fixed as well and determined by $\xi(\mathfrak{p}_1), \xi(\mathfrak{p}_3)$, so the sum is only over the steps $\xi_{E+1} \cdots \xi_{F-1}$. Since weights sum up to 1, we can also sum over $l$ and bound

$$ \sum_{\substack{\mathfrak{p}:\xi(\mathfrak{p}_1)=\xi_1 \\ \xi(\mathfrak{p}_3)=\xi_3}} \mathcal{P}(\mathfrak{p}) \le w_{\max} \qquad (5.81) $$

thanks to the weight constraint (v). In words: the total probability of nice paths with prescribed long-range edges in $E$ and $F$ is upper bounded by $w_{\max}$.

### 5.9.3 Nice paths are typical

We prove here points (i)-(ii) of Proposition 5.2. The argument is the same for both points and relies on Lemmas 5.1, 5.2, 5.3 and Proposition 5.1. Let $t = \log n/h + C_0(\varepsilon)\sqrt{\log n}$. To prove (i) we can consider a fixed starting state $x \in V$ and then need
to ensure that the $t$ steps of a trajectory are nice with quenched probability at least $1 - \varepsilon$, while for point (ii) we need to prove the last $t$ steps of a length $s' + t$ trajectory are nice, for $s' = (\log n)^a, a \ge 1$ or $s' = C \log \log n, C > 0$ in the reversible case, this time independently of the starting state. The proof thus only differs by which statement of the aforementioned Lemmas and Proposition we use. Let us for instance focus on point (ii) in the general model. Consider $a \ge 1$ such that the statement of Lemmas 5.2, 5.3 and Proposition 5.1 hold. There are several properties to check. Since there are finitely many of them, once a property is shown to hold with probability $1 - o_p(1)$ or $1-\varepsilon$ we can automatically assume it is satisfied when checking the remaining properties. Write $t' := s' + t$ to simplify notation.

We already proved in Lemma 5.3 that a failure of the requirement $(X_{s'} \cdots X_{t'}) \in \Gamma(R, L, M)$ occurs with probability $o_p(1)$. For fixed $r, l$ the very definition of the backward neighbourhood $B(r, r+s, l)$ implies that it necessarily contains the last $r-s$ steps of the trajectory provided they have the prescribed long-range length $l$. Summing over $r$ and $l$, the constraint that $p_2$ only has its last endpoint in the backward neighbourhood while $p_3$ is contained in it amounts to conditioning by the last regeneration time occurring before $s$. In particular this requires the existence of a regeneration time in the interval $[t' - s - M, t' - s]$ but this is exactly ensured by the fact that $(X_{s'} \cdots X_{t'}) \in \Gamma(R, L, M)$. Assume now this property hold and let $T_{F'}$ denote the last regeneration before time $t' - s$. The remaining obstructions to following a nice paths are:

1. the first steps of $(X_{s'} \cdots X_{t'})$ are not contained in $K = K(X_{s'}, l, w_{\min})$, which occurs if $B_{LR}(X_{s'}, L)$ is not quasi-tree-like. This occurs with probability $o_p(1)$ by Lemma 5.2.

2. from $X_{s'}$, the chain leaves $K$ before it reaches long-range distance $l_1$, which occurs if:

* the loop-erased trace exits $K$ through the $L$ long-range neighbourhood of an edge $e$ which satisfied $\hat{w}(e) < w_{\min}$: since cumulative weights along a path are non-increasing this implies $-\log w(\xi(X_{s'} \cdots X_{t'-s})) > -\log w_{\min} = h(t-s) + C_h \sqrt{t}$ which occurs with probability less than $\varepsilon$ by Proposition 5.1.

* the chain crosses an edge which violated the quasi-tree structure. Recall the process considered in Lemma 5.23. As mentionned above we can suppose $B_{LR}(X_{s'}, L)$ is quasi-tree-like. Then by Proposition 5.1, the total probability of paths with long-range length $L$ and weights above $\varepsilon/2$ is $o_p(1)$. Thus up to this $o_p(1)$ error the quantity $W_\kappa$ considered in the lemma exactly counts the probability to exit $K$ at an edge which violated the tree structure. Thanks
to the choice of $w_{\min}$ (5.79) the lemma establishes that with high probability, $W_{\kappa} \le W_{[L/2]} + \varepsilon$ for any value of $X_{s'}$. However $W_{[L/2]} = 0$ as $B_{LR}(X_{s'}, L)$ is quasi-tree-like.

3. the path from $X_{t'-s-T_{F'}}$ to $y$ is not unique or its long-range length is not in the interval $[ds - C_5\sqrt{\log n}, ds + C_5\sqrt{\log n}]$. If this path is not unique, this implies in particular that the ball $B(X_{t'-s-M}, t' - s - M)$ is not quasi-tree-like. Since $s+M = O(s)$ Lemma 5.2 shows this occurs with probability $o_P(1)$. For the long-range distance requirement, Proposition 5.1 shows that $||\xi(X_{t'-s}...X_{t'})| - ds| \le C_{LR}\sqrt{s}$ with probability at least $1 - \varepsilon - o(1)$. Then note that the long-range distance traveled in the intervals $[T_{F'}, t']$ and $[t' - s, t']$ differ by at most $M$, hence $||\xi(X_{t'-s-T_{F'}}...X_{t'})| - ds| \le C_{LR}\sqrt{s} + M \le C_5\sqrt{s}$ for a large enough constant $C_5$, using that $M = o(s)$.

4. No regeneration occured outside $K$ during the first ML steps of the intermediate path $\mathfrak{p}_2$ or the latter does not have length $O(\sqrt{t})$. Since the trajectory is in $\Gamma(R, L, M)$ there must be regeneration edge in less than $M$ steps after having first reached $E'$. By the non-backtracking property, this regeneration edge is either outside $K$ or at long-range distance less than $L$ from $E'$, after which the chain is forced to exit $K$. Thus the $L$-th consecutive regeneration edge must be outside $K$. Using again that regeneration edges are spaced by at most $M$ steps, this makes in total ML steps at most until a regeneration occurs outside $K(x, l_1)$. For the length requirement observe that the long-range length is sub-additive. Since by definition a nice trajectory decomposes as the concatenation $(X_{s'}...X_{t'}) = \mathfrak{p}_1\mathfrak{p}_2\mathfrak{p}_3$ the sub-additivity implies

$$|\xi(X_{s'}...X_{s'+t})| \le |\xi(\mathfrak{p}_1)| + |\xi(\mathfrak{p}_2)| + |\xi(\mathfrak{p}_3)|.$$

The path $\xi(\mathfrak{p}_1)$ has length $l_1$, whereas $\xi(\mathfrak{p}_3)$ has variable length but from the bounds on $l$ in Definition 5.7 and (5.79) we infer that their combined length is

$$|\xi(\mathfrak{p}_1)| + |\xi(\mathfrak{p}_3)| \le dt - (C_4 - C_5)\sqrt{t},$$

while the intermediate path obviously has length $|\xi(\mathfrak{p}_2)| \le |\mathfrak{p}_2|$. Choose $C_4 \ge C_5+2C_{LR}$. Hence if $|\mathfrak{p}_2| < C_3\sqrt{t}$ with $C_3 := C_{LR}$, then $|\xi(X_{s'}...X_{s'+t})| < dt - C_{LR}\sqrt{t}$, which occurs with probability at most $o_P(1)$ by Proposition 5.1. To prove the upper bound on $|\mathfrak{p}_2|$, observe $|\mathfrak{p}_1| + s'$ coincides with the first hitting time $\tau_{l_1}$ of long-range distance $l_1$ after step $s'$. From Proposition 5.1 we can deduce the existence of $C_2 > 0$ such that $\tau_{l_1} - s' \ge t - s - C_2\sqrt{t}$ with probability at least $1 - \varepsilon$. Since $|\mathfrak{p}_3| \ge s$, we deduce that

$$|\mathfrak{p}_2| = t - |\mathfrak{p}_1| - |\mathfrak{p}_3| \le C_2\sqrt{t}.$$
5. $w_E(\xi(X_{s'} \cdots X_{\tau_{l_1}}))w_F(\xi(X_{t'-s-T_F'} \cdots X_{t'})) > w_{\max}$: let $\xi := \xi(X_{s'} \cdots X_t)$. When deriving (5.81) we used that

$$w_{x,R,L}(\xi) = w_E(\xi_1 \cdots \xi_E)w_{\xi_E^+,R,L}(\xi_{E+1} \cdots \xi_F)w_F(\xi_{F+1} \cdots \xi_l)$$

where $\xi_l$ is the last edge of $\xi$. Now by the non-backtracking property of nice paths $\xi(X_{s'} \cdots X_{\tau_{l_1}})$ and $\xi(X_{t'-s-T_F'} \cdots X_{t'})$ contain $\xi_1 \cdots \xi_E$ and $\xi_{F+1} \cdots \xi_l$ respectively so the goal is to show that $w_E(\xi_1 \cdots \xi_E)w_F(\xi_{F+1} \cdots \xi_l) > w_{\max}$ with probability at most $\varepsilon$. As we argued for the previous point, Proposition 5.1 implies $\tau_{l_1} - s' \ge t_1 := t - s - C_2\sqrt{t}$ with probability at least $1 - \varepsilon$. Since cumulative weights are non-increasing along a path, we deduce that

$$w_E(\xi_1 \cdots \xi_E) \le w_{x,R,L}(\xi(X_{s'} \cdots X_{t_1})) \le e^{-t_1 h + C_h \sqrt{t_1}}$$

with probability at least $1 - \varepsilon$. Similarly we know that $T_F' \le t' - s$, hence

$$w_E(\xi_1 \cdots \xi_F) \ge w(\xi(X_{s'} \cdots X_{t'-s})) \ge e^{-(t-s)h - C_h \sqrt{t-s}}$$

with probability at least $1 - \varepsilon - o(1)$. From these two bounds, we deduce

$$w_{\xi_E^+,R,L}(\xi_{E+1} \cdots \xi_F) \ge e^{-C_h \sqrt{t-s} - C_h \sqrt{t_1} - Ch\sqrt{t}} \ge e^{-C'\sqrt{t}}$$

for some $C' = C'(\varepsilon) > 0$. Thus if $w_E(\xi_1 \cdots \xi_E)w_F(\xi_{F+1} \cdots \xi_l) > w_{\max}$ we obtain that

$$w_{x,R,L}(\xi) \ge w_{\max} e^{-C'\sqrt{t}}$$

which has probability at most $\varepsilon$ if the constant $C_1$ in $w_{\max}$ (5.79) is taken sufficiently large.

### 5.9.4 Concentration of nice paths

Recall $\mathcal{F}_{r,l}$ is the $\sigma$-algebra generated by the long-range edges revealed during the two first stages. For fixed $r$ and $l$, we prove concentration of $\mathcal{P}_{\mathfrak{N}_{r,l}}^t(x, y)$ conditional on $\mathcal{F}_{r,l}$ using Theorem 4.1. The concentration will be strong enough for a union bound, which will yield Proposition 5.2. Conditional on $\mathcal{F}_{r,l}$ all the randomness of $\mathcal{P}_{\mathfrak{N}_{r,l}}^t(x, y)$ comes from the intermediate path $\mathfrak{p}_2$. It is contained in a random environment that arises from a uniform bijection $\sigma'$ between the two subsets $V'_1 \subset V_1$, $V'_2 \subset V_2$ that remain to be matched after the two first stages. As was observed in the previous section, the two first stages revealed a number of long-range edges which is $O(n^{1-\varepsilon'})$, so $\sigma'$ is a uniform bijection between sets of $n' = n - o(n)$ elements, which can be identified with a uniform permutation of $n'$ elements.

The following lemma proves that conditions of concentration are fulfilled. We use Corollary 4.1 which is more practical to use than Theorem 4.1.
**Lemma 5.24.** For all $r \le M, l \ge 0$, conditional on $\mathcal{F}_{r,l} \mathcal{P}_{\mathfrak{N}_{r,l}}^t (x, y)$ can be realized as a
multilinear function $\phi$ on $S_{n'}$ of degree at most

$$d := C_2 \sqrt{\log n'}. \qquad (5.82)$$

With the notations of Corollary 4.1,

$$\alpha_{\phi} = O(d^3(4\Delta)^d w_{\max} \log n), \quad A_{\phi} = O(d^2 \Delta^d n^{2/10} w_{\max}) \\ \text{and} \quad A_{\nabla \phi} = O(d^2(2\Delta)^d w_{\max}).$$

*Proof.* A pair of multi-indices $(i, j)$ of size $k$ identifies with a sequence of $k$ potential long-range edges $(i_1, j_1), \dots (i_k, j_k)$. Note that all properties required of nice paths are either $\mathcal{F}_{r,l}$-measurable or can be determined from the path (this would not be the case if we had chosen for instance to take the weight of $w(\xi(p_2))$ into account). Therefore it is possible to define the coefficient $a_{ij}$ as the total probability of nice paths which meet exactly these long-range edges in addition to those that are contained in $K$ or $B$ (which do not count as random here). Nice paths do not have to cross the long-range edges but may only pass through one endpoint, due to the fact that the probability $p = p(x, \sigma(x))$ of crossing a long-range edge depends in general on $\sigma$.

The upper bound on the degree follows easily from this definition. By Point (iii) in Definition 5.7, the random part $p_2$ of nice paths has length bounded by $d = C_2\sqrt{\log n'}$ which thus also upper bounds the number of long-range edges met by nice paths and consequently the degree.

To prove concentration recall the notation of Proposition 4.1. Consider a set $S$ of long-range edges of size $d$ or less. It is connected to at most $d$ vertices of $E'$ and $F'$, which in turn correspond to at most $d$ edges in $E$ and $F$. Therefore the set of nice paths that meet the edges of $S$ exactly can cross at most $d$ edges of $E$ and $d$ edges of $F$, hence by (5.81) we deduce that the maximal coefficient of $\phi$ is bounded by $d^2 w_{\max}$. By multilinearity, the maximal coefficient is non-increasing with respect to partial differentiation (see Lemma 4.6) so this proves

$$M(\partial_{ij}\phi, \sigma) \le M(\phi, \sigma) \le d^2 w_{\max}$$

for any potential long-range edge $(i, j)$. On the other hand, the number of monomials in $\phi$ can be upper bounded by the maximal number of paths between $E'$ and $F'$ of length $d$. Since $F'$ has cardinality at most $n^{2/10}$ by (5.80)

$$N(\phi, \sigma) \le |F'| \Delta^d = O(\Delta^d n^{2/10}).$$

Restricting to a potential long-range edge $(i, j)$, the latter can be part of at most $O((2\Delta)^d)$ paths of length $d$ between $E'$ and $F'$ and thus as many monomials. Therefore

$$N(\partial_{ij}(\phi, \sigma)) \le O((2\Delta)^d).$$
We deduce that $A_{\phi} = O(d^2\Delta^d n^{2/10}w_{\max})$ and $A_{\nabla\phi} = O(d^2(2\Delta)^d w_{\max})$. The log factor in Theorem 4.1 is thus $O(\log n)$ hence

$$ \alpha_{\phi} = O(d^3(4\Delta)^d w_{\max} \log n). $$

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

The following Lemma will be sufficient to deduce Proposition 5.2. The proof is postponed to the next section. Recall the measure $Q_u^{(L)}$ was defined in (5.19). To ease notation we will drop the exponent (L) in the sequel. Recall also that $T_1^{(G,l)}$, $T_1^{(G,l)}$ denote regeneration times with horizon L in $G^*$ and $G$ respectively, $\mu$ is the invariant measure of the regeneration chain in the quasi-tree and $\nu$ was considered in Proposition 5.12. Below we write $Q_{\nu+c} = \sum_u (\nu(u) + c(u))Q_u$.

**Lemma 5.25.** There exists a measure c on V such that $\sum_{v \in V} c(v) = o_P(1)$ and

$$ 1-o_P(1) \le \mathbb{E} \left[ \mathcal{P}_{\mathfrak{N}_{r,l}}^t (x,y) \mid \mathcal{F}_{r,l} \right] \left( \frac{\mathbf{Q}_{\nu+c} [X_{r+s} = y, |\xi(X_0 \cdots X_{r+s})| = l, r < T_1 \le M]}{\mathbb{E}_{\mathcal{Q}_{\mu}} [T_1^{(G,\infty)}]} \right)^{-1} \le 1. \quad (5.83) $$

*Proof of Proposition 5.2.* Points (i)-(ii) were established proved in Section 5.9.3 so we now prove (iii) - (iv). Suppose first $x, y \in V$ and $r, l$ are fixed. Let $\phi := \mathcal{P}_{\mathfrak{N}_{r,l}}^t (x, y)$ as in Lemma 5.24 and $z := \frac{\varepsilon}{2} \mathbb{E}[\phi] + \frac{\varepsilon}{2C_6 M n \sqrt{\log n}}$ for some $C_6 > 0$. Note that $w_{\max} \le e^{-C\sqrt{\log n}}/n$ for some constant C which tends to $+\infty$ as the constant $C_0$ in the definition of t grows (5.79), while other factors of $\alpha_{\phi}$, $A_{\nabla\phi}$ are of all of order at most $e^{C'\sqrt{\log n}}$. Thus for any choice of $C = C(\varepsilon) > 0$ Lemma 5.24 shows that $\alpha_{\phi}$, $A_{\nabla\phi}$ can both be bounded by $e^{-C\sqrt{\log n}}/n$, provided the constant $C_0$ is sufficiently large, while $d^2(d-1)A_{\phi}/n = o(n^{-3/5})$. In particular we can choose C so that $A_{\nabla\phi} \le z$. Since $\mathbb{E}[\phi] \le 2z/\varepsilon$ and $z \ge \varepsilon/(2C_6 M n \sqrt{\log n})$, applying Corollary 4.1 yields

$$ \mathbb{P}[|\phi - \mathbb{E}[\phi]| \ge z] \le 2 \exp \left( \frac{-C' \varepsilon^2}{\alpha_{\phi} M n \sqrt{\log n}} \right) \quad (5.84) $$

for some $C' = C'(\varepsilon) > 0$. Up to increasing again the value of C, we can ensure that $\alpha_{\phi} M n \sqrt{\log n} \le (\log n)^{-2}$, hence

$$ \mathbb{P}\left[\left|\phi - \mathbb{E}[\phi]\right| > \frac{\varepsilon}{2}\mathbb{E}[\phi] + \frac{\varepsilon}{2C_6 M n \sqrt{\log n}}\right] \le \exp\left(-C'\varepsilon^2(\log n)^2\right). $$

This is sufficient to take a union bound over $x, y \in V$ and $r \le M, l \in [ds - C_5\sqrt{\log n}, ds + C_5\sqrt{\log n}]$. Thus summing over $r, l$ we obtain that with high probability, for all $x, y \in V$,

$$ \left| \mathcal{P}_{\mathfrak{N}}^t (x, y) - \sum_{r,l} \mathbb{E} \left[ \mathcal{P}_{\mathfrak{N}_{r,l}}^t (x, y) \mid \mathcal{F}_{r,l} \right] \right| \le \frac{\varepsilon}{2} \sum_{r,l} \mathbb{E} \left[ \mathcal{P}_{\mathfrak{N}_{r,l}}^t (x, y) \mid \mathcal{F}_{r,l} \right] + \frac{\varepsilon}{n}. $$
Lemma 5.25 gives an estimate of the conditional expectation which shows:

$$
\begin{align}
\mathcal{P}_{\mathfrak{N}}^{t}(x, y) &\le \frac{1 + \varepsilon/2}{\mathbb{E}_{\mathbb{Q}_{\mu}}[T_{1}^{(G, \infty)}]} \sum_{r=0}^{M} \mathbf{Q}_{\nu+c} \left[X_{r+s} = y, r < T_{1}^{(G,L)} \le M\right] + \frac{\varepsilon}{n} \nonumber \\
&= (1 + \varepsilon/2) A \hat{\pi}(y) + \frac{(1 + \varepsilon/2) A}{\mathbf{E}_{\mathbb{Q}_{\nu}}[T_{1}^{(G,L)}]} \sum_{r=0}^{M} \mathbf{Q}_{c} \left[X_{r+s} = y, r < T_{1}^{(G,L)} \le M\right] + \frac{\varepsilon}{n}. \tag{5.85}
\end{align}
$$

with $A := \frac{\mathbf{E}_{\mathbb{Q}_{\nu}}[T_1^{(G,L)}]}{\mathbb{E}_{\mathbb{Q}_{\mu}}[T_1^{(G,\infty)}]}$. Summing over $y \in V$ and $r \in [0, M]$ in the second term yields $(1 + \varepsilon/2) A \sum_{v \in V} c(v) \le 2A\varepsilon$ with high probability. On the other hand, from Lemma 5.25 we also have the lower bound

$$
\mathcal{P}_{\mathfrak{N}}^{t}(x, y) \geq (1 - \varepsilon/2)(1 - o_{\mathbb{P}}(1))A\hat{\pi}(y) - \varepsilon/n,
$$

which by summing over $y \in V$ shows that $A \le 1 + 10\varepsilon$ with high probability. Plugging
this in the upper bound above yields the second statement of the proposition.

Let us move to the proof of (iv). Define

$$
\hat{\pi}_1(v) := \frac{1}{\mathbf{E}_{\mathbf{Q}_\nu}[T_1^{(G,L)}]} \sum_{r=0}^{M} \sum_{u \in S} \nu(u) \mathbf{Q}_u \left[ X_{r+s} = v, r < T_1 \le M, \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} > M+s \right]
$$

for all $v \in V$ and decompose $\hat{\pi} := \hat{\pi}_1 + \hat{\pi}_2$.

We start bounding $\hat{\pi}_2(V)$. Summing over $y$ in (5.85), the left hand side becomes the total probability of following a nice path, which by the first part of the proposition is at least $1 - \varepsilon$ with high probability for a typical $x \in V$. Consequently $A$ can be lower bounded by a constant with high probability, which implies that for some constant $c > 0$, $\mathbf{E}_{\mathbb{Q}_{\nu}}[T_1^{(G,L)}] \ge c$ with high probability. Thus by summing over $v \in V$ we can bound

$$
\hat{\pi}_2(V) \le c^{-1} M \mathbf{Q}_{\nu} \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \le M + s \right] + o_{\mathbb{P}}(1).
$$

Then notice that the quenched probability $\mathbf{P}[\tau_{\eta(u)} > \tau_L | X_{1/2} = u]$ can always be lower
bounded by $q_n := \delta^{CL}$ for some constant $C > 0$, hence

$$
\begin{align*}
\hat{\pi}_2(V) &\le c^{-1} M \sum_{u \in V} \nu(u) \frac{\mathbf{P}\left[\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \le M+s, \tau_{\eta(u)} > \tau_L \mid X_{1/2} = u\right]}{\mathbf{P}\left[\tau_{\eta(u)} > \tau_L, X_{1/2} = u\right]} + o_{\mathbb{P}}(1) \\
&\le c^{-1} q_n^{-1} M \sum_{u \in V} \nu(u) \mathbf{P}\left[\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \le M+s \mid X_{1/2} = u\right] + o_{\mathbb{P}}(1).
\end{align*}
$$

As $L = O(\log \log n)$ one has $q_n^{-1} = O((\log n)^{-b})$ for some $b > 0$. Next by Markov's
property for all $u \in V$

$$ 
\begin{aligned}
\mathbf{P} \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s \mid X_{1/2} = u \right] &= \mathbf{P} \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s \mid X_0 = u, X_{1/2} = u \right] \\
&= \frac{\mathbf{P}_u \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s, X_{1/2} = u \right]}{p(u, \eta(u))} \\
&\leq c' \mathbf{P}_u \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s \right]
\end{aligned}
$$

for some constant $c' > 0$ as the entries of $p$ are bounded (Assumption (H2)). For fixed $u \in V$, Lemma 5.3 shows $\mathbf{P}_u[\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s] = o_{\mathbb{P}}((\log n)^{-b}) = o_{\mathbb{P}}(q_n^{-1})$ as $M + s = O(\log n)$. Letting $U \in V$ be a random variable independent from the environment, this can be rephrased as the fact that $\mathbf{P}_U[\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s] = o_{\mathbb{P}}(q_n^{-1})$ conditional on $U$, but then this statement must also hold unconditionally. As the measure $\nu$ is deterministic we can take $U$ of law $\nu$, after which by taking the conditional expectation with respect to the environment we get that

$$ \mathbb{E} \left[ \mathbf{P}_U \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s \right] \mid \eta \right] = \sum_{u \in V} \nu(u) \mathbf{P}_u \left[ \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} \leq M + s \right] = o_{\mathbb{P}}(q_n^{-1}). $$

All in all, this proves $\hat{\pi}_2(V) = o_{\mathbb{P}}(1)$.

To bound the $\ell^2$ norm of $\hat{\pi}_1$, we can use what precedes to first bound

$$ 
\begin{aligned}
\hat{\pi}_1 &\leq c^{-1} M \max_{r \leq M} \mathbf{Q}_{\nu} \left[ X_{r+s} = \cdot, \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} > s \right] \\
&\leq c^{-1} q_n^{-1} M \max_{r \leq M} \sum_{u \in V} \nu(u) \mathbf{P} \left[ X_{r+s} = \cdot, \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} > M + s \mid X_{1/2} = u \right].
\end{aligned}
$$

Consequently

$$ \mathbb{E} \left[ \sum_{v \in V} \tilde{\pi}_1(v)^2 \right] \leq c^{-2} q_n^{-2} M^2 \max_{r \leq M} \mathbb{P} \left[ \begin{array}{l} X_{r+s} = X'_{r+s}, \tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} > s, \\ \tau_{\eta(X_{1/2})} > \tau_L, \tau_{\eta(X'_{1/2})} > \tau_L \end{array} \right] $$

where $X, X'$ are two independent chains conditional on the same environment, both started at time $1/2$ under the law $\nu$. Here the event $\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} > s$ applies to both chains. Fix $r \leq M$. Observe that if all long-range edges crossed by $X'$ are at distance more than $R$ from the trajectory followed by the first chain $X$, then $X'$ can reach $X_{r+s}$ only by deviating by a small-range distance $R$ or by crossing the long-range edge $(X'_{1/2}, \eta(X'_{1/2}))$ if $\eta(X'_{1/2}) \in B_{\text{SR}}^{-}(X_{1/2} \dots X_{r+s}, R)$. The event $\{\tau_{\eta(X'_{1/2})} > \tau_L\}$ proscribes this last possibility to occur before the chain has crossed a long-range distance $L$, so the chain must backtrack. Thus either of these two possibilities contradicts $\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)} > s$. Consequently the only possibility that the two chains meet is that the second one crosses a long-range edge at small-range distance less than $R$ from the first chain. From (5.56) $d_{\text{SR}}(X_{1/2}, X'_{1/2}) \leq R$ with probability $O(\Delta^R/n) = o(1)$ under $\nu$. Then assuming this does not hold, under the annealed law the environment can be generated sequentially
along the trajectories of the chains as explained in Section 5.2.7. The number of long-range edges met by $X'$ up to time $M+s$ which fall in a $R$ small-range neighbourhood of $X$ is thus stochastically dominated by a binomial $Bin(M+s, \Delta^R(M+s)/n)$. As $q_n = O((\log)^b)$, $R = O(\log \log n)$, $s = O(\log n)$, $M = o(\log n)$ we deduce that

$$ \mathbb{E}\left[\sum_{v \in V} \hat{\pi}_2(v)\right] \le O\left(\frac{C(\log n)^{b'}}{n}\right) $$

for some $b' > 0$, which gives the result by the first moment argument (5.4). $\square$

### 5.9.5 Expectation of nice paths

*Proof of Lemma 5.25.* Let $\tau_{E'}$ be the hitting time of $E'$ and $U_{t'}(K)$ the time spent in $K$ before the time $t' \ge 0$. By definition, a nice path requires that $\tau_{E'} \le t-s$ and the first part $\mathfrak{p}_1$ of the path is the trajectory until $\tau_{E'}$. The second part of a nice path is the trajectory until hitting $F'$ and is assured to spend less than $m := ML$ steps in $K$. Therefore by strong Markov's property, one can bound

$$ \begin{aligned} \sum_{\mathfrak{p} \in \mathfrak{N}_{r,l}} \mathcal{P}(\mathfrak{p}) &\le \sum_{\substack{t_1+t_2=t-(r+s) \\ C_3\sqrt{\log n} \le t_2 \le C_2\sqrt{\log n}}} \sum_{u \in E'} \sum_{v \in F'} (\mathbf{P}_x[\tau_{E'} = t_1, X_{t_1} = u]) \\ &\times \mathbf{P}\left[\exists k \ge 0 : T_k^{(G,L)} = t_2, X_{t_2} = v, U_{t_2}(K) \le m \mid X_{1/2} = u\right] \\ &\times \mathbf{P}\left[X_{r+s} = y, r < T_1 \le M \mid X_{1/2} = v, \tau_{\eta(v)>\tau_L}\right]. \end{aligned} \quad (5.86) $$

In each term of this sum, the first and third factor are $\mathcal{F}_{r,l}$-measurable, so only the second factor gets averaged when taking conditional expectation. We claim this expectation satisfies

$$ \sum_{v \in F'} \left| \mathbb{P} \left[ \exists k \ge 0 : T_k^{(G,L)} = t_2, X_{t_2} = v, U_{t_2}(K) \le m \mid X_{1/2} = u, \mathcal{F}_{r,l} \right] - \frac{\nu(v)}{\mathbb{E}_{\mathcal{Q}_\mu} [T_1^{(G,\infty)}]} \right| + o_P(1). $$

Note that $\nu/\mathbb{E}_{\mathcal{Q}_\mu}[T_1^{(G,\infty)}]$ is independent of $u$ and $t_1$, while the first factor in the sum considered above can be summed to at most 1. Also we can recognize the measure $\mathcal{Q}_v$ (5.19) in the third factor. Therefore provided the claim holds one obtains that for some $c = (c_v)_v$ satisfying $\sum_{v \in V} c(v) = o_P(1)$,

$$ \begin{aligned} \mathbb{E}\left[\left|\sum_{\mathfrak{p} \in \mathfrak{N}_{r,l}} \mathcal{P}(\mathfrak{p})\right| \mathcal{F}_{r,l}\right] &\le \sum_{v \in F'} \left(\frac{\nu(v)}{\mathbb{E}_{\mathcal{Q}_\mu}[T_1^{(G,\infty)}]} + c(v)\right) \mathcal{Q}_v[X_{r+s} = y, r < T_1 \le M] \\ &\le \sum_{v \in V} \frac{\nu(v) + c(v)}{\mathbb{E}_{\mathcal{Q}_\mu}[T_1^{(G,\infty)}]} \mathcal{Q}_v[X_{r+s} = y, d_{LR}(v, y) = l, r < T_1 \le M], \end{aligned} $$

where in the second we implicitly changed the definition of $c$, using that $\mathbb{E}_{\mathcal{Q}_\mu}[T_1^{(G,\infty)}] = O(1)$. This proves the upper bound in the lemma. To prove the lower bound, note that
the inequality (5.86) is not sharp if the trajectory is not in $\Gamma(R, L, M)$ or there is no regeneration time in the interval $[\tau_1, ML]$. This was shown to occur with probability $o_{\mathbb{P}}(1)$ in Section 5.9.3, so the upper bound is also a lower bound up to a $o_{\mathbb{P}}(1)$ error.

Let us prove the claim. Let $u \in E'$, $v \in F'$. The idea is to couple the chains $X$ and $\mathcal{X}$ on a quasi-tree to relate their regeneration times, in order to use Proposition 5.12. However the conditioning by $\mathcal{F}_{r,l}$ already revealed some-long range edges, which requires in turn a similar conditioning in the quasi-tree. We argue that the only conditioning required is by $B_{LR}(O, L)$, the ball of radius $L$ in a quasi-tree. Let $u_0$ be the ancestor of $E$ at long-range distance $L$ from $u$. By definition of $K(x, l_1)$, the $L$ long-range neighbourhood $B_{LR}(u_0, L)$ contains no long-range cycle and thus is a possible realization of $B_{LR}(O, L)$ around the root of a quasi-tree. Consider a quasi-tree $\mathcal{G}$ which has this ball as the neighbourhood of its root and is completed with the standard procedure (so without taking consideration of the long-range edges revealed in $K \cup B$). Using the coupling of Section 5.2.7, the chain $X$ started at $u$ can thus be coupled with the chain $\mathcal{X}$ on $\mathcal{G}$, started at the vertex of $B_{LR}(O, L)$ that identifies with $u$. This coupling fails after $X$ enters $B$ or if it re-enters $K$ by another path that the one it used. Let $\tau_{\text{coup}}$ denote this new coupling time.

From (5.80), the probability of sampling an element of either $K$ or $B$ under the uniform measure on $V$ is $O(1/n^{\varepsilon'})$ for some $\varepsilon' > 0$. Consequently, using the same comparison with a binomial we used in the proof of Lemma 5.1, this implies that the chain $X$ re-enters $K$ or reaches $B$ in $O(\sqrt{\log n})$ steps is $O(\log n/n^{2\varepsilon'}) = o(1)$. Note that considering regeneration times requires the knowledge of the $L$ steps ahead but this is $O(\log \log n)$. Consequently it remains true that for $t_2 + L = O(\sqrt{\log n})$,

$$ \sum_{v \in F'} \left| \begin{aligned} & \mathbb{P} \left[ \exists k \ge 0 : T_k^{(G,L)} = t_2, X_{t_2} = v, U_{t_2}(K) \le m \mid X_{1/2} = u, \mathcal{F}_{r,l} \right] \\ & - \mathbb{P} \left[ \exists k \ge 0 : T_k^{(G,L)} = t_2, \iota(\mathcal{X}_{t_2}) = v, U_{t_2}(K) \le m \mid \mathcal{X}_{1/2} = x, B_{LR}(O, L) \right] \end{aligned} \right| = o(1) $$

where $x \in B_{LR}(O, L)$ is a vertex at long-range distance $L$ with type $u$. Obviously, $\{T_k^{(G,\infty)}, k \ge 1\} \subset \{T_k^{(G,L)}, k \ge 1\}$. This inclusion may be strict however, if the chain backtracks over a long-range distance $L$. Lemma 5.18 shows this occurs before time $O(\sqrt{\log n})$ with probability $o(1)$. Consequently, with high probability $T_k^{(G,L)} = T_k^{(G,\infty)}$ for all regeneration times that occur before $t_2$, so we can exchange these random times in the equation above. Now since $t_2 = \Theta(\sqrt{\log n})$ and $m^2 = O((\log \log n)^{2\kappa+2}) = o(t_2)$, Proposition 5.12 proves that

$$ \sum_{v \in V} \left| \mathbb{P}_u \left[ \exists k \ge 0 : T_k^{(G,\infty)} = t_2, \iota(\mathcal{X}_{t_2}) = v, U_{t_2}(K) \le m \mid B_{LR}(O, L) \right] - \frac{\nu(v)}{\mathbb{E}_{\mathbb{Q}_\mu} \left[ T_1^{(G,\infty)} \right]} \right| \\ \le \mathbb{P}_u \left[ U_{t_2}(K) > m \mid B_{LR}(O, L) \right] / \mathbb{E}_{\mathbb{Q}_\mu} \left[ T_1^{(G,\infty)} \right] + o(1). $$
By Lemma 5.14, the first term is stretched exponential in $m$ and thus $o(1)$. Using triangle inequality to combine the two previous bounds yields the claim. $\square$
Bibliography

[1] Roy L Adler and Benjamin Weiss. Entropy, a complete metric invariant for automorphisms of the torus. *Proceedings of the National Academy of Sciences of the United States of America*, 57(6):1573, 1967. 90

[2] Elie Aidékon. Large deviations for transient random walks in random environment on a galton-watson tree. *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, 46(1):159-189, 2010. doi:doi:10.1214/09-AIHP204. 178, 180

[3] Joseph S. Alameda, Caroline Bang, Zachary Brennan, David P. Herzog, Jürgen Kritschgau, and Elizabeth Sprangel. Cutoff in the Bernoulli-Laplace model with $O(n)$ swaps, 2022. arXiv:2203.08647. 22, 33

[4] David Aldous. Random walks on finite groups and rapidly mixing markov chains. pages 243-297, 1983. URL: https://doi.org/10.1007%2Ffbf0068322, doi:10.1007/bfb0068322. 21, 22, 33

[5] David Aldous and Persi Diaconis. Shuffling cards and stopping times. *The American Mathematical Monthly*, 93(5):333–348, 1986. URL: http://www.jstor.org/stable/2323590. 21, 33

[6] David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/$\sim$aldous/RWG/book.html. 13, 25

[7] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. *Commun. Contemp. Math.*, 9(4):585–603, 2007. doi: 10.1142/S0219199707002551. 18, 30

[8] Claudio Asci. Generating uniform random vectors. *Journal of Theoretical Probability*, 14(2):333–356, 2001. 19, 31, 67, 70, 75

[9] Claudio Asci. Generating uniform random vectors in $Z_p^k$: The general case. *Journal of Theoretical Probability*, 22(3):791–809, 2009. 19, 31, 67, 68, 70
[10] Koenraad MR Audenaert. A sharp continuity estimate for the von Neumann entropy. *Journal of Physics A: Mathematical and Theoretical*, 40(28):8127, 2007.
74

[11] Luca Avena, Hakan Güldaş, 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, sep 2019. URL: https://doi.org/10.1016%2Fj.spa.2018.09.010, doi:10.1016/j.spa.2018.09.010. 119

[12] André Avez. Entropie des groupes de type fini. *C. R. Acad. Sci. Paris*, Sér. A-B 275:A1363–A1366, 1972. 14, 15, 26, 44

[13] Zsuzsanna Baran, Jonathan Hermon, Anđela Šarković, and Perla Sousi. Phase transition for random walks on graphs with added weighted random matching. 2023. arXiv:2306.13077. 119, 120, 121

[14] Riddhipratim Basu, Jonathan Hermon, and Yuval Peres. Characterization of cutoff for reversible markov chains. *The Annals of Probability*, 45(3):1448–1487, 2017. URL: http://www.jstor.org/stable/44245575. 23, 34

[15] Dave Bayer and Persi Diaconis. Trailing the dovetail shuffle to its lair. *The Annals of Applied Probability*, 2:294–313, 1992. doi:doi:10.1214/aoap/1177005705. 22, 33

[16] Anna Ben-Hamou. A threshold for cutoff in two-community random graphs. *The Annals of Applied Probability*, 30(4):1824 – 1846, 2020. doi:10.1214/19-AAP1544. 119

[17] Anna Ben-Hamou, Eyal Lubetzky, and Yuval Peres. Comparing mixing times on sparse random graphs. *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, 55(2):1116 – 1130, 2019. doi:10.1214/18-AIHP911. 118

[18] Anna Ben-Hamou and Yuval Peres. Cutoff for permuted Markov chains. *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, 59(1):230 – 243, 2023. doi:10.1214/22-AIHP1248. 67, 71, 119

[19] Anna Ben-Hamou and Justin Salez. Cutoff for nonbacktracking random walks on sparse random graphs. *The Annals of Probability*, 45(3):1752–1770, 2017. 115, 118, 120, 122, 207

[20] Itai Benjamini, Gady Kozma, and Nicholas Wormald. The mixing time of the giant component of a random graph. *Random Structures & Algorithms*,
45(3):383-407, 2014. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20539, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20539, doi:https://doi.org/10.1002/rsa.20539. 115, 118

[21] Yves Benoist and Frédéric Paulin. Systèmes dynamiques élémentaires. *Cours de Magistère ENS*, 3, 2002. URL: https://www.imo.universite-paris-saclay.fr/~paulin/notescours/cours_sysdyn.pdf. 79, 90

[22] Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, and Allan Sly. Random walks on the random graph. *The Annals of Probability*, 46(1):456–490, 2018. doi:doi:10.1214/17-AOP1189. 115, 118, 121, 146, 148, 149

[23] Kenneth Richard Berg. *On the conjugacy problem for K-systems*. PhD thesis, University of Minnesota, 1967. 90

[24] Sébastien Blachère, Peter Haïssinsky, and Pierre Mathieu. Asymptotic entropy and Green speed for random walks on countable groups. *Ann. Probab.*, 36(3):1134–1152, 2008. doi:10.1214/07-AOP356. 44

[25] E. Bolthausen. An estimate of the remainder in a combinatorial central limit theorem. *Probability Theory and Related Fields*, 66(3):379–386, 1984. doi:10.1007/BF00533704. 101

[26] Erwin Bolthausen and Friedrich Götze. The rate of convergence for multivariate sampling statistics. *Ann. Stat.*, 21(4):1692–1710, 1993. doi:10.1214/aos/1176349393. 101

[27] Charles Bordenave. A new proof of Friedman's second eigenvalue theorem and its extension to random lifts. *Ann. Sci. Éc. Norm. Supér. (4)*, 53(6):1393–1439, 2020. doi:10.24033/asens.2450. 119

[28] Charles Bordenave, Pietro Caputo, and Justin Salez. Random walk on sparse random digraphs. *Probab. Theory Relat. Fields*, 170(3-4):933–960, 2018. doi:10.1007/s00440-017-0796-7. 115, 119, 120, 122, 200, 207

[29] Charles Bordenave, Pietro Caputo, and Justin Salez. Cutoff at the “entropic time” for sparse Markov chains. *Probability Theory and Related Fields*, 173(1):261–292, February 2019. doi:10.1007/s00440-018-0834-0. 115, 119, 120, 122, 200

[30] Charles Bordenave and Bastien Dubail. Markovian Linearization of Random Walks on Groups. *International Mathematics Research Notices*, 05 2022. doi:10.1093/imrn/rnac045. 13, 25, 37
[31] Charles Bordenave and Hubert Lacoin. Cutoff at the entropic time for random walks on covered expander graphs. *J. Inst. Math. Jussieu*, 21(5):1571–1616, 2022. doi:10.1017/S1474748020000663. 47, 119, 172

[32] Charles Bordenave, Yanqi Qiu, and Yiwei Zhang. Spectral gap of sparse bico stochastic matrices with exchangeable rows. *Ann. Inst. Henri Poincaré, Probab. Stat.*, 56(4):2971–2995, 2020. doi:10.1214/20-AIHP1065. 70

[33] Stéphane Boucheron, Gábor Lugosi, and Pacal Massart. On concentration of self-bounding functions. *Electron. J. Probab.*, 14:no. 64, 1884–1899, 2009. doi:10.1214/EJP.v14-690. 104

[34] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. *Concentration in-equalities*. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux. doi:10.1093/acprof:oso/9780199535255.001.0001. 20, 31, 106, 107

[35] Philippe Bougerol et al. *Products of random matrices with applications to Schrödinger operators*, volume 8. Springer Science & Business Media, 2012. 61, 65

[36] Rufus Bowen. Markov partitions and minimal sets for Axiom A diffeomorphisms. *Amer. J. Math.*, 92:907–918, 1970. doi:10.2307/2373402. 79

[37] Rufus Bowen. *Equilibrium states and the ergodic theory of Anosov diffeomorphisms*, volume 470 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, revised edition, 2008. With a preface by David Ruelle, Edited by Jean-René Chazottes. 79, 90, 93

[38] Pietro Caputo and Matteo Quattropani. Mixing time of PageRank surfers on sparse random digraphs. *Random Structures & Algorithms*, 59(3):376–406, apr 2021. URL: https://doi.org/10.1002%2Frsa.21009, doi:10.1002/rsa.21009. 119

[39] Pietro Caputo and Matteo Quattropani. Mixing time trichotomy in regenerating dynamic digraphs. *Stochastic Processes and their Applications*, 137:222–251, jul 2021. URL: https://doi.org/10.1016%2Fj.spa.2021.03.003, doi:10.1016/j.spa.2021.03.003. 119

[40] René Carmona and Jean Lacroix. *Spectral theory of random Schrödinger operators*. Springer Science & Business Media, 2012. 61, 65
[41] Sourav Chatterjee. Concentration inequalities with exchangeable pairs. PhD thesis, Stanford University, 2005. arXiv:math/0507526. 20, 32, 97, 101, 104, 106, 108

[42] Sourav Chatterjee. Concentration of Haar measures, with an application to random matrices. *J. Funct. Anal.*, 245(2):379-389, 2007. doi:10.1016/j.jfa.2007.01.003. 20, 32, 101, 104, 108

[43] Sourav Chatterjee. Stein's method for concentration inequalities. *Probab. Theory Related Fields*, 138(1-2):305-321, 2007. doi:10.1007/s00440-006-0029-y. 20, 32, 97, 101, 104

[44] Sourav Chatterjee. A short survey of Stein's method, 2014. arXiv:1404.1392. 101

[45] Sourav Chatterjee and Persi Diaconis. Speeding up Markov chains with deterministic jumps. *Probab. Theory Related Fields*, 181(1-3):377-400, 2021. doi:10.1007/s00440-021-01049-1. 19, 30, 67, 69, 70, 71, 73, 119

[46] Sourav Chatterjee, Persi Diaconis, and Elizabeth Meckes. Exchangeable pairs and Poisson approximation. *Probability Surveys*, 2(none):64 – 106, 2005. doi:10.1214/154957805100000096. 101

[47] Fang Chen, László Lovász, and Igor Pak. Lifting markov chains to speed up mixing. In *Proceedings of the thirty-first annual ACM symposium on Theory of Computing*. ACM, may 1999. URL: https://doi.org/10.1145/2F301250.301315, doi:10.1145/301250.301315. 18, 30

[48] Guan-Yu Chen and Laurent Saloff-Coste. The cutoff phenomenon for ergodic markov processes. *Electronic Journal of Probability*, 13(3):26-78, 2008. doi:doi:10.1214/EJP.v13-474. 22, 33

[49] F. R. K. Chung, Persi Diaconis, and R. L. Graham. Random walks arising in random number generation. *Ann. Probab.*, 15(3):1148-1165, 1987. URL: https://www.jstor.org/stable/2244046. 19, 30, 67, 68, 69, 70, 72, 73, 78, 85, 88

[50] Guillaume Conchon-Kerjan. Cutoff for random lifts of weighted graphs. *The Annals of Probability*, 50(1):304 – 338, 2022. doi:10.1214/21-AOP1534. 119

[51] Alain Connes and EJ Woods. Hyperfinite von Neumann algebras and Poisson boundaries of time dependent random walks. *Pacific journal of mathematics*, 137(2):225-243, 1989. 39