Stationary diffusion on nonnegatively curved graphs

Introduction

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 [6, 7]; it is related to path coupling [9] and to the graph-curvature definition of Lin, Lu and Yau [8]. The condition compares 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 § 2. For probability measures $\rho$, $\sigma$, let $W_1(\rho,\sigma)$ be the infimum of $\mathbb{E}d(U,V)$ over couplings with these marginals.

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 [3] established sublinear stationary displacement under nonnegative curvature and a bounded-degree assumption. Brena, Hutchcroft and Münch [1 Introduction, p. 3] 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.

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 [1 Corollary 1.2 and Theorem 1.3]. 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.

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.

1. Theorem 1.3 gives the finite-graph second-moment and tail bounds. Proposition 6.1 shows that the factor $D$ in the second moment has the correct order.

2. Theorem 1.4 extends both estimates to stationary random rooted graphs, including infinite graphs. Curvature supplies the reversibility needed for this extension.

3. Proposition 5.1 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.

For the infinite version, stationarity concerns the graph as 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.

The averaging is essential to these statements. In particular, (3) is an 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 $\mathbb{E}_x d(x,X_n)^2 \le C(D)n$ from every vertex, stated separately in [1 Remark 1.4], is not resolved here.

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)=\mathbb{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ünch [2 Corollary 3.1.2, preprint numbering] proves that neighboring heat kernels approach each other in total variation at rate $O(\sqrt{D/t})$. Salez [3 Section 3.2] develops the coupling method, and Münch and Salez [5 Theorem 4] give an explicit finite discrete-time estimate. We use Münch’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 § 7.

Stationarity of a random rooted graph does not by itself imply reversibility. Salez’s zero-entropy theorem [3 Theorem 11] and the entropy theory of Benjamini and Curien [4 Proposition 3.6 and Theorem 4.4] supply the relevant principle. Appendix § 8 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 [1 Theorem 1.3] is bounded by $C(D)n(\log n)^{3/2}$. Since the uniform vertex measure is at most $D\pi$, Theorem 1.3 also gives a uniform-vertex bound $4D^2n$, removing this logarithmic loss. Zhou’s pointwise estimate [13 Theorem 2.1 and Corollary 2.2] retains a subpolynomial loss in time; it applies to every vertex, a stronger quantifier than stationary averaging. Hutchcroft and Lopez [12 Theorem 2.1] give upper tails relative to the supremum of the expected displacement over all starting vertices. A stationary mean does not control that supremum, so their theorem does not directly give (3).

Transition-probability bounds such as the Carne–Varopoulos estimate [10] 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 [11] and Münch and Salez [5 Theorem 3 and Corollary 5], address the complementary question of slow escape. In the transitive setting the polynomial-growth theorem of [1] and the rigidity theorem of Brena and Bruè [14 Theorem 1.9] give stronger geometric information. The proof below obtains stationary diffusion directly, without a geometric classification.

Heat evolution and stationary edge reversal

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

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 (1), 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.

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 1.4, Lemmas B.1 and B.2 in Appendix § 8 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 $\mathbb{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

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.

Edge reversal gives the two identities

Their sum is (6). All quantities are integrable: $a_t\leq 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.

Diffusive second moments

Proof. Apply Lemma 2.2 first to $\phi(a)=a$. Since $\lvert(v_y-v_x)(g)\rvert\leq2\varepsilon_t$, it gives $\left\lvert\frac{d}{dt}\mathbb{E}_{\mu}a_t\right\rvert\leq\varepsilon_t$. The mean starts at zero, proving the first bound.

Next let $A(t)=\mathbb{E}_{\mu}a_t^2$ and take $\phi(a)=a^2$ in the same identity:

The first term is at most $2\varepsilon_t\mathbb{E}_{\mu}a_t$; the remaining terms satisfy

Consequently $A'(t)\leq2\varepsilon_tB(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\leq s\leq t$, has jumps of absolute value at most one, because $S_{t-s}f$ is 1-Lipschitz. Its predictable quadratic variation has rate

Therefore $\operatorname{Var}_x d(x,Y_t)\leq 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

Proof of the moment bounds in Theorems 1.3 and 1.4. Use one nonlazy $R$-walk $(Z_j)_{j\geq0}$ 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,

Both clocks have mean $n/2$, and $\mathbb{E}(K-N)^2=n/4+n/2=3n/4$. Using $(r+s)^2\leq2r^2+2s^2$ and Proposition 3.1 yields

Cauchy–Schwarz gives the first moment. Finite stationary walks are reversible by degree detailed balance; the random-rooted case uses Appendix § 8, as explained above. Restoring any mass on a one-vertex graph contributes zero displacement.

Exponential energy and Gaussian tails

Combining the conditional bound with Proposition 4.1 gives

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

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.

Proof of the tail bound in Theorems 1.3 and 1.4. Use the independent clocks $K,N$ in (10). For $|\theta| \le1$, their exact moment generating functions give

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

If $0 \le u \le n$, split the excess in (10) into two parts of size $u/2$. Use (14) at $t=n/2$ and $v=u/2$, and (15) at $w=u/2$. Since $B(n/2) \le\sqrt{Dn/2}$, the union bound gives

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$. $\square$

Proof. Integrate (3) using $\mathbb{E}V^p=\int_0^\infty pu^{p-1}\mathbb{P}(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^re^{-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. $\square$

Conditional moments at typical roots

Let $b_n(x)=\mathbb{E}_xd(x,X_n)$ for the discrete lazy walk, and put $c_D=\sqrt{D/2}+\sqrt{3}/2$. Taking conditional expectations in (10), then using Cauchy–Schwarz for the clocks, gives $b_n(x)\le a_{n/2}(x)+\sqrt{3n}/4$. Proposition 4.1 therefore implies the following root-distribution bound for every $u\ge0$:

This controls how the conditional mean varies between roots. The next proposition turns it into a simultaneous statement in time.

Proof. Wasserstein contraction gives subadditivity at a fixed root:

In (16) set $n=2^j$ and $u=\frac{1}{2}\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_2 n\rfloor$, the logarithmic factor is bounded by its value at $J$, while $\sum_{j=0}^J 2^{j/2}\le(2+\sqrt{2})\sqrt{n}$. This proves (17). 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 (17) proves (18).

For a finite graph, (16) also gives, for every vertex and time,

Indeed, if this inequality failed, a slightly smaller threshold than $b_n(x)$ in (16) 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.

Sharp degree dependence

Proposition 6.1. For every integer $D\ge1$, any bounds $\mathbb{E}_{\pi}d(X_0,X_n)\le C_1(D)\sqrt{n}$ and $\mathbb{E}_{\pi}d(X_0,X_n)^2\le C_2(D)n$, uniform over the graphs in Theorem 1.3, must satisfy

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 (1) 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,

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.

A self-contained coupling estimate

Set

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, (1) 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$.

Lemma A.1. 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

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

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.

Entropy and 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$.

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$,

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

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)$.

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,\mathord\cdot)$. The entropy chain rule gives

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_z j(z)$. Then (20) gives

The channel from $A$ to $Z$ has common part $j$ of mass $c$. More explicitly, independently of $A$ choose a Bernoulli variable $L$ with $\mathbb{P}(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

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)$.

Entropy and reversal of the rooted edge

The next argument is a counting-measure version of the Radon–Nikodym cocycle method in [4 Section 4].

Proof. On graphs with two ordered roots define the sigma-finite counting measures

They are finite on sets where the roots have bounded distance. They are equivalent: if $\mathcal{M}(A)=0$, saturation applied to $\sum_y 1_A(G,x,y)$ shows that this sum vanishes at every $x$ almost surely, and hence $\widetilde{\mathcal{M}}(A)=0$. Reversing the set proves the converse. Let $J=d\widetilde{\mathcal{M}}/d\mathcal{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)=\mathbb{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

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}$,

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 $\widetilde{\Lambda}_n$ its reversal. Their densities with respect to $\mathcal{M}$ are $Q_G^n(x,y)$ and $J(x,y)Q_G^n(y,x)$. Degree detailed balance on each fixed graph implies

Both endpoint laws have first-root marginal $\mu$, by stationarity. It follows that

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 (22) 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

The equality uses (22). The cocycle identity and stationarity along the walk give $-\mathbb{E}_{\mu}\log\Delta(o,Y_n)=n\eta$. On the other hand, the $o$ term of (22) at $Y_n$ gives

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=\widetilde{\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. □

Remark B.3 (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, $\mathcal{M}$ has mass $3/2$, whereas $\widetilde{\mathcal{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.