Metropolis–Hastings Algorithm

The Metropolis–Hastings algorithm is the workhorse of Markov-chain Monte Carlo. Its purpose is to generate a sequence of configurations $x_0, x_1, x_2, \dots$ distributed, in the long run, according to a target probability distribution $\pi(x)$ that is typically known only up to an unknown normalizing constant. In equilibrium statistical mechanics the target is the canonical Boltzmann distribution $\pi(x) \propto e^{-\beta E(x)}$ , whose normalization is the partition function $Z$ — a quantity that is generically intractable. Metropolis–Hastings sidesteps $Z$ entirely because the algorithm depends on $\pi$ only through ratios. The construction has two ingredients. A proposal mechanism $g(x'\mid x)$ suggests a candidate state; an accept/reject step then corrects the proposal so that the resulting transition kernel satisfies detailed balance with respect to $\pi$ . Detailed balance — the pairwise flow condition owned by the detailed-balance article — is a sufficient condition making $\pi$ stationary; the genius of the acceptance rule is that it enforces this condition using only the ratio $\pi(x')/\pi(x)$ , in which $Z$ cancels identically. The Monte-Carlo framework into which this rule slots — importance sampling, the estimator, the $N^{-1/2}$ error law — is owned by the monte-carlo-method article and recalled here by name; this article owns the algorithm itself. The single most important structural fact is that the acceptance rule $A=\min(1,r)$ is not arbitrary: it is the largest acceptance probability consistent with detailed balance, and Peskun's theorem shows this maximizes sampling efficiency at fixed proposal. The original Metropolis (1953) rule is the symmetric special case; Hastings (1970) extended it to arbitrary, possibly asymmetric proposals by inserting a correction factor. The chief practical limitation is correlation between successive samples: near a continuous phase transition the integrated autocorrelation time diverges (critical slowing down), which is exactly the failure that cluster algorithms were invented to defeat.

Key takeaways

