Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 3 (2006) open journal systems 


Markov chain comparison

Martin Dyer, University of Leeds
Leslie Ann Goldberg, University of Warwick
Mark Jerrum, University of Edinburgh
Russell Martin, University of Liverpool


Abstract
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.

AMS 2000 subject classifications: Primary 60J10, 68W20; secondary 60J27.

Keywords: Markov chains, mixing time, comparison.

Creative Common LOGO

Full Text: PDF


Dyer, Martin, Goldberg, Leslie Ann, Jerrum, Mark, Martin, Russell, Markov chain comparison, Probability Surveys, 3, (2006), 89-111 (electronic).

References

[1]   D. Aldous, Some inequalities for reversible Markov chains, J. London Math Society (2) 25 (1982), pp. 564–576. MR0657512

[2]   D. Aldous and J. Fill, Reversible Markov chains and random walks on graphs. http://oz.berkeley.edu/users/aldous/RWG/book.html.

[3]   M. Cryan, M. Dyer, L.A. Goldberg, M. Jerrum and R. Martin, Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 711–720.

[4]   P. Diaconis, S. Holmes and R.M. Neal, Analysis of a nonreversible Markov chain sampler, Annals of Applied Probability 10 (2000), pp. 726–752. MR1789978

[5]   P. Diaconis and L. Saloff-Coste, Comparison theorems for reversible Markov chains, Annals of Applied Probability 3 (1993), pp. 696–730. MR1233621

[6]   P. Diaconis and L. Saloff-Coste, Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993), no. 4, 2131–2156. MR1245303

[7]   P. Diaconis and L. Saloff-Coste, Walks on generating sets of abelian groups. Probab. Theory Related Fields 105 (1996), no. 3, 393–421. MR1425868

[8]   P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Annals of Applied Probability 1 (1991), pp. 36–61. MR1097463

[9]   M. Dyer, A. Frieze and M. Jerrum, On counting independent sets in sparse graphs, SIAM J. Computing 33 (2002), pp. 1527–1541. MR1936657

[10]   J.A. Fill, Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Annals of Applied Probability 1 (1991), pp. 62–87. MR1097464

[11]   R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985. MR0832183

[12]   M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Birkhäuser Verlag, Basel, 2003. MR1960003

[13]   J. Keilson, Marlov Chain Models: Rarity and Exponentiality, Springer-Verlag, New York, 1979. MR0528293

[14]   L. Miclo, Remarques sur l’hypercontractivité et l’évolution de l’entropie pour des chaînes de Markov finies, Séminaire de Probabilités XXXI Springer Lecture Notes in Mathematics 1655 (in French).

[15]   M. Mihail, Combinatorial Aspects of Expanders, PhD Thesis, Harvard University, 1989.

[16]   J.R. Norris, Markov Chains, Cambridge University Press, Cambridge, 1997. MR1600720

[17]   J. Quastel, Diffusion of colour in the simple exclusion process, Comm. Pure Appl. Math. 45 (1992), pp. 623–679. MR1162368

[18]   D. Randall and P. Tetali, Analyzing Glauber dynamics by comparison of Markov chains. J. Mathematical Physics 41 (2000), pp. 1598–1615. MR1757972

[19]   A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combinatorics, Probability and Computing 1 (1992), pp. 351–370. MR1211324

[20]   A. Sinclair, Algorithms for Random Generation & Counting: A Markov Chain Approach, Birkhäuser, Boston, 1993. MR1201590




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787