The previous chapter's Metropolis chain walked on a grid and proposed the left or the right neighbour with chance ½ each. That evenness was quietly essential: the chapter warned that proposing unevenly, for example always proposing the inside point at the ends of the grid, would make the chain settle on the wrong distribution. Real problems need uneven proposals all the time, and continuous parameters instead of grids. In 1970 W. K. Hastings showed that one extra factor in the acceptance chance repairs any proposal. With it, the algorithm, Metropolis–Hastings, can sample from almost any posterior you can write down up to a constant.
By the end you can
- Write the Metropolis–Hastings acceptance chance and say what each factor does.
- Prove with detailed balance that it targets g for any proposal, and show what goes wrong without the correction.
- Run random-walk Metropolis on a continuous p by hand, working in logarithms.
- Use proposals drawn from the prior, and explain why then only the likelihood ratio decides.
- Read a trace, choose a burn-in and a step size from the acceptance rate, and estimate from the samples.
The target is a posterior known only up to a constant: g(x) = prior × likelihood, with every factor that does not contain x dropped. The chain is at x. One step:
- Propose a new value x′ by drawing it from a proposal distribution q(x′ | x), which may depend on where you are.
- Compute the acceptance chance α (below).
- Draw u uniformly from [0, 1]. If u < α, move to x′. Otherwise stay at x, and record x again: a rejected proposal still counts as a step.
Why the reverse move goes on top: if x′ is easy to propose from x but x is hard to propose from x′, the chain would arrive at x′ often and leave rarely, piling up there for reasons that have nothing to do with g. The factor q(x | x′)/q(x′ | x) is below 1 exactly in that case, and it accepts such moves less often, by the right amount.
On a grid, the chance of moving from i to j ≠ i is P_ij = q(j | i) · α_ij: propose j, then accept. The proof of the previous chapter goes through with q inside the min:
The free-throw grid with an uneven proposal
Take the previous chapter's example: prior Beta(2, 2), 3 hits in 4, grid {1/4, 1/2, 3/4}, so g ∝ (9, 64, 81). Now use the proposal that chapter forbade: from an end, always propose the middle; from the middle, propose either end with chance ½. The proposal is uneven, q(2 | 1) = 1 but q(1 | 2) = ½, so the Hastings factor matters.
| from ↓ to → | 1/4 | 1/2 | 3/4 |
|---|---|---|---|
| 1/4 | 0 | 1 | 0 |
| 1/2 | 9/64 | 23/64 | 1/2 |
| 3/4 | 0 | 32/81 | 49/81 |
Balance across the edges: π₁ · 1 = π₂ · 9/64 gives π₂ = (64/9) π₁, and π₂ · ½ = π₃ · 32/81 gives π₃ = 9 π₁. So π ∝ (9, 64, 81), the posterior, as promised. Now drop the correction and accept with min(1, gⱼ/gᵢ) as plain Metropolis would. The edges become P₂₁ = ½ · 9/64 = 9/128 and P₃₂ = 1 · 64/81, and the same balance gives π ∝ (9, 128, 81): the middle gets twice its weight, because it is proposed twice as eagerly as it proposes. The posterior mean comes out as 127/218 ≈ 0.583 instead of the correct 95/154 ≈ 0.617.
| chain | stationary distribution | mean of p |
|---|---|---|
| with the Hastings factor | (9, 64, 81) / 154 | 95/154 ≈ 0.617 |
| without it | (9, 128, 81) / 218 | 127/218 ≈ 0.583, wrong |
Without a grid, p can be any number in [0, 1]. The simplest proposal is a random step: p′ = p + s·Z, where Z is a standard normal number and s, the step size, is a number you choose. The chance of proposing p′ from p depends only on the distance |p′ − p|, so it is the same both ways: the proposal is symmetric, the Hastings factor is 1, and α = min(1, g(p′)/g(p)). A proposal outside [0, 1] has g(p′) = 0 and is simply rejected.
For the player the target is the kernel of Beta(5, 3), g(p) = p⁴(1 − p)². Five steps by hand from p = 0.5, with the random steps and the uniform numbers u already drawn:
| step | p | p′ | g(p′) / g(p) | u | result |
|---|---|---|---|---|---|
| 1 | 0.50 | 0.62 | 0.02134 / 0.01563 = 1.366 | — | ratio ≥ 1: accept, p = 0.62 |
| 2 | 0.62 | 0.90 | 0.00656 / 0.02134 = 0.308 | 0.52 | u > α: reject, p stays 0.62 |
| 3 | 0.62 | 0.55 | 0.01853 / 0.02134 = 0.868 | 0.31 | u < α: accept, p = 0.55 |
| 4 | 0.55 | 1.06 | 0 (outside [0, 1]) | — | reject, p stays 0.55 |
| 5 | 0.55 | 0.71 | 0.02137 / 0.01853 = 1.153 | — | accept, p = 0.71 |
The recorded chain is 0.50, 0.62, 0.62, 0.55, 0.55, 0.71. The repeated values are not a mistake: staying put is how the chain spends more time in plausible regions. If the rejected steps were left out of the record, the samples would follow the wrong distribution.
Work in logarithms
With real data the kernel itself is unusable. For 7500 hits in 10 000 throws, g(0.75) contains 0.75⁷⁵⁰⁰ = e^(7500 · ln 0.75) ≈ e^(−2158), far below the smallest number a computer can store (about 10⁻³⁰⁸), so both g values come out as 0 and the ratio as 0/0. Compare logarithms instead: ln g(p) = (a′ − 1) ln p + (b′ − 1) ln(1 − p), and accept when ln u < ln g(p′) − ln g(p) (plus ln q(p | p′) − ln q(p′ | p) for an uneven proposal). The differences are ordinary numbers.
A proposal does not have to be a small step. One idea is to ignore where you are and draw p′ from the prior: q(p′ | p) = f(p′). This is very uneven (the chance of proposing p′ does not depend on p at all), so the Hastings factor is essential. It simplifies beautifully:
Forget the correction and accept with min(1, g(p′)/g(p)), and the chain targets g · f instead of g, the prior multiplied in twice: detailed balance holds, but for the wrong distribution. With a mild prior the error is small; with a strong one it is plain to see. The figure below lets you switch the correction off. One practical caveat: drawing from the prior only works well when the prior is not much wider than the posterior. With a lot of data the posterior is narrow, almost every draw from the prior lands where the likelihood is tiny, and nearly everything is rejected.
The theory promises the right distribution in the long run; practice decides how long that is. Three things to watch, all visible in the figure:
| what | problem | what to do |
|---|---|---|
| burn-in | the first steps still remember the starting point; started at p₀ = 0.05, the trace takes a while to climb to where the posterior is | throw away the first part of the run, until the trace stops drifting |
| step too small | almost every proposal is accepted, but each moves only a little; the trace wanders slowly and successive values are nearly equal | increase s |
| step too large | most proposals land outside [0, 1] or far downhill and are rejected; the trace shows long flat stretches | decrease s |
| acceptance rate | the share of accepted proposals summarises both problems | for one parameter aim for roughly 20–50 % (about 44 % is the classic best for a bell-shaped target); with many parameters, lower, around 25 % |
Successive values of a chain are correlated, so 10 000 steps carry less information than 10 000 independent draws, sometimes only as much as a few hundred. A well-tuned trace looks like dense, even noise around a fixed level, with no slow drifts and no flat stretches. A useful check: run the chain again from a very different starting point; after burn-in the two runs should agree.
Press play. Top: the value of p at each step, starting from p₀; the first steps still remember the start and are thrown away (the red band, burn-in). Bottom: the histogram of the kept steps against the exact posterior (green). With the random walk, try a tiny step (s = 0.01: almost everything is accepted, but the chain crawls) and a huge one (s = 1: most proposals land outside [0, 1] or far downhill and are rejected); somewhere around 20–50 % acceptance mixes best. Then switch to drawing proposals from the prior and turn the Hastings correction off: the histogram drifts to the red curve, because without the factor q(p)/q(p′) the prior is counted twice. The strong prior Beta(8, 8) makes the error easy to see.
Estimating from the samples
After burn-in, the kept values behave like (correlated) draws from the posterior, so any question about p becomes counting or averaging. The posterior mean is the average of the kept values. P(p > ½) is the share of kept values above ½. A 95 % credible interval runs from the value with 2.5 % of the samples below it to the value with 97.5 % below it. For the player, the exact answers from the Beta(5, 3) posterior are 0.625 and 99/128 ≈ 0.773, and a long run of the chain gets as close to them as you like.
| step | what to do |
|---|---|
| 1 | Write the target kernel g = prior × likelihood, dropping constants (in logs, for a program). |
| 2 | Write the proposal q(x′ | x). Is it symmetric? Then the Hastings factor is 1. |
| 3 | α = min(1, g(x′) q(x | x′) / (g(x) q(x′ | x))): the reverse proposal on top. |
| 4 | Grid: P_ij = q(j | i) α_ij for j ≠ i, and P_ii = 1 minus the rest of the row. |
| 5 | Simulation: accept if u < α; otherwise record the current value again. |
| 6 | Discard the burn-in, check the trace and the acceptance rate, then average, count or take quantiles. |
A round of 10 questions
Answer as many as you can. Mistakes come back at the end for a review round.
Every exercise is made on the spot, so a new round is never the same. The computer picks the answer first and builds the question around it, working with exact fractions, so the answer key is always right. Answers are read exactly: 0.75, 3/4 and 6/8 count as the same number (where lowest terms are asked for, 6/8 just gets a reminder). A wrong answer shows the worked solution line by line, in the order the lesson does it; the new number in each line is coloured.
| Wrong | Right | Why |
|---|---|---|
| min(1, g′/g) with an uneven proposal | multiply by q(x | x′)/q(x′ | x) | without it the chain targets the wrong distribution, (9, 128, 81) instead of (9, 64, 81) |
| q(x′ | x)/q(x | x′) | q(x | x′)/q(x′ | x) | the reverse move goes on top |
| skipping rejected steps in the record | record the current value again | the repeats are what weights the plausible values |
| pushing a proposal outside [0, 1] back to the edge | reject it (g = 0 there) | moving it changes q, and the edges would be proposed too often |
| acceptance near 100 % means the chain works well | it means the steps are too small | the chain crawls; aim for 20–50 % with one parameter |
| using every step, from the first | discard the burn-in | the start can be far from the posterior |
| computing g(p) directly with lots of data | compare ln g | the powers underflow to 0, and 0/0 is meaningless |
Key ideas
- Metropolis–Hastings: propose x′ from q(x′ | x), accept with α = min(1, g(x′) q(x | x′) / (g(x) q(x′ | x))), otherwise stay.
- The reverse proposal goes on top; for a symmetric proposal the factor is 1 and it is plain Metropolis.
- g_i q(j | i) α_ij = min(g_i q(j | i), g_j q(i | j)) is symmetric: detailed balance, so the target is stationary for any proposal.
- Without the factor an uneven proposal biases the chain: on the free-throw grid, (9, 128, 81) instead of (9, 64, 81).
- Random walk p′ = p + s·Z: symmetric; reject proposals outside [0, 1]; compare logarithms.
- Proposals drawn from the prior leave only the likelihood ratio, min(1, L(p′)/L(p)).
- Discard the burn-in, tune s to about 20–50 % acceptance, remember the samples are correlated.
- Estimate by averaging, counting and taking quantiles of the kept values.