Preface Overview For the Reader For the Instructor For the Expert Acknowledgements Part Ⅰ： Basic Methods and Examples Chapter 1． Introduction to Finite Markov Chains 1．1． Finite Markov Chains 1．2． Random Mapping Representation 1．3． Irreducibility and Aperiodicity 1．4． Random Walks on Graphs 1．5． Stationary Distributions 1．6． Reversibility and Time Reversals 1．7． Classifying the States of a Markov Chain Exercises Notes Chapter 2． Classical （and Useful） Markov Chains 2．1． Gambler's Ruin 2．2． Coupon Collecting 2．3． The Hypercube and the Ehrenfest Urn Model 2．4． The Polya Urn Model 2．5． Birth-and-Death Chains 2．6． Random Walks on Groups 2．7． Random Walks on Z and Reflection Principles Exercises Notes Chapter 3． Markov Chain Monte Carlo： Metropolis and Glauber Chains 3．1． Introduction 3．2． Metropolis Chains 3．3． Glauber Dynamics Exercises Notes Chapter 4． Introduction to Markov Chain Mixing 4．1． Total Variation Distance 4．2． Coupling and Total Variation Distance 4．3． The Convergence Theorem 4．4． Standardizing Distance from Stationarity 4．5． Mixing Time 4．6． Mixing and Time Reversal 4．7． Ergodic Theorem* Exercises Notes Chapter 5． Coupling 5．1． Definition 5．2． Bounding Total．Variation Distance 5．3． Examples 5．4． Grand Couplings Exercises Notes Chapter 6． Strong Stationary Times 6．1． Top-to-Random Shuffle 6．2． Definitions 6．3． Achieving Equilibrium 6．4． Strong Stationary Times and Bounding Distance 6．5． Examples 6．6． Stationary Times and Cesaro Mixing Time Exercises Notes Chapter 7． Lower Bounds on Mixing Times 7．1． Counting and Diameter Bounds 7．2． Bottleneck Ratio 7．3． Distinguishing Statistics 7．4． Examples Exercises Notes Chapter 8． The Symmetric Group and Shuffling Cards 8．1． The Symmetric Group 8．2． Random Transpositions 8．3． Riffle Shuffles Exercises Notes Chapter 9． Random Walks on Networks 9．1． Networks and Reversible Markov Chains 9．2． Harmonic Functions 9．3． Voltages and Current Flows 9．4． Effective Resistance 9．5． Escape Probabilities on a Square Exercises Notes Chapter 10． Hitting Times 10．1． Definition 10．2． Random Target Times 10．3． Commute Time 10．4． Hitting Times for the Torus 10．5． Bounding Mixing Times via Hitting Times 10．6． Mixing for the Walk on Two Glued Graphs Exercises Notes Chapter 11． Cover Times 11．1． Cover Times 11．2． The Matthews Method 11．3． Applications of the Matthews Method Exercises Notes Chapter 12． Eigenvalues 12．1． The Spectral Representation of a Reversible Transition Matrix 12．2． The Relaxation Time 12．3． Eigenvalues and Eigenfunctions of Some Simple Random Walks 12．4． Product Chains 12．5． An l2 Bound 12．6． Time Averages Exercises Notes Part Ⅱ： The Plot Thickens Chapter 13． Eigenfunctions and Comparison of Chains 13．1． Bounds on Spectral Gap via Contractions 13．2． Wilson's Method for Lower Bounds 13．3． The Dirichlet Form and the Bottleneck Ratio 13．4． Simple Comparison of Markov Chains 13．5． The Path Method 13．6． Expander Graphs Exercises Notes Chapter 14． The Transportation Metric and Path Coupling 14．1． The Transportation Metric 14．2． Path Coupling 14．3． Fast Mixing for Colorings 14．4． Approximate Counting Exercises Notes Chapter 15． The Ising Model 15．1． Fast Mixing at High Temperature 15．2． The Complete Graph 15．3． The Cycle 15．4． The Tree 15．5． Block Dynamics 15．6． Lower Bound for Ising on Square Exercises Notes Chapter 16． From Shuffling Cards to Shuffling Genes 16．1． Random Adjacent Transpositions 16．2． Shuffling Genes Exercise Notes Chapter 17． Martingales and Evolving Sets 17．1． Definition and Examples 17．2． Optional Stopping Theorem 17．3． Applications 17．4． Evolving Sets 17．5． A General Bound on Return Probabilities 17．6． Harmonic Fhnctions and the Doob h-Transform 17．7． Strong Stationary Times from Evolving Sets Exercises Notes Chapter 18． The Cutoff Phenomenon 18．1． Definition 18．2． Examples of Cutoff 18．3． A Necessary Condition for Cutoff 18．4． Separation Cutoff Exercise Notes Chapter 19． Lamplighter Walks 19．1． Introduction 19．2． Relaxation Time Bounds 19．3． Mixing Time Bounds 19．4． Examples Notes Chapter 20． Continuous-Time Chains 20．1． Definitions 20．2． Continuous-Time Mixing 20．3． Spectral Gap 20．4． Product Chains Exercises Notes Chapter 21． Countable State Space Chains 21．1． Recurrence and Transience 21．2． Infinite Networks 21．3． Positive Recurrence and Convergence 21．4． Null Recurrence and Convergence 21．5． Bounds on Return Probabilities Exercises Notes Chapter 22． Coupling from the Past 22．1． Introduction 22．2． Monotone CFTP 22．3． Perfect Sampling via Coupling from the Past 22．4． The Hardcore Model 22．5． Random State of an Unknown Markov Chain Exercise Notes Chapter 23． Open Problems 23．1． The Ising Model 23．2． Cutoff 23．3． Other Problems Appendix A． Background Material A．1． Probability Spaces and Random Variables A．2． Metric Spaces A．3． Linear Algebra A．4． Miscellaneous Appendix B． Introduction to Simulation B．1． What Is Simulation? B．2． Von Neumann Unbiasing B．3． Simulating Discrete Distributions and Sampling B．4． Inverse Distribution Function Method B．5． Acceptance-Rejection Sampling B．6． Simulating Normal Random Variables B．7． Sampling from the Simplex B．8． About Random Numbers B．9． Sampling from Large Sets Exercises Notes Appendix C． Solutions to Selected Exercises Bibliography Notation Index Index
鄂公网安备 42010302001612号 