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.

nexusstc/Markov Chains and Mixing Times/7248ec24264428bc80506c4c32bac837.pdf

lgli/markov chains and mixing times

lgrsnf/markov chains and mixing times

David Asher Levin; Y Peres; Elizabeth L Wilmer; American Mathematical Society

Levin, David Asher; Peres, Y.; Wilmer, Elizabeth L.

LaTeX with hyperref package

Levin, David Asher , 1971-

Education Development Center, Incorporated

American Mathematical Society, Providence, R.I., 2009

Miscellaneous Books, no. 58, Providence, R.I, ©2009

United States, United States of America

Providence, R.I, Rhode Island, 2008

Providence, R.I, Rhode Island, 2009

Providence, R.I., London, 2008

Providence, R.I, c2009

0

lg869364

producers:
dvips + AFPL Ghostscript 8.51

{"edition":"1","isbns":["0821847392","1470412047","9780821847398","9781470412043"],"last_page":387,"publisher":"American Mathematical Society"}

Includes bibliographical references and index.

"With a chapter on coupling from the past by James G. Propp and David B. Wilson."
Includes bibliographical references (p. 353-361) and indexes.

Preface 9
Overview 10
For the Reader 11
For the Instructor 12
For the Expert 14
Acknowledgements 14
Part I: Basic Methods and Examples 15
Chapter 1. Introduction to Finite Markov Chains 19
1.1. Finite Markov Chains 19
1.2. Random Mapping Representation 22
1.3. Irreducibility and Aperiodicity 24
1.4. Random Walks on Graphs 25
1.5. Stationary Distributions 26
1.6. Reversibility and Time Reversals 30
1.7. Classifying the States of a Markov Chain* 32
Exercises 34
Notes 36
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 53
3.1. Introduction 53
3.2. Metropolis Chains 53
3.3. Glauber Dynamics 56
Exercises 60
Notes 60
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 71
4.6. Mixing and Time Reversal 71
4.7. Ergodic Theorem* 74
Exercises 75
Notes 76
Chapter 5. Coupling 79
5.1. Definition 79
5.2. Bounding Total Variation Distance 80
5.3. Examples 81
5.4. Grand Couplings 86
Exercises 89
Notes 90
Chapter 6. Strong Stationary Times 91
6.1. Top-to-Random Shuffle 91
6.2. Definitions 92
6.3. Achieving Equilibrium 93
6.4. Strong Stationary Times and Bounding Distance 94
6.5. Examples 96
6.6. Stationary Times and Cesaro Mixing Time* 99
Exercises 100
Notes 101
Chapter 7. Lower Bounds on Mixing Times 103
7.1. Counting and Diameter Bounds 103
7.2. Bottleneck Ratio 104
7.3. Distinguishing Statistics 108
7.4. Examples 112
Exercises 114
Notes 114
Chapter 8. The Symmetric Group and Shuffling Cards 115
8.1. The Symmetric Group 115
8.2. Random Transpositions 117
8.3. Riffle Shuffles 122
Exercises 125
Notes 127
Chapter 9. Random Walks on Networks 131
9.1. Networks and Reversible Markov Chains 131
9.2. Harmonic Functions 132
9.3. Voltages and Current Flows 133
9.4. Effective Resistance 134
9.5. Escape Probabilities on a Square 139
Exercises 140
Notes 141
Chapter 10. Hitting Times 143
10.1. Definition 143
10.2. Random Target Times 144
10.3. Commute Time 146
10.4. Hitting Times for the Torus 149
10.5. Bounding Mixing Times via Hitting Times 150
10.6. Mixing for the Walk on Two Glued Graphs 154
Exercises 155
Notes 157
Chapter 11. Cover Times 159
11.1. Cover Times 159
11.2. The Matthews Method 159
11.3. Applications of the Matthews Method 163
Exercises 167
Notes 168
Chapter 12. Eigenvalues 169
12.1. The Spectral Representation of a Reversible Transition Matrix 169
12.2. The Relaxation Time 170
12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks 172
12.4. Product Chains 176
12.5. An 2 Bound 179
12.6. Time Averages 181
Exercises 183
Notes 184
Part II: The Plot Thickens 184
Chapter 13. Eigenfunctions and Comparison of Chains 187
13.1. Bounds on Spectral Gap via Contractions 187
13.2. Wilson's Method for Lower Bounds 188
13.3. The Dirichlet Form and the Bottleneck Ratio 191
13.4. Simple Comparison of Markov Chains 195
13.5. The Path Method 198
13.6. Expander Graphs* 201
Exercises 203
Notes 203
Chapter 14. The Transportation Metric and Path Coupling 205
14.1. The Transportation Metric 205
14.2. Path Coupling 207
14.3. Fast Mixing for Colorings 209
14.4. Approximate Counting 211
Exercises 214
Notes 215
Chapter 15. The Ising Model 217
15.1. Fast Mixing at High Temperature 217
15.2. The Complete Graph 219
15.3. The Cycle 220
15.4. The Tree 222
15.5. Block Dynamics 224
15.6. Lower Bound for Ising on Square* 227
Exercises 229
Notes 230
Chapter 16. From Shuffling Cards to Shuffling Genes 233
16.1. Random Adjacent Transpositions 233
16.2. Shuffling Genes 237
Exercise 242
Notes 243
Chapter 17. Martingales and Evolving Sets 245
17.1. Definition and Examples 245
17.2. Optional Stopping Theorem 247
17.3. Applications 249
17.4. Evolving Sets 251
17.5. A General Bound on Return Probabilities 255
17.6. Harmonic Functions and the Doob h-Transform 257
17.7. Strong Stationary Times from Evolving Sets 259
Exercises 261
Notes 261
Chapter 18. The Cutoff Phenomenon 263
18.1. Definition 263
18.2. Examples of Cutoff 264
18.3. A Necessary Condition for Cutoff 268
18.4. Separation Cutoff 270
Exercise 271
Notes 271
Chapter 19. Lamplighter Walks 273
19.1. Introduction 273
19.2. Relaxation Time Bounds 274
19.3. Mixing Time Bounds 276
19.4. Examples 278
Notes 279
Chapter 20. Continuous-Time Chains* 281
20.1. Definitions 281
20.2. Continuous-Time Mixing 282
20.3. Spectral Gap 284
20.4. Product Chains 285
Exercises 289
Notes 289
Chapter 21. Countable State Space Chains* 291
21.1. Recurrence and Transience 291
21.2. Infinite Networks 293
21.3. Positive Recurrence and Convergence 295
21.4. Null Recurrence and Convergence 299
21.5. Bounds on Return Probabilities 300
Exercises 301
Notes 302
Chapter 22. Coupling from the Past 303
22.1. Introduction 303
22.2. Monotone CFTP 304
22.3. Perfect Sampling via Coupling from the Past 309
22.4. The Hardcore Model 310
22.5. Random State of an Unknown Markov Chain 312
Exercise 313
Notes 313
Chapter 23. Open Problems 315
23.1. The Ising Model 315
23.2. Cutoff 316
23.3. Other Problems 317
Appendix A. Background Material 319
A.1. Probability Spaces and Random Variables 319
A.2. Metric Spaces 324
A.3. Linear Algebra 324
A.4. Miscellaneous 325
Appendix B. Introduction to Simulation 327
B.1. What Is Simulation? 327
B.2. Von Neumann Unbiasing* 328
B.3. Simulating Discrete Distributions and Sampling 329
B.4. Inverse Distribution Function Method 330
B.5. Acceptance-Rejection Sampling 330
B.6. Simulating Normal Random Variables 333
B.7. Sampling from the Simplex 334
B.8. About Random Numbers 334
B.9. Sampling from Large Sets* 335
Exercises 338
Notes 341
Appendix C. Solutions to Selected Exercises 343
Bibliography 367
Notation Index 377
Index 379

