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

nexusstc/Markov Chains and Mixing Times/4a326d903ff0974280aa4856f5d17045.pdf

lgli/levin peres wilmer - markov chains and mixing times - 2nd edition draft 2017.pdf

lgrsnf/levin peres wilmer - markov chains and mixing times - 2nd edition draft 2017.pdf

LaTeX with hyperref package

Downloaded from http://pages.uoregon.edu/dlevin/MARKOV/

0

lg2192916

producers:
pdfTeX-1.40.17

{"last_page":461,"publisher":"American Mathematical Society","series":"AMS MBK","volume":"107"}

2018-03-06