Overview
The Metropolis–Hastings algorithm is a family of Markov Chain Monte Carlo (MCMC) methods used to sample from complex Bayesian posterior distributions when direct sampling is not possible.
The Metropolis algorithm is the simplest version, and the Gibbs sampler is a special case of Metropolis–Hastings where every proposed move is always accepted because proposals are drawn exactly from conditional posteriors.
1. The Metropolis Algorithm
Algorithm steps
- Initialize
- Choose a starting value $θ^{(0)}$ such that $p(θ^{(0)} \mid y) > 0$.
- The starting point may come from an approximation or a crude estimate.
- Iterate for t = 1, 2, …
- (a) Propose a candidate value $θ^* \sim J_t(θ^* \mid θ^{(t-1)})$ where $J_t$ is the proposal (jumping) distribution.
- For the basic Metropolis algorithm, $J_t$ must be symmetric:
- $J_t(θ_a \mid θ_b) = J_t(θ_b \mid θ_a)$
- (b) Compute the acceptance ratio $r = \frac{p(θ^* \mid y)}{p(θ^{(t-1)} \mid y)}$
- (c) Accept or reject the proposal
- $θ^{(t)} = \begin{cases} θ^*, & \text{with probability } \min(r, 1) \\ θ^{(t-1)}, & \text{otherwise.} \end{cases}$
Even if the proposal is rejected (so $θ^{(t)} = θ^{(t-1)}$), the iteration still counts toward the total.
Example — Bivariate unit normal
- Target distribution:
- $p(θ \mid y) = N(θ \mid 0, I)$, a bivariate standard normal.
- Proposal distribution:
- $J_t(θ^* \mid θ^{(t-1)}) = N(θ^* \mid θ^{(t-1)}, 0.2^2 I)$, i.e. a local random walk.
- Acceptance ratio:
- $r = \frac{N(θ^* \mid 0, I)}{N(θ^{(t-1)} \mid 0, I)}$
- This proposal is symmetric, satisfying
- $J_t(θ_a \mid θ_b) = J_t(θ_b \mid θ_a)$.
- When the proposal variance is small, the chain moves slowly—producing an inefficient “random walk” behavior.
2. Intuition and Connection to Optimization
The Metropolis algorithm behaves like a stochastic mode-finding procedure:
- If the proposed step increases the posterior density, accept it.
- If it decreases the density, accept it only with probability equal to rrr.
Hence, the algorithm explores the posterior surface but avoids getting stuck only at the mode.
3. Why the Metropolis Algorithm Works
Two-part reasoning
- The sequence $\{θ^{(t)}\}$ forms a Markov chain that is:
- Irreducible (can reach any region of the space),
- Aperiodic (does not oscillate predictably),
- Non-transient (does not diverge).
- The chain’s stationary distribution is exactly the target posterior $p(θ \mid y)$.
Intuitive proof idea
- Because of the symmetric proposal and the acceptance rule, the chain satisfies detailed balance:
- $p(θ_a \mid y) J_t(θ_b \mid θ_a) = p(θ_b \mid y) J_t(θ_a \mid θ_b)$
- Hence, the probability of moving from $θ_a$ to $θ_b$ equals that of moving from $θ_b$ to $θ_a$, implying $p(θ \mid y)$ is stationary.
4. The Metropolis–Hastings Algorithm (Generalization)
The Metropolis–Hastings (MH) algorithm relaxes the symmetry restriction on the proposal distribution.
General algorithm
- Propose:
- $θ^* \sim J_t(θ^* \mid θ^{(t-1)})$
- Compute the generalized acceptance ratio:
- $r = \frac{p(θ^* \mid y) / J_t(θ^{(t-1)} \mid θ^*)} {p(θ^{(t-1)} \mid y) / J_t(θ^* \mid θ^{(t-1)})}$
- Accept or reject:
- $θ^{(t)} = \begin{cases} θ^*, & \text{with probability } \min(r, 1) \\ θ^{(t-1)}, & \text{otherwise.} \end{cases}$
This correction term ensures that the target posterior $p(θ \mid y)$ remains the stationary distribution even when proposals are asymmetric.
5. Choosing a Good Proposal (Jumping) Distribution
The efficiency of the Metropolis–Hastings algorithm depends heavily on the choice of the proposal distribution $J(θ^* \mid θ)$.
A good proposal should:
- Be easy to sample from.
- Allow easy computation of the ratio $r$.
- Propose jumps that move a reasonable distance in parameter space (not too small, not too large).
- Too small → chain moves slowly.
- Too large → high rejection rate.
- Avoid too many rejections, ensuring effective exploration.
6. Ideal and Practical Cases
- Ideal case:
- If $J(θ^* \mid θ) = p(θ^* \mid y)$, then every proposed move is accepted ($r = 1$), giving independent samples from the posterior. (Of course, this is rarely feasible in real problems.)
- In practice:
- $J(θ^* \mid θ)$ serves as an approximation to $p(θ^* \mid y)$.
- The closer the proposal resembles the target, the more efficient the simulation.
Key Takeaways
| Concept | Explanation |
|---|---|
| Goal | Generate samples from a posterior distribution $p(θ \mid y)$ using an iterative accept/reject process. |
| Metropolis algorithm | Uses a symmetric proposal; accepts based on posterior density ratio rrr. |
| Metropolis–Hastings algorithm | Generalizes to asymmetric proposals with an adjusted ratio. |
| Acceptance rule | Always accept higher-density moves; sometimes accept lower-density ones. |
| Efficiency | Determined by the choice of proposal distribution $J(θ^* \mid θ)$. |
| Relation to Gibbs sampler | Gibbs is a special case where every proposed move is accepted because the proposal equals the conditional posterior. |
Summary:
The Metropolis and Metropolis–Hastings algorithms generate samples from complex posteriors by proposing candidate points from a chosen distribution and accepting or rejecting them based on a probability that ensures the chain converges to the target distribution $p(θ \mid y)$; efficiency depends on how well the proposal distribution matches the target.