Regarding Ricci curvature of Markov chains

Question

In Ricci curvature of Markov chains on metric spaces Yann Ollivier, defines a coarse Ricci curvature for a Markov chain with transition kernels $\{m_x\}$ defined on a metric space $(X,d)$ as follows: The curvature along $(xy)$ is $$ \kappa(x,y) := 1 - \frac{W_1(m_x,m_y)}{d(x,y)}, $$ where $W_1$ is the $\ell_1$ transportation distance between $m_x$ and $m_y$ with transportation cost $d$. The space is positively curved if $\kappa(x,y) \ge \kappa > 0$. Then, it follows that the Markov chain shows contraction (in $W_1$ metric) to a unique invariant distribution, at a geometric rate (at least like $(1-\kappa)^n$). This is Corollary 21 in the paper.

My question is what happens if we only have $\kappa(x,y) \ge \kappa > 0$ for $d(x,y) \ge M$ for $M$ large enoguh. That is, the space is positively curved if $x$ and $y$ are far apart (and maybe negatively curved if they are close.) Can we still show a contraction from any (or a subset) of starting distributions? If not what else is needed to get such a result.

Answer 1

Just an example to show that you will certainly need something to get the kind of contraction you're after.

Let the space be $\mathbb N\times \{0,1\}$, where the distance from $(n,i)$ to $(m,j)$ is just $|n-m|+|i-j|$. Imagine a kernel which sends everything towards the origin, but leaving you in the same copy of the Markov chain e.g. $(n,i)$ transitions to $(\lfloor n/2\rfloor + Q,i)$, where $Q$ is a Poisson random variable. This satisfies the large scale geometric contraction you're looking for, but clearly two distributions on the two parts of the space will never approach each other.

Answer 2

I believe that you can establish a geometric bound if your contraction constraint is the other way around, i.e. if $\kappa(x,y) \geq \kappa > 0$ when $d(x,y) \leq M$ for some suitable $M$. This kind of approach seems to me to generalise the small set coupling constructions for general state space Markov chains to more Wasserstein distances than the classical total variation metric. It's explained in this paper (and other places most likely):

http://link.springer.com/article/10.1007/s11222-014-9511-z

Answer 3

That is indeed a beautiful question!

In principle, there are two ways to ensure Wasserstein contaction when the original Markov chain does not:

1. Deform the distance

2. Take powers/exponential of the original Markov chain

For 1), assume that $d$ is the hop count distance. Then, you can set $d' = \phi \circ d$ for a suitable increasing function $\phi: \mathbb R_+ \to \mathbb R_+$. Suitable here means that $\phi(n)$ is sufficiently concave for $n<M$ to ensure positive curvature for small distances. For $n>M$, you can set $\phi$ to be (affine) linear, and this will give you positive curvature for large distances. This should always give something as long as you have a lower bound for the positive jump rates, but the decay rates seem to be very bad in the general case.

For 2), there is a paper establishing cutoff for the random walk on the permutation group by Berestycki and Sengul N Berestycki, B Sengul They show positive curvature for powers of the Markov kernel although the original Markov kernel is negatively curved.

Also, a general, but rather easy thing to note is that if $d(\operatorname{supp} \nu,\operatorname{supp} \mu) \geq M + R$, then for all $r<R$, $$ W(\mu P^r, \nu P^r) \leq (1-\kappa)^r W(\mu,\nu), $$ again assuming hop count distance.

It might be promising to combine 1) and 2) but as Anthony pointed out, you need some additional assumptions: You consider $P' = P^R$ for some $R>M$, and $d'$ the hop count distance of $P'$. The goal is to establish positive curvature for $P'$ with respect to $d'$. Let $$ \rho_0 := 1 -\sup_{d(x,y) \leq R} d_{TV}(\delta_x P^R, \delta_y P^R) $$ You need a good lower bound on $\rho_0$ this which is not there in the general case by the example of Anthony, but might work in your application. On the other hand, you fix $x,y$ with $d(x,y) \leq R$, and consider the coupled random walks $X_R$ and $Y_R$ after $R$ steps, and the curvature assumption should yield an upper bound on $$ \rho_2 := P(d(X_R,Y_R) >R) $$ Indeed having lazyness, you can couple $X_R,Y_R$ such that $d(X_R,Y_R) \leq 2R$ meaning that $d'$ can only increase by at most one after one step of $P'$ meaning $R$ steps of $P$. Some upper bound on $\rho_2$ should follow by estimating the random variable $d(X_R,Y_R)$ by the random walk on a biased birth death chain (with bias towards the origin with rate $\kappa$ on all states $\geq M$, and reflecting at state $M-1$). Then, the curvature of $P'$ with respect to $d'$ should be at least $\rho_0 - \rho_2$ which is hopefully positive.