Markov Chain Monte Carlo

Markov chain Monte Carlo samples from a complex target distribution by simulating a Markov chain engineered to have that distribution as its stationary law, so that the chain's path, once converged, behaves like a dependent sample from the target.

Definition

Markov chain Monte Carlo is a class of algorithms that estimate expectations under a target distribution by constructing an ergodic Markov chain whose invariant distribution is the target and averaging a function over the chain's realized states.

Scope

This topic covers the construction of chains with a prescribed stationary distribution through detailed balance, the Metropolis-Hastings algorithm and its proposal mechanisms, convergence and mixing diagnostics, burn-in and autocorrelation, and the estimation of Monte Carlo standard errors from dependent draws. The Gibbs sampler is treated as a distinct sibling topic, and Hamiltonian and adaptive variants are noted as extensions.

Core questions

• How is a Markov chain constructed so that its stationary distribution is a prescribed target?
• How does the Metropolis-Hastings accept-reject step enforce detailed balance for an arbitrary proposal?
• How is convergence to stationarity assessed, and how is mixing speed diagnosed?
• How are Monte Carlo standard errors computed from autocorrelated draws?

Key concepts

• Stationary distribution
• Detailed balance
• Acceptance ratio
• Burn-in
• Autocorrelation and mixing
• Convergence diagnostics

Key theories

Detailed balance and stationarity

If a transition kernel satisfies detailed balance with respect to a target distribution, that distribution is stationary; ergodic averages of the resulting chain then converge to expectations under the target.

Metropolis-Hastings algorithm

Proposing a move and accepting it with a probability built from the target and proposal densities yields a chain reversible with respect to the target, requiring the target only up to a normalizing constant.

Clinical relevance

Markov chain Monte Carlo made fully Bayesian inference practical for hierarchical and high-dimensional models, and is applied across statistical genetics, ecology, epidemiology, econometrics and the physical sciences wherever posterior or Boltzmann distributions must be explored but cannot be sampled directly.

History

The Metropolis algorithm appeared in 1953 in statistical physics, Hastings generalized it in 1970, and the early 1990s saw statisticians adopt Markov chain Monte Carlo as the standard engine of Bayesian computation, later extended by Hamiltonian Monte Carlo and adaptive samplers.

Debates

Assessing convergence

Because no finite run can prove a chain has reached its stationary distribution, practitioners rely on diagnostics and multiple chains; there is ongoing discussion about which diagnostics are trustworthy and how conservative burn-in and run length should be.

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Christian P. Robert
• Andrew Gelman

Seminal works

• metropolis1953
• hastings1970

Frequently asked questions

Why are Markov chain Monte Carlo samples correlated?

Each state is generated from the previous one, so consecutive draws are dependent. This autocorrelation reduces the effective amount of information, which is why mixing speed and effective sample size matter when estimating accuracy.

What is burn-in?

Burn-in is the initial portion of the chain discarded because it still reflects the arbitrary starting point rather than the target distribution. Discarding it reduces the bias from initialization before averaging the remaining draws.