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 . on a given finite partially ordered state space X. When K.L in this partial order we say that K and L satisfy a comparison inequality. We establish that if K1,.,Kt and L1,.,Lt are reversible and Ks.Ls for s=1,.,t, then K1.Kt.L1.Lt. In particular, in the time-homogeneous case we have Kt.Lt 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 L2-distance.between the law of Yt and . is smaller than that between the law of Zt and . 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 X={0,.,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 . 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 . is slowest in the sense of maximizing separation at every time.