Skip to content
LumenaryAcademy
Inference 75 min

Markov chain Monte Carlo

Computing with a posterior you can only write down up to a constant — the Metropolis–Hastings algorithm built from scratch, the diagnostics that tell you whether to trust it, and Hamiltonian Monte Carlo as Stan and PyMC use it.

Code tested · 6AI-draftedAwaiting review by a statistician

Your guides: Chloe · The Statistician, Margaret · The Simulator, Gideon · The Sceptic

MotivationH

Why integrals are hard

Everything a Bayesian wants from a posterior is an integral. The posterior mean of a parameter is ∫θ p(θ∣y) dθ\int \theta\, p(\theta \mid y)\, d\theta; the probability that it exceeds a threshold is the integral of the posterior over that region; a prediction averages the model over the posterior. Even the posterior itself contains an integral, the evidence p(y)=∫p(y∣θ) p(θ) dθp(y) = \int p(y \mid \theta)\, p(\theta)\, d\theta in the denominator of Bayes' theorem.

In Bayesian inference we were lucky twice. The beta prior was conjugate to the binomial likelihood, so the integrals had formulas; and there was only one parameter, so a grid of 2,001 points could check them. Real models are rarely so kind. A logistic regression with normal priors has no conjugate posterior. A model of exam results in 300 schools, with a parameter for each school, has hundreds of parameters. A grid with 50 points per parameter needs 50d50^d evaluations of the posterior:

Parameters dd12510100
Grid points 50d50^d502,5003.1×1083.1 \times 10^{8}9.8×10169.8 \times 10^{16}7.9×101697.9 \times 10^{169}

Beyond about five parameters, grids are hopeless. There is a way out, and it comes from simulation. If we could draw independent values θ(1),…,θ(N)\theta^{(1)}, \ldots, \theta^{(N)} from the posterior, we could estimate any posterior expectation by an average, ∫g(θ) p(θ∣y) dθ≈1N∑ig(θ(i))\int g(\theta)\, p(\theta \mid y)\, d\theta \approx \frac{1}{N} \sum_i g(\theta^{(i)}), with an error that shrinks like 1/N1/\sqrt{N} whatever the number of parameters. This is Monte Carlo integration. The remaining obstacle is that we cannot draw independent values from a distribution we know only up to its normalising constant.

Markov chain Monte Carlo (MCMC) removes the obstacle. Instead of independent draws, it produces a sequence in which each value depends on the previous one — a Markov chain — designed so that, in the long run, the values are distributed according to the posterior. This lesson builds the simplest such chain from scratch, applies it to a model with no formula, learns how to tell whether it has worked, and then meets the gradient-based method that powers modern software.

DefinitionsH

Markov chains with a chosen destination

A Markov chain is a sequence of random values in which the next value depends only on the current one, through a fixed transition rule. Lumenary Math's Markov chains develops the theory; we need three facts. A distribution π\pi is stationary for the chain if, when the current value is drawn from π\pi, the next one is too. Under mild conditions — the chain can reach every region of positive probability (it is irreducible) and does not cycle with a fixed period (it is aperiodic) — the chain converges to its stationary distribution from any starting point. And then the ergodic theorem holds: averages along a single long run converge to expectations under π\pi, just as averages of independent draws would. MCMC turns this around: we choose π\pi to be the posterior, and design a transition rule that has it as its stationary distribution.

Definition— Metropolis–Hastings algorithm

