Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Markov Chains and Mixing Times
 
David A. Levin University of Oregon, Eugene, OR
Yuval Peres Microsoft Research, Redmond, WA and University of Washington, Seattle, WA and University of California, Berkeley, Berkeley, CA
Elizabeth L. Wilmer Oberlin College, Oberlin, OH
Markov Chains and Mixing Times
Now available in new edition: MBK/107
Markov Chains and Mixing Times
Click above image for expanded view
Markov Chains and Mixing Times
David A. Levin University of Oregon, Eugene, OR
Yuval Peres Microsoft Research, Redmond, WA and University of Washington, Seattle, WA and University of California, Berkeley, Berkeley, CA
Elizabeth L. Wilmer Oberlin College, Oberlin, OH
Now available in new edition: MBK/107
  • Book Details
     
     
    2009; 371 pp
    MSC: Primary 60; 65; 68; 82;

    Now available in Second Edition: MBK/107

    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.

    Readership

    Undergraduates, graduate students, and research mathematicians interested in probability, combinatorics, simulation, computer science, and Markov chain.

  • Table of Contents
     
     
    • 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
  • Reviews
     
     
    • Markov Chains and Mixing Times is a magical book, managing to be both friendly and deep. It gently introduces probabilistic techniques so that an outsider can follow. At the same time, it is the first book covering the geometric theory of Markov chains and has much that will be new to experts. It is certainly THE book that I will use to teach from. I recommend it to all comers, an amazing achievement.

      Persi Diaconis, Mary V. Sunseri Professor of Statistics and Mathematics, Stanford University
    • A superb introduction to Markov chains which treats riffle shuffling and stationary times...

      Sami Assaf, University of Southern California, Persi Diaconis, Stanford University, and Kannan Soundararajan, Stanford University, in their paper "Riffle Shuffles with Biased Cuts"
    • In this book, [the authors] rapidly take a well-prepared undergraduate to the frontiers of research. Short, focused chapters with clear logical dependencies allow readers to use the book in multiple ways.

      CHOICE Magazine
    • This book is a beautiful introduction to Markov chains and the analysis of their convergence towards a stationary distribution. Personally, I enjoyed very much the lucid and clear writing style of the exposition in combination with full mathematical rigor and the fascinating relations of the theory of Markov chains to several other mathematical areas.

      Zentralblatt MATH
    • Throughout the book, the authors generously provide concrete examples that motivate theory and illustrate ideas. I expect this superb book to be widely used in graduate courses around the world, and to become a standard reference.

      Mathematical Reviews
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Desk Copy – for instructors who have adopted an AMS textbook for a course
    Examination Copy – for faculty considering an AMS textbook for a course
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
2009; 371 pp
MSC: Primary 60; 65; 68; 82;

Now available in Second Edition: MBK/107

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.

Readership

Undergraduates, graduate students, and research mathematicians interested in probability, combinatorics, simulation, computer science, and Markov chain.

  • 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
  • Markov Chains and Mixing Times is a magical book, managing to be both friendly and deep. It gently introduces probabilistic techniques so that an outsider can follow. At the same time, it is the first book covering the geometric theory of Markov chains and has much that will be new to experts. It is certainly THE book that I will use to teach from. I recommend it to all comers, an amazing achievement.

    Persi Diaconis, Mary V. Sunseri Professor of Statistics and Mathematics, Stanford University
  • A superb introduction to Markov chains which treats riffle shuffling and stationary times...

    Sami Assaf, University of Southern California, Persi Diaconis, Stanford University, and Kannan Soundararajan, Stanford University, in their paper "Riffle Shuffles with Biased Cuts"
  • In this book, [the authors] rapidly take a well-prepared undergraduate to the frontiers of research. Short, focused chapters with clear logical dependencies allow readers to use the book in multiple ways.

    CHOICE Magazine
  • This book is a beautiful introduction to Markov chains and the analysis of their convergence towards a stationary distribution. Personally, I enjoyed very much the lucid and clear writing style of the exposition in combination with full mathematical rigor and the fascinating relations of the theory of Markov chains to several other mathematical areas.

    Zentralblatt MATH
  • Throughout the book, the authors generously provide concrete examples that motivate theory and illustrate ideas. I expect this superb book to be widely used in graduate courses around the world, and to become a standard reference.

    Mathematical Reviews
Review Copy – for publishers of book reviews
Desk Copy – for instructors who have adopted an AMS textbook for a course
Examination Copy – for faculty considering an AMS textbook for a course
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
You may be interested in...
Please select which format for which you are requesting permissions.