Metropolis-Hastings Sampling

The Metropolis-Hastings sampling algorithm is a Markov chain Monte Carlo (MCMC) method for drawing samples from a probability distribution when direct sampling is impractical, either because the target density is known only up to a normalizing constant or because its shape is too complex to handle analytically. It was introduced by Nicholas Metropolis and colleagues in 1953 for problems in statistical physics and generalized by W. K. Hastings in 1970, who brought it into mainstream statistics.

The idea is to build a Markov chain whose stationary distribution matches the target distribution p. Starting from a current state, the algorithm proposes a candidate and then decides, through an acceptance rule, whether the chain moves there or stays put. Repeated many times, the chain's path yields samples that represent p.

How it works: the acceptance probability

The method relies on two ingredients: a proposal distribution q, which suggests a candidate x' from the current state x, and an acceptance probability. The candidate is accepted with probability min(1, [p(x') q(x|x')] / [p(x) q(x'|x)]). Here p is the target density, q(x'|x) is the probability of proposing x' while at x, and q(x|x') that of the reverse move. The ratio p(x')/p(x) favours more probable states —and needs no normalizing constant, since it cancels out— while the proposal ratio corrects any asymmetry in q; that correction is Hastings's contribution. If q is symmetric, the term simplifies to min(1, p(x')/p(x)), the original Metropolis form. When the candidate is rejected, the chain repeats its current state.

Where it is used

Metropolis-Hastings is a cornerstone of Bayesian inference and computational physics: it estimates posterior distributions, evaluates integrals and explores high-dimensional spaces. Gibbs sampling can be seen as a special case in which each variable is updated from its full conditional distribution and the proposal is always accepted.

Metropolis-Hastings versus HMC and NUTS

It is worth not conflating MH with its relatives. Hamiltonian Monte Carlo (HMC), which stems from the 1987 work of Duane and colleagues and was popularized in statistics by Radford Neal, and the No-U-Turn Sampler (NUTS), proposed by Hoffman and Gelman in 2014, are not mere improvements on MH: they are distinct MCMC algorithms that use the gradient of the density to propose longer, better-informed moves, curbing random-walk behaviour. They power libraries such as Stan and PyMC. They share MH's propose-and-accept scheme but differ in how candidates are generated.

Limits

MH is not inherently superior to other methods; its performance hinges on the proposal. Consecutive samples are usually autocorrelated, which lowers the effective sample size; the step size of q must be tuned with care (too large brings frequent rejections, too small means slow progress); and confirming that the chain has converged requires diagnostics, with no automatic guarantees. Choosing a good proposal remains an open problem.