# Mixing time and expansion of non-negatively curved Markov chains

Florentin Münch111Max Planck Institute for Mathematics in the Sciences,
Leipzig<EMAIL_ADDRESS>& Justin Salez222Université Paris-Dauphine & PSL,
CEREMADE, Paris<EMAIL_ADDRESS>
###### Abstract

We establish three remarkable consequences of non-negative curvature for
sparse Markov chains. First, their conductance decreases logarithmically with
the number of states. Second, their displacement is at least diffusive until
the mixing time. Third, they never exhibit the cutoff phenomenon. The first
result provides a nearly sharp quantitative answer to a classical question of
Ollivier, Milman & Naor. The second settles a conjecture of Lee and Peres for
graphs with non-negative curvature. The third offers a striking counterpoint
to the recently established cutoff for non-negatively curved chains with
uniform expansion.

##  1 Introduction

In Riemaniann geometry, a lower bound on the Ricci curvature classically
implies an array of powerful estimates for the underlying manifold, including
diameter bounds, volume growth, comparison principles, splitting theorems,
spectral estimates, and concentration inequalities [11]. Over the past decade,
those remarkable implications have motivated the development of non-smooth
analogues of curvature that can be applied to discrete geometries [28, 16, 10,
9, 23, 12, 21, 20]. In particular, Ollivier [23] proposed a transportation-
based definition that makes sense on arbitrary metric spaces, hence in
particular on graphs and Markov chains. Informally, a metric space has non-
negative Ollivier-Ricci curvature if balls are at least as close to each other
as their centers are. The simplest example of a finite non-negatively curved
graph is a cycle. It is classical that this graph has poor expansion, that the
random walk on it exhibits a diffusive behavior, and that its mixing time is
of the same order as the inverse spectral gap. The aim of the present paper is
to show that those three properties are in fact shared by all sparse Markov
chains with non-negative curvature. Before we state our results in full
generality, let us describe their content in the simple but important special
case of random walk on graphs.

#### Non-negatively curved graphs.

Let $G=(V,E)$ be a finite simple graph, and let $P$ denote the random-walk
transition matrix of $G$. Thus, $P$ acts on any function $f\colon
V\to\mathbb{R}$ as follows:

$\displaystyle(Pf)(x)$ $\displaystyle=$
$\displaystyle\frac{1}{\deg(x)}\sum_{y\sim x}f(y),$

where the notation $y\sim x$ indicates that $\\{x,y\\}\in E$. Following
Ollivier [23, 22], we say that $G$ has _non-negative curvature_ if $P$
contracts the Lipschitz norm $\|f\|_{\textsc{lip}}:=\max_{y\sim
x}{|f(y)-f(x)|}$, i.e.

$\displaystyle\|Pf\|_{\textsc{lip}}$ $\displaystyle\leq$
$\displaystyle\|f\|_{\textsc{lip}}.$

This fundamental property is satisfied by many natural families of graphs,
including all Abelian Cayley graphs and, more generally, all Cayley graphs
whose generating set is conjugacy-invariant. Additional details, including a
more effective formulation in terms of couplings, will be provided in the next
section when we discuss curvature for general Markov chains.

#### Expansion.

Our first result concerns the expansion of non-negatively curved graphs. Write
$\partial A$ for the edge-boundary of a set $A\subseteq V$, and $\deg(A)$ for
the sum of the degrees of all vertices in $A$. With this notation, the
_conductance_ (also known as Cheeger constant, or bottleneck ratio) of $G$ is

$\displaystyle\Phi$ $\displaystyle:=$
$\displaystyle\min\left\\{\frac{|\partial A|}{\deg(A)}\colon A\subseteq
V,0<\deg(A)\leq|E|\right\\}.$

Sequences of bounded-degree graphs whose size diverges but whose conductance
remains bounded away from zero are famously known as _expanders_. Whether such
graphs can have non-negative curvature is a natural question, first raised by
Milman and Naor and then popularized in a survey by Ollivier [22, Problem T].
The problem has remained open until very recently, when a negative answer was
given by the second author [27]. Specifically, the latter used the notion of
entropy for graph limits to prove that non-negative curvature and expansion
are incompatible “at infinity”, and the conclusion was then transferred to
finite graphs using a compactness argument. A clear drawback of this approach
is its non-quantitative nature. In particular, the second author asked for a
direct, quantitative relation between volume, degree and expansion on non-
negatively curved graphs. This is precisely the content of our first main
result.

######  Theorem 1 (Poor expansion).

If $G$ has non-negative curvature, then

$\displaystyle\Phi$ $\displaystyle\leq$ $\displaystyle c\sqrt{\frac{d\log
d}{\log n}},$

where $n$ denotes the number of vertices of $G$, $d$ the maximum degree, and
$c$ a universal constant.

In other words, large graphs can not simultaneously enjoy non-negative
curvature and uniform expansion unless their maximum degree grows at least
like $\log n/\log\log n$. We note that this is sharp up to the $\log\log n$
correction. Indeed, a celebrated result of Alon and Roichman asserts that
random Cayley graphs with logarithmic degrees have uniform expansion with high
probability [1], and non-negative curvature can be enforced by specializing
this result to Abelian groups.

#### Mixing times.

Our second result is a complete determination of the order of magnitude of the
mixing time of all vertex-transitive graphs with bounded degrees and non-
negative curvature. Suppose that $G$ is vertex-transitive, with degree $d$ and
volume $n$. Fix an arbitrary origin $x\in V$ (the choice is irrelevant, by
transitivity), and consider the lazy simple random walk on $G$ started at $x$,
i.e. the Markov chain $(X_{t})_{t\geq 0}$ on $V$ with initial condition
$X_{0}=x$ and transition matrix $(P+I)/2$. The _mixing time_ of $G$ is a
fundamental graph-theoretical parameter, defined as follows [14]:

$\displaystyle{\rm t}_{\textsc{mix}}$ $\displaystyle:=$
$\displaystyle\min\left\\{t\in\mathbb{N}\colon\max_{A\subseteq
V}\left|{\mathbb{P}}(X_{t}\in
A)-\frac{|A|}{n}\right|\leq\frac{1}{4}\right\\}.$

An important, closely related quantity is the so-called _relaxation time_ (or
inverse spectral gap)

$\displaystyle{\rm t}_{\textsc{rel}}$ $\displaystyle:=$
$\displaystyle\frac{1}{1-\lambda_{2}},$

where $1=\lambda_{1}>\lambda_{2}\geq\ldots\geq\lambda_{n}$ denote the ordered
eigenvalues of $P$. It is classical that ${\rm t}_{\textsc{mix}}\geq{\rm
t}_{\textsc{rel}}$, but this inequality can be off by a factor as large as
$\log n$ (this is the case, e.g., for expanders).

######  Theorem 2 (Mixing times).

All vertex-transitive graphs with non-negative curvature satisfy

$\displaystyle{\rm t}_{\textsc{mix}}\ \asymp_{d}\ {\rm t}_{\textsc{rel}}\
\asymp_{d}\ \frac{1}{\Phi^{2}},$

