CONTENTS ix 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 Index 365
Previous Page Next Page