Tutorials › Stochastic Processes › Metropolis-Hastings with Asymmetric Proposals

Home  /  Tutorials  /  Markov Chain Monte Carlo

Markov Chain Monte Carlo · Tutorial 915 of 994

Metropolis-Hastings with Asymmetric Proposals

Calculate Metropolis–Hastings transitions for asymmetric proposals and verify why the reverse-proposal factor is essential for targeting the intended distribution.

Advanced 10 min read

What You'll Learn

  • Write the acceptance probability when proposal probabilities differ by direction.
  • Construct a Metropolis–Hastings transition matrix from a state-dependent proposal.
  • Verify detailed balance and invariance by checking probability flows.
  • Calculate a birth-death proposal on a finite state space.
  • Find the invariant distribution produced by an uncorrected proposal rule.
  • Identify cases where a proposal has no reverse move.

Why Asymmetric Proposals Need a Correction

A proposal mechanism may favor one direction over another. For example, a state-dependent rule might propose moving upward with high probability at one state and downward with high probability at another. Accepting proposed moves using only the target probabilities does not, in general, compensate for this directional imbalance. Metropolis–Hastings corrects it by including the probability of proposing the reverse move.

Let \(S\) be a finite state space, let \(\pi\) be a probability distribution on \(S\) with \(\pi(i)>0\) for every \(i\), and let \(q(i,j)\) be a proposal probability. Thus \(q(i,j)\ge 0\) and \(\sum_{j\in S}q(i,j)=1\) for each \(i\). A Metropolis–Hastings chain \((X_n)_{n\ge 0}\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), uses this proposal and accepts or rejects it. Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). For a proposed move from \(i\) to a distinct state \(j\) with \(q(i,j)>0\), define

$$ \alpha(i,j)=\min\left\{1,\frac{\pi(j)q(j,i)}{\pi(i)q(i,j)}\right\}. $$

If \(q(i,j)=0\), that move is never proposed and its acceptance probability can be set to \(0\). If \(q(i,j)>0\) but \(q(j,i)=0\), then \(\alpha(i,j)=0\): the proposed one-way move is rejected. The transition probabilities for distinct states and the probability of staying put are

$$ P(i,j)=q(i,j)\alpha(i,j)\quad (j\ne i),\qquad P(i,i)=1-\sum_{j\ne i}P(i,j). $$

The diagonal probability includes both rejected proposals and proposals that leave the state unchanged. This definition makes every row of \(P\) sum to \(1\).

Theorem: For finite \(S\), a strictly positive target distribution \(\pi\), and any proposal matrix \(q\) whose rows sum to \(1\), the Metropolis–Hastings transition matrix defined above satisfies detailed balance, \(\pi(i)P(i,j)=\pi(j)P(j,i)\) for every \(i,j\). Consequently, \(\pi P=\pi\), so \(\pi\) is invariant.

Proof. For distinct \(i,j\), if either proposal probability is zero, both sides of the detailed-balance equation are zero: if \(q(i,j)=0\), then \(P(i,j)=0\), and if \(q(j,i)=0\), then \(\alpha(i,j)=0\); the reverse direction is handled by the same reasoning. If both proposal probabilities are positive, substitution gives

$$ \pi(i)P(i,j) =q(i,j)\min\left\{\pi(i),\frac{\pi(j)q(j,i)}{q(i,j)}\right\} =\min\{\pi(i)q(i,j),\pi(j)q(j,i)\}. $$

The final expression is unchanged when \(i\) and \(j\) are exchanged, so detailed balance holds off the diagonal. On the diagonal, \(\pi(i)P(i,i)=\pi(i)P(i,i)\), so it holds there as well. For each \(j\), sum detailed balance over \(i\):

$$ \sum_{i\in S}\pi(i)P(i,j) =\sum_{i\in S}\pi(j)P(j,i) =\pi(j)\sum_{i\in S}P(j,i) =\pi(j). $$

The last equality uses the fact that row \(j\) of \(P\) sums to \(1\). This is exactly \(\pi P=\pi\). \(\square\)

Calculating the Correction

The ratio has two parts: the target ratio \(\pi(j)/\pi(i)\) and the reverse-to-forward proposal ratio \(q(j,i)/q(i,j)\). When proposals are symmetric, the latter is \(1\); otherwise it adjusts acceptance to account for how often each direction is proposed. Detailed balance expresses the resulting balance of probability flow between each pair of states.

Worked Example: A Three-State Asymmetric Proposal

Take \(S=\{0,1,2\}\), target distribution \(\pi=(\tfrac12,\tfrac13,\tfrac16)\), and proposal matrix

$$ q= \begin{bmatrix} \tfrac14&\tfrac34&0\\ \tfrac14&\tfrac14&\tfrac12\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$

Before calculating transitions, check the proposal rows: \(\tfrac14+\tfrac34+0=1\), \(\tfrac14+\tfrac14+\tfrac12=1\), and \(0+\tfrac12+\tfrac12=1\). For the move \(0\to1\),

