The Metropolis–Hastings algorithm is a method for constructing a Markov chain whose long-run distribution is a specified probability distribution. It is one of the principal algorithms in Markov chain Monte Carlo (MCMC), used when direct independent sampling is difficult. Starting from a current state, the algorithm proposes a candidate state and then accepts or rejects it according to a probability that corrects for both the target distribution and the proposal mechanism. Rejection leaves the chain at its current state.
Its central advantage is that the target need only be evaluated up to a multiplicative constant. This makes it useful in Bayesian inference, where a posterior distribution may have an intractable normalizing constant, and in statistical physics, where equilibrium distributions involve partition functions that are difficult to calculate. The method originated in a 1953 paper on molecular simulation and was generalized by W. Keith Hastings in 1970. Its mathematical validity rests on invariant distributions and appropriate convergence conditions; its practical usefulness depends heavily on how proposals explore the target.
Historical development and computational purpose
The original Metropolis method appeared in the 1953 paper “Equation of State Calculations by Fast Computing Machines,” authored by Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. The paper described simulations of interacting particles using the MANIAC computer at Los Alamos. Rather than sampling configurations uniformly and assigning them unequal statistical weights, the method generated a sequence of configurations whose frequency of occurrence reflected their equilibrium probabilities.
For a physical system with configuration , potential energy , and absolute temperature , the canonical equilibrium distribution has the form
where is Boltzmann’s constant and is the partition function. With symmetric proposals, a move that lowers the energy is accepted, while a move that raises the energy by is accepted with probability . The partition function cancels from the acceptance ratio. This cancellation made equilibrium calculations possible without first enumerating all configurations.
In 1970, Hastings published “Monte Carlo Sampling Methods Using Markov Chains and Their Applications.” His formulation allowed asymmetric proposal mechanisms and placed the construction in a general statistical framework. The additional proposal-density ratio is what distinguishes the general Metropolis–Hastings rule from the original symmetric-proposal Metropolis rule. Peter H. Peskun’s 1973 work subsequently established important comparisons between reversible transition rules, helping explain the efficiency advantages of the standard acceptance function.
The algorithm addresses a sampling problem rather than a direct optimization problem. Its objective is not merely to find a high-density point, but to reproduce the relative probability of entire regions. A narrow peak can have a greater density than a broad region while containing less total probability. Correct sampling must reflect that distinction. Once a suitable chain has been generated, Monte Carlo averages can approximate expectations, event probabilities, and other distributional quantities.
This computational viewpoint also explains the algorithm’s limitations. Avoiding a normalizing constant does not eliminate the difficulty of exploring a complicated state space. A formally correct sampler can spend an extremely long time in one region, especially when the target has separated modes or strong dependence between coordinates. Much of the subsequent development of MCMC has therefore concerned the design of proposals, rather than changes to the basic accept–reject principle.
Target distributions and the acceptance rule
Let the target have density or mass function , written as
For discrete states, the integral is replaced by a sum. The unnormalized target must be nonnegative, and a probability target requires . In continuous spaces, densities are understood relative to a specified reference measure, commonly Lebesgue measure. The proposal density specifies how a candidate is generated from the current state .
For a current state with positive target density, the Metropolis–Hastings acceptance probability is
The ratio contains the probability of proposing the reverse move, , divided by that of proposing the forward move, . The constant cancels. A proposal into a zero-density region is rejected. If the reverse proposal has zero density while the forward proposal and target densities are positive, the candidate is also rejected.
A single iteration consists of three random operations and decisions:
- Generate from .
- Generate independently from the uniform distribution on .
- Set if ; otherwise set .
Rejected iterations are part of the sample path. They record the time the chain spends at a state, rather than unsuccessful attempts that may simply be deleted.
When proposals are symmetric, , the acceptance probability simplifies to
For example, consider an unnormalized standard normal density, , and a Gaussian proposal centered at the current state. A proposal from to is accepted with probability , approximately . The reverse move is accepted with probability one.
The general rule matters even when asymmetry seems incidental. A proposal whose scale depends on the current position, a truncated proposal near a boundary, or a proposal guided by local derivatives will ordinarily be asymmetric. Using only the target-density ratio in such cases generally produces the wrong stationary distribution. Validity depends on the actual probability law used to generate candidates, not merely on whether the proposed displacement appears locally balanced.
Detailed balance and invariance
The standard correctness argument uses detailed balance. A transition kernel satisfies detailed balance with respect to when the probability flow from one region to another equals the reverse flow under the target distribution. For distinct states with densities, the Metropolis–Hastings construction gives
The expression is unchanged when and are exchanged, so
The full transition kernel also includes the probability of remaining at the current state:
where
and is unit point mass at . In a continuous state space, this point mass explains why consecutive states can be exactly equal even though the proposal distribution itself is continuous. In a discrete space, the corresponding construction uses sums and includes any direct proposal of the current state.
Integrating the detailed-balance identity establishes invariance:
for every measurable set . Thus, if has distribution , then also has distribution . The target is therefore a stationary distribution of the chain. Detailed balance is a sufficient condition for invariance, not a necessary condition: nonreversible Markov chains can also preserve a target distribution.
Rejection is essential to this construction. If only accepted states are retained, the resulting sequence is the jump chain, whose stationary distribution is generally different. When a stationary jump-chain distribution exists and the probability of leaving state is positive, it is proportional to . States from which departures are easy become overrepresented relative to the intended target. Appropriate holding-time weights can correct this, but simply discarding repeats cannot.
Among acceptance rules for a fixed proposal, the Metropolis choice has a particular efficiency property. Detailed balance requires the acceptance probabilities in opposite directions to have a specified ratio; choosing the minimum of one and the Hastings ratio makes accepted off-diagonal transitions as large as possible. Under the conditions of Peskun-type comparisons, increasing these transition probabilities reduces asymptotic variance for stationary averages. This does not imply that any Metropolis–Hastings proposal is efficient, because a poor proposal can still make almost no useful movement.
Convergence and Monte Carlo error
Invariance alone does not ensure convergence from an arbitrary starting point. A chain may preserve the desired target while remaining permanently inside a subset of its support. Irreducibility requires that every target-relevant region be reachable with positive probability in some number of steps. Aperiodicity excludes a rigid cyclic schedule. On general state spaces, Harris recurrence and related regularity conditions provide the framework for convergence of distributions and sample averages.
A simple failure occurs when a discrete proposal always changes an integer by two. Even and odd states then form separate communicating classes. If the target gives positive probability to both, a chain initialized at an even state cannot sample the full target. Another failure arises when a proposal cannot cross a zero-density barrier: local moves confined to one connected component leave other components unexplored. Rejection often helps establish aperiodicity by introducing self-transitions, but does not by itself guarantee irreducibility or convergence.
Under suitable ergodic conditions, a law of large numbers yields
with probability one for integrable . This permits approximation of an expectation without independent samples. An initial period is often discarded as warm-up or burn-in to reduce sensitivity to initialization, but no universal number of discarded iterations ensures stationarity.
A central limit theorem requires stronger conditions than a law of large numbers. When applicable,
where, for a stationary chain with suitably summable covariances,
The variance of the Monte Carlo average therefore depends on serial dependence, not just on the marginal spread of the target.
Writing for the lag- autocorrelation gives the integrated autocorrelation time
and the approximate effective sample size
These quantities are specific to the function . A chain may estimate a posterior mean accurately while giving a poor estimate of a rare-event probability. Some targets or proposal combinations yield very slow convergence, and a finite second moment of the target alone does not guarantee a Markov-chain central limit theorem. Monte Carlo uncertainty must consequently be assessed from the dependence structure of the generated sequence.
Proposal families and geometric design
A common proposal is a random walk:
where the increment distribution is symmetric about zero. A Gaussian increment with covariance matrix produces a simple symmetric proposal. The matrix determines both scale and direction: larger eigenvalues allow wider moves along the corresponding directions. If the target is elongated or strongly correlated, an isotropic proposal may move adequately in narrow directions only by making unnecessarily small steps in broad ones.
An independence proposal instead has , so candidates do not depend on the current state. Its acceptance rule is
This can mix rapidly when closely approximates the target. Conversely, a proposal that rarely generates an important target region can produce long periods of immobility after the chain reaches that region. A strong sufficient condition for uniform ergodicity is a global bound for a finite constant ; this illustrates the importance of adequate proposal tail mass.
In multivariate problems, proposals can update all coordinates jointly, a block of coordinates, or one coordinate at a time. Each component update can be constructed to preserve the same joint target. Their composition therefore preserves that target, although a deterministic sequence of individually reversible updates need not itself be reversible. Blocking strongly dependent coordinates can improve movement, while small blocks may reduce the computational cost of each proposal. The best comparison concerns estimation accuracy per unit of computation, not simply iterations per second.
Gibbs sampling is closely related. Updating a coordinate from its exact full conditional distribution can be expressed as a Metropolis–Hastings step with acceptance probability one. If that conditional is difficult to sample, a Metropolis update can replace the exact draw, yielding Metropolis-within-Gibbs sampling. This construction is widely useful in hierarchical statistical models, where different parameter groups have different conditional structures.
Geometry can also be improved by reparameterization. For a positive parameter, sampling its logarithm removes the boundary at zero. Such a transformation changes the target density: if , then
The determinant of the Jacobian matrix accounts for the change in volume. Omitting it generally changes the distribution being sampled. Reparameterization and proposal design are therefore closely connected, but neither permits ignoring the underlying reference measure.
Scaling, dimension, and gradient-based methods
Proposal scale creates a basic trade-off. Very small random-walk increments are often accepted but explore the target slowly. Very large increments may traverse substantial distances when accepted, but most proposals can fall in low-probability regions and be rejected. Acceptance rate alone is therefore not a measure of efficiency. The relevant objective is effective exploration of quantities of interest relative to the cost of evaluating proposals.
A major theoretical result for random-walk Metropolis was established by Gareth Roberts, Andrew Gelman, and Walter Gilks in 1997. For certain smooth product targets in dimension , with Gaussian random-walk proposals under a high-dimensional diffusion limit, the efficient proposal standard deviation scales as . Optimizing the limiting diffusion speed yields an asymptotic acceptance probability of approximately . This result explains a widely used tuning benchmark, but its assumptions concern a specific class of targets and proposal scalings.
The value is not a universal optimum. In one-dimensional Gaussian random-walk settings, optimal acceptance rates are often near . Strong dependence, heavy tails, constraints, multimodality, and unequal coordinate scales can change the appropriate behavior. Even an apparently suitable acceptance rate cannot reveal whether a chain is trapped in one mode. Two samplers with the same acceptance fraction can have very different effective sample sizes.
When derivatives are available, proposals can use the gradient of the log target. The Metropolis-adjusted Langevin algorithm uses a proposal of the form
The drift points toward increasing log density, while the noise maintains exploration. Since the proposal depends on the current gradient, it is generally asymmetric and requires the full Hastings correction. Under particular high-dimensional product-target assumptions, its theoretically optimal acceptance probability is approximately .
Hamiltonian Monte Carlo follows another route. It augments the position with momentum and uses numerical trajectories derived from Hamiltonian dynamics to propose distant states. With a reversible, volume-preserving integrator and the appropriate momentum reversal convention, a Metropolis correction compensates for numerical energy error. Unlike a random walk, the trajectory can maintain directed movement over many small integration steps.
Both gradient-based methods demonstrate that the acceptance rule is only one part of a sampler. Improved movement may require additional derivative evaluations or numerical integration, and those costs must be compared with the gain in statistical efficiency. They also require suitable differentiability and do not directly replace discrete-state proposals.
Implementation and empirical diagnostics
Implementations usually work with log densities to improve numerical stability. Instead of multiplying small probabilities, they calculate
and accept when
This avoids many underflow problems associated with products of likelihood contributions. Zero target density can be represented by negative infinity in log space, but undefined expressions still require explicit handling. Initialization at a point with finite positive target density simplifies these issues.
The current log target can be cached and updated only after acceptance. In a Bayesian model,
where the first term is the log likelihood and the second is the log prior density. Terms constant in may be omitted. Terms that depend on the state cannot be dropped merely because they resemble normalizing constants: a distribution’s normalization may itself depend on an unknown parameter.
Proposal correctness must be checked separately from target evaluation. A Gaussian increment followed by rejection outside the allowed domain is not the same proposal as repeatedly drawing until an allowed candidate appears. The latter is a truncated distribution with a state-dependent normalizing factor. Similarly, clipping a candidate to a boundary creates point masses that are absent from the original continuous proposal density. These distinctions can produce incorrect acceptance ratios even when the target code is accurate.
Empirical assessment commonly uses multiple chains initialized at dispersed points, trace plots, acceptance statistics, effective sample sizes, and between-chain comparisons. The potential scale reduction statistic, usually denoted , compares within-chain and between-chain variation; modern versions use splitting and rank normalization. Values near one support agreement among the chains, but cannot prove that every relevant region has been explored. Chains initialized in the same undiscovered mode can agree while all missing other modes.
Monte Carlo standard errors quantify uncertainty caused by finite simulation and are distinct from the uncertainty represented by the target distribution. Batch-means and spectral-variance methods estimate this computational error while accounting for serial dependence. Routine thinning—retaining every -th iteration—usually discards useful information when storage is not limiting. Adaptive tuning can improve performance during warm-up, but unrestricted adaptation changes the stochastic process. Retaining samples after adaptation has stopped is a common way to separate tuning from a fixed-kernel sampling phase; continuously adaptive methods require their own convergence conditions.
Extensions and applications
In Bayesian computation, the target is often the posterior distribution
Metropolis–Hastings samples support estimates of posterior means, credible intervals, tail probabilities, and posterior predictive distributions. Applications include hierarchical models, latent-variable models, spatial models, and nonlinear inverse problems. The method does not automatically calculate the marginal likelihood, because ordinary sampling requires only an unnormalized target and does not directly recover its normalizing constant.
In physical simulation, proposals may displace particles, rotate molecules, change lattice states, or alter particle numbers. The target and proposal ratio must match the chosen ensemble. For a fixed-temperature canonical target with symmetric moves, the acceptance rule reduces to the familiar energy-difference expression. More complicated insertion, deletion, or volume-changing moves introduce proposal probabilities and volume factors that cannot be omitted. The same mathematical rule accommodates these differences without requiring the partition function explicitly.
Reversible-jump MCMC, introduced by Peter Green in 1995, extends the construction to state spaces containing models of different dimensions. A move between models introduces auxiliary random variables and a dimension-matching transformation. Its acceptance ratio includes model probabilities, forward and reverse proposal probabilities, and the transformation’s Jacobian determinant. This allows sampling over both model identity and model-specific parameters, rather than fitting each dimension separately.
Pseudo-marginal MCMC addresses targets that cannot be evaluated exactly but admit a nonnegative unbiased estimator of the unnormalized density. An auxiliary-variable construction can produce an exact marginal target despite using noisy estimates. The estimate associated with the current state is retained when a proposal is rejected; it is part of the augmented state. Independently replacing both current and proposed estimates at every iteration generally defines a different algorithm and need not preserve the intended target. Although unbiasedness supports correctness, estimator variability can greatly affect mixing.
Other extensions address multimodality or changing targets. Parallel tempering runs chains at different temperatures and uses carefully balanced swap moves to help transfer configurations between them. Simulated annealing instead changes temperature over time to concentrate probability near optima, so its purpose and convergence theory differ from fixed-target sampling. Delayed-acceptance methods screen candidates with a cheaper approximation before evaluating an expensive target, with corrections designed to preserve the exact distribution. In all these cases, the central design problem is to specify the full transition mechanism and verify that its accepted probability flows correspond to the intended target.