Testing Reversibility by Comparing Flows
For a finite Markov chain, reversibility can be checked using a finite list of exact equalities. The relevant quantity for a transition from \(i\) to \(j\) is not just its probability \(p_{ij}\), but its stationary probability flow \(\pi_i p_{ij}\). Detailed balance asks whether this flow equals the reverse flow \(\pi_j p_{ji}\) for every pair of states. This gives a direct test that can be carried out alongside a calculation of the reverse transition matrix.
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). A distribution \(\pi\) is a row vector with nonnegative entries summing to \(1\); it is stationary if \(\pi P=\pi\).
Because the equation for \(i=j\) is an identity, only distinct-state pairs need checking. For each unordered pair \(\{i,j\}\), compare the two directed flows. If even one pair fails, the chain is not reversible with respect to that candidate \(\pi\). First verify that \(\pi\) really is a probability distribution and is stationary: detailed balance implies stationarity, but a candidate that is not stationary cannot serve as a stationary distribution for reversibility.
Proof. Fix \(j\in S\). Summing the detailed-balance equalities over \(i\in S\) gives \[ \sum_{i\in S}\pi_i p_{ij} =\sum_{i\in S}\pi_j p_{ji} =\pi_j\sum_{i\in S}p_{ji} =\pi_j. \] The first expression is the \(j\)th component of \(\pi P\); the penultimate sum is row \(j\) of \(P\), so it equals \(1\). This holds for every \(j\), and therefore \(\pi P=\pi\). \(\square\)
For a strictly positive stationary distribution, the same pairwise comparison also tests whether the reverse transition matrix equals the original one. Positivity matters because the reverse transition formula divides by the stationary mass of its starting state.
Proof. For each \(i\), stationarity in coordinate \(i\) says \(\sum_{j\in S}\pi_jp_{ji}=\pi_i\). Since \(\pi_i>0\), \[ \sum_{j\in S}p^*_{ij} =\frac{1}{\pi_i}\sum_{j\in S}\pi_jp_{ji} =1. \] All entries are nonnegative, so \(P^*\) is row-stochastic. Now \(p^*_{ij}=p_{ij}\) is equivalent, after multiplying by the positive number \(\pi_i\), to \(\pi_jp_{ji}=\pi_i p_{ij}\). This is exactly detailed balance. The equivalence holds for every pair, proving both directions. \(\square\)
A Practical Pair-by-Pair Test
For a small matrix, the calculation is most reliable when the checks are kept separate. First check every row sum of \(P\); then check that the proposed entries of \(\pi\) sum to \(1\) and that \(\pi P=\pi\). Next form the flows \(F_{ij}=\pi_i p_{ij}\). Compare \(F_{ij}\) and \(F_{ji}\) once for each distinct unordered pair. When \(\pi\) is strictly positive, calculate \(P^*\) from its definition and verify that it is row-stochastic. The theorem explains why agreement of \(P^*\) and \(P\) is equivalent to the flow comparisons.
Worked Example: A Reversible Chain with Unequal Stationary Masses
Consider the state space \(S=\{1,2,3\}\), the transition matrix below, and the candidate \(\pi=(\tfrac12,\tfrac13,\tfrac16)\). Test detailed balance and calculate the reverse matrix.
Before using the matrix, check its rows: row 1 sums to \(\tfrac23+\tfrac16+\tfrac16=1\); row 2 sums to \(\tfrac14+\tfrac12+\tfrac14=1\); row 3 sums to \(\tfrac12+\tfrac12+0=1\). The candidate distribution is normalized because \(\tfrac12+\tfrac13+\tfrac16=1\), and all its entries are positive.
For the pair \(\{1,2\}\), the flows are \(\pi_1p_{12}=\tfrac12\cdot\tfrac16=\tfrac1{12}\) and \(\pi_2p_{21}=\tfrac13\cdot\tfrac14=\tfrac1{12}\). For \(\{1,3\}\), they are \(\pi_1p_{13}=\tfrac12\cdot\tfrac16=\tfrac1{12}\) and \(\pi_3p_{31}=\tfrac16\cdot\tfrac12=\tfrac1{12}\). For \(\{2,3\}\), they are \(\pi_2p_{23}=\tfrac13\cdot\tfrac14=\tfrac1{12}\) and \(\pi_3p_{32}=\tfrac16\cdot\tfrac12=\tfrac1{12}\). The diagonal equations hold automatically. Thus all detailed-balance equations hold.
As a separate stationarity check, multiply the row vector \(\pi\) by \(P\). The three resulting coordinates are \[ \tfrac12\cdot\tfrac23+\tfrac13\cdot\tfrac14+\tfrac16\cdot\tfrac12 =\tfrac13+\tfrac1{12}+\tfrac1{12}=\tfrac12, \] \[ \tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac12+\tfrac16\cdot\tfrac12 =\tfrac1{12}+\tfrac16+\tfrac1{12}=\tfrac13, \] and \[ \tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac14+\tfrac16\cdot0 =\tfrac1{12}+\tfrac1{12}+0=\tfrac16. \] Hence \(\pi P=\pi\), as required.
Using \(p^*_{ij}=\pi_jp_{ji}/\pi_i\), the first reverse row is \((\tfrac23,\tfrac13\cdot\tfrac14/(\tfrac12),\tfrac16\cdot\tfrac12/(\tfrac12))=(\tfrac23,\tfrac16,\tfrac16)\). The second is \((\tfrac12\cdot\tfrac16/(\tfrac13),\tfrac12,\tfrac16\cdot\tfrac12/(\tfrac13))=(\tfrac14,\tfrac12,\tfrac14)\). The third is \((\tfrac12\cdot\tfrac16/(\tfrac16),\tfrac13\cdot\tfrac14/(\tfrac16),0)=(\tfrac12,\tfrac12,0)\). Therefore \(P^*=P\). Each reverse row sums to \(1\): the sums are respectively \(\tfrac23+\tfrac16+\tfrac16=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(\tfrac12+\tfrac12+0=1\). This confirms reversibility by both tests.
Worked Example: A Stationary Chain That Fails Detailed Balance
Let \(S=\{1,2,3\}\) and take \[ P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac12&0&\tfrac12 \end{bmatrix}, \qquad \pi=(\tfrac13,\tfrac13,\tfrac13). \] Each row sums to \(1\): the row sums are \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(\tfrac12+0+\tfrac12=1\). The candidate is normalized, and each column also sums to \(1\); consequently, each coordinate of \(\pi P\) is \(\tfrac13\), so \(\pi P=\pi\).
Stationarity does not settle reversibility. For the pair \(\{1,2\}\), \(\pi_1p_{12}=\tfrac13\cdot\tfrac12=\tfrac16\), whereas \(\pi_2p_{21}=\tfrac13\cdot0=0\). The flows disagree, so detailed balance fails and the chain is not reversible with respect to \(\pi\). The reverse matrix, computed from the formula, is \[ P^*= \begin{bmatrix} \tfrac12&0&\tfrac12\\ \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. \] For example, \(p^*_{12}=\pi_2p_{21}/\pi_1=0\), while \(p^*_{13}=\pi_3p_{31}/\pi_1=\tfrac12\). Its rows sum to \(\tfrac12+0+\tfrac12=1\), \(\tfrac12+\tfrac12+0=1\), and \(0+\tfrac12+\tfrac12=1\). As expected, \(P^*\ne P\).
Zero Stationary Masses and the Scope of the Reverse Matrix
Care is needed if a stationary distribution has zero entries. Detailed balance is still the equation \(\pi_i p_{ij}=\pi_jp_{ji}\), including pairs for which one or both stationary masses vanish. But that equation does not always force the transition probabilities themselves to agree. In particular, when \(\pi_j=0\), the equation \(\pi_i p_{ij}=\pi_jp_{ji}\) with \(\pi_i>0\) forces \(p_{ij}=0\); it says nothing that would force \(p_{ji}=0\).
For a distribution with zero entries, the reverse formula \(p^*_{ij}=\pi_jp_{ji}/\pi_i\) defines rows only for states \(i\) with \(\pi_i>0\). These rows sum to \(1\), by stationarity. Rows at zero-mass states cannot be obtained by division by \(\pi_i\) from this formula. Thus the full-matrix equivalence between \(P^*=P\) and detailed balance was stated above under strict positivity; do not apply it unchanged to a distribution with zero entries.
Worked Example: Detailed Balance with a Zero-Mass State
On \(S=\{1,2\}\), let \[ P=\begin{bmatrix}1&0\\1&0\end{bmatrix}, \qquad \pi=(1,0). \] Both rows sum to \(1\), and \(\pi\) is normalized. Direct multiplication gives \(\pi P=(1\cdot1+0\cdot1,\ 1\cdot0+0\cdot0)=(1,0)=\pi\).
For the distinct pair, \(\pi_1p_{12}=1\cdot0=0\) and \(\pi_2p_{21}=0\cdot1=0\), so detailed balance holds. The diagonal equations are identities. Nevertheless \(p_{12}=0\) and \(p_{21}=1\). This example shows why a zero stationary mass must not be cancelled or treated as positive in a balance equation. The reverse row for state 1 is defined and equals \((\pi_1p_{11}/\pi_1,\pi_2p_{21}/\pi_1)=(1,0)\); the formula does not define a row for state 2 because \(\pi_2=0\).
Common Mistakes and a Reliable Check
A frequent error is to obtain the reverse matrix by transposing \(P\). Transposition reverses the positions of entries, but it does not account for unequal stationary masses. In the first example, the first row of \(P^{\mathsf T}\) is \((\tfrac23,\tfrac14,\tfrac12)\), whose sum is \(\tfrac23+\tfrac14+\tfrac12=\tfrac{17}{12}\), not \(1\). It cannot be a transition row. The correct reverse row is calculated as \(p^*_{1j}=\pi_jp_{j1}/\pi_1\); the three entries are \(\tfrac23,\tfrac16,\tfrac16\), which sum to \(1\).
Another error is to test only whether \(\pi\) is stationary and conclude that the chain is reversible. The second example has a stationary uniform distribution, but its \(\{1,2\}\) flows are \(\tfrac16\) and \(0\). Stationarity balances the total incoming and outgoing mass at each state; reversibility requires equality of the flows separately for every pair. A dependable calculation therefore checks both the candidate distribution and every unordered pair, and it treats zero-mass states without division or cancellation.
| Check | Calculation | What it establishes |
|---|---|---|
| Transition matrix | \(\sum_j p_{ij}=1\) for each row \(i\) | The rows are probability distributions. |
| Candidate distribution | \(\pi_i\ge0\) and \(\sum_i\pi_i=1\) | The candidate is a probability distribution. |
| Stationarity | Compute \(\pi P\) and compare with \(\pi\) | The candidate is stationary. |
| Detailed balance | Compare \(\pi_i p_{ij}\) with \(\pi_jp_{ji}\) for each distinct pair | All pairwise flows balance exactly when the chain is reversible with respect to \(\pi\). |
| Reverse matrix | \(p^*_{ij}=\pi_jp_{ji}/\pi_i\) for \(\pi_i>0\) | For strictly positive \(\pi\), \(P^*=P\) exactly when detailed balance holds. |
Check Your Understanding
Use exact fractions, check all transition-row sums, and state which candidate distribution you are using.
- For the first worked example, verify the detailed-balance equation for the pair \(\{1,3\}\) and calculate \(p^*_{31}\).
- In the second example, calculate both flows for the pair \(\{2,3\}\). Does that pair alone fail the test?
- Why does \(\pi P=\pi\) not imply \(\pi_i p_{ij}=\pi_jp_{ji}\) for each pair?
- For \(P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac14&\tfrac34\end{bmatrix}\) and \(\pi=(\tfrac12,\tfrac12)\), test detailed balance and compute the reverse matrix.
- In the zero-mass example, which detailed-balance equation rules out a transition from state 1 to state 2, and why does no equation rule out the reverse transition?