Markov chains and mixing times

Preface......Page 10
Overview......Page 11
For the Reader......Page 12
For the Instructor......Page 13
Acknowledgements......Page 15
Part I: Basic Methods and Examples......Page 16
1.1. Finite Markov Chains......Page 20
1.2. Random Mapping Representation......Page 23
1.3. Irreducibility and Aperiodicity......Page 25
1.4. Random Walks on Graphs......Page 26
1.5. Stationary Distributions......Page 27
1.6. Reversibility and Time Reversals......Page 31
1.7. Classifying the States of a Markov Chain*......Page 33
Exercises......Page 35
Notes......Page 37
2.1. Gambler\'s Ruin......Page 38
2.2. Coupon Collecting......Page 39
2.3. The Hypercube and the Ehrenfest Urn Model......Page 40
2.4. The Pólya Urn Model......Page 42
2.5. Birth-and-Death Chains......Page 43
2.6. Random Walks on Groups......Page 44
2.7. Random Walks on Z and Reflection Principles......Page 47
Exercises......Page 51
Notes......Page 52
3.2. Metropolis Chains......Page 54
3.3. Glauber Dynamics......Page 57
Notes......Page 61
4.1. Total Variation Distance......Page 64
4.2. Coupling and Total Variation Distance......Page 66
4.3. The Convergence Theorem......Page 69
4.4. Standardizing Distance from Stationarity......Page 70
4.6. Mixing and Time Reversal......Page 72
4.7. Ergodic Theorem*......Page 75
Exercises......Page 76
Notes......Page 77
5.1. Definition......Page 80
5.2. Bounding Total Variation Distance......Page 81
5.3. Examples......Page 82
5.4. Grand Couplings......Page 87
Exercises......Page 90
Notes......Page 91
6.1. Top-to-Random Shuffle......Page 92
6.2. Definitions......Page 93
6.3. Achieving Equilibrium......Page 94
6.4. Strong Stationary Times and Bounding Distance......Page 95
6.5. Examples......Page 97
6.6. Stationary Times and Cesaro Mixing Time*......Page 100
Exercises......Page 101
Notes......Page 102
7.1. Counting and Diameter Bounds......Page 104
7.2. Bottleneck Ratio......Page 105
7.3. Distinguishing Statistics......Page 109
7.4. Examples......Page 113
Notes......Page 115
8.1. The Symmetric Group......Page 116
8.2. Random Transpositions......Page 118
8.3. Riffle Shuffles......Page 123
Exercises......Page 126
Notes......Page 128
9.1. Networks and Reversible Markov Chains......Page 132
9.2. Harmonic Functions......Page 133
9.3. Voltages and Current Flows......Page 134
9.4. Effective Resistance......Page 135
9.5. Escape Probabilities on a Square......Page 140
Exercises......Page 141
Notes......Page 142
10.1. Definition......Page 144
10.2. Random Target Times......Page 145
10.3. Commute Time......Page 147
10.4. Hitting Times for the Torus......Page 150
10.5. Bounding Mixing Times via Hitting Times......Page 151
10.6. Mixing for the Walk on Two Glued Graphs......Page 155
Exercises......Page 156
Notes......Page 158
11.2. The Matthews Method......Page 160
11.3. Applications of the Matthews Method......Page 164
Exercises......Page 168
Notes......Page 169
12.1. The Spectral Representation of a Reversible Transition Matrix......Page 170
12.2. The Relaxation Time......Page 171
12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks......Page 173
12.4. Product Chains......Page 177
12.5. An 2 Bound......Page 180
12.6. Time Averages......Page 182
Exercises......Page 184
Part II: The Plot Thickens......Page 185
13.1. Bounds on Spectral Gap via Contractions......Page 188
13.2. Wilson\'s Method for Lower Bounds......Page 189
13.3. The Dirichlet Form and the Bottleneck Ratio......Page 192
13.4. Simple Comparison of Markov Chains......Page 196
13.5. The Path Method......Page 199
13.6. Expander Graphs*......Page 202
Notes......Page 204
14.1. The Transportation Metric......Page 206
14.2. Path Coupling......Page 208
14.3. Fast Mixing for Colorings......Page 210
14.4. Approximate Counting......Page 212
Exercises......Page 215
Notes......Page 216
15.1. Fast Mixing at High Temperature......Page 218
15.2. The Complete Graph......Page 220
15.3. The Cycle......Page 221
15.4. The Tree......Page 223
15.5. Block Dynamics......Page 225
15.6. Lower Bound for Ising on Square*......Page 228
Exercises......Page 230
Notes......Page 231
16.1. Random Adjacent Transpositions......Page 234
16.2. Shuffling Genes......Page 238
Exercise......Page 243
Notes......Page 244
17.1. Definition and Examples......Page 246
17.2. Optional Stopping Theorem......Page 248
17.3. Applications......Page 250
17.4. Evolving Sets......Page 252
17.5. A General Bound on Return Probabilities......Page 256
17.6. Harmonic Functions and the Doob h-Transform......Page 258
17.7. Strong Stationary Times from Evolving Sets......Page 260
Notes......Page 262
18.1. Definition......Page 264
18.2. Examples of Cutoff......Page 265
18.3. A Necessary Condition for Cutoff......Page 269
18.4. Separation Cutoff......Page 271
Notes......Page 272
19.1. Introduction......Page 274
19.2. Relaxation Time Bounds......Page 275
19.3. Mixing Time Bounds......Page 277
19.4. Examples......Page 279
Notes......Page 280
20.1. Definitions......Page 282
20.2. Continuous-Time Mixing......Page 283
20.3. Spectral Gap......Page 285
20.4. Product Chains......Page 286
Notes......Page 290
21.1. Recurrence and Transience......Page 292
21.2. Infinite Networks......Page 294
21.3. Positive Recurrence and Convergence......Page 296
21.4. Null Recurrence and Convergence......Page 300
21.5. Bounds on Return Probabilities......Page 301
Exercises......Page 302
Notes......Page 303
22.1. Introduction......Page 304
22.2. Monotone CFTP......Page 305
22.3. Perfect Sampling via Coupling from the Past......Page 310
22.4. The Hardcore Model......Page 311
22.5. Random State of an Unknown Markov Chain......Page 313
Notes......Page 314
23.1. The Ising Model......Page 316
23.2. Cutoff......Page 317
23.3. Other Problems......Page 318
A.1. Probability Spaces and Random Variables......Page 320
A.3. Linear Algebra......Page 325
A.4. Miscellaneous......Page 326
B.1. What Is Simulation?......Page 328
B.2. Von Neumann Unbiasing*......Page 329
B.3. Simulating Discrete Distributions and Sampling......Page 330
B.5. Acceptance-Rejection Sampling......Page 331
B.6. Simulating Normal Random Variables......Page 334
B.8. About Random Numbers......Page 335
B.9. Sampling from Large Sets*......Page 336
Exercises......Page 339
Notes......Page 342
Appendix C. Solutions to Selected Exercises......Page 344
Bibliography......Page 368
Notation Index......Page 378
Index......Page 380