viii CONTENTS 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
Previous Page Next Page