Content
Summary
The Metropolis algorithm draws samples from a probability distribution known only up to a normalising constant, such as a Bayesian posterior. It proposes a random move and accepts it with probability equal to the ratio of target densities (capped at 1). The resulting Markov chain has the target as its stationary distribution, so a histogram of its visits approximates the posterior.
Intuition
Imagine a hiker walking in fog over a landscape whose height is the posterior density. The hiker cannot see the whole map, only the height at the current spot and at a trial spot nearby. If the trial spot is higher, they always step there. If it is lower, they step there only with probability equal to the ratio of heights, so they sometimes go downhill. Over a long walk, the time spent in each region is proportional to its height, which is exactly the posterior probability. Because only ratios matter, the intractable normalising constant (the marginal likelihood) cancels. The proposal width is a tuning knob: too small and the chain creeps slowly with high acceptance, too large and most proposals are rejected so the chain sticks. An acceptance rate around 20-40 percent is a good target in moderate dimensions.
Key equations
The target is known only up to a constant: likelihood times prior.
A symmetric proposal, for example a normal random walk centred at the current value.
Acceptance probability; the normalising constant cancels in the ratio.
Detailed balance, which guarantees that is stationary.
Derivation
- Goal: build a Markov chain with transition kernel whose stationary distribution is .
- Sufficient condition: detailed balance, for all .
- For different from , .
- With symmetric , detailed balance requires .
- Choose . If , then and , so both sides equal .
- The case is symmetric, so detailed balance holds and is stationary.
- With irreducibility and aperiodicity, the chain converges to , and ergodic averages estimate posterior expectations.
Worked example
Target proportional to on , from 3 successes and 2 failures with a flat prior. The chain is at and proposes . Compute the acceptance probability. If the uniform draw is , is the move accepted?
- Compute .
- Compute .
- Ratio = 0.03087/0.03125 = 0.988.
- .
- Compare with : , so accept.
Answer is about 0.988; the move to 0.7 is accepted, so .
Common mistakes
- Forgetting that on rejection the chain repeats the current value; dropping the repeat biases the samples.
- Using an asymmetric proposal without the Hastings correction .
- Judging convergence from a single chain or ignoring burn-in; run several chains and check R-hat and trace plots.
- Tuning for a very high acceptance rate; tiny steps give strongly autocorrelated samples.
- Treating samples as independent when computing standard errors; use effective sample size.
- Computing ratios of raw densities and underflowing; work with log densities.