Reversible Markov Chains and Random Walks on Graphs

Chapter 11 Markov Chain Monte Carlo (January 8 2001)

This book is intended primarily as “theoretical mathematics”, focusing on ideas that can be encapsulated in theorems. Markov Chain Monte Carlo (MCMC), which has grown explosively since the early 1990s, is in a sense more of an “engineering mathematics” field – a suite of techniques which attempt to solve applied problems, the design of the techniques being based on intuition and physical analogies, and their analysis being based on experimental evaluation. In such a field, the key insights do not correspond well to theorems.

In section 11.1 we give a verbal overview of the field. Section 11.2 describes the two basic schemes (Metropolis and line-sampling), and section 11.3 describes a few of the many more complex chains which have been suggested. The subsequent sections are fragments of theory, indicating places where MCMC interfaces with topics treated elsewhere in this book. Liu [237] gives a comprehensive textbook treatment of the field.