Markov chain comparison

Abstract

This is an expository paper, focussing on the following scenario. We have two Markov chains, $\mathcal{M}$ and ${\mathcal{M}}^{\prime }$. By some means, we have obtained a bound on the mixing time of ${\mathcal{M}}^{\prime }$. We wish to compare $\mathcal{M}$ with ${\mathcal{M}}^{\prime }$ in order to derive a corresponding bound on the mixing time of $\mathcal{M}$. We investigate the application of the comparison method of Diaconis and Saloff-Coste to this scenario, giving a number of theorems which characterize the applicability of the method. We focus particularly on the case in which the chains are not reversible. The purpose of the paper is to provide a catalogue of theorems which can be easily applied to bound mixing times.

Published at http://dx.doi.org/10.1214/154957806000000041 in the Probability Surveys (http://www.i-journals.org/ps/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (11)

• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Some things we've learned (about Markov chain Monte Carlo)
• Matrix norms and rapid mixing for spin systems
• Structure and eigenvalues of heat-bath Markov chains
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• A Counterexample to rapid mixing of the Ge-Stefankovic Process
• The Invisible Hand of Laplace: the Role of Market Structure in Price Convergence and Oscillation
• Gibbs Sampling, Exponential Families and Orthogonal Polynomials
• Intersection conductance and canonical alternating paths, methods for general finite Markov chains
• Reversibility of the non-backtracking random walk
• Rejoinder: Gibbs Sampling, Exponential Families and Orthogonal Polynomials