the Metropolis-Hastings algorithm
/ meh-TROP-oh-lis HAY-stings /
Often you can write down a posterior up to its normalizing constant — you know a function proportional to the density — but the constant itself is a hopeless integral, so you cannot sample directly. Metropolis-Hastings is the brilliant escape: it builds a random walk through the space of possible values that, if you let it wander long enough, visits each region exactly as often as the target distribution says it should. You never need the normalizing constant, because only RATIOS of the density appear, and the constant cancels.
It is a Markov chain Monte Carlo (MCMC) method, and the loop is short. From the current state x, propose a candidate y from some proposal distribution q(y given x). Compute the acceptance ratio alpha = min(1, [pi(y) q(x given y)] / [pi(x) q(y given x)]), where pi is the target density known only up to a constant — note pi appears only as the ratio pi(y)/pi(x), so the unknown constant vanishes. With probability alpha, move to y; otherwise stay at x and record x again. Repeat. The genius is in the acceptance rule: it is engineered so the chain satisfies detailed balance with respect to pi, which forces pi to be the chain's stationary distribution, so the long-run fraction of time spent in any region matches pi.
After discarding an initial 'burn-in' stretch (the time the chain takes to forget its arbitrary starting point), the remaining states are samples from the target, and you treat them like Monte Carlo draws. This single idea unlocked modern Bayesian statistics: it lets you sample posteriors that have no conjugate form and no closed integral. The honest caveats are real, though. The samples are correlated, not independent, so the effective sample size is smaller than the raw count. The chain can mix slowly or get stuck in one mode, so tuning the proposal (not too timid, not too bold) matters enormously, and you must always check convergence — a chain can look settled yet be wrong.
Sample from a target shaped like two bumps. Start anywhere; at each step propose a small random hop. If the proposed spot has higher target density, always move there; if lower, move there only with probability equal to the density ratio (so you sometimes climb down). Over thousands of steps the walker spends time in each bump in proportion to its mass — a histogram of the visited points reproduces the two-bump shape.
Only density ratios appear, so the unknown normalizing constant cancels and never needs computing.
MCMC samples are correlated and the chain needs burn-in; a chain that looks converged can still be stuck in one mode, so always check mixing and convergence rather than trusting a single run.