$$ \alpha(0,1)=\min\left\{1,\frac{(\tfrac13)(\tfrac14)}{(\tfrac12)(\tfrac34)}\right\} =\min\{1,\tfrac29\}=\tfrac29. $$

For the reverse move, \(\alpha(1,0)=\min\{1,(\tfrac12)(\tfrac34)/[(\tfrac13)(\tfrac14)]\}=1\). For \(1\to2\),

$$ \alpha(1,2)=\min\left\{1,\frac{(\tfrac16)(\tfrac12)}{(\tfrac13)(\tfrac12)}\right\}=\tfrac12, \qquad \alpha(2,1)=\min\left\{1,\frac{(\tfrac13)(\tfrac12)}{(\tfrac16)(\tfrac12)}\right\}=1. $$

Thus the accepted probabilities are \(P(0,1)=\tfrac34\cdot\tfrac29=\tfrac16\), \(P(1,0)=\tfrac14\), \(P(1,2)=\tfrac12\cdot\tfrac12=\tfrac14\), and \(P(2,1)=\tfrac12\). Adding the remaining probability to each diagonal gives

$$ P= \begin{bmatrix} \tfrac56&\tfrac16&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$

Its rows sum to \(1\): \(\tfrac56+\tfrac16=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(\tfrac12+\tfrac12=1\). Check the two nontrivial detailed-balance pairs: \((\tfrac12)(\tfrac16)=\tfrac1{12}=(\tfrac13)(\tfrac14)\), and \((\tfrac13)(\tfrac14)=\tfrac1{12}=(\tfrac16)(\tfrac12)\). The \(0,2\) pair has zero flow in both directions. The diagonal pairs are equal by identity. Hence detailed balance holds. As a direct stationarity check, the three coordinates of \(\pi P\) are \(\tfrac12\cdot\tfrac56+\tfrac13\cdot\tfrac14=\tfrac12\), \(\tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac12+\tfrac16\cdot\tfrac12=\tfrac13\), and \(\tfrac13\cdot\tfrac14+\tfrac16\cdot\tfrac12=\tfrac16\). Therefore \(\pi P=\pi\).

A State-Dependent Birth-Death Proposal

A birth-death proposal on \(\{0,1,\ldots,m\}\) proposes only a neighboring state: a birth moves from \(i\) to \(i+1\), and a death moves from \(i\) to \(i-1\). The proposal probabilities may depend on \(i\), and at the boundary only the move that stays in the state space is available. The reverse-proposal factor is especially important here because the probability of proposing a birth at one state need not equal the probability of proposing the corresponding death at the next state.

Worked Example: A Four-State Birth-Death Proposal

Let \(S=\{0,1,2,3\}\), with target distribution \(\pi=(\tfrac1{10},\tfrac2{10},\tfrac3{10},\tfrac4{10})\). Use the proposal matrix

$$ q= \begin{bmatrix} 0&1&0&0\\ \tfrac14&0&\tfrac34&0\\ 0&\tfrac13&0&\tfrac23\\ 0&0&1&0 \end{bmatrix}. $$

Each proposal row sums to \(1\): \(1=1\), \(\tfrac14+\tfrac34=1\), \(\tfrac13+\tfrac23=1\), and \(1=1\). For \(0\to1\), the acceptance probability is \(\min\{1,(\tfrac2{10})(\tfrac14)/[(\tfrac1{10})(1)]\}=\tfrac12\); for \(1\to0\), it is \(1\). For \(1\to2\), it is \(\min\{1,(\tfrac3{10})(\tfrac13)/[(\tfrac2{10})(\tfrac34)]\}=\tfrac23\); for \(2\to1\), it is \(1\). For \(2\to3\), it is \(\min\{1,(\tfrac4{10})(1)/[(\tfrac3{10})(\tfrac23)]\}=1\); for \(3\to2\), it is \(\min\{1,(\tfrac3{10})(\tfrac23)/[(\tfrac4{10})(1)]\}=\tfrac12\).

Multiplying each acceptance probability by its proposal probability gives

$$ P= \begin{bmatrix} \tfrac12&\tfrac12&0&0\\ \tfrac14&\tfrac14&\tfrac12&0\\ 0&\tfrac13&0&\tfrac23\\ 0&0&\tfrac12&\tfrac12 \end{bmatrix}. $$

The row sums are \(\tfrac12+\tfrac12=1\), \(\tfrac14+\tfrac14+\tfrac12=1\), \(\tfrac13+\tfrac23=1\), and \(\tfrac12+\tfrac12=1\). To check stationarity directly, the incoming masses are \((\tfrac1{10})(\tfrac12)+(\tfrac2{10})(\tfrac14)=\tfrac1{10}\) at state \(0\); \((\tfrac1{10})(\tfrac12)+(\tfrac2{10})(\tfrac14)+(\tfrac3{10})(\tfrac13)=\tfrac2{10}\) at state \(1\); \((\tfrac2{10})(\tfrac12)+(\tfrac4{10})(\tfrac12)=\tfrac3{10}\) at state \(2\); and \((\tfrac3{10})(\tfrac23)+(\tfrac4{10})(\tfrac12)=\tfrac4{10}\) at state \(3\). These reproduce \(\pi\), and its entries sum to \(\tfrac1{10}+\tfrac2{10}+\tfrac3{10}+\tfrac4{10}=1\).

Why the Reverse Probability Cannot Be Dropped

For a proposed move \(i\to j\), the uncorrected rule \(\min\{1,\pi(j)/\pi(i)\}\) considers only whether the destination has more or less target mass. It ignores how frequently the proposal mechanism sends the chain in each direction. The next calculation shows that this can change the invariant distribution, even when every move has a reverse proposal.

Worked Example: The Wrong Invariant Distribution Without the Correction

Use the three-state target and proposal from the first example, but replace the Metropolis–Hastings acceptance rule by \(\widetilde{\alpha}(i,j)=\min\{1,\pi(j)/\pi(i)\}\). For \(0\to1\), this gives \(\min\{1,(\tfrac13)/(\tfrac12)\}=\tfrac23\); for \(1\to0\), it gives \(1\). For \(1\to2\), it gives \(\min\{1,(\tfrac16)/(\tfrac13)\}=\tfrac12\); for \(2\to1\), it gives \(1\).

The resulting transition probabilities, including rejected proposals on the diagonal, are

$$ \widetilde P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$

Each row sums to \(1\). A stationary distribution for this chain is \(\widetilde\pi=(\tfrac14,\tfrac12,\tfrac14)\). To verify it, calculate the incoming coordinates: \((\tfrac14)(\tfrac12)+(\tfrac12)(\tfrac14)=\tfrac14\); \((\tfrac14)(\tfrac12)+(\tfrac12)(\tfrac12)+(\tfrac14)(\tfrac12)=\tfrac12\); and \((\tfrac12)(\tfrac14)+(\tfrac14)(\tfrac12)=\tfrac14\). Its entries sum to \(1\), but it differs from the desired \((\tfrac12,\tfrac13,\tfrac16)\). For instance, the uncorrected flow from \(0\) to \(1\) under the target is \((\tfrac12)(\tfrac12)=\tfrac14\), whereas the reverse flow is \((\tfrac13)(\tfrac14)=\tfrac1{12}\); these are not equal. The reverse-proposal factor restores the balance.

Accepted Flow and a Common Pitfall

Proposition: For a pair of distinct states \(i,j\) with positive proposal probabilities in both directions, any accept-or-reject rule satisfying detailed balance has accepted flow no greater than \(\min\{\pi(i)q(i,j),\pi(j)q(j,i)\}\). The Metropolis–Hastings rule attains this bound.

Proof. Let \(a(i,j)\) and \(a(j,i)\) be acceptance probabilities for the two directions, each between \(0\) and \(1\). Detailed balance requires the common accepted flow \(c=\pi(i)q(i,j)a(i,j)=\pi(j)q(j,i)a(j,i)\). Since both acceptance probabilities are at most \(1\), \(c\le\pi(i)q(i,j)\) and \(c\le\pi(j)q(j,i)\). Therefore \(c\le\min\{\pi(i)q(i,j),\pi(j)q(j,i)\}\). Under Metropolis–Hastings, the detailed-balance calculation gives exactly this minimum, so the bound is attained. \(\square\)

Common pitfall: using the target ratio alone is correct only in special circumstances, such as symmetric proposals. In the three-state example, the naive rule gives \(\widetilde{\alpha}(0,1)=\tfrac23\), while the correct rule gives \(\alpha(0,1)=\tfrac29\). The difference comes from \(q(1,0)/q(0,1)=(\tfrac14)/(\tfrac34)=\tfrac13\). Omitting that factor produces the matrix \(\widetilde P\) and its different stationary distribution. A reliable calculation lists both \(q(i,j)\) and \(q(j,i)\) for every proposed move before evaluating acceptance.

Check Your Understanding

For each question, state the proposal probabilities used and check any claimed transition row or distribution by substitution.

  1. If \(\pi(i)=\tfrac14\), \(\pi(j)=\tfrac12\), \(q(i,j)=\tfrac23\), and \(q(j,i)=\tfrac13\), calculate \(\alpha(i,j)\).
  2. What happens to a proposed move when \(q(i,j)>0\) but \(q(j,i)=0\)?
  3. For the four-state birth-death example, verify detailed balance on the pair \(1,2\).
  4. Explain why a proposal matrix must have rows summing to \(1\) before it can define a proposal distribution.
  5. In the three-state example, calculate the target flow from \(1\) to \(2\) and compare it with the reverse flow after Metropolis–Hastings correction.

Previous

Next

Back to Tutorials