Hence, we can now suppose that all vectors expressions are given in a basis adapted to $H$, so $H$ is generated by $(a_i e_i)_{i \in [d]}$. Then one easily obtains from the definition of $W$ that

$$ W = \left\{ \left( \frac{k_i}{a_i} \right)_{i=1}^d, k_i \in [0, a_i - 1] \ \forall i \in [d] \right\}. \qquad (3.18) $$

**Lemma 3.4.** There exists constants $c_1, c_2 > 0$ such that the following holds. Let $\rho \in \mathbb{T}_n \setminus \{0\}$ and $y$ be either a point of $W$ or $y = \rho'/n$ with $\rho' \in \mathbb{T}_n \setminus \{0\}$ distinct from $\rho$. Then either $d(\rho/n, y) \ge \epsilon$ or, letting $v$ be the unique representative of $\rho/n - y$ in $B(0, \epsilon)$,

$$ \|v_u\| \ge \frac{c_1}{n^{c_2}}. \qquad (3.19) $$

where $v = v_s + v_u$ is the decomposition of $v$ into stable and unstable component.

*Proof.* Consider the case of $y = w \in W$. Then there exist integers $(k_i)_{i=1}^d$ such that $w = \left(\frac{k_i}{a_i}\right)_{i=1}^d$ while $\rho = (\rho_i)_{i \in [d]} \in \mathbb{T}_n \setminus \{0\}$. Suppose that $d(\rho/n, w) < \epsilon$. Assuming that $n$ is coprime with the $a_i$, it is impossible to have $\rho/n = w$ and furthermore any non-zero coordinate has absolute value

$$ |(\rho/n - w)_i| = \left| \frac{\rho_i a_i - k_i n}{a_i n} \right| \ge \frac{1}{a_i n}. $$

By equivalence of norms we deduce there exists a constant $c_1 = c_1(A, a_i) \in (0, 1)$ such that

$$ \|v\| = \|\rho/n - w\| \ge \frac{c_1}{n}. $$

Since the norm is adapted, this implies that $\|v_u\| \ge c_1/n$, in which case the claimed result holds, or $\|v_s\| \ge c_1/n$. In that case, one still has $\|v_s\| \le \epsilon$. Thus for $k > \log n / \log(\lambda^{-1})$ and $n$ large enough,

$$ \|A^k v_s\| \le \lambda^k \|v_s\| < \frac{c_1}{n}. $$

Now if $\|A^l v\| < \epsilon$ for all $0 \le l \le k$, then $A^k v$ is the representative in $B(0, \epsilon)$ of $A^k \rho/n - A^k w$. Since the sets $\{\rho'/n, \rho' \in \mathbb{T}_n \setminus \{0\}\}$ and $W$ are left invariant by $A$, $A^k v$ must also satisfy:

$$ \|A^k v\| \ge \frac{c_1}{n}. $$

From the choice of $k$ we deduce that $\|A^k v_u\| \ge c_1/n$. Then $\|A^k v_u\| \le \|A\|^k \|v_u\|$ yields

$$ \|v_u\| \ge \frac{c_1}{\|A\|^k n} = \frac{c_1}{n^{1+\log \|A\| / \log \lambda^{-1}}}. $$

Finally if $A^l v$ leaves the ball $B(0, \epsilon)$ for some $0 \le l \le k$, it can only expand in the unstable direction so necessarily $\|A^l v_u\| \ge \epsilon \ge c_2/n$ for $n$ large enough and the same conclusion holds.

The case $y = \rho'/n$ is proved similarly. $\square$
Let us now turn to symbolic representations. Consider a Markov partition $\mathcal{R}$ associated to $A^\top$, of diameter $\delta$ determined later on, as given by Proposition 3.3. Let $m := |\mathcal{R}|$ be the number of rectangles and $(\Omega, \pi)$ the symbolic representation given by the Markov partition (Proposition 3.4). Consider the set $\mathcal{R}_0$ of rectangles which contain a point of $W$ and set $\mathcal{R}_1 := \mathcal{R} \setminus \mathcal{R}_0$. We define

$$ \delta_0 := \min \left( \epsilon_c, \frac{\min_{x \neq y \in W} d(x, y)}{1 + \|A^\top\|} \right), $$

which is positive by finiteness of $W$. From now on, we identify $[m]$ with the set of rectangles $\mathcal{R}$. In particular, given a sequence $\omega \in \Omega$, we will write $\omega_k \in \mathcal{R}_0$ to indicate that $R_{\omega_k} \in \mathcal{R}_0$. Similarly, we may use the words letters and rectangles interchangeably.

**Lemma 3.5.** Suppose the diameter of the partition satisfies $\delta < \delta_0$. Then

(i) for all $i \in \mathcal{R}_0$, there exists a unique $j \in \mathcal{R}_0$ such that $A(i, j) = 1$;

$$ (ii) \qquad W = \{ \pi(\omega) : \forall k \in \mathbb{Z}, \omega_k \in \mathcal{R}_0 \}. $$

*Proof.* We start proving (ii).

One inclusion in (ii) is easy. For all $w \in W$ by surjectivity of $\pi$ there exists $\tau \in \Omega$ such that $w = \pi(\tau)$. Then by definition of $\pi$, $(A^\top)^k w \in R_{\tau_k}$ for all $k \in \mathbb{Z}$. However $W$ is invariant by $A^\top$, so by definition of $\mathcal{R}_0$, $\tau_k \in \mathcal{R}_0$. This holds for every sequence $\tau \in \pi^{-1}(w)$.

Conversely, suppose $\tau \in \Omega$ is such that $\tau_k \in \mathcal{R}_0$ for all $k \ge 0$ and let $x = \pi(\tau)$. Then for all $k \ge 0$ there exists $w_k \in R_{\tau_k} \cap W$ at distance at most $\delta$ from $(A^\top)^k x$. The sequence $(w_k)_{k \ge 0}$ is a $\delta(1 + \|A^\top\|)$-pseudo orbit, in the sense

$$ \forall k \ge 0 \quad d(w_{k+1}, A^\top w_k) \le d(w_{k+1}, (A^\top)^{k+1} x) + d(A^\top (A^\top)^k x, A^\top w_k) \\ \le (1 + \|A^\top\|)\delta. $$

Therefore if $\delta(1 + \|A^\top\|) < \min_{x \neq y \in W} d(x, y)$, the sequence $(w_k)_{k \in \mathbb{Z}}$ is necessary the orbit of a point $w \in W$. Then we obtain $d((A^\top)^k x, (A^\top)^k w) \le \delta$ for all $k \in \mathbb{Z}$. If $\delta \le \epsilon_c$, Proposition 3.2 implies $x = w$. Hence $x \in W$.

We now prove (i). Consider $i \in \mathcal{R}_0$. By definition $R_i$ must contain a point $w \in W$. From Proposition 3.5 (i), $w$ admits a symbolic representation $\tau$ such that $\tau_0 = i$. Let $j := \tau_1$. Then $A(i, j) = 1$ and $R_j$ contains $A^\top w \in W$ so $j \in \mathcal{R}_0$. This proves existence.

Suppose now $A_{i,j'} = 1$ with $j' \in \mathcal{R}_0$. By the existence results one can find for all $l \ge 2$ $\tau^{(l)} \in \Omega$ such that $\tau_0^{(l)} = i, \tau_1^{(l)} = j'$ and $\tau_k^{(l)} \in \mathcal{R}_0$ for all $k \le l$. By
compactness of $\Omega$, $(\tau^{(l)})_l$ admits a subsequence converging towards $\tau' \in \Omega$, which satisfies $\tau'_0 = i, \tau'_1 = j'$ and $\tau'_k \in \mathcal{R}_0$ for all $k \ge 0$. By (ii), $\pi(\tau') =: w'$ is a point of $W$ which is also in the rectangle $R_i$. However notice that $\delta < \delta_0 < \min_{x \ne y \in W} d(x, y)$ so every rectangle of the Markov partition contains at most one point of $W$ and necessarily $w' = w$. We thus proved that $\tau, \tau'$, or any other sequence in $\mathcal{R}_0^Z$ starting with $i$, represent the same element $w$. A last observation to make is that by Proposition 3.5 (ii), $\tau, \tau'$ are periodic sequences. Thus $\tau, \tau'$ are the concatenation infinitely many times of a same block of finite size, say $B$ for $\tau$ and $B'$ for $\tau'$. Substituting any block $B$ by a block $B'$ and vice versa, one obtains other representations of $w$. Since $\pi$ is finite-to-one, there can only be finitely many such representations, which implies $B = B'$ and in particular $j = j'$. Hence uniqueness.

□

Given an integer $k \ge 1$, $\xi \in \mathbb{T}^d$ and a symbolic representation $\omega = (\omega_i)_{i \ge 0} \in \pi^{-1}(\xi)$ of $\xi$. we decompose $\omega$ into blocks of $k$ letters: $B_i(\omega) := \omega_{(i-1)k} \cdots \omega_{ik-1}$, which we call $k$-blocks. We set $B_i(\xi) := \{B_i(\omega), \omega \in \pi^{-1}(\xi)\}$ to be the set of all blocks that are the $i$-th block of some symbolic representation of $\xi$. When considering $\xi = \rho/n$, we may simply write $B_i(\rho)$ instead of $B_i(\rho/n)$.

**Lemma 3.6.** Let $\mathcal{R}$ be a Markov partition of diameter $\delta < \delta_0$, and some constant $c$. For all $n \ge 1$ let

$$k = 1 + \left\lceil \frac{c_2}{\log \lambda^{-1}} \log n \right\rceil. \qquad (3.20)$$

and decompose symbolic representations into blocks of $k$ letters. For large enough $n$:

(i) For all $\rho \in \mathbb{T}_n \setminus \{0\}$, every block of $B_1(\rho)$ contains at least one letter in $\mathcal{R}_1$.

(ii) The sets of blocks $(B_1(\rho)_{\rho \in \mathbb{T}_n})$ are all disjoint.

(iii) The family $(B_i(\rho)_{\rho \in \mathbb{T}_n})$ is independent of $i \in \mathbb{Z}$.

*Proof.* (i) Consider any symbolic representation $\omega$ of $\rho \ne 0$. If $\omega_0, \dots, \omega_k \in \mathcal{R}_0$, from the proof of Lemma 3.5 (i), there exists $\omega' \in \Omega$ with $\omega'_l = \omega_l$ for all $0 \le l \le k$ and $\omega'_l \in \mathcal{R}_0$ for all $l \in \mathbb{Z}$. Lemma 3.5 (ii) tells us that $\pi(\omega') =: w$ is a point of $W$. $w$ is at distance at most $\delta$ from $\rho/n$ so we can consider the unique representative $v$ of $\rho/n - w$ in $B(0, \epsilon_c)$. Since $\omega, \omega'$ coincide up to rank $k$, (3.7) yields $\|v_u\| \le \epsilon_c \lambda^k$, which contradicts (3.19) for $k \ge c_2 / \log \lambda^{-1} \log n$ and $n$ large enough. Hence for $k$ as in (3.20) $\omega_l \in \mathcal{R}_1$ for some $0 \le l \le k-1$.

(ii) The proof is the same as (i), since if $\rho, \rho' \in \mathbb{T}_n$ are distinct, $\rho/n - \rho'/n$ has unstable component lower bounded by $\min(\epsilon_c, c_1 n^{-1-c_2})$ by Lemma 3.4.
(iii) The matrix $A^T$ is a bijection on $\mathbb{T}_n \setminus \{0\}$, so the shift by $k$ letters on $\Omega$ induces a permutation on the blocks.

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

The rest of the proof is now similar to the original argument of Chung, Diaconis and Graham [49]. Let $k$ be as in (3.20).

By definition, rectangles of $\mathcal{R}_1$ are closed sets which contain no point of $W$, and $\mathcal{R}_1$, $W$ are both finite sets, thus $\eta := \min_{R \in \mathcal{R}_1} d(R, W)$ must be positive. By equation (3.16) and the continuity of the function $f$ (3.13), there exists $\gamma = \gamma(\eta, \alpha) \in (0, 1)$ such that $f$ is bounded by $\gamma$ on the compact set $\{\xi \in \mathbb{T}_d, d(x, W) \ge \eta\}$. In particular $f(\rho/n) \le \gamma$ if $\rho/n$ is contained in a rectangle of $\mathcal{R}_1$.

Combining this observation with Lemma 3.6 and equation (3.14), we deduce that for all $\rho \in \mathbb{T}_n \setminus \{0\}$, for all $r \ge 0$