To sample from a density π(θ)\pi(\theta) known up to a constant, choose a proposal distribution q(θ′∣θ)q(\theta' \mid \theta) and a starting value θ(0)\theta^{(0)}. At each step tt:

  1. Propose θ′∼q(⋅∣θ(t))\theta' \sim q(\cdot \mid \theta^{(t)}).
  2. Compute the acceptance probability α=min⁡ ⁣(1,  π(θ′) q(θ(t)∣θ′)π(θ(t)) q(θ′∣θ(t))).\alpha = \min\!\left(1,\; \frac{\pi(\theta')\, q(\theta^{(t)} \mid \theta')}{\pi(\theta^{(t)})\, q(\theta' \mid \theta^{(t)})}\right).
  3. With probability α\alpha set θ(t+1)=θ′\theta^{(t+1)} = \theta' (accept); otherwise set θ(t+1)=θ(t)\theta^{(t+1)} = \theta^{(t)} (reject, and repeat the current value).

If the proposal is symmetric, q(θ′∣θ)=q(θ∣θ′)q(\theta' \mid \theta) = q(\theta \mid \theta') — for example θ′=θ+ε\theta' = \theta + \varepsilon with ε∼N(0,s2)\varepsilon \sim N(0, s^2) — the qq terms cancel and α=min⁡(1,π(θ′)/π(θ))\alpha = \min(1, \pi(\theta')/\pi(\theta)). This random-walk Metropolis algorithm always accepts a move uphill and accepts a move downhill with probability equal to the ratio of heights.

Theorem— Metropolis–Hastings leaves the target distribution invariant

The Metropolis–Hastings transition satisfies detailed balance with respect to π\pi: for all θ≠θ′\theta \ne \theta', π(θ) P(θ→θ′)=π(θ′) P(θ′→θ)\pi(\theta)\, P(\theta \to \theta') = \pi(\theta')\, P(\theta' \to \theta). Consequently π\pi is a stationary distribution of the chain.

Proof

For θ≠θ′\theta \ne \theta', the chain moves from θ\theta to θ′\theta' only by proposing θ′\theta' and accepting, so P(θ→θ′)=q(θ′∣θ) α(θ,θ′)P(\theta \to \theta') = q(\theta' \mid \theta)\, \alpha(\theta, \theta'). Write a=π(θ) q(θ′∣θ)a = \pi(\theta)\, q(\theta' \mid \theta) and b=π(θ′) q(θ∣θ′)b = \pi(\theta')\, q(\theta \mid \theta'). Then α(θ,θ′)=min⁡(1,b/a)\alpha(\theta, \theta') = \min(1, b/a) and α(θ′,θ)=min⁡(1,a/b)\alpha(\theta', \theta) = \min(1, a/b), so π(θ) P(θ→θ′)=amin⁡(1,b/a)=min⁡(a,b)=bmin⁡(1,a/b)=π(θ′) P(θ′→θ).\pi(\theta)\, P(\theta \to \theta') = a \min(1, b/a) = \min(a, b) = b \min(1, a/b) = \pi(\theta')\, P(\theta' \to \theta). Detailed balance says the probability flow from any θ\theta to any θ′\theta' equals the flow back. Summing (or integrating) the flow into θ′\theta' over all θ\theta, including the probability of staying put, gives ∫π(θ) P(θ→θ′) dθ=π(θ′)∫P(θ′→θ) dθ=π(θ′)\int \pi(\theta)\, P(\theta \to \theta')\, d\theta = \pi(\theta') \int P(\theta' \to \theta)\, d\theta = \pi(\theta'), which is the definition of stationarity.

∎

Stationarity is not the whole story: it says that a chain which starts in the posterior stays there, not how quickly a chain started elsewhere gets there, nor how quickly its averages settle down. Those practical questions are what the diagnostics later in this lesson are for.

ComputationC

Metropolis from scratch

Our first target is the posterior from the previous lesson, Beta(8,14)\text{Beta}(8, 14), written only as the unnormalised product of likelihood and uniform prior, θ7(1−θ)13\theta^7 (1-\theta)^{13}. We know the exact answers, so we can check the chain. The program works with logarithms, as all serious samplers do, because products of many small probabilities underflow to zero in floating-point arithmetic, while sums of their logarithms do not.

python
import numpy as np
from scipy import stats

def log_target(theta):
    """Unnormalised log posterior from the previous lesson: Beta(8, 14), known only up to a constant."""
    if not 0 < theta < 1:
        return -np.inf
    return 7 * np.log(theta) + 13 * np.log(1 - theta)

def metropolis(log_p, start, step, n_iter, rng):
    x, lp = start, log_p(start)
    chain, accepted = np.empty(n_iter), 0
    for i in range(n_iter):
        proposal = x + step * rng.normal()            # symmetric random-walk proposal
        lp_new = log_p(proposal)
        if np.log(rng.uniform()) < lp_new - lp:       # accept with probability min(1, ratio)
            x, lp = proposal, lp_new
            accepted += 1
        chain[i] = x                                  # a rejected move repeats the old value
    return chain, accepted / n_iter

rng = np.random.default_rng(1953)
chain, rate = metropolis(log_target, start=0.9, step=0.15, n_iter=50_000, rng=rng)
draws = chain[1_000:]                                 # discard the warm-up
exact = stats.beta(8, 14)
print(f"acceptance rate {rate:.2f}")
print(f"{'':10} {'MCMC':>7} {'exact':>7}")
print(f"{'mean':10} {draws.mean():7.4f} {exact.mean():7.4f}")
print(f"{'sd':10} {draws.std():7.4f} {exact.std():7.4f}")
for q in [0.025, 0.5, 0.975]:
    print(f"{'q ' + str(q):10} {np.quantile(draws, q):7.4f} {exact.ppf(q):7.4f}")
