MCMC Sampling: Metropolis–Hastings & Gibbs
Bayesian inference produces a posterior . The proportionality hides a problem: the normalizing constant is usually an intractable high-dimensional integral. Markov Chain Monte Carlo (MCMC) sidesteps it entirely — it draws samples from the posterior knowing the density only up to that constant, then answers every downstream question (means, intervals, predictions) with sample averages.
Why sampling, and why Monte Carlo works
Almost every Bayesian quantity is an expectation under the posterior:
If we can draw samples from the posterior, the integral becomes an average — the Monte Carlo estimate, which converges by the law of large numbers. The catch: we can't sample directly from a distribution we only know up to a constant. MCMC's trick is to construct a Markov chain whose stationary distribution is the posterior; run it long enough and its states are (correlated) samples from the target.
Metropolis–Hastings
The general-purpose recipe. To sample from a target known up to a constant:
- From the current state , draw a candidate from a proposal (e.g. a Gaussian centered at ).
- Compute the acceptance ratio
- Accept with probability (set next state to ); otherwise stay at (and record again).
- Repeat.
The normalizing constant cancels in the ratio , which is the whole point. You only ever need the unnormalized posterior .
When the proposal is symmetric (, as for a Gaussian random walk), the terms cancel too and the ratio collapses to the original Metropolis form — always move to higher density, sometimes move to lower.
Detailed balance is why it works
The acceptance rule is engineered so the chain satisfies detailed balance: . A chain in detailed balance with is reversible and has as its stationary distribution, so its long-run samples are distributed according to the target, whatever the (positive) proposal.
Watch it run
Metropolis sampling a target it is only allowed to see up to a constant. The target here is deliberately one we can solve exactly — the Beta(8, 4) posterior after 7 heads in 10 flips, so the sampler's answer can be checked against the truth instead of merely admired:
Metropolis–Hastings — proposing, accepting, and the σ that ruins everything
The target is the posterior after 7 heads in 10 flips under a uniform prior — a Beta(8, 4) with mean 0.667. Crucially the sampler is only ever shown the *unnormalized* density θ⁷(1−θ)³; it never gets the normalizing constant, which is the situation every real Bayesian model is in. The chain starts at θ = 0.2, deliberately far out in the tail.
Random-walk Metropolis sampling a Beta(8, 4) posterior it is only allowed to see up to a constant. Step through the accept/reject decision — uphill moves always taken, downhill moves taken sometimes — and watch the chain climb out of the tail during burn-in. The final step runs three proposal scales against the same target: one accepts almost everything, one almost nothing, and both collapse the effective sample size for opposite reasons.
What to notice as you step:
- The constant never appears. Every decision is made from , and the normalizer cancels there. That single fact is why MCMC works on posteriors nobody can integrate.
- Downhill moves are accepted on purpose. A proposal with ratio is taken 41% of the time. Reject those always and you have hill-climbing, which converges to the mode and gets the distribution completely wrong.
- A rejection still emits a sample. The current state is recorded again, which is why trace plots have flat stretches, and why a high rejection rate destroys the effective sample size without shortening the chain.
- The first steps are burn-in, and they describe the starting point rather than the target.
- The last step is the tuning lesson: σ = 0.005 accepts 98% of proposals and is nearly useless (ESS 6); σ = 5 rejects 97% and is nearly useless (ESS 55); σ = 0.3 gets ESS 813 at a 46% acceptance rate — almost exactly the ~44% that the next section recommends for a single parameter.
Gibbs sampling
When you can derive the full conditional distribution of each parameter given all the others, , and sample from it directly, Gibbs sampling applies. Cycle through the parameters, updating one at a time from its full conditional:
Gibbs is a special case of Metropolis–Hastings where the proposal is the full conditional and every move is accepted (). It shines for conditionally conjugate models (hierarchical models, mixtures with latent labels) where each conditional is a standard distribution. Its weakness: when parameters are highly correlated, updating one axis at a time produces slow, zig-zag exploration.
The practical machinery
A raw chain is not yet a clean set of posterior samples. Four issues to handle:
- Burn-in. The chain starts at an arbitrary point and needs time to reach the high-density region. Discard the first samples (e.g. the first 10–50%) so the start point doesn't bias estimates.
- Thinning. Consecutive states are autocorrelated. Keeping every -th sample reduces storage and autocorrelation, though for estimating means it's usually better to keep everything and rely on the effective sample size. Thin only when storage or per-sample cost is the bottleneck.
- Acceptance rate tuning. The proposal scale is the key knob. Too small → nearly all proposals accepted but tiny steps, glacial exploration. Too large → big jumps almost always rejected, the chain gets stuck. The classic target is ~23% acceptance for high-dimensional random-walk Metropolis (≈44% for a single parameter).
- Multiple chains. Run several chains from dispersed starts to diagnose convergence and detect multimodality a single chain might miss.
Convergence diagnostics
You can never prove convergence, but several diagnostics catch failure:
- Trace plots. Plot each parameter against iteration. A converged chain looks like a stationary "fuzzy caterpillar"; trends, drift, or a chain stuck in a region signal trouble.
- (Gelman–Rubin). Compares between-chain and within-chain variance across multiple chains. (conventionally ) indicates the chains have mixed to the same distribution; well above 1 means they haven't.
- Effective sample size (ESS). Because samples are autocorrelated, draws carry the information of fewer independent ones: , where is the lag- autocorrelation. ESS is what actually determines Monte-Carlo error — report it, not the raw chain length.
A converged-looking chain can still be wrong
Good trace plots and show the chains agree — not that they found the whole posterior. If every chain starts near the same mode of a multimodal posterior, they can all converge to that mode and report while missing the rest of the distribution. Disperse the starting points and, where feasible, use samplers built for multimodality (parallel tempering, HMC/NUTS).
Beyond random-walk MCMC
Random-walk Metropolis explores by diffusion, which scales poorly in high dimensions. Hamiltonian Monte Carlo (HMC) uses the gradient of the log-posterior to propose distant, high-acceptance moves; the No-U-Turn Sampler (NUTS) auto-tunes its trajectory length and is the default engine in Stan, PyMC, and NumPyro. When you have gradients and a continuous parameter space, HMC/NUTS typically delivers far higher ESS per second than the methods on this page, which remain the conceptual foundation and the right tool for discrete or non-differentiable targets.
Related concepts
- Bayesian Inference: the posterior that MCMC samples from, and the intractable evidence integral it routes around
- Bayesian Linear Regression: a conjugate model where Gibbs full conditionals are clean and closed-form
- The Bootstrap: the frequentist resampling counterpart: approximate a sampling distribution instead of a posterior
- Beta–Bernoulli Posterior: the conjugate case where you can sample the posterior directly, no MCMC required