From Proposals to a Transition Matrix
A Metropolis–Hastings calculation is not complete once the acceptance probabilities are known. The chain can move to a proposed state, remain at its current state because a proposal was rejected, or receive a proposal equal to its current state. All of these possibilities contribute to the transition matrix. In particular, rejected proposals add probability to the diagonal; omitting them generally produces rows whose sums are less than one.
We work with a nonempty finite state space \(S\) and a target distribution that assigns positive probability to every state. Write its unnormalized weights as \(w_i>0\), for \(i\in S\), and define \(Z=\sum_{i\in S}w_i\) and \(\pi_i=w_i/Z\). The proposal matrix is \(R=(r_{ij})\), where \(r_{ij}\) is the probability of proposing \(j\) when the current state is \(i\). For this tutorial, assume the proposal is symmetric, \(r_{ij}=r_{ji}\), and row-stochastic, \(\sum_{j\in S}r_{ij}=1\). The asymmetric case requires a different acceptance ratio.
Let \((X_n)_{n\ge0}\) be the resulting discrete-time chain on \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\), with natural filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). Given \(X_n=i\), first draw a proposal \(j\) with probability \(r_{ij}\). If \(j\ne i\), accept it with probability \(\alpha_{ij}=\min(1,w_j/w_i)\); otherwise stay at \(i\). A proposal \(j=i\) leaves the state unchanged.
Equivalently, because the proposal probabilities in row \(i\) sum to one, the diagonal can be computed as \(p_{ii}=1-\sum_{j\ne i}r_{ij}\alpha_{ij}\). This second expression is often convenient after all accepted moves have been calculated. The first expression makes the sources of diagonal probability explicit.
Why the Construction Works
Proof. Every off-diagonal entry \(p_{ij}=r_{ij}\alpha_{ij}\) is nonnegative. The diagonal is a sum of nonnegative terms, \(r_{ii}+\sum_{j\ne i}r_{ij}(1-\alpha_{ij})\), so it is also nonnegative. For any row \(i\), adding its entries gives \(\sum_jp_{ij}=r_{ii}+\sum_{j\ne i}r_{ij}(1-\alpha_{ij})+\sum_{j\ne i}r_{ij}\alpha_{ij}=r_{ii}+\sum_{j\ne i}r_{ij}=1\), using the row sum of \(R\). This argument also applies when \(S\) has one state: the sum over \(j\ne i\) is empty and \(r_{ii}=1\). Therefore \(P\) is row-stochastic. \(\square\)
Proof. Fix distinct states \(i\) and \(j\). Since \(Z>0\) and \(\alpha_{ij}=\min(1,w_j/w_i)\), \(\pi_i p_{ij}=Z^{-1}w_i r_{ij}\min(1,w_j/w_i)=Z^{-1}r_{ij}\min(w_i,w_j)\). Symmetry gives \(r_{ij}=r_{ji}\), and \(\min(w_i,w_j)=\min(w_j,w_i)\). Reversing \(i\) and \(j\) therefore gives \(\pi_i p_{ij}=\pi_jp_{ji}\). For \(i=j\), the equality has identical sides. Now fix \(j\) and sum detailed balance over \(i\): \((\pi P)_j=\sum_i\pi_i p_{ij}=\sum_i\pi_jp_{ji}=\pi_j\sum_i p_{ji}=\pi_j\), because row \(j\) of \(P\) sums to one. Hence \(\pi P=\pi\). \(\square\)
This proves that the target is stationary for the constructed chain under the stated assumptions. It does not establish that a chain started from an arbitrary state converges to that distribution; invariance and convergence are different claims, and convergence requires additional conditions.
Worked Example: A Three-State Proposal with Self-Proposals
Let \(S=\{1,2,3\}\), with weights \(w_1=1,w_2=2,w_3=4\), and proposal matrix \(R=\begin{bmatrix}\tfrac12&\tfrac12&0\\\tfrac12&0&\tfrac12\\0&\tfrac12&\tfrac12\end{bmatrix}\). Its row sums are \(\tfrac12+\tfrac12=1\), \(\tfrac12+\tfrac12=1\), and \(\tfrac12+\tfrac12=1\); its entries are symmetric across the diagonal. The normalizing constant is \(Z=1+2+4=7\), so the proposed target is \(\pi=(\tfrac17,\tfrac27,\tfrac47)\).
From state 1, the only different proposal is state 2. Its acceptance probability is \(\min(1,2/1)=1\), so \(p_{12}=\tfrac12\). The self-proposal has probability \(\tfrac12\), and no proposal is rejected; thus \(p_{11}=\tfrac12\), \(p_{13}=0\), and row 1 is \((\tfrac12,\tfrac12,0)\).
From state 2, proposing state 1 has acceptance probability \(\min(1,1/2)=\tfrac12\), giving \(p_{21}=\tfrac12\cdot\tfrac12=\tfrac14\). Proposing state 3 has acceptance probability \(\min(1,4/2)=1\), giving \(p_{23}=\tfrac12\). The proposal row has no self-proposal, so rejection of the move to state 1 contributes \(p_{22}=\tfrac12(1-\tfrac12)=\tfrac14\). Row 2 is \((\tfrac14,\tfrac14,\tfrac12)\), which sums to \(\tfrac14+\tfrac14+\tfrac12=1\).
From state 3, proposing state 2 has acceptance probability \(\min(1,2/4)=\tfrac12\), giving \(p_{32}=\tfrac14\). The self-proposal contributes \(\tfrac12\), and rejection of the proposal to state 2 contributes \(\tfrac12(1-\tfrac12)=\tfrac14\). Thus \(p_{33}=\tfrac12+\tfrac14=\tfrac34\), \(p_{31}=0\), and row 3 is \((0,\tfrac14,\tfrac34)\), with sum \(0+\tfrac14+\tfrac34=1\).
The complete matrix and target check are \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\\tfrac14&\tfrac14&\tfrac12\\0&\tfrac14&\tfrac34\end{bmatrix}\). Multiplication gives first coordinate \(\tfrac17\cdot\tfrac12+\tfrac27\cdot\tfrac14+\tfrac47\cdot0=\tfrac1{14}+\tfrac1{14}=\tfrac17\); second coordinate \(\tfrac17\cdot\tfrac12+\tfrac27\cdot\tfrac14+\tfrac47\cdot\tfrac14=\tfrac1{14}+\tfrac1{14}+\tfrac17=\tfrac27\); and third coordinate \(\tfrac17\cdot0+\tfrac27\cdot\tfrac12+\tfrac47\cdot\tfrac34=\tfrac17+\tfrac37=\tfrac47\). Hence \(\pi P=\pi\), as required.
Worked Example: A Four-State Nearest-Neighbor Proposal
Take \(S=\{1,2,3,4\}\), weights \((1,3,2,6)\), and proposal rows \(R=\begin{bmatrix}\tfrac12&\tfrac12&0&0\\\tfrac12&0&\tfrac12&0\\0&\tfrac12&0&\tfrac12\\0&0&\tfrac12&\tfrac12\end{bmatrix}\). The four row sums are respectively \(\tfrac12+\tfrac12=1\), \(\tfrac12+\tfrac12=1\), \(\tfrac12+\tfrac12=1\), and \(\tfrac12+\tfrac12=1\). The matrix is symmetric. The target normalizer is \(Z=1+3+2+6=12\), so \(\pi=(\tfrac1{12},\tfrac3{12},\tfrac2{12},\tfrac6{12})\).
At state 1, the proposal to 2 is accepted with probability \(\min(1,3/1)=1\). Therefore \(p_{12}=\tfrac12\), while the self-proposal gives \(p_{11}=\tfrac12\); row 1 is \((\tfrac12,\tfrac12,0,0)\).
At state 2, the proposal to 1 is accepted with probability \(\min(1,1/3)=\tfrac13\), giving \(p_{21}=\tfrac16\). The proposal to 3 is accepted with probability \(\min(1,2/3)=\tfrac23\), giving \(p_{23}=\tfrac13\). The remaining probability is rejection: \(p_{22}=1-\tfrac16-\tfrac13=\tfrac12\). Row 2 is \((\tfrac16,\tfrac12,\tfrac13,0)\), with sum \(\tfrac16+\tfrac12+\tfrac13=1\).
At state 3, the proposal to 2 is accepted with probability \(\min(1,3/2)=1\), and the proposal to 4 is accepted with probability \(\min(1,6/2)=1\). Thus \(p_{32}=\tfrac12,p_{34}=\tfrac12,p_{33}=0,p_{31}=0\); row 3 sums to \(\tfrac12+\tfrac12=1\).
At state 4, the proposal to 3 is accepted with probability \(\min(1,2/6)=\tfrac13\), giving \(p_{43}=\tfrac16\). The self-proposal contributes \(\tfrac12\), and rejection contributes \(\tfrac12(1-\tfrac13)=\tfrac13\), so \(p_{44}=\tfrac56\). Row 4 is \((0,0,\tfrac16,\tfrac56)\), whose sum is \(\tfrac16+\tfrac56=1\). Therefore \(P=\begin{bmatrix}\tfrac12&\tfrac12&0&0\\\tfrac16&\tfrac12&\tfrac13&0\\0&\tfrac12&0&\tfrac12\\0&0&\tfrac16&\tfrac56\end{bmatrix}\).
Check \(\pi P\) coordinate by coordinate. Coordinate 1 is \(\tfrac1{12}\cdot\tfrac12+\tfrac3{12}\cdot\tfrac16=\tfrac1{24}+\tfrac1{24}=\tfrac1{12}\). Coordinate 2 is \(\tfrac1{12}\cdot\tfrac12+\tfrac3{12}\cdot\tfrac12+\tfrac2{12}\cdot\tfrac12=\tfrac1{24}+\tfrac3{24}+\tfrac2{24}=\tfrac14=\tfrac3{12}\). Coordinate 3 is \(\tfrac3{12}\cdot\tfrac13+\tfrac6{12}\cdot\tfrac16=\tfrac1{12}+\tfrac1{12}=\tfrac2{12}\). Coordinate 4 is \(\tfrac2{12}\cdot\tfrac12+\tfrac6{12}\cdot\tfrac56=\tfrac1{12}+\tfrac5{12}=\tfrac6{12}\). Thus \(\pi P=\pi\).
Worked Example: Rejections with a Complete Proposal
Let \(S=\{1,2,3\}\), with weights \((1,2,1)\), and propose each of the three states with probability \(\tfrac13\), regardless of the current state. Every proposal row sums to \(\tfrac13+\tfrac13+\tfrac13=1\), and the proposal matrix is symmetric. Here \(Z=1+2+1=4\), so \(\pi=(\tfrac14,\tfrac12,\tfrac14)\).
From state 1, proposals to 2 and 3 are both accepted: their acceptance probabilities are \(\min(1,2/1)=1\) and \(\min(1,1/1)=1\). Each has transition probability \(\tfrac13\), while the proposal of 1 itself contributes \(\tfrac13\) to the diagonal. Row 1 is \((\tfrac13,\tfrac13,\tfrac13)\), summing to 1.
From state 2, proposals to 1 and 3 each have acceptance probability \(\min(1,1/2)=\tfrac12\). Each corresponding off-diagonal transition probability is \(\tfrac13\cdot\tfrac12=\tfrac16\). The proposal of 2 itself contributes \(\tfrac13\), and the two rejected proposals contribute \(\tfrac16+\tfrac16\). Hence \(p_{22}=\tfrac13+\tfrac16+\tfrac16=\tfrac23\). Row 2 is \((\tfrac16,\tfrac23,\tfrac16)\), with sum \(\tfrac16+\tfrac23+\tfrac16=1\). State 3 has the same transition row as state 1, since its weight equals \(w_1\).
The completed matrix is \(P=\begin{bmatrix}\tfrac13&\tfrac13&\tfrac13\\\tfrac16&\tfrac23&\tfrac16\\\tfrac13&\tfrac13&\tfrac13\end{bmatrix}\). The coordinates of \(\pi P\) are \(\tfrac14\cdot\tfrac13+\tfrac12\cdot\tfrac16+\tfrac14\cdot\tfrac13=\tfrac1{12}+\tfrac1{12}+\tfrac1{12}=\tfrac14\), \(\tfrac14\cdot\tfrac13+\tfrac12\cdot\tfrac23+\tfrac14\cdot\tfrac13=\tfrac1{12}+\tfrac13+\tfrac1{12}=\tfrac12\), and \(\tfrac14\cdot\tfrac13+\tfrac12\cdot\tfrac16+\tfrac14\cdot\tfrac13=\tfrac14\). Thus the target is preserved.
Common Mistake: Dropping Rejected Probability
In the first example, a common incorrect calculation sets \(p_{22}=0\) because the proposal matrix has no self-proposal from state 2. That confuses “no self-proposal” with “no probability of staying.” From state 2, the proposal to 1 occurs with probability \(\tfrac12\) and is rejected with probability \(\tfrac12\), so the stay probability contributed by rejection is \(\tfrac12\cdot\tfrac12=\tfrac14\). The proposal to 3 is accepted, contributing \(\tfrac12\) to \(p_{23}\), and the accepted move to 1 contributes \(\tfrac14\) to \(p_{21}\). If \(p_{22}\) is incorrectly set to zero, row 2 sums to \(\tfrac14+0+\tfrac12=\tfrac34\), not 1. The correction is to put the rejected mass on the diagonal, giving row \((\tfrac14,\tfrac14,\tfrac12)\).
A reliable calculation therefore follows a fixed order: verify that the proposal rows sum to one; calculate each off-diagonal transition as proposal probability times acceptance probability; place all remaining probability on the diagonal; check each completed row; and finally multiply the proposed target by the matrix. The last check confirms invariance for the specific calculation, while the detailed-balance proof explains why it works for every finite positive target and symmetric proposal under these assumptions.
Check Your Understanding
Use the off-diagonal acceptance rule and include rejected proposals when computing each diagonal entry.
- For two states with weights \(w_1=1,w_2=3\) and proposal matrix \(\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac12&\tfrac12\end{bmatrix}\), compute the full Metropolis–Hastings matrix and check both row sums.
- In the three-state complete-proposal example, identify separately the proposal-of-current-state and rejected-proposal contributions to \(p_{22}\).
- Explain why \(p_{ij}=r_{ij}\alpha_{ij}\) for \(i\ne j\) does not by itself specify a complete transition matrix.
- For a finite symmetric proposal and positive weights, show how the expression \(Z^{-1}r_{ij}\min(w_i,w_j)\) verifies detailed balance for distinct \(i\) and \(j\).
- Give one reason why verifying \(\pi P=\pi\) does not, by itself, prove convergence to \(\pi\) from every starting state.