Markov Chain Monte Carlo: Sampling from Distributions You…

The Problem: Distributions You Can Evaluate but Not Normalize

In Bayesian statistics, physics, and machine learning, you often know a target distribution only as an unnormalized function. Bayes' rule gives the posterior as P(x) = f(x) / Z, where f(x) = likelihood(x) × prior(x) is easy to compute for any single point x, but the normalizing constant Z = ∫ f(x) dx requires integrating over every possible value of x. In one dimension that integral might be tractable; in the hundred or thousand dimensions typical of a real model, it becomes a hopeless sum over an astronomically large space. Worse, even if you knew Z, you still could not easily draw random samples from a bizarrely shaped, high-dimensional distribution using ordinary methods like inverse-transform sampling, which need the full cumulative distribution in closed form. MCMC sidesteps both problems at once: it needs only the ratio f(x')/f(x) between two points to decide how to move, so the unreachable constant Z cancels out before it ever causes trouble, and it never requires integrating or normalizing anything globally.

A Random Walk That Remembers Where It Should Live

A Markov chain is a sequence of random states x0, x1, x2, ... where each new state depends only on the current one, not on the full history — a memoryless random walk defined by a transition rule T(x → x'). The central trick of MCMC is to design that transition rule so the chain has a unique stationary distribution equal to the target P(x): once the chain has run long enough, the fraction of time it spends near any point x converges to P(x), regardless of where it started. A distribution π is stationary for the chain if, once the chain's states are distributed according to π, one more step leaves the distribution unchanged: π(x') = ∑_x π(x) T(x → x'). The entire craft of MCMC algorithm design is choosing a transition rule T that is easy to simulate step by step, yet provably has the target P as its stationary distribution.

The Metropolis-Hastings Algorithm

The Metropolis-Hastings algorithm builds such a transition rule out of two simple ingredients repeated over and over. First, from the current state x, a proposal distribution Q(x'|x) suggests a candidate next state x' — often just x plus a small random jitter, like a step in a random direction. Second, the candidate is either accepted or rejected according to the acceptance probability: A = min(1, [P(x')Q(x|x')] / [P(x)Q(x'|x)]). If the proposal distribution is symmetric, meaning Q(x'|x) = Q(x|x') (as with a simple Gaussian jitter), the Q terms cancel and this reduces to the original Metropolis rule: A = min(1, P(x')/P(x)). Because P appears only as a ratio, you can substitute the unnormalized f in its place: A = min(1, f(x')/f(x)), and Z drops out entirely. In practice this means: propose a move; if it leads to higher probability, always accept it; if it leads to lower probability, accept it anyway with probability equal to the probability ratio, otherwise stay put and count the current state again. This willingness to occasionally accept a worse move is exactly what lets the chain escape local bumps and explore the full landscape rather than greedily climbing to the nearest peak.

Why Detailed Balance Guarantees Correctness

The reason Metropolis-Hastings is guaranteed to converge to the right distribution, rather than some arbitrary one shaped by the proposal mechanism, is a property called detailed balance (or reversibility): P(x) T(x → x') = P(x') T(x' → x). This says the flow of probability from x to x' exactly balances the flow back from x' to x, for every pair of states. Any transition rule satisfying detailed balance with respect to P automatically has P as a stationary distribution, since summing both sides over x makes the net flow into any state x' equal to P(x') itself. The acceptance rule A = min(1, [P(x')Q(x|x')]/[P(x)Q(x'|x)]) is constructed precisely so that the combined propose-then-accept transition satisfies detailed balance by design — it is not an approximation or a heuristic, but a proof-carrying recipe. This is what separates MCMC from a naive random walk: the algorithm does not merely wander plausibly, it wanders in a mathematically certified way that must converge to the target distribution as the number of steps grows.

Burn-in, Mixing, and Real Applications

Convergence in theory does not mean instant convergence in practice. Early samples are biased toward wherever the chain happened to start, so practitioners discard an initial stretch called the burn-in period before trusting the samples. Consecutive samples are also correlated, since each state is built from the last one by a small step, a property called autocorrelation; a chain with high autocorrelation is said to mix slowly, wastefully revisiting nearby states rather than exploring broadly, and often needs thinning (keeping only every k-th sample) or a better-tuned proposal step size to fix. Too small a proposal step and nearly every move is accepted but the chain crawls; too large a step and almost every move is rejected and the chain stalls in place — tuning the acceptance rate, often targeted around 20-50%, is a core practical skill. Despite these caveats, MCMC methods underpin an enormous range of real work: Bayesian inference uses them to sample posterior distributions over model parameters that have no closed form; statistical physics uses the original Metropolis algorithm to simulate systems like the Ising model at thermal equilibrium; and training restricted Boltzmann machines (RBMs) in machine learning relies on MCMC-based methods like contrastive divergence to approximate the intractable expectations needed for learning.

Frequently asked questions

Why can't we just normalize the distribution first and sample directly?

Normalizing requires computing Z, an integral (or sum) over the entire state space, which in high dimensions has no closed form and is computationally infeasible to approximate directly by brute force. MCMC avoids this entirely because its acceptance rule only ever needs the ratio f(x')/f(x) between two points, so the unknown constant Z cancels out and never needs to be computed.

What happens if the proposal distribution is a poor match for the target?

The chain still converges to the correct stationary distribution eventually, since detailed balance holds for any valid proposal distribution, but a poorly matched proposal makes convergence painfully slow. Steps that are too large get rejected constantly, and steps that are too small barely move the chain, so in both cases you need vastly more iterations to adequately explore the distribution and get reliable samples.

How do you know when a Markov chain has converged?

There is no perfect test, but common diagnostics include running multiple independent chains from different starting points and checking whether they agree with each other (such as the Gelman-Rubin statistic), visually inspecting trace plots for stability, and monitoring autocorrelation to ensure samples aren't still drifting systematically. In practice, most workflows combine several diagnostics rather than trusting any single one.

Is Metropolis-Hastings the only MCMC algorithm?

No. It is the foundational, most general version, but many specialized variants exist, including Gibbs sampling (which cycles through updating one variable at a time from its full conditional distribution), Hamiltonian Monte Carlo (which uses gradient information to propose distant, high-acceptance moves efficiently), and slice sampling. All of them are, in one way or another, built on the same detailed-balance idea.

Does a higher acceptance rate always mean a better sampler?

Not necessarily. A very high acceptance rate often means the proposal steps are too small, so the chain accepts almost everything but barely moves anywhere, resulting in slow exploration despite looking efficient on paper. This is why practitioners aim for a moderate target acceptance rate rather than maximizing it, balancing how far each step travels against how often it succeeds.

Try it live

Everything above runs in your browser — open Markov Chain Monte Carlo: Sampling from Distributions You Can't Compute and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Markov Chain Monte Carlo: Sampling from Distributions You Can't Compute simulation