where the notation $a\asymp_{d}b$ means that the ratio $a/b$ is bounded from
above and below by positive constants that depend only on the degree $d$.

This has the following remarkable consequence. For a sequence of graphs
$(G_{n})_{n\geq 1}$, the condition

$\displaystyle\frac{{\rm t}_{\textsc{mix}}(G_{n})}{{\rm
t}_{\textsc{rel}}(G_{n})}$ $\displaystyle\xrightarrow[n\to\infty]{}$
$\displaystyle+\infty$

is known as the _product condition_. It is necessary (and conjecturally also
sufficient, at least for vertex-transitive graphs) for the occurrence of the
so-called _cutoff phenomenon_ , a celebrated but still mysterious phase
transition in the approach to equilibrium of certain Markov chains [7, 14].
Thus, Theorem 2 implies that vertex-transitive graphs with fixed degree and
non-negative curvature never exhibit cutoff. This stands in stark contrast
with recent results due to the second author, showing that many non-negatively
curved graphs with logarithmic degree do exhibit cutoff [26]. Interestingly,
the conclusion of Theorem 2 is known to hold for fixed-degree Cayley graphs of
_moderate growth_ [6]. This geometric condition was later shown to be
equivalent to the much simpler requirement that the diameter is algebraically
large in the volume [5] (see the recent paper [29] for an extension to vertex-
transitive graphs). This raises the following question. A positive answer
would be surprisingly strong, but we have not been able to produce any
counter-example.

######  Question 1 (Moderate growth?).

Do all non-negatively curved graphs with degree at most $d$ satisfy

$\displaystyle\mathrm{diam}(G)$ $\displaystyle\geq$
$\displaystyle\varepsilon_{d}n^{\varepsilon_{d}},$

where $n$ is the number of vertices, and $\varepsilon_{d}>0$ a constant
depending only on $d$?

Indeed, this question was answered affirmatively in case of a modified Barky
Emery curvature dimension condition in [2], and later by the first author in
case of the weaker, unmodified Bakry Emery curvature dimension condition [18].

#### Diffusivity.

Finally, our last result concerns the speed of random walk on vertex-
transitive graphs with non-negative curvature. Many infinite graphs such as
the line $\mathbb{Z}$ are known to exhibit a _diffusive_ behavior, in the
sense that the typical graph distance between $X_{t}$ and $X_{0}$ grows like
$\sqrt{t}$. On a finite graph, the distance to the starting point can of
course no longer grow indefinitely with time, but one may still hope for a
diffusive behavior on _appropriate time-scales_. This vague statement was
recently given a powerful rigorous content by Lee and Peres [13], who showed
that the simple random walk on any finite vertex-transitive graph satisfies
the diffusive lower-bound

$\displaystyle{\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]$ $\displaystyle\geq$
$\displaystyle c\sqrt{\frac{t}{d}}$

for all $t\in[d,{\rm t}_{\textsc{rel}}]$, where $c>0$ is a universal constant.
The graph $\mathbb{Z}_{2}^{d}\times\mathbb{Z}_{n}$ shows that this lower-bound
is sharp. However, the authors conjectured that the time-scale on which the
diffusive behavior remains valid should actually be much longer, namely, of
order ${\rm t}_{\textsc{mix}}$ [13, Conjecture 2.5]. Our second result
confirms this prediction in the case of non-negatively curved graphs.

######  Theorem 3 (Diffusive lower-bound).

If $G$ is vertex-transitive and non-negatively curved, then

$\displaystyle{\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]$ $\displaystyle\geq$
$\displaystyle c\sqrt{\frac{t}{d}},$

for $t\in[d,{\rm t}_{\textsc{mix}}]$, where $c$ is a universal constant.

We emphasize that our estimates are not restricted to simple random walks on
graphs. Analogous results will be stated for general Markov chains with non-
negative curvature. In particular, neither reversibility, nor even the
symmetry of the support of $P$ are actually required for a version of Theorem
1 to hold. Ollivier curvature with respect to a directed metric has been
explored before in [31, 24, 25, 8]. However the specific consequences of non-
negative curvature seem to be unexplored to the best of our knowledge. Our
general results are exposed in Section 2 below, and are proved in Section 3.

##  2 Main results

In the remainder of the paper, we consider an arbitrary, irreducible
stochastic matrix $P$ on a finite state space $V$. A natural measure of the
“distance” from a state $x\in V$ to a state $y\in V$ is the minimum number of
transitions needed for the chain to move from $x$ to $y$, namely

$\displaystyle\mathrm{dist}(x,y)$ $\displaystyle:=$
$\displaystyle\min\left\\{k\in\mathbb{N}\colon P^{k}(x,y)>0\right\\}.$

This quantity is not necessarily symmetric, but it clearly satisfies the two
other axioms of a distance. We may then use optimal transport to extend this
notion to probability measures as follows: write $\mathcal{P}(V)$ for the set
of probability measures on $V$, and define
$W\colon\mathcal{P}(V)\times\mathcal{P}(V)\to\mathbb{R}_{+}$ by

$\displaystyle W(\mu,\nu)$ $\displaystyle:=$
$\displaystyle\inf_{X\sim\mu,Y\sim\nu}{\mathbb{E}}\left[\mathrm{dist}(X,Y)\right],$

where the infimum runs over all possible random pairs $(X,Y)$ whose marginals
are $\mu$ and $\nu$. Again, this quantity is not necessarily symmetric, but it
always satisfies the two other axioms of a distance. Due to Kantorovich
duality [30, Theorem 5.10 and Particular Case 5.4], we can write

$W(\mu,\nu)=\sup\left\\{\nu f-\mu f:\|f\|_{\textsc{lip}}\leq 1\right\\}$

with

$\|f\|_{\textsc{lip}}:=\sup_{y\sim x}f(y)-f(x).$

Finally, we say that $P$ has _non-negative curvature_ if it is a contraction
under $W$, i.e.

$\displaystyle\forall\mu,\nu\in\mathcal{P}(V),\quad W(\mu P,\nu P)$
$\displaystyle\leq$ $\displaystyle W(\mu,\nu).$ (1)

Due to Kantorovich duality and as in the introduction, non-negative is
equivalent to

$\|Pf\|_{\textsc{lip}}\leq\|f\|_{\textsc{lip}}.$

For a continuous time version in the directed graph case, see [25]. Indeed,
Ollivier curvature with non-symmetric distance has been studied before in [31,
24, 8]. By convexity, it is in fact sufficient to check property (1) on Dirac
masses $\mu=\delta_{x},\nu=\delta_{y}$, $x,y\in V$. Moreover, by the triangle
inequality, we may further restrict our attention to the case where $y$ is a
neighbor of $x$ (by which we mean that $\mathrm{dist}(x,y)=1$ and which we
denote by $y\sim x$), i.e.

$\displaystyle\forall y\sim x,\quad W\left(P(x,\cdot),P(y,\cdot)\right)$
$\displaystyle\leq$ $\displaystyle 1.$ (2)

This local condition is easily verified in practice. For example, it holds for
random walks on Abelian groups and, more generally, random walks with a
conjugacy-invariant support, as we now explain.

