Markov Chains and Mixing Times

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