Metropolis–Hastings (MH) builds a Markov chain whose unique stationary distribution is a prescribed target $\pi(x)$ , allowing sampling from $\pi$ even when its normalization is unknown.
Each step proposes $x\to x'$ from a proposal density $g(x'\mid x)$ and accepts it with probability $A(x'\mid x)=\min\!\big(1,\tfrac{\pi(x')\,g(x\mid x')}{\pi(x)\,g(x'\mid x)}\big)$ .
The acceptance rule enforces detailed balance, so together with ergodicity the chain converges to $\pi$ — and only ratios $\pi(x')/\pi(x)$ appear, so $Z$ cancels.
The original Metropolis (1953) rule is the symmetric special case $g(x'\mid x)=g(x\mid x')$ , giving $\min(1,e^{-\beta\Delta E})$ ; Hastings (1970) added the proposal-ratio correction for asymmetric proposals.
$A=\min(1,r)$ is the largest acceptance consistent with detailed balance (Peskun), so it mixes fastest at fixed proposal; efficiency is set by the autocorrelation time and the acceptance ratio.
Key idea: choose any proposal $g$ you like; accepting with $A=\min(1,\tfrac{\pi(x')g(x\mid x')}{\pi(x)g(x'\mid x)})$ forces detailed balance for $\pi$ , so the sampled distribution is $\pi$ regardless of the proposal — the proposal affects only efficiency, never correctness.

The core insight

Choose any proposal $g(x'\mid x)$ ; then accepting with $A=\min\!\big(1,\tfrac{\pi(x')g(x\mid x')}{\pi(x)g(x'\mid x)}\big)$ forces the chain to obey detailed balance for $\pi$ — so the sampled distribution is $\pi$ regardless of the proposal, which affects only efficiency, not correctness.

Where this lives today

Single-spin Metropolis sampling remains the reference method for measuring magnetization, susceptibility and transition temperatures in lattice spin models, and it is the accept/reject engine inside Hybrid (Hamiltonian) Monte Carlo used in lattice QCD, where molecular-dynamics trajectories serve as elaborate proposals and the MH step corrects for integration error. In Bayesian statistics and probabilistic machine learning, Metropolis–Hastings (and its gradient-informed descendant MALA, with optimal acceptance $\approx0.574$ ) samples posteriors known only up to the evidence — the same $Z$ -free setting as the Boltzmann distribution. The Roberts–Gelman–Gilks result that random-walk Metropolis is optimally tuned at acceptance $\approx0.234$ in high dimension is a daily rule of thumb for practitioners. Where local MH stalls — near critical points, where $\tau_{\mathrm{int}}\sim\xi^z$ — cluster algorithms take over.

The physical picture

Imagine exploring a landscape whose height is $-\ln\pi(x)$ . You repeatedly propose a step. Downhill steps (toward higher probability) are always taken; uphill steps are taken only sometimes, with a probability that decreases the steeper the climb. This biased random walk spends time in each region in exact proportion to $\pi$ , so a histogram of where you have been reproduces the target distribution. The acceptance curve $A(\Delta E)=\min(1,e^{-\beta\Delta E})$ is the whole rule in one picture: a flat plateau at $1$ for downhill moves ( $\Delta E\le0$ ), then an exponential roll-off for uphill moves. The genius is that only the ratio $\pi(x')/\pi(x)$ enters. The unknown normalization $Z$ cancels identically — you never need to know how probable a state is in absolute terms, only how it compares to its neighbour. This is what makes Boltzmann sampling feasible despite $Z$ being uncomputable, and it is why the same algorithm samples Bayesian posteriors (known only up to the evidence) without change. Two features often confuse newcomers. First, rejection is not wasted effort: staying put is how the chain assigns extra weight to high-probability states, so a rejected proposal means the current state is counted again in the average. Second, detailed balance is a bookkeeping device — it guarantees that in steady state the probability current from $x$ to $x'$ exactly cancels the reverse current for every pair, which is a stronger (and more convenient) condition than mere stationarity. The detailed-balance article owns why pairwise balance implies stationarity; here we use it as a lemma and build the acceptance rule on top of it.

Figure

Metropolis acceptance A(ΔE)=min(1,e^(−βΔE)): flat downhill, exponential roll-off uphill

Figure

Rejection keeps the current state: the chain re-counts x, weighting high-π regions

The core equations

The design target is detailed balance with respect to $\pi$ : for every pair of states the forward probability flux equals the reverse flux. This is a sufficient (not necessary) condition for $\pi$ to be stationary, and it is the condition the acceptance rule is built to satisfy.

\pi(x)\,P(x'\mid x) = \pi(x')\,P(x\mid x') \quad \forall\, x, x' \qquad (1)

where: $\pi(x)$ — target stationary distribution (e.g. Boltzmann $\propto e^{-\beta E(x)}$ ); $P(x'\mid x)$ — transition probability of the constructed Markov chain. The kernel factorizes into a proposal and an acceptance. Whatever probability is not spent on accepted moves is assigned to staying put — this is where rejected proposals go, and it is what makes the chain re-count the current state.

P(x'\mid x) = g(x'\mid x)\,A(x'\mid x)\ (x'\neq x),\qquad P(x\mid x)=1-\!\!\sum_{x'\neq x}\!\! g(x'\mid x)A(x'\mid x) \qquad (2)

where: $g(x'\mid x)$ — proposal density; $A(x'\mid x)$ — acceptance probability, $0\le A\le1$ . The Metropolis–Hastings acceptance probability is the rule that makes (2) satisfy (1). The Hastings factor $g(x\mid x')/g(x'\mid x)$ corrects for any asymmetry in the proposal; when the proposal is symmetric it drops out.

A(x'\mid x) = \min\!\left(1,\; \frac{\pi(x')\,g(x\mid x')}{\pi(x)\,g(x'\mid x)}\right) \qquad (3)

where: $\pi(x')/\pi(x)$ — target ratio ( $Z$ cancels); $g(x\mid x')/g(x'\mid x)$ — Hastings proposal-ratio correcting for asymmetry. For Boltzmann sampling with a symmetric proposal, (3) collapses to the celebrated 1953 rule that depends only on the energy difference.

A(x'\mid x) = \min\!\big(1,\, e^{-\beta[E(x')-E(x)]}\big)=\min(1,e^{-\beta\Delta E}) \qquad (4)

where: $\beta=1/(k_BT)$ ; $E(x)$ — energy of configuration $x$ ; $\Delta E=E(x')-E(x)$ . Efficiency is governed by autocorrelation. The variance of an estimate scales with the integrated autocorrelation time; near a critical point this diverges as a power of the correlation length — critical slowing down.

\tau_{\mathrm{int}}=\tfrac12+\sum_{t\ge1}\rho_O(t),\qquad \tau_{\mathrm{int}}\sim\xi^z\sim|T-T_c|^{-z\nu} \qquad (5)

where: $\rho_O(t)$ — normalized autocorrelation of observable $O$ at lag $t$ ; $\xi$ — correlation length; $z$ — dynamic exponent (local Metropolis on 2D Ising: $z\approx2.17$ ); $\nu$ — correlation-length exponent.

Derivation AThe Metropolis choice of acceptance from detailed balance

This derivation shows that the $\min(1,r)$ form is not a lucky guess but the optimal acceptance rule: it is the unique largest acceptance probability that satisfies detailed balance, and by Peskun's theorem the largest acceptance minimizes the asymptotic variance of Monte-Carlo estimates. We recall the detailed-balance condition (owned by the detailed-balance article) as our lemma and solve it for $A$ , keeping the acceptance as high as possible so the chain mixes fastest.

Step 1. Impose detailed balance on the factorized kernel. Substituting $P=gA$ into $\pi(x)P(x'\mid x)=\pi(x')P(x\mid x')$ :

\pi(x)\,g(x'\mid x)\,A(x'\mid x) = \pi(x')\,g(x\mid x')\,A(x\mid x').

Why: the flux of accepted-and-proposed transitions must balance in each direction — this is the detailed-balance lemma applied to the constructed chain.

Step 2. Solve for the ratio of acceptances. Define $r\equiv\dfrac{\pi(x')\,g(x\mid x')}{\pi(x)\,g(x'\mid x)}$ ; then

\frac{A(x'\mid x)}{A(x\mid x')}=r.

Why: any pair $(A(x'\mid x),\,A(x\mid x'))$ whose ratio equals $r$ satisfies detailed balance — the condition fixes only the ratio, not the individual values.

Step 3. Maximize the acceptance subject to $A\le1$ . To decorrelate as fast as possible we want $A$ as large as the constraint allows. If $r\le1$ set $A(x'\mid x)=r$ and $A(x\mid x')=1$ ; if $r\ge1$ set $A(x'\mid x)=1$ and $A(x\mid x')=1/r$ . Why: pushing whichever acceptance can be $1$ up to $1$ leaves the other determined by the ratio and never exceeds the bound.

Step 4. Both cases collapse to a single formula:

A(x'\mid x)=\min(1,r)=\min\!\left(1,\frac{\pi(x')\,g(x\mid x')}{\pi(x)\,g(x'\mid x)}\right).

Why this is optimal: Peskun (1973) proved that among all acceptance functions satisfying detailed balance, $\min(1,r)$ dominates — it gives the smallest asymptotic variance. Barker's alternative $r/(1+r)$ also satisfies detailed balance but is provably less efficient. Verified: $\min(1,r)$ satisfies detailed balance symbolically for both orderings, and Barker's rule is confirmed valid-but-smaller, in verify_aq-sm-metropolis-hastings-algorithm.py.

Go deeper · Derivation B · 1 minSingle-spin Metropolis update for the Ising model

Derivation BSingle-spin Metropolis update for the Ising model

The point of this derivation is to make the abstract rule concrete and to expose why Metropolis is so cheap on lattice models: the acceptance depends only on a local energy change involving a spin and its neighbours, and on a square lattice only five distinct values of $\Delta E$ ever occur, so the Boltzmann factors can be precomputed. This locality is the source of the algorithm's $O(1)$ -per-update efficiency and its dominance in critical-phenomena simulation.

Step 1. Local energy change. For $E=-J\sum_{\langle ij\rangle}s_is_j$ with $s_i=\pm1$ , propose flipping spin $i$ : $s_i\to-s_i$ . Only bonds touching site $i$ change, so

\Delta E = -J(-s_i)\!\!\sum_{j\in n(i)}\!\!s_j - \Big(-Js_i\!\!\sum_{j\in n(i)}\!\!s_j\Big)=2Js_i\!\!\sum_{j\in n(i)}\!\!s_j.

Why local: the flip reverses the sign of every bond at site $i$ and nothing else, so the global energy sum reduces to a neighbour sum.

Step 2. Acceptance. The proposal (pick a spin uniformly) is symmetric, so the Hastings factor is $1$ and

A=\min\!\big(1,\,e^{-\beta\Delta E}\big)=\min\!\Big(1,\exp\!\big[-2\beta J\,s_i\textstyle\sum_{j\in n(i)}s_j\big]\Big).

Step 3. Enumerate the possibilities. On the square lattice ( $z=4$ neighbours) $\sum_{j}s_j\in\{-4,-2,0,2,4\}$ , so $\Delta E\in\{-8J,-4J,0,4J,8J\}$ . Why this matters: only five Boltzmann factors $e^{-\beta\Delta E}$ ever occur; precomputing them makes each update $O(1)$ , independent of system size. Verified: the five allowed $\Delta E$ values and the symmetric-proposal reduction to $\min(1,e^{-\beta\Delta E})$ are checked in verify_aq-sm-metropolis-hastings-algorithm.py.

Limiting cases

Case	Result	Meaning
Symmetric proposal (original Metropolis)	$A=\min(1,e^{-\beta\Delta E})$	$g(x'\mid x)=g(x\mid x')$ makes the proposal ratio drop out — the famous 1953 rule.
Heat-bath / Barker limit	$A=\dfrac{\pi(x')g(x\mid x')}{\pi(x)g(x'\mid x)+\pi(x')g(x\mid x')}$	Barker's alternative also satisfies detailed balance; for a single-spin flip it becomes $1/(1+e^{\beta\Delta E})$ . Provably less efficient than Metropolis (Peskun).
High temperature / flat target	$\beta\to0:\ A\to1$	All moves accepted; the chain reduces to the proposal random walk — fast mixing, little structure.
Low temperature / sharp target	$\beta\to\infty:\ A\to\Theta(-\Delta E)$	Only energy-lowering moves accepted; greedy descent freezes in local minima — needs annealing or parallel tempering.
Critical region	$\tau_{\mathrm{int}}\sim\xi^z,\ z\approx2.17$ (2D Ising)	Local updates suffer critical slowing down; cluster algorithms restructure the spectrum to drive $z\to0$ .

Worked examples

Example 1 — Two-level system: sampling $p_1/p_0=e^{-\beta\Delta E}$ and verifying detailed balance. Take two states $0$ (energy $0$ ) and $1$ (energy $\Delta E$ ) with $\beta\Delta E=2$ . Compute the target ratio and the Metropolis acceptances, then check detailed balance numerically.

Step 1. Target ratio. The Boltzmann weights give $p_1/p_0=e^{-\beta\Delta E}=e^{-2}=\mathbf{0.1353}$ . This is what a long chain must reproduce.

Step 2. Acceptances (symmetric proposal, $g=1$ each way). Uphill $0\to1$ : $A_{0\to1}=\min(1,e^{-2})=e^{-2}=0.1353$ . Downhill $1\to0$ : $A_{1\to0}=\min(1,e^{+2})=1$ .

Step 3. Verify detailed balance. The flux $0\to1$ is $p_0\,A_{0\to1}=p_0 e^{-2}$ ; the flux $1\to0$ is $p_1\,A_{1\to0}=p_1\cdot1$ . Using $p_1=p_0 e^{-2}$ , both equal $p_0 e^{-2}$ — balanced exactly. A simulated chain of $10^6$ steps visits state $1$ a fraction $\approx e^{-2}/(1+e^{-2})=0.1192$ of the time, matching $p_1=e^{-2}/(1+e^{-2})$ within Monte-Carlo error.

Example 2 — Hastings correction restores detailed balance for a biased proposal. Suppose the proposal favours state $1$ over state $0$ : $g(1\mid0)=0.8$ , $g(0\mid1)=0.3$ (asymmetric). Show the bare Metropolis rule is wrong and the Hastings factor fixes it, at $\beta\Delta E=2$ .

Step 1. Bare (wrong) acceptance. Using $\min(1,e^{-\beta\Delta E})$ ignores the proposal bias; the resulting stationary ratio is $p_1^{\text{wrong}}/p_0 = (g_{0\to1}A_{0\to1})/(g_{1\to0}A_{1\to0})=(0.8\times e^{-2})/(0.3\times1)=0.361\neq e^{-2}=0.135$ . The chain samples the wrong distribution.

Step 2. Hastings acceptance. Insert the proposal ratio: $r=\dfrac{\pi_1 g_{1\to0}}{\pi_0 g_{0\to1}}=\dfrac{e^{-2}\times0.3}{1\times0.8}=0.0508$ , so $A_{0\to1}=\min(1,0.0508)=0.0508$ and $A_{1\to0}=\min(1,1/0.0508)=1$ .

Step 3. Verify. Now the flux ratio is $\dfrac{g_{0\to1}A_{0\to1}\,p_0}{g_{1\to0}A_{1\to0}\,p_1}=\dfrac{0.8\times0.0508}{0.3\times1}\cdot\dfrac{p_0}{p_1}=\dfrac{0.0406}{0.3}\cdot e^{2}=1$ , so detailed balance holds and the chain samples $\pi$ correctly. The Hastings factor is not optional for asymmetric proposals — omitting it gives a stationary ratio $0.361$ instead of the correct $0.135$ .

Origins · 1 minnicholas metropolis and how this was discovered

nicholas metropolis

1915–1999 · Greek-American physicist and computing pioneer at Los Alamos. He built the MANIAC computer and headed the computing group behind the 1953 paper (with Arianna and Marshall Rosenbluth and Augusta and Edward Teller) that introduced importance sampling via the acceptance rule now bearing his name — arguably the most-cited algorithm in computational science. Marshall Rosenbluth later recounted (2003) that he and Arianna Rosenbluth devised and coded the actual method, with Metropolis chiefly providing the machine and computer time — so the rule's name honours the group leader more than its inventor. He also coined the term "Monte Carlo" with Stanislaw Ulam. W. Keith Hastings generalized the rule to asymmetric proposals in 1970, completing the modern Metropolis–Hastings framework.

History

1953

— Metropolis, Rosenbluth, Rosenbluth, Teller and Teller publish the acceptance rule for hard-sphere fluids on MANIAC

1970

— Hastings generalizes the rule to arbitrary asymmetric proposals in Biometrika

1973

— Peskun proves that min(1,r) minimizes asymptotic variance among detailed-balance acceptances

1987

— Swendsen and Wang introduce cluster updates to beat critical slowing down

1997

— Roberts, Gelman and Gilks establish the optimal high-dimensional acceptance rate ≈ 0.234

Going further

References. Pathria & Beale, Statistical Mechanics, 3rd ed., Ch. 16 (Computer Simulations) · Kardar, Statistical Physics of Fields, Ch. 8 (Monte Carlo methods) · Sethna, Statistical Mechanics: Entropy, Order Parameters, and Complexity, Ch. 8 · Newman & Barkema, Monte Carlo Methods in Statistical Physics, Ch. 2–3 · Metropolis, Rosenbluth, Rosenbluth, Teller & Teller, J. Chem. Phys. 21, 1087 (1953) · Hastings, Biometrika 57, 97 (1970) · Peskun, Biometrika 60, 607 (1973) · Roberts, Gelman & Gilks, Ann. Appl. Prob. 7, 110 (1997).

Provenance. A verifier should: (1) confirm $\min(1,r)$ satisfies detailed balance for both orderings, and that Barker's rule is valid but smaller (Peskun); (2) check the Ising single-spin $\Delta E=2Js_i\sum_j s_j$ and the five allowed square-lattice values; (3) verify the two-level $p_1/p_0=e^{-\beta\Delta E}$ sampling and the Hastings correction for an asymmetric proposal (this article's verify script); (4) the quoted $z\approx2.17$ (2D Ising local dynamics) and optimal acceptances $0.234$ / $0.574$ are standard literature values. Detailed balance itself is owned by the detailed-balance article and the MC framework by the monte-carlo-method article.

Builds on: Markov Processes and the Markov Property · Detailed Balance and Microscopic Reversibility · The Master Equation · Chapman–Kolmogorov Equation. Leads to: Monte Carlo Method · Cluster Algorithms and Critical Slowing Down · Thermostats and Ensemble Control in Molecular Dynamics · Molecular Dynamics Simulation.

What exactly is the difference between "Metropolis" and "Metropolis–Hastings"?

The 1953 Metropolis rule assumes a symmetric proposal, $g(x'\mid x)=g(x\mid x')$ , so the acceptance is just $\min(1,e^{-\beta\Delta E})$ . Hastings (1970) generalized this to any proposal by inserting the ratio $g(x\mid x')/g(x'\mid x)$ , giving $\min(1,\tfrac{\pi(x')g(x\mid x')}{\pi(x)g(x'\mid x)})$ . Metropolis is the symmetric special case of Metropolis–Hastings. The generalization matters whenever the proposal is deliberately biased — e.g. particle insertion/deletion in the grand-canonical ensemble.

Is detailed balance necessary, or just convenient?

Just sufficient, not necessary. The necessary-and-sufficient condition for $\pi$ to be stationary is global balance, $\sum_x\pi(x)P(x'\mid x)=\pi(x')$ — total flow into each state equals total flow out. Detailed balance enforces this pairwise, which is stronger but far easier to arrange (it fixes the acceptance ratio locally). Non-reversible samplers satisfy global balance without detailed balance and can mix faster, at the cost of a harder design. The detailed-balance article owns the distinction; here it is the lemma the acceptance rule is built on.

Why not just always accept the proposed move?

Because always moving would under-sample the high-probability states. Rejection is the mechanism by which the chain lingers in probable regions: a state with high $\pi$ tends to reject proposals to lower- $\pi$ neighbours, so the chain sits there longer and accumulates more weight. Removing rejection (or, equivalently, failing to re-count the current state after a rejection) breaks the $\pi$ -weighting and biases every estimate.

How do I choose the proposal step size?

Tune it to a target acceptance rate. Too-bold proposals are almost always rejected (the chain stalls); too-timid proposals are almost always accepted but move a tiny distance (slow exploration). The efficiency measure is the expected squared jump distance $\delta^2\langle A\rangle$ , maximized at intermediate step size. In high dimension the universal optimum for random-walk Metropolis is acceptance $\approx0.234$ (Roberts–Gelman–Gilks 1997); for the gradient-informed MALA variant it is $\approx0.574$ . In practice, tune $\delta$ to acceptance $0.2$ – $0.5$ .

Does Metropolis–Hastings give real physical dynamics?

No — the "time" of an MH chain is fictitious, a sequence of accept/reject moves chosen to sample the correct statics. With single-spin flips it happens to resemble Glauber relaxation, but in general it carries no dynamical information. Genuine time-correlation functions and transport coefficients require molecular dynamics (owned by the molecular-dynamics article) or a physically rated kinetic Monte Carlo. MH guarantees the equilibrium distribution, nothing about the route to it.

What is critical slowing down and why does it break local MH?

Near a continuous transition the correlation length $\xi$ diverges. A local update can only rearrange an ordered domain of size $\xi$ by a random walk of single flips across it, which takes $\sim\xi^2$ sweeps, so the integrated autocorrelation time grows as $\tau_{\mathrm{int}}\sim\xi^z$ with $z\approx2.17$ in 2D Ising. Since the effective sample count is $N/(2\tau_{\mathrm{int}})$ , precision collapses right where the interesting physics is. Cluster algorithms flip whole correlated domains in one move, restructuring the transition operator's spectrum so $z\to0$ .

Can I use Metropolis–Hastings for continuous-parameter Bayesian inference?

Yes — this is one of its biggest modern uses. Set $\pi(\theta)\propto \text{likelihood}(\theta)\times\text{prior}(\theta)$ , the unnormalized posterior; the evidence (normalization) plays the role of $Z$ and cancels. Propose $\theta'$ from a Gaussian random walk (or a gradient-informed MALA/HMC proposal), accept with the MH rule, and the chain samples the posterior. The same autocorrelation and acceptance-tuning caveats apply; convergence diagnostics (multiple chains, $\hat R$ ) replace the physicist's thermalization checks.