Preface 9 Preface to second edition 9 Preface to first edition 9 Overview 11 For the Reader 12 For the Instructor 13 For the Expert 13 Acknowledgements 16 Part I: Basic Methods and Examples 17 Chapter 1. Introduction to Finite Markov Chains 18 1.1. Markov Chains 18 1.2. Random Mapping Representation 21 1.3. Irreducibility and Aperiodicity 23 1.4. Random Walks on Graphs 24 1.5. Stationary Distributions 25 1.6. Reversibility and Time Reversals 29 1.7. Classifying the States of a Markov Chain* 31 Exercises 33 Notes 34 Chapter 2. Classical (and Useful) Markov Chains 37 2.1. Gambler's Ruin 37 2.2. Coupon Collecting 38 2.3. The Hypercube and the Ehrenfest Urn Model 39 2.4. The Pólya Urn Model 41 2.5. Birth-and-Death Chains 42 2.6. Random Walks on Groups 43 2.7. Random Walks on Z and Reflection Principles 46 Exercises 50 Notes 51 Chapter 3. Markov Chain Monte Carlo: Metropolis and Glauber Chains 54 3.1. Introduction 54 3.2. Metropolis Chains 54 3.3. Glauber Dynamics 57 Exercises 61 Notes 61 Chapter 4. Introduction to Markov Chain Mixing 63 4.1. Total Variation Distance 63 4.2. Coupling and Total Variation Distance 65 4.3. The Convergence Theorem 68 4.4. Standardizing Distance from Stationarity 69 4.5. Mixing Time 70 4.6. Mixing and Time Reversal 71 4.7. p Distance and Mixing 72 Exercises 73 Notes 74 Chapter 5. Coupling 76 5.1. Definition 76 5.2. Bounding Total Variation Distance 78 5.3. Examples 78 5.4. Grand Couplings 85 Exercises 89 Notes 90 Chapter 6. Strong Stationary Times 91 6.1. Top-to-Random Shuffle 91 6.2. Markov Chains with Filtrations 92 6.3. Stationary Times 93 6.4. Strong Stationary Times and Bounding Distance 94 6.5. Examples 97 6.6. Stationary Times and Cesaro Mixing Time 100 6.7. Optimal Strong Stationary Times* 101 Exercises 102 Notes 103 Chapter 7. Lower Bounds on Mixing Times 104 7.1. Counting and Diameter Bounds 104 7.2. Bottleneck Ratio 105 7.3. Distinguishing Statistics 108 7.4. Examples 112 Exercises 114 Notes 115 Chapter 8. The Symmetric Group and Shuffling Cards 116 8.1. The Symmetric Group 116 8.2. Random Transpositions 118 8.3. Riffle Shuffles 123 Exercises 126 Notes 128 Chapter 9. Random Walks on Networks 132 9.1. Networks and Reversible Markov Chains 132 9.2. Harmonic Functions 133 9.3. Voltages and Current Flows 134 9.4. Effective Resistance 135 9.5. Escape Probabilities on a Square 140 Exercises 141 Notes 143 Chapter 10. Hitting Times 144 10.1. Definition 144 10.2. Random Target Times 145 10.3. Commute Time 147 10.4. Hitting Times on Trees 150 10.5. Hitting Times for Eulerian Graphs 153 10.6. Hitting Times for the Torus 153 10.7. Bounding Mixing Times via Hitting Times 156 10.8. Mixing for the Walk on Two Glued Graphs 160 Exercises 162 Notes 165 Chapter 11. Cover Times 166 11.1. Definitions 166 11.2. The Matthews Method 166 11.3. Applications of the Matthews Method 168 11.4. Spanning Tree Bound for Cover Time 170 11.5. Waiting for all patterns in coin tossing 172 Exercises 174 Notes 174 Chapter 12. Eigenvalues 177 12.1. The Spectral Representation of a Reversible Transition Matrix 177 12.2. The Relaxation Time 179 12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks 181 12.4. Product Chains 185 12.5. Spectral Formula for the Target Time 188 12.6. An 2 Bound 188 12.7. Time Averages 189 Exercises 193 Notes 194 Part II: The Plot Thickens 195 Chapter 13. Eigenfunctions and Comparison of Chains 196 13.1. Bounds on Spectral Gap via Contractions 196 13.2. The Dirichlet Form and the Bottleneck Ratio 197 13.3. Simple Comparison of Markov Chains 201 13.4. The Path Method 203 13.5. Wilson's Method for Lower Bounds 208 13.6. Expander Graphs* 212 Exercises 214 Notes 215 Chapter 14. The Transportation Metric and Path Coupling 217 14.1. The Transportation Metric 217 14.2. Path Coupling 219 14.3. Rapid Mixing for Colorings 222 14.4. Approximate Counting 225 Exercises 228 Notes 230 Chapter 15. The Ising Model 231 15.1. Fast Mixing at High Temperature 231 15.2. The Complete Graph 234 15.3. The Cycle 235 15.4. The Tree 236 15.5. Block Dynamics 239 15.6. Lower Bound for Ising on Square* 242 Exercises 244 Notes 245 Chapter 16. From Shuffling Cards to Shuffling Genes 248 16.1. Random Adjacent Transpositions 248 16.2. Shuffling Genes 252 Exercise 257 Notes 257 Chapter 17. Martingales and Evolving Sets 259 17.1. Definition and Examples 259 17.2. Optional Stopping Theorem 260 17.3. Applications 262 17.4. Evolving Sets 265 17.5. A General Bound on Return Probabilities 269 17.6. Harmonic Functions and the Doob h-Transform 271 17.7. Strong Stationary Times from Evolving Sets 272 Exercises 275 Notes 275 Chapter 18. The Cutoff Phenomenon 277 18.1. Definition 277 18.2. Examples of Cutoff 278 18.3. A Necessary Condition for Cutoff 283 18.4. Separation Cutoff 284 Exercises 285 Notes 285 Chapter 19. Lamplighter Walks 288 19.1. Introduction 288 19.2. Relaxation Time Bounds 289 19.3. Mixing Time Bounds 291 19.4. Examples 293 Exercises 293 Notes 294 Chapter 20. Continuous-Time Chains* 296 20.1. Definitions 296 20.2. Continuous-Time Mixing 297 20.3. Spectral Gap 300 20.4. Product Chains 301 Exercises 305 Notes 306 Chapter 21. Countable State Space Chains* 307 21.1. Recurrence and Transience 307 21.2. Infinite Networks 309 21.3. Positive Recurrence and Convergence 311 21.4. Null Recurrence and Convergence 316 21.5. Bounds on Return Probabilities 317 Exercises 318 Notes 320 Chapter 22. Monotone Chains 321 22.1. Introduction 321 22.2. Stochastic Domination 322 22.3. Definition and Examples of Monotone Markov Chains 324 22.4. Positive Correlations 325 22.5. The Second Eigenfunction 329 22.6. Censoring Inequality 330 22.7. Lower bound on 335 22.8. Proof of Strassen's Theorem 336 22.9. Exercises 337 22.10. Notes 338 Chapter 23. The Exclusion Process 339 23.1. Introduction 339 23.2. Mixing Time of k-exclusion on the n-path 344 23.3. Biased Exclusion 345 23.4. Exercises 349 23.5. Notes 350 Chapter 24. Cesàro Mixing Time, Stationary Times, and Hitting Large Sets 351 24.1. Introduction 351 24.2. Equivalence of tstop, tCes and tG for reversible chains 353 24.3. Halting States and Mean-Optimal Stopping Times 355 24.4. Regularity Properties of Geometric Mixing Times 356 24.5. Equivalence of tG and tH 357 24.6. Upward Skip-Free Chains 358 24.7. tH() are comparable for 1/2. 359 24.8. An Upper Bound on trel 360 24.9. Application to Robustness of Mixing 361 Exercises 362 Notes 362 Chapter 25. Coupling from the Past 364 25.1. Introduction 364 25.2. Monotone CFTP 365 25.3. Perfect Sampling via Coupling from the Past 370 25.4. The Hardcore Model 371 25.5. Random State of an Unknown Markov Chain 373 Exercise 374 Notes 374 Chapter 26. Open Problems 375 26.1. The Ising Model 375 26.2. Cutoff 376 26.3. Other Problems 376 26.4. Update: Previously Open Problems 377 Appendix A. Background Material 379 A.1. Probability Spaces and Random Variables 379 A.2. Conditional Expectation 385 A.3. Strong Markov Property 388 A.4. Metric Spaces 389 A.5. Linear Algebra 390 A.6. Miscellaneous 390 Exercises 390 Appendix B. Introduction to Simulation 391 B.1. What Is Simulation? 391 B.2. Von Neumann Unbiasing* 392 B.3. Simulating Discrete Distributions and Sampling 393 B.4. Inverse Distribution Function Method 394 B.5. Acceptance-Rejection Sampling 394 B.6. Simulating Normal Random Variables 396 B.7. Sampling from the Simplex 398 B.8. About Random Numbers 398 B.9. Sampling from Large Sets* 399 Exercises 402 Notes 405 Appendix C. Ergodic Theorem 406 C.1. Ergodic Theorem* 406 Exercise 407 Appendix D. Solutions to Selected Exercises 408 Bibliography 438 Notation Index 453 Index 455

