Deriving the Metropolis-Hastings Acceptance Probability

From Proposed Moves to Probability Flow

Markov chain Monte Carlo constructs a Markov chain whose long-run sampling distribution is a chosen target distribution. A proposal mechanism suggests a move; an acceptance rule decides whether the chain makes it or stays where it is. The key design question is how to choose that rule so that flow from one state to another is balanced by flow in the reverse direction.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(\pi\) be the desired target distribution. In a finite or countable state space, write \(\pi(x)\) for its probability mass at \(x\). In a continuous state space, write \(\pi(x)\) for its density with respect to a common reference measure \(\nu\). The same derivation applies in either case. We assume the chain is currently at a state \(x\) with \(\pi(x)>0\).

Let \(q(y\mid x)\) denote the proposal probability or density for proposing \(y\) from \(x\). For each \(x\), the proposal probabilities sum to one in a countable space, or the proposal density integrates to one in a continuous space. Given a proposed \(y\), the chain accepts with probability \(\alpha(x,y)\in[0,1]\). If it rejects, it remains at \(x\). Thus the probability or density of an accepted move from \(x\) to \(y\), before accounting for the possibility of staying put, is \(q(y\mid x)\alpha(x,y)\).

For two distinct states \(x\) and \(y\), the target-weighted flow of accepted moves from \(x\) to \(y\) is \(\pi(x)q(y\mid x)\alpha(x,y)\). The reverse flow is \(\pi(y)q(x\mid y)\alpha(y,x)\). Detailed balance asks these two quantities to agree. It is a sufficient condition for \(\pi\) to be invariant, and the derivation below shows exactly how it determines the familiar acceptance rule.

When the target is known only up to a positive normalizing constant, write \(\pi(x)=\widetilde{\pi}(x)/Z\), where \(Z\) does not depend on \(x\). The ratio in the definition is unchanged: the factor \(1/Z\) appears in both numerator and denominator and cancels. This is why the rule can be implemented using an unnormalized target.

Deriving the Rule from Pairwise Balance

Proof. The accepted flow from \(x\) to \(y\) is \(a\alpha(x,y)\), while the reverse accepted flow is \(b\alpha(y,x)\). Their equality is therefore precisely the displayed pairwise balance equation. For \(a,b>0\), that equation implies \(\alpha(y,x)=(a/b)\alpha(x,y)\). The constraints that both probabilities are at most one give \(\alpha(x,y)\le1\) and \(\alpha(x,y)\le b/a\). Hence \(\alpha(x,y)\le\min(1,b/a)\). Applying the same argument in the reverse direction gives \(\alpha(y,x)\le\min(1,a/b)\). Choosing these two upper bounds gives equal flows: if \(b\le a\), the forward acceptance is \(b/a\) and the reverse acceptance is \(1\), so both flows equal \(b\); if \(a\le b\), the forward acceptance is \(1\) and the reverse acceptance is \(a/b\), so both flows equal \(a\). Thus the rule balances flow and is maximal in each direction. If \(a>0\) and \(b=0\), pairwise balance reads \(a\alpha(x,y)=0\), which forces \(\alpha(x,y)=0\). \(\square\)

Balance alone does not force this particular rule: multiplying both Metropolis–Hastings acceptance probabilities for a pair by the same constant in \([0,1]\) also balances flow, but accepts less often. The standard rule is the largest pairwise-balanced choice. If both \(a\) and \(b\) are zero, neither direction carries target-weighted proposal flow, so the pairwise equation imposes no restriction.

Why the Rule Preserves the Target

Detailed balance is useful because it implies invariance, including the probability of remaining at the current state after rejection. The next result gives the argument for both countable and continuous state spaces. In the continuous case, assume the proposal has density \(q(y\mid x)\) with respect to \(\nu\), and that the target has density \(\pi\) with respect to the same measure.

Proof. Write \(A(x,dy)=q(y\mid x)\alpha(x,y)\nu(dy)\) for the accepted-move part of the kernel, with sums replacing integrals on a countable space. For \(\pi(x)q(y\mid x)>0\), the acceptance definition gives \[ \pi(x)q(y\mid x)\alpha(x,y) =\min\{\pi(x)q(y\mid x),\pi(y)q(x\mid y)\}. \] The right-hand side is unchanged when \(x\) and \(y\) are exchanged. If either forward weighted proposal flow is zero, both sides of the corresponding accepted-flow balance are zero by the zero-reverse rule. Thus the accepted-flow measure is symmetric in \(x,y\).

Let \(r(x)=1-\int q(y\mid x)\alpha(x,y)\nu(dy)\) be the rejection probability; on a countable space the integral is a sum. It is nonnegative because \(0\le\alpha\le1\) and the proposal integrates or sums to one. The full kernel consists of accepted moves plus rejection at \(x\): \(K(x,dy)=A(x,dy)+r(x)\delta_x(dy)\). For any measurable set \(C\), symmetry of the accepted-flow measure implies that its incoming mass to \(C\) equals its outgoing mass from \(C\). The outgoing accepted mass plus rejection mass from \(C\) is \(\int_C\pi(x)(1-r(x))\nu(dx)+\int_C\pi(x)r(x)\nu(dx)=\int_C\pi(x)\nu(dx)\). Therefore \(\int\pi(dx)K(x,C)=\int_C\pi(x)\nu(dx)\), proving invariance. The same calculation with sums proves the countable case. \(\square\)

Worked Derivations

A Common Error and Its Correction

A frequent mistake is to compare only the target values and omit the proposal probabilities. In the asymmetric two-state example, that shortcut gives the proposed acceptance probability for \(A\to B\) as \(\min(1,\pi(B)/\pi(A))=\min(1,5/2)=1\). But it would produce forward flow \(\tfrac27\cdot\tfrac34\cdot1=\tfrac3{14}=\tfrac6{28}\), while the reverse flow, even with acceptance one, is only \(\tfrac57\cdot\tfrac14=\tfrac5{28}\). The flows do not balance. Including the reverse-to-forward proposal ratio gives \(\alpha(A,B)=\tfrac56\), making both flows \(\tfrac5{28}\). The target ratio alone is appropriate only when the proposal probabilities in the two directions are equal and positive.

The acceptance rule balances the proposed moves, not the probabilities of being at the two states by themselves. A proposal that favors one direction must be corrected by the reverse proposal probability. Also, invariance does not by itself guarantee that a chain can reach every part of the state space: as the one-way example shows, a kernel can preserve a target while failing to explore it. Conditions for convergence and irreducibility are separate questions.