Comparison inequalities and fastest-mixing Markov chains

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⪯L$ in this partial order we say that $K$ and $L$ satisfy a comparison inequality. We establish that if $K_1,\dots ,K_t$ and $L_1,\dots ,L_t$ are reversible and $K_s⪯L_s$ for $s=1,\dots ,t$, then $K_1\cdots K_t⪯L_1\cdots L_t$. In particular, in the time-homogeneous case we have $K^t⪯L^t$ for every $t$ if $K$ and $L$ are reversible and $K⪯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,\dots ,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.

Published in at http://dx.doi.org/10.1214/12-AAP886 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Fastest mixing Markov chain on graphs with symmetries
• Proof of Aldous' spectral gap conjecture
• Merging for inhomogeneous finite Markov chains, part II: Nash and log-Sobolev inequalities
• Time inhomogeneous Markov chains with wave-like behavior
• Some circumstances where extra updates can delay mixing

Cited by in corpus (5)

• Exclusive ${\mathbf{\pi }}^0\mathbf{p}$ electroproduction off protons in the resonance region at photon virtualities 0.4~GeV${}^2$ $\le {\mathbf{Q}}^2\le 1$~GeV${}^2$
• Fastest Mixing Reversible Markov Chain: Clique Lifted Graphs and Subgraphs
• Stochastic Orderings of Multivariate Elliptical Distributions
• Geometric Bounds on the Fastest Mixing Markov Chain
• Comparison of hit-and-run, slice sampling and random walk Metropolis