Metropolis-Hastings from scratch

Exploring a posterior you cannot write down

Often you can write the posterior only up to a constant, as prior times likelihood, and you cannot add it up or find its mean with algebra. Metropolis-Hastings builds a random walk that visits places in proportion to the posterior. At the current point $\theta$, propose a nearby point $\theta'$, for example $\theta$ plus a bit of normal noise. Compare the posterior heights with the ratio $r=p(\theta')/p(\theta)$. If $r\ge1$ the new point is at least as good, so move. Otherwise move with probability $r$. If you do not move, write down the current point again. The unknown constant is the same in both heights, so it cancels in the ratio. That is why the method works.

The list of visited points is the chain. After a warm-up, called burn-in, it behaves like a sample from the posterior, so the mean and the interval come from plain averages and percentiles of the chain. The step size is the main knob. If it is too small, nearly every move is accepted but the chain crawls. If it is too large, most proposals land in bad places and are rejected, so the chain sits still. A good chain accepts roughly a quarter to a half of the proposals. Always look at the chain: plot it, and start it from different places to see that they agree.

• Proposal and ratio: propose a nearby point and compare posterior heights. The unknown constant cancels.
• Chain: the visited points, repeated when a move is rejected. Drop the burn-in, then average.
• Step size: too small crawls, too large gets stuck. Aim at accepting about a quarter to a half.

Lab · what's graded

• A good proposal15 pts
• A worse proposal15 pts
• A log ratio10 pts
• Averaging a chain10 pts
• A step that is too large10 pts
• One iteration10 pts
• Match the vocabulary15 pts
• Why the constant is not needed15 pts