Markov chain comparison

By M. Dyer, Leslie Ann Goldberg, M. Jerrum, Russell Martin. 2004

68 citations recorded by the source corpus.

This is an expository paper, focussing on the following scenario. We have two Markov chains, M and M'. By some means, we have obtained a bound on the mixing time of M'. We wish to compare M with M' in order to derive a corresponding bound on the mixing time of 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.

Subfields: Management Information Systems, Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/650d8f9a2a8a744c1dffc8db9ecb290013c60cb5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Information Systems

1. L. Saloff‐Coste
2. Persi Diaconis
3. Kshitij Khare

In Management Science and Operations Research

1. Persi Diaconis
2. Kshitij Khare

In Statistics and Probability

1. Persi Diaconis
2. Kshitij Khare
3. L. Saloff‐Coste
4. Prasad Tetali
5. Ravi Montenegro
6. Neil O'Connell
7. W. Koenig
8. Ali H. Sayed

Citations in the corpus

• Mathematical Aspects of Mixing Times in Markov Chains (2006, background): “[29] describes several comparison theorems for reversible as well as nonreversible Markov chains.”
• Gibbs sampling, exponential families and orthogonal polynomials (2008, methodology): “M E ] 2 8 A ug 2 00 8 Key words and phrases: Gibbs sampler, running time analyses, exponential families, conjugate priors, location families, orthogonal polynomials, singular value decomposition.”