Comparison inequalities and fastest-mixing Markov chains

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\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⪯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.