the Metropolis algorithm
/ meh-TROP-oh-liss /
In statistical mechanics you want to sample configurations of a system in proportion to their Boltzmann weight, so that thermally likely states show up often and unlikely ones rarely. The trouble is that the weight is exp(-E / kT) divided by the partition function Z, and Z is a sum over an astronomically large number of states that you cannot compute. The Metropolis algorithm is the beautiful escape: it builds a guided random walk through configuration space that visits each state exactly as often as its probability demands, and it never needs to know Z.
The recipe is a loop. From the current configuration, propose a small random change (flip one spin, nudge one particle) and compute the resulting energy change, delta E. If delta E <= 0 the move lowers the energy and you always accept it. If delta E > 0 you accept it only with probability exp(-delta E / kT), otherwise you keep the old configuration and count it again. Iterating generates a Markov chain whose stationary distribution is exactly the Boltzmann distribution, because this accept rule satisfies detailed balance. The crucial magic is that only the ratio of probabilities enters through delta E, so the intractable normalizing constant Z cancels and never has to be evaluated.
This is the engine behind an enormous range of simulations: the Ising model, lattice field theory and lattice QCD, and, in the broader Metropolis-Hastings form, Bayesian inference across science. The honest caveat is that successive samples are correlated, since it is a walk rather than a set of independent draws; you must discard an initial burn-in period and thin the chain to get near-independent samples. Worse, near a critical point the autocorrelation time diverges (critical slowing down) and the walk crawls through configuration space maddeningly slowly.
To simulate a two-dimensional Ising magnet at temperature T, repeatedly pick a random spin, compute the energy cost of flipping it, accept or reject per the Metropolis rule, and after the system has equilibrated average the magnetization; sweeping T through the critical point reproduces the ferromagnetic phase transition.
Sampling the Boltzmann distribution one spin flip at a time, with Z never computed.
Metropolis samples are correlated and only asymptotically Boltzmann-distributed, so burn-in and thinning matter; the partition function cancels precisely because the acceptance rule depends only on energy differences, never on absolute probabilities.