A basketball player makes 3 of her first 4 free throws. What is her real hit rate p? Bayes' theorem answers with a whole distribution for p, the posterior. Writing it down is easy up to one number, the constant that makes it add up to 1, and that number is exactly what becomes impossible to compute when there are many unknowns. The Metropolis algorithm gets around it with the tool of the previous chapters: it builds a Markov chain whose stationary distribution is the posterior, using only ratios, in which the constant cancels.
By the end you can
- Write the posterior of a probability as prior times likelihood, up to a constant.
- Restrict the unknown to a grid and find the posterior weight of each grid value.
- Build the transition matrix of the Metropolis chain with neighbour proposals.
- Prove with detailed balance that its stationary distribution is the posterior.
- Solve πP = π for the chain and compute the posterior mean from it.
A short recap of the Likelihood, Beta Priors & Bayesian Updating chapter, which builds each piece slowly. Before the data, a prior density f(p), here a beta, says what we believe about p. The data are y successes in n independent trials; their probability, read as a function of p, is the likelihood. Bayes' rule multiplies the two and rescales: the new weight of each value is its old weight times how well it explains the data, divided by the total.
Only the kernel matters
With a Beta(a, b) prior, f(p) = p^(a−1)(1 − p)^(b−1)/B(a, b). Multiply by the likelihood and drop every factor that does not contain p: B(a, b), the binomial coefficient C(n, y) and the denominator are all constants. What is left is the kernel of the posterior; call it g. The posterior is g divided by its own total.
To work with numbers instead of a curve, let p take only a few values, a grid p₁ < p₂ < … < pₘ. The posterior on the grid gives each value the weight g(pₖ), rescaled to add up to 1. For the player on the grid {1/4, 1/2, 3/4}:
With three grid points the sum is trivial. With ten unknown parameters and a grid of 100 values for each, it would have 100¹⁰ = 10²⁰ terms, more than any computer can add. Ratios such as g(3/4)/g(1/2) = 81/64, on the other hand, are always cheap. Metropolis needs nothing else.
The chain walks on the grid. From the current point pᵢ, one step is:
- Propose a neighbour: pᵢ₋₁ or pᵢ₊₁, each with probability ½.
- If the proposal falls off the grid (left of p₁ or right of pₘ), reject it: stay at pᵢ.
- Otherwise accept it with probability min(1, g(pⱼ)/g(pᵢ)): always if the new point is at least as plausible, sometimes if it is less. If it is not accepted, stay at pᵢ.
The free-throw chain
| from ↓ to → | 1/4 | 1/2 | 3/4 |
|---|---|---|---|
| 1/4 | 1/2 | 1/2 | 0 |
| 1/2 | 9/128 | 55/128 | 1/2 |
| 3/4 | 0 | 32/81 | 49/81 |
The Markov-chains chapter showed that a walk between neighbours satisfies detailed balance in its stationary state: the flow across each edge is the same both ways. Metropolis is built so that g itself balances every edge. That is the whole proof:
Solving πP = π and the posterior mean
| 1/4 | 1/2 | 1/2 | 0 |
| 1/2 | 9/128 | 55/128 | 1/2 |
| 3/4 | 0 | 32/81 | 49/81 |
π = (9/154, 32/77, 81/154)
g(p) = p^(a−1+y) (1 − p)^(b−1+n−y) is prior kernel times likelihood; the chain only ever uses ratios of g. The bars are the stationary distribution of the chain, found by solving πP = π (exactly, as fractions, for up to 9 points): it is the posterior on the grid, without ever dividing g by its sum. Press play: the walker proposes a neighbour, a green arrow is an accepted move, a red one a rejection (it stays and that point is counted again). Moves uphill are always accepted; downhill ones only sometimes. Use fast and watch the dots settle on the bars.
For a big problem nobody writes P down. The chain is simulated: start anywhere, take many steps, and average whatever you want over the values visited. The long-run average of a Markov chain equals the average under π (the ergodic result of the Markov-chains chapter), so the average of the visited p tends to the posterior mean. Running a chain well (a continuous p, uneven proposals, burn-in, step size and acceptance rate) is the subject of the Metropolis–Hastings chapter.
| Step | What to do |
|---|---|
| 1 | Kernel: g(p) = p^(a−1+y)(1 − p)^(b−1+n−y). Drop every constant. |
| 2 | Evaluate g at each grid point; scale to whole numbers if you like (only ratios matter). |
| 3 | Neighbour entries: P_ij = ½ min(1, gⱼ/gᵢ). Diagonal: 1 minus the rest (it holds the off-grid ½ at the ends). |
| 4 | Check that every row adds up to 1. |
| 5 | Solve πP = π with Σπ = 1; for a neighbour walk, balance each edge: πᵢPᵢⱼ = πⱼPⱼᵢ. |
| 6 | Posterior mean: Σ pₖ π(pₖ). Sanity check: π should be proportional to g. |
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 |
|---|---|---|
| P_ij = g_j/g_i | ½ · min(1, g_j/g_i) | the proposal chance ½ comes first, and a ratio above 1 is not a probability |
| rows that do not add up to 1 | put the rest on P_ii | rejections and off-grid proposals mean staying |
| at an end, always propose the inside point | propose off the grid with ½ and stay | unequal proposals break detailed balance and change the stationary distribution |
| keeping C(n, y) and B(a, b) | drop them | they cancel in every ratio; only the kernel matters |
| posterior mean = the most visited point | Σ pₖ π(pₖ) | the mean is a weighted average, not the mode |
Key ideas
- Posterior ∝ prior × likelihood; with a Beta(a, b) prior and y of n, g(p) = p^(a−1+y)(1 − p)^(b−1+n−y).
- The normalising constant is one number; it cancels in every ratio g(pⱼ)/g(pᵢ).
- Metropolis with neighbour proposals: P_ij = ½ min(1, g_j/g_i) for j = i ± 1; staying takes the rest, including proposals off the grid.
- g_i P_ij = ½ min(g_i, g_j) = g_j P_ji: detailed balance, so the posterior is the stationary distribution.
- Solve πP = π (or run the chain), then the posterior mean is Σ pₖ π(pₖ).
- Simulated chains need burn-in and many steps, because successive values are correlated.