print(f"{'P(>0.2)':10} {np.mean(draws > 0.2):7.4f} {exact.sf(0.2):7.4f}")
print("first ten values of the chain:", np.round(chain[:10], 3))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Every summary agrees with the exact beta distribution to about two decimal places, without the program ever knowing the normalising constant. Look at the first ten values: the chain started far out at 0.9, repeated values whenever a proposal was rejected, and took several steps to reach the bulk of the posterior. Those early values are not representative, which is why the program discarded the first 1,000 iterations as warm-up (also called burn-in).

Worked examplesH

A model without a formula

Now a model that needs MCMC. A plant-breeding station in Saskatchewan tests the frost tolerance of a new winter-wheat line (the data are synthetic). Batches of 20 seedlings are held in a climate chamber at −2, −4, −6, −8 and −10 °C, and the survivors are counted: 19, 16, 12, 5 and 1. A logistic regression models the survival probability at temperature tt as logit⁡P(survive)=α+β (t+6),\operatorname{logit} P(\text{survive}) = \alpha + \beta\,(t + 6), centred at −6 °C so that α\alpha is the log-odds of survival there and β\beta is the change in log-odds per degree. We give both parameters weakly informative N(0,2.52)N(0, 2.5^2) priors. The breeders care most about the LT50, the temperature at which half the seedlings survive, which is t=−6−α/βt = -6 - \alpha/\beta. There is no conjugate prior here and no formula for the posterior, but the log posterior is easy to evaluate at any point, and that is all Metropolis needs.

python
import numpy as np

# Synthetic frost-tolerance trial: 20 seedlings at each temperature; survivors counted.
temp = np.array([-2.0, -4.0, -6.0, -8.0, -10.0])        # degrees Celsius
x = temp + 6.0                                          # centred at -6 C
n = np.array([20, 20, 20, 20, 20])
y = np.array([19, 16, 12, 5, 1])

def log_post(alpha, beta):
    """Logistic regression, logit P(survive) = alpha + beta * x, with Normal(0, 2.5^2) priors."""
    eta = alpha + beta * x
    loglik = np.sum(y * eta - n * np.logaddexp(0.0, eta))
    return loglik - (alpha**2 + beta**2) / (2 * 2.5**2)

def metropolis_2d(start, step, n_iter, rng):
    theta = np.array(start, dtype=float)
    lp = log_post(*theta)
    out, acc = np.empty((n_iter, 2)), 0
    for i in range(n_iter):
        prop = theta + step * rng.normal(size=2)
        lp_new = log_post(*prop)
        if np.log(rng.uniform()) < lp_new - lp:
            theta, lp, acc = prop, lp_new, acc + 1
        out[i] = theta
    return out, acc / n_iter

rng = np.random.default_rng(7)
starts = [(-3, -2), (3, 2), (-3, 2), (3, -2)]          # deliberately scattered
chains = []
for s in starts:
    c, rate = metropolis_2d(s, step=0.3, n_iter=6_000, rng=rng)
    chains.append(c[1_000:])                           # drop 1,000 warm-up iterations
    print(f"chain from {s}: acceptance {rate:.2f}, mean alpha {c[1000:, 0].mean():.3f}, mean beta {c[1000:, 1].mean():.3f}")
draws = np.concatenate(chains)

# Derived quantity: LT50, the temperature at which half the seedlings survive.
lt50 = -6.0 - draws[:, 0] / draws[:, 1]
print(f"\nMCMC  alpha {draws[:, 0].mean():.3f} (sd {draws[:, 0].std():.3f})   beta {draws[:, 1].mean():.3f} (sd {draws[:, 1].std():.3f})")
print(f"      LT50 mean {lt50.mean():.2f} C, 95% interval [{np.quantile(lt50, 0.025):.2f}, {np.quantile(lt50, 0.975):.2f}] C")

