Contents Preface xi 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 olya 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 v
Previous Page Next Page