Metropolis-Hastings MCMC theory

Prior to MCMC, Bayesian statistics was largely restricted to simple models with analytical conjugate priors. In realistic multi-parameter models, computing posterior expectations E[g(θ) | y] = ∫ g(θ) p(θ | y) dθ requires integrating over high-dimensional spaces where the normalizing constant p(y) = ∫ L(θ) p(θ) dθ is intractable. MCMC constructs an ergodic Markov chain whose unique stationary distribution is exactly the target posterior distribution p(θ | y). By simulating the chain forward in time, sample states asymptotically represent draws from the posterior, bypassing the need to compute normalizing constants.

Introduced by Nicholas Metropolis et al. in 1953 and generalized by W. K. Hastings in 1970, the algorithm generates states as follows: at current state x, a candidate y is proposed from density q(y | x). The candidate is accepted with probability: α(x, y) = min(1, [p(y) q(x | y)] / [p(x) q(y | x)]). If accepted, X_{t+1} = y; if rejected, the chain remains at its current state X_{t+1} = x. Crucially, the target density p(x) appears only as a ratio p(y)/p(x), meaning any unknown normalizing constant cancels out completely.

Detailed balance requires p(x) P(x, y) = p(y) P(y, x) for all x ≠ y. The transition probability for moving from x to y is P(x, y) = q(y | x) α(x, y). Without loss of generality, assume p(y) q(x | y) ≤ p(x) q(y | x). Then α(x, y) = [p(y) q(x | y)] / [p(x) q(y | x)] and α(y, x) = 1. Substituting into the flux equations: p(x) P(x, y) = p(x) q(y | x) [p(y) q(x | y)] / [p(x) q(y | x)] = p(y) q(x | y) = p(y) q(x | y) · 1 = p(y) P(y, x). Because detailed balance holds, p(x) is guaranteed to be a stationary distribution of the chain.

Gelman, Roberts, and Gilks (1997) proved celebrated asymptotic optimality results for random walk Metropolis on target densities in d dimensions: (1) In 1 dimension (d = 1), the optimal acceptance rate that minimizes autocorrelation is approximately 44% (0.44); (2) As dimension d → ∞, the optimal acceptance rate asymptotically converges to 23.8% (0.234). If acceptance is too high (>70%), the proposal step size is too small, resulting in slow diffusive exploration; if acceptance is too low (<10%), proposals are constantly rejected, causing the chain to freeze.

Because MCMC states are correlated across successive iterations, N dependent MCMC samples contain less statistical information than N independent draws. The variance of the sample mean is Var(θ̄) = (σ^2 / N) · [1 + 2 ∑_{k=1}^∞ ρ_k] = (σ^2 / N) · τ_int, where ρ_k is the lag-k autocorrelation and τ_int = 1 + 2 ∑ ρ_k is the integrated autocorrelation time. The Effective Sample Size is defined as ESS = N / τ_int. An MCMC chain of 10,000 steps with τ_int = 10 provides only ESS = 1,000 independent-equivalent draws.

The initial trajectory of an MCMC chain depends heavily on the starting state X_0. The burn-in period is the initial sequence of iterations discarded to allow the chain to reach its stationary distribution. Andrew Gelman and Donald Rubin (1992) introduced the potential scale reduction factor R̂ (Gelman-Rubin diagnostic) using multiple chains initialized from dispersed starting values. R̂ compares the between-chain variance B to the within-chain variance W: R̂ = √[(W (n - 1)/n + B/n) / W]. An R̂ < 1.05 across all parameters indicates that chains have mixed and converged to stationarity.

Introduced by Stuart and Donald Geman in 1984, Gibbs Sampling is a special case of Metropolis-Hastings where parameters are updated one at a time by sampling directly from full conditional posterior distributions: θ_j^(t+1) ~ p(θ_j | θ_{-j}^(t), y). Because proposing from the exact full conditional yields an acceptance ratio α = min(1, 1) = 1, Gibbs sampling has an acceptance probability of identically 100%, avoiding tuning proposal step sizes.