Markov chain Monte Carlo

MCMC algorithms generate a sequence of samples by simulating a Markov chain that has the target distribution as its unique stationary distribution. The chain is designed so that, after a burn-in period, the samples approximate draws from the target. The theoretical guarantee relies on ergodic theorems: the sample average converges to the expected value under the target distribution as the number of iterations grows.¹

The most fundamental algorithm is the Metropolis–Hastings (MH) method, which uses a proposal distribution to generate candidate states and accepts or rejects them with a probability that ensures detailed balance. The acceptance probability is min(1, [π(y)q(x|y)]/[π(x)q(y|x)]), where π is the target and q is the proposal. This construction guarantees that the chain is reversible with respect to π, making π stationary.²

Several MCMC variants improve efficiency for specific problems. The Gibbs sampler updates each variable sequentially from its conditional distribution given the others, avoiding the need for tuning proposal distributions. It is particularly effective when full conditionals are easy to sample.³ Hamiltonian Monte Carlo (HMC) uses gradient information to propose distant states, reducing random-walk behavior and improving mixing in high-dimensional spaces. The No-U-Turn Sampler (NUTS) automates HMC's step-size and trajectory length tuning, making it a default in probabilistic programming languages like Stan.⁴

Other notable extensions include slice sampling, adaptive MCMC, and population-based methods like parallel tempering, which help sample multimodal distributions. Reversible-jump MCMC allows the dimension of the parameter space to vary, useful for model selection.⁵

MCMC has transformed Bayesian statistics, enabling posterior inference for complex hierarchical models that were previously intractable. In physics, it is used to simulate lattice systems and study phase transitions. In computational biology, MCMC reconstructs phylogenetic trees and infers population genetics parameters. In machine learning, it underpins Bayesian neural networks and topic models like latent Dirichlet allocation.⁶

In finance, MCMC calibrates stochastic volatility models and estimates risk. In astronomy, it fits cosmological parameters to observational data. The versatility of MCMC stems from its ability to handle high-dimensional, non-normal, and correlated distributions with minimal assumptions.⁷

Ensuring that the Markov chain has converged to the stationary distribution is critical. Common diagnostics include trace plots, autocorrelation analysis, and the Gelman-Rubin statistic, which compares within-chain and between-chain variances. The effective sample size (ESS) quantifies the number of independent samples equivalent to the correlated chain output.⁸

Practical guidelines recommend running multiple chains with dispersed starting points, discarding a burn-in fraction, and checking that the potential scale reduction factor R-hat is close to 1.0. However, no diagnostic can guarantee convergence; they only provide necessary conditions.¹

The first MCMC algorithm, the Metropolis algorithm, was developed in 1953 by Nicholas Metropolis and colleagues for the Manhattan Project to compute equations of state for hard spheres.² The name 'Monte Carlo' was coined by Stanislaw Ulam, inspired by his uncle's gambling habits. The method was later generalized by W.K. Hastings in 1970, and the Gibbs sampler was introduced by Stuart Geman and Donald Geman in 1984 for image restoration.³

An edge case is the 'curse of dimensionality': MCMC methods often struggle in very high dimensions, but HMC mitigates this by exploiting gradient information. Another niche application is in 'approximate Bayesian computation' (ABC), where MCMC is used when the likelihood is intractable. Additionally, MCMC has been applied to the analysis of the cosmic microwave background radiation, helping to map the universe's early structure.⁷

Stationary distribution

A probability distribution that remains unchanged after the Markov chain transition; the target distribution in MCMC.

Burn-in

The initial portion of the chain that is discarded to reduce dependence on the starting point.

Detailed balance

A condition ensuring reversibility of the chain, which guarantees the stationary distribution.

Effective sample size (ESS)

The number of independent samples equivalent to the correlated MCMC output.

Hamiltonian Monte Carlo (HMC)

An MCMC method that uses Hamiltonian dynamics to propose distant states, improving efficiency in high dimensions.