Markov Chain Monte Carlo

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. The Sampling Problem
5. Markov Chains: Foundations
6. The Metropolis-Hastings Algorithm
7. Detailed Balance and Correctness
8. Gibbs Sampling
9. Hamiltonian Monte Carlo
10. Convergence Diagnostics
11. Common Pitfalls
12. Research Perspective
13. Summary
14. Exercises

Learning Objectives

1. Explain why direct sampling from posterior distributions is generally intractable.
2. Define Markov chains and state the conditions for ergodicity.
3. Derive the Metropolis-Hastings acceptance probability from detailed balance.
4. Show that Gibbs sampling is a special case of Metropolis-Hastings.
5. Derive the Hamiltonian dynamics underlying HMC and explain its advantages.
6. Apply convergence diagnostics (R-hat, effective sample size, trace plots).

Notation

• $\pi(\boldsymbol\theta)$ — target distribution (posterior), known up to normalizing constant
• $q(\boldsymbol\theta' \mid \boldsymbol\theta)$ — proposal distribution
• $\alpha(\boldsymbol\theta' \mid \boldsymbol\theta)$ — acceptance probability
• $T(\boldsymbol\theta' \mid \boldsymbol\theta)$ — transition kernel of the chain
• $\boldsymbol\theta^{(t)}$ — state of chain at iteration $t$

Core Intuition

Bayesian inference requires computing expectations under the posterior $p(\boldsymbol\theta \mid \mathcal{D})$, which involves intractable integrals. MCMC constructs a Markov chain whose stationary distribution is the posterior. Running the chain generates correlated samples; the empirical average of these samples converges to the posterior expectation by the ergodic theorem.

The Sampling Problem

We want to compute:

where $\pi(\boldsymbol\theta) = p(\boldsymbol\theta \mid \mathcal{D}) = \frac{p(\mathcal{D} \mid \boldsymbol\theta)p(\boldsymbol\theta)}{p(\mathcal{D})}$.

The normalizing constant $p(\mathcal{D}) = \int p(\mathcal{D} \mid \boldsymbol\theta)p(\boldsymbol\theta)\,d\boldsymbol\theta$ is typically intractable. We can evaluate $\tilde{\pi}(\boldsymbol\theta) = p(\mathcal{D} \mid \boldsymbol\theta)p(\boldsymbol\theta)$ pointwise, but cannot normalize it.

MCMC solves this: it only requires $\tilde{\pi}$ up to a constant.

Markov Chains: Foundations

Definition. A sequence $\{\boldsymbol\theta^{(t)}\}$ is a Markov chain if $p(\boldsymbol\theta^{(t+1)} \mid \boldsymbol\theta^{(t)}, \ldots, \boldsymbol\theta^{(0)}) = T(\boldsymbol\theta^{(t+1)} \mid \boldsymbol\theta^{(t)})$.

Stationary distribution. $\pi$ is stationary for $T$ if:

Ergodic Theorem. If the chain is irreducible and aperiodic with stationary distribution $\pi$, then:

The Metropolis-Hastings Algorithm

Algorithm:

1. Initialize $\boldsymbol\theta^{(0)}$.
2. For $t = 0, 1, 2, \ldots$:
   • Propose $\boldsymbol\theta' \sim q(\cdot \mid \boldsymbol\theta^{(t)})$.
   • Compute acceptance probability:

• With probability $\alpha$: set $\boldsymbol\theta^{(t+1)} = \boldsymbol\theta'$. Otherwise: $\boldsymbol\theta^{(t+1)} = \boldsymbol\theta^{(t)}$.

The normalizing constants cancel in the ratio $\tilde{\pi}(\boldsymbol\theta')/\tilde{\pi}(\boldsymbol\theta^{(t)})$.

Detailed Balance and Correctness

Detailed balance (sufficient condition for $\pi$ to be stationary):

Theorem. The MH transition kernel satisfies detailed balance with respect to $\pi$.

Proof. The transition kernel is $T(\boldsymbol\theta' \mid \boldsymbol\theta) = q(\boldsymbol\theta' \mid \boldsymbol\theta)\alpha(\boldsymbol\theta' \mid \boldsymbol\theta)$ for $\boldsymbol\theta' \neq \boldsymbol\theta$. Then:

which is symmetric in $(\boldsymbol\theta, \boldsymbol\theta')$, establishing detailed balance. $\blacksquare$

Gibbs Sampling

For $\boldsymbol\theta = (\theta_1, \ldots, \theta_d)$, Gibbs sampling updates one coordinate at a time from its full conditional:

Proposition. Gibbs sampling is a special case of Metropolis-Hastings where the proposal $q(\boldsymbol\theta' \mid \boldsymbol\theta)$ proposes from the full conditional distribution, and the acceptance probability is always 1.

Proof. Let $q(\boldsymbol\theta' \mid \boldsymbol\theta) = p(\theta_j' \mid \boldsymbol\theta_{-j})$. Then:

So $\alpha = \min(1, 1) = 1$. $\blacksquare$

Hamiltonian Monte Carlo

HMC augments the parameter space with "momentum" variables $\mathbf{p}$ and simulates Hamiltonian dynamics to propose distant states with high acceptance probability.

Joint distribution: $p(\boldsymbol\theta, \mathbf{p}) \propto \exp(-H(\boldsymbol\theta, \mathbf{p}))$ where:

Leapfrog integrator (discrete approximation to Hamilton's equations):

After $L$ leapfrog steps, accept/reject with MH correction (accounts for discretization error).

Advantage: HMC proposes states far from the current position while maintaining high acceptance rates, greatly reducing autocorrelation compared to random-walk MH.

Convergence Diagnostics

• Trace plots: Visual inspection for stationarity (chain should look like white noise after burn-in).
• $\hat{R}$ (Gelman-Rubin): Run multiple chains; $\hat{R} \approx 1$ indicates convergence. $\hat{R} > 1.01$ suggests non-convergence.
• Effective Sample Size (ESS): $\text{ESS} = N / (1 + 2\sum_k \rho_k)$ where $\rho_k$ is autocorrelation at lag $k$. Low ESS means high autocorrelation.
• Burn-in: Discard initial samples before the chain reaches stationarity.

Common Pitfalls

Pitfall 1. Using too narrow a proposal in MH: high acceptance rate but slow exploration (random walk behavior). Optimal acceptance rate ≈ 23% for high-dimensional targets.

Pitfall 2. Not accounting for multimodality. Standard MCMC can get trapped in a single mode. Use tempering or multiple initialization strategies.

Pitfall 3. Declaring convergence too early. Short chains may appear stationary but haven't explored the full posterior. Always run multiple chains with dispersed initializations.

Research Perspective

MCMC was introduced by Metropolis et al. (1953) and generalized by Hastings (1970). Modern advances include the No-U-Turn Sampler (NUTS, Hoffman & Gelman, 2014) which automatically tunes HMC trajectory length, stochastic gradient MCMC for large datasets, and transport-based methods that combine variational inference with MCMC.

Summary

• MCMC generates samples from distributions known only up to a constant.
• Metropolis-Hastings uses propose-accept/reject; correctness follows from detailed balance.
• Gibbs sampling cycles through full conditionals; always accepts.
• HMC uses gradient information for efficient exploration of high-dimensional posteriors.
• Convergence is assessed via $\hat{R}$, ESS, and trace plots.

Exercises

Exercise 1. Prove that detailed balance implies stationarity: if $\pi T = \pi$ follows from equation (5).

Exercise 2. For a 1D Gaussian target $\pi(\theta) = \mathcal{N}(0, 1)$ with Gaussian proposal $q(\theta' \mid \theta) = \mathcal{N}(\theta, \sigma^2)$, compute the acceptance probability and discuss the effect of $\sigma$.

Exercise 3. Show that the leapfrog integrator is time-reversible and volume-preserving (symplectic).

Exercise 4. Derive the Gibbs sampler for the bivariate Gaussian $(\theta_1, \theta_2)$ with correlation $\rho$, and compute the autocorrelation of the chain.

Exercise 5. Show that ideal HMC (exact Hamiltonian dynamics, no discretization error) has acceptance probability 1.