October 2017, Front Cover Mathematics REsearch Communities Quantitative Linear Algebra Table of Contents Front matter The Rigidity of Frameworks: Theory and Applications by Jessica Sidman and Audrey St. John AMS Short Course Dido's Problem and Its Impact on Modern Mathematics by Catherine Bandle Call for Applications Associate Editor, Mathematical Reviews Ensuring That Mathematics is Relevant ina World of Data Science AMS Centennial Fellowship Fund Flexibility in the Mathematics Major Would benefit Students and Society Statistics on Women Mathematicians Euphemia Lofton Haynes, Bringing Education Closer to the Goal of Perfection" Call for Suggestions Evelyn Lamb Interview by Alexander Diaz-Lopez What is...? Perimeter by Frank Morgan Gerrymandering, Sandwiches, and Topology by Pablo Soberion. AMS Graduate Student Blog Free Shipping for AMS Members AMS Short Course IAS Membership A Formula Goes to Court: Partisan Gerrymandering and the Efficiency Gap by Mira Bernstein and Moon Duchin AMS on Social Networks Report of the Treasurer (2016) London Mathematical Society Inside the AMS Mathematics People Latinos and Hispanics int he Mathematical Sciences Mathematics Opportunities AMS Employment Center The Mathematician's Shiva, A Review by Dennis DeTurck Bookshelf The Back Page New Publications Offered by the AMS Classified Advertisements Mathematics Calendar Meetings & Conferences of the AMS October Table of Contents Meetings & Conferences of the AMS Program at a Glance AMS Dinner JMM Hotel Reservations JMM Advance REgistration/housing In the Next Issue Graduate Studies in Mathematics

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

本书是对Markov链理论的现代处理方法的导引,该方法的主要目标是确定一个Markov链收敛到作为态空间体积和几何之函数的平稳分布的收敛速率。作者发展了估计收敛时间的关键工具,包括耦合、强平稳时间以及谱方法:一有可能,便强调概率论式的方法。本书包括了许多例题并对统计力学的中心模型给出了简短介绍;还讲述了网络上的随机游动,包括击中和掩盖时间,以及对洗牌的各种方法的分析。至于预备知识,作者假定了对概率论的适度了解以及大学水平的线性代数。本书打算将这个活跃的研究领域的激情带给大范围的受众。

<p><P>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.</p>

<p><P>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.</p>

<p><P>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.</p>