# Check against brute force on a 2-D grid (possible here only because there are two parameters).
a_grid, b_grid = np.meshgrid(np.linspace(-1.5, 2.0, 351), np.linspace(0.2, 1.4, 361), indexing="ij")
eta = a_grid[..., None] + b_grid[..., None] * x
logp = (y * eta - n * np.logaddexp(0.0, eta)).sum(axis=-1) - (a_grid**2 + b_grid**2) / (2 * 2.5**2)
w = np.exp(logp - logp.max()); w /= w.sum()
print(f"grid  alpha {(w * a_grid).sum():.3f} (sd {np.sqrt((w * a_grid**2).sum() - (w * a_grid).sum()**2):.3f})"
      f"   beta {(w * b_grid).sum():.3f} (sd {np.sqrt((w * b_grid**2).sum() - (w * b_grid).sum()**2):.3f})")
print("correlation of alpha and beta in the posterior:", round(np.corrcoef(draws.T)[0, 1], 2))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Four chains started at deliberately scattered points all settle on the same region and agree with each other to about 0.02, and the pooled results agree with a brute-force grid, which is still affordable with two parameters. The derived quantity is where MCMC shines. The posterior of the LT50, a nonlinear function of two correlated parameters, would be awkward to obtain analytically; with draws, we simply compute −6−α/β-6 - \alpha/\beta for every draw and summarise the results. The breeders can report that the LT50 is about −6.3 °C, with a 95% credible interval from −7.1 to −5.6 °C.

This is the general pattern: once you have draws from the posterior, every question becomes a question about a list of numbers. Probabilities are fractions of draws, intervals are quantiles of draws, and predictions come from simulating new data for each draw.

ComputationC

Is the chain telling the truth?

An MCMC run always produces numbers. The hard part is knowing whether they describe the posterior. Three things can go wrong: the chain has not yet forgotten its starting point; it moves so sluggishly that its draws carry little information; or it has explored only part of the posterior. Practitioners check for all three, using several chains and a few standard quantities.

Definition— autocorrelation and effective sample size

The autocorrelation at lag kk, ρk\rho_k, is the correlation between draws kk steps apart in a chain. The effective sample size of NN correlated draws is Neff=N1+2∑k=1∞ρk,N_{\text{eff}} = \frac{N}{1 + 2\sum_{k=1}^{\infty} \rho_k}, the number of independent draws that would estimate a posterior mean with the same precision. The Monte Carlo standard error of a posterior mean is then about sd/Neff\text{sd}/\sqrt{N_{\text{eff}}}. In practice the infinite sum is estimated from the chains and truncated where the estimated autocorrelations become noise; the program below uses Charles Geyer's rule of adding lags in pairs while the pairs stay positive.

Definition— split R-hat

Run m≥4m \ge 4 chains from dispersed starting points, discard warm-up, and split each remaining chain in half, giving 2m2m sequences of length nn. Let WW be the average within-sequence variance and B/nB/n the variance of the sequence means. The potential scale reduction factor is R^=n−1nW+BnW.\hat R = \sqrt{\frac{\frac{n-1}{n} W + \frac{B}{n}}{W}}. If all sequences explore the same distribution, R^≈1\hat R \approx 1; values above 1 mean the sequences disagree, so the chains have not mixed. Splitting catches a single chain that drifts during the run.

The program runs four chains of random-walk Metropolis on the frost model with three proposal step sizes, and computes the acceptance rate, the autocorrelation of β\beta at lags 1 and 20, the effective sample sizes and split R^\hat R for both parameters. Every row uses the same 10,000 kept draws.

python
import numpy as np

x = np.array([4.0, 2.0, 0.0, -2.0, -4.0])               # the frost trial again, temperature + 6 C
n = np.array([20, 20, 20, 20, 20])
y = np.array([19, 16, 12, 5, 1])

def log_post(theta):
    eta = theta[0] + theta[1] * x
    return np.sum(y * eta - n * np.logaddexp(0.0, eta)) - (theta @ theta) / (2 * 2.5**2)

def run_chains(step, starts, n_iter, warmup, seed):
    rng = np.random.default_rng(seed)
    chains, rates = [], []
    for s in starts:
        theta = np.array(s, dtype=float); lp = log_post(theta); acc = 0
        out = np.empty((n_iter, 2))
        for i in range(n_iter):
            prop = theta + step * rng.normal(size=2)
            lp_new = log_post(prop)
            if np.log(rng.uniform()) < lp_new - lp:
                theta, lp, acc = prop, lp_new, acc + 1
            out[i] = theta
        chains.append(out[warmup:]); rates.append(acc / n_iter)
    return np.array(chains), np.mean(rates)              # shape (chains, draws, 2)