######  Example 1 (Random walks on groups).

Suppose that $V$ is a group, and fix $\mu\in\mathcal{P}(V)$. By definition,
the _random walk_ on $V$ with increment distribution $\mu$ is the Markov chain
whose transitions correspond to left-multiplication by a $\mu-$distributed
element, i.e. $P(x,y):=\mu(yx^{-1}).$ This chain has non-negative curvature as
soon as the set $S:=\\{z\in V\colon\mu(z)>0\\}$ is _conjugacy-invariant_ ,
i.e.

$\displaystyle\forall z\in V,\quad zSz^{-1}$ $\displaystyle=$ $\displaystyle
S.$ (3)

Indeed, this assumption implies that $\mathrm{dist}(zx,zy)=\mathrm{dist}(x,y)$
for all $x,y,z\in V$. In particular, if $Z$ denotes a random variable with law
$\mu$, then the “obvious” coupling of $P(x,\cdot)$ and $P(y,\cdot)$ given by
$X:=Zx$ and $Y:=Zy$ verifies (2). Note that the condition (3) trivially holds
if the group is Abelian. An emblematic non-Abelian example is the
transposition walk on the symmetric group [3].

To avoid periodicity issues, we now assume that $P$ is lazy, i.e., $P(x,x)\geq
1/2$ for all $x\in V$. This is more than enough to guarantee that the chain
mixes, in the sense that

$\displaystyle\forall x,y\in V,\quad P^{t}(x,y)$
$\displaystyle\xrightarrow[t\to\infty]{}$ $\displaystyle\pi(y),$

where $\pi=\pi P$ denotes the unique invariant distribution. Quantifying the
speed at which this convergence to equilibrium occurs is a fundamental
question, with many applications [14, 17]. Formally, this amounts to
estimating the so-called _mixing time_ of the chain:

$\displaystyle{\rm t}_{\textsc{mix}}$ $\displaystyle:=$
$\displaystyle\min\left\\{t\geq 0\colon
d_{\textsc{tv}}(t)\leq\frac{1}{4}\right\\},\quad\textrm{ where }\quad
d_{\textsc{tv}}(t):=\max_{x\in
V}\left\|P^{t}(x,\cdot)-\pi\right\|_{\textsc{tv}}.$

Here $\|\mu-\nu\|_{\textsc{tv}}$ denotes the _total-variation distance_
between $\mu,\nu\in\mathcal{P}(V)$, defined as

$\displaystyle\left\|\mu-\nu\right\|_{\textsc{tv}}$ $\displaystyle=$
$\displaystyle\max_{A\subseteq V}|\mu(A)-\nu(A)|\ =\ \frac{1}{2}\sum_{x\in
V}|\mu(x)-\nu(x)|\ =\ \inf_{X\sim\mu,Y\sim\nu}{\mathbb{P}}(X\neq Y),$

where the infimum in the last expression runs over all possible couplings
$(X,Y)$ of $\mu$ and $\nu$. Thus, a natural way to estimate mixing times is to
exhibit good couplings, and this is precisely where curvature enters the play.
Indeed, an elementary but crucial reformulation of the non-negative curvature
assumption (1) is that the trajectories $(X_{t})_{t\geq 0}$ and
$(Y_{t})_{t\geq 0}$ emanating from any two states $X_{0}=x$ and $Y_{0}=y$ can
be coupled in such a way that their distance
$t\mapsto\mathrm{dist}(X_{t},Y_{t})$ forms a super-martingale. When combined
with an appropriate diffusive estimate for super-martingales, this observation
turns out to imply the following $O(1/\sqrt{t})$ decay for the total-variation
distance between the laws of $X_{t}$ and $Y_{t}$.

######  Theorem 4 (Total-variation decay).

Suppose that $P$ is lazy and non-negatively curved. Then,

$\displaystyle\left\|P^{t}(x,\cdot)-P^{t}(y,\cdot)\right\|_{\textsc{tv}}$
$\displaystyle\leq$
$\displaystyle\mathrm{dist}(x,y)\sqrt{\frac{10\,}{{(t+1)P_{\mathrm{min}}}}},$

for all $x,y\in V$ and all $t\geq 0$, where $P_{\mathrm{min}}$ denotes the
smallest non-zero entry of $P$.

Variants of this result have appeared in a number of works, under various
forms [4, 15, 19, 27]. However, all proofs use the fact that the increments of
the process $t\mapsto\mathrm{dist}(X_{t},Y_{t})$ are uniformly bounded (by
$2$), and this property may dramatically fail in our more general setup where
the metric is directed. Nevertheless, the conclusion turns out to remain
valid, and a proof is presented in Section 3.3. The most “obvious” application
of Theorem 4 consists in taking a maximum over all states $x,y\in V$ to obtain
the following mixing-time estimate, which is new in our directed setup.

######  Corollary 1 (Diameter bound).

If $P$ is lazy and non-negatively curved, then

$\displaystyle{\rm t}_{\textsc{mix}}$ $\displaystyle\leq$
$\displaystyle\frac{160\,(\mathrm{diam})^{2}}{P_{\mathrm{min}}},$

where $\mathrm{diam}:=\max_{x,y}\mathrm{dist}(x,y)$ denotes the diameter of
the state space.

While interesting in its own right, this estimate is actually not the key to
the new results mentioned in the Introduction. Our main finding is that a
significantly finer estimate can be deduced from Theorem 4 provided we replace
the _worst-case_ mixing time by its _average_ version:

$\displaystyle{\rm t}_{\textsc{mix}}^{\sharp}$ $\displaystyle:=$
$\displaystyle\min\left\\{t\geq 0\colon
d_{\textsc{tv}}^{\sharp}(t)\leq\frac{1}{4}\right\\},\quad\textrm{ where }\quad
d_{\textsc{tv}}^{\sharp}(t):=\sum_{x\in
V}\pi(x)\left\|P^{t}(x,\cdot)-\pi\right\|_{\textsc{tv}}.$

######  Remark 1 (Transitive chains).

Obtaining a bound on ${\rm t}_{\textsc{mix}}^{\sharp}$ rather than ${\rm
t}_{\textsc{mix}}$ is not a huge drawback. For example, we have ${\rm
t}_{\textsc{mix}}^{\sharp}={\rm t}_{\textsc{mix}}$ for all random walks on
groups and, more generally, for all _transitive_ chains ($P$ is transitive if
for each $x,y\in V$, there is a bijection $f\colon V\to V$ which maps $x$ to
$y$ and preserves the transition kernel, i.e., $P(f(u),f(v))=P(u,v)$ for all
$u,v\in V$).

Throughout the paper, we let $X=(X_{t})_{t\geq 0}$ denote a Markov chain with
transition matrix $P$ starting from stationarity ($X_{0}\sim\pi$). Our main
new estimate on ${\rm t}_{\textsc{mix}}^{\sharp}$ will depend on two key
statistics of this chain. The first one is the _mean displacement_ at time
$t$:

$\displaystyle{\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]$ $\displaystyle=$
$\displaystyle\sum_{x,y\in V}\pi(x)P^{t}(x,y)\mathrm{dist}(x,y).$