Chapter 1. Introduction To Finite Markov Chains Chapter 2. Classical (and Useful) Markov Chains Chapter 3. Markov Chain Monte Carlo: Metropolis And Glauber Chains Chapter 4. Introduction To Markov Chain Mixing Chapter 5. Coupling Chapter 6. Strong Stationary Times Chapter 7. Lower Bounds On Mixing Times Chapter 8. The Symmetric Group And Shuffling Cards Chapter 9. Random Walks On Networks Chapter 10. Hitting Times Chapter 11. Cover Times Chapter 12. Eigenvalues Chapter 13. Eigenfunctions And Comparison Of Chains Chapter 14. The Transportation Metric And Path Coupling Chapter 15. The Ising Model Chapter 16. From Shuffling Cards To Shuffling Genes Chapter 17. Martingales And Evolving Sets Chapter 18. The Cutoff Phenomenon Chapter 19. Lamplighter Walks Chapter 20. Continuous-time Chains Chapter 21. Countable State Space Chains Chapter 22. Coupling From The Past Chapter 23. Open Problems Appendix A. Background Material Appendix B. Introduction To Simulation Appendix C. Solutions To Selected Exercises. David A. Levin, Yuval Peres, Elizabeth L. Wilmer. With A Chapter On Coupling From The Past By James G. Propp And David B. Wilson. Includes Bibliographical References (pages 353-361) And Indexes. Mode Of Access: World Wide Web.

2012-11-28