vi CONTENTS 4.2. Coupling and Total Variation Distance 49 4.3. The Convergence Theorem 52 4.4. Standardizing Distance from Stationarity 53 4.5. Mixing Time 55 4.6. Mixing and Time Reversal 55 4.7. Ergodic Theorem* 58 Exercises 59 Notes 60 Chapter 5. Coupling 63 5.1. Definition 63 5.2. Bounding Total Variation Distance 64 5.3. Examples 65 5.4. Grand Couplings 70 Exercises 73 Notes 74 Chapter 6. Strong Stationary Times 75 6.1. Top-to-Random Shuffle 75 6.2. Definitions 76 6.3. Achieving Equilibrium 77 6.4. Strong Stationary Times and Bounding Distance 78 6.5. Examples 80 6.6. Stationary Times and Cesaro Mixing Time* 83 Exercises 84 Notes 85 Chapter 7. Lower Bounds on Mixing Times 87 7.1. Counting and Diameter Bounds 87 7.2. Bottleneck Ratio 88 7.3. Distinguishing Statistics 92 7.4. Examples 96 Exercises 98 Notes 98 Chapter 8. The Symmetric Group and Shuffling Cards 99 8.1. The Symmetric Group 99 8.2. Random Transpositions 101 8.3. Riffle Shuffles 106 Exercises 109 Notes 111 Chapter 9. Random Walks on Networks 115 9.1. Networks and Reversible Markov Chains 115 9.2. Harmonic Functions 116 9.3. Voltages and Current Flows 117 9.4. Effective Resistance 118 9.5. Escape Probabilities on a Square 123 Exercises 124 Notes 125
Previous Page Next Page