The second is the _escape probability_ in $t$ steps, i.e. the conductance of
the $t$-th power of $P$:

$\displaystyle\Phi(P^{t})$ $\displaystyle=$
$\displaystyle\min\left\\{{\mathbb{P}}\left(X_{t}\notin A|X_{0}\in
A\right)\colon A\subseteq V,0<\pi(A)\leq\frac{1}{2}\right\\}$ $\displaystyle=$
$\displaystyle\min\left\\{\frac{1}{\pi(A)}\sum_{x\in A}\sum_{y\in
A^{c}}\pi(x)P^{t}(x,y)\colon A\subseteq V,0<\pi(A)\leq\frac{1}{2}\right\\}.$

######  Theorem 5 (Main estimate).

If $P$ is lazy and non-negatively curved, then

$\displaystyle{\rm t}_{\textsc{mix}}^{\sharp}$ $\displaystyle\leq$
$\displaystyle\frac{160}{P_{\mathrm{min}}}\,\inf_{t\geq
1}\left\\{\frac{{\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]}{\Phi(P^{t})}\right\\}^{2},$
(4)

where we recall that $P_{\mathrm{min}}$ denotes the smallest non-zero entry of
$P$.

Theorem 5 has a number of notable consequences, which we now enumerate. The
simplest one is an “average” version of Corollary 1, obtained by sending
$t\to\infty$ in the infimum (4):

$\displaystyle{\rm t}_{\textsc{mix}}^{\sharp}$ $\displaystyle\leq$
$\displaystyle\frac{640\,(\mathrm{diam}^{\sharp})^{2}}{P_{\mathrm{min}}},$ (5)

where $\mathrm{diam}^{\sharp}:=\sum_{x,y\in V}\pi(x)\pi(y)\mathrm{dist}(x,y)$
denotes the _effective diameter_. Note that the latter can be significantly
smaller than the true diameter appearing in Corollary 1 (consider, e.g., the
biased random walk on a segment). A much more refined consequence of Theorem 5
is obtained by taking $t=1$ in the infimum (4): writing $\Phi=\Phi(P)$, we
readily obtain the following surprising bound.

######  Corollary 2 (Conductance bound).

If $P$ is lazy and non-negatively curved, then

$\displaystyle{\rm t}_{\textsc{mix}}^{\sharp}$ $\displaystyle\leq$
$\displaystyle\frac{40}{P_{\mathrm{min}}\Phi^{2}}.$

This offers a considerable improvement over (5) in situations where the
effective diameter diverges while the conductance remains bounded away from
$0$ (consider, e.g., random walk on a random Abelian Cayley graph with
logarithmic degree). More importantly, by virtue of an elementary
combinatorial lower-bound on ${\rm t}_{\textsc{mix}}^{\sharp}$ (see, e.g.,
[14, Section 7.1.1]), Corollary 2 implies the quantitative non-existence of
non-negatively curved expanders promised in Theorem 1. For general chains, we
will show that ${\rm t}_{\textsc{mix}}^{\sharp}$ can be bounded below by
$\mathrm{diam}^{\sharp}$, leading to the following result.

######  Corollary 3 (Poor expansion).

If $P$ is non-negatively curved, then

$\displaystyle\Phi$ $\displaystyle\leq$
$\displaystyle\frac{19}{\sqrt{P_{\mathrm{min}}\mathrm{diam}^{\sharp}}}.$

Thus, non-negatively curved chains which are large ($\mathrm{diam}^{\sharp}\gg
1$) and sparse ($P_{\mathrm{min}}$ bounded away from $0$) must have poor
expansion ($\Phi\ll 1$). This constitutes a precise quantitative answer to the
Markov-chain generalization of the question of Milman, Naor and Ollivier [22,
Problem T]. Note that there are examples of sparse chains with non-negative
curvature and arbitrarily many states (consider, e.g., a biased random walk on
a segment). However, the fact that their effective diameter is bounded forces
their stationary measure to concentrate on a bounded number of states.

Corollary 2 is sharp in the important case where $P$ is transitive, reversible
and sparse. Indeed, we have the classical lower-bound ${\rm
t}_{\textsc{mix}}\geq{\rm t}_{\textsc{rel}}$, where ${\rm
t}_{\textsc{rel}}:=(1-\lambda_{2})^{-1}$ denotes the inverse spectral gap of
$P$ (see, e.g., [14]), and the first author established in [19] the Buser
inequality

$\displaystyle{\rm t}_{\textsc{rel}}$ $\displaystyle\geq$
$\displaystyle\frac{P_{\mathrm{min}}}{12\Phi^{2}},$

for any non-negatively curved, reversible chain. When combined with Corollary
2, this yields the following result, of which Theorem 2 is clearly a special
case.

######  Corollary 4 (No cutoff for sparse chains).

Fix $p\in(0,1)$. Then, any lazy reversible transitive chain with non-negative
curvature and $P_{\mathrm{min}}\geq p$ satisfies

$\displaystyle{\rm t}_{\textsc{mix}}\ \asymp_{p}\ {\rm t}_{\textsc{rel}}\
\asymp_{p}\ \frac{1}{\Phi^{2}},$

where the notation $a\asymp_{p}b$ means that the ratio $a/b$ is bounded from
above and below by positive constants that depend only on $p$. In particular,
no family of such chains can exhibit cutoff.

An important observation here is that the transitivity of the chain is only
used to ensure that ${\rm t}_{\textsc{mix}}={\rm t}_{\textsc{mix}}^{\sharp}$.
Consequently, Corollary 4 extends to any collection of chains which are
“spatially homogeneous” in the mild sense that ${\rm
t}_{\textsc{mix}}\asymp{\rm t}_{\textsc{mix}}^{\sharp}$.

Finally, a last notable consequence of Theorem 5 is that the expected
displacement of the chain over short time-scales is already substantial. More
precisely, assuming that $P$ is reversible, we have

$\displaystyle\Phi(P^{t})$ $\displaystyle\geq$
$\displaystyle\frac{1-\lambda_{2}^{t}}{2}\ \geq\ \frac{1-e^{-\frac{t}{{\rm
t}_{\textsc{rel}}}}}{2},$

and the right-hand side is at least $\frac{1-e^{-1}}{2}$ for all $t\geq{\rm
t}_{\textsc{rel}}$, yielding the following estimate.

######  Corollary 5 (Fast escape).

If $P$ is lazy, reversible and non-negatively curved, then

$\displaystyle\forall t\geq{\rm
t}_{\textsc{rel}},\quad{\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]$
$\displaystyle\geq$ $\displaystyle\frac{\sqrt{{\rm
t}_{\textsc{mix}}^{\sharp}P_{\mathrm{min}}}}{41},$

where we recall that
${\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]=\sum_{x,y}\pi(x)P^{t}(x,y)\mathrm{dist}(x,y)$.

For reversible transitive chains, Lee and Peres [13] proved the diffusive
lower-bound

$\displaystyle{\mathbb{E}}[\mathrm{dist}(X_{0},X_{t})]$ $\displaystyle\geq$
$\displaystyle c\sqrt{tP_{\mathrm{min}}},$

