The Metropolis-Hastings Algorithm
You'll learn the accept-reject mechanism that makes it possible to sample from complex posterior distributions without computing normalizing constants.
The Core Idea
Imagine you're exploring a dark mountain range wearing night-vision goggles that show elevation (your posterior probability). You want to collect soil samples proportional to altitude—more samples from peaks, fewer from valleys. But you can only see your immediate surroundings, not the whole landscape.
The Metropolis-Hastings algorithm solves this by creating a smart random walk:
- Propose a new location nearby (a candidate parameter value)
- Compare the "height" (posterior probability) at your current spot vs. the proposal
- Decide: If the proposal is higher, always go there. If lower, sometimes go there anyway (with probability proportional to the height ratio)
- Repeat thousands of times
This accept-reject mechanism is brilliant because:
- You never need to calculate the normalizing constant (the "evidence" that makes probabilities sum to 1)
- You only need to evaluate the ratio of posterior probabilities
- Over time, you visit regions proportional to their posterior probability
The Mathematical Acceptance Rule
Accept the proposal with probability:
α = min(1, P(θ*|data) / P(θ_current|data))
Where θ* is your proposed parameter value. If the ratio exceeds 1 (proposal better), always accept. Otherwise, accept probabilistically—this prevents getting stuck in local peaks and ensures proper exploration.
The occasional "downhill" moves are crucial: they let the chain escape local maxima and eventually converge to the true posterior distribution.
Key Takeaway: The Metropolis-Hastings accept-reject mechanism lets you sample from any posterior by comparing probability ratios, making Bayesian inference practical even when analytical solutions don't exist.