$$ \begin{aligned} |\overline{Pr^{k'+d}}(\rho)|^2 &\le \gamma^{g(\rho/n)} \\ &\le \prod_{i=1}^{r} \gamma^{g(B_i(\rho/n))} \end{aligned} $$

where $g(\rho/n)$ is the number of letters in $\mathcal{R}_1$ appearing in the first $rk$ letters of any symbolic representation of $\rho/n$, and $g(B_i(\rho/n))$ is the maximal number of letters in $\mathcal{R}_1$ appearing in the $i$-th $k'$-block of some symbolic representation of $\rho/n$.

As in [49], we then make use of the following interchange lemma in order to regroup similar blocks when summing over $\rho \ne 0$: for all $a \le a'$, $b \le b'$,

$$ \gamma^{a+b'} + \gamma^{a'+b} \le \gamma^{a+b} + \gamma^{a'+b'} \qquad (3.21) $$

Using point (iii) of Lemma 3.6, we deduce the bound

$$ \sum_{\rho \ne 0} |\overline{Pr^{k+d}}(\rho)|^2 \le \sum_{\rho \ne 0} \gamma^{rg(B_1(\rho/n))} $$

Then, using point (i) and (ii) of Lemma 3.6, this sum can be bounded by the sum over all blocks of length $k$ with at least one letter in $\mathcal{R}_1$. Let $m_0 := |\mathcal{R}_0|$, $m_1 = |\mathcal{R}_1| = m - m_0$. Once the positions of the rectangles in $\mathcal{R}_1$ have been determined, there are $m_1^j$ choices of such rectangles. On the other hand, Lemma 3.5 (i) shows that the sequences containing only rectangles in $\mathcal{R}_0$ are completely determined by their first letter. Thus the total
number of blocks with $j$ letters in $\mathcal{R}_1$ is upper bounded by $\binom{k}{j}(m_1m_0)^j$. Hence

$$ \sum_{\rho \neq 0} |\overline{P^{rk+d}(\rho)}|^2 \leq \sum_{\rho \neq 0} \gamma^{rg(B_1(\rho/n))} \\ \leq \sum_{j=1}^{k} \binom{k}{j} (m_1m_0)^j \gamma^{rj} \\ = ((1 + m_0m_1\gamma^r)^k - 1) \\ \leq (e^{km_0m_1\gamma^r} - 1). $$

Finally use the upper bound lemma (3.4) to get

$$ \| P^{rk+d}(0, \cdot) - U \|_{\text{TV}} \leq \frac{1}{4} (e^{m_0 m_1 k \gamma^r} - 1). \qquad (3.22) $$

Thus for all $s > 0$ and $r \ge \frac{\log(m_0 m_1 k)}{\log(\gamma^{-1})} + s$ we obtain

$$ \| P^{rk'+d}(0, \cdot) - U \|_{\text{TV}} \leq \frac{1}{4} (e^{\gamma^s} - 1). $$

Since $k = O(\log n)$, this yields the result.

## 3.4 Necessary condition for irreducibility and aperiodicity

In this section we prove that the condition on the subgroup $H$ given in Theorems 3.1 and 3.3 is necessary to ensure irreducibility and aperiodicity of the random walk. Proposition 3.6 and its proof should be reminiscent of the following result for convolution random walks on groups.

For a random walk on a finite group $\Gamma$ defined as the product of iid random increments of law $\mu$, irreducibility is equivalent to the fact that the subgroup generated by $\text{supp } \mu$ is the whole group $\Gamma$. Furthermore if it is irreducible, it is aperiodic if and only if $\text{supp } \mu$ is not contained in the coset of a proper normal subgroup, which is also equivalent to (see for example [137, p.97])

$$ \bigcup_{k \ge 0} (\text{supp } \mu)^{-k} (\text{supp } \mu)^k = \Gamma, $$

where for all subset $K \subseteq \Gamma$ and $l \ge 0$, $K^l := \{x_1 \cdots x_k, \forall i \ x_i \in K\}$, $K^{-1} := \{x^{-1}, x \in K\}$ and $K^{-l} := (K^{-1})^l$. In what follows, additive notation is used for group operation.

**Proposition 3.6.** Let $H$ be the smallest $A$-invariant subgroup of $\mathbb{Z}^d$ that contains $\text{supp } \mu - \text{supp } \mu$. Suppose it is generated by $(a_i u_i)_{i=1}^l$ for some basis $(u_i)_{i=1}^d$ of $\mathbb{Z}^d$ and integers $(a_i)_{i=1}^l$. If the random walk $X_t$ is irreducible and aperiodic then necessarily $l = d$ and $n$ is coprime with all the $a_i$.
*Proof.* The subgroup $H$ is described by (3.15). Let $P^t$ denote the law of $X_t$ at time $t$. Consider the subgroup $N := H \mod n$ of $\mathbb{T}_n$ defined as the image of $H$ under the natural projection. We claim the following:

**Claim 1.**

$$N = \bigcup_{k \ge 0} \mathrm{supp} P^k - \mathrm{supp} P^k$$

**Claim 2.** If $X_t$ is irreducible and aperiodic then $N = \mathbb{T}_n$.

From the second claim and Lemma 3.3 we easily deduce the result. Consider a basis $(u_i)_{i=1}^d$ of $\mathbb{Z}^d$ and integers $a_1, \dots, a_l$ such that $(a_i u_i)_{i=1}^l$ forms a basis of $H$. Then $N$ consists of the projections on $\mathbb{T}_n$ of all linear combinations of the $a_i u_i$ with coefficients in $[0, n-1]$. In particular $N$ has at most $n^l$ points, which proves the necessity of $l = d$.

Suppose now $l = d$. The basis $(u_i)_{i=1}^d$ actually yields an isomorphism between $N$ and the subgroup of $\mathbb{T}_n$ generated by elements $(0, \dots, 0, a_i, 0, \dots, 0)$ where $a_i$ is in position $i$. As $a_i$ generates $\mathbb{Z}/n\mathbb{Z}$ if and only if $n$ is coprime with $a_i$, we deduce $N = \mathbb{T}_n$ if and only if $n$ is coprime with all the $a_i$, which is the desired result.

Let us now prove the claims. For all $k \ge 0$, let $\mu_k := A^k \mu$. $N$ is by definition the subgroup generated by $\bigcup_{k \ge 0} \mathrm{supp} \mu_k - \mathrm{supp} \mu_k$. For $k \ge 1$, the random walk can be written

$$X_t = \sum_{i=1}^{k} A^{k-i} g_i \quad \mathrm{mod} \; n$$

with $g_i \in \mathrm{supp} \mu$ for all $i = 1, \dots, k$, so $P^k = \mu_0 * \dots * \mu_{k-1}$, from which we deduce $\mathrm{supp} P^k - \mathrm{supp} P^k \subseteq N$ for all $k \ge 0$.

Conversely, notice that $0 \in \mathrm{supp} P^k - \mathrm{supp} P^k$ for all $k \ge 0$. Thus, given $x_k - y_k \in \mathrm{supp} \mu_k - \mathrm{supp} \mu_k$, we can choose $x_i = y_i \in \mathrm{supp} \mu_i$ for $i = 0, \dots, k-1$ and write $x_k - y_k = x_k - y_k + \sum_{i \le k-1} (x_i - y_i)$ to obtain that $\mathrm{supp} \mu_k - \mathrm{supp} \mu_k \subseteq \mathrm{supp} P_k - \mathrm{supp} P_k$. Since $N$ is generated by the $\mathrm{supp} \mu_k - \mathrm{supp} \mu_k$, it suffices to prove that the set $\bigcup_{k \ge 0} \mathrm{supp} P^k - \mathrm{supp} P^k$ is a group.

Stability under inverse is clear, whereas stability under addition will be derived from of the following observation: since $\det A = \pm 1$, $A$ induces an automorphism of the finite group $\mathbb{T}_n$, a power of which is the identity. Consequently, the sequence of image measures $(\mu_k)_{k \ge 0}$ is periodic, say of period $m$. Now for $l \ge 0$, using the trick that $0 \in \mathrm{supp} \mu_l - \mathrm{supp} \mu_l$ for all $l \ge 0$, we see that $\mathrm{supp} P^k - \mathrm{supp} P^k \subseteq \mathrm{supp} P^l - \mathrm{supp} P^l$ for all $l \ge k$. We can consider in particular $l = -1 \mod m$, so that for all $k' \ge 0$, $P^{l+k'} = P^l * \mu^0 * \dots * \mu^{k'-1} = P^l * P^{k'}$. All in all, this shows that $\mathrm{supp} P^k - \mathrm{supp} P^k + \mathrm{supp} P^{k'} - \mathrm{supp} P^{k'} \subseteq \mathrm{supp} P^{l+k'} - \mathrm{supp} P^{l+k'}$, which is the desired addition property.

Finally, the second claim is easily deduced from the first. Consider any sequence $(x_t)_{t \ge 0}$ such that $x_t \in \mathrm{supp} P^t$ for all $t \ge 0$. Then by the characterization of $N$, for all
$t \ge 0$, $X_t$ is included in the coset $x_t + N$. Hence if $N \neq \mathbb{T}_n$ the random walk cannot be irreducible and aperiodic.

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

## 3.5 An upper bound for almost all $n$: proof of Theorem 3.3

In this section we reuse the results of Section 3.3. The proof follows the same argumentation as in [49, 95]. For all $n \ge 1$, let $U_n$ be the uniform measure on $\mathbb{T}_n$ and $P_n^t$ the law at time $t$ of the random walk on $\mathbb{T}_n$ defined by (3.1).

Fix an integer $k \ge 2$, $t = \Omega(k)$ and $a_i$ be defined as in Lemma 3.4. We will consider at once all integers $n \in N_k := \{c\tilde{\lambda}^{k-1} \le m < c\tilde{\lambda}^k, m \text{ coprime with all } a_i\}$, where $c > 0$ is some constant which can be explicit and $\tilde{\lambda} = \lambda^{-1/c_2}$. The choice of $N_k$ (and thus of $c$) is made so that

$$ \epsilon_c \lambda^k < \frac{c_1}{n^{c_2}} \le \epsilon_c \lambda^{k-1} $$

whenever $n \in N_k$, $c_1, c_2$ being the constants appearing in Lemma 3.4. In the sequel, $n$ is implicitly taken in this set. By the upper bound Lemma (3.4) and (3.14), we can upper bound $\sum_n \|P_n^{t+d} - U_n\|_{\text{TV}}$ by

$$ S := \sum_n \sum_{\rho \in \mathbb{T}_n \setminus \{0\}} \prod_{j=0}^{t-1} f((A^\top)^j \rho/n) $$

Since $n$ is not fixed anymore, it may happen that $\rho/n = \rho'/n'$ for distinct pairs $(\rho, n), (\rho', n')$. We regroup these terms as follows.

Given $r \in \mathbb{N}^d$ a vector with integer entries and an integer $s > 0$, define $\text{gcd}(r, s)$ as $\text{gcd}(r_1, \dots, r_d, s)$. Any vector $\rho/n$ can be rewritten uniquely under the form $r/s$ with $\text{gcd}(r, s) = 1$. Furthermore $s$ is necessarily coprime with the $a_i$ if $n$ is. Given $r$ and $s$ such that $\text{gcd}(r, s) = 1$, let $M(r/s)$ be the number of pairs $(\rho, n)$ such that $\rho/n = r/s$. Such $\rho/n$ are obtained simply by multiplying numerators and denominators of $r/s$ by an integer factor necessarily smaller than $c\tilde{\lambda}^k/s$, hence $M(r/s) \le c\tilde{\lambda}^k/s$. Then rewrite the sum as

$$ \begin{aligned} S &= \sum_{\substack{1 \le s < c\tilde{\lambda}^k \\ \text{gcd}(r,s)=1}} \sum_{r \in \mathbb{T}_s \setminus \{0\}} M(r/s) \prod_{j=0}^{t-1} f((A^\top)^j r/s) \\ &= \sum_{l=1}^k \sum_{c\tilde{\lambda}^{l-1} \le s < c\tilde{\lambda}^l} \sum_{r \in \mathbb{T}_s \setminus \{0\} \\ \text{gcd}(r,s)=1} M(r/s) \prod_{j=0}^{t-1} f((A^\top)^j r/s) \\ &\le c\tilde{\lambda}^k \sum_{\substack{l=1 \\ c\tilde{\lambda}^{l-1} \le s < c\tilde{\lambda}^l}} \sum_{r \in \mathbb{T}_s \setminus \{0\} \\ \text{gcd}(r,s)=1} \frac{1}{s} \prod_{j=0}^{t-1} f((A^\top)^j r/s). \end{aligned} $$
As we did for $n$, the integers $s$ considered will now be implicitly assumed to be coprime with the $a_i$.

For every pair $(r, s)$ the product can be bounded by $\gamma^{g(r/s)}$, where we recall $g(r/s)$ is the maximal number of rectangles in $\mathcal{R}_1$ appearing in the $t$ first letters of some symbolic representation of $r/s$. What follows now is the same application of Lemma 3.6 as we did in Section 3.3 but with $l$ and $s$ in place of respectively $k$ and $n$. Define for all $l \ge 1$,

$$Q_l := \{(r, s) : c\tilde{\lambda}^{l-1} \le s < c\tilde{\lambda}^l, r \in \mathbb{T}_s \setminus \{0\}, \gcd(r, s) = \gcd(s, a_i) = 1\}.$$

Then

$$S \le c\tilde{\lambda}^k \sum_{l=1}^{k} \sum_{(r,s) \in Q_l} \frac{1}{s} \gamma^{g(r/s)}.$$

Decompose the symbolic representations of $r/s$ into blocks of $l_1 = Cl$ letters and set $t' = [t/l_1]$. Since $s$ is coprime with the $a_i$, we can apply Lemma 3.6 with $s$ instead of $n$ basically in the same way. The only difference concerns point (ii), as the distance between distincts points is now lower bounded by

$$d(r/s, r'/s') \ge \frac{c'}{ss'}$$

for some constant $c'$. Arguing as in the proof of Lemma 3.4, this implies a lower bound on the unstable component $v_u$ of $r/s - r'/s'$, namely $\|v_u\| \ge c'/(ss')^{c_2}$ for some possibly different constant $c'$. The definition of $Q_l$ is made so that $(r, s) \in Q_l$ implies $\epsilon_c \lambda^l < c_1/s^{c_2}$. Thus choosing $C$ large enough in the definition of blocks, one has $\epsilon_c \lambda^{l_1} < c_1/(ss')^{c_2}$ so by Proposition 3.2 symbolic representations of $r/s, r'/s'$ must have distinct blocks.

Then use the interchange inequality (3.21) to obtain

$$S \le c\tilde{\lambda}^k \sum_{l=1}^{k} \sum_{(r,s) \in Q_l} \frac{1}{s} \gamma^{t'g(B_1(r/s))}.$$

For $(r, s) \in Q_l$, $\frac{1}{s} \le c^{-1}\tilde{\lambda}^{-l+1} = O(\tilde{\lambda}^{-l})$. On the other hand, we can upper bound the sum over $Q_l$ by the sum over all blocks of length $l_1$, thus

$$\sum_{(r,s) \in Q_l} \frac{1}{s} \gamma^{t'g(B_1(r/s))} \le \tilde{\lambda}^{-l} \sum_{j=1}^{l_1} \binom{l_1}{j} \gamma^{t'j} (m_0 m_1)^j \\ = \tilde{\lambda}^{-l} \left( (1 + m_0 m_1 \gamma^{t'})^{l_1} - 1 \right).$$

We now consider two different regimes for $l$.
If $l \le k/\log k$, then $t' \to \infty$ as $k \to \infty$. Now for large $t'$ we can use Taylor's theorem to bound $(1 + m_0 m_1 \gamma^{t'})^{l_1} - 1$ by $O(l_1 \gamma^{t'})$. As $l_1 = C \log l$ this yields

$$ 
\begin{aligned}
\sum_{l \le k/\log k} \tilde{\lambda}^{-l} \left( (1 + m_0 m_1 \gamma^{t'})^{l_1} - 1 \right) &\le O \left( \sum_{l \le k/\log k} \tilde{\lambda}^{-l} l \gamma^{t/(Cl)} \right) \\
&\le O \left( \sum_{l \ge 0} \tilde{\lambda}^{-l} l \gamma^{t \log k/(Ck)} \right) \\
&\le O(\gamma^{t \log k/(Ck)})
\end{aligned}
$$

so for $t \ge C'k$ with a sufficiently large constant $C'$, $S_1 \to 0$ as $k \to \infty$.

On the other hand, for $k/\log k < l \le k$, choose $t \ge \tilde{C}k$ with $\tilde{C} > 0$ large enough so that $\tilde{\gamma} := \tilde{\lambda}^{-1}(1 + m_0 m_1 \gamma^{\tilde{C}})^C < 1$. Then as $t' \ge t/l \ge \tilde{C}$ we can bound

$$ 
\begin{aligned}
\sum_{k/\log k < l \le k} \tilde{\lambda}^{-l} \left( (1 + m_0 m_1 \gamma^{t'})^{l_1} - 1 \right) &\le k \max_{k/\log k < l \le k} \tilde{\lambda}^{-l} \left( (1 + m_0 m_1 \gamma^{\tilde{C}})^{Cl} - 1 \right) \\
&\le k \max_{k/\log k < l \le k} \left( \tilde{\lambda}^{-1} (1 + m_0 m_1 \gamma^{\tilde{C}})^C \right)^l \\
&= O(\tilde{\gamma}^{k/\log k}).
\end{aligned}
$$

All in all, we have proved there exists a constant $C'$ such that for large enough $k$ and $t = C'k$,

$$ \sum_{n \in N_k} \| P_n^{t+d} - U_n \|_{\text{TV}} \le S \le o(\tilde{\lambda}^k). $$

As a consequence the number of integers $n$ in the interval $N_k$ for which the random walk has not mixed by time $t+d$ is $o(\tilde{\lambda}^k)$.

On the other hand, for every integer $a \ge 1$, the number of multiples of $a$ in the interval $[c\tilde{\lambda}^{k-1}, c\tilde{\lambda}^k)$ is of order $O(\tilde{\lambda}^{k-1})$. Consequently it must contain $\Omega(\tilde{\lambda}^k)$ integers coprime with all $a_i$, hence $|N_k| \ge \Omega(\tilde{\lambda}^k)$. Ultimately this shows that the fraction of integers in $N_k$ for which the random walk has mixed at time $C'k$ can be made arbitrarily large by choosing $k$ large enough.

## 3.6 Markov partitions

In this section we define Markov partitions and prove Propositions 3.3, 3.4 and 3.5. The first use of Markov constructions for toral automorphisms goes back to the work of Berg [23] and Adler and Weiss [1] for dimension 2. Since, many other constructions, with different degrees of explicitness, have been proposed for dynamical systems more general than automorphisms of the torus. This section is based on the general construction for Axiom A diffeomorphisms by Bowen [37]; see also [21]. For the reader interested in more explicit partitions, relating to arithmetic properties of the map A, see [153, 158].
We note that these partitions are related to the β-ary expansions used in [106], but do not apply in the same generality as the Bowen construction.

### 3.6.1 Hyperbolic dynamics

We identify A with the induced map on $\mathbb{T}^d$. Recall $p$ denotes the natural projection $\mathbb{R}^d \to \mathbb{T}^d$, and that $d$ is the quotient metric induced by a norm $\|\cdot\|$ on $\mathbb{R}^d$ adapted to A. For $x \in \mathbb{T}^d$ and $\epsilon > 0$ define

$$ 
\begin{align} 
W^s(x) &= \{y \in \mathbb{T}^d, d(A^n x, A^n y) \to 0\} \notag \\ 
W^s_\epsilon(x) &= \{y \in \mathbb{T}^d, d(A^n x, A^n y) \le \epsilon \ \forall n \ge 0\} \tag{3.23} \\ 
W^u(x) &= \{y \in \mathbb{T}^d, d(A^{-n} x, A^{-n} y) \to 0\} \notag \\ 
W^u_\epsilon(x) &= \{y \in \mathbb{T}^d, d(A^{-n} x, A^{-n} y) \le \epsilon \ \forall n \ge 0\}. \notag 
\end{align} 
$$

$W^s(x)$, resp. $W^u(x)$ are the stable, resp. unstable manifold going through $x$. $W^s_\epsilon(x)$, resp. $W^u_\epsilon(x)$ are the local stable, resp. unstable manifold going through $x$.

They can be described as: $W^s(x) = p(x + E_s)$, $W^u(x) = p(x + E_u)$ and $W^s_\epsilon(x) = p(B(x, \epsilon) \cap (x + E_s))$, $W^u_\epsilon(x) = p(B(x, \epsilon) \cap (x + E_u))$ where we recall $B(x, \epsilon)$ denotes the ball of radius $\epsilon$ and center $x$ in $\mathbb{R}^d$. The previous definitions readily imply the following.

**Lemma 3.7.** For all sufficiently small $\epsilon > 0$ such that $p$ is injective on $B(0, \epsilon)$, if $d(x, y) \le \epsilon$ then $W^s_\epsilon(x) \cap W^u_\epsilon(y)$ consists of a single point, denoted $[x, y]$. The map $(x, y) \mapsto [x, y]$ is continuous.

The construction of Markov partitions that we will present is quite general, for it is essentially based on compactness arguments combined with the following property, called shadowing of orbits.

**Definition 3.2.** Given $\alpha > 0$, a sequence $(x_k)_{k \in \mathbb{Z}}$ is called an $\alpha$-pseudo-orbit if for all $k \in \mathbb{Z}$, $d(Ax_k, x_{k+1}) < \alpha$. Given $\beta > 0$, a point $x \in \mathbb{T}^d$ $\beta$-shadows the pseudo-orbit $(x_k)_{k \in \mathbb{Z}}$ if for all $k \in \mathbb{Z}$, $d(x_k, A^k x) < \beta$.

**Proposition 3.7.** For all $\beta > 0$ small enough, there exists $\alpha > 0$ such that every $\alpha$-pseudo-orbit $(x_k)_k$ is $\beta$-shadowed by a unique point $x$ of $\mathbb{T}^d$.

*Proof.* Let $\beta > 0$. Uniqueness is provided by expansiveness (Proposition 3.2), provided $\beta \le \epsilon_c$. For the existence, it suffices to prove the analog result in $\mathbb{R}^d$: if $(x_k)_{k \in \mathbb{Z}}$ an $\alpha$-pseudo-orbit in $\mathbb{R}^d$, then it can be $\beta$-shadowed by a true orbit, provided $\alpha$ is small enough. Indeed, lifting a pseudo-orbit of the torus to $\mathbb{R}^d$, then we can project the shadowing orbit back to $\mathbb{T}^d$ to prove the statement for the torus.
Decompose $x_k = s_k + u_k$ with $s_k \in E_s, u_k \in E_u$ for all $k \in \mathbb{Z}$. Since the metric is adapted to $A$, it is easily seen that the sequences $(s_k)_{k \in \mathbb{Z}}$ and $(u_k)_{k \in \mathbb{Z}}$ are both $\alpha$-pseudo-orbits. Write $S = A|_{E_s}$ and $T = A^{-1}|_{E_u}$. Since $(s_k)_{k \in \mathbb{Z}}$ is an $\alpha$-pseudo-orbit

$$ \|S^{k+1}s_{-(k+1)} - S^k s_{-k}\| \le \|S^k\| \alpha \le \lambda^k \alpha $$

hence the sequence $(S^k s_{-k})_{k \in \mathbb{N}}$ is a Cauchy sequence and we can define $s := \lim_{k \to \infty} S^k x_{-k}$. Then for all $m \ge 1-k$,

$$ \begin{aligned} \|s_k - S^k s\| &\le \sum_{i=0}^{k+m-1} \|S^i s_{k-i} - S^{i+1} s_{k-i-1}\| + \|S^{k+m}(s_{-m}) - S^k s\| \\ &\le \sum_{i=0}^{k+m-1} \lambda^i \alpha + \lambda^k \|S^m s_{-m} - s\| \\ &\le \frac{\alpha}{1-\lambda}. \end{aligned} $$

by taking $m \to \infty$.

Repeating the argument with $T$, the sequence $(T^k u_{-k})_{k \in \mathbb{N}}$ converges to a point $t \in \mathbb{R}^d$ so that $\|u_k - T^k u\| \le \alpha/(1-\lambda)$. Since the metric is adapted, $x := s+u$ $\beta$-shadows the pseudo orbit $(x_k)_{k \in \mathbb{Z}}$ for $\beta = \alpha/(1-\lambda)$. $\square$

### 3.6.2 Markov Partitions

Let $\epsilon > 0$ be sufficiently small so that the conclusion of Lemma 3.7 holds.

**Definition 3.3.** A set $R \subset \mathbb{R}^d$ is called a rectangle if it has diameter at most $\epsilon$ and, for all $x, y \in R$, $[x, y] \in R$. A rectangle is said to be proper if $R = \text{int}(R)$.

Given a rectangle $R$ and $x \in R$, let

$$ W^s(x, R) := W_{\epsilon}^s(x) \cap R \quad W^u(x, R) := W_{\epsilon}^u(x) \cap R. $$

**Definition 3.4.** A Markov partition is a finite covering $\mathcal{R} = \{R_1, \dots, R_m\}$ of $\mathbb{R}^d$ by proper rectangles such that

(i) $\text{int}(R_i) \cap \text{int}(R_j) = \emptyset$ for all $i \ne j$

(ii) for all $x \in \text{int}(R_i)$ if $Ax \in \text{int}(R_j)$, then

$$ A(W^s(x, R_i)) \subseteq W^s(Ax, R_j) \quad \text{and} \quad A(W^u(x, R_i)) \supseteq W^u(Ax, R_j). \quad (3.24) $$

Notice that the second part of (ii) above is equivalent to

$$ A^{-1}(W^u(x, R_i)) \subseteq W^u(A^{-1}(x), R_j). $$
It is thus a dual statement of the first part obtained by replacing $A$ with $A^{-1}$, which
has the effect of exchanging stable and unstable directions.

Condition (ii) is really the Markov property of the partition. It ensures that if
$\text{int}R_i \cap A^{-1}\text{int}R_j \neq \emptyset$ and $\text{int}R_j \cap A^{-1}\text{int}R_k \neq \emptyset$ then $\text{int}R_i \cap A^{-1}\text{int}R_j \cap \text{int}A^{-2}R_k \neq \emptyset$:
if $x, y$ are respectively in the first and second intersection, consider $A^{-1}[y, Ax]$.

We have all the tools for the proofs. We give all the essential arguments, but only
sketch the technical details. We refer to [37] for a detailed proof, which extends to the
general case of Axiom A diffeomorphisms.

*Proof of Proposition 3.5.* (i) Let $R$ be a rectangle and consider the compact set $U := \{\omega \in \Omega \mid \omega_0 = R\}$. Since rectangles of a Markov partition are proper and of disjoint interior, one has $\pi^{-1}(\text{int}R) \subset U$. Because $\pi$ is surjective we deduce $\text{int}R \subset \pi(U)$. Finally continuity implies $\pi(U)$ is compact, hence $R \subset \pi(U)$.

(ii) Recall that $\pi$ is finite-to-one. Thus if $x$ is periodic of period $k$, the shift $\theta$ induces a permutation of the finite set of symbolic representations $\pi^{-1}(\{x, Ax, \dots A^{k-1}x\})$. For the integer $m$ such that the permutation induced by $\theta^m$ is the identity, one gets exactly that all sequences in $\pi^{-1}(x)$ are $m$-periodic. $\square$

*Proof of Proposition 3.4.* Given two non-empty rectangles $R, S$ of a Markov partition, $S$ will be called a stable, resp. unstable subrectangle of $R$ if $S \subset R$, $S$ is proper and for all $x \in S$, $W^s(x, S) = W^s(x, R)$, resp. $W^u(x, S) = W^u(x, R)$.

Consider a Markov partition $\mathcal{R} = \{R_1, \dots, R_m\}$, $\mathcal{A} = \mathcal{A}(R)$ and $\Omega := \Omega_{\mathcal{A}}$ the associated shift.

If $S \subseteq R_i$ is a non-empty unstable subrectangle and $A_{ij} = 1$, Lemma 3.17 in [37]
establishes that $A(S) \cap R_j$ is a non-empty unstable rectangle of $R_j$. Similarly, $A^{-1}(S) \cap
R_j$ is a non-empty stable rectangle of $R_i$.

Let $\omega \in \Omega$. By the previous statement, $R_{\omega_0} \cap A^{-1}(R_{\omega_1})$ is a non-empty stable
subrectangle of $R_{\omega_0}$. By an immediate induction, every intersection $\bigcap_{k=0}^l A^{-k}R_{\omega_k}$ is a
non-empty stable subrectangle of $R_{\omega_0}$. By compactness, $\bigcap_{k=0}^{\infty} A^{-k}R_{\omega_k}$ is then also a
non-empty stable subrectangle. Then reiterate the argument with $A^{-1}$ to deduce that
$\pi(\omega) := \bigcap_{k \in \mathbb{Z}} A^{-k}R_{\omega_k}$ is non-empty. By construction, the orbits of two points in this
intersection must remain at distance $\epsilon$ from each other. If $\epsilon$ is taken smaller than the
expansiveness constant, the intersection is thus a singleton.

Let $\pi(\omega)$ be the unique point of this singleton. From the construction, it is immedi-
ate that $\pi \circ \theta = A \circ \pi$. By what precedes the diameter of the intersection $\bigcap_{k=-l}^{l} A^{-k}R_{\omega_k}$
tends to 0 as $l$ tends to infinity, which implies the continuity of the map $\pi$.

We prove surjectivity. Let $\partial \mathcal{R} := \bigcup_{R \in \mathcal{R}} \partial R$ denote the union of all boundaries of rectangles. Its complement $\text{int}(\mathcal{R})$ is an open dense subset of $\mathbb{T}^d$. If $x \in \bigcap_k A^k \text{int}(\mathcal{R})$, $x$
is the image of any sequence $\omega \in \Omega$ such that $A^k x \in R_{\omega_k}$ for all $k$. By Baire's theorem, an intersection of open dense subsets is dense, hence the image of $\pi$ contains an open dense subset of $\mathbb{T}^d$. However $\pi(\Omega)$ has to be compact by continuity, whence $\pi(\Omega) = \mathbb{T}^d$.

Finally, let us prove that any point of $\mathbb{T}^d$ cannot have more than $m^2$ pre-images under $\pi$. Suppose there exist $\omega^{(1)}, \dots, \omega^{(m^2+1)} \in \Omega$ with the same image $x$. Then one can find $k_1 \le k_2$ such that the indices between $k_1$ and $k_2$ of these sequences do not coincide. However there is at most $m^2$ possibilities when choosing the $k_1$-th and $k_2$-th index, therefore there exists among these sequences a pair $(\omega, \omega')$ such that $\omega_{k_1} = \omega'_{k_1}$, $\omega_{k_2} = \omega'_{k_2}$ and $\omega_l \ne \omega'_l$ for $k_1 < l < k_2$.

Now from the Markov property of the partition, the intersection $\cap_{k=k_1}^{k_2} A^{-k} \text{int} R_{\omega_k}$ must be non-empty. Take $u$ in this open set and consider $\tau \in \pi^{-1}(u)$. Since $u$ is an interior point $\tau$ and $\omega$ coincide on indexes between $k_1$ and $k_2$.

On the other hand, since indexes $k_1$ and $k_2$ of $\omega$ and $\omega'$ coincide, one can build a new sequence $\tau'$ by replacing the block of $\tau$ between $k_1$ and $k_2$ by that of $\omega'$, that is we define

$$ \tau'_{k} := \begin{cases} \tau_{k} & \text{for } k \le k_{1} \text{ or } k \ge k_{2} \\ \omega'_{k} & \text{if } k_{1} \le k \le k_{2} \end{cases}. $$

Consider finally the point $v := \pi(\tau')$. By construction $A^k u$ and $A^k v$ are contained in the same rectangles for all $k \le k_1$ and $k \ge k_2$, whereas for $k_1 \le k \le k_2$, they are contained in the rectangles $R_{\omega_k}$ and $R_{\omega'_k}$ respectively. However the latter both contain the point $A^k x$, so $A^k u, A^k v$ are at distance at most $2\eta$ from each other by triangle inequality. Thus $d(A^k u, A^k v) \le 2\eta$ for all $k$. Consequently if $2\eta \le \epsilon_c$ expansiveness ensures that $A^l u \in W^s(A^l, R_{\omega_l})$. In the end we obtain $A^l u \in \text{int} R_{\omega_l} \cap R_{\omega'_l}$, which contradicts the fact that rectangles have disjoint interior. $\square$

*Proof of Proposition 3.3.* Let $\beta > 0$ and consider $\eta > 0$ such that all $2\eta(1 + \|A\|)$-pseudo-orbits are $\beta$-shadowed by a true orbit (Proposition 3.7). Consider a finite cover of $\mathbb{T}^d$ with balls $B(x_i, \eta)$, $i = 1, \dots, m$. Let $\mathcal{A}$ be the matrix defined by $\mathcal{A}_{ij} = 1$ if and only $Ax_i \in B(x_j, 2\eta(1 + \|A\|))$ and consider the shift $\Omega := \Omega_{\mathcal{A}}$ associated.

For all $\omega \in \Omega$, the sequence $(x_{\omega_n})_n$ is a $2\eta(1 + \|A\|)$-pseudo-orbit and thus can be $\beta$-shadowed by points of a set $\pi(\omega) \subset \mathbb{T}^d$ (which is a singleton in the invertible case).

By construction, $A \circ \pi = \pi \circ \theta$. $\pi$ is surjective: every point $x \in \mathbb{T}^d$ is an image $\pi(\omega)$ for any sequence $\omega$ such that $A^n x \in B(x_{\omega_n}, \eta)$ for all $n \in \mathbb{Z}$. These sequences are indeed in $\Omega$, since

$$ d(Ax_{\omega_n}, x_{\omega_{n+1}}) \le d(Ax_{\omega_n}, A^{n+1}x) + d(A^{n+1}x, x_{\omega_{n+1}}) \le (\|A\| + 1)\eta < 2(1 + \|A\|)\eta. $$

$\pi$ is also continuous when giving $\Omega$ the product topology. The argument is similar to the one given in the previous proof.
For $i \in [m]$, let

$$T_i := \pi(\{\omega \in \Omega, \omega_0 = i\}).$$

By construction for all $\omega \in \Omega$ $d(\rho(\omega), x_{\omega_0}) \le \beta$, so the sets $T_i$ have diameter at most $2\beta$, which can be made arbitrarily small. From the continuity of $\pi$, the sets $T_i$ are closed sets.

Consider now the local product on $\Omega$ defined for $\omega, \omega' \in \Omega$ with $\omega_0 = \omega'_0$ by

$$[\omega, \omega']_k = \begin{cases} \omega_k & \text{if } k \ge 0 \\ \omega'_k & \text{if } k \le 0 \end{cases}$$

Then $d(A^k\pi(\omega), A^k\pi([\omega, \omega'])) \le 2\beta$ for all $k \ge 0$, and $d(A^k\pi(\omega), A^k\pi([\omega, \omega'])) \le 2\beta$ for all $k \le 0$. Thus $\pi([\omega, \omega']) \in W_{2\beta}^s(\pi(\omega)) \cap W_{2\beta}^u(\pi(\omega'))$, so that $\pi([\omega, \omega']) = [\pi(\omega), \pi(\omega')]$ by Lemma 3.7. This immediately implies that the sets $T_i$ are rectangles.

Suppose then that $x = \pi(\omega)$, with $\omega_0 = i, \omega_1 = j$. From $\pi \circ \theta = A \circ \pi$ we deduce $W^s(x, T_i) = \pi(\{\omega' \in \Omega, \forall k \ge 0, \omega_k = \omega'_k\})$. Thus

$$\begin{aligned} AW^s(x, T_i) &= \pi(\{\omega' \in \Omega, \forall n \ge -1, \omega'_n = \omega_{n+1}\}) \\ &\subset \pi(\{\omega' \in \Omega, \forall n \ge 0, \omega'_n = \omega_{n+1}\}) \\ &= W^s(Ax, T_j), \end{aligned}$$

hence

$$A(W^s(x, T_i)) \subseteq W^s(Ax, T_j).$$

Using $A^{-1}$ in place of $A$, we can prove similarly $A^{-1}(W^u(x, T_i)) \subseteq W^u(A^{-1}x, T_j)$. Therefore the rectangles $T_i$ satisfy almost all the properties of a Markov partition, except there may not be proper or of disjoint interiors.

To get rectangles satisfying these properties, the idea is to divide the $T_i$ further into smaller rectangles. Namely if $T_j \cap T_k \ne \emptyset$, let

$$\begin{align*} T_{j,k}^1 &= \{x \in T_j, W^u(x, T_j) \cap T_k \ne \emptyset, W^s(x, T_j) \cap T_k \ne \emptyset\} = T_j \cap T_k \\ T_{j,k}^2 &= \{x \in T_j, W^u(x, T_j) \cap T_k \ne \emptyset, W^s(x, T_j) \cap T_k = \emptyset\} \\ T_{j,k}^3 &= \{x \in T_j, W^u(x, T_j) \cap T_k = \emptyset, W^s(x, T_j) \cap T_k \ne \emptyset\} \\ T_{j,k}^4 &= \{x \in T_j, W^u(x, T_j) \cap T_k = \emptyset, W^s(x, T_j) \cap T_k = \emptyset\} \end{align*}$$

Then for all $x, y \in T_j$, the fact that $W^s([x, y], T_j) = W^s(x, T_j)$ and $W^u([x, y], T_j) = W^u(y, T_j)$ proves that the $T_{j,k}^i$ are rectangles. For any $x \in \mathbb{T}^d$ let

$$R(x) := \bigcap \{\text{int}(T_{j,k}^i) : T_j \cap T_k \ne \emptyset \text{ and } x \in T_{j,k}^i\}$$

and $\mathcal{R} := \{\overline{R(x)}, x \in \mathbb{T}^d\}$. It can be easily checked that $R(x) \cap R(x') \ne \emptyset$ implies $R(x) = R(x')$ so the set $\mathcal{R}$ is finite. Therefore $\mathcal{R}$ defines a finite covering by proper
rectangles of disjoint interiors. It remains to prove the second property of Markov
partitions.

Suppose $y \in W^s(x, \overline{R(x)})$. Suppose that $x \in \text{int}(T_i)$ and $Ax \in \text{int}(T_j)$. From the
property proved previously for the $T_i$, $Ay \in W^s(Ax, T_j)$. We will argue by contradiction
to prove that $R(Ax) = R(Ay)$. If this does not hold, it implies the existence of a
rectangle $T_k$ intersecting $T_j$ such that $Ax, Ay$ are not in the same $T_{j,k}$. From the
definition of $T_{j,k}$ we can suppose without loss of generality that $W^u(Ax, T_j) \cap T_k \neq \emptyset$ and
$W^u(Ay, T_j) \cap T_k = \emptyset$. Since $AW^u(x, T_i) \supset W^u(Ax, T_j)$, we can thus find $z \in W^u(x, T_i)$
such that $Az \in T_j \cap T_k = T_{j,k}^1$. Consider $l$ such that $z \in T_i \cap T_l = T_{i,l}^1$. Since $R(x) = R(y)$,
$x, y$ are in the same subrectangle $T_{i,l}$, so there exists a point $z' \in W^u(y, T_i) \cap T_l$. Then
$z'' := [z, z'] = [z, y]$ is in $W^s(z, T_l) \cap W^u(y, T_i)$ and $Az'' = [Az, Ay] \in W^s(Az, T_k) \cap
W^u(Ay, T_j)$, which contradicts $W^u(Ay, T_j) \cap T_k = \emptyset$. Hence $R(Ax) = R(Ay)$ which
implies $AW^s(x, \overline{R(x)}) \subset W^s(Ax, \overline{R(Ax)})$.
$\square$
# Chapter 4

## Concentration for low-degree functions on the symmetric group

This chapter is based on a work not yet published. We give a concentration inequality for functions on the symmetric group that was developed as a part of the work on the cutoff phenomenon presented in the next chapter.

### 4.1 Introduction

#### 4.1.1 Main results

In [43][Prop. 1.1], Chatterjee established an exponential concentration inequality for random variables of the form

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

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

$$\mathbb{P}[|Z - \mathbb{E}[Z]| \ge t] \le 2 \exp\left(\frac{-t^2}{2 \|A\|(t + 2\mathbb{E}[X])}\right), \qquad (4.2)$$

where $\|A\| = \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 $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 even $n-1$. Furthermore there already exist concentration results for generic functions on the symmetric group, regardless of the degree: Maurey's inequality [133] (see also Thm. 2.14 in [41]), Talagrand's inequality [156][Thm 5.1], and Proposition 4.8 in [41] 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} := \mathrm{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 4.3. 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

$$ \mathfrak{F} := \{ \phi : M_n(\mathbb{R}) \to \mathbb{R} \mid \forall i, j, k \in [n] : \partial_{ij}\partial_{ik}\phi = \partial_{ji}\partial_{ki}\phi = 0 \}, \quad (4.3) $$

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 \ge 0} \mathfrak{F}_{=d} $$

where for each $d \ge 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 \ge 1$, a convenient way to write $\phi \in \mathfrak{F}_{=d}$ is given by Euler's theorem:

$$ \phi(X) = \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), \quad (4.4) $$

which can be seen as a generalization of (4.1). 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 \quad U\phi(X) := \frac{1}{dn} \sum_{i,j,k,l \in [n]} X_{il}X_{kj}\partial_{ij}\partial_{kl}\phi(X). \quad (4.5) $$

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

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

In this chapter, we write $\mathbb{E}[\phi] := \mathbb{E}[\phi(\sigma)]$ for the expectation with respect to a uniformly distributed $\sigma \in \mathfrak{S}_n$.
**Theorem 4.1.** Let $n \ge 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'_D, C_U \ge 0$ such that for all $k \in [0, d]$,

$$ \|D^k \phi\|_{\infty} \le C_D, \quad \|\nabla D^k \phi\|_{\infty} \le C'_D \quad \text{and} \quad \|D^k U \phi\|_{\infty} \le C_U. \qquad (4.6) $$

Then for all $t \ge 0$,

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

where

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

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

**Remark 4.2.** As was mentioned 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 4.1 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 \to 0$. In the next chapter, Theorem 4.1 will be applied with $d = O(\sqrt{\log n})$.

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

$$ E_{i_1 \cdots i_k} := \{ \sigma \in \mathfrak{S}_n \mid \forall m = 1, \dots, k \quad \sigma(i_m) = j_m \}. $$

where $\mathbf{i} = (i_1, \dots, i_k)$, $\mathbf{j} = (j_1, \dots, 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 \to \mathbb{R}$, the degree of $f$ can be defined as the least integer $d \ge 0$ such that $f$ writes as a linear combination of $k$-coset indicator functions with $k \le 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 [69][Thm. 7], it coincides with the *Fourier degree* of $f$, which is the least integer $d \ge 0$ such that all Fourier coefficients of $f$ corresponding to irreducible representations of dimension $k > d$ are zero. We 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 4.4.

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 $\|D^k\phi\|_{\infty}, \|\nabla D^k\phi\|_{\infty}, \|D^k U\phi\|_{\infty}$ for all $k \le 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'_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 4.1.** Let $\phi$ be a polynomial in the indeterminates $(X_{ij})_{i,j=1}^n$ of degree $d \ge 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 \ge 0$

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

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

**Corollary 4.1.** Let $\phi \in \mathfrak{F}_d$ be a polynomial function of degree at most $d \ge 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 \ge 0$,

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

with

$$ \alpha_{\phi} := 6d2^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) $$

### 4.1.2 Related works

Random variables of the form (4.1) were introduced in the "combinatorial central limit theorem" by Hoeffding [101]. 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 (4.2) and our result. Early applications of Stein's method for such random
variables are found in the works of Bolthausen and Goetze [25, 26] who obtained error bounds on the normal approximation.

Introduced by Stein in [154] 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 [155] and to the survey [44] of Chatterjee and [46] 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 [41], see also [43]. The inequality (4.2) 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 [42], where he establishes a connection between concentration and the rate of convergence of some random walks on groups.

## Organization of the chapter

We start proving Proposition 4.1 in Section 4.2 then prove the main Theorem in Section 4.3.

## 4.2 Control of the smoothness parameters: proof of Proposition 4.1

Let $\phi$ be a multilinear polynomial in the indeterminates $(X_{ij})_{i,j=1}^n$ of degree $d$. The operator $D$ has the effect of replacing one indeterminate in each monomial by 1 and take the average. When doing so, some coefficients coming from different monomials of $\phi$ can be regrouped together. To avoid this, we can introduce new indeterminates instead of evaluating them at 1. This is formalized by the following construction: for all $m \ge 1$ write $X^{(m)} = (X_{ij}^{(m)})_{i,j=1}^n$. Let $\tilde{D}$ be the linear operator on $\mathcal{R} = \mathbb{R}[X^{(1)}, X^{(2)}, \dots]$ defined on monomials as

$$ \tilde{D} : X_{i_1 j_1}^{(1)} \cdots X_{i_k j_k}^{(1)} X_{i_{k+1} j_{k+1}}^{(m_{k+1})} X_{i_d j_d}^{(m_d)} \mapsto \frac{1}{kn} \sum_{l=1}^{k} X_{i_1 j_1}^{(1)} \cdots X_{i_{l-1} j_{l-1}}^{(1)} X_{i_l j_l}^{(m_d+1)} X_{i_{l+1} j_{l+1}}^{(m_{l+1})} \cdots X_{i_d j_d}^{(m_d)}, $$

where $m_1 = \dots m_k = 1 < m_{k+1} \le \dots \le m_d$. Let $T: \mathcal{R} \to \mathbb{R}[X_{ij}]$ be the operator that identifies $X^{(1)}$ with the $X_{ij}$ and evaluates all other indeterminates $X^{(2)}, X^{(3)}, \dots$ at 1. Then by construction for all $l \ge 1$,

$$ D^l \phi = T \tilde{D}^l \phi. \qquad (4.9) $$

Extend the definitions of $M, N$ to $\mathcal{R}$ as follows: if $\psi \in \mathcal{R}$, let $M(\psi)$ be the maximal coefficient in absolute value of $\psi$ and $N(\psi, \sigma)$ the number of non-zero monomials when
evaluating $X_{ij}^{(1)} = 1_{\sigma(i)=j}$ and indeterminates $X^{(m)}$ at 1 for all $m \ge 2$. Note these
are not $M(T\psi), N(T\psi, \sigma)$: the point is precisely to distinguish monomials that would
otherwise be regrouped together when applying $T$. Write $N(\psi) := \max_{\sigma \in \mathfrak{S}_n} N(\psi, \sigma)$.
If $\psi = \sum_{k=1}^d \psi_k \in \mathcal{R}$ decomposes as the sum of functions that are homogeneous in $X^{(1)}$
of degree $k$, then for all $\sigma \in \mathfrak{S}_n$

$$
|T\psi(\sigma)| \le \sum_{k=1}^{d} M(\psi_k)N(\psi_k, \sigma) \qquad (4.10)
$$

On the other hand we claim that if $\psi$ is homogeneous of degree $d \ge 1$, then

$$
M(\tilde{D}\psi) \le \frac{1}{dn} M(\psi), \quad \text{and} \quad \forall \sigma \in \mathcal{S}_n : N(\tilde{D}\psi, \sigma) \le 2dn N(\psi, \sigma). \qquad (4.11)
$$

The first inequality is obvious from the definition of $\tilde{D}$. For the second inequality,
observe that every monomial in $\tilde{D}\phi$ comes from a unique monomial of $\phi$. The issue
is that when evaluating $X^{(1)}$ at $\sigma$ and other indeterminates $X^{(m)}$ at 1, a non-zero
contribution in $\tilde{D}\phi(\sigma)$ may arise from a monomial that was zero in $\phi(\sigma)$. This occurs
if this monomial contains exactly one indeterminate $X_{ij}^{(1)}$ with $\sigma(i) \neq j$, whereas all
other indeterminates evaluate to 1. This leaves at most $2dn$ choices for each monomial,
from which we deduce the claim.

Combining (4.9), (4.10) and (4.11), we obtain that for all $\sigma \in \mathfrak{S}_n$ and $l \le d$

$$
\begin{align*}
|D^l \phi(\sigma)| &\le \sum_{k=1}^d M(\tilde{D}^l \phi_k) N(\tilde{D}^l \phi_k, \sigma) \\
&\le 2^l \sum_{k=1}^d M(\phi_k) N(\phi_k, \sigma) \\
&\le 2^l M(\phi) N(\phi)
\end{align*}
$$

using that $M(\phi) = \max_{k \le d} M(\phi_k)$ and $N(\phi, \sigma) = \sum_{k=1}^d N(\phi_k, \sigma)$.

The inequality for $U\phi$ is proved similarly. Clearly $M(U\phi) \le (dn)^{-1}M(\phi)$ if $\phi$ is
homogeneous of degree $d$. On the other hand, monomials of $U\phi$ are obtained by picking
a monomial of $\phi$, two indeterminates $X_{ij}, X_{kl}$ in this monomial and replace them by
$X_{il}, X_{kj}$. Consequently every monomial of $\phi$ gives rise to at most $d(d-1)$ monomials
in $U\phi$. Thus we deduce that

$$
M(U\phi)N(U\phi) \le \frac{d-1}{n} M(\phi)N(\phi)
$$

Then for a general function decomposing $\phi = \sum_{k=1}^{d} \phi_k$ as a sum of homogeneous func-
tions implies that for all $\sigma \in \mathfrak{S}_n$

$$ 
\begin{aligned}
|U\phi(\sigma)| & \le \sum_{k=1}^{d} M(U\phi_k)N(U\phi_k, \sigma) \\
& \le \sum_{k=1}^{d} \frac{k-1}{n} M(\phi_k)N(\phi_k, \sigma) \\
& \le \frac{d-1}{n} M(\phi)N(\phi, \sigma).
\end{aligned}
$$

## 4.3 Proof of the concentration inequality

### 4.3.1 Induction with the method of exchangeable pairs

The proof of Theorem 4.1 follows the original argument of Chatterjee for the $d = 1$ case, based on Stein's method of exchangeable pairs. Eventually, the argument consists in establishing an inequality involving the moment generating function of the random variable and its derivatives, so that it can be integrated to give a bound in the tail probability by Chernoff's inequality. In our case, we will obtain a differential inequality relating the moment generating functions of $\phi$ and that of the functions $D^k\phi$, which are of lower degree. A bound is thus proved for the function $\phi$ only by induction on the degree, which is made possible by the condition (4.6). To that end, we reindex the quantities $\beta_\phi, \gamma_\phi$ in terms of $d$:

$$ 
\begin{aligned}
\beta_d &:= 6dC'_D \left( \log \left( \frac{4C_D n}{C'_D} \right)^+ + \frac{(2/n)(2 - e^{-2/n})}{1 - e^{-2/n}} \right) \\
\gamma_d &:= \frac{2\beta_d}{3} (2\mathbb{E}[\phi] + C_U)
\end{aligned}
\quad (4.12) $$

Theorem 4.1 is thus the consequence of the following lemma.

**Lemma 4.1.** Let $\phi \in \mathfrak{F}_d$, $d \ge 1$ and $m(\theta) := \log \mathbb{E}[e^{\theta(\phi(\sigma) - \mathbb{E}[\phi])}]$. Suppose $\phi$ satisfies the assumptions of Theorem 4.1. Then for all $\theta \in [0, 1/\beta_d)$

$$ m(\theta) \le \frac{\gamma_d \theta^2}{2(1 - \beta_d \theta)}. \quad (4.13) $$

and for all $\theta \in (-1/\beta_d, 0]$,

$$ m(\theta) \le \frac{\gamma_d \theta^2}{2}. \quad (4.14) $$

*Proof of Theorem 4.1.* For $\theta := t/(\gamma_d + \beta_d t)$, Chernoff's inequality and (4.13) give for all $t \ge 0$

$$ \mathbb{P}[\phi(\sigma) - \mathbb{E}[\phi(\sigma)] \ge t] \le e^{-\theta t + \log m(\theta)} \le e^{\frac{-t^2}{2(\gamma_d + \beta_d t)}}. $$

Taking $\theta = -t/\gamma_d$ and (4.14) yields the lower tail. $\square$
For the case $d = 1$, a better inequality is established in the proofs of Proposition 1.1 and Theorem 1.5 in [41] using the method of exchangeable pairs. An exchangeable pair is a couple of random variables $(X, X')$ invariant by permutation, so it has the same distribution as $(X', X)$. We prove Lemma 4.1 by induction, using the following rephrasing of Chatterjee's method of exchangeable pairs to prove concentration.

**Proposition 4.2** ([43][Proof of Thm. 1.5]). Let $\mathcal{X}$ be a separable metric space, $(X, X')$ be an exchangeable pair of $\mathcal{X}$-valued random variables. Let $f: \mathcal{X} \to \mathbb{R}$ such that $\mathbb{E}[f] := \mathbb{E}[f(X)] = 0$. Suppose $F: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a square-integrable antisymmetric function which satisfies

$$f(X) := \mathbb{E}[F(X, X') | X] \\ \text{and } \mathbb{E}|e^{\theta f(x)} F(X, X')| < \infty \text{ for all } \theta \in \mathbb{R}. \text{ Then for all } \theta \in \mathbb{R} \\ \left|\mathbb{E}[f(X)e^{\theta f(X)}]\right| \le |\theta| \mathbb{E}[e^{\theta f(X)} \Delta(X)] \quad (4.15) \\ \text{where} \\ \Delta(X) := \frac{1}{2} \mathbb{E}[|F(X, X')(f(X) - f(X'))| | X].$$

As explained in [41, 42], defining an exchangeable pair $(X, X')$ on $\mathcal{X} \times \mathcal{X}$ is equivalent to the consideration of a reversible Markov kernel $P$ on $\mathcal{X} \times \mathcal{X}$ defined by $Ph(x) = \mathbb{E}[h(X') | X = x]$ for all function $h$. Given a function $f$ of zero mean, the antisymmetric function $F$ can then be obtained as $F(X, X') = g(X) - g(X')$ where $g$ satisfies the Poisson equation

$$g - Pg = f$$

which can generally be constructed as $g = \sum_{k \ge 0} P^k f$. If $\mathcal{X}$ is a finite group and $P$ is the kernel of an ergodic random walk on $\mathcal{X}$ which puts constant mass on conjugacy classes, the previous infinite sum converges and [42][Theorem 1.2] provides a concentration result in terms of what is essentially the mixing time of the random walk. Lemma 4.1 is proved by refining this result, to handle the case of a non-uniform bound on the quantity $\Delta(\sigma)$ and get a Bernstein-like inequality. This is analog to proving concentration bounds for self-bounding functions or weakly self-bounding functions [33].

On the symmetric group, one obvious candidate of a Markov kernel is that of random transpositions. The corresponding exchangeable pair is $(\sigma, \sigma\tau)$ where $\tau = (IJ)$ is a random transposition with $I, J$ uniform and independent in $[n]$ ($\tau$ can be the identity). The random transposition chain puts constant mass on the identity and on transpositions, which are conjugacy classes, and thus can be applied the previously mentioned argumentation, its mixing time having been completely determined from the work of Diaconis and Shahshahani [61]. Adapting arguments of [41][Chapt. 4], we arrive at the following lemma, proved in Section 4.3.2.
**Lemma 4.2.** Let $f: \mathcal{S}_n \to \mathbb{R}$ have zero mean. There exists a function $F: \mathcal{S}_n \times \mathcal{S}_n \to \mathbb{R}$ such that $\mathbb{E}[F(\sigma, \sigma\tau) | \sigma] = f(\sigma)$. Furthermore, if $C \ge 0$ is a constant such that $|f(\sigma) - f(\sigma\tau)| \le C$ for all $\sigma \in \mathcal{S}_n$ and transposition $\tau$ then

$$|F(\sigma, \sigma\tau)| \le \frac{Cn}{2} \left( \log \left( \frac{24 \|f\|_{\infty} n}{C} \right) + \frac{(2/n)(2 - e^{-2/n})}{1 - e^{-2/n}} \right). \quad (4.16)$$

If $f$ has degree 1, $F = (n/2)f$, so one has actually $|F(\sigma, \sigma\tau)| \le Cn/2$.

From the previous lemma, upper bounding $\Delta(\sigma)$ essentially comes down to various quantities involving $\phi$ only. This will be done using a tensor representation of the function $\phi$, namely we represent the function $\phi$ as $\phi(\sigma) = \text{tr}(AS^{\otimes d})$ for some $A \in M_n(\mathbb{R}_+)^{\otimes d}$. Restricting first to homogeneous functions, we can follow most of the arguments of Chatterjee in the one-dimensional case, which leads to the following lemmas, proved in Section 4.3.3.

**Lemma 4.3.** Let $\phi \in \mathcal{F}$. A.s.

$$|\phi(\sigma) - \phi(\sigma\tau)| \le \begin{cases} 2 \|\nabla\phi\|_{\infty} & \text{if } d = 1 \\ 6 \|\nabla\phi\|_{\infty} & \text{if } d \ge 2 \end{cases} \quad (4.17)$$

**Lemma 4.4.** Let $\phi \in \mathcal{F}_{=d}$. Then

$$(i) \qquad \frac{n}{2d} \mathbb{E}[\phi(\sigma) - \phi(\sigma\tau) | \sigma] = \left(1 - \frac{d-1}{2n}\right) \phi(\sigma) - D\phi(\sigma) - U\phi(\sigma).$$

$$(ii) \qquad \frac{n}{2d} \mathbb{E}[|\phi(\sigma) - \phi(\sigma\tau)| | \sigma] \le \left(1 - \frac{d-1}{2n}\right) \phi(\sigma) + D\phi(\sigma) + U\phi(\sigma).$$

(iii) $D\phi \in \mathcal{F}_{=(d-1)}$ satisfies

$$\mathbb{E}[D\phi] = \left(1 - \frac{d-1}{n}\right) \mathbb{E}[\phi].$$

**Remark 4.4.** The degree 1 case is made much simpler as in this case the function $\phi - \mathbb{E}[\phi]$ is actually an eigenfunction of the random transposition kernel. In general, decomposing the function into a basis of eigenfunctions or using representation theory can provide a neat expression of the function $F$ in Lemma 4.2, but is not clear how to relate the projections onto eigenspaces to the hypotheses made on $\phi$, in particular the non-negativity of the coefficients. This seems however to be the good strategy if one wants to get rid of the log factor, and could provide further improvements in the proof of Theorem 4.1, allowing perhaps to get rid of the consideration of the operators $D$ and $U$. For instance, it is always possible to replace the function $\phi$ by another representative $\psi \in \mathcal{F}$, which yields the same function on $\mathcal{S}_n$ but has the property that
$D\phi = 0$. The issue is of course that we lose the non-negativity of the coefficients, which seems essential to get a self-bounding property like in the lemma. Note that writing $\phi(\sigma) = \text{tr}(AS^{\otimes d})$ can already be seen as the use of a specific representation of the symmetric group, the $d$-fold tensor product of the standard representation (by permutation matrices).

*Proof of Lemma 4.1.* The result is proved by induction on the degree. The case $d = 1$ is proved in [41] but can be recovered from the following arguments.

Let $\phi \in \mathfrak{F}_d$ satisfy the assumptions of Theorem 4.1. Let $\psi := \phi - \mathbb{E}[\phi]$ denote the centered version of $\phi$ and $m(\theta) := \log \mathbb{E}[e^{\theta\psi(\sigma)}]$.

Consider the function $F$ obtained from Lemma 4.2 for the case $f = \psi$ and set $\Delta(\sigma) := 1/2 \mathbb{E}[|F(\sigma, \sigma\tau)||f(\sigma) - f(\sigma\tau)| | \sigma]$. Equation (4.17) gives an upper bound on the constant $C$ appearing in (4.16), and the definition (4.12) of $\beta_d$ is made to give the a.s. bound $|F(\sigma, \sigma\tau)| \le \beta_d(n/2d)$. On the other hand, decompose $\phi = \sum_{l=0}^d \phi_l$ as a sum of homogeneous functions with non-negative coefficients. We can suppose that $\phi_0 = 0$. From Point (ii) in Lemma 4.4, one gets the bound in (conditional) expectation

$$ \begin{aligned} \frac{n}{2d} \mathbb{E}[|\phi(\sigma) - \phi(\sigma\tau)| | \sigma] &\le \sum_{l=1}^{d} \frac{n}{2l} \mathbb{E}[|\phi_l(\sigma) - \phi_l(\sigma\tau)| | \sigma] \\ &\le \sum_{l=1}^{d} \phi_l(\sigma) + D\phi_l(\sigma) + U\phi_l(\sigma) \\ &= \phi(\sigma) + D\phi(\sigma) + U\phi(\sigma). \end{aligned} $$

By assumption (4.6), $U\phi(\sigma) \le C_U$. From Point (iii) of Lemma 4.4 $\mathbb{E}[D\phi] \le \mathbb{E}[\phi]$, hence letting $\psi_2 := D\phi - \mathbb{E}[D\phi]$, one has

$$ \begin{aligned} \Delta(\sigma) &\le \frac{\beta_d}{2} (\psi(\sigma) + \psi_2(\sigma) + 2\mathbb{E}[\phi] + C_U) \\ &\le \frac{\beta_d}{2} (\psi(\sigma) + \psi_2(\sigma) + \tilde{\gamma}_d) \end{aligned} $$

where we write $\tilde{\gamma}_d := 2\mathbb{E}[\phi] + C_U$. Apply (4.15) to obtain

$$ |\mathbb{E}[\psi(\sigma)e^{\theta\psi(\sigma)}]| \le \frac{\beta_d}{2} |\theta| \mathbb{E}[e^{\theta\psi(\sigma)}(\psi(\sigma) + \psi_2(\sigma) + \tilde{\gamma}_d)]. \quad (4.18) $$

Now by (iii), $\psi_2$ is the centered version of a degree $d-1$ function with non-negative coefficients. In the case $d = 1$, $\psi_2 = 0$ so the previous inequality can easily be integrated to give (4.13) (see the proof of Thm. 1.5 in [41]). In the general case, we make use of the following duality formula for the entropy functional, to relate the moment generating functions of $\psi$ and that of $\psi_2$.

**Proposition 4.3** ([34][Thm. 4.13]). Let $Y$ be a non-negative random variable. Define the entropy of $Y$ as

$$ \text{Ent}(Y) := \mathbb{E}[Y \log Y] - \mathbb{E}[Y] \log \mathbb{E}[Y]. \quad (4.19) $$
The entropy satisfies the variational relation

$$ \mathrm{Ent}(Y) = \sup_W \mathbb{E} \left[ (W - \log \mathbb{E}[e^W]) Y \right] \quad (4.20) $$

where the supremum is over all random variables with finite exponential moment.

Notice that

$$ \frac{\mathrm{Ent}(e^{\theta\psi(\sigma)})}{\mathbb{E}[e^{\theta\psi}]} = \theta m'(\theta) - m(\theta), $$

which is at the basis of the well known Herbst argument to prove concentration inequalities (see [34]). Letting $m_2(\theta) := \log \mathbb{E}[e^{\theta\psi_2(\sigma)}]$, (4.20) implies

$$ \mathbb{E}[|\theta| e^{\theta\psi(\sigma)} \psi_2(\sigma)] \le \mathbb{E}[e^{\theta\psi(\sigma)}] m_2(|\theta|) + \mathrm{Ent}(e^{\theta\psi(\sigma)}). $$

Dividing by $\mathbb{E}[e^{\theta\psi(\sigma)}]$ in (4.18) thus yields

$$ \begin{aligned} |m'(\theta)| &\le \frac{\beta_d}{2} \left( |\theta| m'(\theta) + \tilde{\gamma}_d |\theta| + m_2(|\theta|) + \frac{\mathrm{Ent}(e^{\theta\psi(\sigma)})}{\mathbb{E}[e^{\theta\psi(\sigma)}]} \right) \\ &= \frac{\beta_d}{2} \left( (|\theta| + \theta)m'(\theta) - m(\theta) + \tilde{\gamma}_d |\theta| + m_2(|\theta|) \right). \end{aligned} $$

The term $m(\theta)$ can be neglected, observing that $e^m$ is a convex function, which at $\theta = 0$ takes value 1 and derivative $\mathbb{E}[\psi] = 0$, implying $m'(\theta)$ has the sign of $\theta$ and $m(\theta) \ge 0$ for all $\theta \in \mathbb{R}$. Hence for $\theta \in [0, 1/\beta_d)$

$$ m'(\theta) \le \frac{(\beta_d \tilde{\gamma}_d / 2) \theta}{1 - \beta_d \theta} + \frac{(\beta_d / 2) m_2(\theta)}{1 - \beta_d \theta}. $$

Now assumption (4.6) was made so that $D\phi$ satisfies the same conditions as $\phi$ and can thus be applied the induction hypothesis:

$$ m_2(\theta) \le \frac{\gamma_{d-1} \theta^2}{2(1 - \beta_{d-1} \theta)}. $$

For all $\theta \in [0, 1/\beta_d)$, we can bound further

$$ \frac{\beta_d \theta}{1 - \beta_{d-1} \theta} \le \frac{\beta_d}{\beta_d - \beta_{d-1}} = 1. $$

As $m(0) = 0$ we deduce that for all $\theta \in [0, 1/\beta_d)$

$$ \begin{aligned} m(\theta) &\le \int_0^\theta \frac{(\beta_d \tilde{\gamma}_d / 2 + \gamma_{d-1} / 4)u}{1 - \beta_d u} du \\ &\le \frac{(\beta_d \tilde{\gamma}_d / 2 + \gamma_{d-1} / 4)\theta^2}{2(1 - \beta_d \theta)}. \end{aligned} $$

Finally, (4.12) implies that $\beta_d \tilde{\gamma}_d / 2 + \gamma_{d-1} / 4 \le \gamma_d$, which proves (4.13).
For the lower tail, consider $\theta \in (-1/\beta_d, 0]$. Using the same computations as above, bound

$$ 
\begin{aligned}
|m'(\theta)| & \le \frac{\beta_d}{2} (\tilde{\gamma}_d |\theta| + m_2(|\theta|)) \\
& \le (\beta_d \tilde{\gamma}_d / 2 + \gamma_{d-1} / 4) |\theta| \\
& \le \gamma_d |\theta|
\end{aligned}
$$

which shows $m(\theta) \le \gamma_d \theta^2 / 2$.

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

### 4.3.2 Almost sure bound on F: proof of Lemma 4.2

Let $\mu$ be the probability measure on $\mathfrak{S}_n$ which puts mass $1/n$ on the identity and $2/n^2$ on transpositions. The random transposition Markov chain is the random walk on $\mathfrak{S}_n$ defined by iid increments of law $\mu$. These are symmetric hence the uniform distribution unif is stationary. The Markov chain is ergodic and its mixing properties have been thoroughly investigated in [61]. In particular, it was proved that for all $k \ge 0$,

$$ \|\mu^{*k} - \text{unif}\|_{\text{TV}} \le 6ne^{-2k/n}. \qquad (4.21) $$

Let $P$ denote the transition matrix of random transpositions and $f$ be a function on $\mathfrak{S}_n$ with zero mean under the uniform measure. Then the function $F$ given by

$$ F(\sigma, \sigma') := \sum_{k \ge 0} (P^k f(\sigma) - P^k f(\sigma')) $$

is well defined by the total variation convergence above and satisfies $\mathbb{E}[F(\sigma, \sigma') | \sigma] = f(\sigma)$. We refer to [41, 42] for details.

Lemma 4.2 is obtained by bounding $F$ in two ways. On the one hand (4.21) implies

$$ |P^k f(\sigma)| = |P^k f(\sigma) - \mathbb{E}[f]| \le 12 \|f\|_{\infty} ne^{-2k/n} $$

and thus

$$ |P^k f(\sigma) - P^k f(\sigma\tau)| \le 24 \|f\|_{\infty} ne^{-2k/n}. $$

The second bound is based on the fact that $\mu$ puts constant mass on conjugacy classes. As observed by Chatterjee in [41, 42], this implies that

$$ |P^k f(\sigma) - P^k f(\sigma\tau)| \le \max_{\sigma', \tau'} |f(\sigma') - f(\sigma'\tau')| \le C $$

for all $k \ge 0$, $\sigma \in \mathfrak{S}_n$ and transposition $\tau$. Combine the two bounds as

$$ 
\begin{aligned}
|F(\sigma, \sigma\tau)| & \le \sum_{k \ge 0} \min \left(C, 24 \|f\|_{\infty} ne^{-2k/n}\right) \\
& \le C \sum_{k \ge 0} \min \left(1, 24 C^{-1} \|f\|_{\infty} ne^{-2k/n}\right) \\
& \le C \left(\frac{n}{2} \log (24C^{-1} \|f\|_{\infty} n) + 1 + \frac{1}{1 - e^{-2/n}}\right)
\end{aligned}
$$
### 4.3.3 Tensor representation

We now prove Lemmas 4.3 and 4.4.

**Lemma 4.5.** Let $\phi \in \mathfrak{F}$ and $\tau = (IJ)$. For all $\sigma \in \mathfrak{S}_n$,

$$ \phi(\sigma\tau) = \phi(\sigma) + \partial_{I\sigma(J)}\phi(\sigma) + \partial_{J\sigma(I)}\phi(\sigma) - \partial_{I\sigma(I)}\phi(\sigma) - \partial_{J\sigma(J)}\phi(\sigma) \tag{4.22} \\ + 2\partial_{I\sigma(I)}\partial_{J\sigma(J)}\phi(\sigma) + 2\partial_{I\sigma(J)}\partial_{J\sigma(I)}\phi(\sigma). $$

*Proof.* Let $\phi \in \mathfrak{F}$. Decomposing $\phi$ into homogeneous components, it suffices to consider the case of a homogeneous function. Suppose therefore that $\phi$ is homogeneous of degree $d \ge 1$. It can be realized as $\phi(\sigma) = \text{tr}(AS^{\otimes d})$ for some $A \in M_n(\mathbb{R}_+)^{\otimes d}$. We start with a simple computation relating derivatives of $\phi$ with the tensor $A$.

Let $E_{ij}$ denote the matrix which has entry $(i, j)$ equal to 1 and all other entries equal to 0. For all $M \in M_n(\mathbb{R})$, $i, j \in [n]$,

$$ \partial_{ij}\phi(M) = \sum_{k=1}^{d} \text{tr}(A M^{\otimes (k-1)} \otimes E_{ij} \otimes M^{\otimes (d-k)}). \tag{4.23} $$

Indeed, for all $t \in \mathbb{R}$, expanding the tensor product yields

$$ (M + tE_{ij})^{\otimes d} = M^{\otimes d} + t \sum_{k=1}^{d} M^{\otimes (k-1)} \otimes E_{ij} \otimes M^{\otimes (d-k)} + O(t^2) $$

Dividing by $t \ne 0$ and taking the limit $t \to 0$ gives the result.

For the sequel, we make use of the multilinearity of $\phi$. Given multi-indices $i, j \in [n]^d$, write $A_{i,j} = A_{i_1 \cdots i_d}$. The multilinearity implies we can suppose that $A_{i,j} = 0$ whenever $i$ or $j$ has two identical coordinates. Consequently the computation of $\text{tr}(AM)$ does not depend either on the entries $M_{ij}$ when $i$ or $j$ has some identical coordinates. More precisely, the kernel of the linear map $M \mapsto \text{tr}(AM)$ contains the subspace $H$ of tensors whose only non-zero entries are such multi-indices. Therefore when computing $\text{tr}(AM)$, one can freely replace $M$ with any of its representative modulo $H$, which allows in particular to get rid of potential dependency properties between entries of $S$. The permutation matrix of $\tau$ is $T = I + M_{IJ}$ with

$$ M_{IJ} := E_{IJ} + E_{JI} - E_{II} - E_{JJ}. $$

Note that if we write products of permutation from right to left, so $\sigma\tau$ applies $\tau$ first and then $\sigma$, the permutation matrix of $\sigma\tau$ is $TS$, hence $\phi(\sigma\tau) = \text{tr}(AT^{\otimes d}S^{\otimes d})$. By expanding the tensor product,

$$ T^{\otimes d} = I + \sum_{k=1}^{d} I^{\otimes (k-1)} \otimes M_{IJ} \otimes I^{\otimes (d-k)} \\ + \sum_{k_1 < k_2 \in [d]} I^{\otimes (k_1-1)} \otimes M_{IJ} \otimes I^{\otimes (k_2-k_1)} \otimes M_{IJ} \otimes I^{\otimes (d-k_2)} \mod H. $$
Expanding the expression of $M_{IJ}$ in the second sum yields terms like $E_{IJ} \otimes E_{II}$ which are also in $H$ and can be discarded. Now by (4.23),

$$ \sum_{k=1}^{d} \mathrm{tr}(A(I^{\otimes (k-1)} \otimes E_{IJ} \otimes I^{\otimes (d-k)}) S^{\otimes d}) = \partial_{I\sigma(J)} \phi(\sigma) $$

and a similar observation can be made for order 2 derivatives. This proves Lemma 4.5. $\square$

Lemma 4.3 can be deduced easily, provided one can control second order derivatives. This requires no additional assumption, for taking partial derivates can only give a smaller function, as proved by the following lemma.

**Lemma 4.6.** Let $\phi \in \mathfrak{F}$. For all $k \ge 1$ and $\mathbf{i}, \mathbf{j} \in [n]^k$,

$$ \| \partial_{\mathbf{ij}}^k \phi \|_{\infty} \le \| \phi \|_{\infty}. \qquad (4.24) $$

*Proof.* The general case follows from the $k=1$ case by an easy induction. Let $i, j \in [n]$. Note that by multilinearity, the partial derivative $\partial_{ij}\phi$ cannot contain any indeterminate $X_{ik}$ or $X_{kj}, k \in [n]$, so $\partial_{ij}\phi(\sigma) = \partial_{ij}\phi((\sigma(i)j)\sigma)$. Hence the maximum is always realized for a permutation $\sigma$ such that $\sigma(i) = j$, but then for such permutations $\phi$ actually coincides with the partial derivative $\partial_{ij}\phi$. Consequently

$$ \begin{aligned} \max_{\sigma \in \mathfrak{S}_n} |\partial_{ij}\phi(\sigma)| &= \max_{\sigma: \sigma(i)=j} |\partial_{ij}\phi(\sigma)| \\ &\le \max_{\sigma: \sigma(i)=j} |\phi(\sigma)| \\ &\le \|\phi\|_{\infty}. \end{aligned} $$

$\square$

*Proof of Lemma 4.3.* If $\phi$ is assumed to have non-negative coefficients, (4.22) shows that

$$ \begin{aligned} |\phi(\sigma) - \phi(\sigma\tau)| &\le |\partial_{I\sigma(J)}\phi(\sigma) + \partial_{J\sigma(I)}\phi(\sigma) - \partial_{I\sigma(I)}\phi(\sigma) - \partial_{J\sigma(J)}\phi(\sigma)| \\ &\quad + 2\partial_{I\sigma(I)}\partial_{J\sigma(J)}\phi(\sigma) + 2\partial_{I\sigma(J)}\partial_{J\sigma(I)}\phi(\sigma) \\ &\le 2 \|\nabla\phi\|_{\infty} + 4 \max_{i,j,k,l \in [n]} |\partial_{ij,kl}^2 \phi(S)|, \end{aligned} $$

which establishes (4.17) thanks to the previous lemma. $\square$

*Proof of Lemma 4.4.* Restricting to a homogeneous function $\phi \in \mathfrak{F}_{=d}$, (4.22) gives by
averaging over I, J

$$ \frac{n}{2d} \mathbb{E}[\phi(\sigma) - \phi(\sigma\tau) | \sigma] = \frac{1}{2dn} \sum_{i,j \in [n]} (\partial_{i\sigma(i)}\phi(\sigma) + \partial_{j\sigma(j)}\phi(\sigma) - \partial_{i\sigma(j)}\phi(\sigma) - \partial_{j\sigma(i)}\phi(\sigma) \\ -2\partial_{i\sigma(i)}\partial_{j\sigma(j)}\phi(\sigma) - 2\partial_{i\sigma(j)}\partial_{j\sigma(i)}\phi(\sigma)) \\ = \left(1 - \frac{d-1}{2n}\right)\phi(\sigma) - \frac{1}{dn} \sum_{i,j \in [n]} \partial_{i\sigma(j)}\phi(\sigma) - \frac{1}{dn} \sum_{i,j \in [n]} \partial_{i\sigma(j)}\partial_{j\sigma(i)}\phi(\sigma), $$

which gives Point (i) of the Lemma. The second equality arises from the relation (4.4).

The bound in absolute value (ii) is obtained similarly, using first triangle inequality in (4.22). Finally Point (iii) is proved easily. □
# Chapter 5

## Cutoff for mixtures of permuted Markov chains

### 5.1 Models and main results

Like the previous chapter, the content of this chapter is yet to be published. We establish a cutoff phenomenon at entropic time for a model of Markov chain in random environment.

#### 5.1.1 Cutoff for mixtures of permuted Markov Chains

Let $n \ge 1$ be an integer and $P_1, P_2$ two $n \times n$ stochastic matrices. This work is basically concerned with the mixing time of the Markov chain with transition matrix

$$p_1 P_1 + p_2 S P_2 S^{-1}$$

where $p_1 \in (0, 1)$, $p_2 = 1 - p_1$ and $S$ is a uniform $n \times n$ permutation matrix. This model is inspired by the work [92] 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. The model above aims to look at more general Markov chains, possibly non reversible, obtained by superposing two deterministic ones with a layer of randomness in between taking the form of a permutation of the states. Our model will in fact allow the probabilities $p_1, p_2$ to depend on the current state of the chain and on the permutation $S$, which is necessary to recover the case of the simple random walk on the superposition of graphs if these are not regular. For this case however, and more generally for reversible chains, there is a more adapted model tailored to preserve reversibility, corresponding to a specific choice of $p_1, p_2$, which we will describe afterwards.
Let us introduce or recall notations that will be used throughout this chapter. Given two measures $\mu, \nu$ on a countable set $S$, their total variation distance is defined as

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

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_{\text{mix}}(x, \varepsilon) := \inf\{t \ge 0 : \|P^t(x, \cdot) - \pi\|_{\text{TV}} < \varepsilon\}. $$

and the worst-case mixing time is

$$ t_{\text{mix}}(\varepsilon) := \sup_{x \in S} t_{\text{mix}}(x, \varepsilon). $$

If the chain is not irreducible or aperiodic, we consider the mixing time to be infinite. Given two functions $f, g: \mathbb{N} \to \mathbb{R}$, $f(n) = O(g(n))$ if there exists a constant $C > 0$ such that $|f(n)| \le Cg(n)$ for all $n$, $f = o(g)$ if $f(n)/g(n) \xrightarrow{n \to \infty} 0$ and $f = \Theta(g)$ if $f = O(g)$ and $g = O(f)$. An event $A = A(n)$ is said to occur with high probability if $\mathbb{P}(A) = 1 - o(1)$. Given an integer $n \ge 1$, we write $[n] := \{1, \dots, n\}$.

**Theorem 5.1.** Let $P_1, P_2$ be two $n \times n$ stochastic matrices, $p_1, p_2 \in M_n([0, 1])$ be $n \times n$ matrices with entries in $[0, 1]$ such that $p_1 + p_2 = 1$ entry-wise and $\sigma$ a permutation of $n$ elements chosen uniformly at random. Consider the Markov chain with transition probabilities

$$ \forall x, y \in [n]: \quad \mathcal{P}_0(x, y) := p_1(x, \sigma(x)) P_1(x, y) + p_2(x, \sigma(x)) P_2(\sigma(x), \sigma(y)). \quad (5.1) $$

Suppose

(H1) for each $i \in \{1, 2\}$ the non-zero entries of $P_1, P_2$ are $\Theta(1)$ and $\max_{y \in V} \sum_{x \in V} P_i(x, y) = O(1)$.

(H2) the entries of $p_1, p_2$ are $\Theta(1)$.

(H3) For all $x \in [n]$ and $i = 1, 2$:

$$ |\{y \in V : \exists k \ge 0 : P_i^k(x, y) > 0\}| \ge \begin{cases} 3 & \text{if } i = 1 \\ 2 & \text{if } i = 2 \end{cases}, $$

(H4) There exists a constant $l \ge 1$ independent of $n$ such that

$$ |\{x \in V | \forall y \in V : P(x, y) > 0 \Leftrightarrow (I + P)^l(y, x) > 0\}| = n - o(n) $$
Then the chain defined by (5.1) is irreducible, aperiodic and there exists $h = \Theta(1)$ for which the following holds. For all $\varepsilon \in (0, 1)$, there exists $C(\varepsilon)$ such that for all $x \in [n]$ with high probability,

$$ t_{\text{mix}}(x, \varepsilon) \le \frac{\log n}{h} + C(\varepsilon)\sqrt{\log n}, \\ t_{\text{mix}}(x, 1 - \varepsilon) \ge \frac{\log n}{h} - C(\varepsilon)\sqrt{\log n}. $$

Our proof adapts the strategy used to prove cutoff for non-backtracking chains [19, 28, 29] to handle backtracking chains as well, including reversible ones, but reversibility does not need to be assumed. This is undoubtedly the most salient aspect of our contribution, as earlier works proving cutoffs in random environment generally relied on reversibility or a non-backtracking property, which can be thought of as the opposite of reversibility. Thus an important goal of our work 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 which in turn yield a weaker result than in the reversible model studied in [92]: note that in Theorem 5.1, the starting state of the chain is fixed before generating the random environment. This implicitly makes the state $x$ typical: from the result for a fixed $x$ one can for instance replace $x$ with a state chosen uniformly at random. However it cannot be chosen arbitrarily after the permutation $\sigma$ is fixed. Consequently our result does not establish uniform cutoff in the sense that with high probability $t_{\text{mix}}(x, \varepsilon) = \log n/h + o(\log n)$ simultaneously for all $x \in [n]$. It turns out that with the level of generality considered here, the lack of a uniform result is not an artifact of the proof but is characteristic of the model. In whole generality, there is no uniform cutoff at entropic time, as proved by the following result.

**Theorem 5.2.** For all $a > 1$, there exist transition matrices $P_1, P_2$ satisfying Assumptions (H1) - (H4) such that with high probability, the Markov chain $\mathcal{P}_0 = 1/2(P_1 + SP_2S^{-1})$ has worst-case mixing time $\max_x t_{\text{mix}}(x, 1/2) \ge (\log n)^a$.

The lack of uniform cutoff 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$ [20, 73], while the typical mixing time is $O(\log n)$ [22].

In our model, the potential slowdown of the chain is a consequence of irreversibility: having too much bias on the transition probabilities, the environment can with positive probability contain trapping neighbourhoods, from which the chain escapes in a time that scales exponentially with the size of the neighbourhood. The previous proposition
is based on an example where these neighbourhoods are of size $O(\log \log n)$, hence the polylogarithmic order in the result. Our next result establishes a matching upper bound of polylogarithmic order on the worst-case mixing time.

**Theorem 5.3.** In the setting of Theorem 5.1 under the same assumptions there exists $a \ge 1$ such that for all $\varepsilon \in (0, 1)$, with high probability

$$t_{\text{mix}}(\varepsilon) \le (\log n)^a.$$

*Remark 5.1.* Let us comment on the assumptions made above. Hypotheses (H1) and (H2) bound uniformly in $n$ the transition probabilities and the number of ingoing and outgoing transitions at every state, while (H3) imposes a minimal size on the set of states reachable by a given state. These are not restrictive: it is easy to find examples where these assumptions are not satisfied and the mixing time scales differently as $\Theta(\log n)$, without cutoff. The most restrictive assumption is thus (H4). It can be interpreted as a constraint on the degree of irreversibility of the chains $P_1, P_2$, which for instance prevents them from having too many transient states. It is not clear whether it is really needed for our result but from the proof it does not seem superfluous either, as having too many transient states may amplify the trapping phenomenon mentioned above. Nonetheless, irreversibility is still permitted to a considerable extent.

### 5.1.2 A reversible model

Taking a mixture of transition matrices seems a most natural way to blend together two Markov chains. However if the chains are reversible there is another, which preserves reversibility, while a convex combination of reversible chains fails to be reversible in general.

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) \qquad (5.2)$$

for all $x, y \in V$, 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 [128] 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 superpositioning the corresponding electrical networks, that is taking a linear positive combination of the conductances. As was explained before, the lack of a uniform bound in Theorem 5.1 is a consequence of irreversibility, so wo may hope for stronger results in the reversible case. The following theorem confirms this intuition.

**Theorem 5.4.** Let $n \ge 1$ be an integer, $(G_1, c_1), (G_2, c_2)$ two electrical networks with common vertex set $[n]$, $\alpha, \beta > 0$ and $\sigma$ a permutation of $n$ elements chosen uniformly at random. Consider the Markov chain on $[n]$ defined by the electrical network $(G^*, c)$ with conductances

$$ \forall x, y \in [n] : c^*(x, y) := \alpha c_1(x, y) + \beta c_2(\sigma(x), \sigma(y)). \quad (5.3) $$

Suppose

(H1) The degrees and non-zero conductances of $(G_1, c_1)$ and $(G_2, c_2)$ are all $\Theta(1)$.

(H2) $\alpha, \beta$ are constants independent of $n$.

(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 = \Theta(1)$ for which the following holds. For all $\varepsilon \in (0, 1)$, there exists a constant $C(\varepsilon)$ such that with high probability,

$$ \min_{x \in [n]} t_{\text{mix}}(x, 1-\varepsilon) \ge \frac{\log n}{h} - C(\varepsilon)\sqrt{\log n}, $$

$$ \max_{x \in [n]} t_{\text{mix}}(x, \varepsilon) \le \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 \to \infty} \frac{\max_{x \in [n]} t_{\text{mix}}(x, \varepsilon)}{\min_{x \in [n]} t_{\text{mix}}(x, 1-\varepsilon)} = 1 $$

in probability.

**Remark 5.2.** Being defined with conductances, the chain considered in the previous theorem is thus automatically reversible. It is a particular case of (5.1): 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 (5.1) taking

$$ p_1(x, y) := \frac{\alpha c_1(x)}{\alpha c_1(x) + \beta c_2(y)}. $$
Remark 5.3. 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 [92] 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 5.7), so our result is also true when superpositionning simple graphs and discarding multi-edges in the resulting graph.

### 5.1.3 Related works

To this date, it remains an open question to determine a characterization of cutoff. A sufficient condition was given by Salez in [149], which is certainly the closest result one has ever been from a full characterization. This 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 [57, 150] for global references on the subject), the seminal work of Lubetzky and Sly [122] 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 an *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 [19]. This case is also considered in [22], 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 $\Theta((\log n)^2)$ by Fountoulakis and Reed [73] and Benjamini, Kosma and Wormald [20], while in the configuration model cutoff at entropic time was obtained subsequently by Ben Hamou, Lubetzky and Peres in [17]. Models of random
non-backtracking chains have also been considered by Bordenave, Caputo and Salez: [28] considers the non-backtracking walk on directed configuration models, while [29] considers the case of a stochastic matrix in which the entries of each row are permuted uniformly at random. In [50], 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 [90, 91] on random walks on random Cayley graphs of Abelian groups. A model similar to ours is the *PS* model, introduced by Chatterjee and Diaconis [45] and shown to exhibit cutoff at entropic time by Ben Hamou and Peres [18].

Some recent works investigate the case of random graphs with community structures: in [16], 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 [93] 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 [92] 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 [13] 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 [11] and Caputo and Quattropani [39]. A related work is [38] 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 [121, 143] or environments with a Ramanujan property [31]. In fact from the work of Friedman [75] (see also [27]) 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ù [68] falls in that category, which can also be interpreted as a deterministic realization of the *PS* model studied in [18]. Finally, the sufficient condition of Salez [149] allows him to deduce cutoff for a large family of chains satisfying a non-negative curvature criterion, not necessarily random.
### 5.1.4 Proof outline

**Dealing with an unknown invariant measure:** first the absence of a reversibility assumption prevents any knowledge of the invariant measure. To establish mixing, we follow the strategy of [28, 29] of proving convergence towards an approximate invariant measure $\hat{\pi}$. If $\|\mathcal{P}_0^t(x, \cdot) - \hat{\pi}\|_{TV} \le \varepsilon$ holds uniformly in $x$ for a given time $t$, then the invariance property implies that a true invariant measure $\pi$ satisfies $\|\pi - \hat{\pi}\|_{TV} \le \varepsilon$, establishing in particular the uniqueness of the invariant measure. The additional issue here is that Theorem 5.1 is valid only for typical starting states, so we will have to prove that mixing towards $\hat{\pi}$ occurs both at $t \approx \log n/h$ for a typical starting state and at larger times for an arbitrary starting state, namely $t = (\log n)^a$. Note that since $\hat{\pi}$ is not a priori a genuine invariant measure, there is no monotonicity in the distance to equilibrium that would maintain the chain distributed as $\hat{\pi}$ once it has become close to it. We note that Proposition 5.2 below gives an expression for the proxy measure $\hat{\pi}$ we use in our proofs.

**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 [19, 28, 29]. First we prove a quenched entropic concentration property for trajectories, namely we prove a statement of the form $\mathcal{P}(X_0\cdots X_t) \approx e^{-th+O(\sqrt{t})}$, where we write $\mathcal{P}(X_0\cdots X_t) = \prod_{i=0}^{t-1} \mathcal{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 [92], 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 for instance.

**Analysis on the quasi-tree:** this part is essentially the only one where reversibility plays a role to obtain a uniform cutoff result. At the basis of the analysis for reversible chains in [92, 93, 13] is the property of uniform transience, which asserts that at any
vertex, the probability to escape to infinity along the neighbouring "branch" of the quasi-tree, conditional on the environment, is lower bounded away from 0 uniformly in $n$. This property extends to any reversible chain on the quasi-tree thanks to a comparison argument, after which the analysis can be conducted pretty much as is done in [92]. On the other hand, such a uniform lower bound may not be achieved in the general model of Theorem 5.1, which is ultimately the reason why cutoff cannot occur for a uniform starting state. Incidentally, the lack of uniform transience is an issue that could already be present in the case of a Galton-Watson tree, leading to a non-uniform cutoff for Erdös-Renyi graphs [22]. Our analysis is thus largely inspired by this paper and the references cited therein. The lack of uniform transience is bypassed by proving that the probability to escape at infinity along is in expectation lower bounded uniformly in $n$. This will again be proved thanks to a comparison argument, namely the chain is going to be compared with a reversible chain, which is the main reason why Hypothesis (H4) comes into play. The lower bound on the expected escape probabilities implies then that such a lower bound is also achieved when restricting to typical points. Very roughly, the difference with the reversible case will thus consist in arguing that the trajectories of the chain remain up to the mixing time on typical parts of the quasi-tree. While uniform transience allows to make many "quenched" statements, ie conditional on the environment, we will have to replace these by "annealed" statements, which average over the environment.

As in [22, 92, 93, 13], the proof of the entropic concentration relies on the use of regeneration times, which are times at which the chain in the quasi-tree crosses a long-range edge for the first and last time in the quasi-tree. 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 [93], 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 generic way. An important requirement for the proof is the fast mixing of the Markov chain underlying 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 in a set of size $e^{th+O(\sqrt{t})}$ at most. This becomes $o(n)$ for $t \le \log n/h - C\sqrt{\log n}$ and a large constant $C > 0$, which is sufficient to conclude provided the invariant measure is well spread-out across the state space. Since the
latter is unknown, we use the proxy measure $\hat{\pi}$ and its expression which is explicit enough for our purpose.

**Concentration of nice trajectories:** the second part of the argument for the upper bound 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 $\mathcal{P}_{\mathfrak{N}}^t(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 $\mathcal{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 4.1 conditional on the two neighbourhoods. The notable difference with the case of non-backtracking chains [19, 28, 29] 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 $dt + 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 4.1 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 4.1 remain sufficiently small to obtain exponential concentration bounds.
**Computation of $\hat{\pi}$:** another 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 mentioned 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 5.2).

**Getting a bound on the worst-case mixing time** : nice paths are in fact really defined only from typical states, so the previous arguments will ensure $\mathcal{P}_0^t(x, \cdot) \simeq \hat{\pi}$ at time $t = \log n/h + O(\sqrt{\log n})$ only for a typical $x$. To obtain an upper bound on the worst-case mixing time, which as remarked in the first paragraph above is crucial to justify $\hat{\pi}$ is close to being invariant, we will essentially argue that for some $a \ge 1$, at time $s = (\log n)^a$ the chain is likely to reach a typical point and have its $t$ subsequent steps following a nice trajectory, regardless of its starting state. Thus mixing at time $t = O(\log n)$ from typical states implies mixing at time $s+t = O((\log n)^a)$ from any starting state. This argument is also used in the reversible case, where $s = \Theta(\log \log n)$ steps are enough, which is the consequence of the quenched uniform lower bound on escape probabilities in quasi-trees. In the general case, a heuristic is as follows: we will get from the estimates on escape probabilities (Prop. 5.4) that these are so unlikely to fall below $(\log n)^{-b}$ for some $b > 0$ that we can basically take $(\log n)^{-b}$ as a quenched lower bound. Thus we can expect it takes $(\log n)^{bl}$ steps at worst for the chain to escape potentially trapping neighbourhoods of size $l$, after which the chain is likely to be back in a typical neighbourhood if $l$ is chosen adequately.

## Organization of the chapter

In Section 5.2 we give material that will be used throughout the paper, including the definition of quasi-trees. In Section 5.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 Theorems 5.1, 5.3 and 5.4. In Section 5.4, we provide a counter-example to uniform entropic mixing time, proving Theorem 5.2. The three next sections deal with the analysis of the quasi-tree: Section 5.5 establish the lower bound on escape probabilities, Section 5.6 proves technical results about the regeneration structure of quasi-trees while Section 5.7 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 5.8, which also
contains the arguments that will lead to the upper bound on the worst-case mixing
time. Finally, these properties are used in Section 5.9 where nice paths are properly
defined and shown to have their probability concentrate around the mean.

## 5.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$, $|S|$ denotes its cardinality, $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 $|f(n)| \le Cg(n)$ for all $n$, $f = o(g)$ if $f(n)/g(n) \xrightarrow{n \to \infty} 0$. We may write $O_{\varepsilon}(\cdot)$ to precise a potential dependence of the implicit constant in $\varepsilon$. Given two functions, $f = \Theta(g)$ if $f = O(g)$ and $g = O(f)$, and $f \gg g$ if $g = o(f)$. 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 $\mathbb{P}(A) = 1 - o(1)$.

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

Consider $(X_t)_{t \ge 0}$ a Markov chain in random environment, ie with random transition probabilities, such as the one defined by (5.1). There are two laws naturally associated with the process $(X_t)_{t \ge 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 \ge 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}[\cdot | X_0 = x]$, $\mathbf{P}_x := \mathbf{P}[\cdot | X_0 := x]$. Of course taking the expectation of the quenched law gives back the annealed law, which is the basis of the following first moment argument that will be used throughout the article. To prove a trajectorial event $A$ has quenched probability vanishing to $0$ in probability as $n \to \infty$, it suffices to prove $A$ has annealed vanishing probability, as Markov's inequality implies for all $\varepsilon > 0$,

$$ \mathbb{P}[\mathbf{P}[A] \ge \varepsilon] \le \frac{\mathbb{P}[A]}{\varepsilon}. \qquad (5.4) $$
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[A] = o(1)$, to obtain $\mathbb{P}_x[A] = o_P(1)$. These can be interpreted as conditional statements for the case where the starting state is also random, with a law which 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[A] = o(1/n)$. This strategy will be used in Section 5.8 to extend results from typical to all states.

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

Let us start by rewriting and actually generalizing our model further, which lacks symmetry in the roles of $P_1$ and $P_2$. To obtain a model that is more symmetric, we construct the chain as a projection of its two-lift: this consists in seeing $P_1, P_2$ as two disjoint components of one Markov chain 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 [92], but it can also prove useful on its own. All in all, the main 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, \quad \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 \mathbb{1}_{x \in V_1} + V_2 \mathbb{1}_{x \in V_2}$. Let $P$ be a stochastic matrix on $V$ with block form $P := \begin{pmatrix} P_1 & 0 \\ 0 & P_2 \end{pmatrix}$ and $p: V \times V \to [0, 1]$ such that $p(x, y) + p(y, x) = 1$ for all $x, y \in V$ and let $q(x, y) := 1 - p(x, y) = p(y, x)$. Consider the Markov chain on $V$ given by the transition probabilities:

$$ \forall x, y \in V: \mathcal{P}(x, y) := \begin{cases} p(x, \eta(x)) P(x, y) & \text{if } V(x) = V(y) \\ q(x, \eta(x)) P(\eta(x), y) & \text{if } V(x) \neq V(y). \end{cases} \quad (5.5) $$

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

$$ \forall x, y \in [n], \bar{\mathcal{P}}(x, y) := \mathcal{P}(x, y) + \mathcal{P}(x, \eta(y)) \quad (5.6) $$
This model contains (5.1) as a particular case: taking $p(x, y) := p_1(x, y - n)$ for all $x \in V_1, y \in V_2$ suffices to define $p$ completely. Furthermore $\sigma - n$ is a uniform permutation on $[n]$. From these it is easily checked that the projected chain $\bar{\mathcal{P}}$ coincides with $\mathcal{P}_0$. This applies in particular to the reversible model by Remark 5.2. Let us remark that in this case the two-lift chain may not be reversible, however its projection to $V/\sim$ is as projecting gives back the chain defined by (5.3).

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 $\mathcal{P}$, then $\bar{\pi}$ is invariant for $\bar{\mathcal{P}}$. Furthermore, total variation distance is non-increasing under projections, so

$$ \| \bar{\mathcal{P}}^t(x, \cdot) - \bar{\pi} \|_{\text{TV}} \le \| \mathcal{P}^t(x, \cdot) - \pi \|_{\text{TV}}. \qquad (5.7) $$

Therefore to obtain the upper bound in Theorem 5.1, which is the most difficult part of the argument, it suffices to prove an upper bound for the two-lift. In fact, our results hold for both chains.

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

$$ \mathbf{P}[X_{t+1/2} = y | X_t = x] = \begin{cases} p(x, \eta(x)) & \text{if } y = x \\ q(x, \eta(x)) & \text{if } y = \eta(x) \\ 0 & \text{otherwise} \end{cases} \qquad (5.8) \\ \mathbf{P}[X_{t+1} = y | X_{t+1/2} = x] = P(x, y) $$

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

### 5.2.3 The graph point of view

To emphasize the underlying tree structure of the Markov chains considered in this paper, these can be visualized as evolving on directed graphs.

**Definition 5.1.** If $K$ is a Markov kernel on a countable state space $S$, the underlying graph $G = (S, E)$ is the oriented graph with vertex set $S$ and edge set

$$ E := \{(x, y) \in S \mid K(x, y) > 0\}. $$

We consider in fact multi-graphs, so that loops and multi-edges are allowed in $G$. In quasi-trees, we will use graphs of Markov chains as parts of a larger structure. To that
end, define a morphism of directed graphs as a map between two graphs that preserves the adjacency relations as well as the orientations of the edges. If weighted graphs are considered, such as underlying graphs of Markov chains, we may also implicitly require that weights are preserved. An isomorphism is as usual a bijective morphism.

Given an oriented edge $e = (x, y) \in E$, write $e^{-} := x$ and $e^{+} := y$ for its initial and terminal vertex respectively. A path $\mathfrak{p}$ in $G$ can be made either of vertices or oriented edges, which can be identified. Given a path $\mathfrak{p}$, we write $K(\mathfrak{p})$ for the product of transition probabilities along the edges of this path.

The set $S$ is equipped with the following metric: for all $x, y \in S$, $d_K(x, y) := \inf\{l \ge 0 : K^l(x, y) > 0\}$. It is not symmetric in general because of irreversibility. It thus gives rise to several notions of balls, depending on the orientation: given $x \in V, r \in \mathbb{N} \cup \{+\infty\}$, the forward and backward (closed) $K$-balls of radius $r$ around $x$ are respectively the sets

$$B_K^+(x, r) := \{y \in S \mid d_K(x, y) \le r\}$$

$$B_K^-(x, r) := \{y \in S \mid d_K(y, x) \le r\}.$$

Without further precision, the $K$-ball of radius $r$ around $x$ is $B_K(x, r) := B_K^-(x, r) \cup B_K^+(x, r)$, which forgets about the orientation of edges. Note that for any $x \in S$, $B_K^+(x, \infty)$ is the set that can be reached by the chain from the state $x$. If $x$ is recurrent, this is the communicating class of $x$.

Apply the previous definition to the case at hand: from now on, let $G = (V, E)$ be the underlying graph of the Markov chain $P$: the graphs $G_1 = (V_1, E_1)$, $G_2 = (V_2, E_2)$ spanned by $V_1$ and $V_2$ respectively are the underlying graphs of $P_1$ and $P_2$ and form two disconnected components of $G$. Adding the edges $(x, \eta(x))$ of the uniform matching yields a random graph $G^* := (V, E^*)$, which can be seen as the underlying graph of the Markov chain $(X_t)_{t \ge 0}$, provided we take into account half-integer time steps (5.8). We introduce a terminology inspired by [92] to distinguish between these edges: an edge $(x, y) \in E^*$ is called a *small-range edge* if $(x, y) \in E$, that is if $P(x, y) > 0$ or $P(y, x) > 0$. An edge $(x, \eta(x))$ added by the random matching will be called a *long-range edge*. Note that long-range edges appear in $E$ with both orientations. When restricting to integer times only, the Markov chain $X$ moves along a long-range and a small-range edge at once or along a small-range edge only. Thus two vertices at *P*-distance 1 from each other may in fact be separated by two edges in $G^*$. Similarly, a path in $G^*$ without further precision will be refering to a possible trajectory of the chain *P*. Finally, let us remark that in the reversible model edges appear with both orientations so graphs can actually be considered non-oriented.
### 5.2.4 Quasi-trees

We now define quasi-trees, which are designed to be an infinite approximation of the graph $G^*$. The same terminology and notation as in the finite setting will be used 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 5.2.** A rooted quasi-tree is a 4-tuple $(\mathcal{G}, O, \eta, \iota)$ where $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ is an oriented graph, $O \in \mathcal{V}$ is a distinguished vertex and $\iota$ is a map $\iota: \mathcal{V} \to \mathcal{V}$ that labels vertices of $\mathcal{G}$ with states in $\mathcal{V}$. We call $\iota(x)$ the type of the vertex $x \in \mathcal{V}$. Finally $\eta$ is a map $\eta = \mathcal{V} \to \mathcal{V}$, which satisfies:

(i) $\eta$ is an involution either of $\mathcal{V}$ or of $\mathcal{V} \setminus \{O\}$ with no fixed point. The quasi-tree is called respectively *two-sided* or *one-sided* in these cases.

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

(iii) for all $x, y \in \mathcal{V}$, there is a unique family, possibly empty, of long-range edges $e_1, \dots, e_k$ such that all paths between $x$ and $y$ of minimal length contain the edges $e_1, \dots, 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. A *small-range path* is a path made exclusively of small-range edges. Given $x, y \in \mathcal{V}$, the *small-range distance* $d_{\text{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_{\text{SR}}(x, r)$.

2. A *long-range path* is a sequence $e = (e_i)_{i=1}^k$ of long-range edges such that for all $i \le k-1$ $d_{\text{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 $|e|$ of e is the number of edges it contain. It joins two vertices $x, y \in \mathcal{V}$ if $d_{\text{SR}}(x, e_1) < \infty$ and $d_{\text{SR}}(e_k, y) < \infty$. Given $x, y \in \mathcal{V}$, the *long-range distance* $d_{\text{LR}}(x, y)$ is the minimal length of a long-range path between $x$ and $y$. We write $B_{\text{LR}}(x, r)$ for the corresponding *long-range balls*.
As for the distance in Markov chain underlying graphs, these distances are not sym-
metric, so we may add + or – sign in exponent to denote forward and backward balls.
From the definition, for any $x \in \mathcal{V}$, $B_{\text{SR}}^{+}(x, \infty) = B_{\text{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:

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

that is, the small-range component of $x$ is the whole set of vertices in $V$ than can be
reached from $\iota(x^{\circ})$ in the graph $G$.

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

Property (iii) above clearly gives quasi-trees a tree structure. For this reason, let us
introduce a few extra notations. Given $k \ge 0$, the $k$-th level $\mathcal{V}_k$ is the set of vertices which
are at long-range distance $k$ from the root. Set also $\mathcal{V}_{\le k} := \bigcup_{i \le k} \mathcal{V}_i$. The requirement
that $\eta$ has no fixed point implies that every vertex $x$ is joined to vertex $\eta(x)$ in another
level. If $x$ is a center, $\eta(x)$ is in a level below, whereas if $x$ is not a center $\eta(x)$ is in a
level above.

**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} \setminus \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 5.3.** Let $\mathcal{G}$ be a quasi-tree. A long-range path $e = (e_1, \dots, e_k)$ backtracks over a distance $l \ge 1$ if it contains a subpath of distinct edges and of length $l$ immediately followed by the reversed path, that is there exists $i \le k-2l+1$ such that $e_{i+l+j} = \bar{e}_{i+l-1-j}$ for all $j \in [0, l-1]$, where $\bar{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 \ge 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} \mid d_{\text{SR}}(x^{\circ}, x) < R\}. \qquad (5.9) $$

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 \ge 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** Let $\mathcal{G}$ be a quasi-tree. It is naturally the underlying graph of the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ on $\mathcal{G}$ which has transition probabilities:

$$ \mathbf{P}[\mathcal{X}_{t+1/2} = y \mid \mathcal{X}_t = x] = \begin{cases} p(\iota(x), \iota(\eta(x))) & \text{if } y = x \\ q(\iota(x), \iota(\eta(x))) & \text{if } y = \eta(x) \\ 0 & \text{otherwise} \end{cases} \qquad (5.10) \\ \mathbf{P}[\mathcal{X}_{t+1} = y \mid \mathcal{X}_{t+1/2} = x] = \begin{cases} P(\iota(x), \iota(y)) & \text{if } y^{\circ} = x^{\circ} \\ 0 & \text{otherwise} \end{cases} $$

for all $t \in \mathbb{N}$. 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 in the reversible model.

### 5.2.5 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 \to V$ to define the matching on the quasi-tree. Given $x \in V$, this is the quasi-tree $(\mathcal{G}^*(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 5.2, 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_{LR}(O, 1)$. The process iterates to infinity to yield an infinite quasi-tree $\mathcal{G}^*$.

This quasi-tree has the property that it covers exactly $G^*$: the map $\iota$ is a surjective morphism of $\mathcal{G}^*$ onto $G^*$ which preserves the transition probabilities, so the Markov chain $\mathcal{X}$ defined above projects exactly onto the chain $X$: for all $t \ge 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}^*$ 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. Namely we extend notions of small-range, long-range paths, backtracking, etc. defined above to $G^*$ 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 \ge 1$ and recall the definition of the restricted quasi-tree $\mathcal{G}^{(R)}$ (5.9). Given $x \in V$ and $l \ge 0$, we define $B_{LR}^{(G,R)}(x, r)$ in $G^*$ as the projection

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

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

Finally, we introduce a last definition which is specific to $G^*$: 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^*$ 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 5.1 below will establish that 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) imply that the graph $G$ and consequently $G^*, \mathcal{G}$ as well, have degrees bounded uniformly in $n$. Together with Assumption (H2) it also implies all transition probabilities are lower bounded 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^*$ and any quasi-tree $\mathcal{G}$: for all $x \in V$ and $l \ge 0$

$$|B_{SR}(x, l)| \le |B_{\mathcal{P}}(x, l)| \le \frac{\Delta^{l+1} - 1}{\Delta - 1}, \quad |B_{LR}^{(G,R)}(x, l)| \le \Delta^R \frac{\Delta^{R(l+1)} - 1}{\Delta^R - 1}. \quad (5.11)$$

In particular, $\Delta^R$ can be thought of as the "long-range" degree.
### 5.2.6 Random setting

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 \setminus V(\iota(x))$.

The following formalisation of random quasi-trees will be useful to deal with subquasi-trees and their independency properties. It is analog to the Ulam-Harris labelling for Galton-Watson trees. Let

$$ \mathcal{U} := \bigcup_{k \ge 0} \{ ( (u_i)_i^{k-1}, v) \mid (u,v) \in V^{k+1}, \forall i \in [2,k], u_i \notin V(u_{i-1}), v \notin V(u_k) \}. \quad (5.12) $$

The elements in $\mathcal{U}$ corresponding to $k=0$ have their first coordinate empty and are identified with $V$. Given two sequences $u, v$, write $uv$ for their concatenation. If $u = (u_i)_{i=1}^k$ is non-empty, write $u^b := (u_i)_{i=1}^{k-1}$ and $\bar{u} := u_k$. A rooted quasi-tree can then be represented as a pair $(V, O)$ where $V \subset \mathcal{U}$, $O \in V$ satisfy:

$$ (i) \ V \cap V = B_{SR}^{+}(O, \infty) $$

$$ (ii) \ \forall (u, v) \in V, \ (u^b, \bar{u}) \in V. $$

(iii) there exists an involution $\eta: V \to V$ such that for all $(u, v) \in V$,

* either $\eta(u, v) = (u^b, \bar{u})$, $((u, v)$ is then a center),

* or $\eta(u, v) = (uv, \rho(u, v))$ for some $\rho(u, v) \in V \setminus V(v)$.

In the second case, for all $w \in V$, $(uv, w) \in V$ if and only if $w \in B_{SR}^{+}(\rho(u, v), \infty)$.

It is easily checked that with this definition the set $V$ identifies with the vertex set of a quasi-tree as defined in 5.2. Note the type of a vertex $(u, v) \in \mathcal{U}$ is $\iota(u, v) = v$.

Consider now a family $(\zeta_{(u,v)})_{(u,v) \in \mathcal{U}}$ of independent random variables, where for every $(u, v) \in \mathcal{U}$, $\zeta_{(u,v)}$ is uniform in $V \setminus V(v)$. Letting $U$ be independent and uniform in $V$, let $V$ be the random subset of $\mathcal{U}$ obtained by taking $O = U$ and $\rho(u, v) := \zeta(u, v)$ in the case $(u, v)$ is not a center. This yields the same random quasi-tree as in the iterative definition above.

The previous construction is a bit heavy and can be avoided most of the time, however it has the advantage that it allows to consider subquasi-trees in a rigourous
way: for every $x = (u, v) \in \mathcal{U}$, $x$ being a center or not is measurable with respect to $\mathcal{G} \setminus \mathcal{G}_x$. Then recall that if $x \in \mathcal{V}$ is not a center $\mathcal{G}_x$ does not contain $x$, so conditional on $\mathcal{G} \setminus \mathcal{G}_x$ and $x \in \mathcal{V}$ not being a center, $\mathcal{G}_x$ has the law of $\mathcal{G}'_{O'}$ where $(\mathcal{G}', O')$ is an independent copy of $(\mathcal{G}, O)$. If $x$ is a center then the root of $\mathcal{G}_x$ is already determined by $\iota(x) = v$, thus conditional and $\mathcal{G} \setminus \mathcal{G}_x$ and $x \in \mathcal{V}$ being a center, $\mathcal{G}_x$ has the law of $\mathcal{G}'_{O'}$ conditional on $\iota(\eta(O')) = v$.

### 5.2.7 Coupling and sequential generation

We now explain how one can couple the Markov chain $(X_t)_{t \ge 0}$ on $G^*$ with the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ on the random infinite quasi-tree $\mathcal{G}$ defined in the previous section.

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

Let $x \in \mathcal{V}$ be the point whose long-range neighbourhood is to be explored up to long-range distance $L \ge 0$. For $t \ge 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^*$ and quasi-trees: $D_0 := \emptyset$; $EQ_0 := B_{\text{SR}}^+(x, R)$ in $\mathcal{G}$, $EQ_0 := B_{\text{SR}}^+(x, \infty)$ in $\mathcal{G}$. The procedure repeats then the following steps. If one wants to explore a neighbourhood in $G^*$ sampling is performed without replacement:

**Sequential generation of $G^*$, sampling without replacement:** for $t \ge 0$,

1. pick $y \in EQ_t$: sample $\eta(y)$ uniformly at random in $(V \setminus V(y)) \setminus D_t$,

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

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

If performed with replacement, each new value $\eta(y)$ is picked uniformly in $V \setminus 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 \ge 0$,

1'. pick $y \in EQ_t$: sample $\eta(y)$ uniformly at random in $V \setminus V(y)$,

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

3'. add all vertices $z \in B_{\text{SR}}^+(\eta(y), R) \setminus \{\eta(y)\}$ such that $d_{\text{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 5.2. Taking $L = \infty$ would thus yield a realization of the infinite random quasi-tree $\mathcal{G}$. Finally, the procedures can be adapted to explore balls $B_{\mathcal{P}}$ in $G^*$ or $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 \ge 0$:

a. Explore the long-range $L$-neighbourhood of $X_t$ with the first procedure described above.

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

If one considers the second procedure one obtains instead $(\mathcal{X}_t)_{t \ge 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 \setminus V(y)$ and use it for step 1' in the generation of $\mathcal{G}$. If in addition $B_{SR}(\eta(y), R) \cap D_t = \emptyset$, it can also be used for step 1 in the generation of $G^*$. Otherwise, make a second draw with the first procedure. This rejection sampling scheme yields a coupling of $(X_t)_{t \ge 0}$ and $(\mathcal{X}_t)_{t \ge 0}$ until the first time a newly revealed small-range ball $B_{SR}(\eta(y), R)$ contain vertices that have already been explored, that is when a long-range cycle appears around the trajectory:

$$ \tau_{\text{coup}} := \inf \left\{ t \ge 0 \mid \bigcup_{k=0}^{t} B_{\text{LR}}(X_k, L) \text{ contains a long-range cycle} \right\}. \quad (5.13) $$

As a first application of the coupling and the first moment argument, we give the following Lemma.

**Lemma 5.1.** There exists $C_R, C_L$ large enough such that for $R = C_R \log \log n, L = C_L \log \log n$, for all $x \in V, \varepsilon \in (0, 3/10)$ and $t = O(n^{3/10-\varepsilon})$,

$$ (i) \mathbf{P}_x [\exists s \le t : B_{\mathcal{P}}(X_s, [\log n/(5 \log \Delta)]) \text{ is not quasi-tree-like}] = o_{\mathbb{P}}(n^{-\varepsilon}) = o_{\mathbb{P}}(1). $$

$$ (ii) \mathbf{P}_x [\exists s \le t : B_{\text{LR}}^{(G,R)}(X_s, L) \text{ is not quasi-tree-like}] = o_{\mathbb{P}}(n^{-\varepsilon}) = o_{\mathbb{P}}(1). \quad \text{Thus} $$

$$ \mathbf{P}_x [\tau_{\text{coup}} \le t] = o_{\mathbb{P}}(n^{-\varepsilon}) = o_{\mathbb{P}}(1). $$
Proof. Let the chain be started at $x \in V$ and $t = o(n^{3/10-\epsilon})$ for $\epsilon \in (0, 3/10)$. Write $k := [\log n/(5 \log \Delta)]$. By (5.11), the number of vertices contained in a $\mathcal{P}$-ball of radius $k$ is $O(\Delta^k)$. This implies $\bigcup_{s \le t} B_{\mathcal{P}}(X_s, k)$ contains $m = O((t+1)\Delta^k)$ vertices. Therefore, the exploration procedure along the path $X_0 \cdots X_t$ requires at most $m$ draws of values $\eta(y)$, each having probability at most $m\Delta^R/n$ that the small-range ball $B_{SR}(\eta(y), R)$ contains already explored vertices. Hence the number of long-range cycles in $\bigcup_{s \le t} B_{\mathcal{P}}(X_s, k)$ is stochastically upper bounded by a binomial $\text{Bin}(m, m\Delta^R/n)$ so that by Markov's inequality

$$ \mathbb{P}_x[\exists s \le t : B(X_s, k) \text{ is not quasi-tree-like}] \le \frac{m^2 \Delta^R}{n} = O\left(\frac{(t+1)^2 \Delta^R \Delta^{2k}}{n}\right) \\ = O\left(t^2 n^{-3/5+o(1)}\right) = o(n^{-2\epsilon+o(1)}) = o(n^{-\epsilon}) $$

by the choice of $t = O(n^{3/10-\epsilon})$ and $R = O(\log \log n)$. This bound on the annealed probability implies the quenched result (i) by the first moment argument (5.4). The result (ii) is proved similarly, noting that $\Delta^{RL}$ is still $n^{o(1)}$ if $R, L = O(\log \log n)$ (in this case we can take $t$ up to $n^{1/2-\epsilon}$). $\square$

## 5.3 The entropic method: main arguments

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

(i) it is contained in a quasi-tree-like portion of the graph, the endpoint having a quasi-tree-like neighbourhood up to $\mathcal{P}$-distance $[\alpha \log n]$ for some $\alpha > 0$ (Lemmas 5.1 and 5.2),

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

(iii) the drift, ie the long-range distance travelled, and entropy concentrate on this trajectory (Proposition 5.1).
As mentioned in the proof outline, nice trajectories will be likely to be followed by the chain only if it is started at a typical state. To derive the upper bound on the worst-case mixing time, we will thus establish that for an arbitrary starting state the trajectory becomes nice only after some time, namely after $s = (\log n)^a$ steps for some $a > 0$ or $s = O(\log \log n)$ steps in the reversible case. This is why in the sequel we state different results with a "typical, non-shifted" version valid from time 0 and a "worst-case, shifted" version valid for arbitrary starting states from time $s$. For the first important property of nice trajectories, the typical version has in fact already been proved in Lemma 5.1. The worst-case version is given in the following.

**Lemma 5.2.** (i) There exists $a \ge 1$ such that for all $s \ge (\log n)^a$ and $t = o(n^{1/16})$, for all $C_R, C_L > 0$, letting $R := C_R \log \log n, L := C_L \log \log n$,

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

In the reversible model, the conclusion holds for $s \ge C \log \log n$ and a large enough constant $C > 0$.

(ii) There exists $a \ge 1, \alpha > 0$ such that for all $s \ge (\log n)^a$,

$$ \max_{x \in V} \mathbf{P}_x [B_{\mathcal{P}}(X_s, [\alpha \log n]) \text{ is not quasi-tree-like}] = o_{\mathbb{P}}(1). \quad (5.14) $$

In the reversible model: for all $C > 0$, there exists $\alpha > 0$ such that for any $t \ge C \log n$,

$$ \max_{x \in V} \mathbf{P}_x [B_{\mathcal{P}}(X_t, [\alpha \log n]) \text{ is not quasi-tree-like}] = o_{\mathbb{P}}(1) $$

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

**Lemma 5.3.** Let $\Gamma(R, L, M)$ denote the set of paths $p$ in $G^*$ such that $p$ does not deviate from a small-range distance more than $R$, backtrack over a long-range distance $L$ or contain a subpath of length $M$ without a regeneration edge. There exist constants $\kappa \ge 1$, $a \ge 1$, $C_R, C_L > 0$ such that for $L = C_L \log \log n$, $R = C_R \log \log n$ and $M = (\log \log n)^\kappa$, for all $t = O(\log n)$, the following holds:

(i) for all $x \in V$:

$$ \mathbf{P}_x [(X_0 \cdots X_t) \in \Gamma(R, L, M)] = 1 - o_{\mathbb{P}}(1). $$

Furthermore, for any $b > 0$, this probability is even $1 - o_{\mathbb{P}}((\log n)^{-b})$ provided the constants $C_R, C_L$ are allowed to depend on $b$.
(ii) for all $s \ge (\log n)^a$:

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

In the reversible model, the conclusion holds for $s \ge C \log \log n$ and a large enough constant $C > 0$.

*Remark 5.4.* Notice that for any trajectorial event A

$$ \mathbf{P}_x [(X_s, X_{s+1}, \dots) \in A] = \sum_{y \in V} \mathbf{P}_x [X_s = y] \mathbf{P}_y [(X_0, X_1, \dots) \in A] \\ \le \max_{y \in V} \mathbf{P}_y [(X_0, X_1, \dots) \in A]. $$

Thus if we prove A holds from time $t$ with probability $1 - o_{\mathbb{P}}(1)$ uniformly over the starting state this automatically extends to larger times $t \ge s$. Thus in the above lemmas it will be sufficient to prove the case $s = (\log n)^a$ to establish the case $s \ge (\log n)^a$ for instance.

### 5.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 \ge 1$, $\tau_l$ will generally denote the time a certain distance $l$ is reached. For all $l \ge 0$, consider in this section

$$ \tau_l := \inf\{t \ge 0 \mid |\xi(X_0 \cdots X_t)| = l\} $$

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

$$ \begin{aligned} \tau_{\text{SR}}^{(R)} &:= \inf\{t \ge 0 \mid (X_0 \cdots X_t) \text{ deviates from a small-range distance } R\} \\ \tau_{\text{NB}}^{(L)} &:= \inf\{t \ge 0 \mid (X_0 \cdots X_t) \text{ backtracks over a long-range distance } L\}. \end{aligned} \quad (5.15) $$

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 5.3, the stopping time $\tau_{\text{SR}}^{(R)} \wedge \tau_{\text{NB}}^{(L)}$ does not occur on the trajectory $\mathfrak{p}$. Given a long-range edge $e$ and $x \in V$ such that $d_{\text{SR}}(x, e^-) < R$, define the weights

$$ \begin{aligned} w_{x,R,L}(e) &:= \mathbf{P}_x \left[ \xi(X_0 \cdots X_{\tau_L})_1 = e, \tau_L < \tau_{\text{SR}}^{(R)} \right] \\ w_{R,L}(e \mid x) &:= \mathbf{P}_x \left[ \xi(X_0 \cdots X_{\tau_L})_1 = e \mid \tau_L < \tau_{\eta(x)} \wedge \tau_{\text{SR}}^{(R)} \right] \end{aligned} \quad (5.16) $$
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}^{+}) \qquad (5.17) $$

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

*Remark 5.5.* Note that for fixed $x \in V$, $\sum_e w_{x,R,L}(e) \le 1$ and $\sum_e w_{R,L}(e | x) \le 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 \le l}$ of length $l$ and $k \ge 1$, we write $(u)_{\le k} := (u_i)_{i \le k}$ for the sequence truncated at length $k$. The following lemma shows that weights are good proxies for measuring the probability that the loop-erased trace follows a given non-backtracking path.

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

$$ \mathbf{P}_x \left[ \begin{array}{l} \xi(X_0 \cdots X_{\tau_{k+L-1}})_{\le k} = \xi, \\ \tau_{k+L-1} < \tau_{SR}^{(R)} \wedge \tau_{NB}^{(L)} \end{array} \right] \le w_{x,R,L}(\xi) \le \mathbf{P}_x \left[ \begin{array}{l} \xi(X_0 \cdots X_{\tau_{k+L-1}})_{\le k} = \xi, \\ \tau_{k+L-1} < \tau_{SR}^{(R)} \wedge \tau_{NB}^{(L)} \end{array} \right] + u(\xi) \quad (5.18) $$

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

$$ \sum_{\xi} u(\xi) \le \mathbf{P}_x [\tau_{SR}^{(R)} \wedge \tau_{NB}^{(L)} \le \tau_{k+L-1}], $$

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

*Proof.* The proof is by induction on $k \ge 1$. For $k = 1$ the inequalities are in fact equalities by definition, since $\tau_{NB}^{(L)} > \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 \ge 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 $|\xi(X_0 \cdots X_t)| = 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}})_{\le k} = (\xi)_{\le 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,

$$ \begin{aligned} w_x((\xi)_{\le k}) &\ge \mathbf{P}_x [\xi(X_0 \cdots X_{\tau_{k+L-1}})_{\le k} = \xi, \tau_{k+L-1} < \tau_{SR} \wedge \tau_{NB}] \\ &= \mathbf{P}_x [X_{L_k} = e^+, L_k < \tau_{SR} \wedge \tau_{NB}] \mathbf{P}_{e^+} [\tau_{L-1} < \tau_{e^-} \wedge \tau_{SR}]. \end{aligned} $$
On the other hand,

$$w(f | e^+) = \frac{\mathbf{P}_{e^+} [\xi(X_0 \cdots X_{\tau_L})_1 = f, \tau_L < \tau_{e^-} \wedge \tau_{SR}]}{\mathbf{P}_{e^+} [\tau_L < \tau_{e^-} \wedge \tau_{SR}]}.$$

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

$$w_x(\xi) = w_x((\xi)_{\le k}) w(f | e^+) \\ \ge \mathbf{P}_x [X_{L_k} = e^+, \tau_{SR} \wedge \tau_{NB} > L_k] \mathbf{P}_{e^+} [\xi(X_0 \cdots X_{\tau_L})_1 = f, \tau_L < \tau_{SR} \wedge \tau_{e^-}].$$

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_{SR} \wedge \tau_{NB}$, which proves the lower bound.

For the upper bound, the induction hypothesis yields this time

$$w_x((\xi)_{\le k}) \le \mathbf{P}_x [X_{L_k} = e^+, L_k < \tau_{SR} \wedge \tau_{NB}] \mathbf{P}_{e^+} [\tau_{L-1} < \tau_{e^-} \wedge \tau_{SR}] + u((\xi)_{\le k}).$$

Then use that

$$\mathbf{P}_{e^+} [\tau_{L-1} < \tau_{e^-} \wedge \tau_{SR}] \le \mathbf{P}_{e^+} [\tau_L < \tau_{e^-} \wedge \tau_{SR}] + \mathbf{P}_{e^+} [\tau_{L-1} < \tau_{e^-} \wedge \tau_{SR} \le \tau_L]$$

to bound

$$w_x(\xi) \le \mathbf{P}_x [X_{L_k} = e^+] \mathbf{P}_{e^+} [\xi(X_0 \cdots X_{\tau_L})_1 = f, \tau_L < \tau_{SR} \wedge \tau_{e^-}] \\ + \mathbf{P}_x [X_{L_k} = e^+] \mathbf{P}_{e^+} [\tau_{L-1} < \tau_{e^-} \wedge \tau_{SR} \le \tau_L] w(f | e^+) + u((\xi)_{\le 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) \le \sum_{e} \mathbf{P}_x [X_{L_k} = e^+] \mathbf{P}_{e^+} [\tau_{L-1} < \tau_{e^-} \wedge \tau_{SR} \le \tau_L] + \mathbf{P}_x [\tau_{SR} \wedge \tau_{NB} \le \tau_{k+L-1}].$$

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_{SR} \wedge \tau_{NB} \le \tau_{k+L}$, hence the upper bound. $\square$

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

**Proposition 5.1.** There exist $d, h = \Theta(1)$ and constants $a \ge 1, C_R, C_L > 0$ for which the following holds. Letting $R := C_R \log \log n, L := C_L \log \log n$, for all $\varepsilon \in (0, 1)$, there exist $C_{LR}(a, \varepsilon), C_h(a, \varepsilon)$ such that for all $t \gg 1$, $t = O(\log n)$:
(i) for all $x \in V$, with high probability

$$ \mathbf{P}_x \left[ \begin{array}{l} \|\xi(X_0 \cdots X_t)\| - dt \le C_{LR} \sqrt{t} \\ |-\log w_{X_0, R, L}(\xi(X_0 \cdots X_t)) - ht| \le C_h \sqrt{t} \end{array} \right] \ge 1 - \varepsilon. $$

(ii) for all $s \ge (\log n)^a$, with high probability,

$$ \min_{x \in V} \mathbf{P}_x \left[ \begin{array}{l} \|\xi(X_s \cdots X_{s+t})\| - dt \le C_{LR} \sqrt{t} \\ |-\log w_{X_s, R, L}(\xi(X_s \cdots X_{s+t})) - ht| \le C_h \sqrt{t} \end{array} \right] \ge 1 - \varepsilon. $$

In the reversible model, the conclusion holds for $s \ge C \log \log n$ and a large enough constant $C > 0$.

### 5.3.3 Concentration of nice paths

The second part of the argument consists in finding a set of "nice trajectories", defined in particular so that they satisfy the entropic and drift requirements given by Proposition 5.1. Eventually the drift and entropic concentration are used 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 $\mathcal{P}$ on $V$.

Given $u \in V$, $L \ge 1$ consider again $\tau_L := \inf\{t \ge 0 \mid |\xi(X_0 \cdots X_t)| = L\}$ and

$$ \mathbf{Q}_u^{(L)} := \mathbf{P} \left[ \cdot \mid X_{1/2} = u, \tau_{\eta(u)} > \tau_L \right] \quad (5.19) $$

In words, this measure considers trajectories immediately after a regeneration time. By Lemma 5.3, if one takes $L = \Theta(\log \log n)$, the conditioning 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}_{\nu}^{(L)} := \sum_{u \in V} \nu(u) \mathbf{Q}_{u}^{(L)}$ and $\mathbf{E}_{\mathbf{Q}_{\nu}}^{(L)}$ for the expectation with respect to this measure. All in all, the second part of the argument is summarized in the following proposition.

**Proposition 5.2.** There exist a deterministic probability measure $\nu$ on $V$, a deterministic $s_0 = \Theta(\log n)$, constants $C_L, C_0 > 0, a, \kappa \ge 1$ 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 := (\log \log n)^\kappa$ and write $\mathcal{P}_{\mathfrak{N}^t}(x, y) := \sum_{p \in \mathfrak{N}^t(x, y)} \mathcal{P}(p)$. Consider the random probability measure

$$ \hat{\pi}(v) := \frac{1}{\mathbf{E}_{\mathbf{Q}_{\nu}^{(L)}}[T_1 \wedge M]} \sum_{r=0}^{M} \mathbf{Q}_{\nu}^{(L)}[X_{r+s_0} = v, r < T_1 \le M] \quad (5.20) $$

where $T_1$ denotes the first regeneration time with horizon $L = C_L \log \log n$. For all $\varepsilon \in (0, 1)$ there exists $C(\varepsilon) > 0$ such that for $t = \log n/h + C(\varepsilon)\sqrt{\log n}$,
(i) for all $x \in V$, with high probability,

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

(ii) for all $s \geq (\log n)^a$ or $s \geq C \log \log n$ in the reversible model, with high probability

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

(iii) there exists $c = (c_v)_{v \in V}$ such that $\sum_{v \in V} c_v = o_P(1)$ and with high probability, for all $x, y \in V$,

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

(iv) the measure $\hat{\pi}$ can be decomposed as $\hat{\pi} = \hat{\pi}_1 + \hat{\pi}_2$ with

$$ \|\hat{\pi}_1\|_2^2 = o_P((\log n)^b/n), \quad \hat{\pi}_2(V) = o_P(1) $$

for some $b > 0$.

*Proof of Theorems 5.1, 5.3 and 5.4.* Recall $\mathcal{P}$ is the transition matrix of the two-lift chain on $V$, which projects to a transition matrix $\bar{\mathcal{P}}$ on $[n]$.

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

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

Point (iii) 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,

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

Using point (ii), if $s \geq (\log n)^a$ or $s \geq C \log \log n$ in the reversible model, with high probability

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

which projects by (5.7) to

$$ \max_{x \in V} \| \bar{\mathcal{P}}^{s+t}(x, \cdot) - \hat{\pi} \|_{\text{TV}} \leq 4\varepsilon. $$
with $\tilde{\pi}$ the projection onto $[n]$ of $\hat{\pi}$. Since this estimate is uniform in the starting state, it extends to any starting distribution and particularly to a stationary distribution. Thus for any stationary distribution $\pi$ of $\tilde{\mathcal{P}}$,

$$ \|\pi - \tilde{\pi}\|_{\text{TV}} \le 4\varepsilon. \qquad (5.21) $$

and from triangular inequality we obtain that with high probability

$$ \max_{x \in [n]} \| \tilde{\mathcal{P}}^{s+t}(x, \cdot) - \pi \|_{\text{TV}} \le 8\varepsilon. $$

Since this is valid for any invariant measure, the latter must be unique. This proves in particular the irreducibility and aperiodicity of the chain and establishes Theorem 5.3 as well as the upper bound of Theorem 5.4, since $O(\log \log n) = o(\sqrt{\log n})$.

On the other hand for a fixed $x \in V$, taking $s = 0$ in the above bounds yields and using point (i) that with high probability,

$$ \| \tilde{\mathcal{P}}^t(x, \cdot) - \pi \|_{\text{TV}} \le 8\varepsilon, $$

proving the upper bound in Theorem 5.1.

Let us prove the lower bound. For all $t \ge 0, \theta > 0$ and $x, y \in [n]$,

$$ \begin{aligned} \tilde{\mathcal{P}}^t(x, y) &= \mathcal{P}^t(x, y) + \mathcal{P}^t(x, \eta(y)) \\ &\ge \mathbf{P}_x[X_t \in \{y, \eta(y)\}, w_{x,R,L}(\xi(X_0 \cdots X_t)) \le \theta]. \end{aligned} $$

If equality holds, then

$$ \tilde{\pi}(y) - \mathbf{P}_x[X_t \in \{y, \eta(y)\}, w_{x,R,L}(\xi(X_0 \cdots X_t)) \le \theta] \le [\tilde{\pi}(y) - \tilde{\mathcal{P}}^t(x, y)]_+ $$

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

$$ \begin{aligned} \tilde{\pi}(y) - \mathbf{P}_x[X_t \in \{y, \eta(y)\}, w_{x,R,L}(\xi(X_0 \cdots X_t)) \le \theta] \le \tilde{\pi}(y) \mathbb{1}_{\exists \xi: w_{x,R,L}(\xi) > \theta} \\ + \tilde{\pi}(\eta(y)) \mathbb{1}_{\exists \xi: w_{x,R,L}(\xi) > \theta}. \end{aligned} $$

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

$$ \begin{aligned} \tilde{\pi}(y) - \mathbf{P}_x[X_t \in \{y, \eta(y)\}, w_{x,R,L}(\xi(X_0 \cdots X_t)) \le \theta] \le [\tilde{\pi}(y) - \tilde{\mathcal{P}}^t(x, y)]_+ + \tilde{\pi}(y) \mathbb{1}_{\exists \xi: w_{x,R,L}(\xi) > \theta} \\ + \tilde{\pi}(\eta(y)) \mathbb{1}_{\exists \xi: w_{x,R,L}(\xi) > \theta}. \end{aligned} $$
Decompose now $\hat{\pi} = \hat{\pi}_1 + \hat{\pi}_2$ as in Proposition 5.2. From (iv), summing over $y \in [n]$ in the previous inequality yields

$$ \mathbf{P}_x[w_{x,R,L}(\xi(X_0 \cdots X_t)) > \theta] \le \|\bar{\mathcal{P}}^t(x, \cdot) - \bar{\hat{\pi}}\|_{\text{TV}} + \sum_{y \in V} \hat{\pi}_1(y) \mathbb{1}_{\exists \xi: w_{x,R,L}(\xi) > \theta} + o_{\mathbb{P}}(1). $$

By Cauchy-Schwarz inequality,

$$ \sum_{y \in V} \hat{\pi}_1(y) \mathbb{1}(\exists \xi: w_{x,R,L}(\xi) > \theta) \le \left( \sum_{y \in V} \hat{\pi}_1(y)^2 \right)^{1/2} \left( \sum_{\xi} \mathbb{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 5.5 weights sum up to at most 1 hence so this sum contains at most $\theta^{-1}$ positive terms and

$$ \mathbf{P}_x[X_t = y, w_{x,R,L}(\xi(X_0 \cdots X_t)) > \theta] \le \|\bar{\mathcal{P}}^t(x, \cdot) - \bar{\hat{\pi}}\|_{\text{TV}} + \sqrt{\frac{1}{\theta} \sum_{y \in V} \hat{\pi}_1(y)^2 + o_{\mathbb{P}}(1)}. \quad (5.22) $$

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 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/h)\sqrt{\log n} - o(\sqrt{\log n})) > \theta$ for large enough $n$, hence Proposition 5.1 implies that the left hand-side of (5.22) is at least $1 - \varepsilon$ with high probability. On the other hand, (iv) shows that the square-root in the right hand side is $o_{\mathbb{P}}(1)$. All in all, this proves that with high probability

$$ \|\bar{\mathcal{P}}^t(x, \cdot) - \bar{\hat{\pi}}\|_{\text{TV}} \ge 1 - 2\varepsilon. $$

Finally by (5.21) we deduce

$$ \|\bar{\mathcal{P}}^t(x, \cdot) - \bar{\pi}\|_{\text{TV}} \ge 1 - 6\varepsilon $$

with high probability. $\square$

*Remark 5.6.* From the previous proof, the decomposition of $\hat{\pi}$ given by (iv) also extends to the unique invariant measures of $\mathcal{P}$ and $\bar{\mathcal{P}}$: $\pi = \pi_1 + \pi_2$ with $\|\pi_1\|_2^2 = o_{\mathbb{P}}((\log n)^b/n)$ and $\pi_2([n]) = o_{\mathbb{P}}(1)$.

*Remark 5.7.* Let us also comment on how the proof accomodates the superposition of simple graphs in the reversible model. 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 5.2 will require having a quasi-tree-like neighbourhood, they avoid in particular these edges, so it makes no difference in the end to adjust the transition probabilities of these edges or not.
<figure><img src="image_14.png" /><figcaption>Figure 5.1: The finite chains $P_1, P_2$ and the quasi-tree $T$ with all centers of type 0, after identifying each $x \approx \eta(x)$. The probability to remain at a vertex is not represented.</figcaption></figure>

## 5.4 Counter-example to uniform entropic time

In this section we prove Theorem 5.2. Let $n \ge 1$ and $\delta \in (0, 1)$. Consider the reversible Markov chains $Q_1, Q_2$ on the segments $\{0, 1, 2\}$ and $\{0, 1\}$ which go from left to right with probability $\delta$, from right to left with probability $1 - \delta$ and stay at the extremities with remaining probability. Let $P_1$ be the transition matrix on $[6n]$ corresponding to $2n$ disjoint copies of $Q_1$, that is $P_1(i, j) = Q_1(i \text{ mod } 3, j \text{ mod } 3)$ for all $i, j \in [6n]$. Similarly let $P_2$ be the matrix corresponding to $3n$ copies of $Q_2$. Our counter-example to uniform mixing time is obtained with the matrix $\mathcal{P} := 1/2(P_1 + SP_2S^{-1})$ and small $\delta$. On this example, it will be exceptionally clearer to forget about the two-lift and half-integer time transitions. We thus identify each $x$ with $\eta(x)$, both in the finite and quasi-tree setting, which has the effect of pruning the long-range edges in the graphs, and we use the notations $G^*, \mathcal{G}, \mathcal{X}$ to refer to the objects obtained after this operation.

Consider first the quasi-tree $\mathcal{G}$ that would be obtained from $P_1$ and $P_2$: because the underlying graphs $G_1, G_2$ are forests, all realizations of quasi-trees are in fact genuine trees. On the other hand, if $\delta$ is small, the Markov chains on segments are heavily biased towards 0. Say a vertex $x \in \mathcal{G}$ has type 0 if the map $\iota$ identifies $x$ with the leftmost vertex of a segment. Then consider the quasi-tree obtained $T$ if all centers in $\mathcal{G}$ have type 0. As one can check, this is a periodic weighted tree $T$ where except the root all vertices have their transition probabilities depending only on whether the degree is 2 or 3, see Figure 5.1. Notice that for sufficiently small $\delta$, this chain becomes recurrent. Of course this configuration occurs with probability 0, however a finite portion of $T$ can arise with positive probability. Coming back to the finite graph $G^*$, which resembles locally a quasi-tree, this probability is in fact sufficiently large that $G^*$ also contains such neighbourhoods, which trap the chain for a long time.
**Lemma 5.5.** There exists $\beta > 0$ such that for all $\delta \in (0, 1)$, with high probability there exists $x \in [6n]$ for which

$$ \mathbf{P}_x[X_t \notin B_{\bar{\mathcal{P}}}(x, \beta \log \log n)] = o(1) $$

for all $t \le (\log n)^{\beta \log(2\delta/(1-\delta))}$.

*Proof.* Let $l := \beta \log \log n$. In the present setting, the degrees of $G^*$ and $G$ are clearly bounded by $\Delta = 3$. Consequently the exploration of a $\mathcal{P}$-ball of radius $l$ around any $x \in V$ reveals at most $O(\Delta^l) = O((\log n)^{\beta \log 3})$ vertices. Suppose we reveal such neighbourhoods around vertices $x_0, \dots, x_k$, each time picking a vertex disjoint from the previously explored neighbourhoods. As explained in Section 5.2.7, this exploration can be performed with replacement at a total variation cost which is $o(1)$ as long as $k\Delta^l = o(\sqrt{n})$. If this holds we can thus make the neighbourhoods of all $x_k$ coincide with trees with probability $1-o(1)$. Now in the quasi-tree $G$, each center has type 0 with probability at least $1/3$, so the probability that all centers up to depth $l$ have type 0 is at least $3^{-\Delta^{l+1}}$. Consequently, the probability that no vertex among $x_0, \dots, x_k$ has its neighbourhood isomorphic to $T_{\le l}$, the subtree of $T$ up to depth $l$, is upper bounded by

$$ (1 - 3^{-\Delta^{l+1}})^k \le \exp(-k3^{-\Delta^{l+1}}) = \exp(-k9^{-(\log n)^{\beta \log 3}}) $$

For $\beta > 0$ small enough, we can take for instance $k = n^{1/4}$ so that the previous probability is $o(1)$ and in the same time $k\Delta^l = o(\sqrt{n})$ so the approximation with the quasi-tree is justified. This proves that with high probability, there exists $x_0 \in [6n]$ such that $B_{\bar{\mathcal{P}}}(x_0, l)$ coincides with $T_{\le l}$.

It remains to show that the Markov chain $(X_t)_{t \ge 0}$ is very unlikely to escape $B_{\bar{\mathcal{P}}}(x, l)$ by time $e^{cl}$. It suffices to prove the statement for the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ on $T$. This is done by considering the maximal drift of the chain: the vertices which maximize the probability to go away from the root are vertices of degree 3. If $\mathcal{X}_t$ is at such a vertex, it goes away from the root with probability $\delta$, moves towards the root with probability with probability $(1-\delta)/2$ and stays put with remaining probability. Consequently, the distance between $\mathcal{X}_t$ and the root is stochastically upper bounded by a lazy random walk on the segment $[0, l]$ which goes left with probability $(1-\delta)/2$ and right with probability $\delta$. By the classical Gambler's ruin problem, this random walk has probability at most $O((2\delta/(1-\delta))^l)$ to go from 1 to $l$ before returning to 0. In turn this implies that the hitting time $\tau_l$ of level $l$ by $\mathcal{X}_t$ dominates stochastically a geometric random variable
with parameter $r := (2\delta/(1-\delta))^l$. In the end we deduce that if $t = t(n) = o(1/r)$

$$ 
\begin{aligned}
\mathbb{P}[X_t \notin B_{\bar{\mathcal{P}}}(x_0, l)] &\le \mathbb{P}[\tau_l \le t] \\
&\le 1 - (1-r)^t \\
&= rt + o(rt) = o(1).
\end{aligned}
$$

Since $1/r = (\log n)^{\beta \log(2\delta/(1-\delta))}$, this proves the result. $\square$

**Proof of Theorem 5.2.** Let $a > 1$, $t := (\log n)^a$ and $\varepsilon \in (0,1)$. By Theorem 5.1 the chain is irreducible and aperiodic with high probability. Let $\pi$ be the unique stationary measure of $\bar{\mathcal{P}}$. Thanks to the lemma, we can find $\beta > 0$ and $\delta > 0$ small enough for which there exists with high probability a state $x \in [n]$ satisfying $\mathbf{P}_x[X_t \notin B] = o(1)$, where $B := B_{\bar{\mathcal{P}}}(x, \beta \log \log n)$. Then recall the decomposition of $\pi = \pi_1 + \pi_2$ given by Remark 5.6. Since the ball $B$ contains at most $O(\Delta^{\beta \log \log n}) = n^{o(1)}$ vertices, Cauchy-Schwarz inequality implies

$$ \pi_1(B) \le \sqrt{|B| \sum_{u \in B} \pi_1(u)^2} = n^{-1/2+o_{\mathbb{P}}(1)}, $$

while $\pi_2(B) \le \pi_2([n]) = o_{\mathbb{P}}(1)$. Consequently

$$ \bar{\mathcal{P}}^t(x, B) - \pi(B) = 1 - o_{\mathbb{P}}(1) $$

which implies $t_{\text{mix}}(x, \varepsilon) \ge (\log n)^a$. $\square$

**Remark 5.8.** As was noticed above for $\delta$ sufficiently small the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ on the tree $T$ becomes sufficiently biased towards the root to be recurrent. On the other hand, the Borel-Cantelli lemma implies that the quasi-tree $\mathcal{G}$ contains a.s. infintely many copies of $T_\le l$ for any $l$. The existence of such "trapping neighbourhoods" which could potentially slow down the chain by an important amount is a problem that will arise in the next section where we study asymptotic properties of $(\mathcal{X}_t)_{t \ge 0}$. In particular the spectral radius of this Markov chain may be equal to 1, despite the tree-like aspect of the graph.

## 5.5 Analysis on the quasi-tree on quasi-trees I: escape prob- abilities

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 5.3 for the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ on a random infinite quasi-tree $\mathcal{G}$. This will allow us later to deduce the corresponding statements for the chain $X$ thanks to the coupling presented in Section 5.2.7. As in [22, 92], the argument is based on the existence of regeneration times,
which are 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. Because of the potential trapping phenomenon mentioned in Remark 5.8, this requires non trivial arguments, which is the object of this whole section.

### 5.5.1 Escape probabilities

We recall $\mathcal{G}$ denotes a random rooted quasi-tree which under $\mathbb{P}$ has the law of the random quasi-tree described in Section 5.2.6. Its vertex set is $\mathcal{V}$.

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

$$q_{\text{Esc}}(x) := \mathbf{P}_x [\forall t \ge 1 : \mathcal{X}_t \in \mathcal{G}_x].$$

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_{\text{Esc}}(x) := \mathbf{P}_x [\forall t \ge 0 : \mathcal{X}_t \in \mathcal{G}_x] \wedge \mathbf{P} [\tau_{\eta(x)} = \infty \mid \mathcal{X}_{1/2} = x].$$

We call these quantities the *escape probability* at $x$.

*Remark 5.9.* Note that if $x$ is not a center,

$$q_{\text{Esc}}(x) \ge q(x, \eta(x)) \mathbf{P} [\tau_x = \infty \mid \mathcal{X}_{1/2} = \eta(x)].$$

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

$$q_{\text{Esc}}(x) \ge p(x, \eta(x)) P(x, y) q_{\text{Esc}}(y).$$

By Assumption (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.

Furthermore, recall the Ulam labelling of Section 5.2.6. For all $x \in \mathcal{U}$, if $x \in \mathcal{V}$ is not a center then the probability $q_{\text{Esc}}(x)$ is measurable with respect to $\mathcal{G}_x$ and $\iota(x)$ only. Hence

$$\mathbb{P}[q_{\text{Esc}}(x) \in \cdot \mid x \in \mathcal{V}, \mathcal{G} \setminus \mathcal{G}_x] = \mathbb{P}[q_{\text{Esc}}(O) \in \cdot \mid \iota(O) = \iota(x)]. \quad (5.23)$$

If $x$ is a center,

$$\mathbb{P}[q_{\text{Esc}}(x) \in \cdot \mid x \in \mathcal{V}, \mathcal{G} \setminus \mathcal{G}_x] = \mathbb{P}[q_{\text{Esc}}(\eta(O)) \in \cdot \mid \iota(O) = \iota(\eta(x)), \iota(\eta(O)) = \iota(x)].$$

Thus the law of escape probabilities is entirely determined by the case of the root, conditional on $\iota(O)$ and $\iota(\eta(O))$. To ease the notation, we will sometimes keep $\iota$ implicit in the sequel and write only $O, \eta(O)$ when conditioning on the types of these vertices.
In [92], the authors prove that the escape probability is lower bounded uniformly in $n$, conditional on $\mathcal{G}$. This comes from the fact that the momentum of the chain, that is the expected change in distance to the root, is everywhere non-negative, and even positive for most vertices. This argument is very specific to the case of the simple random walk: with biases on the transition probabilities the momentum can be negative. In the reversible model, we can still prove a uniform lower bound on escape probabilities thanks to a comparison argument.

**Proposition 5.3.** In the reversible model of Section 5.1.2,

$$ \inf_{x \in \mathcal{V}} q_{\text{Esc}}(x) = \Theta(1). $$

In the general model, a uniform lower bound on escape probabilities may not be achievable. The counter example of Section 5.4 and Remark 5.8 show that in the corresponding quasi-tree,

$$ \inf_{x \in \mathcal{V}} q_{\text{Esc}}(x) = 0. $$

This phenomenon, which was already present in [22], is ultimately what prevents uniform cutoff. Cutoff from typical vertices remains possible as we will argue that "trapping neighbourhoods", where escape probabilities tend to 0, are sufficiently rare that they are essentially ignored from the chain, provided it is started at a typical vertex. The starting point is the following lemma, also proved with comparison arguments. The result is stated for the root but from Remark 5.9 it extends to other subquasi-trees.

**Lemma 5.6.** For all types of $O, \eta(O)$,

$$ \mathbb{E}[q_{\text{Esc}}(O) | O, \eta(O)] = \Theta(1). $$

Equivalently, there exists a constant $q_0 > 0$ such that for all types of $O, \eta(O)$,

$$ \mathbb{P}[q_{\text{Esc}}(O) \ge q_0 | O, \eta(O)] \ge q_0. \qquad (5.24) $$

Establishing this lemma is the main difficulty so the proof is deferred to the next sections. Using the tree structure of $\mathcal{G}$, the previous lemma can be boostapped to yield a much better control on the behaviour of the escape probability at typical vertices.

**Proposition 5.4.** There exist constants $q_0, \delta \in (0, 1)$ such that for all types of $O, \eta(O)$ and $k \ge 0$,

$$ \mathbb{P}[q_{\text{Esc}}(x) < q_0 \delta^{4k} | O, \eta(O)] \le q_0^{2k}. \qquad (5.25) $$

*Proof of Proposition 5.4.* Recall that from assumptions (H1) and (H2) we suppose all transition probabilities are lower bounded by a constant $\delta$. This is also the constant $\delta$
of the proposition. By Assumption (H3), every vertex $y \in \mathcal{V}$ has at least one vertex at small-range distance 1 and two vertices if $\iota(y) \in V_1$. Consequently, for any realization of $G_x$ and $k \ge 0$, there are at least $2^k$ centers at distance at long-range distance $2k$ from $x$ in $G_x$ which can be joined from $x$ in less than $4k$ steps by $\mathcal{X}_t$. Since transition probabilities are bounded below by $\delta$, it suffices that one of these vertices $y$ has $q_{\text{Esc}}(y) \ge q_0$ to obtain that $q_{\text{Esc}}(O) \ge q_0\delta^{4k}$. Now since these vertices are centers and at the same long-range distance from $x$ their respective subtrees are disjoint and thus independent. The probability that all $y$ have $q_{\text{Esc}}(y) < q_0$ is thus upper bounded by $q_0^{2k}$ by Lemma 5.6. $\square$

From the previous proposition, we also deduce the following. Below, a path refers to a possible trajectory of the chain $\mathcal{P}$ and its $\mathcal{P}$-length is the corresponding number of transitions.

**Proposition 5.5.** For all $C > 0$ there exist constants $q_0, \alpha \in (0, 1]$ such that the following holds: for all $r \ge 0$, with probability at least $1 - \exp(-Cr)$ conditional on the types of $O, \eta(O)$, every path in $G$ of $\mathcal{P}$-length $r$ starting from $O$ contains a proportion at least $\alpha$ of vertices $x$ such that $q_{\text{Esc}}(x) \ge q_0$.

The proof is concluded with an argument similar in spirit to Lemma 2.2 in [52] (initially due to Grimmett and Kesten [81]) and used to prove Lemma 2.3 in [22].

*Proof of Prop 5.5.* We reason conditional on $\iota(O)$ and $\iota(\eta(O))$ so we can assume these are fixed. We distinguish the case of large and small paths, for which it suffices to find one state with lower bounded escape probability. Namely if $r < 10$, Lemma 5.6 shows that $q_{\text{Esc}}(O) \ge q_0$ with positive probability, in which case every path of length at most 10 contains a proportion at least $1/10$ vertices with escape probability lower bounded by $q_0$.

For larger paths, since $G$ is random, we use the Ulam labelling to consider vertices independently of the realization of $G$. Given $q_0 > 0$ to be determined and $x \in \mathcal{U}$, let $A_x = \mathbb{1}_{x \in \mathcal{V}, q_{\text{Esc}}(x) \ge q_0}$. Consider now a self-avoiding path $\mathfrak{p}$ in $\mathcal{U}$ started at $\iota(O)$ which can be the realization of a path of $\mathcal{P}$-length $r \ge 10$ in $G$, starting at $O$. If $\mathfrak{p}$ is indeed a path in $G$, let $K_{\mathfrak{p}}$ be the set of vertices which are at small-range distance at most 1 from $\mathfrak{p}$ but are not endpoints of a long-range edge crossed by $\mathfrak{p}$. Let us give an example for clarity: a path in $\mathcal{U}$ may for instance contain vertices $u_0, u_1, (u_1, v_1), (u_1, v_2) \in \mathcal{U}$ such that $u_0 = \iota(O)$, $P(u_0, u_1) > 0$, $V(v_1) \ne V(u_2)$ and $P(v_1, v_2) > 0$. If $\eta(u_1)$ is such that $P(\eta(u_1), v_1) > 0$, this path becomes a genuine path in $G$ of $\mathcal{P}$-length 3, with $K(\mathfrak{p}) = \{u_0, (u_1, v_1), (u_1, v_2)\}$ unless $\eta(u_1) \in \{v_1, v_2\}$ in which case one needs to discard the corresponding vertex. Define $A(\mathfrak{p}) := \sum_{x \in K_{\mathfrak{p}}} A_x$. Then by construction vertices
which are in $K_p$ must have disjoint subquasi-trees, so conditional on $\mathfrak{p} \in \mathcal{G} \ A(\mathfrak{p})$ is
a sum of independent Bernoulli variables. Let us lower bound the number of these
variables. Since the path is self-avoiding $\mathfrak{p}$ contains $r+1$ vertices. Supposing $k$ is the
number of long-range edges crossed by $\mathfrak{p}$, $r+1-2k$ vertices do not belong to a long-range
edge of $\mathfrak{p}$. $k+1$ is also the number of small-range components crossed by $\mathfrak{p}$. Now every
other of these small-range component is isomorphic to a component of $V_1$, which from
assumption (H3) contains at least three vertices. By the self-avoiding property, there
is at least one vertex of such a small-range component which is in $K_p$. Hence

$$
m := |K_{\mathfrak{p}}| \ge \max(r+1-2k, \lfloor (k+1)/2 \rfloor) \ge \frac{r}{5} - 1 \ge 1.
$$

On the other hand, for all $q \in (0,1)$ Proposition 5.4 and Remark 5.9 imply the
existence of a value of $q_0 > 0$, independent of $n$, such that conditional on $x \in \mathcal{V}$, the
Bernoulli variable $A_x$ has parameter lower bounded by $q$. Thus for any path $\mathfrak{p}$ in $\mathcal{W}$,
conditional on it being in $\mathcal{G}$, $A(\mathfrak{p})$ dominates a Binomial$(m,q)$. From Chernoff's bound,
if $Z$ is such a binomial variable, for any $\alpha, \theta > 0$

$$
\begin{align*}
\mathbb{P}[Z < \alpha m] &= \mathbb{P}[e^{-\theta Z} > e^{-\theta \alpha m}] \\
&\le e^{\theta \alpha m + \log \mathbb{E}[e^{-\theta Z}]} \\
&= e^{m(\theta \alpha + \log(1-q+qe^{-\theta}))}.
\end{align*}
$$

The base of the exponential can be made arbitrarily small by letting $q \to 1$, $\theta \to \infty$ and
$\alpha \to 0$, namely for all $\varepsilon \in (0,1)$, for all $q > 1 - \varepsilon$, there exists $\alpha \in (0,1)$ such that for all
$m \ge 0$,

$$
\mathbb{P}[Z < \alpha m] \le \varepsilon^m. \tag{5.26}
$$

Hence, combining the previous observations, for all $\varepsilon > 0$ one can find $q_0 > 0$ and
$\alpha > 0$, all independent of $n$, so that for all self-avoiding path $\mathfrak{p}$ of length $r$ starting from
$\iota(O)$ in $\mathcal{U}$.

$$
\mathbb{P}[A(\mathfrak{p}) < \alpha r \mid \iota(O), \iota(\eta(O)), \mathfrak{p} \in \mathcal{G}] \le \varepsilon^r. \quad (5.27)
$$

Since the number of self-avoiding paths of $\mathcal{P}$-length $r$ in $\mathcal{G}$ is bounded by $O(\Delta^r)$ thanks
to (5.11), we can bound

$$
\begin{align*}
& \mathbb{P}[\exists \mathfrak{p} \subset \mathcal{G} : |\mathfrak{p}|_\mathcal{P} = r, A(\mathfrak{p}) < \alpha r \mid O, \eta(O)] \\
&= \mathbb{E} \left[ \sum_{\mathfrak{p} \subset \mathcal{W}} \mathbb{1}_{\mathfrak{p} \subset \mathcal{G}, |\mathfrak{p}|_\mathcal{P} = r} \mathbb{P}[A(\mathfrak{p}) < \alpha r \mid \iota(O), \iota(\eta(O)), \mathfrak{p} \in \mathcal{G}] \mid O, \eta(O) \right] \\
&\le O((\Delta \varepsilon)^r)
\end{align*}
$$

where $\mathfrak{p} \subset \mathcal{W}, \mathcal{G}$ denotes a self-avoiding path of $\mathcal{W}$ or $\mathcal{G}$ respectively. Thus given $C > 0$,
$A(\mathfrak{p}) \ge \alpha r$ holds simultaneously for all paths with probability $1 - (\varepsilon\Delta)^r = 1 - e^{-Cr}$
choosing $\varepsilon$ and then $q_0, \alpha$ accordingly. This almost proves the result, except that the vertices considered in the random variables $A(\mathfrak{p})$ may not be on the path $\mathfrak{p}$. However even if the proportion $\alpha r$ of vertices with lower bounded escape probability may lie partly outside $\mathfrak{p}$, this consists of vertices which can be reached in at most one step from $\mathfrak{p}$. Hence up to modifying the constant $q_0$ we can in the end deduce that every path $\mathfrak{p}$ contains a proportion $\alpha r$ of vertices with lower bounded escape probability. $\square$

*Remark 5.10.* The proof actually shows a further property: with probability $1 - e^{-Cr}$ every path $\mathfrak{p}$ contains a constant proportion of vertices for which the probability to escape to infinity outside $\mathfrak{p}$ is lower bounded. This can be useful to argue that the chain is unlikely to follow a given path.

### 5.5.2 Escape probabilities: reversible model

The goal is now to establish Proposition 5.3. Some of the results proved here will also be used for the general model, when we will compare $(\mathcal{X}_t)_{t \ge 0}$ with a reversible chain. The proof is based on methods 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 [128][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 [128, Chapters 2, 3, 5] for a detailed account. Let $(\mathcal{Y}_t)_{t \ge 0}$ be an irreducible, reversible Markov chain on a state space $W$, with reversible measure $\mu$. As explained in Section 5.1.2 it can be represented as a random walk on an electrical network $(G_W, c)$, with $G_W$ a graph with vertex set $W$ and $c$ is a family of conductances on the edges of $G_W$. 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[\tau_Z < \tau_a^+] = \mathcal{C}(a \leftrightarrow Z) $$

where $\mathcal{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[\tau_a^+ = \infty] = \mathcal{C}(a \leftrightarrow \infty) \qquad (5.28) $$
In particular the chain is transient if and only if $\mathcal{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 [128]. This monotonicity can be made quantitative as follows. The proof is identical to that of [128, p.35] of the same reference.

**Lemma 5.7.** Let $G_W$ 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 \ge \lambda c_2$ edge-wise. Then for all $a \in W$

$$ \mathcal{C}_1(a \leftrightarrow \infty) \ge \lambda \mathcal{C}_2(a \leftrightarrow \infty). $$

*Remark 5.11.* If $G' \subset G_W$ 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 $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 \ge 1$, the branching number is $d-1$. We refer to [128] for a more general definition. We will only need the following facts, which can be found in Chapters 3 and 5:

**Proposition 5.6.** 1. Given a tree $T$ and $k \ge 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 $br T^{(k)} = (br T)^k$.

2. The simple random walk on a tree $T$ is transient if and only if $br T > 1$

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 5.3.* 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 \approx \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 $\tilde{\mathcal{X}}$ to $\mathcal{V}/\sim$. Clearly, lower bounding the escape probabilities of $\mathcal{X}$ or $\tilde{\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 $\tilde{\mathcal{X}}$, with the probability of going from $O$ to $\dagger$ being that of $\tilde{\mathcal{X}}$ leaving the image of $\mathcal{G}_O$.
in the quotient. Since $\tilde{\mathcal{X}}$ is reversible, the chain $\tilde{\mathcal{X}}$ is also a reversible chain. Letting $\tau_\dagger, \tau_\ddagger^+$ denote the hitting and return time to $\dagger$ of the chain $\tilde{\mathcal{X}}$, (5.28) implies

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

where $\mathcal{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}'$ be the set of vertices in $\mathcal{G}_O$ that are at small-range distance at most 2 from their centers and consider any spanning tree $\mathcal{T}$ of the subgraph spanned by $\mathcal{V}'$. Let $\tilde{\mathcal{T}}$ be the graph spanned by its projection in $\mathcal{V}'$ together with the edge $(\dagger, O)$, which remains a tree, and $\mathcal{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 5.7 implies that

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

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

We claim now $\mathcal{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}'$. 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 5.6, contains the 2-forward regular tree $T_2$, ie the tree where every vertex has 2 children. From Proposition 5.6 $\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 5.7, we can in the end lower bound $\mathcal{C}_{\tilde{\mathcal{T}}}(O \leftrightarrow \infty)$ by a universal constant. $\square$

*Remark 5.12.* 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.5.3 Escape probabilities: general model

The proof for the general model also relies on a comparison with a reversible chain. For this comparison to be valid, we will need Assumption (H4). We start with the simpler case where the property of (H4) is satisfied by all vertices, ie there exists $l \ge 1$ such that

$$ \forall x, y \in V \quad P(x, y) > 0 \Leftrightarrow (I + P)^l(y, x) > 0. \qquad (H4') $$

Note this implies in particular that all states are recurrent.

#### Comparison of Green Functions

The comparison will only be possible on a random subgraph of $\mathcal{G}$. The starting point is Theorem 2.25 in [159], which proves that transience of a non-reversible Markov chain can be deduced from that of a reversible chain, provided their transition probabilities and their invariant measures can be compared up to multiplicative factors. As for Rayleigh's monotonicity principle, this qualitative result can be made quantitative as it based on a comparison between Green functions, which is the consequence of the following lemma.

**Lemma 5.8** ([159, Lemma 2.24]). Let $H$ be a Hilbert space with inner product $\langle \cdot, \cdot \rangle$ and let $T_1, T_2$ be two invertible linear operators on $H$ such that:

(i) $T_1$ is self-adjoint,

(ii) $\langle T_2 f, f \rangle \ge \langle T_1 f, f \rangle \ge 0$ for all $f \in H$.

Then for all $f \in H$,

$$ \langle T_1^{-1} f, f \rangle \ge \langle T_2^{-1} f, f \rangle. $$

By Remark 5.9 it suffices to lower bound $\mathbf{P}[\tau_O = \infty | \mathcal{X}_{1/2} = \eta(O)]$. Consider $\tilde{\mathcal{G}} = \{O\} \cup \mathcal{G}_O$ and let $\mathcal{P}_0$ denote the transition kernel of the chain on $\tilde{\mathcal{G}}$ which goes from $O$ to $\eta(O)$ with probability 1 at integer time steps, stays at $O$ at half-integer time steps, and otherwise has the transitions of $\mathcal{X}$. Let

$$ G_{\mathcal{P}_0}(x, y) := \sum_{t \in \mathbb{N}} \mathcal{P}_0^t(x, y) $$

be the Green function of $\mathcal{P}_0$. $G_{\mathcal{P}_0}(O, O)$ is the expected number of visits to $O$, which has a geometric distribution of parameter $q_{\text{Esc}}(\eta(O))$ since the chain automatically goes from $O$ to $\eta(O)$. Hence

$$ G_{\mathcal{P}_0}(O, O) = \mathbf{P}[\tau_O = \infty | \mathcal{X}_{1/2} = \eta(O)]^{-1} \qquad (5.29) $$
so it is equivalent to lower bound escape probabilities and upper bound the Green function. Lemma 5.8 will allow to do so by comparison, expressing the Green function as $G_{\mathcal{P}_0} = \lim_{z \to 1} (I - z\mathcal{P}_0)^{-1}$.

We will apply the lemma to compare the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ with basically the simple random walk on a subgraph of the quasi-tree. To this end, we will need to show that the transition probabilities as well as an invariant measure can be lower bounded pointwise by those of the simple random walk, up to multiplicative factor. Since the graph $\mathcal{G}$ has bounded degrees by (5.11), the transition probabilities and invariant measure of the simple random walk are both of constant order. By Assumption (H1) transition probabilities of $(\mathcal{X}_t)_{t \ge 0}$ are also of constant order however these transitions may occur in only one direction. From the hypothesis done in this section (H4'), this issue is solved by considering a bounded power of a lazy version of the chain. However when it comes to the invariant measure, the counter example from Section 5.4 shows that we can expect the infimum of the invariant measure to be 0, which is why comparison is only possible on a subgraph. Since the invariant measure can be taken up to multiplicative constant, comparison with the simple random walk requires finding a subgraph where the invariant measure is of the same order or larger than the measure of the root. In particular we need to find explicitly one such invariant measure for $(\mathcal{X}_t)_{t \ge 0}$. This can be done thanks to the tree structure of $\mathcal{G}$.

## Invariant measure of $(\mathcal{X}_t)_{t \ge 0}$

The idea is based on Kolmogorov's criterion for reversibility: for a reversible chain, an invariant measure can be determined explicitly from the detailed balance equation, which allows to propagate the value of the measure from a state $x$ to another state $y$ by considering any path between $x$ and $y$. Since the invariant measure, which does not need to be a probability, is determined up to multiplicative constant anyway, this gives an algorithmic way to compute an invariant measure. For a non-reversible chain this procedure does not work as multiple paths between vertices may give different values of the measure (the absence of this phenomenon is precisely Kolmogorov's condition for reversibility). However if there are no multiple paths, in other words if the underlying graph is a tree, and transitions can be reversed, then we can find such a reversible measure. Now in our setting, quasi-trees have a large-scale tree structure arising from the long-range edges, while cycles can only be present in small-range components. We can thus combine invariant measures of small-range components to obtain invariance with respect to transitions inside a component, with the previous idea to obtain invariance along long-range edges as well.

Let $\pi_P$ be an invariant measure of $P$ which puts positive mass on every commu-
nicating class. Assumption (H4') implies that $P$ has no transient states so $\pi_P(x) > 0$ for all $x \in V$. Extend $\pi_P$ to $\mathcal{G}$ by setting $\pi_P(x) := \pi_P(\iota(x))$ for all $x$. The invariant measure $\nu$ is described in terms of the following weights: for every center $x$, set

$$a_x := \frac{\pi_P(\eta(x))q(\eta(x), x)}{\pi_P(x)q(x, \eta(x))} \qquad (5.30)$$

Then define

$$Z(x) := \prod_{i=1}^{k} a_{x_i} \qquad (5.31)$$

where $x_1, \dots, x_k = x$ is the unique sequence of centers that lie on any path in $\mathcal{G}$ from $O$ to $x$, and $Z(O) := 1$. We extend $Z$ to non-center vertices by $Z(x) := Z(x^o)$.

**Lemma 5.9.** Under Assumption (H4') the measure $\nu$ on $\mathcal{V}$ defined by

$$\nu(x) := Z(x)\pi_P(x) \qquad (5.32)$$

is an invariant measure of the Markov chain $(\mathcal{X}_t)_{t \ge 0}$.

*Proof.* Recall $\mathcal{P}$ denotes the transition kernel of the Markov chain $(\mathcal{X}_t)_{t \ge 0}$ and consider $x, y \in \mathcal{V}$. Having $\mathcal{P}(x, y) > 0$ requires that either $x$ is in the same small-range component as $y$, which occurs if and only if $x^o = y^o$, or $x = \eta(y^o)$ is in a lower level, or $x$ is in a higher level, that is $x = \eta(z)$ for $z \neq y^o$ in the small-range component of $y$. In the second case, (5.30) implies

$$\begin{aligned} \nu(\eta(y^o))\mathcal{P}(\eta(y^o), y) &= Z(\eta(y^o))\pi_P(\eta(y^o))q(\eta(y^o), y^o)P(y^o, y) \\ &= Z(y^o)\pi_P(y^o)q(y^o, \eta(y^o))P(y^o, y) \end{aligned}$$

Similarly if $z \neq y^o$ is in the small-range component of $y$,

$$\begin{aligned} \nu(\eta(z))\mathcal{P}(\eta(z), y) &= Z(y^o)a_{\eta(z)}\pi_P(\eta(z))q(\eta(z), z)P(z, y) \\ &= Z(y^o)\pi_P(z)q(z, \eta(z))P(z, y). \end{aligned}$$

Thus these two cases can be regrouped together as

$$\sum_{x:x^o \neq y^o} \nu(x)\mathcal{P}(x,y) = \sum_{x:x^o=y^o} Z(y^o)\pi_P(x)q(x,\eta(x))P(x,y).$$

Then using that $p+q=1$ and the invariance of $\pi_P$ with respect to $P$, we deduce

$$\begin{aligned} \sum_x \nu(x) \mathcal{P}(x, y) &= \sum_{x:x^o=y^o} Z(y^o) \pi_P(x) p(x, \eta(x)) P(x, y) + Z(y^o) \pi_P(x) q(x, \eta(x)) P(x, y) \\ &= Z(y^o) \sum_{x \in V(y^o)} \pi_P(x) P(x, y) \\ &= Z(y^o) \pi_P(y) \\ &= \nu(y). \end{aligned}$$

□