for all $P_{\mathrm{min}}^{-1}\leq t\leq{\rm t}_{\textsc{rel}}$, where $c>0$
is a universal constant. They conjectured that this diffusive lower-bound
should remain valid until the mixing time [13, Conjecture 2.5]. Corollary 5
readily implies that this is true in the non-negatively curved case, and
Theorem 3 follows as a special case.

##  3 Proofs

Section 3.1 below is devoted to the proof of our main result, namely the
relation between conductance, displacement and mixing times (Theorem 5). The
latter exploits the diffusive total-variation decay of non-negatively curved
chains (Theorem 4), which will be proven independently in Section 3.3. Once
Theorem 5 is established, all announced corollaries follow effortlessly,
except for Corollary 3: the latter requires a lower bound on the average
mixing time in terms of the effective diameter, which we prove in Section 3.2.

###  3.1 Mixing time vs. conductance

In this section, we prove Theorem 5. We will make crucial use of Theorem 4, as
well as the following $L^{1}$ version of Cheeger’s inequality. An important
remark is that the latter holds without any assumption on the transition
matrix $P$, and will thus also apply to powers of $P$.

######  Lemma 1 ($L^{1}$ analogue of Cheeger’s inequality).

If $f\colon V\to\mathbb{R}$ satisfies $\pi f=0$, then,

$\displaystyle\sum_{x\in V}\pi(x)\left|f(x)\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{\Phi(P)}\sum_{x,y\in
V}\pi(x)P(x,y)\left|f(y)-f(x)\right|.$

###### Proof.

Upon replacing $f$ with $-f$, we may assume that $\pi(f\geq 0)\geq 1/2$. For
any $t\geq 0$, we may take $A=\\{f\geq t\\}$ in the definition of $\Phi(P)$ to
obtain

$\displaystyle\Phi(P)\sum_{x\in V}\pi(x){\bf 1}_{(f(x)\geq t)}$
$\displaystyle\leq$ $\displaystyle\sum_{x,y\in V}\pi(x)P(x,y){\bf
1}_{(f(y)\leq t<f(x))}.$

Integrating over $t\in\mathbb{R}_{+}$ and interchanging the sum and integral,
we obtain

$\displaystyle\Phi(P)\sum_{x\in V}\pi(x)f_{+}(x)$ $\displaystyle\leq$
$\displaystyle\sum_{x,y\in V}\pi(x)P(x,y)\left(f_{+}(x)-f_{+}(y)\right)_{+},$

where $a_{+}:=\max(0,a)$ denotes the positive part of $a$. Now, since $f$ is
centered under $\pi$, the left-hand side does not change if we replace
$f_{+}(x)$ by $|f(x)|/2$. Similarly, since any gradient is centered under the
measure $(x,y)\mapsto\pi(x)P(x,y)$, the right-hand side does not change if we
replace $\left(f_{+}(x)-f_{+}(y)\right)_{+}$ by
$\left|f_{+}(x)-f_{+}(y)\right|/2$. Finally, observe that
$\left|f_{+}(x)-f_{+}(y)\right|\leq|f(x)-f(y)|$. ∎

###### Proof of Theorem 5.

Fix $s\geq 1$. Lemma 1 applied to $P^{s}$ instead of $P$ gives

$\displaystyle\sum_{x\in V}\pi(x)\left|f(x)\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{\Phi(P^{s})}\sum_{x,y\in
V}\pi(x)P^{s}(x,y)\left|f(x)-f(y)\right|,$

for any centered observable $f\colon V\to\mathbb{R}$. Now, fix
$t\in\mathbb{N}$ and $z\in V$, and let us apply this to the observable
$f(x):=P^{t}(x,z)-\pi(z)$, which is centered because $\pi P^{t}=\pi$. We
readily obtain

$\displaystyle\sum_{x\in V}\pi(x)\left|P^{t}(x,z)-\pi(z)\right|$
$\displaystyle\leq$ $\displaystyle\frac{1}{\Phi(P^{s})}\sum_{x,y\in
V}\pi(x)P^{s}(x,y)\left|P^{t}(x,z)-P^{t}(y,z)\right|.$

We may now sum over all $z\in V$ and use Theorem 4 to get

$\displaystyle d_{\textsc{tv}}^{\sharp}(t)$ $\displaystyle\leq$
$\displaystyle\frac{1}{\Phi(P^{s})}\sum_{x,y\in
V}\pi(x)P^{s}(x,y)\left\|P^{t}(x,\cdot)-P^{t}(y,\cdot)\right\|_{\textsc{tv}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{10}{(t+1)P_{\mathrm{min}}}}\frac{{\mathbb{E}}\left[\mathrm{dist}(X_{0},X_{s})\right]}{\Phi(P^{s})}.$

Finally, choosing $t$ so that the right-hand side is smaller than $1/4$ shows
that

$\displaystyle{\rm t}_{\textsc{mix}}^{\sharp}$ $\displaystyle\leq$
$\displaystyle\frac{160}{P_{\mathrm{min}}}\left(\frac{{\mathbb{E}}\left[\mathrm{dist}(X_{0},X_{s})\right]}{\Phi(P^{s})}\right)^{2}.$

The result follows by taking an infimum over all $s\geq 1$. ∎

###  3.2 Effective diameter vs. conductance

Here we prove Corollary 3. We will use the following concentration inequality.

######  Lemma 2 (Concentration inequality).

For any $f\colon V\to\mathbb{R}$ and $a>0$,

