Markov Chain Monte Carlo: The Metropolis-Hastings Algorithm
What You'll Learn
You'll learn how MCMC generates samples from complex posterior distributions when exact integration is impossible, using a clever accept-reject mechanism.
The Problem
In Bayesian inference, we often need to compute expectations over posterior distributions that have no closed-form solution. Direct sampling is impossible, and even Monte Carlo integration (as you learned) requires being able to sample from the distribution—which we can't do easily for complex posteriors.
The Metropolis-Hastings Solution
Think of exploring a dark cave with a flashlight. You can't see the whole cave, but you can see where you are now and make informed guesses about where to step next. Metropolis-Hastings works similarly:
- Start somewhere in parameter space
- Propose a new location using a proposal distribution (like "try a random step within 2 meters")
- Decide whether to accept the proposal based on an acceptance ratio
- Repeat many times, building a chain of samples
The acceptance rule is elegant: you compare the posterior density at the proposed point to your current point. If the proposal is in a higher-density region, always accept. If lower, accept with probability proportional to the density ratio. This ensures you spend more time in high-probability regions.
Why It Works
The "Markov Chain" part means each step only depends on the current position. Over many iterations, the chain "forgets" where it started and converges to samples that genuinely represent the posterior distribution—even though you never computed it explicitly!
Key Takeaway: Metropolis-Hastings generates samples from complex posteriors by constructing a Markov chain that proposes moves and accepts/rejects them based on density ratios, allowing Bayesian inference when exact methods fail.