What Does Reversing Twice Recover?
Time reversal asks what transition rule describes a stationary chain when its direction of time is read backward. Reversing that rule again ought to restore the forward transitions, but the claim needs care: the reverse transition formula divides by stationary probabilities. If some states have stationary probability zero, the formula is not defined there, and the original chain’s transition rows from those states cannot be inferred from a stationary trajectory.
Let \((X_n)_{n\ge 0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic, so \(\sum_{j\in S}p_{ij}=1\) for each \(i\). Suppose the initial distribution is the stationary row vector \(\pi\), meaning \(\pi_i\ge 0\), \(\sum_{i\in S}\pi_i=1\), and \(\pi P=\pi\). Define its positive-mass support by \(C=\{i\in S:\pi_i>0\}\).
The formula comes from the stationary joint probability \(\mathbb{P}(X_{n-1}=j,X_n=i)=\pi_jp_{ji}\): dividing by \(\mathbb{P}(X_n=i)=\pi_i\) gives the conditional probability. In a stationary chain, the reversed finite path probabilities factor according to these transitions, so this rule gives the transition matrix of the chain read backward on states in \(C\). States outside \(C\) occur with probability zero at each fixed time under the stationary law.
The Support Must Be Checked First
A basic fact makes the reverse matrix a genuine transition matrix on \(C\): a state with positive stationary probability cannot send positive probability to a state with zero stationary probability. This fact also ensures that restricting each forward row to \(C\) does not remove any of its probability mass.
Proof. Fix \(j\notin C\). Then \(\pi_j=0\), and stationarity gives \(\pi_j=\sum_{i\in S}\pi_i p_{ij}\). Every summand is nonnegative. Therefore, for each \(i\in C\), the summand \(\pi_i p_{ij}\) must be zero. Since \(\pi_i>0\), it follows that \(p_{ij}=0\). Thus, for \(i\in C\), \(\sum_{j\in C}p_{ij}=\sum_{j\in S}p_{ij}=1\), because all terms outside \(C\) are zero and the full row sums to one. \(\square\)
This support argument is essential when checking stationarity of the reversed chain. The reverse formula is defined for starting states \(i\in C\), so sums over its possible next states must be restricted to states where the formula is defined.
Proof. For \(i\in C\), the row sum of \(\widehat P\), with next states restricted to \(C\), is \(\sum_{j\in C}\widehat p_{ij}=\sum_{j\in C}\pi_jp_{ji}/\pi_i\). The numerator is \((\pi P)_i=\pi_i\); terms with \(j\notin C\) vanish because \(\pi_j=0\). Hence the row sum is one.
Next, for \(i\in C\), the \(i\)-th coordinate of \(\pi\widehat P\), calculated on \(C\), is \(\sum_{j\in C}\pi_j\widehat p_{ji} =\sum_{j\in C}\pi_j(\pi_i p_{ij}/\pi_j) =\pi_i\sum_{j\in C}p_{ij} =\pi_i\). Every denominator \(\pi_j\) in this calculation is positive because the sum is over \(C\). The last equality follows from the lemma, which shows that a row starting in \(C\) has all its mass in \(C\). Thus \(\pi\) restricted to \(C\) is stationary for \(\widehat P\).
For \(i,j\in C\), reverse once more using this stationary distribution: \(\widehat{\widehat p}_{ij}=\pi_j\widehat p_{ji}/\pi_i\). Substituting the first reversal formula gives \(\widehat{\widehat p}_{ij}=(\pi_j/\pi_i)(\pi_i p_{ij}/\pi_j)=p_{ij}\). All divisions are valid since both states lie in \(C\). This proves the claim on \(C\); if \(C=S\), it proves equality on the whole state space. \(\square\)
Worked Calculations
Worked Example: A Uniform Stationary Distribution and Zero Edges
Consider the chain on \(S=\{1,2,3\}\) with \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\\\tfrac12&0&\tfrac12\end{bmatrix}\). Every row sums to one: the three row sums are \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(\tfrac12+0+\tfrac12=1\). Each column also sums to one, so \(\pi=(\tfrac13,\tfrac13,\tfrac13)\) is stationary: each coordinate of \(\pi P\) is \(\tfrac13\). In particular, all states belong to \(C\), even though some transitions have probability zero.
For every \(i,j\), the reverse formula reduces to \(\widehat p_{ij}=p_{ji}\). Therefore the reversed matrix is \(\widehat P=\begin{bmatrix}\tfrac12&0&\tfrac12\\\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\end{bmatrix}\). Its rows sum to one: each has entries \(\tfrac12,0,\tfrac12\) in some order. The zero entries have not been replaced by undefined expressions: all denominators are \(\tfrac13\), and an entry is zero precisely when the corresponding \(p_{ji}\) is zero.
Reversing again transposes this matrix once more, giving \(\widehat{\widehat P}=\begin{bmatrix}\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\\\tfrac12&0&\tfrac12\end{bmatrix}=P\). The equality can also be checked entrywise: \(\widehat{\widehat p}_{ij}=\pi_j\widehat p_{ji}/\pi_i=(\tfrac13)\widehat p_{ji}/(\tfrac13)=\widehat p_{ji}=p_{ij}\). Thus zero transition edges cause no problem when stationary probabilities are positive.
Worked Example: A Nonuniform Stationary Distribution
Take \(P=\begin{bmatrix}\tfrac56&\tfrac16&0\\0&\tfrac34&\tfrac14\\\tfrac12&0&\tfrac12\end{bmatrix}\). The row sums are \(\tfrac56+\tfrac16+0=1\), \(0+\tfrac34+\tfrac14=1\), and \(\tfrac12+0+\tfrac12=1\). Set \(\pi=(\tfrac12,\tfrac13,\tfrac16)\), whose entries sum to \(\tfrac12+\tfrac13+\tfrac16=1\). Check stationarity coordinate by coordinate: \((\pi P)_1=\tfrac12\cdot\tfrac56+\tfrac13\cdot0+\tfrac16\cdot\tfrac12=\tfrac5{12}+\tfrac1{12}=\tfrac12\); \((\pi P)_2=\tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac34+\tfrac16\cdot0=\tfrac1{12}+\tfrac14=\tfrac13\); and \((\pi P)_3=\tfrac12\cdot0+\tfrac13\cdot\tfrac14+\tfrac16\cdot\tfrac12=\tfrac1{12}+\tfrac1{12}=\tfrac16\).
All three states have positive stationary mass. Compute each row of the reverse matrix. From state 1, the entries are \(\widehat p_{11}=(\tfrac12\cdot\tfrac56)/(\tfrac12)=\tfrac56\), \(\widehat p_{12}=(\tfrac13\cdot0)/(\tfrac12)=0\), and \(\widehat p_{13}=(\tfrac16\cdot\tfrac12)/(\tfrac12)=\tfrac16\). From state 2, they are \(\widehat p_{21}=(\tfrac12\cdot\tfrac16)/(\tfrac13)=\tfrac14\), \(\widehat p_{22}=(\tfrac13\cdot\tfrac34)/(\tfrac13)=\tfrac34\), and \(\widehat p_{23}=(\tfrac16\cdot0)/(\tfrac13)=0\). From state 3, they are \(\widehat p_{31}=(\tfrac12\cdot0)/(\tfrac16)=0\), \(\widehat p_{32}=(\tfrac13\cdot\tfrac14)/(\tfrac16)=\tfrac12\), and \(\widehat p_{33}=(\tfrac16\cdot\tfrac12)/(\tfrac16)=\tfrac12\).
Hence \(\widehat P=\begin{bmatrix}\tfrac56&0&\tfrac16\\\tfrac14&\tfrac34&0\\0&\tfrac12&\tfrac12\end{bmatrix}\). The row sums are \(\tfrac56+0+\tfrac16=1\), \(\tfrac14+\tfrac34+0=1\), and \(0+\tfrac12+\tfrac12=1\). Reversing this matrix gives, for example, \(\widehat{\widehat p}_{12}=(\tfrac13\cdot\tfrac14)/(\tfrac12)=\tfrac16=p_{12}\), while \(\widehat{\widehat p}_{31}=(\tfrac12\cdot\tfrac16)/(\tfrac16)=\tfrac12=p_{31}\). In general, substitution yields \(\widehat{\widehat p}_{ij}=p_{ij}\) for all nine entries. These checks include entries that were zero: for instance \(\widehat{\widehat p}_{13}=(\tfrac16\cdot0)/(\tfrac12)=0=p_{13}\).
Worked Example: A Zero-Mass State and an Unrecoverable Row
Let \(S=\{a,b,c\}\) and first take \(P=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\), in the order \(a,b,c\). Each row sums to one. The distribution \(\pi=(\tfrac12,\tfrac12,0)\) is stationary: \(\pi P=(\tfrac12,\tfrac12,0)\). Thus \(C=\{a,b\}\). For \(i\in C\), the reverse formula is defined, and its two rows on \(C\) give \(\widehat P_C=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Reversing this two-state matrix again gives the same matrix, so the original transitions within \(C\) are recovered.
The formula does not define a row for \(c\), because it would require division by \(\pi_c=0\). This is not a zero transition probability; it is an undefined conditional probability, since under the stationary law the event \(X_n=c\) has probability zero. To see why the missing row cannot be recovered, change only the row from \(c\) and consider \(P'=\begin{bmatrix}0&1&0\\1&0&0\\1&0&0\end{bmatrix}\). Its rows still sum to one, and \((\tfrac12,\tfrac12,0)P'=(\tfrac12,\tfrac12,0)\). Both chains therefore have the same stationary law and the same reverse matrix on \(C\), although their transition rows from \(c\) differ. Reversing twice recovers the original matrix on the support, not an arbitrary row belonging to a zero-mass state.
A Common Mistake and Its Correction
A tempting but invalid stationarity calculation is to write \(\sum_{j\in S}\pi_j\widehat p_{ji}\) without first restricting to the states where \(\widehat p_{ji}\) is defined. In the preceding example, the term with \(j=c\) would involve \(\widehat p_{ci}=\pi_i p_{ic}/\pi_c\), whose denominator is zero. It is not legitimate to treat this term as zero just because \(\pi_c=0\): the product \(0\cdot\widehat p_{ci}\) is not defined when \(\widehat p_{ci}\) is undefined.
The correction is to work on \(C\). First use stationarity and nonnegativity to prove \(p_{ij}=0\) whenever \(i\in C\) and \(j\notin C\). Then sum only over \(j\in C\), where every reverse transition is defined and the restricted forward row still sums to one. Only after those steps is the reversed stationarity identity valid.
Keep the two kinds of zero distinct. A zero entry \(p_{ij}=0\) between positive-mass states simply gives a zero reverse entry in the corresponding reversed direction. A zero stationary mass \(\pi_i=0\), by contrast, prevents definition of the reverse row from \(i\) and means the stationary chain never occupies that state. The involution statement is therefore exact on \(C\); it is a statement about all of \(S\) only when \(\pi\) is positive at every state.
Check Your Understanding
For each question, keep the state space on which the reverse formula is defined explicit.
- Why does \(\pi_j=0\) imply \(p_{ij}=0\) for every \(i\) with \(\pi_i>0\)? State the nonnegativity argument.
- If \(\pi_i>0\) for all states, express \(\widehat{\widehat p}_{ij}\) using the reverse formula and simplify it to \(p_{ij}\).
- For a chain with \(\pi=(\tfrac12,\tfrac12,0)\), explain why the reverse transition row from the third state is undefined, rather than automatically a row of zeros.
- In the nonuniform example, verify the reverse row sum for state 2 and identify which forward transition makes \(\widehat p_{23}=0\).
- Can two different transition matrices have the same stationary distribution and the same reversed matrix on its support? Explain using the zero-mass-state example.