Source-linked AI summary
The Metropolis-Hastings algorithm
Christian P. Robert
TL;DR
Complex targets make direct integration and simulation difficult, motivating Metropolis–Hastings as a general MCMC tool. The paper introduces its construction, illustrates calibration effects with simple examples and R code, and reviews extensions. The examples show that proposal choice affects exploration and convergence, while later sections discuss pseudo-marginal methods and broader limitations.
Problem
Integrating or simulating from complex target distributions can be intractable or costly, especially when target densities or normalizing constants are unavailable.
Method
The paper presents Metropolis–Hastings, which constructs a Markov chain stationary with respect to a target known up to a constant, and describes examples, calibration, and extensions.
Results
Proposal choices materially affect exploration and convergence: α = 0.1 explores only one mode, while α = 0.2 fails to reproduce the target shape after T = 10^5 iterations.
Takeaways & Limitations
Metropolis–Hastings is a versatile default or baseline MCMC solution, but proposal calibration is important for practical efficiency and exploration.
Takeaways & Limitations
Metropolis–Hastings rarely achieves optimal convergence rates, can encounter convergence difficulties when improperly calibrated, and may be unavailable as a practical solution for some intractable targets.
Abstract
from arXiv · showhide
This short note is a self-contained and basic introduction to the Metropolis-Hastings algorithm, this ubiquitous tool used for producing dependent simulations from an arbitrary distribution. The document illustrates the principles of the methodology on simple examples with R codes and provides references to the recent extensions of the method.
1. INTRODUCTION
Computing integrals or extrema for complex probability distributions can be intractable, making Monte Carlo approximations attractive but difficult when direct simulation is costly. MCMC addresses this by using Markov chains associated with the target distribution.
- Integrals and extrema can become intractable because of the domain’s shape, dimensionality, or the complexity of h or π.
- Monte Carlo approximates target-related integrals and identifies heavily weighted regions by averaging many realizations from the target distribution.
- Direct simulation from a specific distribution may be nearly impossible or costly, limiting standard Monte Carlo methods.
- MCMC uses a Markov chain associated with the target distribution to address the curse of dimensionality affecting regular Monte Carlo methods.
- The paper introduces and justifies Metropolis–Hastings, covers implementation and calibration, demonstrates a mixture example, and reviews recent extensions.
2. THE ALGORITHM
Metropolis–Hastings constructs an ergodic Markov chain stationary with respect to a target density known up to a constant, using proposals and an accept-reject transition. Examples show that proposal calibration strongly affects exploration and convergence.
- 2. THE ALGORITHM: Metropolis–Hastings targets π known up to a multiplying constant and constructs an ergodic, stationary Markov chain converging in distribution to π.
- 2. THE ALGORITHM: The chain produces a dependent sample whose empirical average converges almost surely to the target integral when the chain is ergodic.
- 2. THE ALGORITHM: The algorithm chooses a proposal kernel q and transitions by proposing Y_t, then selecting it with probability ρ(x(t), Y_t) or retaining x(t).
- 2. THE ALGORITHM: Stationarity is preserved when the chain is irreducible; a sufficient condition is that q is positive everywhere.
- 2.3 An experiment with the algorithm: In the example, α = 0.1 explores only one mode, while α = 0.2 remains slow and fails to reproduce the target shape after T = 10^5 iterations.
- 2.3 An experiment with the algorithm: Some proposal kernels recover the target shape, whereas others are poorer or may fail altogether to converge.
- 2.4 Historical interlude: The algorithm’s development spans the Metropolis algorithm of 1953 and Hastings’s 1970 generalization toward statistical applications.
3. IMPLEMENTATION DETAILS
Metropolis–Hastings is broadly applicable, but proposal choice and calibration determine practical efficiency. The section presents random-walk proposals, effective sample size, acceptance-rate guidance, and calibration strategies for simple and multidimensional settings.
- Calibration: Proposal calibration is a central practical difficulty because nearly any proposal q is theoretically valid, while convergence performance depends strongly on its scale.The paper contrasts scales α = 0.3, 3, and 30 and notes that automated calibration remains difficult.
- Random-walk proposals: Random-walk Metropolis–Hastings explores locally using a proposal formed by adding a symmetric random perturbation to the current chain value.The perturbation may follow, for example, a uniform or normal distribution; symmetry simplifies the acceptance probability.
- Calibration: The ideal acceptance rate is close to 1/4 in the formal Gaussian setting, corresponding to proposal variance twice the target variance.The paper presents this as an indication and default calibration rule rather than a universal guarantee.
- Effective sample size: Effective sample size corrects the nominal iteration count for correlations among chain values when comparing and calibrating MCMC algorithms.It is defined through the factor τ_T relating the variance of the empirical average to the variance implied by T iterations, and can use autocorrelation estimates or subsampling.
- Effective sample size: For α = 3, autocorrelation-based comparisons show comparative improvement, although even this quasi-optimal chain remains far from an i.i.d. sample.Figure 4 compares the three chains at α = 0.3, 3, and 30 for T = 10^4 iterations from x(1) = 3.14.
- Calibration: Multidimensional calibration can use partial optimisations or embed proposal-parameter optimisation within Metropolis-within-Gibbs, while adaptive tuning should diminish over time.The paper warns that global grid optimisation faces the curse of dimensionality and that continuous tuning can otherwise destroy the Markov property.
4. ILLUSTRATION
The illustration applies Metropolis–Hastings to a Poisson–Geometric mixture posterior, comparing joint two-dimensional and Metropolis-within-Gibbs proposals. The two approaches produce mostly equivalent outcomes, while the Metropolis-within-Gibbs output is slightly more dispersed and remains easier to calibrate in higher dimensions.
- Metropolis-within-Gibbs successively updates λ and α using separate Metropolis–Hastings proposals for the conditional components.This contrasts with proposing a joint move on (α, λ).
- The joint proposal uses an exponential move for α and a log-normal random-walk move for λ, with tuning parameters ϵ and δ controlling proposal behavior.
- The implementation tunes ϵ and δ to obtain a sufficiently large average acceptance probability and evaluates λ's average acceptance through the fraction of unique sampled values.
- Both algorithms return mostly equivalent outcomes, with a slightly more dispersed output for Metropolis-within-Gibbs in Figure 7.
- Joint random-walk calibration may become unwieldy in large dimensions, whereas Metropolis-within-Gibbs remains manageable but can induce higher component correlations and slower convergence.
5. EXTENSIONS
The paper surveys extensions of Metropolis–Hastings for settings involving gradients, latent state-space variables, and intractable target densities. These methods preserve or recover target-distribution validity through tailored proposals or unbiased estimators, while introducing additional computational or calibration considerations.
- MALA discretizes a Langevin diffusion whose stationary and limiting distribution is π, then applies a standard Metropolis–Hastings correction.The method uses gradient information and a discretization step h.
- MALA requires twice computing the gradient of π at each iteration but provides noticeable convergence speed-ups for most problems.
- Particle MCMC proposes a parameter value, generates a latent series with a particle-filter approximation, and inserts the filter's unbiased marginal-posterior estimator into the Metropolis–Hastings ratio.
- Particle MCMC is particularly appealing for state-space models such as hidden Markov models, and SMC2 extends it to approximate sequential filtering distributions.
- For doubly intractable likelihoods, pseudo-marginal Metropolis–Hastings replaces the intractable target with an unbiased estimator while preserving stationarity for the target through an adjusted acceptance ratio.
- Pseudo-marginal performance depends on estimator quality and is poorer than with the exact target, although multiple samples can improve estimation.
6. CONCLUSION AND NEW DIRECTIONS
The conclusion presents Metropolis–Hastings as a flexible default component for complex simulation problems, while emphasizing that it is not universally practical or optimally convergent. It also points to HMC and Big Data methods as directions addressing local exploration and costly likelihood evaluation.
- Metropolis–Hastings is a default or off-the-shelf solution that rarely achieves optimal convergence rates and may have convergence difficulties when improperly calibrated.
- When reversibility is preserved, Metropolis–Hastings kernels can be mixed with other MCMC solutions as baseline, local, or occasional global exploration components.
- HMC augments the target with a momentum-like variable and Hamiltonian dynamics, using a leapfrog approximation and Metropolis–Hastings correction in practice.
- HMC can produce distant moves in the target variable while changing the Hamiltonian very little, helping avoid the local nature of regular MCMC algorithms.
- Big Data settings require methods that avoid evaluating the entire likelihood at once when full-dataset evaluation is not cheap.