COMPARISON INEQUALITIES AND FASTEST-MIXING MARKOV CHAINS

• 成果类型: Article
• 署名作者: Fill, James Allen; Kahn, Jonas
• 署名单位: Johns Hopkins University; Universite de Lille; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/12-AAP886
• 发表日期: 2013
• 页码: 1778-1816
• 关键词: times; algorithm; graph

摘要

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 X. When K L in this partial order we say that K and L satisfy a comparison inequality. We establish that if K-1, ..., K-t and L-1, ..., L-t are reversible and K-s <= L-s for s =1, ..., t, then K-1 ... K-t <= L-1 ... 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 chi = {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 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.