Chib-Greenberg (1995) Understanding the Metropolis-Hastings Algorithm

Summary

Chib and Greenberg (1995) provide a tutorial derivation of the Metropolis-Hastings (MH) algorithm from the reversibility condition (detailed balance), unifying five families of candidate-generating kernels under a single framework. The paper proves the Product of Kernels principle — that a composition $P_1\cdot P_2$ whose factors respectively preserve the conditional distributions of $\pi$ inherits $\pi$ as joint invariant — from which the Gibbs sampler emerges as the $\alpha = 1$ special case. Section 6.1 introduces the M-H A-R algorithm, which embeds acceptance-rejection sampling inside MH using a pseudodominating envelope.

Key Claims

• Reversibility derivation: $\alpha(x,y) = \min[\pi(y)q(y,x) / \pi(x)q(x,y),\, 1]$ follows from requiring $\pi(x)p(x,y) = \pi(y)p(y,x)$ (detailed balance); any symmetric form of this acceptance function that satisfies detailed balance and minimizes rejection probability gives the Hastings form
• Five candidate-generating families:
  1. Random walk — $q(x,y)$ symmetric ($y = x + \varepsilon$) $\to \alpha = \min\{\pi(y)/\pi(x),\, 1\}$
  2. Independence chain — $q(y)$ independent of current state $x$
  3. Rejection-sampling — $\pi \propto \psi h \to$ accept with $\alpha = \min\{\psi(y)/\psi(x),\, 1\}$; Gibbs is the limit
  4. Autoregressive/reflection — $y = a + B(x-a) + z$; $B = -I$ reflects about point $a$, inducing negative serial correlation
  5. Block-at-a-time — partition $\theta$ into blocks; update each block conditioning on the rest
• Product of Kernels principle: if $P_1$ has $\pi^*_{1|2}$ as invariant and $P_2$ has $\pi^*_{2|1}$ as invariant, then $P_1\cdot P_2$ has joint $\pi^*$ as invariant; Gibbs sampler is the special case where each block kernel samples exactly from the full conditional ($\alpha = 1$ everywhere); MH within Gibbs uses this for blocks where full conditionals are intractable
• M-H A-R algorithm (§6.1): pseudodominating density $q(y) = f(y)/(cd)$ for $y \in C = \{x: f(x) < ch(x)\}$, $= h(y)/d$ for $y \notin C$; acceptance probabilities for four cases depending on whether $(x, y) \in$ or $\notin C$; equivalent to performing rejection sampling on the candidate and then applying an MH correction
• Optimal acceptance rates: ~0.45 ($d = 1$), ~0.23 ($d \to \infty$), ~0.25 for $d \geq 6$ (Roberts-Gelman-Gilks 1994 technical report); these apply to the random-walk Gaussian kernel
• AR(2) (second-order autoregressive) block example: $\phi$ proposed via MH with normal proposal truncated to stationarity region; $\sigma^2$ drawn from inverted gamma; $N = 5000$ draws after $n_0 = 500$ burn-in; posterior means $\hat\phi_1 = 1.044$ (standard error, SE, 0.002), $\hat\phi_2 = -0.608$ (SE 0.001), $\hat\sigma^2 = 1.160$ (SE 0.003)

Concepts Introduced or Extended

• Metropolis-Hastings Algorithm
• Gibbs Sampler

Entities Mentioned

• Siddhartha Chib
• Edward Greenberg
• Luke Tierney

Quotes

"The MH algorithm generates a Markov chain whose stationary distribution is π." "The Gibbs sampling algorithm is a special case of the Metropolis-Hastings algorithm."

My Take

The clearest pedagogical derivation of MH from first principles in the literature. The Product of Kernels theorem is the key insight unifying MH and Gibbs and justifying hybrid samplers; it is the theoretical backbone for all Metropolis-within-Gibbs algorithms used in time-varying-parameter VAR (TVP-VAR), stochastic volatility (SV), and cointegrated vector-autoregression (VAR) models. The M-H A-R algorithm (§6.1) is less widely cited but useful when a partial rejection-sampling envelope is available. Acceptance rate calibration from Roberts-Gelman-Gilks (1994) has become standard tuning folklore for random-walk MH.