def autocov(c):
    """Autocovariance of one chain at every lag, via the FFT."""
    m = len(c); z = c - c.mean()
    f = np.fft.rfft(z, 2 * m)
    return np.fft.irfft(f * np.conj(f))[:m] / m

def split_rhat(ch):
    """Split R-hat for one parameter; ch has shape (chains, draws)."""
    half = ch.shape[1] // 2
    s = np.concatenate([ch[:, :half], ch[:, half:2 * half]])
    W = s.var(axis=1, ddof=1).mean()
    B = half * s.mean(axis=1).var(ddof=1)
    return np.sqrt(((half - 1) / half * W + B / half) / W)

def ess(ch):
    """Effective sample size for one parameter across chains (autocorrelations summed with Geyer's rule)."""
    m, nd = ch.shape
    acov = np.array([autocov(c) for c in ch])
    W = (acov[:, 0] * nd / (nd - 1)).mean()
    var_plus = W * (nd - 1) / nd + (ch.mean(axis=1).var(ddof=1) if m > 1 else 0.0)
    rho = 1 - (W - acov.mean(axis=0)) / var_plus
    rho[0] = 1.0
    tau, t = 0.0, 0
    while t + 1 < nd:
        pair = rho[t] + rho[t + 1]                       # sum lags in pairs while the pairs stay positive
        if pair <= 0:
            break
        tau += pair; t += 2
    return m * nd / (2 * tau - 1)

starts = [(-3, -2), (3, 2), (-3, 2), (3, -2)]
print(f"{'step':>5} {'accept':>7} {'lag-1 ac':>9} {'lag-20 ac':>10} {'ESS alpha':>10} {'ESS beta':>9} {'Rhat alpha':>11} {'Rhat beta':>10}")
for step in [0.02, 0.3, 3.0]:
    ch, rate = run_chains(step, starts, n_iter=3_000, warmup=500, seed=11)
    b = ch[:, :, 1]
    ac = np.mean([autocov(c) / autocov(c)[0] for c in b], axis=0)
    print(f"{step:5.2f} {rate:7.2f} {ac[1]:9.2f} {ac[20]:10.2f} {ess(ch[:, :, 0]):10.0f} {ess(b):9.0f}"
          f" {split_rhat(ch[:, :, 0]):11.3f} {split_rhat(b):10.3f}")
print("(4 chains x 2,500 kept draws = 10,000 draws per row)")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
-201step 0.02: too small (acceptance 0.80)-201step 0.3: about right (acceptance 0.35)-201step 3: too large (acceptance 0.01)02505007501000iterationslope β
The first 1,000 iterations of the slope β in one Metropolis chain for the frost model, started at β = −2, for three step sizes. The dashed line is the posterior mean, 0.715. A tiny step accepts often but crawls; a huge step proposes wild values that are almost always rejected, so the chain sits still; a moderate step explores the posterior quickly.

The output and the figure tell one story. With tiny steps (0.02) nearly every proposal is accepted, but each move is so small that draws 20 iterations apart are still correlated at 0.84; 10,000 draws are worth only 12 independent ones for α\alpha, and R^=1.49\hat R = 1.49 says the four chains still disagree. With huge steps (3.0) almost every proposal lands in a region of negligible posterior density and is rejected, so the chain often repeats one value for a hundred iterations or more: again an effective sample size of about 50. The moderate step (0.3) accepts about a third of proposals, its autocorrelation dies out within 20 lags, R^\hat R is 1.00, and the same 10,000 draws are worth over 600 independent ones for α\alpha and about 1,700 for β\beta. (The difference between the two parameters arises because α\alpha has the wider posterior, and a single step size cannot suit both; real samplers adapt a separate scale for each direction.) For random-walk Metropolis in many dimensions, theory suggests aiming for an acceptance rate of about 0.23, and somewhat higher in one or two dimensions.

The current recommendations, from the 2021 paper by Aki Vehtari and colleagues that refined R^\hat R with rank normalisation, are to run at least four chains, to trust the results only when R^<1.01\hat R < 1.01 for every quantity of interest, and to have an effective sample size of at least about 400 for the bulk of the distribution and for its tails (tail quantiles are estimated less precisely than means). Software reports these as r_hat, ess_bulk and ess_tail.

ExplanationH

Hamiltonian Monte Carlo

Random-walk Metropolis has a fatal flaw in high dimensions. To keep a reasonable acceptance rate in dd dimensions, its step size must shrink roughly like 1/d1/\sqrt{d}, and a random walk with tiny steps needs about dd times as many iterations to cross the posterior. Guessing directions blindly is the problem: in 100 dimensions, almost every direction from a point in the posterior leads downhill.

