Comparison inequalities and fastest-mixing Markov chains
Authors:
- James Allen FillJFJames Allen Fill
- Jonas KahnJKJonas Kahn
Open Access
- 1 October 2013
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 23 (5) , 1778-1816
Abstract
We introduce a new partial order on the class of stochastically monotone Markov kernels having a given stationary distribution $\pi$ on a given finite partially ordered state space ${ \mathcal{X}}$. When $K\preceq L$ in this partial order we say that $K$ and $L$ satisfy a comparison inequality. We establish that if $K_{1},\ldots,K_{t}$ and $L_{1},\ldots,L_{t}$ are reversible and $K_{s}\preceq L_{s}$ for $s=1,\ldots,t$, then $K_{1}\cdots K_{t}\preceq L_{1}\cdots L_{t}$. In particular, in the time-homogeneous case we have $K^{t}\preceq L^{t}$ for every $t$ if $K$ and $L$ are reversible and $K\preceq L$, and using this we show that (for suitable common initial distributions) the Markov chain $Y$ with kernel $K$ mixes faster than the chain $Z$ with kernel $L$, in the strong sense that at every time $t$ the discrepancy—measured by total variation distance or separation or $L^{2}$-distance—between the law of $Y_{t}$ and $\pi$ is smaller than that between the law of $Z_{t}$ and $\pi$. Using comparison inequalities together with specialized arguments to remove the stochastic monotonicity restriction, we answer a question of Persi Diaconis by showing that, among all symmetric birth-and-death kernels on the path ${ \mathcal{X}}=\{0,\ldots,n\}$, the one (we call it the uniform chain) that produces fastest convergence from initial state $0$ to the uniform distribution has transition probability $1/2$ in each direction along each edge of the path, with holding probability $1/2$ at each endpoint. We also use comparison inequalities: (i) to identify, when $\pi$ is a given log-concave distribution on the path, the fastest-mixing stochastically monotone birth-and-death chain started at $0$, and (ii) to recover and extend a result of Peres and Winkler that extra updates do not delay mixing for monotone spin systems. Among the fastest-mixing chains in (i), we show that the chain for uniform $\pi$ is slowest in the sense of maximizing separation at every time.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Merging for inhomogeneous finite Markov chains, part II: Nash and log-Sobolev inequalitiesThe Annals of Probability, 2011
- Time inhomogeneous Markov chains with wave-like behaviorThe Annals of Applied Probability, 2010
- Proof of Aldous’ spectral gap conjectureJournal of the American Mathematical Society, 2010
- Fastest Mixing Markov Chain on a PathThe American Mathematical Monthly, 2006
- How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed GraphJournal of Algorithms, 1998
- Mixing of random walks and other diffusions on a graph1995
- Comparison Theorems for Reversible Markov ChainsThe Annals of Applied Probability, 1993
- Time to Stationarity for a Continuous-Time Markov ChainProbability in the Engineering and Informational Sciences, 1991
- Strong Stationary Times Via a New Form of DualityThe Annals of Probability, 1990
- Bounds on the Coarseness of Random SumsThe Annals of Probability, 1988