the Metropolis-Hastings algorithm
/ meh-TROP-oh-lis HAY-stings /
Sometimes you need to draw samples from a distribution you can only evaluate up to an unknown scaling constant — a Bayesian posterior, a Boltzmann distribution in physics — and direct sampling (inversion, rejection) is hopeless in high dimensions. Metropolis-Hastings solves this by a clever device: instead of sampling the distribution directly, it builds a RANDOM WALK that wanders through the space and, in the long run, visits each region in exact proportion to its probability. Collect the walk's stopping points and you have your samples.
Here is the loop, beautifully simple. You are at a current state x. (1) Propose a candidate y by some random move (e.g. a small Gaussian step from x). (2) Compute the acceptance ratio alpha = min(1, [p(y) q(x|y)] / [p(x) q(y|x)]), where p is the target (needed only up to a constant, since the unknown constant cancels in the ratio) and q is the proposal density. (3) Draw a uniform u; if u < alpha, ACCEPT and move to y, otherwise STAY at x and record x again. Repeat. The genius is that p appears only as a ratio p(y)/p(x), so the impossible-to-compute normalizing constant cancels — you never need it. The chain is engineered (via 'detailed balance') so that its long-run distribution is exactly the target p; the Gibbs sampler is a special case that updates one coordinate at a time from its exact conditional.
Metropolis-Hastings, invented for physics in 1953 and generalized by Hastings, revolutionized Bayesian statistics and statistical physics — it makes sampling complicated, high-dimensional distributions possible at all. The honesty is essential, though. The samples are CORRELATED, not independent: consecutive states are close, so the effective number of independent samples is far smaller than the chain length, and the s/sqrt(N) error bar is too optimistic unless you account for autocorrelation. The chain needs a BURN-IN period to forget its arbitrary starting point before its samples are valid, and tuning the proposal step is delicate — too small and it crawls (high acceptance but tiny moves), too large and almost everything is rejected (it gets stuck). Diagnosing whether the chain has truly converged is genuinely hard and never fully certain.
Sample a bimodal target p(x) proportional to e^(-(x^2-4)^2). Start at x = 0, propose y = x + Normal(0, 1). Suppose y = 1.8: compute p(1.8)/p(0); if the ratio exceeds a uniform draw, accept and move to 1.8, else stay at 0. Repeating millions of times produces a histogram matching p — even though p's normalizing constant is never computed.
A guided random walk whose long-run visits match the target — no normalizing constant needed.
MCMC samples are CORRELATED, so the naive s/sqrt(N) error bar overstates your precision — you must account for autocorrelation. The chain also needs burn-in and careful proposal tuning, and 'has it converged?' is genuinely hard to answer with certainty.