Hamiltonian Monte Carlo (HMC) uses the gradient of the log posterior to choose directions. Picture the negative log posterior as a landscape of valleys and hills, and the current parameter value as a frictionless puck on it. Each iteration gives the puck a random push (a momentum drawn from a normal distribution) and lets it slide for a while under simulated physics: it speeds up going downhill and slows going uphill, so it follows the shape of the posterior and travels far from where it started. The physics is simulated with the leapfrog method, alternating small updates of momentum (using the gradient) and position. Exact physics would conserve the total "energy" — potential (the negative log posterior) plus kinetic — and every trajectory would be accepted; the leapfrog's small errors are corrected by a Metropolis accept-or-reject step on the energy change. The result is a valid MCMC method whose proposals are distant yet usually accepted.

The program compares the two methods on a target with dd independent normal coordinates whose standard deviations range from 1 to 3, giving each method the same budget of 40,000 density or gradient evaluations (an HMC iteration with 8 leapfrog steps costs 8). It reports the effective sample size of the widest, slowest-mixing coordinate.

python
import numpy as np

def autocov(c):
    m = len(c); z = c - c.mean()
    f = np.fft.rfft(z, 2 * m)
    return np.fft.irfft(f * np.conj(f))[:m] / m

def ess1(c):
    """Single-chain effective sample size (Geyer's initial positive sequence)."""
    rho = autocov(c) / autocov(c)[0]
    tau, t = 0.0, 0
    while t + 1 < len(c) and rho[t] + rho[t + 1] > 0:
        tau += rho[t] + rho[t + 1]; t += 2
    return len(c) / (2 * tau - 1)

# Target: d independent normals with standard deviations from 1 to 3.
# log p(q) = -sum(q^2 / (2 sd^2)), and its gradient is -q / sd^2.
def rwm(d, budget, rng):
    inv = 1 / np.linspace(1, 3, d) ** 2
    step = 2.38 / np.sqrt(d)                       # the classic scaling with dimension
    q = rng.normal(size=d); out = np.empty(budget); acc = 0
    for i in range(budget):                        # one density evaluation per iteration
        prop = q + step * rng.normal(size=d)
        if np.log(rng.uniform()) < 0.5 * (q @ (q * inv) - prop @ (prop * inv)):
            q, acc = prop, acc + 1
        out[i] = q[-1]                             # the widest coordinate mixes slowest
    return out, acc / budget

