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