Module 6: Metropolis–Hastings Algorithm

This module derives the Metropolis–Hastings (MH) algorithm from detailed balance and analyzes its stationarity, irreducibility, convergence properties, optimal scaling in high dimensions, and common pathologies.

1. Construction of the Metropolis–Hastings Kernel

1.1 Target and Proposal

State space: ((, )).
Target distribution: probability measure () on ((, )), with density (possibly unnormalized) ((x)) w.r.t. a reference measure ().
Proposal kernel: (q(x, dy)), with density (q(x,y)) w.r.t. ().

1.2 Acceptance Probability

Define the acceptance probability \[ \alpha(x,y) = \min\left\{ 1, \frac{\pi(y) q(y,x)}{\pi(x) q(x,y)} \right\} \] when the ratio is well-defined and positive. On sets where ((x) q(x,y) = 0), define ((x,y)) appropriately (e.g., 0) to obtain a measurable function.

1.3 MH Transition Kernel

The Metropolis–Hastings transition kernel is \[ K(x, dy) = q(x, dy) \alpha(x,y) + r(x) \, \delta_x(dy), \] where \[ r(x) = 1 - \int_\mathsf{X} q(x, dy) \alpha(x,y) \] ensures that (K(x, )) is a probability measure. Here, (_x) denotes the Dirac measure at (x).

2. Detailed Balance and Stationarity

Theorem 6.1 (Detailed Balance for MH)

Assume that (q(x,y) > 0) whenever ((x) (y) > 0). Then the MH kernel (K) satisfies detailed balance with respect to (): \[ \pi(dx) K(x, dy) = \pi(dy) K(y, dx). \] In particular, () is invariant for (K).

Proof: We verify the kernel form of detailed balance, \[ \pi(dx) K(x, dy) = \pi(dy) K(y, dx), \] as equality of measures on (( , )). By definition, \[ K(x, dy) = q(x, dy) \alpha(x,y) + r(x) \, \delta_x(dy), \] so \[ \pi(dx) K(x, dy) = \pi(dx) q(x, dy) \alpha(x,y) + \pi(dx) r(x) \, \delta_x(dy). \] The second term satisfies \[ \pi(dx) r(x) \, \delta_x(dy) = \pi(dy) r(y) \, \delta_y(dx), \] which is symmetric in ((x,y)) by construction. Thus it remains to check symmetry of the off-diagonal part \[ \pi(dx) q(x, dy) \alpha(x,y). \] On the product set where ((x) q(x,y) > 0) and ((y) q(y,x) > 0), the Metropolis–Hastings acceptance probabilities satisfy \[ \alpha(x,y) = \min\left\{1, \frac{\pi(y) q(y,x)}{\pi(x) q(x,y)} \right\}, \qquad \alpha(y,x) = \min\left\{1, \frac{\pi(x) q(x,y)}{\pi(y) q(y,x)} \right\}. \] Therefore, \[ \pi(x) q(x,y) \alpha(x,y) = \min\{ \pi(x) q(x,y), \pi(y) q(y,x) \} = \pi(y) q(y,x) \alpha(y,x). \] Since both sides are densities of the corresponding measures with respect to the product reference measure ((dx) , (dy)), we have \[ \pi(dx) q(x, dy) \alpha(x,y) = \pi(dy) q(y, dx) \alpha(y,x) \] on this set. On the complement where ((x) q(x,y) = 0) or ((y) q(y,x) = 0), the acceptance probabilities are defined so that each side is zero, so equality still holds. Combining off-diagonal and diagonal parts gives \[ \pi(dx) K(x, dy) = \pi(dy) K(y, dx) \] as measures, i.e., detailed balance. In particular, () is invariant for (K) by Lemma 5.3. ()

3. Irreducibility, Aperiodicity, and Convergence

3.1 Irreducibility

If the proposal kernel (q) is ()-irreducible on the support of () (for some nontrivial ()) and proposals are accepted with positive probability wherever (>0), then the MH chain is ()-irreducible.

3.2 Aperiodicity

MH chains are typically aperiodic provided there is a nonzero probability of remaining at the current state (e.g., via rejection). The self-transition probability (r(x)) ensures aperiodicity under mild conditions.

Theorem 6.2 (Convergence to Stationarity)

Under irreducibility, aperiodicity, and positive recurrence, the MH chain converges in distribution to (): for any initial distribution (_0), \[ \| \mu_0 K^n - \pi \|_{\text{TV}} \to 0 \quad \text{as } n \to \infty. \]

Moreover, if suitable drift and minorization conditions hold, the convergence is geometric, and ergodic theorems and CLTs apply.

4. Optimal Scaling in High Dimensions

Consider a sequence of target distributions (_d) on (^d), e.g., i.i.d. product measures, and random-walk MH with Gaussian proposals of the form \[ Y = X + \sqrt{\frac{\ell^2}{d}} Z, \quad Z \sim N_d(0, I_d). \]

Theorem 6.3 (Informal Optimal Scaling Result)

Under suitable regularity conditions (e.g., target is product of i.i.d. components with smooth log-density), the rescaled MH chain converges to a diffusion as (d ). The optimal acceptance rate maximizing the speed of this limiting diffusion is approximately \[ \alpha^* \approx 0.234. \]

Idea of proof: Consider the sequence of (d)-dimensional targets and proposal scales such that the MH chain, linearly interpolated in time and appropriately rescaled, converges in distribution to a limiting Langevin diffusion (diffusion limit). The speed of this limiting diffusion depends on the proposal scale (), and one shows that it is maximized when the asymptotic average acceptance probability is approximately 0.234. This involves computing the generator of the limiting diffusion and optimizing its efficiency with respect to ().

5. Pathologies and Failure Modes

5.1 Poorly Tuned Proposals

Step size too small: High acceptance rate but extremely slow exploration (high autocorrelation).
Step size too large: Very low acceptance rate, many rejections, and poor mixing.

5.2 Ill-Conditioned or Multimodal Targets

Targets with strong correlations or narrow ridges lead to slow mixing of isotropic random-walk proposals.
Multimodal targets may trap the chain in one mode for long periods.

5.3 Heavy-Tailed Targets

For targets with heavy tails, random-walk MH may fail to be geometrically ergodic, complicating convergence diagnostics and CLTs.

6. Problem Set 6 (Representative Problems)

Detailed Balance for MH. Prove Theorem ?@thm-mh-detailed-balance rigorously, including the treatment of sets where ((x) q(x,y) = 0) and verifying measurability.
Irreducibility for Random-Walk MH. For a random-walk MH algorithm on (^d) with Gaussian proposal and target density strictly positive and continuous on (^d), prove that the chain is ()-irreducible. Explain how this, together with drift and minorization conditions from Module 5 (see Theorem ?@thm-geom-ergodicity-drift-minorization), leads to convergence as in Theorem ?@thm-mh-convergence.
Geometric Ergodicity and Heavy Tails. Consider a target distribution with polynomially decaying tails and a random-walk MH with Gaussian proposals. Investigate whether the chain satisfies a drift condition that implies geometric ergodicity, and relate your findings to the assumptions of Theorem ?@thm-geom-ergodicity-drift-minorization.
Diffusion Limit Sketch. Outline the diffusion limit argument leading to the 0.234 optimal acceptance rate for high-dimensional random-walk MH, identifying the main probabilistic tools used, and connect your argument to Theorem ?@thm-mh-optimal-scaling.
Practical Tuning. Discuss heuristic rules for tuning proposal variances in MH in finite dimensions and relate them to the high-dimensional scaling theory and the qualitative conclusions of Theorem ?@thm-mh-optimal-scaling.