# Cutoff for mixtures of permuted Markov chains:
reversible case

Bastien Dubail
KTH Correspondence to be sent to<EMAIL_ADDRESS>Stockholm  Sweden

###### Abstract

We investigate the mixing properties of a model of reversible Markov chains in
random environment, which notably contains the simple random walk on the
superposition of a deterministic graph and a second graph whose vertex set has
been permuted uniformly at random. It generalizes in particular a result of
Hermon, Sly and Sousi, who proved the cutoff phenomenon at entropic time for
the simple random walk on a graph with an added uniform matching. Under mild
assumptions on the base Markov chains, we prove that with high probability the
resulting chain exhibits the cutoff phenomenon at entropic time $\log n/h$,
$h$ being some constant related to the entropy of the chain. We note that the
results presented here are the consequence of a work conducted for a more
general model that does not assume reversibility, which will be the object of
a companion paper. Thus, most of our proofs do not actually require
reversibility, which constitutes an important technical contribution. Finally,
our argument relies on a novel concentration result for "low-degree" functions
on the symmetric group, established specifically for our purpose but which
could be of independent interest.

##  1 Models and main results

###  1.1 Cutoff for mixtures of reversible permuted Markov Chains

This paper establishes a cutoff phenomenon at entropic time for a model of
Markov chain in random environment. In the simplest case, think of two multi-
graphs, allowed to contain self-loops and multi-edges, which are
superpositioned one on top of the other. What can be said about the simple
random walk on the resulting graph ? Does it mix faster ? In general nothing
can be said, as the two graphs could be equal and give the same resulting
random walk. On the opposite, if the two graphs are not perfectly aligned but
rather superpositioned in a complementary way the random walk can be expected
to behave much differently. In this paper we consider a random version of this
process, where the vertices of the second graph are permuted uniformly at
random. This model is inspired by the work [39] of Hermon, Sousi and Sly, who
proved the cutoff phenomenon at entropic time for the simple random walk on a
sequence of deterministic graphs to which is added a random uniform matching
of the vertices or a configuration model. In this paper we consider a more
general model which goes in fact beyond the case of the simple random walk on
the superposition of graphs and considers mixtures of reversible Markov
chains. To define this model, we use the well-known theory of representing
reversible Markov chains by electrical networks.

First recall that a chain on state space $S$ with transition kernel $P$ is
reversible if there exists a measure $\pi$ on $S$ such that
$\pi(x)P(x,y)=\pi(y)P(y,x)$ for all $x,y\in S$. An electrical network is a
pair $(G,c)$ consisting in a weighted non-directed graph $G=(V,E)$ equipped
with non-negative weights $c=(c(e))_{e\in E}$, called conductances, on the
edges. Any reversible Markov chain can be represented as a random walk on an
electrical network, defining conductances as

$c(x,y):=\pi(x)P(x,y)$ (1)

which are symmetric by assumption. Conversely, any electrical network gives
rise to a reversible Markov chain whose transition probabilities are
proportional to conductances. We refer to [49] for a detailed account of this
theory. The particular case of the simple random walk on a multi-graph is
obtained by taking all conductances equal to $1$. For more general reversible
chains, the electrical network theory provides a natural and generic way to
mix together two reversible chains by superpositionning the corresponding
electrical networks, that is taking a linear positive combination of the
conductances.

Let us introduce some notation to state our main result. Given two measures
$\mu,\nu$ on a countable set $S$, their total variation distance is defined as

$\left\|\mu-\nu\right\|_{\mathrm{TV}}:=\sup_{A\subseteq
S}\left|\mu(A)-\nu(A)\right|=\frac{1}{2}\sum_{x\in
S}\left|\mu(x)-\nu(x)\right|.$

If $P$ is the transition kernel of a positive recurrent, irreducible and
aperiodic Markov chain on $S$, it admits a unique invariant measure $\pi$. In
that case, given a starting vertex $x\in S$ and $\varepsilon\in(0,1)$, the
mixing time is defined as

$t_{\mathrm{mix}}(x,\varepsilon):=\inf\\{t\geq
0:\left\|P^{t}(x,\cdot)-\pi\right\|_{\mathrm{TV}}<\varepsilon\\}.$

If the chain is not irreducible or aperiodic, we consider the mixing time to
be infinite. An event $A=A(n)$ is said to occur with high probability, if it
has limiting probability $1$ as $n\rightarrow\infty$. Given an integer $n\geq
1$, we write $[n]:=\\{1,\ldots n\\}$.

######  Theorem 1.1.

Let $n\geq 1$ be an integer, $\sigma$ a permutation of $n$ elements chosen
uniformly at random, $(G_{1},c_{1}),(G_{2},c_{2})$ two electrical networks
with common vertex set $[n]$ and $\alpha,\beta>0$. Then consider the Markov
chain on $[n]$ defined by the electrical network $(G^{\ast},c)$ with
conductances

$\forall
x,y\in[n]:c^{\ast}(x,y):=\alpha\,c_{1}(x,y)+\beta\,c_{2}(\sigma(x),\sigma(y)).$
(2)

Suppose

  1. (H1)

The degrees and conductances of $(G_{1},c_{1})$ and $(G_{2},c_{2})$ all
bounded uniformly in $n$, from above and below.

  2. (H2)

$\alpha,\beta$ are constants in $n$.

  3. (H3)

The connected components of $G_{1}$ have size at least $3$ and that of $G_{2}$
size at least $2$.

Then there exists $h=h(n)$ bounded from above and away from $0$ for which the
following holds. For all $\varepsilon\in(0,1)$, there exists a constant
$C(\varepsilon)$ such that with high probability,

$\displaystyle\min_{x\in[n]}t_{\mathrm{mix}}(x,1-\varepsilon)$
$\displaystyle\geq\frac{\log n}{h}-C(\varepsilon)\sqrt{\log n},$
$\displaystyle\max_{x\in[n]}t_{\mathrm{mix}}(x,\varepsilon)$
$\displaystyle\leq\frac{\log n}{h}+C(\varepsilon)\sqrt{\log n}.$

In particular, the chain is irreducible and aperiodic with high probability
and exhibits a uniform cutoff phenomenon: for all $\varepsilon\in(0,1)$

$\lim_{n\rightarrow\infty}\frac{\max_{x\in[n]}t_{\mathrm{mix}}(x,\varepsilon)}{\min_{x\in[x]}t_{\mathrm{mix}}(x,1-\varepsilon)}=1$

in probability.

######  Remark 1.1.

Being defined with conductances, the chain considered in the theorem is thus
automatically reversible. Letting $c_{1},c_{2}\equiv 1$ take the value $1$ on
every edge and setting $\alpha=\beta=1$ as well, we obtain the particular case
of the superposition of two multi-graphs. The case of a graph with an added
random matching analog to the case studied in [39] can then be obtained by
taking for $G_{2}$ a sequence of edges if $n$ is even. A little difference
lies however in the fact that the authors consider there simple graphs while
we consider multi-graphs, thus edges of $G_{1},G_{2}$ that align under the
permutation $\sigma$ would result in a transition with a higher probability.
To obtain rigourously the case of simple graphs, it would in theory be
necessary to adjust $\alpha,\beta$ to make them $1/2$ when edges of the two
networks are aligned. However a close inspection at the proof shows this makes
no difference (see Remark 3.4), so our result is also true when
superpositionning simple graphs and discarding multi-edges in the resulting
graph.

##### About reversibility

The previous theorem was obtained as the consequence of a work conducted for
more general chains than those considered here, that does not assume
reversibility. The general model is the following: let $P_{1},P_{2}$ bet two
$n\times n$ stochastic matrices, $p_{1},p_{2}:M_{n}([0,1])$ two $n\times n$
matrices with entries in $[0,1]$ satisfying $p_{1}+p_{2}\equiv 1$ and consider
the stochastic matrix

$\mathscr{P}(x,y):=p_{1}(x,\sigma(x))\,P_{1}(x,y)+p_{2}(x,\sigma(x))\,P_{2}(\sigma(x),\sigma(y)).$
(3)

The reversible model considered in this paper is a particular case of (3):
supposing $P_{1},P_{2}$ are reversible and correspond to electrical networks
$(G_{1},c_{1}),(G_{2},c_{2})$ respectively, $P_{i}(x,y)=c_{i}(x,y)/c_{i}(x)$
where $c_{i}(x):=\sum_{z\in V}c_{i}(x,z)$ for $i=1,2$. Hence the reversible
model is realized as (3) taking

$p_{1}(x,y):=\frac{\alpha c_{1}(x)}{\alpha c_{1}(x)+\beta c_{2}(y)}.$

The general model (3) is studied in the companion paper [30]. We chose here to
focus first on the reversible case as it simplifies several aspects of the
proof. Our proof adapts the strategy used for non-backtracking chains [8, 14,
15] to handle backtracking chains as well, including reversible ones, but
reversibility is by far not essential. Thus an important goal of this paper is
to provide a unified approach to prove cutoff for Markov chains in random
environment using the "entropic method", with or without reversibility.
Nevertheless, the absence of reversibility brings real additional difficulties
and incidentally makes the conclusion Theorem 1.1 false: for some choices of
$P,Q,p_{1},p_{2}$ the worst-case mixing time is of order $(\log n)^{a}$ with
$a>1$. What remains true however is that cutoff occurs at entropic time if the
chain is started from a typical state. This phenomenon is similar for instance
to the case of random walks on the giant component of Erdös-Renyi graphs: with
high probability these contain segments of length of order $\log n$, resulting
in the worst-case mixing time being of order $(\log n)^{2}$ [9, 34], while the
typical mixing time is $O(\log n)$ [10].

###  1.2 A concentration inequality for low-degree functions on the symmetric
group

A core argument in the proof is a concentration inequality for the uniform
measure on the symmetric group, which as far as we know is new and might be of
independent interest. It generalizes an inequality of Chatterjee [23, Prop.
1.1], which was already used in previous works about cutoff for non-
backtracking walks [8, 14]. The original inequality takes the form of a
Bernstein-like bound for random variables of the form

$Z=\sum_{i}A_{i\sigma(i)}$ (4)

where $A\in M_{n}(\mathbb{R}_{+})$ and $\sigma$ is a uniform permutation of
$n$ elements. Namely, for all $t\geq 0$

$\mathbb{P}\left[\left|Z-\mathbb{E}\left[Z\right]\right|\geq t\right]\leq
2\exp\left(\frac{-t^{2}}{2\left\|A\right\|(t+2\mathbb{E}\left[X\right])}\right),$
(5)

where $\left\|A\right\|=\max_{i,j\in[n]}A_{i,j}$. The random variable $Z$ can
be seen as arising from a linear function on the symmetric group, in the sense
that it is a linear combination of indicators $\mathbbm{1}_{\sigma(i)=j}$,
which are the entries of the matrix representation of $\sigma$. With this
point of view, it seems natural to inquire about more general polynomial
functions. Of course any function on the symmetric group can be represented as
a polynomial of degree $n$ and in fact $n-1$. Furthermore there already exist
concentration results for generic functions on the symmetric group, regardless
of the degree: Maurey’s inequality [50] (see also Thm. 2.14 in [21]),
Talagrand’s inequality [57][Thm 5.1], and Proposition 4.8 in [21] are such
examples. Our motivation is thus mainly to investigate whether an additional
assumption of "low degree" can yield better concentration inequalities.

Some notations are necessary to state our result. Let $\mathfrak{S}_{n}$
denote the symmetric group on $n$ elements. Permutations
$\sigma\in\mathfrak{S}_{n}$ are identified with permutation matrices $S$
defined by $S_{ij}:=\mathbbm{1}_{\sigma(i)=j}$. Let us remark first that there
is no unique representation of a function on $\mathfrak{S}_{n}$ as a
polynomial. In the following result, particular representations are
considered, but some more intrinsic notion of degrees will be discussed in
Remark 1.4. We can without loss of generality suppose that the constant term
is zero. Furthermore, since we are restricting to permutation matrices it is
enough to consider the set of functions

$\mathfrak{F}:=\left\\{\phi:M_{n}(\mathbb{R})\rightarrow\mathbb{R}\ |\ \forall
i,j,k\in[n]:\partial_{ij}\partial_{ik}\,\phi\equiv\partial_{ji}\partial_{ki}\,\phi\equiv
0\right\\},$ (6)

where $\partial_{ij}$ denotes the partial derivative with respect to the entry
$(i,j)$. Functions of $\mathfrak{F}$ are called multilinear, as the degree is
at most one in each entry. In particular, these are polynomial functions on
$M_{n}(\mathbb{R})$, which we identify with polynomials in indeterminates
$X_{ij},i,j\in[n]$. By restriction to the set of permutations, each function
$\phi\in\mathfrak{F}$ induces a map on $\mathfrak{S}_{n}$. Conversely, any map
on $\mathfrak{S}_{n}$ can be written as $\phi_{|\mathfrak{S}_{n}}$ for some
$\phi\in\mathfrak{F}$ of degree at most $n-1$, however this representation is
in general not unique.

The vector space $\mathfrak{F}$ can be decomposed as

$\mathfrak{F}=\bigoplus_{d\geq 0}\mathfrak{F}_{=d}$

where for each $d\geq 0$, $\mathfrak{F}_{=d}$ is the vector space of
homogeneous polynomials of degree $d$. Let
$\mathfrak{F}_{d}=\bigoplus_{k=0}^{d}\mathfrak{F}_{=k}$ be the vector space of
polynomials of degree at most $d$. If $d\geq 1$, a convenient way to write
$\phi\in\mathfrak{F}_{=d}$ is given by Euler’s theorem:

$\displaystyle\phi(X)$
$\displaystyle=\frac{1}{d}\sum_{i,j\in[n]}X_{ij}\partial_{ij}\phi(X).$

In particular, evaluating $\phi$ at $\sigma\in\mathfrak{S}_{n}$ yields

$\phi(\sigma)=\frac{1}{d}\sum_{i,j\in[n]}\partial_{i,\sigma(i)}\phi(\sigma),$
(7)

which can be seen as a generalization of (4). To state our result, we need the
following linear operators on $\mathfrak{F}$. Given an homogeneous function
$\phi\in\mathfrak{F}_{=d}$, let

$D\phi:=\frac{1}{dn}\sum_{i,j\in[n]}\partial_{ij}\phi\qquad
U\phi(X):=\frac{1}{dn}\sum_{i,j,k,l\in[n]}X_{il}X_{kj}\partial_{ij}\partial_{kl}\phi(X).$

Finally, for a function $\phi\in\mathfrak{F}$, let

$\left\|\phi\right\|_{\infty}:=\max_{\sigma\in\mathfrak{S}_{n}}\left|\phi(\sigma)\right|,\qquad\left\|\nabla\phi\right\|_{\infty}:=\max_{\sigma\in\mathfrak{S}_{n}}\max_{i,j\in[n]}\left|\partial_{ij}\phi(\sigma)\right|.$

In this context, we write
$\mathbb{E}\left[\phi\right]:=\mathbb{E}\left[\phi(\sigma)\right]$ for the
expectation with respect to a uniformly distributed
$\sigma\in\mathfrak{S}_{n}$.

######  Theorem 1.2.

Let $n\geq 1$, $d\in[n]$, $\sigma$ a uniform permutation of $n$ elements and
$\phi\in\mathfrak{F}_{d}$ a polynomial map of degree $d$ with non-negative
coefficients. Suppose there exist $C_{D},C^{\prime}_{D},C_{U}\geq 0$ such that
for all $k\in[0,d]$,

$\left\|D^{k}\phi\right\|_{\infty}\leq C_{D},\quad\left\|\nabla
D^{k}\phi\right\|_{\infty}\leq
C^{\prime}_{D}\quad\text{and}\quad\left\|D^{k}U\phi\right\|_{\infty}\leq
C_{U}.$ (8)

Then for all $t\geq 0$,

$\mathbb{P}\left[\phi(\sigma)-\mathbb{E}\left[\phi\right]\geq
t\right]\leq\exp\left(\frac{-t^{2}}{2(\gamma_{\phi}+\beta_{\phi}t)}\right),\quad\text{and}\quad\mathbb{P}\left[\phi(\sigma)-\mathbb{E}\left[\phi\right]\leq-t\right]\leq\exp\left(\frac{-t^{2}}{2\gamma_{\phi}}\right)$

where

$\begin{split}&\beta_{\phi}:=6dC^{\prime}_{D}\left(\log\left(\frac{4C_{D}n}{C^{\prime}_{D}}\right)^{+}+\frac{(2/n)(2-e^{-2/n})}{1-e^{-2/n}}\right)\\\
&\gamma_{\phi}:=\frac{2\beta_{\phi}}{3}\left(2\mathbb{E}\left[\phi\right]+C_{U}\right)\end{split}$

######  Remark 1.2.

If $\phi(X)=\sum_{i,j}A_{i,j}X_{i,j}$, then $\nabla\phi\equiv A^{\top}$.
Therefore, the condition required on $\left\|\nabla\phi\right\|_{\infty}$
generalizes the control needed on $\left\|A\right\|$ in (5). Up to the
logarithmic term and multiplicative constants, Theorem 1.2 thus really aims to
generalize Chatterjee’s inequality to higher degrees.

######  Remark 1.3.

