Random-walk Metropolis algorithm

The algorithm constructs a Markov chain whose long-run distribution is a specified target distribution, usually known only up to a normalizing constant. From the current state x, it proposes y = x + ε, where the increment ε is drawn from a distribution centered at zero; a Gaussian increment is the standard choice. The proposal is accepted with probability α(x,y) = min[1, π(y)/π(x)] when the increment distribution is symmetric. If the proposal is rejected, the chain remains at x. This accept–reject correction compensates for the tendency of local proposals to move toward regions where the target density is lower.¹²

After an initial transient, averages of functions evaluated along the chain can estimate expectations under the target. The method therefore turns sampling into repeated evaluation of the target density, without requiring direct draws or an analytically tractable normalizing constant.

The algorithm is valid because its transition rule satisfies detailed balance with respect to the target distribution when ordinary regularity conditions hold. For a symmetric proposal density q(y|x) = q(x|y), the acceptance ratio reduces to the target-density ratio; with an asymmetric proposal, the corresponding Metropolis–Hastings ratio must include the proposal-density correction.¹³

In practice, the chain is initialized, a proposal scale is selected, and many iterations are generated. Early draws may be discarded as burn-in, although convergence cannot be established merely by deleting a fixed number of iterations. Dependence between successive states means that the nominal number of draws exceeds the effective sample size. Diagnostics commonly examine multiple chains, trace plots, autocorrelation, and estimates of Monte Carlo error. Irreducibility and aperiodicity are central theoretical conditions: without adequate access to the target’s support, the chain may converge only within a subset of it.

Proposal scale controls the central trade-off between movement size and acceptance rate. Very small steps are accepted frequently but produce highly autocorrelated samples; very large steps travel farther when accepted but are rejected more often. For independent, identically distributed Gaussian targets under a sequence of high-dimensional limits, theoretical analyses identify a proposal standard deviation proportional to d^−1/2 and an asymptotically efficient acceptance rate near 0.234.⁴⁵

The 0.234 figure is a benchmark, not a universal rule. Dimension, target geometry, parameterization, tail behavior, and the chosen efficiency criterion all matter. Anisotropic targets can make spherical random walks inefficient because one scale cannot simultaneously fit narrow and broad directions. Reparameterization, componentwise updates, or a covariance-aware proposal can substantially improve performance while retaining the Metropolis correction.

Random-walk Metropolis can be correct yet computationally impractical when the target has separated modes, strong correlations, sharp constraints, or a very large dimension. Local proposals may cross low-density barriers only rarely, causing apparently stable but poorly representative chains; multimodality is therefore a sampling problem rather than merely a tuning problem. Boundaries and discrete components also require proposal designs adapted to the state space, since a naive Gaussian increment may generate invalid states.

The method is nevertheless useful as a diagnostic baseline because its mechanism is transparent and its assumptions are comparatively easy to state. Adaptive variants can learn proposal scales or covariance structure during sampling, but adaptation must be controlled so that it does not destroy convergence guarantees; diminishing adaptation and containment are standard theoretical safeguards.⁶ The original Metropolis work arose in statistical mechanics, while later developments made the method central to Bayesian computation.¹²

Target distribution

The probability distribution that the Markov chain is designed to sample, often specified through an unnormalized density.

Proposal distribution

The conditional distribution used to suggest a candidate next state from the current state.

Acceptance probability

The probability with which a proposed move is retained; for a symmetric proposal it is the minimum of one and the target-density ratio.

Effective sample size

An estimate of how many independent observations would provide approximately the same precision as correlated Markov-chain draws.

Detailed balance

A reversibility condition ensuring that probability flow between pairs of states is balanced under the target distribution.