Why integrals are hard
Everything a Bayesian wants from a posterior is an integral. The posterior mean of a parameter is ; 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 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 evaluations of the posterior:
| Parameters | 1 | 2 | 5 | 10 | 100 |
|---|---|---|---|---|---|
| Grid points | 50 | 2,500 |
Beyond about five parameters, grids are hopeless. There is a way out, and it comes from simulation. If we could draw independent values from the posterior, we could estimate any posterior expectation by an average, , with an error that shrinks like 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.
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 is stationary for the chain if, when the current value is drawn from , 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 , just as averages of independent draws would. MCMC turns this around: we choose 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 known up to a constant, choose a proposal distribution and a starting value . At each step :
- Propose .
- Compute the acceptance probability
- With probability set (accept); otherwise set (reject, and repeat the current value).
If the proposal is symmetric, — for example with — the terms cancel and . 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 : for all , . Consequently is a stationary distribution of the chain.
Proof
For , the chain moves from to only by proposing and accepting, so . Write and . Then and , so Detailed balance says the probability flow from any to any equals the flow back. Summing (or integrating) the flow into over all , including the probability of staying put, gives , 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.
Metropolis from scratch
Our first target is the posterior from the previous lesson, , written only as the unnormalised product of likelihood and uniform prior, . 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.
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))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).
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 as centred at −6 °C so that is the log-odds of survival there and is the change in log-odds per degree. We give both parameters weakly informative priors. The breeders care most about the LT50, the temperature at which half the seedlings survive, which is . 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.
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))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 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.
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 , , is the correlation between draws steps apart in a chain. The effective sample size of correlated draws is 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 . 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 chains from dispersed starting points, discard warm-up, and split each remaining chain in half, giving sequences of length . Let be the average within-sequence variance and the variance of the sequence means. The potential scale reduction factor is If all sequences explore the same distribution, ; 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 at lags 1 and 20, the effective sample sizes and split for both parameters. Every row uses the same 10,000 kept draws.
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)")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 , and 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, is 1.00, and the same 10,000 draws are worth over 600 independent ones for and about 1,700 for . (The difference between the two parameters arises because 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 with rank normalisation, are to run at least four chains, to trust the results only when 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.
Hamiltonian Monte Carlo
Random-walk Metropolis has a fatal flaw in high dimensions. To keep a reasonable acceptance rate in dimensions, its step size must shrink roughly like , and a random walk with tiny steps needs about 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 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.
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}")HMC is ahead by a factor of about 2.6 in two dimensions and 4.5 in ten, and at 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 , 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, 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):
# 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_hatBoth run NUTS (here with four chains), report 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.
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 , 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 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
" 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 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
1. Markov chain Monte Carlo
Warm-upHumanMetropolis–Hastings can sample from a posterior without ever computing the evidence . Why?
2. Markov chain Monte Carlo
Warm-upHumanRandom-walk Metropolis targets the standard normal density, . The chain is at and proposes . What is the probability that the move is accepted, as a percentage rounded to the nearest whole number?
3. Markov chain Monte Carlo
CoreHumanA chain's autocorrelations are well described by for every lag . Using , what is the effective sample size of draws?
4. Markov chain Monte Carlo
Warm-upHumanA grid approximation uses 50 points along each parameter. What is the smallest number of parameters for which the grid needs more than a trillion () evaluations of the posterior?
5. Markov chain Monte Carlo
CoreHumanA 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?
6. Markov chain Monte Carlo
CoreComputationalWrite 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 , 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 starting far away at , and from an exponential distribution whose density is zero for .
7. Markov chain Monte Carlo
StretchComputationalWrite split_rhat(chains), where chains is an array of shape (m, n) holding chains of draws of one parameter. Split each chain into halves of length n // 2 (dropping the last draw if is odd), giving sequences; let be the mean within-sequence variance and the variance of the sequence means (both with ddof=1); and return
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.
Further reading and resources
- Equation of State Calculations by Fast Computing Machines · Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosenbluth, Augusta Teller and Edward Teller · 1953The original Metropolis algorithm, for simulating a fluid of hard spheres.
- Monte Carlo Sampling Methods Using Markov Chains and Their Applications · W. K. Hastings · 1970The generalisation to asymmetric proposals.
- Inference from Iterative Simulation Using Multiple Sequences · Andrew Gelman and Donald Rubin · 1992The paper that introduced R-hat.
- Rank-normalization, folding, and localization: An improved R-hat for assessing convergence of MCMC · Aki Vehtari, Andrew Gelman, Daniel Simpson, Bob Carpenter and Paul-Christian Bürkner · 2021The diagnostics Stan, PyMC and ArviZ report today, with recommended thresholds.
- MCMC using Hamiltonian dynamics · Radford Neal · 2011A clear and thorough account of HMC.
- The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo · Matthew Hoffman and Andrew Gelman · 2014NUTS, the default sampler in Stan and PyMC.
- A Conceptual Introduction to Hamiltonian Monte Carlo · Michael Betancourt · 2017Why HMC works in high dimensions, explained geometrically.
- Stan documentationThe reference manual explains Stan's effective sample size and R-hat computations in detail.
- PyMCA probabilistic programming library for Python.