As was mentionned earlier, the finiteness of $\mathfrak{S}_{n}$ implies that
any function can in fact be seen as a polynomial function of degree at most
$n-1$, so Theorem 1.2 provides in theory a concentration inequality for any
non-negative random variable defined by a uniform permutation. It is likely
however that this bound becomes irrelevant when $d/n\nrightarrow 0$. In this
paper, Theorem 1.2 will be applied with $d=O(\sqrt{\log n})$.

######  Remark 1.4.

There are intrinsic notions of degree for functions on $\mathfrak{S}_{n}$. A
natural notion of degree is as follows: given $k\geq 1$, a $k$-coset of
$\mathfrak{S}_{n}$ is a subset of the form

$E_{\begin{subarray}{c}i_{1}\cdots i_{k}\\\ j_{1}\cdots
j_{k}\end{subarray}}:=\\{\sigma\in\mathfrak{S}_{n}\ |\ \forall
m=1,\ldots,k\quad\sigma(i_{m})=j_{m}\\}.$

where $\mathbf{i}=(i_{1},\dots,i_{k})$,
$\mathbf{j}=(j_{1},\ldots,j_{k})\in[n]^{k}$ are multi-indices of length $k$.
If $k=0$, we consider the whole set $\mathfrak{S}_{n}$ to be a $0$-coset.
Given a function $f:\mathfrak{S}_{n}\rightarrow\mathbb{R}$, the degree of $f$
can be defined as the least integer $d\geq 0$ such that $f$ writes as a linear
combination of $k$-coset indicator functions with $k\leq d$. With this
definition the degree of $f$ is the minimal degree of a polynomial
representation of $\phi$.

The previous notion of degree is also intimately related to Fourier analysis:
from [32][Thm. 7], it coincides with the _Fourier degree_ of $f$, which is the
least integer $d\geq 0$ such that all Fourier coefficients of $f$
corresponding to irreducible representations of dimension $k>d$ are zero. We
do not know whether the considerations of these notions of degree could lead
to better concentration inequalities. The use of Fourier analysis, in
particular character theory could definitely be of help at some point in the
proof but other arguments seem to require more than the sole use of the
characters. See Remark 9.1.

The presence of the operators $D$ and $U$ is a consequence of the proof. It
follows the method of exchangeable pairs used by Chatterjee in the one-
dimensional case to bound the log-Laplace transform, which can be done in
terms of the functions $D^{k}\phi,UD^{k}\phi$. In the degree one case, these
operators are trivial and thus need not be considered, but in the more general
case an induction argument on the degree seems necessary, which is the reason
why one needs to bound $\left\|D^{k}\phi\right\|_{\infty},\left\|\nabla
D^{k}\phi\right\|_{\infty},\left\|D^{k}U\phi\right\|_{\infty}$ for all $k\leq
d$. These quantities seem to lack good monotonicity properties that could
simplify the bounds. However if we can control the coefficients of the
polynomial directly as well as the number of monomials that do not evaluate to
zero, the following proposition provides some control on the constants
$C_{D},C^{\prime}_{D},C_{U}$. These are rough bounds but can be sufficient for
small degree functions, which is how the theorem is intended to be used.

######  Proposition 1.1.

Let $\phi$ be a polynomial in the indeterminates $(X_{ij})_{i,j=1}^{n}$ of
degree $d\geq 1$. Let $M(\phi)$ be the maximal coefficient of $\phi$. Given
$\sigma\in\mathfrak{S}_{n}$ let $N(\phi,\sigma)$ be the number of monomials in
$\phi$ which are non-zero when evaluated at $\sigma$ and
$N(\phi):=\max_{\sigma\in\mathfrak{S}_{n}}N(\phi,\sigma)$. For all $k\geq 0$

$\left\|D^{k}\phi\right\|_{\infty}\leq
2^{k}M(\phi)N(\phi),\qquad\left\|U\phi\right\|_{\infty}\leq\frac{d-1}{n}\,M(\phi)N(\phi).$

Plugging the previous estimates into Theorem 1.2 yields the following
corollary.

######  Corollary 1.1.

Let $\phi\in\mathfrak{F}_{d}$ be a polynomial function of degree at most
$d\geq 1$. Using the notations of the previous proposition, let
$A_{\phi}:=M(\phi)N(\phi)$ and
$A_{\nabla\phi}:=\max_{i,j\in[n]}A_{\partial_{ij}\phi}$. For all $t\geq 0$,

$\mathbb{P}\left[\left|\phi(\sigma)-\mathbb{E}\left[\phi\right]\right|\geq
t\right]\leq
2\exp\left(\frac{-t^{2}}{2\alpha_{\phi}(\frac{4}{3}\mathbb{E}\left[\phi\right]+\frac{2^{d+1}(d-1)}{3n}A_{\phi}+t)}\right).$

with

$\alpha_{\phi}:=6\,d\,2^{d}A_{\nabla\phi}\left(\log\left(\frac{4A_{\phi}\,n}{A_{\nabla\phi}}\right)^{+}+\frac{(2/n)(2-e^{-2/n})}{1-e^{-2/n}}\right)$

###  1.3 Related works

Discovered by Diaconis, Shahshahani and Aldous [29, 1, 2], the cutoff
phenomenon is a famous feature observed in a large number of Markov chains.
Not all Markov chains exhibit cutoff and it remains an open question to
determine a characterization of this intriguing phenomenon. To this date, the
sufficient condition given by Salez in [53] is certainly the closest result
one has ever been from a full characterization. This sufficient condition
expresses an entropic concentration phenomenon, which has been at the heart of
many important achievements on cutoff over the last decade. While the initial
focus was on specific, explicit Markov chains with high degrees of symmetry,
like random walks on groups (see [28, 54] for global references on the
subject), the seminal work of Lubetzky and Sly [47] on random walks on random
regular graphs initiated a series of papers studying instead generic Markov
chains. In that regard, a lot of attention was drawn on Markov chains in
random environment, which showed that cutoff is actually quite common and
often the result of an entropic concentration phenomenon, leading to an
_entropic mixing time_ $\log n/h$, where $n$ is the size of the state space
and $h$ can be interpreted as a entropy rate.

After Lubetzky and Sly proved the cutoff for simple and non-backtracking
random walks on random regular graphs, Ben Hamou and Salez proved the cutoff
for the non-backtracking walk on random graphs with a given degree sequence,
ie the configuration model [8]. This case is also considered in [10], in which
Berestycki, Lyons, Peres and Sly prove the cutoff, for both the simple and
non-backtracking walks on the giant component of an Erdös Renyi random graph
as well as for the configuration model. In the case of the simple random walk,
the starting point is not uniform but needs to be typical. For Erdös Renyi
random graphs, the worst-case mixing time had been established to be $O((\log
n)^{2})$ by Fountoulakis and Reed [34] and Benjamini, Kosma and Wormald [9],
while in the configuration model cutoff was obtained subsequently by Ben
Hamou, Lubetzky and Peres in [6]. Models of random non-backtracking chains
have also been considered by Bordenave, Caputo and Salez: [14] considers the
non-backtracking walk on directed configuration models, while [15] considers
the case of a stochastic matrix in which the entries of each row are permuted
uniformly at random. In [27], Conchon-Kerjan considers random walks on random
lifts of weighted graphs which are not reversible. Let us also mention the
work of Hermon and Olesker-Taylor [37, 38] on random walks on random Cayley
graphs of Abelian groups. A model similar to ours is the $PS$ model,
introduced by Chatterjee and Diaconis [25] and shown to exhibit cutoff at
entropic time by Ben Hamou and Peres [7].

Some recent works investigate the case of random graphs with community
structures: in [5], Ben Hamou proves a phase transition for the cutoff of the
non-backtracking random walk on a random graph with two communities. A
extension of this result for the simple random walk was obtained by Hermon,
Šarković and Sousi [40] who also consider a second model of random graphs
allowing more communities.

While the previously cited works consider the case of an essentially totally
random Markov chains, cutoff was also shown to occur when randomizing a given
chain, where the final environment still keeps a lot of the structure of the
initial chain. We already cited the work of Hermon, Sly and Sousi [39] as the
main inspiration of this work, where cutoff is proved for the simple random
walk on a graph to which is added a uniform matching. This model was extended
by Baran, Hermon, Šarković and Sousi [4] who prove a phase transition when
weights are added on the random matching.

Another direction of recent works is the competition between different
mechanisms such as having a dynamic environment: see the papers by Avena,
Güldaş, van der Hofstad and den Hollander [3] and Caputo and Quattropani [20].
A related work is [19] by Caputo and Quattropani on PageRank random walks on
random digraphs.

Let us mention that cutoff at entropic phenomenon is not bound to random
Markov chains: it can also arise in deterministic settings, such as Ramanujan
graphs [46, 51] or environments with a Ramanujan property [16]. In fact from
the work of Friedman [36] (see also [13]) it is known that that random regular
graphs are Ramanujan with high probability, so the above results can be
interpreted as cutoff phenomena in pseudo-deterministic settings. The paper by
Eberhard and Varjù [31] falls in that category, which can also be interpreted
as a deterministic realization of the $PS$ model studied in [7]. Finally, the
sufficient condition of Salez [53] allows him to deduce cutoff for a large
family of chains satisfying a non-negative curvature criterion, not
necessarily random.

When it comes to the concentration result, random variables of the form (4)
were introduced in the "combinatorial central limit theorem" by Hoeffding
[41]. Since then, they have been one of the main motivations for the
developments of Stein’s method, which is at the basis of the concentration
inequality (5) and our result. Early applications of Stein’s method for such
random variables are found in the works of Bolthausen and Goetze [11, 12] who
obtained error bounds on the normal approximation.

Introduced by Stein in [55] to give a new proof of the classical CLT, Stein’s
method of exchangeable pairs rapidly became an important tool to prove limit
theorems that go way beyond the setting of the CLT, we refer to Stein’s paper
[56] and to the survey [24] of Chatterjee and [26] of Chatterjee, Diaconis and
Meckes which focuses more closely on the subject of Poisson approximation. The
first concentration inequalities using Stein’s method are due to Chatterjee in
his PhD Thesis [21], see also [23]. The inequality (5) can also be interpreted
as the concentration of the uniform measure on the symmetric group. Generally,
the subject of concentration for the Haar measure is considered by Chatterjee
in [22], where he establishes a connection between concentration and the rate
of convergence of some random walks on groups.

###  1.4 Proof outline

##### Knowledge of the invariant measure:

as our model is reversible, the electrical network analogy provides an
expression for the invariant measure. Indeed we can infer from (1) that

$\pi(x)=\frac{c^{\ast}(x)}{\sum_{y,z\in[n]}c^{\ast}(y,z)}=\frac{\sum_{z\in[n]}c^{\ast}(x,z)}{\sum_{y,z\in[n]}c^{\ast}(y,z)}$

is an invariant probability measure. From the boundedness Assumptions (H1),
(H2) we immediately see this implies $\pi(x)=\Theta(1/n)$ for all $x\in[n]$.
In general, this knowledge about the invariant measure is sufficient to make a
lot of arguments much simpler. We will for instance use it in the proof of the
lower bound of Theorem 1.1. However as mentionned after Theorem 1.1, most of
our arguments do not require reversibility and thus will not use this
knowledge about the invariant measure. Instead, we follow the strategy used in
[14, 15] of proving convergence towards an approximate invariant measure
$\hat{\pi}$. Letting $\mathscr{P}$ be the transition matrix of the chain
studied, if
$\left\|\mathscr{P}^{t}(x,\cdot)-\hat{\pi}\right\|_{\mathrm{TV}}\leq\varepsilon$
holds uniformly in $x$ for a given time $t$, then the invariance property
implies that a true invariant measure $\pi$ satisfies automatically
$\left\|\pi-\hat{\pi}\right\|_{\mathrm{TV}}\leq\varepsilon$, establishing in
particular the uniqueness of the invariant measure.

##### The entropic method:

the entropic method has become over the last years quite a standard technique
to prove cutoff, proof being that it is common to almost all previous works on
cutoff for randomized Markov chains cited above. It is essentially made of two
arguments: first an entropic concentration is shown to occur at the entropic
time $\log n/h$, which is shown to imply cutoff in the second part of the
proof. These arguments come with different variations, depending on whether
reversibility is supposed or not. We follow the approach originally designed
for non-backtracking random walks [8, 14, 15], which can be thought of as the
complete opposite of reversiblity. A main contribution of this paper is thus
to extend this approach to backtracking chains as well, including reversible
chains. First we prove a quenched entropic concentration property for
trajectories, namely we prove a statement of the form $\mathscr{P}(X_{0}\cdots
X_{t})\simeq e^{-th+O(\sqrt{t})}$, where we write $\mathscr{P}(X_{0}\cdots
X_{t})=\prod_{i=0}^{t-1}\mathscr{P}(X_{i},X_{i+1})$. This statement is given
here as a rough heuristic, which would be correct in the non-backtracking
case. In general, what we prove in practice is rather concentration of the
probability to follow the _loop-erased trace_ of $X$, so we are back at
studying non-backtracking trajectories. This concentration phenomenon is
proved by a coupling with another Markov chain lying on an infinite random
state space. We call this environment a quasi-tree in reference to [39], as
this object is similar to theirs. Basically, it is designed to be a stationary
approximation of the universal cover of the finite chain, in the same way
Erdös-Renyi random graphs can be approximated by infinite Galton-Watson trees.

##### Analysis on the quasi-tree:

this part is essentially the only one where reversibility comes into play. In
the reversible case, a comparison argument will show that conditional on the
environment, from any vertex, the probability to escape to infinity along the
neighbouring "branch" of the quasi-tree is lower bounded by a constant. This
may not be true in the general model (3). Once this is proved, the rest of
analysis can be conducted pretty much as is done in [39, 40, 4].

The proof of the entropic concentration notably relies on the use of
_regeneration times_ , which are times where the chain in the quasi-tree makes
a transition for the first and last time. In fact, the use of these times goes
beyond the entropic concentration phenomenon, so we will spend some time
studying the regeneration process. In particular, as in [40], our model
requires the consideration of an underlying Markov chain. We thought useful to
introduce the setting of Markov renewal processes to formalize these arguments
in a a generic way. An important requirement for the proof is the fast mixing
of the Markov chain underyling the regeneration process. In our case, the law
of the environment presents enough independence so that the regeneration chain
satisfies Doeblin’s condition, which implies the mixing time is $O(1)$.

##### Argument for the lower bound:

the lower bound in the mixing time is based on a simple coverage argument.
From the concentration of entropy, at time $t=O(\log n)$ the chain is
necessarily confined is a set of size $e^{th+O(\sqrt{t})}$ at most. This
becomes $o(n)$ for $t\leq\log n/h-C\sqrt{\log n}$ and a large constant $C>0$,
which is sufficient to conclude using that the invariant measure satisfies
$\pi(x)=\Theta(1/n)$.

##### Concentration of nice trajectories:

the second part of the argument uses the entropic concentration to show a
second concentration phenomenon. Specifically, for all $x,y\in V$, we define a
set $\mathfrak{N}^{t}(x,y)$ of "nice" trajectories between $x,y$, of length
$t$, which will have the property that: 1. they are typical, that is the
trajectory of the chain is likely to be nice, 2. the probability
$\mathscr{P}^{t}_{\mathfrak{N}}(x,y)$ of following a nice trajectory
concentrates around its mean, which is shown to be independent of the starting
point. From these properties we deduce that $\mathscr{P}^{t}(x,\cdot)$ mixes
towards a proxy stationary distribution $\hat{\pi}$.

Nice paths are basically defined by splitting a path in three components
$\mathfrak{p}_{1},\mathfrak{p}_{2},\mathfrak{p}_{3}$ and restricting
$\mathfrak{p}_{1},\mathfrak{p}_{3}$ to be contained in a nice quasi-tree-like
neighbourhood around $x$ and $y$ respectively. Thanks to the entropic
concentration, paths can be restricted to have probability
$e^{-th+O(\sqrt{t})}$, which allows to use the concentration result of Theorem
1.2 conditional on the two neighbourhoods. The notable difference with the
case of non-backtracking chains [8, 14, 15] comes from the path
$\mathfrak{p}_{2}$. In the case of non-backtracking chains, it merely
consisted in one edge so only the concentration for degree $1$ functions was
needed. When backtracking is allowed, trajectories could bounce back and forth
between the two neighbourhoods, so taking just one edge is not sufficient. Our
strategy is here to reduce as much as possible the setting to the non-
backtracking case. To that end, we can use concentration of the speed (or
drift), which is proved in the same time as for the entropy: the distance
traveled by the chain at time $t$ is shown to be $\mathscr{d}t+O(\sqrt{t})$.
On the other hand, using the lower bound on escape probabilities, we can argue
that the chain is unlikely to backtrack over more than $L=\Theta(\log\log n)$
steps on a time scale $t=O(\log n)$. Thus by allowing the distance between the
two neighbourhoods to be of order $\sqrt{t}$, we can ensure the chain does not
backtrack from one neighbourhood to the other and discard trajectories which
have intermediate length much smaller or much larger than $\sqrt{t}$. In the
end, the estimate on the traveled distance leads us to consider neighbourhoods
of variable size, with a variable distance between them, but with bounded
windows on these parameters. Concentration is thus proved using Theorem 1.2
for fixed parameters and extended by union bound. When realized as a
multilinear function, the probability to follow a nice path between $x$ and
$y$ will have degree the length of the path $\mathfrak{p}_{2}$ between the two
neighbourhoods. Since this is $O(\sqrt{t})=O(\sqrt{\log n})$, the exponential
factors in Corollary 1.1 remain sufficiently small to obtain exponential
concentration bounds.

##### Computation of $\hat{\pi}$:

the last difficulty is to compute the expectation precisely enough to get the
probability measure $\hat{\pi}$. To that end, we use regeneration times for
the finite chain, essentially defined to be times at which the chain makes a
transition and does not backtrack before it has traveled distance
$L=\Theta(\log\log n)$. From the non-backtracking property mentionned above,
this essentially amounts to consider transitions which are made only once on
the time scale $t=O(\log n)$. Furthermore, such regeneration times can of
course be coupled with those defined in the quasi-tree setting. From this, we
can use the mixing results proved for the regeneration chain in the quasi-tree
to deduce similar mixing properties in the finite setting, which yields the
expression of the limiting measure $\hat{\pi}$ (Proposition 3.2).

###  1.5 Organisation of the paper

In Section 2 we give material that will be used throughout the paper,
including the definition of quasi-trees. In Section 3, we give in detail the
main technical arguments of the paper that sum up the arguments of the
entropic method, from which we will be able to deduce Theorem 1.1. The three
next sections deal with the analysis of the quasi-tree: Section 4 establish
the lower bound on escape probabilities, Section 5 proves the main results
about the regeneration structure while Section 6 basically establishes "nice
properties" in the quasi-tree setting, including in particular the
concentration of the speed and entropy. These nice properties are then
transferred back to the finite setting in Section 7, to be used in Section 8
where nice paths are properly defined and shown to have their probability
concentrate around the mean. Finally Section 9 proves the concentration
result, Theorem 1.2, and is independent of the rest of the paper.

##  2 First moment argument, quasi-trees

##### Basic notations:

throughout the paper, all quantities involved may have an implicit dependency
in $n$ and the term constant will refer to quantities that are independent of
$n$ and of the randomness. Given a set $S$, $\left|S\right|$ denotes its
cardinality, $\mathbbm{1}_{S}$ is the indicator of $S$. Given
$x,y\in\mathbb{R}$, we write $x\wedge y:=\min(x,y)$, $x\vee y:=\max(x,y)$. We
use the standard Landau notations $o,O$ for deterministic sequences:
$f(n)=O(g(n))$ if there exists a constant $C>0$ such that
$\left|f(n)\right|\leq Cg(n)$ for all $n$, $f=o(g)$ if
$f(n)/g(n)\xrightarrow[n\rightarrow\infty]{}0$. We may write
$O_{\varepsilon}(\cdot)$ to precise a potential dependence of the implicit
constant in $\varepsilon$. We also write $f=\Theta(g)$ if $f=O(g)$ and
$g=O(f)$, and $f\gg g$ if $g=o(f)$. When it comes to randomness, all the
random variables considered in this paper are defined on an implicit
probability space with measure $\mathbb{P}$. If $Y_{n},Z_{n},Z$ are random
variables, we write $Z_{n}\xrightarrow[]{\mathbb{P}}Z$ for convergence in
probability and $Z_{n}=o_{\mathbb{P}}(Y_{n})$ if
$Z_{n}/Y_{n}\xrightarrow[]{\mathbb{P}}0$. In particular
$Z_{n}=o_{\mathbb{P}}(1)$ if $Z_{n}\xrightarrow[]{\mathbb{P}}0$. An event
$A=A(n)$ is said to occur with high probability, if its probability is
$1-o(1)$.

###  2.1 Quenched vs annealed probability, first moment argument

Consider $(X_{t})_{t\geq 0}$ a Markov chain in random environment, ie with
random transition probabilities, such as the one defined by (2). There are two
laws naturally associated with the process $(X_{t})_{t\geq 0}$. The
probability $\mathbb{P}$, which averages over both the random walk and the
environment, gives rise to the _annealed_ law of the process $(X_{t})_{t\geq
0}$ under which it is not a Markov chain. It is however a Markov chain under
the _quenched_ law, which conditions on the environment. To emphasize the
distinction, it is written using a different font, namely $\mathbf{P}$ will
denote the quenched distribution. For all state $x$, we write
$\mathbb{P}_{x}:=\mathbb{P}\left[\left.\cdot\ \right|\
X_{0}=x\right],\mathbf{P}_{x}:=\mathbf{P}\left[\left.\cdot\ \right|\
X_{0}:=x\right]$. Of course taking the expectation of the quenched law gives
back the annealed law. This is the basis of the following first moment
argument that will be used used throughout the article, whose phrasing is
taken from [15]. To prove a trajectorial event $A$ has quenched probability
vanishing to $0$ in probability as $n\rightarrow\infty$, it suffices to prove
$A$ has annealed vanishing probability, as Markov’s inequality implies for all
$\varepsilon>0$,

$\mathbb{P}\left[\mathbf{P}\left[A\right]\geq\varepsilon\right]\leq\frac{\mathbb{P}\left[A\right]}{\varepsilon}.$
(9)

In most of this paper we will first prove statements valid for fixed starting
states, chosen independently of the environment, such as
$\mathbb{P}_{x}\left[A\right]=o(1)$, to obtain
$\mathbf{P}_{x}\left[A\right]=o_{\mathbb{P}}(1)$. These can be interpreted as
conditional statements for the case where the starting state is also random,
with a law which is independent of the environment. Results for fixed starting
states thus extend automatically to _typical states_ , for instance taken
uniformly at random in the case the state space is $[n]$. To obtain stronger
results valid for all states simultaneously, union bound shows it suffices to
improve the annealed error bounds to $\mathbb{P}_{x}\left[A\right]=o(1/n)$.
This strategy will be used in Section 7 to extend results from typical to all
vertices.

###  2.2 The two-lift chain and half-integer time steps

We start by rewriting the model (2) further, which lacks symmetry in the roles
of the two electrical networks $(G_{1},c_{1}),(G_{2},c_{2})$. To obtain a
model that is more symmetric, we can construct the chain as a projection of
its two-lift: this consists in seeing $G_{1},G_{2}$ as two disjoint components
of one electrical network on a twice larger state space, which can be
projected back to obtain the original model. This is essentially a matter of
unifying notation and recover a setting which is somewhat similar to that of
[39], but it can also prove useful on its own. All in all, the model we will
work with in this paper is the following.

Let $V:=[2n],V_{1}:=[n],V_{2}:=[n+1,2n]$. Let $\sigma$ be now a uniform
bijection from $V_{1}$ to $V_{2}$, which can be extended as a matching, or
involution, $\eta$ on $V$ by

$\eta_{|V_{1}}:=\sigma,\qquad\eta_{|V_{2}}:=\sigma^{-1}.$

This matching defines an equivalence relation, namely $x\sim\eta(x)$. For all
$x\in V$, define $V(x)=V_{1}\ \mathbbm{1}_{x\in V_{1}}+V_{2}\
\mathbbm{1}_{x\in V_{2}}$. Consider $(G,c)$ to be an electrical network with
two disjoint components $V_{1},V_{2}$, which can themselves have several
connected components. We can consider conductances to be defined on all pairs
of $V\times V$, but equal to $0$ on edges not present in $G$, and we recall
$c(x):=\sum_{y}c(x,y)$. Let $\alpha,\beta>0$ be two constants and
$\gamma:V^{2}\rightarrow(0,\infty)$ be a map such that $\gamma_{|V_{1}\times
V_{2}}\equiv\alpha,\gamma_{|V_{2}\times V_{1}}\equiv\beta$. Since we will
rarely resort to the reversibility of the chains considered, we use most of
the time the notations of the general model (3): for all $x,y\in V$ let
$P(x,y):=c(x,y)/c(x)$ be the transition matrix of the chain corresponding to
the conductances $c$, and

$p(x,u):=\frac{\gamma(x,u)c(x)}{\gamma(x,u)c(x)+\gamma(u,x)c(u)},\quad
q(x,u):=1-p(x,u)$

for all $x,u\in V$. Notice that by construction $q(x,u)=p(u,x)$ for all
$x,u\in V$. Then consider the Markov chain on $V$ defined by the transition
probabilities

$\forall x,y\in V:\mathscr{P}(x,y):=\left\\{\begin{array}[]{l
l}p(x,\eta(x))\,P(x,y)&\text{if $i(x)=i(y)$}\\\
q(x,\eta(x))\,P(\eta(x),y)&\text{if $i(x)\neq i(y)$}.\\\ \end{array}\right.$

We will work with this Markov chain most of the time, which may not be
reversible, however the main object of interest of this paper is rather its
projection to the quotient $V/\sim\ =[n]$. As can be checked, the fact that
$q(x,u)=p(u,x)$ implies that
$\mathscr{P}(x,y)+\mathscr{P}(x,\eta(y))=\mathscr{P}(\eta(x),y)+\mathscr{P}(\eta(y),\eta(y))$.
This condition ensures the projection is itself a Markov chain, with
transition matrix given by

$\displaystyle\forall x,y\in[n],\bar{\mathscr{P}}(x,y)$
$\displaystyle:=\mathscr{P}(x,y)+\mathscr{P}(x,\eta(y))$
$\displaystyle=p(x,\eta(x))P(x,y)+q(x,\eta(x))P(\eta(x),\eta(y)).$

By construction $\bar{\mathscr{P}}$ is reversible, corresponding to the
conductances

$\bar{c}(x,y):=\alpha c(x,y)+\beta c(\eta(x),\eta(y))$

The original chain (2) is recovered if one sets
$c:=c_{1}\mathbbm{1}_{V_{1}\times V_{1}}+c_{2}\mathbbm{1}_{V_{2}\times
V_{2}}$, identifying $V_{2}$ with $[n]$ through $x\mapsto x-n$.

Given a probability measure $\mu$ on $V$, its projection $\bar{\mu}$ on $[n]$
is defined by $\bar{\mu}(x)=\mu(x)+\mu(\eta(x))$ for all $x\in[n]$. Notice
that if $\pi$ is invariant for $\mathscr{P}$, then $\bar{\pi}$ is invariant
for $\bar{\mathscr{P}}$. Furthermore, total variation distance is non-
increasing under projections, so

$\left\|\bar{\mathscr{P}}^{t}(x,\cdot)-\bar{\pi}\right\|_{\mathrm{TV}}\leq\left\|\mathscr{P}^{t}(x,\cdot)-\pi\right\|_{\mathrm{TV}}.$
(10)

Therefore to obtain the upper bound in Theorem 1.1, which is the most
difficult part of the argument, it suffices to prove an upper bound for the
two-lift. In fact, our arguments show both chains exhibit cutoff at entropic
time.

Now let us introduce another characteristic of the two-lift. The two-lift is
by construction made of two disjoint subspaces $V_{1},V_{2}$: when at $x$ the
Markov chain stays in the same subspace with probability $p(x,\eta(x))$, and
change with probability $q(x,\eta(x))$, after which it takes a step
independent of $\eta$. Because of this, it may be convenient to actually
distinguish between these two steps, adding transitions at half integer times,
defining transition probabilities

$\begin{array}[]{l l}\mathbf{P}\left[X_{t+1/2}=y\ |\
X_{t}=x\right]=\left\\{\begin{array}[]{l l}p(x,\eta(x))&\text{if $y=x$}\\\
q(x,\eta(x))&\text{if $y=\eta(x)$}\\\
0&\text{otherwise}\end{array}\right.&\text{for $t=0\mod\mathbb{Z}$}\\\
\mathbf{P}\left[X_{t+1}=y\ |\ X_{t+1/2}=x\right]=P(x,y)&\text{for
$t=1/2\mod\mathbb{Z}$.}\end{array}$ (11)

As is easily checked, the Markov chain $(X_{t})_{t\in\mathbb{N}}$ evaluated at
integer times exactly has the transition matrix $\mathscr{P}$.

##### Small-range vs long-range:

From now on let $G$ denote the deterministic graph underlying the electrical
network of the chain $P$ and let $G^{\ast}$ be the graph obtained after adding
the edges $(x,\eta(x))$ of the random matching. Using the terminology
introduced in [39], call the latter _long-range_ edges. By opposition, the
deterministic edges of $G$ are called _small-range_. If one takes the half-
integer time steps above into account, the random graph $G^{\ast}$ exactly
supports the Markov chain $X$, whereas if one considers only integer time
steps the chain moves along a long-range and a small-range edge at once or
along a small-range edge only. We will consider different metrics on these
graphs defined in terms of Markov kernels. To start with, we consider the
$\mathscr{P}$-distance $d$ defined by $\mathscr{P}$: given $x,y\in V$,
$d(x,y):=\inf\\{k\geq 0:\mathscr{P}^{k}(x,y)>0\\}$, which is symmetric by the
reversibility of $\mathscr{P}$. The corresponding (closed) ball of radius
$r\geq 0$ is written $B_{\mathscr{P}}(x,r):=\\{y\in V\ |\ d(x,y)\leq r\\}$ to
highlight the role of $\mathscr{P}$. Paths can be made of either vertices or
oriented edges. If $e$ is an oriented edge, $e^{-},e^{+}$ denote respectively
the initial and terminal endpoint of $e$. Given a path $\mathfrak{p}$, we
write $\mathscr{P}(\mathfrak{p})$ for the product of transition probabilities
along the edges of this path. These notations will extend for other transition
kernels as well. In particular, we can also consider the ball $B_{P}(x,r)$
which discards long-range edges. For this reason it will also be written
$B_{\mathrm{SR}}(x,r)$ and called the _small-range_ ball around $x$.

###  2.3 Quasi-trees

We now define quasi-trees, which are designed to be an infinite approximation
of the graph $G^{\ast}$. The same terminology and notation is used as in the
finite setting to emphasize analogies. This abuse is justified by the fact
that later, both settings will be coupled so that quantities with matching
terminology or notation will be equal. If necessary, we will introduce
distinct notation.

######  Definition 2.1.

A rooted quasi-tree is a $4$-tuple $(\mathcal{G},O,\eta,\iota)$ where
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ is an non-oriented graph,
$O\in\mathcal{V}$ is a distinguished vertex and $\iota$ is a map
$\iota:\mathcal{V}\rightarrow V$ that labels vertices of $\mathcal{G}$ with
states in $V$. We call $\iota(x)$ the type of the vertex $x\in V$. Finally
$\eta$ is a map $\eta=\mathcal{V}\rightarrow\mathcal{V}$, which satisfies:

  1. (i)

$\eta$ is an involution either of $\mathcal{V}$ or of
$\mathcal{V}\smallsetminus\\{O\\}$ with no fixed point. The quasi-tree is
called respectively _two-sided_ or _one-sided_ in these cases.

  2. (ii)

For all $x\in\mathcal{V}$, the edge $(x,\eta(x))$ is present in $\mathcal{E}$.
Such edges are called long-range edges, others are called small-range edges.

  3. (iii)

for all $x,y\in\mathcal{V}$, there is a unique family, possibly empty, of
long-range edges $e_{1},\ldots,e_{k}$ such that all paths between $x$ and $y$
of minimal length contain the edges $e_{1},\ldots,e_{k}$.

In particular, there must exist a unique sequence of long-range edges joining
the root $O$ to $x$. If this sequence is non-empty let $x^{\circ}$ be the the
endpoint of these long-range edges which is the furthest from $O$. We call
such a vertex a _center_. If this sequence is empty, let $x^{\circ}:=O$,
however the root is not considered a center.

The two types of edges lead in turn to two additional types of paths and
distances.

  1. 1.

A _small-range path_ is a path made exclusively of small-range edges. Given
$x,y\in V$, the _small-range distance_ $d_{\mathrm{SR}}(x,y)$ is the minimal
number of edges in small-range path from $x$ to $y$. The corresponding _small-
range balls_ are written $B_{\mathrm{SR}}(x,r)$.

  2. 2.

A _long-range path_ is a sequence $e=(e_{i})_{i=1}^{k}$ of long-range edges
such that for all $i\leq k-1$ $d_{\mathrm{SR}}(e_{i},e_{i+1})<\infty$ (so $e$
could be completed with small-range paths between long-range edges to obtain a
genuine path in $\mathcal{G}$). The length $\left|e\right|$ of $e$ is the
number of edges it contain. It joins two vertices $x,y\in\mathcal{V}$ if
$d_{\mathrm{SR}}(x,e_{1})<\infty$ and $d_{\mathrm{SR}}(e_{k},y)<\infty$. Given
$x,y\in V$, the _long-range distance_ $d_{\mathrm{LR}}(x,y)$ is the minimal
length of a long-range path between $x$ and $y$. We write
$B_{\mathrm{LR}}(x,r)$ for the corresponding _long-range balls_.

From the definition, for any $x\in\mathcal{V}$,
$B_{\mathrm{SR}}(x,\infty)=B_{\mathrm{LR}}(x,0)$ is the set of vertices which
can be joined from $x$ by a small-range path. We call the subgraph spanned by
this set the _small-range component_ of $x$. We can now state a fourth
property we require for quasi-trees:

  1. (iv)

for all $x\in\mathcal{V}$, $B_{\mathrm{LR}}(x,0)$ is isomorphic to
$B_{P}(\iota(x^{\circ}),\infty)$,

that is, the small-range component of $x$ is the communicating class of
$\iota(x)$ in the graph $G$.

In the sequel we will refer to quasi-trees by their graph component only while
keeping the other parameters implicit.

##### One-sided quasi-trees and subquasi-trees

We introduced one-sided quasi-trees to consider subquasi-trees. If $x$ is a
center, the subquasi-tree $\mathcal{G}_{x}$ of $x$ is the graph spanned by the
vertices $y$ for which all paths between $O$ and $y$ pass through $x$. If $x$
is not a center, $\eta(x)$ is and we set
$\mathcal{G}_{x}:=\mathcal{G}_{\eta(x)}$, so $\mathcal{G}_{x}$ does not in
fact contain $x$ in that case. Finally the complement subgraph
$\mathcal{G}\smallsetminus\mathcal{G}_{x}$ is the graph spanned by vertices
which can be reached from $O$ by a long-range path that does not use the long-
range edge $(x,\eta(x))$.

##### Non-backtracking paths, loop-erased paths, deviation, regeneration

One main interest of having a genuine tree structure is the consideration of
loop-erased trajectories. We thus introduce the following definitions.

######  Definition 2.2.

Let $\mathcal{G}$ be a quasi-tree. A long-range path $e=(e_{1},\ldots,e_{k})$
backtracks over a distance $l\geq 1$ if it contains a subpath of distinct
edges and of length $l$ immediately followed by the reversed path, that is
there exists $i\leq k-2l+1$ such that $e_{i+l+j}=\overline{e_{i+l-1-j}}$ for
all $j\in[0,l-1]$, where $\overline{e_{j}}$ denotes the edge $e_{j}$ with
reversed orientation. The loop-erased path $\xi(e)$ is the path obtained after
erasing all backtracking steps. The long-range path $e$ is called _non-
backtracking_ if $\xi(e)=e$.

To previous definition is extended to general paths by extracting the long-
range path: given a general path $\mathfrak{p}$, let $\xi(\mathfrak{p})$
denote the loop-erased path formed by the long-range edges crossed by
$\mathfrak{p}$. This is a non-backtracking path, which we call the loop-erased
path or loop-erased trace of $\mathfrak{p}$. The long-range distance crossed
by $\mathfrak{p}$ is the length of $\xi(\mathfrak{p})$, or equivalently the
long-range distance between its endpoints.

The last two definitions require integer parameters. Given $R\geq 1$, let
$\mathcal{G}^{(R)}$ be the connected component of $O$ of the subgraph of
$\mathcal{G}$ spanned by the set

$\mathcal{V}^{(R)}:=\\{x\in\mathcal{V}\ |\ d_{\mathrm{SR}}(x^{\circ},x)<R\\}.$
(12)

A path $\mathfrak{p}$ is said to _deviate_ from a small-range distance $R$ if
it is not included in $\mathcal{G}^{(R)}$.

Finally, the following notion of _regeneration edges_ will be used in several
places: let $L\geq 1$ be an integer and consider a path $\mathfrak{p}$. A
long-range edge $e$ crossed by $\mathfrak{p}$ is said to be a regeneration
edge for $\mathfrak{p}$ with horizon $L$ if after the first time going through
$e$ the path crosses a long-range distance $L$ or ends before going back to
the endpoint of $e$ which was first visited by $\mathfrak{p}$.

##### Markov chains on quasi-trees

Given a quasi-tree $\mathcal{G}$, it is naturally the underlying graph of the
Markov chain $(\mathcal{X}_{t})_{t\geq 0}$ on $\mathcal{G}$ which has
transition probabilities:

$\begin{split}&\mathbf{P}\left[\left.\mathcal{X}_{t+1/2}=y\ \right|\
\mathcal{X}_{t}=x\right]=\left\\{\begin{array}[]{l
l}p(\iota(x),\iota(\eta(x)))&\text{if $y=x$}\\\
q(\iota(x),\iota(\eta(x)))&\text{if $y=\eta(x)$}\end{array}\right.\\\
&\mathbf{P}\left[\left.\mathcal{X}_{t+1}=y\ \right|\
\mathcal{X}_{t+1/2}=x\right]=\left\\{\begin{array}[]{l
l}P(\iota(x),\iota(y))&\text{if $y^{\circ}=x^{\circ}$}\\\
0&\text{otherwise}\end{array}\right..\end{split}$ (13)

The kernel of this Markov chain will be written $\mathcal{P}$. As for the
chain $X$ in finite environment, this chain may not be reversible but can be
projected to the quotient $\mathcal{G}/\sim$, which identifies each
$x\sim\eta(x)$. The projection is then a reversible chain.

###  2.4 The covering quasi-tree

Among all quasi-trees, one is very natural to consider: this is the quasi-tree
obtained by using the random matching $\eta:V\rightarrow V$ to define the
matching on the quasi-tree. Given $x\in V$, this is the quasi-tree
$(\mathcal{G}^{\ast}(x),O,\iota,\tilde{\eta})$ defined by $\iota(O)=x$ and

$\forall y\in\mathcal{V}:\iota(\tilde{\eta}(y))=\eta(\iota(y)).$

The fact that this defines a unique quasi-tree is the consequence from
property (iv) in Definition 2.1, which imply the quasi-tree can be built
iteratively. Starting from the small-range of $O$, which is necessarily
$B_{P}(x,\infty)$, the previous equation uniquely determines the long-range
edges at long-range distance $0$ from $O$ and thus the whole ball
$B_{\mathrm{LR}}(O,1)$. The process iterates to infinity to yield an infinite
quasi-tree $\mathcal{G}^{\ast}$.

This quasi-tree has the property that it covers exactly $G^{\ast}$: the map
$\iota$ is a surjective graph morphism of $\mathcal{G}^{\ast}$ onto $G^{\ast}$
which preserves the transition probabilities, so the Markov chain
$\mathcal{X}$ defined above projects exactly onto the chain $X$: for all
$t\geq 0$ $\iota(\mathcal{X}_{t})=X_{t}$ in distribution, conditional on
$X_{0}=x,\mathcal{X}_{0}=O$.

The chain $\mathcal{X}$ on $\mathcal{G}^{\ast}$ will not be studied per se. We
introduced it mainly to obtain easier definitions in the finite setting of
objects and quantities that are naturally considered in the idealized setting
of quasi-trees. First notice that the notions of long-range and small-range
edges defined in the finite setting coincide with the projections under
$\iota$ of the corresponding edges in the covering quasi-tree. Thus we can
extend notions of small-range, long-range paths, backtracking, etc. defined
above to $G^{\ast}$ by taking their projections under $\iota$. An exception is
the long-range distance, which in the finite setting will make sense only if
restricting the quasi-tree: let $R\geq 1$ and recall the definition of the
restricted quasi-tree $\mathcal{G}^{(R)}$ (12). Given $x\in V$ and $l\geq 0$,
we define $B_{\mathrm{LR}}^{(G^{\ast},R)}(x,r)$ in $G^{\ast}$ as the
projection

$B_{\mathrm{LR}}^{(G^{\ast},R)}(x,r):=\iota\left(B_{\mathrm{LR}}(O,r)\cap\mathcal{G}^{(R)}(x)\right).$

The exponent $(G^{\ast},R)$ is used to distinguish between the two settings.
When not necessary, we may drop it from notation and also keep this parameter
$R$ implicit. Note from the definition that in $G^{\ast}$, for any vertices
$x,y\in V$, $d_{\mathrm{LR}}(x,y)=0$ if and only if $d_{\mathrm{SR}}(x,y)<R$.

Finally, we introduce a last definition which is specific to $G^{\ast}$: a
_long-range cycle_ is a non-deviating non-backtracking long-range path whose
starting and ending point are at small-range distance at most $R$ from each
other. A subgraph of $G^{\ast}$ is said to be _quasi-tree-like_ if it does not
contain any long-range cycle. A quasi-tree-like subgraph can thus be
identified with a neighbourhood of the root in the covering quasi-tree. Lemma
2.1 below will establish that typical and hence most vertices have in fact a
quasi-tree-like neighbourhood. This relies on a bounded degree property, which
is the object of the following paragraph.

##### Bounded degrees and transition probabilities:

Assumption (H1) implies that all graphs considered in this paper,
$G,G^{\ast},\mathcal{G}$ have bounded degrees. Together with Assumption (H2),
it also implies all transition probabilities are bounded away from $0$
uniformly in $n$. Consequently, let $\Delta$ denote a uniform bound on all the
degrees, and $\delta>0$ a uniform bound on transition probabilities, which
will serve throughout the paper. It gives in particular the growth of balls in
$G^{\ast}$ and any quasi-tree $\mathcal{G}$: for all $x\in V$ and $l\geq 0$

$\left|B_{\mathrm{SR}}(x,l)\right|\leq\left|B_{\mathscr{P}}(x,l)\right|\leq\frac{\Delta^{l+1}-1}{\Delta-1},\qquad\left|B_{\mathrm{LR}}^{(G^{\ast},R)}(x,l)\right|\leq\Delta^{R}\frac{\Delta^{R(l+1)}-1}{\Delta^{R}-1}.$
(14)

In particular, $\Delta^{R}$ can be thought of as the "long-range" degree.

###  2.5 Coupling and sequential generation

The above definitions should make pretty clear that the forthcoming proofs are
based on a coupling between the finite chain $X$ and the chain $\mathcal{X}$
on an infinite quasi-tree. The quasi-tree in question is similar to the
covering quasi-tree but contains much more independence, allowing basically to
resample the matching $\eta$ at each new long-range edge. It can be
constructed iteratively as follows: $\iota(O)$ is taken uniformly at random in
$V$, which determines the small-range component around $O$ by point (iv) of
the definition. Then to every vertex $x$ whose type $\iota(x)$ is known,
adjoin a long-range edge $(x,\eta(x))$ to $x$, with $\iota(\eta(x))$ being
taken uniformly in $V\smallsetminus V(\iota(x))$. In words, each new center
added to the quasi-tree is taken uniformly at random in the component of $V$
that maintains the alternation between $V_{1}$ and $V_{2}$. We now explain how
one can couple the Markov chain $(X_{t})_{t\geq 0}$ on $G^{\ast}$ with the
Markov chain $(\mathcal{X}_{t})_{t\geq 0}$ on $\mathcal{G}$.

The following procedure generates the neighbourhood of a vertex in either
$G^{\ast}$ or $\mathcal{G}$ up to some given long-range distance.

Let $x\in V$ be the point whose long-range neighbourhood is to be explored up
to long-range distance $L\geq 0$. For $t\geq 1$ we write $EQ_{t}$ for the
exploration queue, that is the set of vertices which remain to be explored,
and $D_{t}$ for the set of explored vertices. The initiation is similar for
$G^{\ast}$ and quasi-trees: $D_{0}:=\emptyset$; $EQ_{0}:=B_{\mathrm{SR}}(x,R)$
in $G$, $EQ_{0}:=B_{\mathrm{SR}}(x,\infty)$ in $\mathcal{G}$. The procedure
repeats then the following steps. If one wants to explore a neighbourhood in
$G^{\ast}$ sampling is performed without replacement:

##### Sequential generation of $G^{\ast}$, sampling without replacement:

for $t\geq 0$,

  1. 1.

pick $y\in EQ_{t}$: sample $\eta(y)$ uniformly at random in $(V\smallsetminus
V(y))\smallsetminus D_{t}$,

  2. 2.

add $y,\eta(y)$ to $D_{t+1}$ and remove them from $EQ_{t+1}$,

  3. 3.

add all vertices $z\in B_{\mathrm{SR}}(\eta(y),R)\smallsetminus\\{\eta(y)\\}$
such that $z\notin D_{t}$ and $d_{\mathrm{LR}}(x,z)<L$ to $EQ_{t+1}$.

If performed with replacement, each new value $\eta(y)$ is picked uniformly in
$V\smallsetminus V(y)$ independently of previous draws and considered a new
vertex in a set $\mathcal{V}$. Specifically the procedure becomes:

##### Sequential generation of the quasi-tree $\mathcal{G}$, sampling with
replacement:

for $t\geq 0$,

  1. 1’.

pick $y\in EQ_{t}$: sample $\eta(y)$ uniformly at random in $V\smallsetminus
V(y)$,

  2. 2’.

add $y,\eta(y)$ to $D_{t+1}$ and remove $y$ from $EQ_{t+1}$,

  3. 3’.

add all vertices $z\in B_{\mathrm{SR}}(\eta(y),R)\smallsetminus\\{\eta(y)\\}$
such that $d_{\mathrm{LR}}(x,z)<L$ to $EQ_{t+1}$.

Since the constraint $z\notin D_{t}$ has been removed in step 3’, vertices
which would in $G$ be already explored are here added to the exploration queue
and thus considered new vertices. The environment explored is the $L$ long-
range ball of a quasi-tree as in Definition 2.1. Taking $L=\infty$ would thus
yield a realization of the infinite random quasi-tree $\mathcal{G}$. Finally,
the analog procedures can be adapted to explore balls $B_{\mathscr{P}}$ in
$G^{\ast}$ and $B_{\mathcal{P}}$ in $\mathcal{G}$.

##### Sequential generation along trajectories

Under the annealed law, the two processes can be generated together with the
environment. Later our goal will be to couple weights, which require the
exploration of the whole $L$-long range neighbourhood around the trajectory.
The sequential generation of the environment along trajectories thus consists
in the following steps. Consider for instance the finite setting $G$: let the
chain be started at $X_{0}:=x\in V$, and $D_{0}:=\emptyset$. Then for all
$t\geq 0$:

  1. a.

Explore the long-range $L$-neighbourhood of $X_{t}$ with the first procedure
described above.

  2. b.

This determines completely the transition probabilities (11) at the state
$X_{t}$, allowing to sample $X_{t+1}$.

If one considers the second procedure one obtains instead
$(\mathcal{X}_{t})_{t\geq 0}$. One can very naturally couple the two
procedures and hence both processes using rejection sampling: for each $y\in
EQ_{t}$ sample $\eta(y)$ uniformly in $V\smallsetminus V(y)$ and use it for
step 1’ in the generation of $\mathcal{G}$. If in addition
$B_{\mathrm{SR}}(\eta(y),R)\cap D_{t}=\emptyset$, it can also be used for step
$1$ in the generation of $G^{\ast}$. Otherwise, make a second draw with the
first procedure. This rejection sampling scheme yields a coupling of
$(X_{t})_{t\geq 0}$ and $(\mathcal{X}_{t})_{t\geq 0}$ until the first time a
newly revealed small-range balls $B_{\mathrm{SR}}(\eta(y),R)$ contain vertices
that have already been explored, that is when a long-range cycle appears
around the trajectory:

$\tau_{\mathrm{coup}}:=\inf\left\\{t\geq 0\ |\
\bigcup_{k=0}^{t}B_{\mathrm{LR}}(X_{k},L)\text{ contains a long-range
cycle}\right\\}.$

The following lemma will be not be used but justifies that trajectories of
subpolynomial length started at typical vertices can be coupled exactly with
trajectories on a quasi-tree.

######  Lemma 2.1.

For all constants $C_{R},C_{L}>0$, $R=C_{R}\log\log n,L=C_{L}\log\log n$, for
all $x\in V,\varepsilon\in(0,1/2)$ and $t=O(n^{1/2-\varepsilon})$,

$\mathbf{P}_{x}\left[\exists s\leq
t:\text{$B_{\mathrm{LR}}^{(G^{\ast},R)}(X_{s},L)$ is not quasi-tree-
like}\right]=o_{\mathbb{P}}(1)$

Thus $\mathbf{P}_{x}\left[\tau_{\mathrm{coup}}\leq
t\right]=o_{\mathbb{P}}(1)$.

###### Proof.

Let the chain be started at $x\in V$ and $t=o(n^{3/10-\varepsilon})$ for
$\varepsilon\in(0,3/10)$. By (14), the number of vertices contained in a long-
range ball of radius $L$ is $O(\Delta^{R}(L+1))$. This implies $\bigcup_{s\leq
t}B_{\mathrm{LR}}^{(G^{\ast},R)}(X_{s},L)$ contains
$m=O((t+1)\Delta^{R(L+1)})$ vertices. Therefore, the exploration procedure
along the path $X_{0}\cdots X_{t}$ up to long-range distance $L$ requires at
most $m$ draws of values $\eta(y)$, each having probability at most
$m\Delta^{R}/n$ that the small-range ball $B_{\mathrm{SR}}(\eta(y),R)$
contains already explored vertices. Hence the number of long-range cycles in
$\bigcup_{s\leq t}B_{\mathrm{LR}}^{(G^{\ast},R)}(X_{s},L)$ is stochastically
upper bounded by a binomial $\mathrm{Bin}(m,m\Delta^{R}/n)$ so that by
Markov’s inequality

$\displaystyle\mathbb{P}_{x}\left[\exists s\leq
t:\text{$B_{\mathrm{LR}}^{(G^{\ast},R)}(X_{s},L)$ is not quasi-tree-
like}\right]$
$\displaystyle\leq\frac{m^{2}\Delta^{R}}{n}=O\left(\frac{(t+1)^{2}\Delta^{2RL+3R}}{n}\right)$
$\displaystyle=O\left(t^{2}n^{-1+o(1)}\right)=o(1)$

by the choice of $t=O(n^{1/2-\varepsilon})$ and $R,L=O(\log\log n)$. This
bound on the annealed probability implies the quenched result by the first
moment argument (9). ∎

##  3 The entropic method: main arguments

###  3.1 Nice trajectories

Our application of the entropic method consists in finding a definition of
nice trajectories designed to be typical trajectories and have their
probability concentrating around the mean. The latter will come from a
constraint about an entropy-like quantity for the chain, which arises from
comparing the trajectories of the finite chain $X$ with the loop-erased trace
of $\mathcal{X}$ in the (infinite) quasi-tree setting. Other properties will
thus be required from nice paths, whose goal is basically to make them close
to being non-backtracking trajectories in a quasi-tree. All in all, the
defining properties of a nice trajectory will essentially be that:

  1. (i)

it is contained in a quasi-tree-like portion of the graph, the endpoint having
a quasi-tree-like neighbourhood up to $\mathscr{P}$-distance
$\lfloor\alpha\log n\rfloor$ for some $\alpha>0$ (Lemma 3.1),

  2. (ii)

it does not deviate or backtrack too much, and contains sufficiently many
regeneration edges (Lemma 3.2),

  3. (iii)

the drift and entropy concentrate on this trajectory (Proposition 3.1).

The first part of the argument will consist in proving that the chain is
likely to follow nice trajectories. However this may not be true for arbitrary
starting vertices, but only for typical ones. For an arbitrary starting
vertex, we prove the trajectory becomes nice after some time $s=O(\log\log
n)$. Since this is $o(\sqrt{\log n})$, the contribution of these initial steps
will be negligible.

######  Lemma 3.1.

  1. (i)

For all $C_{R},C_{L}>0$, there exists $C>0$ such that for $R:=C_{R}\log\log
n,L:=C_{L}\log\log n$, $s\geq C\log\log n$ and all $t=o(n^{1/16})$,

$\max_{x\in V}\mathbf{P}_{x}\left[\exists
t^{\prime}\in[s,s+t]:B_{\mathrm{LR}}^{(G^{\ast},R)}(X_{t^{\prime}},L)\text{ is
not quasi-tree-like}\right]=o_{\mathbb{P}}(1).$

  2. (ii)

For all $C>0$, there exists $\alpha>0$ such that for any $t\geq C\log n$,

$\max_{x\in V}\mathbf{P}_{x}\left[B_{\mathscr{P}}(X_{t},\lfloor\alpha\log
n\rfloor)\text{ is not quasi-tree-like}\right]=o_{\mathbb{P}}(1)$

For the second property we recall the notions of deviation, backtracking and
regeneration edges are given in Definition 2.2.

######  Lemma 3.2.

Let $\Gamma(R,L,M)$ denote the set of paths $\mathfrak{p}$ in $G^{\ast}$ such
that $\mathfrak{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 exist constants $C_{R},C_{L},C_{M},C>0$
such that for $L=C_{L}\log\log n$, $R=C_{R}\log\log n$ and $M=C_{M}\log\log
n$, for all $s\geq C\log\log n$ and $t=O(\log n)$:

$\min_{x\in V}\mathbf{P}_{x}\left[(X_{s}\cdots
X_{s+t})\in\Gamma(R,L,M)\right]=1-o_{\mathbb{P}}(1).$

######  Remark 3.1.

Notice that for any trajectorial event $A$

$\displaystyle\mathbf{P}_{x}\left[(X_{s},X_{s+1},\ldots)\in A\right]$
$\displaystyle=\sum_{y\in
V}\mathbf{P}_{x}\left[X_{s}=y\right]\mathbf{P}_{y}\left[(X_{0},X_{1},\ldots)\in
A\right]$ $\displaystyle\leq\max_{y\in
V}\mathbf{P}_{y}\left[(X_{0},X_{1},\ldots)\in A\right].$

Thus if we prove $A$ holds from time $s$ with probability
$1-o_{\mathbb{P}}(1)$ uniformly over the starting state this automatically
extends to larger times $t\geq s$.

###  3.2 Concentration of drift and entropy

The third and main property of nice trajectories consists in the concentration
of an entropy-like quantity for the finite chain. To that end, we define
weights as follows.

Throughout the paper, we will use the letter $\tau$ for a variety of stopping
times. It should be clear from the context what the notation refers to. If $x$
is an element or a set $\tau_{x}$ will generally denote the hitting time of
$x$. If $l\geq 0$, $\tau_{l}$ will generally denote the time a certain
distance $l$ is reached. For all $l\geq 0$, consider here

$\tau_{l}:=\inf\\{t\geq 0\ |\ \left|\xi(X_{0}\cdots X_{t})\right|=l\\}$

and fix $R,L\geq 1$ for the rest of this section. Let

$\displaystyle\tau^{(R)}_{\mathrm{SR}}:=\inf\\{t\geq 0\ |\ (X_{0}\cdots
X_{t})\text{ deviates from a small-range distance $R$}\\}$
$\displaystyle\tau^{(L)}_{\mathrm{NB}}:=\inf\\{t\geq 0\ |(X_{0}\cdots
X_{t})\text{ backtracks over a long-range distance $L$}\\}.$

These are stopping times which depend on $R,L$. By construction if
$\mathfrak{p}$ is a path in $\Gamma(R,L,M)$ as defined in Lemma 3.2, the
stopping $\tau^{(R)}_{\mathrm{SR}}\wedge\tau^{(L)}_{\mathrm{NB}}$ does not
occur on the trajectory $\mathfrak{p}$. Given an oriented long-range edge $e$
and $x\in V$ such that $d_{\mathrm{SR}}(x,e^{-})<R$, define the weights

$\begin{split}w_{x,R,L}(e)&:=\mathbf{P}_{x}\left[\xi(X_{0}\cdots
X_{\tau_{L}})_{1}=e,\tau_{L}<\tau^{(R)}_{\mathrm{SR}}\right]\\\ w_{R,L}(e\ |\
x)&:=\mathbf{P}_{x}\left[\left.\xi(X_{0}\cdots X_{\tau_{L}})_{1}=e\ \right|\
\tau_{L}<\tau_{\eta(x)}\wedge\tau^{(R)}_{\mathrm{SR}}\right]\end{split}$ (15)

Here $\xi(X_{0}\cdots X_{\tau_{L}})_{1}$ denotes the first edge of
$\xi(X_{0}\cdots X_{\tau_{L}})$. Then for a non-backtracking long-range path
$\xi=\xi_{1}\cdots\xi_{k}$, set

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

where empty products are by convention equal to $1$. The notation is
consistent with the identification of edges with paths of length $1$.

######  Remark 3.2.

Note that for fixed $x\in V$, $\sum_{e}w_{x,R,L}(e)\leq 1$ and
$\sum_{e}w_{R,L}(e\ |\ x)\leq 1$ where the sum is over all long-range edges.
By extension the sum of weights over all non-backtracking paths starting from
$x$ is at most $1$.

Given a sequence $u=(u_{i})_{i\leq l}$ of length $l$ and $k\geq 1$, we write
$(u)_{\leq k}:=(u_{i})_{i\leq k}$ for the sequence truncated at length $k$.
The following lemma show that weights are good proxies for measuring the
probability that the loop-erased trace follows a given non-backtracking path.
We will only need the lower bound.

######  Lemma 3.3.

Let $x\in V$ and $k\geq 1$ be an integer. Suppose that
$B_{\mathrm{LR}}^{(G^{\ast},R)}(x,k)$ is quasi-tree-like. Then for all non-
backtracking long-range path $\xi$ of length $k$, started in
$B_{\mathrm{SR}}(x,R)$

$\mathbf{P}_{x}\left[\begin{gathered}\xi(X_{0}\cdots X_{\tau_{k+L-1}})_{\leq
k}=\xi,\\\
\tau_{k+L-1}<\tau^{(R)}_{\mathrm{SR}}\wedge\tau^{(L)}_{\mathrm{NB}}\end{gathered}\right]\leq
w_{x,R,L}(\xi)\leq\mathbf{P}_{x}\left[\begin{gathered}\xi(X_{0}\cdots
X_{\tau_{k+L-1}})_{\leq k}=\xi,\\\
\tau_{k+L-1}<\tau^{(R)}_{\mathrm{SR}}\wedge\tau^{(L)}_{\mathrm{NB}}\end{gathered}\right]+u(\xi)$
(16)

where $u(\xi)\geq 0$ is such that

$\sum_{\xi}u(\xi)\leq\mathbf{P}_{x}\left[\tau^{(R)}_{\mathrm{SR}}\wedge\tau^{(L)}_{\mathrm{NB}}\leq\tau_{k+L-1}\right],$

the sum being over non-backtracking long-range paths of length $k$ from $x$.

###### Proof.

The proof is by induction on $k\geq 1$. For $k=1$ the inequalities are in fact
equalities by definition, since $\tau^{(L)}_{\mathrm{NB}}>\tau_{L}$
necessarily.

To ease notation, drop the parameters $R,L$ from the stopping times and
weights for the rest of the proof. Suppose that the result holds for $k\geq 1$
and let $\xi$ be of length $k+1$. Let $e:=\xi_{k},f:=\xi_{k+1}$ and write
$L_{k}$ for the last time $t$ that $\left|\xi(X_{0}\cdots X_{t})\right|=k$
after $\tau_{k}$ and before $\tau_{k+L}$ or coming back to $e^{-}$. Then
having $\xi(X_{0}\cdots X_{\tau_{k+L-1}})_{\leq k}=(\xi)_{\leq k}$ requires
that $X_{L_{k}}=e^{+}$, after which the chain crosses a long-range distance
$L-1$ without backtracking to $e^{-}$. Thus by the induction hypothesis,

$\displaystyle w_{x}((\xi)_{\leq k})$
$\displaystyle\geq\mathbf{P}_{x}\left[\xi(X_{0}\cdots X_{\tau_{k+L-1}})_{\leq
k}=\xi,\tau_{k+L-1}<\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}\right]$
$\displaystyle=\mathbf{P}_{x}\left[X_{L_{k}}=e^{+},L_{k}<\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}\right]\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right].$

On the other hand,

$w(f\ |\ e^{+})=\frac{\mathbf{P}_{e^{+}}\left[\xi(X_{0}\cdots
X_{\tau_{L}})_{1}=f,\tau_{L}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]}{\mathbf{P}_{e^{+}}\left[\tau_{L}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]}.$

Since
$\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]\geq\mathbf{P}_{e^{+}}\left[\tau_{L}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]$,
we deduce that

$\displaystyle w_{x}(\xi)$ $\displaystyle=w_{x}((\xi)_{\leq k})\,w(f\ |\
e^{+})$
$\displaystyle\geq\mathbf{P}_{x}\left[X_{L_{k}}=e^{+},\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}>L_{k}\right]\mathbf{P}_{e^{+}}\left[\xi(X_{0}\cdots
X_{\tau_{L}})_{1}=f,\tau_{L}<\tau_{\mathrm{SR}}\wedge\tau_{e^{-}}\right].$

This is the probability that after $L_{k}$, the chain directly crosses a long-
range distance $L$ using the edge $f$, without reaching the boundary of a
small-range ball of radius $R$ and without coming back to $e^{-}$. Hence on
this event $\xi(X_{0}\cdots X_{\tau_{k+L}})_{k+1}=f$, with
$\tau_{k+L}<\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}$, which proves the
lower bound.

For the upper bound, the induction hypothesis yields this time

$\displaystyle w_{x}((\xi)_{\leq k})$
$\displaystyle\leq\mathbf{P}_{x}\left[X_{L_{k}}=e^{+},L_{k}<\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}\right]\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]+u((\xi)_{\leq
k}).$

Then use that

$\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]\leq\mathbf{P}_{e^{+}}\left[\tau_{L}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\right]+\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\leq\tau_{L}\right]$

to bound

$\displaystyle w_{x}(\xi)$
$\displaystyle\leq\mathbf{P}_{x}\left[X_{L_{k}}=e^{+}\right]\mathbf{P}_{e^{+}}\left[\xi(X_{0}\cdots
X_{\tau_{L}})_{1}=f,\tau_{L}<\tau_{\mathrm{SR}}\wedge\tau_{e^{-}}\right]$
$\displaystyle+\mathbf{P}_{x}\left[X_{L_{k}}=e^{+}\right]\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\leq\tau_{L}\right]w(f\
|\ e^{+})+u((\xi)_{\leq k})w(f\ |\ e^{+}).$

The first term is that of the lower bound. Regroup the two other terms as
$u(\xi)$. Since weights sum to $1$, summing over $\xi$, which involves in
particular summing over $e$ and $f$, yields that

$\sum_{\xi}u(\xi)\leq\sum_{e}\mathbf{P}_{x}\left[X_{L_{k}}=e^{+}\right]\mathbf{P}_{e^{+}}\left[\tau_{L-1}<\tau_{e^{-}}\wedge\tau_{\mathrm{SR}}\leq\tau_{L}\right]+\mathbf{P}_{x}\left[\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}\leq\tau_{k+L-1}\right].$

Observe now the first term corresponds to backtracking or deviating after
reaching level $k+L-1$ but before reaching level $k+L$ from $x$. Thus the two
terms correspond to disjoint events which both imply
$\tau_{\mathrm{SR}}\wedge\tau_{\mathrm{NB}}\leq\tau_{k+L}$, hence the upper
bound. ∎

The first part of the proof of Theorem 1.1 consists in proving the following
quenched concentration phenomenon.

######  Proposition 3.1.

There exists $\mathscr{d},h=\Theta(1)$ and large constants $C_{R},C_{L},C>0$
such that the following holds. Letting $R:=C_{R}\log\log n,L:=C_{L}\log\log
n$, for all $\varepsilon>0$ there exist constants
$C_{\mathrm{LR}}(\varepsilon),C_{h}(\varepsilon)>0$ such that for all $s\geq
C\log\log n,t\gg 1$, $t=O(\log n)$ with high probability,

$\min_{x\in
V}\mathbf{P}_{x}\left[\begin{array}[]{c}\left|\left|\xi(X_{s}\cdots
X_{s+t})\right|-\mathscr{d}t\right|\leq C_{\mathrm{LR}}\sqrt{t}\\\ \left|-\log
w_{X_{s},R,L}(\xi(X_{s}\cdots X_{s+t}))-ht\right|\leq
C_{h}\sqrt{t}\end{array}\right]\geq 1-\varepsilon.$

###  3.3 Concentration of nice paths

The second part of the argument uses the properties of nice paths to show that
the probability of following a nice trajectory concentrates around its mean.
The latter can be computed, providing an approximate stationary distribution
$\hat{\pi}$ for $\mathscr{P}$ on $V$.

Given $u\in V$, $L\geq 1$ consider again $\tau_{L}:=\inf\\{t\geq 0\ |\
\left|\xi(X_{0}\cdots X_{t})\right|=L\\}$ and

$\mathbf{Q}^{(L)}_{u}:=\mathbf{P}\left[\left.\cdot\ \right|\
X_{1/2}=u,\tau_{\eta(u)}>\tau_{L}\right]$ (17)

In words, this measure considers trajectories immediately after a regeneration
time, ie a time at which a regeneration edge is crossed (with horizon $L$). By
Lemma 3.2, if one takes $L=\Theta(\log\log n)$, the conditionning by
$\tau_{L}<\tau_{X_{0}}$ essentially forbids the chain to come back at all to
$u$ on a time scale $O(\log n)$. If $\nu$ is a probability measure on $V$,
write $\mathbf{Q}^{(L)}_{\nu}:=\sum_{u\in V}\nu(u)\mathbf{Q}^{(L)}_{u}$ and
$\mathbf{E}^{(L)}_{\mathbf{Q}_{\nu}}$ for the expectation with respect to this
measure. All in all, the whole argument of this paper is summarized in the
following proposition.

######  Proposition 3.2.

There exist a deterministic probability measure $\nu$ on $V$, a deterministic
$s_{0}=\Theta(\log n)$, constants $C_{L},C_{M},C>0$ and for all $x,y\in
V,t\in\mathbb{N}$ a set $\mathfrak{N}^{t}(x,y)$ of length $t$ paths between
$x$ and $y$ for which the following holds. Let $L:=C_{L}\log\log
n,M:=C_{M}\log\log n$ and write
$\mathscr{P}_{\mathfrak{N}}^{t}(x,y):=\sum_{\mathfrak{p}\in\mathfrak{N}^{t}(x,y)}\mathscr{P}(\mathfrak{p})$.
Consider the random probability measure

$\hat{\pi}(v):=\frac{1}{\mathbf{E}_{\mathbf{Q}_{\nu}^{(L)}}\left[T_{1}\wedge
M\right]}\sum_{r=0}^{M}\mathbf{Q}_{\nu}^{(L)}\left[X_{r+s_{0}}=v,r<T_{1}\leq
M\right]$ (18)

where $T_{1}$ denotes the first regeneration time with horizon
$L=C_{L}\log\log n$. For all $\varepsilon>0$, there exists $C(\varepsilon)>0$
constant in $n$, such that for $t=\log n/h+C(\varepsilon)\sqrt{\log n}$,

  1. (i)

for all $s\geq C\log\log n$, with high probability

$\min_{x\in V}\sum_{y\in
V}\mathscr{P}^{s}\mathscr{P}^{t}_{\mathfrak{N}}\,(x,y)\geq 1-\varepsilon.$

  2. (ii)

there exists $c=(c_{v})_{v\in V}$ such that $\sum_{v\in
V}c_{v}=o_{\mathbb{P}}(1)$ and with high probability, for all $x,y\in V$,

$\mathscr{P}_{\mathfrak{N}}^{t}(x,y)\leq(1+\varepsilon)\hat{\pi}(y)+c(y)+\frac{\varepsilon}{n},$

###### Proof of Theorem 1.1.

Recall $\mathscr{P}$ is the transition matrix of the two-lift chain on $V$,
which projects to a transition matrix $\bar{\mathscr{P}}$ on $[n]$.

Start with the upper bound on the mixing time. Let $\varepsilon>0$ and
consider $s=C\log\log n,t:=\log n/h+C(\varepsilon)\sqrt{\log n}$. Since
$\mathscr{P}\geq\mathscr{P}_{\mathfrak{N}}$ entry-wise, for all $x\in V$

$\displaystyle\left\|\hat{\pi}-\mathscr{P}^{s+t}(x,\cdot)\right\|_{\mathrm{TV}}$
$\displaystyle=\sum_{z\in
V}\left[\hat{\pi}(z)-\mathscr{P}^{s+t}(x,z)\right]_{+}\leq\sum_{y,z\in
V}\mathscr{P}^{s}(x,y)\left[\hat{\pi}(z)-\mathscr{P}^{t}(y,z)\right]_{+}$
$\displaystyle\leq\sum_{y,z\in
V}\mathscr{P}^{s}(x,y)\left[(1+\varepsilon)\hat{\pi}(z)+c(z)+\frac{\varepsilon}{n}-\mathscr{P}_{\mathfrak{N}}^{t}(y,z)\right]_{+}.$

Point (ii) of the above proposition implies that with high probability, the
right hand side summands are non-negative for all $x\in V$, so the sum can be
computed to obtain that with high probability, for all $x\in V$,

$\displaystyle\left\|\hat{\pi}-\mathscr{P}^{s+t}(x,\cdot)\right\|_{\mathrm{TV}}\leq
1-\mathscr{P}^{s}\mathscr{P}_{\mathfrak{N}}^{t}(x,y)+3\varepsilon.$

Using point (i), with high probability

$\max_{x\in
V}\left\|\mathscr{P}^{s+t}(x,\cdot)-\hat{\pi}\right\|_{\mathrm{TV}}\leq
4\varepsilon$

which projects by (10) to

$\max_{x\in
V}\left\|\bar{\mathscr{P}}^{s+t}(x,\cdot)-\bar{\hat{\pi}}\right\|_{\mathrm{TV}}\leq
4\varepsilon.$

with $\bar{\hat{\pi}}$ the projection onto $[n]$ of $\hat{\pi}$. Since this
estimate is uniform in the starting state, it extends to any starting
distribution and in particular to a stationary distribution. Thus for any
stationary distribution $\pi$ of $\bar{\mathscr{P}}$,

$\left\|\pi-\bar{\hat{\pi}}\right\|_{\mathrm{TV}}\leq 4\varepsilon.$ (19)

and from triangular inequality we obtain that with high probability

$\max_{x\in[n]}\left\|\bar{\mathscr{P}}^{s+t}(x,\cdot)-\pi\right\|_{\mathrm{TV}}\leq
8\varepsilon.$

Since this is valid for any invariant measure, the latter must be unique and
the chain irreducible and aperiodic. Noticing that $s=o(\sqrt{\log n})$, this
proves the upper bound of Theorem 1.1.

For the proof of the lower bound we make use of the explicit knowledge of the
invariant measure, although this is not necessary, see Remark 3.3. Without
loss of generality, suppose $\pi$ is the unique invariant measure of
$\mathscr{P}$, which was anyway proved above to be true with high probability.

For all $t\geq 0,\theta>0$ and $x,y\in[n]$,

$\displaystyle\bar{\mathscr{P}}^{t}(x,y)$
$\displaystyle=\mathscr{P}^{t}(x,y)+\mathscr{P}^{t}(x,\eta(y))$
$\displaystyle\geq\mathbf{P}_{x}\left[X_{t}\in\\{y,\eta(y)\\},w_{x,R,L}(\xi(X_{0}\cdots
X_{t}))\leq\theta\right].$

If equality holds, then

$\bar{\pi}(y)-\mathbf{P}_{x}\left[X_{t}\in\\{y,\eta(y)\\},w_{x,R,L}(\xi(X_{0}\cdots
X_{t}))\leq\theta\right]\leq\left[\bar{\pi}(y)-\bar{\mathscr{P}}^{t}(x,y)\right]_{+}$

If equality does not hold, there must exist a non-backtracking long-range path
$\xi$ between $x$ and $y$ or $x$ and $\eta(y)$ for which $w(\xi)>\theta$, in
which case

$\bar{\pi}(y)-\mathbf{P}_{x}\left[X_{t}\in\\{y,\eta(y)\\},w_{x,R,L}(\xi(X_{0}\cdots
X_{t}))\leq\theta\right]\leq\pi(y)\,\mathbbm{1}_{\exists\xi:w_{x,R,L}(\xi)>\theta}\\\
+\pi(\eta(y))\,\mathbbm{1}_{\exists\xi:w_{x,R,L}(\xi)>\theta}.$

We did not precise where $\xi$ lies to ease notation in the indicator
functions but it depends on $y$ and $\eta(y)$ respectively. Combining the two
inequalities we obtain that in either case

$\displaystyle\bar{\pi}(y)-\mathbf{P}_{x}\left[X_{t}\in\\{y,\eta(y)\\},w_{x,R,L}(\xi(X_{0}\cdots
X_{t}))\leq\theta\right]$
$\displaystyle\leq\left[\bar{\pi}(y)-\bar{\mathscr{P}}^{t}(x,y)\right]_{+}+\pi(y)\,\mathbbm{1}_{\exists\xi:w_{x,R,L}(\xi)>\theta}$
$\displaystyle+\pi(\eta(y))\,\mathbbm{1}_{\exists\xi:w_{x,R,L}(\xi)>\theta}.$

By Cauchy-Schwarz inequality,

$\sum_{y\in
V}\pi(y)\mathbbm{1}(\exists\xi:w_{x,R,L}(\xi)>\theta)\leq\left(\sum_{y\in
V}\pi(y)^{2}\right)^{1/2}\left(\sum_{\xi}\mathbbm{1}(w_{x,R,L}(\xi)>\theta)\right)^{1/2},$

where the second sum is over non-backtracking long-range paths from $x$. By
Remark 3.2 weights sum up to at most $1$ hence so this sum contains at most
$\theta^{-1}$ positive terms and

$\mathbf{P}_{x}\left[X_{t}=y,w_{x,R,L}(\xi(X_{0}\cdots
X_{t}))>\theta\right]\leq\left\|\bar{\mathscr{P}}^{t}(x,\cdot)-\bar{\pi}\right\|_{\mathrm{TV}}+\sqrt{\frac{1}{\theta}\sum_{y\in
V}\pi(y)^{2}}.$ (20)

To complete the proof, let $\varepsilon\in(0,1)$ and specialize to $t:=\log
n/h-C_{1}\sqrt{\log n}$ and $\theta:=n^{-1}\exp(C_{2}\sqrt{\log n})$ for some
$C_{1}(\varepsilon)$, $C_{2}(\varepsilon)>0$. Choosing the constant $C_{1}$
large enough, $\exp(-th-
C_{h}(\varepsilon)\sqrt{t})=n^{-1}\exp((C_{1}-C_{h}/\sqrt{h})\sqrt{\log
n}-o(\sqrt{\log n}))>\theta$ for large enough $n$, hence Proposition 3.1
implies that the left hand-side of (20) is at least $1-\epsilon$ with high
probability. On the other hand, as explained in the proof outline (Section
1.4) the boundedness assumptions (H1), (H2) imply that $\pi(x)=\Theta(1/n)$
for all $x\in V$. Hence the square-root term in the right hand side is $o(1)$.
All in all, this proves that with high probability,

$\left\|\bar{\mathscr{P}}^{t}(x,\cdot)-\bar{\pi}\right\|_{\mathrm{TV}}\geq
1-\epsilon.$

∎

######  Remark 3.3.

From the explicit formula for the measure $\hat{\pi}$ (18), we can show it can
be decomposed as $\hat{\pi}=\hat{\pi}_{1}+\hat{\pi}_{2}$ with

$\sum_{x\in V}\hat{\pi}_{1}^{2}=o_{\mathbb{P}}((\log
n)^{b}/n),\qquad\hat{\pi}_{2}(V)=o_{\mathbb{P}}(1)$

for some $b>0$. This is sufficient to prove the lower bound on the mixing time
without resorting to the explicit knowledge of the invariant measure $\pi$, as
we know $\hat{\pi}$ is close to $\pi$ in total variation (19) and the proof
only used the fact that $\pi$ has a small $\ell^{2}$ norm.

######  Remark 3.4.

Let us comment on how the proof also accomodates the superposition of simple
graphs. Observe that if two edges are aligned under the matching $\eta$, ie if
there exist $x,y\in V$ such that $P(x,y)>0$ and $P(\eta(x),\eta(y))>0$, these
constitute an obstruction to the quasi-tree likeness of the neighbourhood of
$x$. As the nice trajectories considered in Proposition 3.2 require having a
quasi-tree-like neighbourhood, they avoid in particular these edges, so it
makes no difference in the end to adjust the conductances of these edges or
not.

##  4 Analysis on the quasi-tree on quasi-trees I: escape probabilities

The objective of the three following sections is to prove the concentration of
the drift and entropy, along with the other nice properties of Section 3, for
the Markov chain $(\mathcal{X}_{t})_{t\geq 0}$ on a random infinite quasi-tree
$\mathcal{G}$, that will allow us to deduce the corresponding statements
thanks to the coupling presented in Section 2.5. As in [10, 39], the argument
is based on the existence of regeneration times, which in the infinite setting
can be defined as times at which $\mathcal{X}_{t}$ visits a long-range edge
for the first and last time. A first step towards this objective is to lower
bound the probability of escaping to infinity in the quasi-tree, which is the
object of this whole section.

###  4.1 Escape probabilities

The following notations will be used for the three next sections.
$\mathcal{G}$ will denote a random quasi-tree, which under $\mathbb{P}$ has
the law of the quasi-tree described in Section 2.5. Its vertex set is
$\mathcal{V}$.

######  Definition 4.1.

Given a non-center vertex $x\in\mathcal{V}$, let

$q_{\mathrm{Esc}}(x):=\mathbf{P}_{x}\left[\forall t\geq
1:\mathcal{X}_{t}\in\mathcal{G}_{x}\right].$

be the quenched probability that the chain enters the subquasi-tree of $x$ and
never leaves it. If $x$ is a center, it is useful to also consider starting at
time $1/2$ and let

$q_{\mathrm{Esc}}(x):=\mathbf{P}_{x}\left[\forall t\geq
0:\mathcal{X}_{t}\in\mathcal{G}_{x}\right]\wedge\mathbf{P}\left[\left.\tau_{\eta(x)}=\infty\
\right|\ \mathcal{X}_{1/2}=x\right].$

We call these quantities the _escape probability_ at $x$.

######  Remark 4.1.

Note that if $x$ is not a center,

$q_{\mathrm{Esc}}(x)\geq q(x,\eta(x))\mathbf{P}\left[\left.\tau_{x}=\infty\
\right|\ \mathcal{X}_{1/2}=\eta(x)\right].$

Similarly, if $x$ is a center, Assumption (H3) asserts there exists $y\neq x$
in the same small-range component as $x$, so that

$\mathbf{P}_{x}\left[\forall t\geq
0:\mathcal{X}_{t}\in\mathcal{G}_{x}\right]\geq
p(x,\eta(x))\,P(x,y)\,q_{\mathrm{Esc}}(y).$

By Assumptions (H1) and (H2) the entries of $p$ and $q$ are bounded. Thus to
lower bound escape probabilities, it matters little to consider a center
vertex or not, and to start at integer or half-integer time.

In [39], the authors prove in their model that the escape probability is lower
bounded uniformly in $n$, conditional on $\mathcal{G}$. This extends to the
reversible case thanks to a comparison argument.

######  Proposition 4.1.

There exists a constant $q_{0}>0$ such that for all realization of
$\mathcal{G}$, for all $x\in\mathcal{V}$ $q_{\mathrm{Esc}}(x)\geq q_{0}$.

###  4.2 Lower bound on escape probabilities

We now establish Proposition 4.1. The proof is based on ideas to prove
transience of a Markov chain, which is fundamental for our purpose and is
already not clear in our model. The reversibility assumption augments
considerably the available toolbox. In particular Rayleigh’s monotonicity
principle is a well-known result which states that the effective conductance
to infinity increases monotonically with individual conductances (see
[49][Chapter 2]). While this result is generally used qualitatively to
establish transience or recurrence of a given chain, it is used here to obtain
a quantitative comparison between escape probabilities.

Let us recall briefly the notions we are going to use. We refer to
[49][Chapters 2, 3, 5] for a detailed account. Let $(\mathcal{Y}_{t})_{t\geq
0}$ be an irreducible, reversible Markov chain on a state space $W$, with
reversible measure $\mu$, represented as a random walk on an electrical
network with vertex set $W$ and $c$ a family of conductances on the edges of
this graph. We write hitting times as $\tau$, return times as $\tau^{+}$, with
the corresponding subset or vertex as index. A classical result for reversible
chains is that for $a\in W$ and $Z\subset W$, the probability to reach before
$Z$ before returning to $a$ can be expressed as

$\mu(a)\mathbb{P}_{a}\left[\tau_{Z}<\tau_{a}^{+}\right]=\mathscr{C}(a\leftrightarrow
Z)$

where $\mathscr{C}(a\leftrightarrow Z)$ is the effective conducance between
$a$ and $Z$, which can be computed using network reductions. If $W$ is
infinite, we can very well take $Z=\\{\infty\\}$ thanks to a limit argument,
to obtain

$\mu(a)\mathbb{P}_{a}\left[\tau_{a}^{+}=\infty\right]=\mathscr{C}(a\leftrightarrow\infty)$
(21)

In particular the chain is transient if and only if
$\mathscr{C}(a\leftrightarrow\infty)>0$. Effective conductances satisfy a
simple yet powerful monotonicity property, in that they are monotonous with
respect to individual conductances. This is called Rayleigh’s monotonicity
principle, see p.35 of [49]. This monotonicity can be made quantitative as
follows. The proof is identical to that of [49][p.35].

######  Lemma 4.1.

Let $G$ be an infinite connected graph with vertex set $W$ and two sets of
conductances $c_{1},c_{2}$ Suppose there exists $\lambda>0$ such that
$c_{1}\geq\lambda c_{2}$ edge-wise. Then for all $a\in W$

$\mathscr{C}_{1}(a\leftrightarrow\infty)\geq\lambda\mathscr{C}_{2}(a\leftrightarrow\infty).$

######  Remark 4.2.

If $G^{\prime}\subset G$ is a subgraph, one can always consider the Markov
chain on $G$ to have state space $W$ as well by setting zero conductances
outside $G$. The lemma thus gives in particular quantitative comparisons
between a reversible chain and the chain restricted to a subnetwork.

The last required notion is that of branching number. The branching number
$\mathrm{br}\ T$ is a parameter than can be associated to any tree $T$ that
basically counts the average number of children per vertex. For instance for a
$d$-regular tree, $d\geq 1$, the branching number is $d-1$. We refer to [49]
for a more general definition. We will only need the following facts, which
can be found in Chapters 3 and 5 of the same reference (the first point is not
proved but follows from the definition on the branching number):

######  Proposition 4.2.

  1. 1.

Given a tree $T$ and $k\geq 1$, let $T^{(k)}$ be the tree obtained by keeping
only the vertices of $T$ which are at depth a multiple of $k$ from the root,
and where vertices are joined by an edge if one is the ancestor of the other
in $T$. Then $\mathrm{br}\ T^{(k)}=(\mathrm{br}\ T)^{k}$.

  2. 2.

The simple random walk on a tree $T$ is transient if and only if $\mathrm{br}\
T>1$

  3. 3.

Conditional on non-extinction, the branching number of a supercritical Galton-
Watson tree is a.s. equal to its average offspring.

###### Proof of Proposition 4.1.

We prove that the root has uniformly lower bounded escape probability, but the
same arguments can be applied to any vertex of the quasi-tree. Recall the
equivalence relation $x\simeq\eta(x)$ on $\mathcal{V}$ which identifies the
endpoints of each long-range edge. Note that the chain $\mathcal{X}$ is not
reversible but only its projection $\bar{\mathcal{X}}$ to $\mathcal{V}/\sim$.
Clearly, lower bounding the escape probabilities of $\mathcal{X}$ or
$\bar{\mathcal{X}}$ is equivalent. Consider the graph obtained by pruning the
long-range edges of $\mathcal{G}_{O}$ and adding an edge $(\dagger,O)$ between
an extra vertex $\dagger$ and the root. Then consider the Markov chain
$\tilde{\mathcal{X}}$ which goes from $\dagger$ to $O$ with probability $1$
and otherwise has the same transition probabilities as $\bar{\mathcal{X}}$,
with the probability of going from $O$ to $\dagger$ being that of
$\bar{\mathcal{X}}$ leaving the image of $\mathcal{G}_{O}$ in the quotient.
Since $\bar{\mathcal{X}}$ is reversible, the chain $\tilde{\mathcal{X}}$ is
also a reversible chain. Letting $\tau_{\dagger},\tau_{\dagger}^{+}$ denote
the hitting and return time to $\dagger$ of the chain $\tilde{\mathcal{X}}$,
(21) implies

$\mathbf{P}_{O}\left[\tau_{\dagger}=\infty\right]=\mathbf{P}_{\dagger}\left[\tau_{\dagger}^{+}=\infty\right]=\frac{\mathscr{C}_{\tilde{\mathcal{X}}}(\dagger\leftrightarrow\infty)}{\mu(\dagger)}$

where $\mathscr{C}_{\tilde{\mathcal{X}}}(\dagger\leftrightarrow\infty)$ is the
effective conductance for the chain $\tilde{\mathcal{X}}$, and $\mu$ is the
invariant measure defined by the conductances $\tilde{c}$ of
$\tilde{\mathcal{X}}$, that is $\mu(x)=\sum_{y\in\mathcal{V}}\tilde{c}(x,y)$
($\mu$ does not need to be a probability measure here). By assumptions (H1)
and (H2), conductances and degrees are bounded uniformly in $n$ thus so is
$\mu(\dagger)$ and it suffices to lower bound the effective conductance. Now
let $\mathcal{V}^{\prime}$ be the set of vertices in $\mathcal{G}_{O}$ that
are at distance at most $2$ from their centers and consider any spanning tree
$\mathcal{T}$ of the subgraph spanned by $\mathcal{V}^{\prime}$. Let
$\tilde{\mathcal{T}}$ be the graph spanned by its projection in
$\mathcal{V}/\sim$ together with the edge $(\dagger,O)$, which remains a tree,
and $\mathscr{C}_{\tilde{\mathcal{T}}}(\dagger\leftrightarrow\infty)$ the
effective conductance of the simple random walk on $\tilde{\mathcal{T}}$. Then
as conductances of $\tilde{\mathcal{X}}$ are bounded Lemma 4.1 implies that

$\mathscr{C}_{\tilde{\mathcal{X}}}(\dagger\leftrightarrow\infty)\geq\lambda\mathscr{C}_{\tilde{\mathcal{T}}}(\dagger\leftrightarrow\infty)$

where $\lambda>0$ is a constant independent of $n$.

We claim now $\mathscr{C}_{\tilde{\mathcal{T}}}(\dagger\leftrightarrow\infty)$
is bounded away from $0$ by a universal constant, which will prove the result.
Observe that the tree $\mathcal{T}$ must contain every long-range edge leaving
from a vertex of $\mathcal{V}^{\prime}$. Hence $\mathcal{T}$ has no leaves and
every vertex other than $O$ has degree at least $2$. Furthermore, from
Assumption (H3), each small-range component in $\tilde{\mathcal{G}}$ contains
at least two vertices and every other which identifies with a component of
$V_{1}$ actually contains at least three vertices. In these $V_{1}$
components, there is thus a vertex which is connected to a long-range edge and
at least two other vertices. Consequently, we can see that every sequence of
three consecutive vertices in $\tilde{\mathcal{T}}$ contains at least one
vertex with degree more than $3$. This implies that the power tree
$\tilde{\mathcal{T}}^{(3)}$, as defined in Proposition 4.2, contains the
$2$-forward regular tree $T_{2}$, ie the tree where every vertex has $2$
children. From Proposition 4.2 $\tilde{\mathcal{T}}$ contains thus a subtree
with branching number $2^{1/3}>1$, so the simple random walk on
$\tilde{\mathcal{T}}$ is transient. Using again Lemma 4.1, we can in the end
lower bound $\mathscr{C}_{\tilde{\mathcal{T}}}(O\leftrightarrow\infty)$ by a
universal constant. ∎

######  Remark 4.3.

The proof shows more generally that any reversible Markov chain supported by a
quasi-tree, (whether it makes half-integer time steps or not) is transient and
has uniformly lower bounded escape probabilities, provided the quasi-tree is
sufficiently branching.

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

Propositions 4.1 implies in particular that the Markov chain
$(\mathcal{X}_{t})_{t\geq 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. The regeneration process will also be used later to compute the
approximate invariant measure $\hat{\pi}$.

###  5.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.1.

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

$\mathbb{P}\left[\left.Y_{k}=y,Z_{k}=z\ \right|\
Y_{k-1}=x,Z_{k-1},\ldots,Y_{0},Z_{0}\right]=\mathbb{P}\left[\left.Y^{\prime}_{1}=y,Z^{\prime}_{1}=z\
\right|\ Y_{0}=x\right],$ (M1)

where $(Y^{\prime}_{1},Z^{\prime}_{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\geq 0}$ is a Markov chain on
$S$.

A _Markov renewal process_ is a process $(Y_{k},T_{k})_{k\geq 0}$ is a process
taking values in $S\times\mathbb{N}$ such that $(Y_{k},T_{k}-T_{k-1})_{k\geq
0}$ satisfies (M1) and $T_{k}-T_{k-1}\geq 1$ a.s. for all $k\geq 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\geq 1}$, where
for each $t\geq 1$,

$Q_{t}(x,y):=\mathbb{P}\left[\left.Y_{1}=y,T_{1}=t\ \right|\
Y_{0}=x,T_{0}=0\right]=\mathbb{P}\left[\left.Y_{1}=y,T_{1}-T_{0}=t\ \right|\
Y_{0}=x\right].$

Notice then that $Y$ has transition kernel $Q:=\sum_{t\geq 1}Q_{t}$.

######  Remark 5.1.

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}\left[\left.\cdot\ \right|\
Y_{0}=y,Z=z\right]\nu(y,dz).$

On the other hand, the (M1) implies that $(Y_{k},Z_{k})_{k\geq 1}$ conditional
on $Y_{0}$ is independent of $Z_{0}$. Thus if we are interested in a quantity
that is measurable only with respect to $(Y_{k},Z_{k})_{k\geq 1}$, we will
slightly abuse notation by writing
$\mathbb{P}_{u}:=\mathbb{P}\left[\left.\cdot\ \right|\ Y_{0}=u\right]$ (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\geq 1}$ becomes stationary under $\mathbb{P}_{\mu}$.
In the sequel if $Y$ is positive recurrent, we only consider invariant
measures which are probability distributions.

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 and can be proved in the same way.

######  Proposition 5.1.

Let $(Y,T)$ be a Markov renewal process with state space $S$. Suppose $Y$ is
positive recurrent with stationary distribution $\mu$ and $\max_{u\in
S}\mathbb{E}_{u}\left[T_{1}\right]<\infty$. Given $t\geq 0$ let

$N_{t}:=\sup\\{k\geq 0,T_{k}\leq t\\}.$

Then a.s.

$\lim_{k\rightarrow\infty}\frac{T_{k}}{k}=\mathbb{E}_{\mu}\left[T_{1}\right]$

and

$\lim_{t\rightarrow\infty}\frac{N_{t}}{t}=\frac{1}{\mathbb{E}_{\mu}\left[T_{1}\right]}.$

###### Proof of Proposition 5.1.

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\geq 0}$, with
$T_{-1}:=0$, which by definition satisfies (M1). It was noted in Remark 5.1
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\geq 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\geq 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\geq 1}$ has the distribution of $(Y_{k})_{k\geq 0}$,
given $Y_{0}=U_{0}$. The number of jumps $N_{t}$ made before time $t\geq 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\rightarrow\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\geq 0}$. As can be checked easily, it is given by:

$\tilde{\mu}(x,t)=\frac{\mathbb{P}_{\mu}\left[X_{1}=y,T_{1}>t\right]}{\mathbb{E}_{\mu}\left[T_{1}\right]}$
(22)

for all $x\in S,t\geq 0$. In particular
$\tilde{\mu}(S\times\\{0\\})=\mathbb{E}_{\mu}\left[T_{1}\right]^{-1}$. ∎

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}$
in Proposition 3.2. Proposition 5.3 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.2, 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 abouts its starting state.

######  Proposition 5.2.

Let $(Y_{k},T_{k}-T_{k-1})_{k\geq 0}$ satisfy (M1), with $T_{-1}:=0$ and
$T_{k}-T_{k-1}\in\mathbb{Z}$ a.s. for all $k\geq 0$. Suppose $Y$ is positive
recurrent, irreducible and aperiodic. Let
$Q_{t}(x,y):=\mathbb{P}\left[\left.Y_{1}=y,T_{1}-T_{0}=t\ \right|\
Y_{0}=x\right]$ for all $t\in\mathbb{Z}$ and

$\alpha:=\min_{x\in S}\sum_{\begin{subarray}{c}t\in\mathbb{Z}\\\ y\in
S\end{subarray}}\left(Q_{t}(x,y)\wedge Q_{t+1}(x,y)\right).$

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

$\sup_{\nu}\mathbb{P}_{\nu}\left[\left|T_{0}-T^{\prime}_{0}\right|>K(\varepsilon)\right]\leq\varepsilon,$

where the supremum is over all couplings
$((Y_{0},T_{0}),(Y^{\prime}_{0},T^{\prime}_{0}))$ of $\nu_{1}$ and $\nu_{2}$.
Then for all $\varepsilon\in(0,1)$, there exists $C(\varepsilon)\geq 0$ such
that

$\left\|\mathbb{P}_{\nu_{1}}\left[(Y_{k},T_{k})=\cdot\right]-\mathbb{P}_{\nu_{2}}\left[(Y_{k},T_{k})=\cdot\right]\right\|_{\mathrm{TV}}\leq\varepsilon$

for all

$k\geq\frac{C(\varepsilon)}{\alpha}\left(t_{\mathrm{mix}}^{(Y)}(\varepsilon)\max_{u\in
S}\mathbb{E}_{u}\left|T_{1}\right|+K(\varepsilon)\right)^{2}.$ (23)

###### Proof of Proposition 5.2.

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}\left[\tau>k\right]\leq CA/\sqrt{k}$ for
some constant $C>0$. The argument can be found in [45] and [44][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^{\prime},T^{\prime}))$ is a coupling of two versions of the
process $(Y_{k},T_{k})_{k\geq 0}$ started at $\nu_{1}$ and $\nu_{2}$
respectively. Let $\tau:=\inf\\{k\geq
0:(Y_{k},T_{k})=(Y^{\prime}_{k},T^{\prime}_{k})\\}$. If the coupling is such
that the two processes coincide after the coalescence time $\tau$, one has

$\left\|\mathbb{P}\left[(Y_{k},T_{k})=\cdot\right]-\mathbb{P}\left[(Y^{\prime}_{k},T^{\prime}_{k})=\cdot\right]\right\|_{\mathrm{TV}}\leq\mathbb{P}\left[\tau>k\right].$

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

$\mathbb{P}\left[Y_{k_{0}}\neq
Y^{\prime}_{k_{0}}\right]=\left\|\mathbb{P}\left[Y_{k_{0}}=\cdot\right]-\mathbb{P}\left[Y^{\prime}_{k_{0}}=\cdot\right]\right\|_{\mathrm{TV}}\leq
2\left\|\mathbb{P}\left[Y_{k_{0}}=\cdot\right]-\mu\right\|_{\mathrm{TV}}\leq
2\varepsilon,$ (24)

where $\mu$ is the stationary measure of $Y$. Then for all $k\geq k_{0}$,
conditional on $Y_{k}=Y^{\prime}_{k}$ draw
$Y_{k+1},Y^{\prime}_{k+1},S_{k+1},S^{\prime}_{k+1}$ according to the
distribution:

$\displaystyle\mathbb{P}\left[\left.Y_{k+1}=Y^{\prime}_{k+1}=y,S_{k+1}=t-1,S^{\prime}_{k+1}=t\
\right|\ Y_{k}=Y^{\prime}_{k}=x\right]=\alpha_{t-1}(x,y)$
$\displaystyle\mathbb{P}\left[\left.Y_{k+1}=Y^{\prime}_{k+1}=y,S_{k+1}=t,S^{\prime}_{k+1}=t-1\
\right|\ Y_{k}=Y^{\prime}_{k}=x\right]=\alpha_{t-1}(x,y)$
$\displaystyle\mathbb{P}\left[\left.Y_{k+1}=Y^{\prime}_{k+1}=y,S_{k+1}=t,S^{\prime}_{k+1}=t\
\right|\
Y_{k}=Y^{\prime}_{k}=x\right]=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}\left[\left.Y_{k+1}=y,S_{k+1}=t\ \right|\
Y_{k}=x\right]=Q_{t}(x,y)=\mathbb{P}_{x}\left[\left.Y^{\prime}_{k+1}=y,S^{\prime}_{k+1}=t\
\right|\ Y^{\prime}_{k}=x\right].$

Therefore if $Y_{k}=Y^{\prime}_{k}$ setting $T_{k+1}:=T_{k}+S_{k+1}$,
$T^{\prime}_{k+1}:=T^{\prime}_{k}+S^{\prime}_{k+1}$ yields a coupling of
$(Y_{k+1},T_{k+1}),(Y^{\prime}_{k+1},T^{\prime}_{k+1})$ with
$Y_{k+1}=Y^{\prime}_{k+1}$. Consequently, this can be used to couple the two
processes $(Y,T),(Y^{\prime},T^{\prime})$ for every step after the coalescence
of $Y$ and $Y^{\prime}$, 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\geq k_{0}:Y_{k}=Y^{\prime}_{k}\\}$ and for all $k\geq
0$, $Z_{k}:=\sum_{i=\tau_{1}}^{k}S_{k}-S^{\prime}_{k}$. Observe that
$(Y_{\tau_{1}+k},Z_{k}-Z_{k-1})_{k\geq 0}$ (with $Z_{-1}:=0$) satisfies the
(M1) property. In addition, for every $k\geq 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}\left[\left.Z_{k+1}-Z_{k}=1\ \right|\ Y_{k}=x\right]=\sum_{t\geq
1}\sum_{y\in S}\alpha_{t}(x,y)\geq\alpha.$ (25)

On the event $\\{\tau_{1}=k_{0}\\}$, for all $k\geq 0$ we can decompose

$T_{k_{0}+k}-T^{\prime}_{k_{0}+k}=T_{k_{0}}-T^{\prime}_{k_{0}}+Z_{k}$

which implies that $\tau=k_{0}+\inf\\{k\geq
0:Z_{k}=T^{\prime}_{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\geq 0$ and $A>0$,

$\displaystyle\mathbb{P}\left[\tau>k_{0}+k\right]\leq\mathbb{P}\left[Y_{k_{0}}\neq
Y^{\prime}_{k_{0}}\right]+\mathbb{P}\left[\left|T_{k_{0}}-T^{\prime}_{k_{0}}\right|>A\right]+\max_{a\in[-A,A]}\max_{u\in
S}\mathbb{P}_{(u,0)}\left[\tilde{\tau}_{a}>k\right].$

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

$\displaystyle\mathbb{P}\left[\left|T_{k_{0}}-T^{\prime}_{k_{0}}\right|>K(\varepsilon)+A\right]$
$\displaystyle\leq\mathbb{P}\left[\left|T_{0}-T^{\prime}_{0}\right|>K(\varepsilon)\right]+\mathbb{P}\left[\left|(T_{k_{0}}-T_{0})-(T^{\prime}_{k_{0}}-T^{\prime}_{0})\right|>A\right].$

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}\left[\left|T_{k_{0}}-T^{\prime}_{k_{0}}\right|>K(\varepsilon)+A\right]\leq\varepsilon+\frac{2k_{0}\max_{u}\mathbb{E}_{u}\left[T_{1}\right]}{A}\leq
2\varepsilon$

for $A:=2k_{0}\max_{u\in S}\mathbb{E}_{u}\left[T_{1}\right]/\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\geq 1$, such that
for all $k\geq 0$

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

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

$\left\|\mathbb{P}\left[(Y_{k},T_{k})=\cdot\right]-\mathbb{P}\left[(Y^{\prime}_{k},T^{\prime}_{k})=\cdot\right]\right\|_{\mathrm{TV}}\leq
5\epsilon$

for

$k\geq
t_{\mathrm{mix}}^{(Y)}(\varepsilon)+\frac{C^{2}(K(\varepsilon)+2t_{\mathrm{mix}}^{(Y)}(\varepsilon)\max_{u\in
S}\mathbb{E}_{u}\left[T_{1}\right])^{2}}{\alpha\varepsilon^{4}},$

proving the result.

Let us now prove the claim: for all $k\geq 1$, let $N_{k}:=\left|\\{i\leq
k:Z_{i}-Z_{i-1}\neq 0\\}\right|$ and define $\tilde{Z}_{k}$ as the sum of the
first $k$ non zero variables $Z_{i}-Z_{i-1}$. By (25), for all $u\in S$,
$N_{k}$ dominates stochastically a binomial random variable
$\mathrm{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^{(\mathrm{SRW})}_{A}$ denote the hitting time of $A$ by $\tilde{Z}$,
[33][III 7.5] shows

$\mathbb{P}_{0}\left[\tau^{(\mathrm{SRW})}_{A}=k\right]=\frac{A}{n}\binom{k}{\frac{A+k}{2}}2^{-k}\leq
C\frac{A}{k^{3/2}},$

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

$\mathbb{P}_{0}\left[\tau^{(\mathrm{SRW})}_{A}>k\right]\leq\frac{C^{\prime}A}{\sqrt{k}}$

for some other constant $C^{\prime}>0$. Thus

$\displaystyle\mathbb{P}_{(u,0)}\left[\tilde{\tau}_{A}>k\right]$
$\displaystyle\leq\mathbb{P}_{u}\left[\tilde{\tau}_{A}>k,N_{k}\geq\alpha
k\right]+\mathbb{P}_{u}\left[N_{k}<\alpha k\right]$
$\displaystyle\leq\mathbb{P}_{0}\left[\tau^{(\mathrm{SRW})}_{A}>\lfloor\alpha
k\rfloor\right]+\mathbb{P}\left[\left|\mathrm{Bin}(k,2\alpha)-2\alpha
k\right|>\alpha k\right]$ $\displaystyle\leq\frac{C^{\prime}A}{\sqrt{\alpha
k}}+\frac{2(1-2\alpha)}{\alpha k}$

using Chebychev’s inequality, which proves the claim. ∎

######  Proposition 5.3.

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

$\sum_{y\in S}\left|\mathbb{P}_{\nu}\left[\exists k\geq
0:Y_{k}=y,T_{k}=t\right]-\frac{\mu(y)}{\mathbb{E}_{\mu}\left[T_{1}\right]}\right|\xrightarrow[t\rightarrow\infty]{}0.$

More precisely, given $\varepsilon\in(0,1)$, let $K_{\nu}(\varepsilon)$ be the
minimal integer such that

$\mathbb{P}_{\nu}\left[T_{0}>K_{\nu}(\varepsilon)\right]\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}\left[\exists k\geq
0:Y_{k}=y,T_{k}=t\right]-\frac{\mu(y)}{\mathbb{E}_{\mu}\left[T_{1}\right]}\right|\leq\varepsilon$

for all

$t\geq\frac{C(\varepsilon)}{\alpha}\left(t_{\mathrm{mix}}^{(Y)}(\varepsilon)\max_{u\in
S}\mathbb{E}_{u}\left[T_{1}\right]+K_{\nu}(\varepsilon)+\frac{\mathbb{E}_{\mu}\left[T_{1}^{2}\right]}{\mathbb{E}_{\mu}\left[T_{1}\right]}\right)^{2}\max_{v}\mathbb{E}_{v}\left[T_{1}\right]$
(26)

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

###### Proof of Proposition 5.3.

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

$u_{t}(\nu,y):=\mathbb{P}_{\nu}\left[\exists k\geq
0:Y_{k}=y,T_{k}=t\right]=\mathbb{P}_{\nu}\left[U_{t}=(y,0)\right]$ (27)

It was proved in the proof of Proposition 5.1 that $U$ has unique invariant
measure given by
$\tilde{\mu}(x,t)=\mathbb{P}_{\mu}\left[Y_{1}=y,T_{1}>t\right]/\mathbb{E}_{\mu}\left[T_{1}\right]$.
Thus if one can prove that $U$ is aperiodic, the convergence theorem for
Markov chains directly implies that
$u_{t}(\nu,y)\rightarrow\tilde{\mu}(y,0)=\mu(y)/\mathbb{E}_{\mu}\left[T_{1}\right]$.
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 (23). By Proposition 5.2 there exists a coupling of two versions of
$(Y,T)$ started at $\nu$ and $\tilde{\mu}$, with coalescence time $\kappa$
such that

$\mathbb{P}\left[\kappa>k_{0}\right]\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

$\left\|\mathbb{P}_{\nu}\left[U_{t}=\cdot\right]-\tilde{\mu}\right\|_{\mathrm{TV}}\leq\mathbb{P}\left[T_{\kappa}>t\right].$

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

$\mathbb{P}\left[T_{\kappa}>t\right]\leq\mathbb{P}\left[\kappa>k_{0}\right]+\mathbb{P}_{\nu}\left[T_{k_{0}}>t\right].$

The first term is bounded by $\varepsilon$. The second term can be bounded by
Markov’s inequality as

$\mathbb{P}_{\nu}\left[T_{k_{0}}>t\right]\leq\frac{k_{0}\max_{u\in
S}\mathbb{E}_{u}\left[T_{1}\right]}{t}\leq\varepsilon$

for $t\geq k_{0}\max_{u\in S}\mathbb{E}_{u}\left[T_{1}\right]/\varepsilon$.
Let us now explicit the value of $k_{0}$. We first bound for the worst
possible coupling of $\nu$ and $\tilde{\mu}$,

$\displaystyle\mathbb{P}\left[\left|T_{0}-T^{\prime}_{0}\right|>K_{\nu}(\varepsilon)+k\right]$
$\displaystyle\leq\mathbb{P}_{\nu}\left[T_{0}>K_{\nu}(\varepsilon)\right]+\mathbb{P}_{\tilde{\mu}}\left[T_{0}>k\right]$
$\displaystyle\leq\varepsilon+\mathbb{E}_{\mu}\left[(T_{1}-k-1)_{+}\right]/\mathbb{E}_{\mu}\left[T_{1}\right]$

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

$\displaystyle\mathbb{E}_{\mu}\left[(T_{1}-k-1)_{+}\right]$
$\displaystyle=\sum_{t\geq k+1}\mathbb{P}_{\mu}\left[T_{1}>t\right]$
$\displaystyle\leq\sum_{t\geq
k+1}\frac{\mathbb{E}_{\mu}\left[T_{1}^{2}\right]}{t^{2}}\leq\frac{C\,\mathbb{E}_{\mu}\left[T_{1}^{2}\right]}{k}$

for some constant $C>0$. Thus
$\mathbb{P}\left[\left|T_{0}-T^{\prime}_{0}\right|>K_{\nu}(\varepsilon)+k\right]\leq
2\varepsilon$ for all $k\geq
C\,\mathbb{E}_{\mu}\left[T_{1}^{2}\right]/(\mathbb{E}_{\mu}\left[T_{1}\right]\varepsilon)$,
which gives the value of $K(\varepsilon)$ in (23) and

$k_{0}\leq\frac{C(\varepsilon)}{\alpha}\left(t_{\mathrm{mix}}^{(Y)}(\varepsilon)\max_{u\in
S}\mathbb{E}_{u}\left|T_{1}\right|+K_{\nu}(\varepsilon)+\frac{\mathbb{E}_{\mu}\left[T_{1}^{2}\right]}{\mathbb{E}_{\mu}\left[T_{1}\right]}\right)^{2}.$

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

$\left\|\mathbb{P}_{\nu}\left[U_{t}=\cdot\right]-\tilde{\mu}\right\|_{\mathrm{TV}}\leq\varepsilon$

for large enough $C(\varepsilon)$. Finally using (27) yields

$\frac{1}{2}\sum_{y\in
S}\left|u_{t}(\nu,y)-\frac{\mu(y)}{\mathbb{E}_{\mu}\left[T_{1}\right]}\right|\leq\varepsilon.$

∎

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 a
countable state space $S$ 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

$\left\langle f\>,\>g\right\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}\ |\ \lambda I-Q\text{ is not
invertible as a bounded linear operator}\\}.$

The adjoint operator of $Q^{\ast}$ is given by

$Q^{\ast}(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 $\mathbbm{1}$ for the constant function equal to
$1$, the fact that $\mu$ is a probability measure implies that
$\mathbbm{1}\in\ell^{2}(S)$ and is an eigenvector of $Q$ associated with the
eigenvalue $1$. The absolute spectral gap of $Q$ is the defined as

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

if $1$ has multiplicity $1$ and $\gamma:=0$ otherwise. It is well known that
the absolute spectral gap is related to mixing properties of $Y$, see for
instance [43, 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\geq
1}\left\\{\frac{\gamma((Q^{\ast})^{k}Q^{k})}{k}\right\\}.$

If $Q$ is reversible obviously $1-\gamma_{ps}=(1-\gamma)^{2}$. The pseudo
spectral gap is a rather natural quantity introduced in [52] but it may have
appeared before-hand in other places under different names. In [16], 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.4 ([52, Prop. 3.4]).

Let $(Y_{k})_{k\geq 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}\left\|\mathbb{P}_{x}\left[Y_{t}=\cdot\right]-\mu\right\|_{\mathrm{TV}}\leq
C\rho^{t}.$

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

$\gamma_{ps}\geq\frac{1-\varepsilon}{t_{\mathrm{mix}}(\varepsilon)}.$

Furthermore if $S$ is finite,

$t_{\mathrm{mix}}(\varepsilon)\leq\frac{1+2\log((2\varepsilon)^{-1})+\log(\mu_{\min}^{-1})}{\gamma_{ps}}$

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.5.

Let $S$ be countable and $E$ a Polish space. Let $(Y_{k},Z_{k})_{k\geq 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\geq 1}$ be a family of functions such that for
all $i\geq 1$, $f_{i}:S\times E\rightarrow\mathbb{R}$ and $\max_{u\in
S}\mathbb{E}_{u}\left[f_{i}(Y_{1},Z_{1})^{2}\right]<\infty$. Then for all
$k\geq 1$

$\operatorname{Var}_{\mu}\left[\sum_{i=1}^{k}f_{i}(Y_{i},Z_{i})\right]\leq\frac{6}{\gamma}\sum_{i=1}^{k}\operatorname{Var}_{\mu}\left[f_{i}(Y_{1},Z_{1})\right].$

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

$\operatorname{Var}_{\mu}\left[T_{k}\right]\leq\frac{6}{\gamma_{ps}}k\operatorname{Var}_{\mu}\left[T_{1}\right].$
(28)

for all $k\geq 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 [52]. 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}\left[f_{i}(Z_{1})\mathbbm{1}_{Y_{1}=y}\right].$

Using matrix notations, for all $i\in[m],x\in S$,
$Q_{i}\mathbbm{1}(x)=\sum_{y\in
S}Q_{i}(x,y)=\mathbb{E}_{x}\left[f_{i}(Z_{1})\right]$. We can suppose without
generality that
$\mathbb{E}_{\mu}\left[f_{i}(Z_{i})\right]=\mathbb{E}_{\mu}\left[f_{i}(Z_{1})\right]=0$,
which can be written matricially as

$\mu Q_{i}\mathbbm{1}=0.$ (29)

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

$\displaystyle\operatorname{Var}_{\mu}\left[\sum_{i=1}^{m}f_{i}(Z_{i})\right]$
$\displaystyle=\sum_{i,j=1}^{m}\mathbb{E}_{\mu}\left[f_{i}(Z_{i})f_{j}(Z_{j})\right]$
$\displaystyle=\sum_{i,j=1}^{m}\mathbb{E}_{\mu}\left[f_{i}(Z_{1})f_{j}(Z_{\left|j-i\right|+1})\right].$

For any $l\geq 1$

$\displaystyle\mathbb{E}_{\mu}\left[f_{i}(Z_{1})f_{j}(Z_{l+1})\right]$
$\displaystyle=\sum_{x,y\in
S}\mu(x)Q_{i}(x,y)\mathbb{E}_{y}\left[f_{j}(Z_{l+1})\right]$
$\displaystyle=\sum_{x,y,z\in S}\mu(x)Q_{i}(x,y)Q^{l}Q_{j}(y,z)$
$\displaystyle=\left\langle
Q_{i}Q^{l}Q_{j}\mathbbm{1}\>,\>\mathbbm{1}\right\rangle_{\mu}$
$\displaystyle=\left\langle
Q_{i}\left(Q^{l}-\mathbbm{1}\mu\right)Q_{j}\mathbbm{1}\>,\>\mathbbm{1}\right\rangle_{\mu}$

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

$\displaystyle\left\langle
Q_{i}(Q-\mathbbm{1}\mu)^{l}Q_{j}\mathbbm{1}\>,\>\mathbbm{1}\right\rangle_{\mu}$
$\displaystyle=\left\langle(Q-\mathbbm{1}\mu)^{l}Q_{j}\mathbbm{1}\>,\>Q_{i}^{\ast}\mathbbm{1}\right\rangle_{\mu}$
$\displaystyle\leq\left\|(Q-\mathbbm{1}\mu)\right\|^{l}\left\|Q_{j}\mathbbm{1}\right\|\left\|Q_{i}^{\ast}\mathbbm{1}\right\|.$

Then by Jensen’s inequality,

$\left\|Q_{j}\mathbbm{1}\right\|^{2}=\sum_{x\in
S}\mu(x)\left|\mathbb{E}_{x}\left[f_{j}(Z_{1})\right]\right|^{2}\leq\mathbb{E}_{\mu}\left[f_{j}(Z_{1})^{2}\right]=\operatorname{Var}_{\mu}(f_{j}(Z_{1})).$

Similarly,

$Q_{i}^{\ast}\mathbbm{1}(y)=\sum_{x\in
S}\frac{\mu(x)Q_{i}(x,y)}{\mu(y)}=\mathbb{E}_{\mu}\left[\left.f_{i}(Z_{1})\
\right|\ Y_{1}=y\right]$

so

$\displaystyle\left\|Q_{i}^{\ast}\mathbbm{1}\right\|^{2}\leq\sum_{y\in
S}\mu(y)\mathbb{E}_{\mu}\left[\left.f_{i}(Z_{1})^{2}\ \right|\
Y_{1}=y\right]=\mathbb{E}_{\mu}\left[f_{i}(Z_{1})^{2}\right]=\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})^{2}\right].$

Hence

$\displaystyle\mathbb{E}_{\mu}\left[f_{i}(Z_{1})f_{j}(Z_{l+1})\right]$
$\displaystyle\leq\left\|(Q-\mathbbm{1}\mu)^{l}\right\|\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]^{1/2}\operatorname{Var}_{\mu}\left[f_{j}(Z_{1})\right]^{1/2}$
$\displaystyle\leq\frac{1}{2}\left\|(Q-\mathbbm{1}\mu)^{l}\right\|\left(\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]+\operatorname{Var}_{\mu}\left[f_{j}(Z_{1})\right]\right).$

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

$\displaystyle\left\|(Q-\mathbbm{1}\mu)^{l}\right\|$
$\displaystyle\leq\left\|(Q-\mathbbm{1}\mu)^{k}\right\|^{\lfloor l/k\rfloor}$
$\displaystyle=(1-k\gamma_{ps})^{\lfloor l/k\rfloor/2}$

Consequently

$\displaystyle\sum_{i\neq
j=1}^{m}\mathbb{E}_{\mu}\left[f_{i}(Z_{1})f_{j}(Z_{\left|j-i\right|+1})\right]$
$\displaystyle\leq\frac{1}{2}\sum_{i\neq
j=1}^{m}\left\|(Q-\mathbbm{1}\mu)^{\left|j-i\right|-1}\right\|\left(\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]+\operatorname{Var}_{\mu}\left[f_{j}(Z_{1})\right]\right)$
$\displaystyle\leq
2\sum_{i=1}^{m}\sum_{l=0}^{\infty}\left\|(Q-\mathbbm{1}\mu)^{l}\right\|\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]$
$\displaystyle\leq
2\sum_{i=1}^{m}\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]\sum_{l=0}^{\infty}(1-k\gamma_{ps})^{\lfloor
l/k\rfloor/2}$ $\displaystyle\leq
4\sum_{i=1}^{m}\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]\sum_{l=0}^{\infty}(1-k\gamma_{ps})^{\lfloor
l/k\rfloor}$
$\displaystyle=\frac{4}{\gamma_{ps}}\sum_{i=1}^{m}\operatorname{Var}_{\mu}\left[f_{i}(Z_{1})\right]$

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

###  5.2 Regeneration structure

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

######  Definition 5.2.

A time $t\in\mathbb{N}+1/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$.

From the uniform lower bound on escape probabilities, it is easy do deduce
there is an infinity of regeneration times and levels, and that these have
exponential tails conditional on the environment.

######  Lemma 5.1.

For any realization of $\mathcal{G}$, for any starting vertex of the chain
$\mathcal{X}$, $L_{1}$ and $T_{1}$ have quenched exponential tails
(independent of $n$).

Frow now on, let $T_{0}:=0,Y_{0}:=\iota(O),L_{0}:=0$ and $(T_{k})_{k\geq 1}$
be the sequence of successive regeneration times of $\mathcal{X}$. For all
$k\geq 1$, define

$Y_{k}:=\iota(\mathcal{X}_{T_{k}-1/2})\qquad L_{k}:=d(O,\mathcal{X}_{T_{k}}).$

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

$\mathbb{Q}_{u}=\mathbb{P}\left[\left.\cdot\ \right|\
\mathcal{X}_{1/2}=\eta(O),\iota(O)=u,\tau_{O}=\infty\right]$

for all $u\in V$.

######  Remark 5.2.

Obviously, the lower bound on escape probabilities of Proposition 4.1 also
holds under the law $\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}\left[\iota(\eta(O))=v\right]=\Theta(1/n).$ (30)

Indeed if $q_{0}>0$ is a constant such that all escape probabilities are lower
bounded by $q_{0}$ for any realization of the quasi-tree then

$\mathbb{Q}_{u}\left[\iota(\eta(O))=v\right]\leq
q_{0}^{-1}\mathbb{P}\left[\left.\eta(O)=v\ \right|\
\iota(O)=u\right]=q_{0}^{-1}/n$

and

$\displaystyle\mathbb{Q}_{u}\left[\iota(\eta(O))=v\right]$
$\displaystyle\geq\mathbb{E}\left[\left.\mathbbm{1}_{\iota(\eta(O))=v}\mathbbm{1}_{\tau_{O}=\infty}\
\right|\ \iota(O)=u,\mathcal{X}_{1/2}=\eta(O)\right]$
$\displaystyle\geq\mathbb{E}\left[\left.\mathbbm{1}_{\iota(\eta(O))=v}\,q_{0}\
\right|\ \iota(O)=u\right]$ $\displaystyle\geq q_{0}/n.$

######  Remark 5.3.

Section 5.1 only considered integer valued processed for the time component of