Why Reversibility Persists Over Several Steps
A reversible chain has balanced probability flow across each pair of states in one step. A natural question is whether the same balance holds when we look only every two steps, every three steps, or every \(n\) steps. This matters whenever a chain is observed at a coarser time scale: the multi-step transition probabilities still describe a reversible chain with the same reference distribution. The result follows from detailed balance and matrix multiplication; neither aperiodicity nor irreducibility is required.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Its transition matrix is \(P=(p_{ij})\), with \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row sums to \(1\). Write \(P^n=(p_{ij}^{(n)})\) for the \(n\)-step transition matrix; \(P^0\) is the identity matrix.
The main result says that these equalities continue to hold for every number of steps. Its proof uses induction and sums over the intermediate state. The key is to apply detailed balance first to the \(n\)-step transition and then to a one-step transition.
Proof. We prove the assertion by induction on \(n\). For \(n=0\), \(p_{ij}^{(0)}\) is \(1\) when \(i=j\) and \(0\) otherwise. Both sides of the claimed equality are therefore equal: when \(i=j\) they are \(\pi_i\), and when \(i\ne j\) they are \(0\). For \(n=1\), the assertion is the assumed detailed-balance equation. Now suppose it holds for some \(n\ge1\). By matrix multiplication and the induction hypothesis, for any \(i,j\in S\), $$ \begin{aligned} \pi_i p_{ij}^{(n+1)} &=\pi_i\sum_{k\in S}p_{ik}^{(n)}p_{kj}\\ &=\sum_{k\in S}\pi_k p_{ki}^{(n)}p_{kj}\\ &=\sum_{k\in S}\pi_j p_{jk}p_{ki}^{(n)}\\ &=\pi_j\sum_{k\in S}p_{jk}p_{ki}^{(n)} =\pi_j p_{ji}^{(n+1)}. \end{aligned} $$ The second equality uses the induction hypothesis for the pair \(i,k\); the third uses one-step detailed balance for \(k,j\); and the final equality is matrix multiplication for \(P^{n+1}\). Thus the result holds for \(n+1\), completing the induction. \(\square\)
Stationarity and the Scope of the Result
Reversibility is stronger than stationarity: it balances flow separately for each pair of states, whereas stationarity requires only that total incoming probability flow equal the mass at each state. In particular, summing detailed balance over the starting state proves stationarity. The same argument applies to every power.
Proof. Fix \(j\in S\). Since the theorem gives detailed balance for \(P^n\), and each row of \(P^n\) sums to \(1\), $$ \sum_{i\in S}\pi_i p_{ij}^{(n)} =\sum_{i\in S}\pi_j p_{ji}^{(n)} =\pi_j\sum_{i\in S}p_{ji}^{(n)} =\pi_j. $$ This is the \(j\)th coordinate of \(\pi P^n=\pi\). For \(n=0\) the same equality follows from \(P^0=I\). Hence the claimed stationarity holds for every \(n\ge0\). \(\square\)
The proof requires a finite state space so the displayed sums are finite; the same argument applies on a countable state space when the sums are well-defined, since their terms are nonnegative and can be summed. It does not require that \(\pi_i>0\) for every state, that the chain be irreducible, or that it be aperiodic. In particular, reversibility of \(P^n\) is a statement about detailed balance, not a claim that the distribution of \(X_n\) converges to \(\pi\) from every starting state.
Worked Example: Squaring a Three-State Reversible Matrix
Consider \(S=\{1,2,3\}\) and $$ P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}, \qquad \pi=\left(\tfrac14,\tfrac12,\tfrac14\right). $$ Each row sums to \(1\): the row sums are \(\tfrac12+\tfrac12+0=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(0+\tfrac12+\tfrac12=1\). Check detailed balance for the distinct pairs. For \((1,2)\), both flows are \(\tfrac14\cdot\tfrac12=\tfrac18\) and \(\tfrac12\cdot\tfrac14=\tfrac18\). For \((1,3)\), both are \(0\). For \((2,3)\), both are \(\tfrac12\cdot\tfrac14=\tfrac18\) and \(\tfrac14\cdot\tfrac12=\tfrac18\). The diagonal equations hold automatically, so \(\pi\) is reversible.
Compute \(P^2\) by multiplying rows of \(P\) by columns of \(P\). Its first row is \((\tfrac14+\tfrac18,\ \tfrac14+\tfrac14,\ \tfrac18)=(\tfrac38,\tfrac12,\tfrac18)\). Its second row is \((\tfrac18+\tfrac18,\ \tfrac18+\tfrac14+\tfrac18,\ \tfrac18+\tfrac18)=(\tfrac14,\tfrac12,\tfrac14)\). Its third row is \((\tfrac18,\ \tfrac14+\tfrac14,\ \tfrac18+\tfrac14)=(\tfrac18,\tfrac12,\tfrac38)\). Thus $$ P^2= \begin{bmatrix} \tfrac38&\tfrac12&\tfrac18\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac18&\tfrac12&\tfrac38 \end{bmatrix}. $$ The row sums are \(\tfrac38+\tfrac12+\tfrac18=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(\tfrac18+\tfrac12+\tfrac38=1\).
Check detailed balance for \(P^2\). For the three distinct pairs, the two weighted entries are respectively \(\tfrac14\cdot\tfrac12=\tfrac18\) and \(\tfrac12\cdot\tfrac14=\tfrac18\); \(\tfrac14\cdot\tfrac18=\tfrac1{32}\) and \(\tfrac14\cdot\tfrac18=\tfrac1{32}\); and \(\tfrac12\cdot\tfrac14=\tfrac18\) and \(\tfrac14\cdot\tfrac12=\tfrac18\). So the computed matrix directly confirms the theorem for two steps.
Worked Example: Three Steps in a Two-State Chain
Let \(S=\{1,2\}\), with $$ P= \begin{bmatrix} \tfrac34&\tfrac14\\ \tfrac12&\tfrac12 \end{bmatrix}, \qquad \pi=\left(\tfrac23,\tfrac13\right). $$ The row sums are \(\tfrac34+\tfrac14=1\) and \(\tfrac12+\tfrac12=1\). The only distinct-pair balance check is \(\tfrac23\cdot\tfrac14=\tfrac16=\tfrac13\cdot\tfrac12\), so \(\pi\) is reversible.
First multiply to obtain $$ P^2= \begin{bmatrix} \tfrac{11}{16}&\tfrac5{16}\\ \tfrac58&\tfrac38 \end{bmatrix}. $$ For example, the first entry is \(\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac12=\tfrac9{16}+\tfrac18=\tfrac{11}{16}\), and the second is \(\tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac3{16}+\tfrac18=\tfrac5{16}\). The second row entries are \(\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac12=\tfrac38+\tfrac14=\tfrac58\) and \(\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac12=\tfrac18+\tfrac14=\tfrac38\). The row sums are \(\tfrac{11}{16}+\tfrac5{16}=1\) and \(\tfrac58+\tfrac38=1\).
Multiplying once more gives $$ P^3= \begin{bmatrix} \tfrac{43}{64}&\tfrac{21}{64}\\ \tfrac{21}{32}&\tfrac{11}{32} \end{bmatrix}. $$ Indeed, its first row is \((\tfrac{11}{16}\cdot\tfrac34+\tfrac5{16}\cdot\tfrac12,\ \tfrac{11}{16}\cdot\tfrac14+\tfrac5{16}\cdot\tfrac12) =(\tfrac{33}{64}+\tfrac{10}{64},\tfrac{11}{64}+\tfrac{10}{64})\). Its second row is \((\tfrac58\cdot\tfrac34+\tfrac38\cdot\tfrac12,\ \tfrac58\cdot\tfrac14+\tfrac38\cdot\tfrac12) =(\tfrac{15}{32}+\tfrac6{32},\tfrac5{32}+\tfrac6{32})\). The row sums are \(\tfrac{43}{64}+\tfrac{21}{64}=1\) and \(\tfrac{21}{32}+\tfrac{11}{32}=1\). Finally, the two weighted off-diagonal entries agree: \(\tfrac23\cdot\tfrac{21}{64}=\tfrac{42}{192}\) and \(\tfrac13\cdot\tfrac{21}{32}=\tfrac{42}{192}\). This verifies three-step reversibility by direct computation.
Worked Example: A Periodic Chain at Four Steps
Consider the deterministic chain on \(S=\{1,2\}\) that switches states at each step: $$ P= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}, \qquad \pi=\left(\tfrac12,\tfrac12\right). $$ Both rows sum to \(1\), and the off-diagonal detailed-balance quantities are both \(\tfrac12\). Thus \(\pi\) is reversible. Direct multiplication gives \(P^2=I\), so \(P^4=I\). The identity matrix has row sums \(1\); its off-diagonal entries are both \(0\), and its diagonal detailed-balance equations each compare \(\tfrac12\) with itself. Hence \(P^4\) is reversible with respect to \(\pi\). This chain has period \(2\), but that causes no difficulty: the theorem does not assume aperiodicity, nor does it assert convergence of \(P^n\).
A Common Mistake and a Practical Check
A tempting shortcut is to write \(\pi_i p_{ij}^{(2)}=\pi_i\sum_k p_{ik}p_{kj}\) and then interchange the indices in the factors without changing the weights. That is not a valid algebraic operation. For the two-state chain in the preceding example, applying that shortcut to the pair \((1,2)\) would replace the correct quantity \(\pi_1p_{12}^{(2)}=\tfrac23\cdot\tfrac5{16}=\tfrac5{24}\) by \(\pi_1\sum_k p_{k1}p_{k2}\). The latter is \(\tfrac23(\tfrac34\cdot\tfrac14+\tfrac12\cdot\tfrac12)=\tfrac23(\tfrac3{16}+\tfrac4{16})=\tfrac7{24}\), which is not the correct value. The correction is to use detailed balance with its weights: \(\pi_i p_{ik}^{(n)}=\pi_k p_{ki}^{(n)}\), followed by \(\pi_k p_{kj}=\pi_j p_{jk}\). Those are the justified substitutions in the induction proof.
For a finite example, a reliable verification routine is to check that the original rows sum to \(1\), verify one-step detailed balance, compute the desired matrix power, check that its rows still sum to \(1\), and then compare \(\pi_i p_{ij}^{(n)}\) with \(\pi_j p_{ji}^{(n)}\) for each distinct pair. The theorem explains why the final check must succeed when the initial assumptions hold; the computation can still catch arithmetic or indexing errors.
Check Your Understanding
Use detailed balance and the displayed computations to justify your answers.
- In the theorem, which induction step uses reversibility of \(P\), and which uses the induction hypothesis for \(P^n\)?
- Why does summing the detailed-balance equations for \(P^n\) over \(i\) give \(\pi P^n=\pi\)? State which row-sum property is used.
- For the three-state example, verify the detailed-balance equation for the pair \((1,3)\) in \(P^2\).
- Does the theorem require an aperiodic chain? Explain using the two-state switching chain.
- What assumption would be needed before dividing a detailed-balance equation by \(\pi_i\), and why does the theorem’s proof avoid that division?