$\displaystyle\pi\left(f\geq\pi f+a\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{a\Phi}\min\left(\max_{y\sim
x}\left(f(y)-f(x)\right)_{+},\max_{y\sim x}\left(f(x)-f(y)\right)_{+}\right),$

and the same holds for $\pi(f\leq\pi f-a)$.

We remark that if ”$\sim$” is symmetric, then the minimum is the Lipschitz
constant of $f$.

###### Proof.

Upon replacing $f$ by $f-\pi f$ if necessary, we may assume that $f$ is
centered under $\pi$, i.e. $\pi f=0$. Now, we use Markov’s inequality and
Lemma 1 to write

$\displaystyle\pi\left(f\geq a\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{a}\sum_{x\in V}\pi(x)f_{+}(x)$ $\displaystyle=$
$\displaystyle\frac{1}{2a}\sum_{x\in V}\pi(x)|f(x)|$ $\displaystyle\leq$
$\displaystyle\frac{1}{2a\Phi}\sum_{x,y\in
V}\pi(x)P(x,y)\left|f(x)-f(y)\right|$ $\displaystyle=$
$\displaystyle\frac{1}{a\Phi}\sum_{x,y\in
V}\pi(x)P(x,y)\left(f(x)-f(y)\right)_{+}$ $\displaystyle\leq$
$\displaystyle\frac{1}{a\Phi}\max_{y\sim x}\left(f(x)-f(y)\right)_{+}.$

Note that, since the function $(x,y)\mapsto f(x)-f(y)$ is centered under the
measure $(x,y)\mapsto\pi(x)P(x,y)$, the integral of its positive part equals
that of its negative part. This establishes the first claim, and the second is
obtained by replacing $f$ with $-f$. ∎

We will use the above lemma to prove the following lower-bound on the mixing
time.

######  Lemma 3 (Diameter lower-bound).

For any lazy chain $P$, we have ${\rm
t}_{\textsc{mix}}^{\sharp}\geq\mathrm{diam}^{\sharp}-\frac{4}{\Phi}$.

###### Proof.

Let us first note that for a lazy chain, Lemma 2 holds with the better
constant $2\Phi$ instead of $\Phi$ (just apply the lemma to the non-lazy chain
$2P-I$). Now, fix $x\in V$ and $t\in\mathbb{N}$, and write $B_{x}(t):=\\{y\in
V\colon\mathrm{dist}(x,y)\leq t\\}$. By definition,

$\displaystyle\|P^{t}(x,\cdot)-\pi\|_{\textsc{tv}}$ $\displaystyle=$
$\displaystyle\max_{A\subseteq V}|P^{t}(x,A)-\pi(A)|$ $\displaystyle\geq$
$\displaystyle 1-\pi\left(B_{x}(t)\right)$ $\displaystyle=$ $\displaystyle
1-{\mathbb{P}}\left(\mathrm{dist}(x,Y)\leq t\right),$

where $Y$ denotes a $\pi-$distributed random variable. Averaging over all
$x\in V$, we obtain

$\displaystyle d_{\textsc{tv}}^{\sharp}(t)$ $\displaystyle\geq$ $\displaystyle
1-{\mathbb{P}}\left(\mathrm{dist}(X,Y)\leq t\right),$

where $X$ is $\pi-$distributed and independent of $Y$. Thus, the claim follows
if we can show

$\displaystyle{\mathbb{P}}\left(\mathrm{dist}(X,Y)\leq\mathrm{diam}^{\sharp}-\frac{4}{\Phi}\right)$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}.$ (6)

Now, for fixed $x\in V$, the function $f\colon y\mapsto\mathrm{dist}(x,y)$
satisfies $f(z)\leq f(y)+1$ whenever $z\sim y$, by the triangle inequality.
Thus, Lemma 2 ensures that

$\displaystyle{\mathbb{P}}\left(\mathrm{dist}(X,Y)\leq{\mathbb{E}}[\mathrm{dist}(X,Y)|X]-\frac{2}{\Phi}\right)$
$\displaystyle\leq$ $\displaystyle\frac{1}{4}.$

On the other hand, by the triangle inequality again, the function $f\colon
x\mapsto{\mathbb{E}}[\mathrm{dist}(x,Y)]$ satisfies $f(x)\leq f(y)+1$ whenever
$y\sim x$, and $\pi
f={\mathbb{E}}[\mathrm{dist}(X,Y)]=\mathrm{diam}^{\sharp}$. Thus, Lemma 2
yields

$\displaystyle{\mathbb{P}}\left({\mathbb{E}}[\mathrm{dist}(X,Y)|X]\leq\mathrm{diam}^{\sharp}-\frac{2}{\Phi}\right)$
$\displaystyle\leq$ $\displaystyle\frac{1}{4}.$

Combining those two estimates readily yields (6). ∎

###### Proof of Corollary 3.

If $P$ is lazy and non-negatively curved, then Corollary 2 and Lemma 3 give

$\displaystyle\mathrm{diam}^{\sharp}$ $\displaystyle\leq$
$\displaystyle\frac{40}{\Phi^{2}P_{\mathrm{min}}}+\frac{4}{\Phi}\ \leq\
\frac{41}{\Phi^{2}P_{\mathrm{min}}},$

because $P_{\mathrm{min}},\Phi\leq\frac{1}{2}$. If $P$ is not lazy, we apply
the above result to $(P+I)/2$. The latter is still non-negatively curved, but
its conductance and minimal entry are half those of $P$, so we loose a factor
of $8$ and obtain

$\displaystyle\mathrm{diam}^{\sharp}$ $\displaystyle\leq$
$\displaystyle\frac{328}{\Phi^{2}P_{\mathrm{min}}}.$

This readily implies the claim, because $\sqrt{328}<19$. ∎

###  3.3 Diffusive total-variation decay

In this section, we prove Theorem 4. Fix two distinct states $x\neq y\in V$,
and recall that

$\displaystyle W\left(P(x,\cdot),P(y,\cdot)\right)$ $\displaystyle=$
$\displaystyle\inf_{\chi}\left\\{\sum_{u,v\in
V}\chi(u,v)\,\mathrm{dist}(u,v)\right\\},$

where the infimum runs over all probability distributions
$\chi\in\mathcal{P}(V^{2})$ with marginals $P(x,\cdot)$ and $P(y,\cdot)$.
Minimizers are called optimal couplings. As in [4, 19], our first task
consists in showing that they can be chosen so as to assign a “decent”
probability to the “good” set

$\displaystyle\Gamma$ $\displaystyle:=$ $\displaystyle\left\\{(u,v)\in
V^{2}\colon\mathrm{dist}(u,v)<\mathrm{dist}(x,y)\right\\}.$

######  Lemma 4 (Good optimal couplings).

If $P$ is lazy and $x\neq y$, then there is an optimal coupling $\chi$ of
$P(x,\cdot),P(y,\cdot)$ such that $\chi\left(\Gamma\right)\geq
P_{\mathrm{min}}.$

###### Proof.

By compactness, we can find an optimal coupling $\chi$ which, among all
optimal couplings, maximizes $\chi(\Gamma)$. Suppose for a contradiction that
this “doubly optimal” coupling satisfies
$\chi\left(\Gamma\right)<P_{\mathrm{min}}$. The set ${A}:=\\{u\sim
x\colon(u,y)\in\Gamma\\}$ is not empty, since it contains the first vertex on
a geodesic from $x$ to $y$. Thus, $\chi(A\times V)=P(x,A)\geq
P_{\mathrm{min}}>\chi(\Gamma)$. This forces $\chi((A\times
V)\setminus\Gamma)>0$, i.e.

$\displaystyle\exists(x_{0},y_{0})\in(A\times
V)\setminus\Gamma,\quad\chi(x_{0},y_{0})$ $\displaystyle\geq$
$\displaystyle\varepsilon,$ (7)

for some $\varepsilon>0$. On the other hand, we have
$\chi(A\times\\{y\\})+\chi(A^{c}\times\\{y\\})=P(y,y)\ \geq\ \frac{1}{2}.$
This forces $\chi(A^{c}\times\\{y\\})>0$, because
$\chi(A\times\\{y\\})\leq\chi(\Gamma)<P_{\mathrm{min}}\leq\frac{1}{2}$. In
other words,

$\displaystyle\exists x_{1}\in A^{c},\quad\chi(x_{1},y)$ $\displaystyle\geq$
$\displaystyle\varepsilon,$ (8)

provided $\varepsilon>0$ is chosen small enough. We now use the vertices
$x_{0},y_{0},x_{1}$ found at (7)-(8) to construct a new coupling
$\widetilde{\chi}$ which contradicts the optimality of $\chi$. For all
$(u,v)\in V^{2}$, we set

$\displaystyle\widetilde{\chi}(u,v)$ $\displaystyle:=$
$\displaystyle\left\\{\begin{array}[]{ll}\chi(u,v)&\textrm{ if
}u\notin\\{x_{0},x_{1}\\}\textrm{ and }b\notin\\{y_{0},y\\};\\\
\chi(u,v)-\varepsilon&\textrm{ if }(u,v)=(x_{0},y_{0})\textrm{ or
}(u,v)=(x_{1},y);\\\ \chi(u,v)+\varepsilon&\textrm{ if
}(u,v)=(x_{0},y)\textrm{ or }(u,v)=(x_{1},y_{0}).\end{array}\right.$

By construction, $\widetilde{\chi}$ is non-negative and has the same marginals
as $\chi$. Thus, it is a coupling of $P(x,\cdot)$ and $P(y,\cdot)$. This
coupling is moreover optimal, since

$\displaystyle\sum_{u,v\in
V}\mathrm{dist}(u,v)\left(\widetilde{\chi}(u,v)-\chi(u,v)\right)$
$\displaystyle=$
$\displaystyle\varepsilon\left(\mathrm{dist}(x_{0},y)+\mathrm{dist}(x_{1},y_{0})-\mathrm{dist}(x_{0},y_{0})-\mathrm{dist}(x_{1},y)\right)$
$\displaystyle\leq$
$\displaystyle\varepsilon\left(\mathrm{dist}(x,y)-1+\mathrm{dist}(x_{1},y_{0})-\mathrm{dist}(x,y)-\mathrm{dist}(x_{1},y)\right)$
$\displaystyle\leq$ $\displaystyle 0,$

where we have successively used $x_{0}\in A$, $(x_{0},y_{0})\notin\Gamma$, and
the triangle inequality
$\mathrm{dist}(x_{1},y_{0})\leq\mathrm{dist}(x_{1},y)+\mathrm{dist}(y,y_{0})$.
Finally, since $\Gamma$ contains $(x_{1},y)$ but not
$(x_{0},y_{0}),(x_{1},y)$, we have
$\widetilde{\chi}(\Gamma)\geq\chi(\Gamma)+\varepsilon,$ contradicting the
double optimality of $\chi$. ∎

Our second ingredient is a diffusive hitting-time estimate for super-
martingales. Results of this sort are standard, but usually require a uniform
bound on the increments, a property which fails in our directed setting
($\mathrm{dist}(x,x^{\prime})=\mathrm{dist}(y,y^{\prime})=1$ no longer implies
$\mathrm{dist}(x^{\prime},y^{\prime})\leq\mathrm{dist}(x,y)+2$).

######  Lemma 5 (Hitting-time estimate).

Let $(Z_{t})_{t\geq 0}$ be a discrete-time, $\mathbb{N}-$valued super-
martingale with $Z_{0}=z_{0}\in\mathbb{N}$, and set $\tau:=\min\\{t\geq
0\colon Z_{t}=0\\}$. Assume that almost-surely,

$\displaystyle{\mathbb{P}}\left(Z_{t+1}\neq Z_{t}|\mathcal{F}_{t}\right)$
$\displaystyle\geq$ $\displaystyle p{\bf 1}_{(\tau>t)},$

for all $t\geq 0$, where $(\mathcal{F}_{t})_{t\geq 0}$ denotes the underlying
filtration. Then, for all $t\geq 1$, we have

$\displaystyle{\mathbb{P}}(\tau\geq t)$ $\displaystyle\leq$ $\displaystyle
z_{0}\sqrt{\frac{10}{pt}}.$

###### Proof.

Our starting point is the following easily verified inequality: for all
$x\in\mathbb{R}$,

$\displaystyle e^{-\frac{x}{2}}$ $\displaystyle\geq$ $\displaystyle
1-\frac{x}{2}+\frac{1\wedge x^{2}}{10}.$

In particular, for all $t\in\mathbb{N}$ and $\lambda\in[0,1]$, we have on the
event $\\{\tau>t\\}$,

$\displaystyle{\mathbb{E}}\left[e^{-\frac{\lambda}{2}(Z_{t+1}-Z_{t})}|\mathcal{F}_{t}\right]$
$\displaystyle\geq$
$\displaystyle{\mathbb{E}}\left[\left.1-\frac{\lambda}{2}(Z_{t+1}-Z_{t})+\frac{1\wedge(\lambda
Z_{t+1}-\lambda Z_{t})^{2}}{10}\right|\mathcal{F}_{t}\right]$
$\displaystyle\geq$ $\displaystyle 1+\frac{p\lambda^{2}}{10}.$

where the second line uses our assumptions on $Z$. It follows by induction
that for all $t\in\mathbb{N}$,

$\displaystyle{\mathbb{E}}\left[e^{-\frac{\lambda}{2}(Z_{t\wedge\tau}-Z_{0})}\left(1+\frac{p\lambda^{2}}{10}\right)^{-t\wedge\tau}\right]$
$\displaystyle\geq$ $\displaystyle 1.$

Since $Z_{t\wedge\tau}-Z_{0}\geq-Z_{0}=-z_{0}$, we deduce that

$\displaystyle{\mathbb{E}}\left[\left(1+\frac{p\lambda^{2}}{10}\right)^{-t\wedge\tau}\right]$
$\displaystyle\geq$ $\displaystyle e^{-\frac{\lambda z_{0}}{2}}\ \geq\
1-\frac{\lambda z_{0}}{2}.$

In particular,

$\displaystyle{\lambda z_{0}}$ $\displaystyle\geq$ $\displaystyle
2{\mathbb{E}}\left[1-\left(1+\frac{p\lambda^{2}}{10}\right)^{-t\wedge\tau}\right]$
$\displaystyle\geq$ $\displaystyle
2\left(1-\left(1+\frac{p\lambda^{2}}{10}\right)^{-t}\right){\mathbb{P}}(\tau\geq
t)$ $\displaystyle\geq$ $\displaystyle
2\left(1-\left(1+\frac{pt\lambda^{2}}{10}\right)^{-1}\right){\mathbb{P}}(\tau\geq
t).$

The result now readily follows by choosing $\lambda=\sqrt{10/pt}$. Note that
this choice satisfies $\lambda\in[0,1]$ only when $10/pt\leq 1$, but the
conclusion trivially holds when $10/pt>1$. ∎

###### Proof of Theorem 4.

For each $(x,y)\in V$, let $\chi_{x,y}$ denote an optimal coupling of
$P(x,\cdot)$ and $P(y,\cdot)$ satisfying the condition in Lemma 4, and let us
define a transition matrix $K$ on $V^{2}$ by

$\displaystyle K((x,y),(u,v))$ $\displaystyle:=$
$\displaystyle\chi_{x,y}(u,v).$

Finally, consider a Markov chain $(X_{t},Y_{t})_{t\geq 0}$ with transition
matrix $K$, and let us use the notation ${\mathbb{E}}_{(x,y)}[\cdot]$ to
indicate that $(X_{0},Y_{0})=(x,y)$. By construction, we have for all $x,y\in
V$,

$\displaystyle{\mathbb{E}}_{(x,y)}[\mathrm{dist}(X_{1},Y_{1})]$
$\displaystyle=$ $\displaystyle W\left(P(x,\cdot),P(y,\cdot)\right)\ \leq\
\mathrm{dist}(x,y);$
$\displaystyle{\mathbb{P}}_{(x,y)}[\mathrm{dist}(X_{1},Y_{1})<\mathrm{dist}(x,y)]$
$\displaystyle\geq$ $\displaystyle P_{\mathrm{min}}{\bf 1}_{(x\neq y)}.$

By the Markov property, the first condition implies that the process
$Z:=(Z_{t})_{t\geq 0}$ defined by $Z_{t}:=\mathrm{dist}(X_{t},Y_{t})$ is a
super-martingale w.r.t. the natural filtration $(\mathcal{F}_{t})_{t\geq 0}$
of $(X_{t},Y_{t})_{t\geq 0}$, and the second implies that
${\mathbb{P}}(Z_{t+1}\neq Z_{t}|\mathcal{F}_{t})\geq P_{\mathrm{min}}{\bf
1}_{Z_{t}\neq 0}$. Thus, Lemma 5 applies and yields

$\displaystyle{\mathbb{P}}_{x,y}(X_{t}\neq Y_{t})$ $\displaystyle\leq$
$\displaystyle\mathrm{dist}(x,y)\sqrt{\frac{10}{(t+1)P_{\mathrm{min}}}}.$

The result follows, since under ${\mathbb{P}}_{(x,y)}(\cdot)$, the pair
$(X_{t},Y_{t})$ is a coupling of $P^{t}(x,\cdot)$ and $P^{t}(y,\cdot)$. ∎

## References

  * [1] Noga Alon and Yuval Roichman.  Random Cayley graphs and expanders.  Random Structures Algorithms, 5(2):271–284, 1994.
  * [2] Frank Bauer, Paul Horn, Yong Lin, Gabor Lippner, Dan Mangoubi, Shing-Tung Yau, et al.  Li-yau inequality on graphs.  Journal of Differential Geometry, 99(3):359–405, 2015.
  * [3] Nathanaël Berestycki and BatıŞengül.  Cutoff for conjugacy-invariant random walks on the permutation group.  Probab. Theory Related Fields, 173(3-4):1197–1241, 2019.
  * [4] Magnus Bordewich and Martin Dyer.  Path coupling without contraction.  J. Discrete Algorithms, 5(2):280–292, 2007.
  * [5] Emmanuel Breuillard and Matthew C. H. Tointon.  Nilprogressions and groups with moderate growth.  Adv. Math., 289:1008–1055, 2016.
  * [6] P. Diaconis and L. Saloff-Coste.  Moderate growth and random walk on finite groups.  Geom. Funct. Anal., 4(1):1–36, 1994.
  * [7] Persi Diaconis.  The cutoff phenomenon in finite Markov chains.  Proc. Nat. Acad. Sci. U.S.A., 93(4):1659–1664, 1996.
  * [8] Marzieh Eidi and Jürgen Jost.  Ollivier ricci curvature of directed hypergraphs.  Scientific Reports, 10(1):1–14, 2020.
  * [9] Matthias Erbar and Jan Maas.  Ricci curvature of finite Markov chains via convexity of the entropy.  Archive for Rational Mechanics and Analysis, pages 1–42, 2012.
  * [10] Robin Forman.  Bochner’s method for cell complexes and combinatorial ricci curvature.  Discrete and Computational Geometry, 29(3):323–374, 2003.
  * [11] J. Jost.  Riemannian geometry and geometric analysis.  Springer, 72017\.
  * [12] Jürgen Jost and Florentin Münch.  Characterizations of forman curvature.  arXiv preprint arXiv:2110.04554, 2021.
  * [13] James R. Lee and Yuval Peres.  Harmonic maps on amenable groups and a diffusive lower bound for random walks.  Ann. Probab., 41(5):3392–3419, 2013.
  * [14] David A. Levin and Yuval Peres.  Markov chains and mixing times.  American Mathematical Society, Providence, RI, 2017.  Second edition of [ MR2466937], With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  * [15] Yong Lin and Shuang Liu.  Equivalent properties of CD inequality on graph.  arXiv preprint arXiv:1512.02677, 2015.
  * [16] Yong Lin and Shing-Tung Yau.  Ricci curvature and eigenvalue estimate on locally finite graphs.  Mathematical research letters, 17(2):343–356, 2010.
  * [17] Ravi Montenegro and Prasad Tetali.  Mathematical aspects of mixing times in Markov chains.  Found. Trends Theor. Comput. Sci., 1(3):x+121, 2006.
  * [18] Florentin Münch.  Li-Yau inequality under $CD(0,n)$ on graphs.  arXiv preprint arXiv:1909.10242, 2019.
  * [19] Florentin Münch.  Non-negative Ollivier curvature on graphs, reverse Poincaré inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates.  arXiv preprint arXiv:1907.13514, 2019.
  * [20] Florentin Münch and Radosław K Wojciechowski.  Ollivier Ricci curvature for general graph Laplacians: Heat equation, Laplacian comparison, non-explosion and diameter bounds.  Advances in Mathematics, 356:106759, 2019.
  * [21] Laurent Najman and Pascal Romon.  Modern approaches to discrete curvature.  Lecture Notes in Mathematics, Springer, Berlin, 2017.
  * [22] Yann Ollivier.  A survey of Ricci curvature for metric spaces and Markov chains, volume 57 of Adv. Stud. Pure Math. Math. Soc. Japan, Tokyo.
  * [23] Yann Ollivier.  Ricci curvature of Markov chains on metric spaces.  Journal of Functional Analysis, 256(3):810–864, 2009.
  * [24] Ryunosuke Ozawa, Yohei Sakurai, and Taiki Yamada.  Geometric and spectral properties of directed graphs under a lower Ricci curvature bound.  Calculus of Variations and Partial Differential Equations, 59(4):1–39, 2020.
  * [25] Ryunosuke Ozawa, Yohei Sakurai, and Taiki Yamada.  Heat flow and concentration of measure on directed graphs with a lower Ricci curvature bound.  Potential Analysis, pages 1–15, 2022.
  * [26] Justin Salez.  Cutoff for non-negatively curved Markov chains.  arXiv preprint arXiv:2102.05597, 2021.
  * [27] Justin Salez.  Sparse expanders have negative curvature.  arXiv preprint arXiv:2101.08242, 2021.
  * [28] Michael Schmuckenschläger.  Curvature of nonlocal Markov generators.  Convex geometric analysis (Berkeley, CA, 1996), 34:189–197, 1998\.
  * [29] Romain Tessera and Matthew C. H. Tointon.  A finitary structure theorem for vertex-transitive graphs of polynomial growth.  Combinatorica, 41(2):263–298, 2021.
  * [30] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer, 2009.
  * [31] Taiki Yamada.  The Ricci curvature on directed graphs.  arXiv preprint arXiv:1602.07779, 2016.