Table of contents for Markov chains and mixing times / David A. Levin, Yuval Peres, Elizabeth L. Wilmer.


Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.


Counter
Overview                                                          xii
For the Reader                                                   xiii
For the Instructor                                               xiv
For the Expert                                                   xvi
Acknowledgements                                                   xvii
Part I: Basic Methods and Examples                                    1
Chapter 1. Introduction to Finite Markov Chains                      3
1.1. Finite Markov Chains                                          3
1.2. Random Mapping Representation                                 6
1.3. Irreducibility and Aperiodicity                               8
1.4. Random Walks on Graphs                                        9
1.5. Stationary Distributions                                     10
1.6. Reversibility and Time Reversals                             14
1.7. Classifying the States of a Markov Chain*                    16
Exercises                                                         18
Notes                                                             20
Chapter 2. Classical (and Useful) Markov Chains                     21
2.1. Gambler's Ruin                                               21
2.2. Coupon Collecting                                            22
2.3. The Hypercube and the Ehrenfest Urn Model                    23
2.4. The P6lya Urn Model                                          25
2.5. Birth-and-Death Chains                                       26
2.6. Random Walks on Groups                                       27
2.7. Random Walks on Z and Reflection Principles                  30
Exercises                                                         34
Notes                                                             35
Chapter 3. Markov Chain Monte Carlo: Metropolis and Glauber Chains   37
3.1. Introduction                                                 37
3.2. Metropolis Chains                                            37
3.3. Glauber Dynamics                                             40
Exercises                                                         44
Notes                                                             44
Chapter 4. Introduction to Markov Chain Mixing                       47
4.1. Total Variation Distance                                     47
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
Chapter 10. Hitting Times                                            127
10.1. Definition                                                   127
10.2. Random Target Times                                          128
10.3. Commute Time                                                 130
10.4. Hitting Times for the Torus                                  133
10.5. Bounding Mixing Times via Hitting Times                      134
10.6. Mixing for the Walk on Two Glued Graphs                      138
Exercises                                                          139
Notes                                                              141
Chapter 11. Cover Times                                              143
11.1. Cover Times                                                  143
11.2. The Matthews Method                                          143
11.3. Applications of the Matthews Method                          147
Exercises                                                          151
Notes                                                              152
Chapter 12. Eigenvalues                                              153
12.1. The Spectral Representation of a Reversible Transition Matrix  153
12.2. The Relaxation Time                                          154
12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks   156
12.4. Product Chains                                               160
12.5. An f2 Bound                                                  163
12.6. Time Averages                                                165
Exercises                                                          167
Notes                                                              168
Part II: The Plot Thickens                                           169
Chapter 13. Eigenfunctions and Comparison of Chains                  171
13.1. Bounds on Spectral Gap via Contractions                      171
13.2. Wilson's Method for Lower Bounds                             172
13.3. The Dirichlet Form and the Bottleneck Ratio                  175
13.4. Simple Comparison of Markov Chains                           179
13.5. The Path Method                                              182
13.6. Expander Graphs*                                             185
Exercises                                                          187
Notes                                                              187
Chapter 14. The Transportation Metric and Path Coupling              189
14.1. The Transportation Metric                                    189
14.2. Path Coupling                                                191
14.3. Fast Mixing for Colorings                                    193
14.4. Approximate Counting                                         195
Exercises                                                          198
Notes                                                              199
Chapter 15. The Ising Model                                          201
15.1. Fast Mixing at High Temperature                              201
15.2. The Complete Graph                                           203
15.3. The Cycle                                                   204
15.4. The Tree                                                    206
15.5. Block Dynamics                                              208
15.6. Lower Bound for Ising on Square*                            211
Exercises                                                         213
Notes                                                             214
Chapter 16. From Shuffling Cards to Shuffling Genes                 217
16.1. Random Adjacent Transpositions                              217
16.2. Shuffling Genes                                             221
Exercise                                                          226
Notes                                                             227
Chapter 17. Martingales and Evolving Sets                           229
17.1. Definition and Examples                                     229
17.2. Optional Stopping Theorem                                   231
17.3. Applications                                                233
17.4. Evolving Sets                                               235
17.5. A General Bound on Return Probabilities                     239
17.6. Harmonic Functions and the Doob h-Transform                 241
17.7. Strong Stationary Times from Evolving Sets                  243
Exercises                                                         245
Notes                                                             245
Chapter 18. The Cutoff Phenomenon                                   247
18.1. Definition                                                  247
18.2. Examples of Cutoff                                          248
18.3. A Necessary Condition for Cutoff                            252
18.4. Separation Cutoff                                           254
Exercise                                                          255
Notes                                                             255
Chapter 19. Lamplighter Walks                                       257
19.1. Introduction                                                257
19.2. Relaxation Time Bounds                                      258
19.3. Mixing Time Bounds                                          260
19.4. Examples                                                    262
Notes                                                             263
Chapter 20. Continuous-Time Chains*                                 265
20.1. Definitions                                                 265
20.2. Continuous-Time Mixing                                      266
20.3. Spectral Gap                                                268
20.4. Product Chains                                              269
Exercises                                                         273
Notes                                                             273
Chapter 21. Countable State Space Chains*                           275
21.1. Recurrence and Transience                                   275
21.2. Infinite Networks                                           277
21.3. Positive Recurrence and Convergence                        279
21.4. Null Recurrence and Convergence                            283
21.5. Bounds on Return Probabilities                             284
Exercises                                                        285
Notes                                                            286
Chapter 22. Coupling from the Past                                 287
22.1. Introduction                                               287
22.2. Monotone CFTP                                              288
22.3. Perfect Sampling via Coupling from the Past                293
22.4. The Hardcore Model                                         294
22.5. Random State of an Unknown Markov Chain                    296
Exercise                                                         297
Notes                                                            297
Chapter 23. Open Problems                                          299
23.1. The Ising Model                                            299
23.2. Cutoff                                                     300
23.3. Other Problems                                             301
Appendix A. Background Material                                    303
A.1. Probability Spaces and Random Variables                     303
A.2. Metric Spaces                                               308
A.3. Linear Algebra                                              308
A.4. Miscellaneous                                               309
Appendix B. Introduction to Simulation                              311
B.1. What Is Simulation?                                         311
B.2. Von Neumann Unbiasing*                                      312
B.3. Simulating Discrete Distributions and Sampling              313
B.4. Inverse Distribution Function Method                        314
B.5. Acceptance-Rejection Sampling                               314
B.6. Simulating Normal Random Variables                          317
B.7. Sampling from the Simplex                                   318
B.8. About Random Numbers                                        318
B.9. Sampling from Large Sets*                                   319
Exercises                                                        322
Notes                                                            325
Appendix C. Solutions to Selected Exercises                         327
Bibliography                                                        353
Notation Index                                                      363



Library of Congress subject headings for this publication: Markov processes