Markov chains and mixing times: with a chapter on coupling from the past by James G. Propp and David B. Wilson

This book is an introduction to the modern approach to the theory of Markov chains. The main goal of this approach is to determine the rate of convergence of a Markov chain to the stationary distribution as a function of the size and geometry of the state space. The authors develop the key tools for estimating convergence times, including coupling, strong stationary times, and spectral methods. Whenever possible, probabilistic methods are emphasized. The book includes many examples and provides brief introductions to some central models of statistical mechanics. Also provided are accounts of random walks on networks, including hitting and cover times, and analyses of several methods of shuffling cards. As a prerequisite, the authors assume a modest understanding of probability theory and linear algebra at an undergraduate level. Markov Chains and Mixing Times is meant to bring the excitement of this active area of research to a wide audience. Chapter 1. Introduction To Finite Markov Chains Chapter 2. Classical (and Useful) Markov Chains Chapter 3. Markov Chain Monte Carlo: Metropolis And Glauber Chains Chapter 4. Introduction To Markov Chain Mixing Chapter 5. Coupling Chapter 6. Strong Stationary Times Chapter 7. Lower Bounds On Mixing Times Chapter 8. The Symmetric Group And Shuffling Cards Chapter 9. Random Walks On Networks Chapter 10. Hitting Times Chapter 11. Cover Times Chapter 12. Eigenvalues Chapter 13. Eigenfunctions And Comparison Of Chains Chapter 14. The Transportation Metric And Path Coupling Chapter 15. The Ising Model Chapter 16. From Shuffling Cards To Shuffling Genes Chapter 17. Martingales And Evolving Sets Chapter 18. The Cutoff Phenomenon Chapter 19. Lamplighter Walks Chapter 20. Continuous-time Chains Chapter 21. Countable State Space Chains Chapter 22. Coupling From The Past Chapter 23. Open Problems Appendix A. Background Material Appendix B. Introduction To Simulation Appendix C. Solutions To Selected Exercises. David A. Levin, Yuval Peres, Elizabeth L. Wilmer. With A Chapter On Coupling From The Past By James G. Propp And David B. Wilson. Includes Bibliographical References (pages 353-361) And Indexes. Mode Of Access: World Wide Web.