2009;
371 pp;
Hardcover

MSC: Primary 60; 65; 68; 82;

Print ISBN: 978-0-8218-4739-8

Product Code: MBK/58

List Price: $71.00

Individual Member Price: $56.80

**Electronic ISBN: 978-1-4704-1204-3
Product Code: MBK/58.E**

List Price: $71.00

Individual Member Price: $56.80

#### You may also like

#### Supplemental Materials

# Markov Chains and Mixing Times

Share this page
*David A. Levin; Yuval Peres; Elizabeth L. Wilmer*

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.

#### Table of Contents

# Table of Contents

## Markov Chains and Mixing Times

- Cover Cover11 free
- Title page iii5 free
- Contents v7 free
- Preface xi13 free
- Acknowledgments xvii19 free
- Part I: Basic Methods and Examples 121 free
- Introduction to finite Markov chains 323
- Classical (and useful) Markov chains 2141
- Markov chain Monte Carlo: Metropolis and Glauber chains 3757
- Introduction to Markov chain mixing 4767
- Coupling 6383
- Strong stationary times 7595
- Lower bounds on mixing times 87107
- The symmetric group and shuffling cards 99119
- Random walks on networks 115135
- Hitting times 127147
- Cover times 143163
- Eigenvalues 153173
- Part II: The Plot Thickens 169189
- Eigenfunctions and comparison of chains 171191
- The transportation metric and path coupling 189209
- The Ising model 201221
- From shuffling cards to shuffling genes 217237
- Martingales and evolving sets 229249
- The cut-off phenomenon 247267
- Lamplighter walks 257277
- Continuous-time chains 265285
- Countable state-space chains 275295
- Coupling from the past 287307
- Open problems 299319
- Appendix A: Background material 303323
- Appendix B: Introduction to Simulation 311331
- Appendix C: Solutions to selected exercises 327347
- Bibliography 353373
- Notation Index 363383
- Index 365385 free
- Back Cover Back Cover1392

#### Readership

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

#### 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 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