2017;
447 pp;
Hardcover

MSC: Primary 60; 65; 68; 82;

Print ISBN: 978-1-4704-2962-1

Product Code: MBK/107

List Price: $84.00

AMS Member Price: $67.20

MAA Member Price: $75.60

**Electronic ISBN: 978-1-4704-4232-3
Product Code: MBK/107.E**

List Price: $84.00

AMS Member Price: $67.20

MAA Member Price: $75.60

#### You may also like

#### Supplemental Materials

# Markov Chains and Mixing Times: Second Edition

Share this page
*David A. Levin; Yuval Peres*

This book is an introduction to the modern theory of Markov chains,
whose goal is to determine the rate of convergence to the stationary
distribution, as a function of state space size and geometry. This
topic has important connections to combinatorics, statistical physics,
and theoretical computer science. Many of the techniques presented
originate in these disciplines.

The central tools for estimating convergence times, including
coupling, strong stationary times, and spectral methods, are
developed. The authors discuss many examples, including card shuffling and the
Ising model, from statistical mechanics, and present the connection of
random walks to electrical networks and apply it to estimate hitting
and cover times.

The first edition has been used in courses in mathematics and
computer science departments of numerous universities. The second
edition features three new chapters (on monotone chains, the exclusion
process, and stationary times) and also includes smaller additions and
corrections throughout. Updated notes at the end of each chapter
inform the reader of recent research developments.

#### Readership

Undergraduate and graduate students interested in the modern theory of Markov chains.

#### Reviews & Endorsements

Mixing times are an active research topic within many fields from statistical physics to the theory of algorithms, as well as having intrinsic interest within mathematical probability and exploiting discrete analogs of important geometry concepts. The first edition became an instant classic, being accessible to advanced undergraduates and yet bringing readers close to current research frontiers. This second edition adds chapters on monotone chains, the exclusion process and hitting time parameters. Having both exercises and citations to important research papers it makes an outstanding basis for either a lecture course or self-study.

-- David Aldous, University of California, Berkeley

Mixing time is the key to Markov chain Monte Carlo, the queen of approximation techniques. With new chapters on monotone chains, exclusion processes, and set-hitting, Markov Chains and Mixing Times is more comprehensive and thus more indispensable than ever. Prepare for an eye-opening mathematical tour!

-- Peter Winkler, Dartmouth College

The study of finite Markov chains has recently attracted increasing interest from a variety of researchers. This is the second edition of a very valuable book on the subject. The main focus is on the mixing time of Markov chains, but there is a lot of additional material.

In this edition, the authors have taken the opportunity to add new material and bring the reader up to date on the latest research. I have used the first edition in a graduate course and I look forward to using this edition for the same purpose in the near future.

-- Alan Frieze, Carnegie Mellon University

*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

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

#### Table of Contents

# Table of Contents

## Markov Chains and Mixing Times: Second Edition

Table of Contents pages: 1 2

- Cover Cover11
- Title page i2
- Contents iii4
- Preface ix10
- Acknowledgements xvi17
- Part I: Basic Methods and Examples 118
- Chapter 1. Introduction to Finite Markov Chains 219
- Chapter 2. Classical (and Useful) Markov Chains 2138
- Chapter 3. Markov Chain Monte Carlo: Metropolis and Glauber Chains 3855
- Chapter 4. Introduction to Markov Chain Mixing 4764
- Chapter 5. Coupling 6077
- Chapter 6. Strong Stationary Times 7592
- Chapter 7. Lower Bounds on Mixing Times 87104
- Chapter 8. The Symmetric Group and Shuffling Cards 99116
- Chapter 9. Random Walks on Networks 115132
- Chapter 10. Hitting Times 127144
- 10.1. Definition 127144
- 10.2. Random Target Times 128145
- 10.3. Commute Time 130147
- 10.4. Hitting Times on Trees 133150
- 10.5. Hitting Times for Eulerian Graphs 135152
- 10.6. Hitting Times for the Torus 136153
- 10.7. Bounding Mixing Times via Hitting Times 139156
- 10.8. Mixing for the Walk on Two Glued Graphs 143160
- Exercises 145162
- Notes 147164

- Chapter 11. Cover Times 149166
- Chapter 12. Eigenvalues 160177
- 12.1. The Spectral Representation of a Reversible Transition Matrix 160177
- 12.2. The Relaxation Time 162179
- 12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks 164181
- 12.4. Product Chains 168185
- 12.5. Spectral Formula for the Target Time 171188
- 12.6. An ℓ² Bound 171188
- 12.7. Time Averages 172189
- Exercises 176193
- Notes 177194

- Part II: The Plot Thickens 179196
- Chapter 13. Eigenfunctions and Comparison of Chains 180197
- Chapter 14. The Transportation Metric and Path Coupling 201218
- Chapter 15. The Ising Model 216233
- Chapter 16. From Shuffling Cards to Shuffling Genes 233250
- Chapter 17. Martingales and Evolving Sets 244261
- 17.1. Definition and Examples 244261
- 17.2. Optional Stopping Theorem 245262
- 17.3. Applications 247264
- 17.4. Evolving Sets 250267
- 17.5. A General Bound on Return Probabilities 255272
- 17.6. Harmonic Functions and the Doob ℎ-Transform 257274
- 17.7. Strong Stationary Times from Evolving Sets 258275
- Exercises 260277
- Notes 260277

- Chapter 18. The Cutoff Phenomenon 262279
- Chapter 19. Lamplighter Walks 273290
- Chapter 20. Continuous-Time Chains* 281298
- Chapter 21. Countable State Space Chains* 292309
- Chapter 22. Monotone Chains 306323
- 22.1. Introduction 306323
- 22.2. Stochastic Domination 307324
- 22.3. Definition and Examples of Monotone Markov Chains 309326
- 22.4. Positive Correlations 310327
- 22.5. The Second Eigenfunction 314331
- 22.6. Censoring Inequality 315332
- 22.7. Lower Bound on 𝑑 320337
- 22.8. Proof of Strassen’s Theorem 321338
- Exercises 322339
- Notes 323340

- Chapter 23. The Exclusion Process 324341

Table of Contents pages: 1 2