Deriving the acceptance probability

Section of Markov chains, Gibbs sampling, and Metropolis–Hastings, part of Bayesian statistics

Deriving the acceptance probability

Type Section
Taught in Markov chains, Gibbs sampling, and Metropolis–Hastings
Part Bayesian statistics

Begin with any proposal density q(y\mid x) that is easy to simulate. It will not generally satisfy detailed balance for \pi:

\pi(x)q(y\mid x)\neq \pi(y)q(x\mid y).

We correct the imbalance by accepting a proposed move x\to y with probability a(x,y). For y\neq x, the resulting transition density is

q_{\mathrm{MH}}(y\mid x)=q(y\mid x)a(x,y).

Detailed balance will hold if

\pi(x)q(y\mid x)a(x,y) =\pi(y)q(x\mid y)a(y,x).

Consequently the paired acceptance probabilities must obey \frac{a(x,y)}{a(y,x)} =\frac{\pi(y)q(x\mid y)}{\pi(x)q(y\mid x)} =:r(x,y). Only their ratio is prescribed. Since rejection wastes a possible move, take the largest probabilities compatible with Equation (4) in Markov chains, Gibbs sampling, and Metropolis–Hastings and with 0\leq a\leq1. If r(x,y)\leq1, set a(x,y)=r(x,y) and a(y,x)=1; if r(x,y)>1, set a(x,y)=1 and a(y,x)=1/r(x,y). Both cases are a(x,y)=\min\!\left\{ 1, \frac{\pi(y)q(x\mid y)}{\pi(x)q(y\mid x)} \right\}.

Definition 1 (Metropolis–Hastings update) Let \pi(x) be a target density known only up to proportionality. Given X_t=x:

  1. propose Y=y from a proposal density q(y\mid x);

  2. calculate r(x,y) from Equation (4) in Markov chains, Gibbs sampling, and Metropolis–Hastings and put a(x,y)=\min\{1,r(x,y)\};

  3. draw U\sim\operatorname{Unif}(0,1) and set

X_{t+1}= \begin{cases} y,&U\leq a(x,y),\\ x,&U>a(x,y). \end{cases}

If \pi(x)=f(x)/C for unknown C, then

\frac{\pi(y)}{\pi(x)} =\frac{f(y)/C}{f(x)/C} =\frac{f(y)}{f(x)},

so the normalising constant cancels.

Article: Metropolis–Hastings update →

For a posterior, the evidence p(\text{data}) is precisely such a constant, so the ratio needs only likelihood times prior. In computation we normally evaluate the log ratio and accept when

\log U\leq \min\{0,\log r(x,y)\}.

This avoids numerical underflow when an unnormalised target is a product of many small terms.

This cancellation is why Metropolis methods became central in statistical physics. An Ising model on m binary sites has 2^m configurations, making its partition function impractical to sum, but ratios of unnormalised target weights are immediate. The original Metropolis algorithm used symmetric proposals; Hastings’ generalisation supplied the proposal-density correction in Equation (5) in Markov chains, Gibbs sampling, and Metropolis–Hastings.

The wartime history surrounding Los Alamos also includes Leó Szilárd.

For y\neq x, the Metropolis–Hastings transition density is

q_{\mathrm{MH}}(y\mid x)=q(y\mid x)a(x,y).

For y=x, the transition probability includes the total rejection probability:

q_{\mathrm{MH}}(x\mid x) =1-\int_{z\neq x}q(z\mid x)a(x,z)\,\mathrm{d} z.

Thus a rejected proposal is not thrown away in search of another proposal: the current value is recorded again. If instead we redraw until a proposal is accepted, the transition density becomes

\widetilde q(y\mid x) =\frac{q(y\mid x)a(x,y)}{A(x)}, \qquad A(x)=\int q(z\mid x)a(x,z)\,\mathrm{d} z.

The extra normaliser depends on the current state. This altered chain is in detailed balance with a density proportional to \pi(x)A(x), not generally with \pi(x), and therefore targets the wrong distribution.

Used in

See also

Markov chain · Stationarity and detailed balance · Detailed balance implies stationarity · Systematic-scan Gibbs sampler · Warm-up is not a convergence proof · Metropolis–Hastings update · Metropolis–Hastings invariance · Markov chains and equilibrium

Glossary and index