def hmc(d, budget, rng, L=8):
    inv = 1 / np.linspace(1, 3, d) ** 2
    eps0 = 1.0 / d**0.25                           # step size shrinks slowly with dimension
    q = rng.normal(size=d); out = []; acc = 0
    for _ in range(budget // L):                   # L gradient evaluations per iteration
        eps = eps0 * rng.uniform(0.3, 1.0)         # jitter, so paths do not loop back on themselves
        p = rng.normal(size=d)                     # fresh random momentum
        qn, pn = q.copy(), p - 0.5 * eps * q * inv # leapfrog: half step for momentum,
        for j in range(L):
            qn += eps * pn                         # full steps for position and momentum,
            if j < L - 1:
                pn -= eps * qn * inv
        pn -= 0.5 * eps * qn * inv                 # and a final half step
        h_old = 0.5 * (q @ (q * inv) + p @ p)      # "energy" = potential + kinetic
        h_new = 0.5 * (qn @ (qn * inv) + pn @ pn)
        if np.log(rng.uniform()) < h_old - h_new:  # accept to correct the leapfrog's small error
            q, acc = qn, acc + 1
        out.append(q[-1])
    return np.array(out), acc / (budget // L)

rng = np.random.default_rng(1987)
budget = 40_000
print(f"effective draws of the slowest coordinate per {budget:,} density or gradient evaluations")
print(f"{'dimension':>9} {'RWM accept':>11} {'RWM ESS':>8} {'HMC accept':>11} {'HMC ESS':>8}")
for d in [2, 10, 100]:
    c1, a1 = rwm(d, budget, rng)
    c2, a2 = hmc(d, budget, rng)
    print(f"{d:9} {a1:11.2f} {ess1(c1[1000:]):8.0f} {a2:11.2f} {ess1(c2[50:]):8.0f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

HMC is ahead by a factor of about 2.6 in two dimensions and 4.5 in ten, and at d=100d = 100 random-walk Metropolis delivers about 30 effective draws for the budget while HMC — not even tuned, as its 99% acceptance rate shows — delivers over 500. Theory for simple targets says HMC's step size needs to shrink only like d−1/4d^{-1/4}, which is why the gap keeps widening as models grow. The price is that HMC needs gradients (modern software computes them exactly by automatic differentiation) and that its two tuning parameters, the step size and the number of leapfrog steps, interact in awkward ways: too many steps and the puck loops back towards where it started, which is why the program jitters the step size.

The No-U-Turn Sampler (NUTS) of Matthew Hoffman and Andrew Gelman removes the second tuning parameter by extending each trajectory until it starts to turn back on itself, and Stan and PyMC adapt the step size during warm-up. HMC also gives a diagnostic that random-walk methods lack: a divergent transition, where the leapfrog simulation blows up because the posterior curves too sharply for the step size, typically in the narrow neck of a hierarchical model. Divergences are a warning that part of the posterior is not being explored, and the usual cure is to reparametrise the model, not to ignore them.

The frost model in Stan (not run here):

stan
// Stan, not run here: the frost-tolerance model
data {
  int<lower=1> K;                 // number of temperatures
  vector[K] x;                    // temperature + 6
  array[K] int<lower=0> n;        // seedlings per batch
  array[K] int<lower=0> y;        // survivors
}
parameters {
  real alpha;
  real beta;
}
model {
  alpha ~ normal(0, 2.5);
  beta ~ normal(0, 2.5);
  y ~ binomial_logit(n, alpha + beta * x);
}
generated quantities {
  real lt50 = -6 - alpha / beta;  // computed for every draw
}

and in PyMC, followed by the standard diagnostic summary from ArviZ (not run here; neither library is available in the browser):

python
# PyMC and ArviZ, not run here
import arviz as az
import numpy as np
import pymc as pm

x = np.array([4.0, 2.0, 0.0, -2.0, -4.0])
n = np.array([20, 20, 20, 20, 20])
y = np.array([19, 16, 12, 5, 1])

with pm.Model():
    alpha = pm.Normal("alpha", 0, 2.5)
    beta = pm.Normal("beta", 0, 2.5)
    pm.Binomial("y", n=n, logit_p=alpha + beta * x, observed=y)
    pm.Deterministic("lt50", -6 - alpha / beta)
    idata = pm.sample(draws=1000, tune=1000, chains=4, random_seed=1)

print(az.summary(idata))   # means, sds, intervals, ess_bulk, ess_tail, r_hat

Both run NUTS (here with four chains), report R^\hat R and bulk and tail effective sample sizes for every parameter, and warn about divergences. Their summaries should agree with our hand-built sampler to within Monte Carlo error.

ExplanationH

MCMC in practice and in history

History. The algorithm was born at Los Alamos in 1953, where Nicholas Metropolis, Arianna and Marshall Rosenbluth, and Augusta and Edward Teller used one of the first electronic computers to simulate the behaviour of a fluid of hard spheres; Arianna Rosenbluth wrote the program. W. K. Hastings generalised it in 1970. Stuart and Donald Geman's Gibbs sampler (1984), which updates one parameter at a time from its conditional distribution, came from image processing, and Alan Gelfand and Adrian Smith's 1990 paper showed statisticians how these methods could compute Bayesian posteriors. The BUGS project made Gibbs sampling available to applied researchers in the 1990s. Hamiltonian ("hybrid") Monte Carlo was invented by physicists for lattice quantum chromodynamics in 1987, brought into statistics by Radford Neal, and made automatic by NUTS and by Stan, first released in 2012.

Tools in 2026. NUTS in Stan, PyMC, NumPyro and Turing is the default for models with continuous parameters; ArviZ computes diagnostics for all of them. Gibbs-based tools such as JAGS remain in use, especially where parameters are discrete. When MCMC is too slow — huge data sets, models refitted constantly — practitioners turn to approximations: variational inference fits a simple distribution close to the posterior by optimisation and is fast but tends to understate uncertainty; INLA computes accurate approximations for the large class of latent Gaussian models; sequential Monte Carlo suits data that arrive over time. Each trades some accuracy for speed, and a careful analyst checks the approximation against MCMC on a smaller version of the problem.

Good practice. Run several chains from dispersed starting points; check R^\hat R, bulk and tail effective sample sizes and divergences for every quantity you report; look at trace plots; report Monte Carlo standard errors when precision matters; and test the whole pipeline on simulated data where you know the truth, a technique called simulation-based calibration that the next lesson carries out.

Common misconceptionsH

Common misconceptions

Misconception

"The draws are a random sample from the posterior." They are a correlated sequence whose distribution approaches the posterior. Averages still converge, but 10,000 draws can be worth 600 independent ones, or 12. Always look at the effective sample size, not the number of iterations.

Misconception

"A high acceptance rate means the sampler is working well." The tiny-step chain above accepted 90% of its proposals and was nearly useless. For random-walk Metropolis, rates around 0.2 to 0.5 usually mix best; for HMC, Stan targets an acceptance statistic of about 0.8 by default.

Misconception

"R^=1.00\hat R = 1.00 proves convergence." It shows that the chains agree with each other, not that they have found the whole posterior. Chains trapped in the same mode, or a posterior region too narrow for the sampler to enter (signalled in HMC by divergences), can leave R^\hat R at 1.00.

Misconception

"Thinning — keeping only every tenth draw — makes the estimates better." Thinning reduces autocorrelation between the draws you keep, but it throws away information, so estimates from the thinned chain are never more precise than from the full one. Its legitimate use is saving storage or memory.

Misconception

"If something looks wrong, just run the chain longer." Sometimes that works. But when the sampler cannot handle the posterior's geometry — strong correlations, a funnel in a hierarchical model, divergences — more iterations only produce more biased draws. The cure is usually to reparametrise the model, rescale the data or use a better sampler.

Exercises

Exercises

1. Markov chain Monte Carlo

Warm-upHuman

Metropolis–Hastings can sample from a posterior p(θ∣y)=p(y∣θ) p(θ)/p(y)p(\theta \mid y) = p(y \mid \theta)\,p(\theta)/p(y) without ever computing the evidence p(y)p(y). Why?

Choose one

2. Markov chain Monte Carlo

Warm-upHuman

Random-walk Metropolis targets the standard normal density, π(x)∝e−x2/2\pi(x) \propto e^{-x^2/2}. The chain is at x=1x = 1 and proposes x′=2x' = 2. What is the probability that the move is accepted, as a percentage rounded to the nearest whole number?

3. Markov chain Monte Carlo

CoreHuman

A chain's autocorrelations are well described by ρk=0.8k\rho_k = 0.8^k for every lag k≥1k \ge 1. Using Neff=N/(1+2∑k≥1ρk)N_{\text{eff}} = N / (1 + 2\sum_{k \ge 1} \rho_k), what is the effective sample size of N=9,000N = 9{,}000 draws?

4. Markov chain Monte Carlo

Warm-upHuman

A grid approximation uses 50 points along each parameter. What is the smallest number of parameters for which the grid needs more than a trillion (101210^{12}) evaluations of the posterior?

5. Markov chain Monte Carlo

CoreHuman

A colleague fits a model with four chains of 1,000 kept draws each. For one parameter the summary shows r_hat = 1.25 and ess_bulk = 35, and the trace plot shows two chains wandering around 0.5 and two around 1.8. What should they do?

Choose one

6. Markov chain Monte Carlo

CoreComputational

Write metropolis(log_p, x0, step, n_iter, seed=0), a random-walk Metropolis sampler for a one-dimensional target. log_p(x) returns the log of the target density up to an additive constant, and may return -np.inf outside the support. Propose x + step * N(0, 1), accept with probability min⁡(1,elog⁡p(x′)−log⁡p(x))\min(1, e^{\log p(x') - \log p(x)}), and return a NumPy array of the n_iter values of the chain (a rejected proposal repeats the current value). Use np.random.default_rng(seed).

The tests sample from N(3,22)N(3, 2^2) starting far away at −10-10, and from an exponential distribution whose density is zero for x≤0x \le 0.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Markov chain Monte Carlo

StretchComputational

Write split_rhat(chains), where chains is an array of shape (m, n) holding mm chains of nn draws of one parameter. Split each chain into halves of length n // 2 (dropping the last draw if nn is odd), giving 2m2m sequences; let WW be the mean within-sequence variance and B/nB/n the variance of the sequence means (both with ddof=1); and return R^=h−1hW+B/nW,h=n/ ⁣/2.\hat R = \sqrt{\frac{\frac{h-1}{h}W + B/n}{W}}, \quad h = n /\!/ 2. The tests include four well-mixed chains, a chain centred elsewhere, a chain that drifts during the run, and a small example you can check by hand.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources