Markov chain Monte Carlo

Markov chain Monte Carlo (MCMC) is a class of algorithms for sampling from probability distributions by constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the desired distribution. MCMC is the workhorse of modern Bayesian statistics, enabling inference in models where the posterior distribution is too complex to compute analytically or sample from directly.

The method was developed by Metropolis et al. in 1953 and generalized by Hastings in 1970. The key insight is that one can sample from a distribution by wandering through its support according to a carefully designed random walk, without needing to know the normalizing constant of the distribution. This is revolutionary for Bayesian inference, where posterior distributions are often known only up to a proportionality constant.

MCMC algorithms include the Metropolis-Hastings algorithm, Gibbs sampling, and Hamiltonian Monte Carlo. Each has different strengths: Metropolis-Hastings is general but can mix slowly; Gibbs sampling is efficient when conditional distributions are easy to sample; Hamiltonian Monte Carlo uses gradient information to propose states, achieving faster mixing in high-dimensional spaces.

The challenge of MCMC is diagnosing convergence. The chain must be run long enough to forget its initial state and reach the equilibrium distribution, but there is no general method for determining when this has occurred. Practitioners rely on heuristics, multiple chains, and visual inspection — a craft that is as much art as science.

MCMC represents a shift in statistical practice from exact computation to approximate exploration. The Bayesian revolution would not have been possible without it. But the reliance on MCMC also means that many Bayesian results are not exact but approximate, and the approximation quality is often unknown. The field has traded analytical rigor for computational feasibility — a trade that is rarely acknowledged explicitly.