\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools,microtype,needspace}
\usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry}
\usepackage{xcolor}
\usepackage{hyperref}
\hypersetup{pdftitle={Stationary diffusion on nonnegatively curved graphs},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}\newtheorem{remark}[theorem]{Remark}
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\Ent}{H}
\newcommand{\E}{\mathbb E}\newcommand{\Pp}{\mathbb P}
\newcommand{\N}{\mathbb N}\newcommand{\M}{\mathcal M}
\title{Stationary diffusion on nonnegatively curved graphs\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}}
\author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em]
Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k}\date{}

% Collection typography.
\definecolor{BolzanoInk}{HTML}{24445C}
\hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk,
  urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}}
\urlstyle{same}
\setlength{\emergencystretch}{1em}
\let\BolzanoBibliography\thebibliography
\renewcommand{\thebibliography}[1]{\Needspace{30\baselineskip}\BolzanoBibliography{#1}\small\raggedright}
\begin{document}\maketitle
\begin{abstract}
Lazy random walk on a bounded-degree graph of nonnegative
Ollivier--Ricci curvature has diffusive second moment and Gaussian
upper tails when started in stationarity. If the maximum degree is
$D$, then $\E d(X_0,X_n)^2\le4Dn$, with optimal order of dependence
on $D$. The results also hold for stationary random rooted infinite
graphs. The proof combines known heat-kernel total-variation decay
with a reversible energy identity for the conditional mean
displacement. Its exponential form controls variation between starting
vertices; martingale concentration then controls the walk itself.
\end{abstract}

\section{Introduction}
\subsection{Background and the source problem}
A lazy random walk on a cycle travels an expected distance of at most
$\sqrt{n/2}$ in $n$ steps, independently of the length of the cycle.
Indeed, lift the walk to the integers: its increments have mean zero
and variance $1/2$, so Cauchy--Schwarz bounds its expected absolute
position by $\sqrt{n/2}$, and projection to the cycle can only decrease
distance. On an infinite regular tree of degree at least three, the
excess of outward directions instead creates a positive drift away
from the starting vertex. Bounded degree by itself therefore does not
force diffusive motion. A geometric condition is needed.

Ollivier--Ricci curvature measures how the local geometry affects two
nearby walks. Run one lazy step from each of two neighboring vertices.
The curvature is nonnegative if the steps can be chosen dependently,
while preserving each walk's transition law, so that their expected
distance is at most one. Such a joint choice is called a coupling.
Iterating these couplings keeps the expected separation from increasing.
This discrete transport formulation of curvature was introduced by
Ollivier~\cite{Ollivier,OllivierSurvey}; it is related to path
coupling~\cite{BD} and to the graph-curvature definition of Lin, Lu
and Yau~\cite{LLY}. The condition compares \emph{two moving walks}.
It does not immediately bound either walk's distance from its fixed
starting point.

Throughout the paper, $G$ is a connected undirected graph, $d$ is graph
distance, and $P$ is the lazy random-walk kernel: with probability $1/2$
the walk stays put, and otherwise it follows a uniformly chosen incident
edge. Loops and multiple edges are permitted; the precise convention is
given in Section~\ref{sec:heat}. For probability measures $\rho,\sigma$,
let $W_1(\rho,\sigma)$ be the infimum of $\E d(U,V)$ over couplings
with these marginals.

\begin{definition}[Nonnegative curvature; {\cite[Introduction, condition~3]{BHM}}]
The graph has nonnegative Ollivier--Ricci curvature if
\begin{equation}\label{eq:curvature}
 W_1(P(x,\cdot),P(y,\cdot))\le1\qquad(x\sim y).
\end{equation}
\end{definition}

A second ingredient is the choice of starting vertex. On a finite graph
with an edge, the stationary probability is
$\pi(x)=\deg(x)/\sum_v\deg(v)$. This is the distribution seen at any fixed
time by a walk in equilibrium; on a regular graph it is uniform.
Expectations with subscript $\pi$ average both this starting vertex and
the subsequent walk. A bound uniform in the size of the graph is much
stronger than the trivial bound by its diameter.

Salez~\cite{Salez} established sublinear stationary displacement under
nonnegative curvature and a bounded-degree assumption. Brena, Hutchcroft
and M\"unch~\cite[Introduction, p.~3]{BHM} ask whether the square-root
scale suggested by Brownian motion on manifolds of nonnegative Ricci
curvature holds in this setting. Their stationary question can be
formulated as follows.

\begin{conjecture}[Stationary first-moment question from {\cite{BHM}}]\label{conj:source}
For each $D$, there is a constant $C(D)$ such that every finite graph of
maximum degree at most $D$ satisfying~\eqref{eq:curvature} obeys
$\E_\pi d(X_0,X_n)\le C(D)\sqrt n$ for every $n\ge1$.
\end{conjecture}

The source proves a diffusive second-moment bound for transitive graphs,
where all vertices have the same rooted geometry, and an averaged
bound with a logarithmic loss for general finite
graphs~\cite[Corollary~1.2 and Theorem~1.3]{BHM}. Removing that loss
requires control of how displacement varies between starting vertices.
Concentration of a walk around its own conditional mean does not supply
such control when those means are different.

\subsection{Contribution}
The stationary question has an affirmative answer, with diffusive
moments of every order and a Gaussian upper tail. The quantitative
bounds below also apply without transitivity. The proof separates
fluctuations of the walk from variation between starting vertices.
A reversible energy identity controls the latter: the square of a
change in conditional mean absorbs a mixed distance term. Combined
with heat-kernel smoothing, this forces the diffusive scale.
\begin{enumerate}
\item Theorem~\ref{thm:finite} gives the finite-graph second-moment and
tail bounds. Proposition~\ref{prop:cube} shows that the factor $D$ in
the second moment has the correct order.
\item Theorem~\ref{thm:rooted} extends both estimates to stationary
random rooted graphs, including infinite graphs. Curvature supplies the
reversibility needed for this extension.
\item Proposition~\ref{prop:typical} bounds the conditional moments at
most roots simultaneously at all times, with only an iterated-logarithm
loss. The bound from every prescribed root with a constant depending
only on $D$ remains open.
\end{enumerate}

\begin{theorem}\label{thm:finite}
Let $G$ be a finite connected graph of maximum degree at most $D\ge1$
satisfying~\eqref{eq:curvature}, and start the lazy walk from $\pi$.
For every integer $n\ge1$,
\begin{equation}\label{eq:main-second}
 \E_\pi d(X_0,X_n)^2\le4Dn,
 \qquad \E_\pi d(X_0,X_n)\le2\sqrt{Dn}.
\end{equation}
Moreover, for every $u\ge0$,
\begin{equation}\label{eq:main-tail}
 \Pp_\pi\!\left(d(X_0,X_n)\ge\sqrt{Dn/2}+u\right)
 \le3\exp\!\left(-\frac{u^2}{8n}\right).
\end{equation}
A one-vertex graph is interpreted as an absorbing walk and has zero
displacement.
\end{theorem}

For the infinite version, stationarity concerns the graph as
\emph{viewed from the walk}. A random rooted graph $(G,o)$ has a
stationary law $\mu$ if moving its root from $o$ to $X_1$ does not
change its law. The integer lattice rooted at the origin is an example,
since its rerootings are isomorphic. Reversibility means that the
doubly rooted graphs $(G,o,X_1)$ and $(G,X_1,o)$ have the same law.

\begin{theorem}\label{thm:rooted}
Let $\mu$ be a stationary law on connected random rooted graphs of
maximum degree at most $D\ge1$. Suppose~\eqref{eq:curvature} holds almost
surely at every edge. Then $\mu$ is reversible, and
\eqref{eq:main-second}--\eqref{eq:main-tail} hold with expectations and
probabilities over $(G,o)\sim\mu$ and the walk started at $o$.
The graphs may be infinite.
\end{theorem}

The averaging is essential to these statements. In particular,
\eqref{eq:main-tail} is an \emph{annealed} bound: it averages both the
rooted graph and the walk. It is not a bound on deviations around the
conditional mean at each individually chosen root. The conjecture
$\E_x d(x,X_n)^2\le C(D)n$ from every vertex, stated separately
in~\cite[Remark~1.4]{BHM}, is not resolved here.

\subsection{The mechanism and related work}
The key step controls the distribution, over the root, of the
conditional mean displacement. To describe it, run the nonlazy walk
at rate one in continuous time, and set
$a_t(x)=\E_x d(x,Y_t)$. For a stationary reversible oriented edge $(x,y)$,
write $v=a_t(y)-a_t(x)$. Differentiating the stationary average of
$a_t^2$ produces a negative energy term $-v^2$. Reversing the initial
edge turns the remaining unbounded distance into
$d(x,z)-d(y,z)$, whose absolute value is at most one. The only mixed
term has the form $-vu$ with $|u|\le1$, and
$-v^2-vu\le1/4$. Thus variation between roots can be absorbed by the
energy rather than bounded separately. Applying the same identity to
$e^{\theta a_t}$ gives Gaussian control of those conditional means.
A heat martingale then handles fluctuations of the walk around its mean.

The heat-kernel input is established work.
M\"unch~\cite[Corollary~3.1.2, preprint numbering]{Munch} proves that
neighboring heat kernels approach each other in total variation at rate
$O(\sqrt{D/t})$. Salez~\cite[Section~3.2]{Salez} develops the coupling
method, and M\"unch and Salez~\cite[Theorem~4]{MS} give an explicit
finite discrete-time estimate. We use M\"unch's continuous-time form
because differentiation leaves no discrete Taylor remainder in the
energy identity. An independent coupling estimate needed for the
random-rooted reversibility argument is included in
Appendix~\ref{sec:coupling}.

Stationarity of a random rooted graph does not by itself imply
reversibility. Salez's zero-entropy theorem~\cite[Theorem~11]{Salez}
and the entropy theory of Benjamini and
Curien~\cite[Proposition~3.6 and Theorem~4.4]{BC} supply the relevant
principle. Appendix~\ref{app:reversibility} gives the required
entropy-production argument, counting vertices with their multiplicities
under graph isomorphisms. This principle and the heat-kernel estimate
are background ingredients; the reversible squared and exponential
energy estimates are the displacement mechanism used here.

For general finite graphs, the uniformly averaged second moment
in~\cite[Theorem~1.3]{BHM} is bounded by
$C(D)n(\log n)^{3/2}$. Since the uniform vertex measure is at most
$D\pi$, Theorem~\ref{thm:finite} also gives a uniform-vertex bound
$4D^2n$, removing this logarithmic loss. Zhou's pointwise
estimate~\cite[Theorem~2.1 and Corollary~2.2]{Zhou} retains a
subpolynomial loss in time; it applies to every vertex, a stronger
quantifier than stationary averaging. Hutchcroft and
Lopez~\cite[Theorem~2.1]{HL} give upper tails relative to the
\emph{supremum} of the expected displacement over all starting vertices.
A stationary mean does not control that supremum, so their theorem does
not directly give~\eqref{eq:main-tail}.

Transition-probability bounds such as the Carne--Varopoulos
estimate~\cite{Carne} do not alone settle the question, since a graph
may have many vertices at a given distance. Diffusive lower bounds,
such as those of Lee and Peres~\cite{LP13} and M\"unch and
Salez~\cite[Theorem~3 and Corollary~5]{MS}, address the complementary
question of slow escape. In the transitive setting the polynomial-growth
theorem of~\cite{BHM} and the rigidity theorem of Brena and
Bru\`e~\cite[Theorem~1.9]{BB} give stronger geometric information.
The proof below obtains stationary diffusion directly, without a
geometric classification.

\section{Heat evolution and stationary edge reversal}\label{sec:heat}
Let $a(x,y)$ count oriented edges from $x$ to $y$, with each loop
contributing two orientations, and put $\deg(x)=\sum_y a(x,y)$.
On a graph with at least two vertices define
\[
 R(x,y)=\frac{a(x,y)}{\deg(x)},\qquad
 P=\frac{I+R}{2},\qquad L=R-I,\qquad S_t=e^{tL}.
\]
Thus $R$ is the nonlazy kernel, $P$ is the discrete kernel in the main
theorems, and $S_t$ is the heat semigroup of a rate-one Poissonization
of $R$. A loop may produce a zero-distance step. On each fixed graph,
degree measure is reversible for all these kernels.

Condition~\eqref{eq:curvature}, the triangle inequality for $W_1$ along
a geodesic, and composition of couplings imply
$W_1(P^n(x,\cdot),P^n(y,\cdot))\le d(x,y)$. Hence $P^n$ preserves
$1$-Lipschitz functions. The identity
$S_t=e^{2t(P-I)}$ expresses $S_t$ as a Poisson mixture of these powers,
so it also preserves $1$-Lipschitz functions.

\begin{lemma}[Heat-kernel input]\label{lem:heat-tv}
For every $t>0$ and neighboring vertices $x,y$,
\begin{equation}\label{eq:heat-tv}
 \|S_t(x,\cdot)-S_t(y,\cdot)\|_{\TV}
 \le\varepsilon_t:=\min\left\{1,\frac{\sqrt D}{2\sqrt t}\right\},
 \qquad
 \|\rho-\sigma\|_{\TV}=\frac12\sum_z|\rho(z)-\sigma(z)|.
\end{equation}
\end{lemma}
\begin{proof}
Apply~\cite[Theorem~2.5.1 and Corollary~3.1.2]{Munch} to the jump rates
$q(x,y)=R(x,y)$ for $x\ne y$, with $q(x,x)=0$. These rates are reversible
with respect to degree measure, and every positive rate is at least
$1/D$. The source allows countable locally finite graphs. Here total
jump rates are at most one, so the heat process is nonexplosive.
Its infinitesimal curvature condition follows from
\eqref{eq:curvature}: if $f$ is $1$-Lipschitz and $f(y)-f(x)=1$ on an
edge, then $Pf(y)-Pf(x)\le1$ gives $Lf(y)-Lf(x)\le0$.
The cited result bounds the $\ell^1$ distance of heat rows by
$d(x,y)/\sqrt{tq_{\min}}$. Our total variation is half that distance.
The bound by one completes~\eqref{eq:heat-tv}.
\end{proof}

For the rest of the main proof, write $\mu$ for a stationary reversible
root law, including the finite law $\pi$. In the setting of
Theorem~\ref{thm:rooted}, Lemmas~\ref{lem:entropy} and~\ref{lem:reversal}
in Appendix~\ref{app:reversibility} establish these properties before
any displacement estimate is used. Stationarity and reversibility for
$P$ imply both properties for $R$, by subtracting the diagonal part of
$P=(I+R)/2$. Write $\E_e$ for the expectation over the oriented
$R$-edge: first sample $(G,x)\sim\mu$, then $y\sim R_G(x,\cdot)$.
Its two root marginals are $\mu$, and its law is invariant under
$(x,y)\mapsto(y,x)$. Graph arguments will be suppressed in the formulas.

Define
\begin{equation}\label{eq:heat-means}
 a_t(x)=\sum_z S_t(x,z)d(x,z),\qquad
 B(t)=\int_0^t\varepsilon_s\,ds\le\sqrt{Dt}.
\end{equation}
The last inequality follows by integrating
$\varepsilon_s\le\sqrt D/(2\sqrt s)$. The Poisson step count gives
$0\le a_t(x)\le t$, uniformly in the graph and root.

\begin{lemma}[Reversible energy identity]\label{lem:energy}
Fix $t\ge0$. For an oriented edge put
\[
 a=a_t(x),\quad b=a_t(y),\quad v=b-a,\quad
 g(z)=d(x,z)-d(y,z),\quad \nu_x=S_t(x,\cdot),\quad u=\nu_x(g).
\]
Then $|g|\le1$ and $|u|\le1$. For a continuously differentiable
function $\phi$ on $[0,\infty)$,
\begin{equation}\label{eq:energy}
 \frac{d}{dt}\E_\mu\phi(a_t)
 =\frac12\E_e\left[
 \phi'(a)(\nu_y-\nu_x)(g)
 -(\phi'(b)-\phi'(a))(v+u)\right].
\end{equation}
\end{lemma}
\begin{proof}
The backward heat equation, applied with the starting vertex fixed,
gives
\begin{equation}\label{eq:mean-evolution}
 a_t'(x)=La_t(x)+\beta_t(x),\qquad
 \beta_t(x)=\sum_yR(x,y)S_t(y,\cdot)\bigl(d(x,\cdot)-d(y,\cdot)\bigr).
\end{equation}
Indeed, expanding $La_t(x)+\beta_t(x)$ cancels the terms involving
$d(y,z)$ and leaves
\[
 \sum_{y,z}R(x,y)S_t(y,z)d(x,z)-a_t(x).
\]
For unbounded distance, write
$a_t(x)=e^{-t}\sum_{k\ge0}t^kr_k(x)/k!$, where
$r_k(x)=\E_x d(x,Z_k)$ for the $R$-walk. Since $0\le r_k\le k$,
this series may be differentiated uniformly on bounded time intervals.
Coupling successive endpoints on the same walk gives
$|r_{k+1}-r_k|\le1$, hence $|a_t'(x)|\le1$.
These bounds justify both the heat equation and differentiation under
$\E_\mu$.

Edge reversal gives the two identities
\begin{align*}
 \E_\mu\phi'(a_t)La_t
 &=-\frac12\E_e[(\phi'(b)-\phi'(a))v],\\
 \E_\mu\phi'(a_t)\beta_t
 &=\frac12\E_e[\phi'(a)\nu_y(g)-\phi'(b)\nu_x(g)]\\
 &=\frac12\E_e[\phi'(a)(\nu_y-\nu_x)(g)
                  -(\phi'(b)-\phi'(a))u].
\end{align*}
Their sum is~\eqref{eq:energy}. All quantities are integrable:
$a_t\le t$, and $g,u$ are bounded. The same calculation is valid with
expectation over a random rooted graph, since it uses only the symmetry
and marginals of the oriented edge law.
\end{proof}

\section{Diffusive second moments}\label{sec:second}
\begin{proposition}\label{prop:heat-second}
For the rate-one heat walk from a stationary reversible root,
\begin{equation}\label{eq:heat-second}
 \E_\mu a_t\le B(t),\qquad
 \E_\mu a_t^2\le B(t)^2+\frac t4,\qquad
 \E_\mu d(Y_0,Y_t)^2\le\left(D+\frac54\right)t.
\end{equation}
\end{proposition}
\begin{proof}
Apply Lemma~\ref{lem:energy} first to $\phi(a)=a$. Since
$|(\nu_y-\nu_x)(g)|\le2\varepsilon_t$, it gives
$|\frac{d}{dt}\E_\mu a_t|\le\varepsilon_t$.
The mean starts at zero, proving the first bound.

Next let $A(t)=\E_\mu a_t^2$ and take $\phi(a)=a^2$ in the same identity:
\begin{equation}\label{eq:squared-energy}
 A'(t)=\E_e[a(\nu_y-\nu_x)(g)-v^2-vu].
\end{equation}
The first term is at most $2\varepsilon_t\E_\mu a_t$; the remaining
terms satisfy
\[
 -v^2-vu=-(v+u/2)^2+u^2/4\le\frac14.
\]
Consequently $A'(t)\le2\varepsilon_t B(t)+1/4
=(B(t)^2)'+1/4$. Integrating from zero proves the second bound.

For the last bound, fix a root $x$ and set $f(z)=d(x,z)$.
The backward heat martingale
$M_s=S_{t-s}f(Y_s)$, $0\le s\le t$, has jumps of absolute value at
most one, because $S_{t-s}f$ is $1$-Lipschitz. Its predictable quadratic
variation has rate
\[
 \sum_yR(Y_s,y)
  \bigl(S_{t-s}f(y)-S_{t-s}f(Y_s)\bigr)^2\le1.
\]
Therefore $\operatorname{Var}_x d(x,Y_t)\le t$.
One can first use $f\wedge K$ and then let $K\to\infty$; the Poisson
step count has finite second moment and dominates the distance.
Averaging the conditional variance identity gives
\[
 \E_\mu d(Y_0,Y_t)^2\le A(t)+t
 \le B(t)^2+\frac{5t}{4}\le\left(D+\frac54\right)t.
\]
\end{proof}

\begin{proof}[Proof of the moment bounds in Theorems~\ref{thm:finite} and~\ref{thm:rooted}]
Use one nonlazy $R$-walk $(Z_j)_{j\ge0}$ from the stationary root.
Independently of the walk and of one another, choose
$K\sim\operatorname{Bin}(n,1/2)$ and $N\sim\operatorname{Pois}(n/2)$.
Then $Z_K$ has the $P^n$ law and $Z_N$ has the $S_{n/2}$ law. Pathwise,
\begin{equation}\label{eq:clock-distance}
 d(Z_0,Z_K)\le d(Z_0,Z_N)+|K-N|.
\end{equation}
Both clocks have mean $n/2$, and
$\E(K-N)^2=n/4+n/2=3n/4$. Using $(r+s)^2\le2r^2+2s^2$ and
Proposition~\ref{prop:heat-second} yields
\[
 \E_\mu d(X_0,X_n)^2
 \le2\left(D+\frac54\right)\frac n2+2\frac{3n}{4}
 =\left(D+\frac{11}{4}\right)n\le4Dn.
\]
Cauchy--Schwarz gives the first moment. Finite stationary walks are
reversible by degree detailed balance; the random-rooted case uses
Appendix~\ref{app:reversibility}, as explained above. Restoring any mass
on a one-vertex graph contributes zero displacement.
\end{proof}

\section{Exponential energy and Gaussian tails}\label{sec:tails}
\begin{proposition}\label{prop:mean-mgf}
For every $t\ge0$ and $\theta\ge0$,
\begin{equation}\label{eq:mean-mgf}
 \E_\mu e^{\theta a_t}
 \le\exp\!\left(\theta B(t)+\frac{\theta^2t}{8}\right).
\end{equation}
In particular,
$\mu\{a_t\ge B(t)+u\}\le e^{-2u^2/t}$ for $t>0$ and $u\ge0$.
\end{proposition}
\begin{proof}
Set $\phi(a)=e^{\theta a}$ and $F(t)=\E_\mu\phi(a_t)$.
The first term of~\eqref{eq:energy} is bounded above by
$\theta\varepsilon_t F(t)$. Define, including when $a=b$,
\[
 h(a,b)=\theta^2\int_0^1 e^{\theta((1-s)a+sb)}\,ds.
\]
Then $\phi'(b)-\phi'(a)=h(a,b)v$, and convexity of the exponential gives
$0\le h(a,b)\le\theta^2(\phi(a)+\phi(b))/2$. Completing the square,
\[
 -\frac12h(a,b)(v^2+vu)\le\frac18h(a,b)u^2.
\]
Its edge expectation is at most $\theta^2F(t)/8$, because $|u|\le1$
and both edge marginals are $\mu$. Hence
$F'(t)\le(\theta\varepsilon_t+\theta^2/8)F(t)$.
Integration with $F(0)=1$ proves~\eqref{eq:mean-mgf}.
Markov's inequality with $\theta=4u/t$ proves the tail assertion.
\end{proof}

\begin{lemma}[Fluctuations at a fixed root]\label{lem:heat-mgf}
For every fixed rooted graph satisfying~\eqref{eq:curvature},
$t\ge0$, and $\theta\ge0$,
\begin{equation}\label{eq:heat-mgf-conditional}
 \E_x\exp\{\theta(d(x,Y_t)-a_t(x))\}
 \le\exp\{t(e^\theta-1-\theta)\}.
\end{equation}
\end{lemma}
\begin{proof}
Use the backward heat martingale from the proof of
Proposition~\ref{prop:heat-second}, first with bounded terminal function
$f\wedge K$. Each possible jump $w$ lies in $[-1,1]$, and
\[
 e^{\theta w}-1-\theta w\le(e^\theta-1-\theta)w^2.
\]
For $w\ge0$ this follows term by term from the exponential series.
For $w<0$ the integral Taylor remainder is at most $\theta^2w^2/2$,
which is bounded by the right-hand side. To make the exponential estimate explicit, write
$H_s=S_{t-s}(f\wedge K)$ and $w_y=H_s(y)-H_s(x)$. The backward equation
$\partial_s H_s=-LH_s$ gives
\[
 (\partial_s+L)e^{\theta H_s}(x)
 =e^{\theta H_s(x)}\sum_y R(x,y)
       \bigl(e^{\theta w_y}-1-\theta w_y\bigr)
 \le(e^\theta-1-\theta)e^{\theta H_s(x)}.
\]
Take expectations along $Y_s$ and integrate this differential inequality
from $0$ to $t$. Since $H_0(x)=S_t(f\wedge K)(x)$, the result is
\eqref{eq:heat-mgf-conditional} for $f\wedge K$.
Let $K\to\infty$. The terminal distance is dominated by the Poisson
step count, which has every exponential moment, so dominated convergence
proves the claimed formula.
\end{proof}

Combining the conditional bound with Proposition~\ref{prop:mean-mgf}
gives
\begin{equation}\label{eq:heat-mgf}
 \E_\mu e^{\theta d(Y_0,Y_t)}
 \le\exp\!\left\{\theta B(t)
       +t\left(\frac{\theta^2}{8}+e^\theta-1-\theta\right)\right\}.
\end{equation}
For $0\le\theta\le1$, the exponential series yields
$e^\theta-1-\theta\le(e-2)\theta^2$, and $1/8+e-2<1$.
Chernoff's bound with $\theta=v/(2t)$ consequently gives
\begin{equation}\label{eq:heat-tail}
 \Pp_\mu(d(Y_0,Y_t)\ge B(t)+v)
 \le e^{-v^2/(4t)}\qquad(0\le v\le2t).
\end{equation}
The range matters: an unbounded Poisson clock does not have a Gaussian
far tail. The bounded discrete-time walk permits the full tail estimate
in the main theorems.

\begin{proof}[Proof of the tail bound in Theorems~\ref{thm:finite} and~\ref{thm:rooted}]
Use the independent clocks $K,N$ in~\eqref{eq:clock-distance}.
For $|\theta|\le1$, their exact moment generating functions give
\begin{align*}
 \log\E e^{\theta(K-N)}
 &=n\log\cosh(\theta/2)
       +\frac n2(e^{-\theta}-1+\theta)\\
 &\le\frac{n\theta^2}{8}+\frac n2(e-2)\theta^2
 \le\frac{n\theta^2}{2}.
\end{align*}
Here $\log\cosh z\le z^2/2$ follows by integrating
$|\tanh z|\le|z|$. Applying Markov's inequality with
$\theta=\pm w/n$ proves
\begin{equation}\label{eq:clock-tail}
 \Pp(|K-N|\ge w)\le2e^{-w^2/(2n)}\qquad(0\le w\le n).
\end{equation}
If $0\le u\le n$, split the excess in~\eqref{eq:clock-distance} into
two parts of size $u/2$. Use~\eqref{eq:heat-tail} at $t=n/2$ and
$v=u/2$, and~\eqref{eq:clock-tail} at $w=u/2$. Since
$B(n/2)\le\sqrt{Dn/2}$, the union bound gives
\[
 \Pp_\mu\!\left(d(X_0,X_n)\ge\sqrt{Dn/2}+u\right)
 \le e^{-u^2/(8n)}+2e^{-u^2/(8n)}.
\]
No independence between the heat displacement and the clock difference
is required. If $u>n$, the event is empty because $d(X_0,X_n)\le n$.
\end{proof}

\begin{corollary}\label{cor:all-moments}
Under either main theorem, for every real $p\ge1$,
\[
 \bigl(\E d(X_0,X_n)^p\bigr)^{1/p}
 \le\sqrt{Dn/2}
       +\bigl[3(8n)^{p/2}\Gamma(p/2+1)\bigr]^{1/p}
 \le C\bigl(\sqrt{Dn}+\sqrt{pn}\bigr),
\]
where $C$ is universal.
\end{corollary}
\begin{proof}
Integrate~\eqref{eq:main-tail} using
$\E V^p=\int_0^\infty p u^{p-1}\Pp(V>u)\,du$ for
$V=(d(X_0,X_n)-\sqrt{Dn/2})_+$. The change of variables
$s=u^2/(8n)$ gives the displayed gamma factor. Minkowski's inequality
adds the deterministic shift. For completeness, if $r=p/2\ge1/2$,
then $s^r e^{-s/2}\le(2r/e)^r$, so
$\Gamma(r+1)=\int_0^\infty s^re^{-s}\,ds\le2(2r/e)^r$.
Taking $p$th roots gives the last inequality with a universal constant.
\end{proof}

\section{Conditional moments at typical roots}\label{sec:typical}
Let $b_n(x)=\E_x d(x,X_n)$ for the discrete lazy walk, and put
$c_D=\sqrt{D/2}+\sqrt3/2$. Taking conditional expectations in
\eqref{eq:clock-distance}, then using Cauchy--Schwarz for the clocks,
gives
$b_n(x)\le a_{n/2}(x)+\sqrt{3n/4}$. Proposition~\ref{prop:mean-mgf}
therefore implies the following root-distribution bound for every $u\ge0$:
\begin{equation}\label{eq:root-tail}
 \mu\{b_n\ge c_D\sqrt n+u\}\le e^{-4u^2/n}.
\end{equation}
This controls how the conditional mean varies between roots. The next
proposition turns it into a simultaneous statement in time.

\begin{proposition}\label{prop:typical}
For every $0<\delta<1$, outside a set of rooted graphs of $\mu$-probability
at most $\delta$, the bounds
\begin{align}
 b_n(o)&\le(2+\sqrt2)\sqrt n\left[
 c_D+\frac12\sqrt{\log\frac{\pi^2(1+\lfloor\log_2n\rfloor)^2}{6\delta}}
 \right],\label{eq:typical-explicit}\\
 \E_o d(o,X_n)^2&\le
 Cn\left[D+\log(1/\delta)+\log\log(n+3)\right]\label{eq:typical-second}
\end{align}
hold for all integers $n\ge1$, with a universal $C$.
\end{proposition}
\begin{proof}
Wasserstein contraction gives subadditivity at a fixed root:
\begin{align*}
 b_{m+n}(x)
 &=W_1(\delta_x,\delta_xP^{m+n})\\
 &\le W_1(\delta_x,\delta_xP^m)
       +W_1(\delta_xP^m,(\delta_xP^n)P^m)
 \le b_m(x)+b_n(x).
\end{align*}
In~\eqref{eq:root-tail} set $n=2^j$ and
$u=\frac12\sqrt{2^j\log(\pi^2(j+1)^2/(6\delta))}$.
The sum of the resulting exceptional probabilities is $\delta$.
On the complementary event, write $n$ in binary and apply subadditivity.
For $J=\lfloor\log_2n\rfloor$, the logarithmic factor is bounded by its
value at $J$, while
$\sum_{j=0}^J2^{j/2}\le(2+\sqrt2)\sqrt n$.
This proves~\eqref{eq:typical-explicit}. No monotonicity of $b_n$ is used.

Finally the discrete backward martingale $P^{n-j}f(X_j)$, with
$f(z)=d(x,z)$, has conditional variance per step at most $1/2$:
its conditional variance is at most the mean squared difference from
$P^{n-j}f(X_{j-1})$, and a lazy step moves distance one with probability
at most $1/2$. Each smoothed function remains $1$-Lipschitz.
Summing martingale variances gives
$\operatorname{Var}_x d(x,X_n)\le n/2$.
Adding the square of~\eqref{eq:typical-explicit} proves
\eqref{eq:typical-second}.
\end{proof}

For a finite graph,~\eqref{eq:root-tail} also gives, for every vertex and
time,
\[
 b_n(x)\le\sqrt n\left(c_D+\frac12\sqrt{\log(1/\pi(x))}\right).
\]
Indeed, if this inequality failed, a slightly smaller threshold than
$b_n(x)$ in~\eqref{eq:root-tail} would contain $x$ but have probability
strictly smaller than $\pi(x)$. With $N$ vertices, $\pi(x)\ge1/(ND)$,
so the conditional second moment is at most $Cn(D+\log N)$.
The dependence on $N$ distinguishes this consequence from the open
pointwise degree-only conjecture.

\section{Sharp degree dependence}
\begin{proposition}\label{prop:cube}
For every integer $D\ge1$, any bounds $\E_\pi d(X_0,X_n)\le C_1(D)\sqrt n$ and
$\E_\pi d(X_0,X_n)^2\le C_2(D)n$, uniform over the graphs in
Theorem~\ref{thm:finite}, must satisfy
\[
 C_1(D)\ge\frac{1-e^{-1}}2\sqrt D,
 \qquad C_2(D)\ge\frac{(1-e^{-1})^2}{4}D.
\]
\end{proposition}
\begin{proof}
Use the $D$-dimensional cube $\{0,1\}^D$ with Hamming distance.
Couple two lazy walks by the same holding or coordinate-flipping action.
Each action preserves their distance, so~\eqref{eq:curvature} holds.
A fixed coordinate flips independently at each time with probability
$1/(2D)$. Its probability of differing from its initial value after $n$
steps is $[1-(1-1/D)^n]/2$. Thus, from every initial vertex,
\[
 \E d(X_0,X_n)=\frac D2\bigl(1-(1-1/D)^n\bigr).
\]
At $n=D$ this is at least $(1-e^{-1})D/2$. Dividing by $\sqrt D$
proves the first assertion; Jensen's inequality proves the second.
\end{proof}


\appendix

\section{A self-contained coupling estimate}\label{sec:coupling}
Set
\[
 Q=\frac{I+P}{2},\qquad \alpha=\frac1{4D}.
\]
The extra holding probability supplies the mass needed for the coupling switch below. This auxiliary kernel is used only to establish sublinear entropy and reversibility of the rooted law. Thus $Q(x,x)\ge3/4$, its nonholding probability is at most $1/4$, and $Q(x,a)\ge1/(4D)$ for each distinct neighbor $a$ of $x$. By the triangle inequality for $W_1$, applied along a geodesic, \eqref{eq:curvature} implies $W_1(P(x,\cdot),P(y,\cdot))\le d(x,y)$ for all $x,y$. Mixing such a coupling with the point mass at $(x,y)$ gives the same inequality for $Q$.

\begin{lemma}\label{lem:step}
For distinct vertices $x,y$ with $r=d(x,y)$, there is a coupling $(U,V)$ of $Q(x,\cdot)$ and $Q(y,\cdot)$ satisfying
\[
 \E d(U,V)\le r,\qquad \Pp(d(U,V)\le r-1)\ge\alpha,
 \qquad |d(U,V)-r|\le2.
\]
\end{lemma}
\begin{proof}
Choose a coupling $\gamma$ of transportation cost at most $r$, and a neighbor $a$ of $x$ on a geodesic to $y$. Every coupling of these marginals has
$\gamma(x,y)\ge Q(x,x)+Q(y,y)-1\ge1/2$.
For every entry $(a,b)$ of positive mass with $d(a,b)\ge r$, replace its mass $\beta_b=\gamma(a,b)$ by the switch
\[
 (a,b),(x,y)\longmapsto(a,y),(x,b).
\]
The total mass removed from $(x,y)$ is at most $Q(x,a)\le1/4$, so all switches are feasible and preserve the marginals. Since $d(a,y)=r-1$ and $d(x,b)\le r+1$, each switch changes the cost by at most
$\beta_b((r-1)+(r+1)-r-r)=0$.
Afterwards every entry in row $a$ has distance at most $r-1$. This row has mass $Q(x,a)\ge\alpha$. Finally each coordinate moves by distance at most one, giving the last assertion. All one-step supports are finite, so the proof also applies on infinite locally finite graphs.
\end{proof}

\begin{lemma}\label{lem:tail}
Suppose a nonnegative integer-valued process $Z_k$, absorbed at zero, starts at $r\ge1$. Before absorption its increments $\xi_k$ satisfy
\[
 |\xi_k|\le2,\qquad \E(\xi_k\mid\mathcal F_k)\le0,
 \qquad \E(\xi_k^2\mid\mathcal F_k)\ge\alpha.
\]
If $\tau$ is its absorption time, then
\[
 \Pp(\tau>n)\le\min\{1,9r/\sqrt{\alpha n}\}\qquad(n\ge1).
\]
\end{lemma}
\begin{proof}
For an integer $R>r$, stop at $T=\inf\{k:Z_k=0\text{ or }Z_k\ge R\}$. The function $v(z)=z(2(R+2)-z)$ satisfies, before $T$,
\[
 \E[v(Z_{k+1})-v(Z_k)\mid\mathcal F_k]
 = (2(R+2)-2Z_k)\E(\xi_k\mid\mathcal F_k)
   -\E(\xi_k^2\mid\mathcal F_k)\le-\alpha.
\]
The stopped process stays in $[0,R+2]$, where $v$ is nonnegative. Summing to a deterministic cutoff and then using monotone convergence yields
$\E T\le v(r)/\alpha\le2(R+2)r/\alpha$.
The stopped supermartingale $Z$ is bounded, and consequently
$\E Z_T\le r$ and $\Pp(Z_T\ge R)\le r/R$. Hence
\begin{equation}\label{eq:exit}
 \Pp(\tau>n)\le\frac rR+\frac{2(R+2)r}{\alpha n}.
\end{equation}
If $\alpha n\ge1$ and $r<\lceil\sqrt{\alpha n}\rceil$, take $R=\lceil\sqrt{\alpha n}\rceil$. Then $R+2\le4\sqrt{\alpha n}$, and \eqref{eq:exit} is at most $9r/\sqrt{\alpha n}$. In the other cases that expression is at least one, and the assertion follows from the trivial probability bound.
\end{proof}

\begin{proposition}\label{prop:tv}
For every graph satisfying the hypotheses above, finite or infinite,
\begin{equation}\label{eq:tv}
 \|Q^n(x,\cdot)-Q^n(y,\cdot)\|_{\TV}
 \le\min\{1,18\sqrt D\,d(x,y)/\sqrt n\}\qquad(n\ge1).
\end{equation}
\end{proposition}
\begin{proof}
On a fixed graph, choose the coupling of Lemma~\ref{lem:step} at each distinct ordered vertex pair, and identical transitions on the diagonal. The vertex set is countable, so these choices define a Markov coupling. Its distance is absorbed at zero, has nonpositive drift and jumps of size at most two, and has conditional second moment of its increments at least $\alpha$ before absorption. Lemma~\ref{lem:tail} bounds the probability that the walks have not coalesced. The coupling inequality for total variation gives \eqref{eq:tv}. No choice of coupling measurable as a function of the graph is needed: the resulting inequality holds on each fixed graph.
\end{proof}

\section{Entropy and reversibility}\label{app:reversibility}
Rooted graphs are considered up to rooted isomorphism, with the Borel structure generated by finite rooted neighborhoods. We give the details needed to use stationary edge reversal without presupposing reversibility. All vertex sums count actual vertices, even when different vertices give isomorphic rerootings. Such sums are Borel: restrict first to finite balls, use the monotone class theorem, and then take increasing limits. The event that the graph has one vertex is invariant under rerooting and contributes zero displacement. We may condition on its complement, so that all degrees lie between $1$ and $D$.

\subsection{Saturation and entropy}
Stationarity for $P$ implies stationarity for $Q=(I+P)/2$. Write $Y$ for the $Q$-walk. We will repeatedly use the following consequence of stationarity. If a rooted Borel event $A$ has full measure, then almost surely it holds at every vertex of the sampled graph. Indeed, for each $n$,
\[
 0=\mu(A^c)=\E_\mu\sum_x Q_G^n(o,x)\mathbf1_{A^c}(G,x).
\]
Intersect over $n$. Every vertex is reached with positive probability at some finite time, so no rerooting can belong to $A^c$. We call this the saturation property.

Set
\[
 H_n(G,x)=-\sum_zQ_G^n(x,z)\log Q_G^n(x,z),\qquad h_n=\E_\mu H_n(G,o).
\]
The convention is $0\log0=0$. Since there are at most $(D+1)^n$ possible endpoints, all these entropies are finite and bounded by $n\log(D+1)$.

\begin{lemma}\label{lem:entropy}
For $N\ge1$,
\[
 h_N\le\log(D+1)\bigl(1+36D^{3/2}\sqrt N\bigr).
\]
In particular, $h_N=o(N)$.
\end{lemma}
\begin{proof}
On a fixed rooted graph let $A=Y_1$ and $Z=Y_{n+1}$. Conditional on $A=a$, the law of $Z$ is $\nu_a=Q_G^n(a,\cdot)$. The entropy chain rule gives
\[
 H_{n+1}(G,o)-\sum_aQ_G(o,a)H_n(G,a)=I(A;Z),
\]
Here $I(A;Z)=H(Z)-H(Z\mid A)$ denotes mutual information on this fixed graph, with conditional entropy obtained by averaging the entropy of the conditional law. Averaging and using stationarity identifies the left side with $h_{n+1}-h_n$.

For $S=\{o\}\cup N_G(o)$ put $j(z)=\min_{a\in S}\nu_a(z)$ and $c=\sum_zj(z)$. Then \eqref{eq:tv} gives
\[
 1-c\le\sum_{a\sim o}\sum_z(\nu_o(z)-\nu_a(z))_+
 =\sum_{a\sim o}\|\nu_o-\nu_a\|_{\TV}
 \le\frac{18D^{3/2}}{\sqrt n}.
\]
The channel from $A$ to $Z$ has common part $j$ of mass $c$. More explicitly, independently of $A$ choose a Bernoulli variable $L$ with $\Pp(L=1)=1-c$. If $L=0$, draw $Z$ from $j/c$, independently of $A$; if $L=1$, use the residual law $(\nu_A-j)/(1-c)$. The chain rule implies
\[
 I(A;Z)\le I(A;Z,L)\le(1-c)H(A)\le(1-c)\log(D+1).
\]
When $c=0$ or $c=1$, the same estimate follows directly. Consequently
$0\le h_{n+1}-h_n\le18D^{3/2}\log(D+1)/\sqrt n$.
Sum this inequality, starting with $h_1\le\log(D+1)$.
\end{proof}

\subsection{Entropy and reversal of the rooted edge}
The next argument is a counting-measure version of the Radon--Nikodym cocycle method in~\cite[Section~4]{BC}.

\begin{lemma}\label{lem:reversal}
For a stationary law of graphs with degrees in $\{1,\ldots,D\}$, sublinear $Q$-entropy $h_n=o(n)$ implies reversibility for $Q$ and for $P$.
\end{lemma}
\begin{proof}
On graphs with two ordered roots define the sigma-finite counting measures
\[
 \M(F)=\E_\mu\sum_yF(G,o,y),\qquad
 \check\M(F)=\E_\mu\sum_yF(G,y,o).
\]
They are finite on sets where the roots have bounded distance. They are equivalent: if $\M(A)=0$, saturation applied to $\sum_y\mathbf1_A(G,x,y)$ shows that this sum vanishes at every $x$ almost surely, and hence $\check\M(A)=0$. Reversing the set proves the converse. Let $J=d\check\M/d\M$ be a positive finite Borel version outside its null exceptional set.

We record why $J$ is a cocycle. On triples use
$\mathcal T(F)=\E_\mu\sum_{y,z}F(G,o,y,z)$, and write $S_{ij}$ for the exchange of coordinates $i,j$. Summing over the unused root shows
\[
 \frac{d(S_{12})_*\mathcal T}{d\mathcal T}(x,y,z)=J(x,y),\qquad
 \frac{d(S_{13})_*\mathcal T}{d\mathcal T}(x,y,z)=J(x,z),
 \qquad (S_{23})_*\mathcal T=\mathcal T,
\]
where the graph argument is suppressed. For an involution $S$ with density $j_S=dS_*\mathcal T/d\mathcal T$, the image of $f\mathcal T$ has density $(f\circ S)j_S$. Applying successively $S_{12},S_{23},S_{12}$ gives densities $J(x,y)$, then $J(x,z)$, then $J(y,z)J(x,y)$. Since this composition is $S_{13}$,
\begin{equation}\label{eq:cocycle}
 J(x,z)=J(x,y)J(y,z)
\end{equation}
for almost every triple. On the diagonal, $J(x,x)=1$. Counting and then saturating these full-measure events makes the identities valid simultaneously for all vertices of almost every sampled graph.

Define $\Delta(x,y)=\deg(x)J(x,y)/\deg(y)$. It obeys the same cocycle identity and $\Delta(x,y)\Delta(y,x)=1$. Let $\Lambda_n$ be the law of $(G,o,Y_n)$ and $\check\Lambda_n$ its reversal. Their densities with respect to $\M$ are $Q_G^n(x,y)$ and $J(x,y)Q_G^n(y,x)$. Degree detailed balance on each fixed graph implies
\[
 \deg(x)Q_G^n(x,y)=\deg(y)Q_G^n(y,x),\qquad
 \check\Lambda_n=\Delta\Lambda_n.
\]
Both endpoint laws have first-root marginal $\mu$, by stationarity. It follows that
\begin{equation}\label{eq:normalization}
 \sum_yQ_G^n(x,y)\Delta(x,y)=1
\end{equation}
for every $x,n$, after intersecting and saturating the relevant full-measure events.

For a possible one-step transition, $Q_G(x,y),Q_G(y,x)\ge1/(4D)$. Apply \eqref{eq:normalization} at $x$ and at $y$, and use reciprocity, to obtain
$(4D)^{-1}\le\Delta(x,y)\le4D$.
Thus its one-step logarithm is integrable. Set
\[
 \eta=-\E_\mu\log\Delta(o,Y_1)
 =\E_\mu\bigl[\Delta(o,Y_1)-1-\log\Delta(o,Y_1)\bigr]\ge0.
\]
The equality uses \eqref{eq:normalization}. The cocycle identity and stationarity along the walk give
$-\E_\mu\log\Delta(o,Y_n)=n\eta$.
On the other hand, the $o$ term of \eqref{eq:normalization} at $Y_n$ gives
\[
 \Delta(o,Y_n)\ge Q_G^n(Y_n,o)
 =\frac{\deg(o)}{\deg(Y_n)}Q_G^n(o,Y_n)
 \ge D^{-1}Q_G^n(o,Y_n).
\]
Taking negative logarithms and expectations gives $n\eta\le h_n+\log D$. Sublinearity forces $\eta=0$. Since $u-1-\log u$ is nonnegative and vanishes only at $u=1$, we have $\Delta(o,Y_1)=1$ almost surely. Hence $\Lambda_1=\check\Lambda_1$, proving $Q$-reversibility. The $Q$ endpoint law is half the diagonal law plus half the $P$ endpoint law; the diagonal law is symmetric, so $P$ is reversible as well.
\end{proof}

\begin{remark}[Why vertices must be counted with multiplicity]
Consider the three-leaf star rooted according to its degree-biased stationary probability. The center has probability $1/2$ and each leaf has probability $1/6$. On the isomorphism type whose first root is the center and whose second root is a leaf, $\M$ has mass $3/2$, whereas $\check\M$ has mass $1/2$. Thus $J=1/3$, and the degree correction gives $\Delta=3J=1$, as reversibility requires. Counting only one representative of the three isomorphic leaves would give the wrong Radon--Nikodym derivative. The counting measures in the proof avoid this problem.
\end{remark}

\begin{thebibliography}{99}
\bibitem{BHM} C. Brena, T. Hutchcroft and F. M\"unch, \emph{Transitive graphs of non-negative Ollivier--Ricci curvature have polynomial growth}, arXiv:2512.03968v2 (2026), \url{https://arxiv.org/abs/2512.03968v2}.
\bibitem{Munch} F. M\"unch, \emph{Non-negative Ollivier curvature on graphs, reverse Poincar\'e inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates}, J. Math. Pures Appl. \textbf{170} (2023), 231--257, \url{https://doi.org/10.1016/j.matpur.2022.12.007}; preprint \url{https://arxiv.org/abs/1907.13514v1}.
\bibitem{Salez} J. Salez, \emph{Sparse expanders have negative curvature}, Geom. Funct. Anal. \textbf{32} (2022), 1486--1513; preprint numbering from \url{https://arxiv.org/abs/2101.08242v2}.
\bibitem{BC} I. Benjamini and N. Curien, \emph{Ergodic theory on stationary random graphs}, Electron. J. Probab. \textbf{17} (2012), no.~93, 1--20, \url{https://doi.org/10.1214/EJP.v17-2401}.
\bibitem{MS} F. M\"unch and J. Salez, \emph{Mixing time and expansion of non-negatively curved Markov chains}, J. \'Ec. polytech. Math. \textbf{10} (2023), 575--590, \url{https://doi.org/10.5802/jep.226}.
\bibitem{Ollivier} Y. Ollivier, \emph{Ricci curvature of Markov chains on metric spaces}, J. Funct. Anal. \textbf{256} (2009), 810--864, \url{https://doi.org/10.1016/j.jfa.2008.11.001}.
\bibitem{OllivierSurvey} Y. Ollivier, \emph{A survey of Ricci curvature for metric spaces and Markov chains}, in Probabilistic Approach to Geometry, Adv. Stud. Pure Math. \textbf{57}, Math. Soc. Japan, Tokyo, 2010, 343--381, \url{https://doi.org/10.2969/aspm/05710343}.
\bibitem{LLY} Y. Lin, L. Lu and S.-T. Yau, \emph{Ricci curvature of graphs}, Tohoku Math. J. \textbf{63} (2011), 605--627, \url{https://doi.org/10.2748/tmj/1325886283}.
\bibitem{BD} R. Bubley and M. Dyer, \emph{Path coupling: a technique for proving rapid mixing in Markov chains}, in Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 1997, 223--231, \url{https://doi.org/10.1109/SFCS.1997.646111}.
\bibitem{Carne} T. K. Carne, \emph{A transmutation formula for Markov chains}, Bull. Sci. Math. (2) \textbf{109} (1985), 399--405.
\bibitem{LP13} J. R. Lee and Y. Peres, \emph{Harmonic maps on amenable groups and a diffusive lower bound for random walks}, Ann. Probab. \textbf{41} (2013), 3392--3419, \url{https://doi.org/10.1214/12-AOP779}.
\bibitem{HL} T. Hutchcroft and I. M. Lopez, \emph{A relation between isoperimetry and total variation decay with applications to graphs of non-negative Ollivier--Ricci curvature}, arXiv:2411.04988v1 (2024), \url{https://arxiv.org/abs/2411.04988v1}.
\bibitem{Zhou} C. Zhou, \emph{Pointwise subexponential growth and near-diffusive displacement on bounded-degree graphs with non-negative Ollivier--Ricci curvature}, arXiv:2607.27162v1 (2026), \url{https://arxiv.org/abs/2607.27162v1}.
\bibitem{BB} C. Brena and E. Bru\`e, \emph{Ollivier--Ricci curvature on groups of polynomial growth}, arXiv:2608.14232v1 (2026), \url{https://arxiv.org/abs/2608.14232v1}.
\end{thebibliography}
\end{document}