AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Markov Chains and Mixing Times

About this Title

David A. Levin, University of Oregon, Eugene, OR, Yuval Peres, Microsoft Research, Redmond, WA and Elizabeth L. Wilmer, Oberlin College, Oberlin, OH

Publication: Miscellaneous Books
Publication Year: 2009; Volume 58
ISBNs: 978-0-8218-4739-8 (print); 978-1-4704-1204-3 (online)
DOI: https://doi.org/10.1090/mbk/058
MathSciNet review: MR2466937
MSC: Primary 60J10; Secondary 60-01, 60J05, 60K35, 60K37, 68U20, 68W20

Read more about this volume

Table of Contents

Front/Back Matter

• View this volume's front and back matter

Part I. Basic Methods and Examples

• 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

Part II. The Plot Thickens

• 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

View full volume PDF