Computing the Reverse Transition Matrix

From Forward Transitions to Reverse Transitions

A transition matrix describes the next state given the current one. In a stationary chain, we can also ask: given the current state, what was the preceding state? The answer is generally not obtained by simply transposing the forward transition matrix. It depends on how frequently the chain visits each state, as well as on the forward transition probabilities.

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})$. Write $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$, and use row distributions. Suppose the chain starts in a stationary distribution $\pi$, so $\pi P=\pi$. Then $X_n$ has distribution $\pi$ at every time $n$.

Definition: For states $i,j$ with $\pi(i)>0$, the reverse transition probability from $i$ to $j$ is the conditional probability that the preceding state was $j$, given that the current state is $i$: $$ p^*_{ij}=\mathbb{P}(X_{n-1}=j\mid X_n=i) =\frac{\pi(j)p_{ji}}{\pi(i)},\qquad n\ge1. $$ The matrix $P^*=(p^*_{ij})$, on the state space $S_+=\{i\in S:\pi(i)>0\}$, is called the reverse transition matrix.

The order of the indices matters: to move backward from current state $i$ to preceding state $j$, the forward transition being used is $j$ to $i$, namely $p_{ji}$. The conditional probability is meaningful only when $\pi(i)>0$. States outside $S_+$ are not observed under the stationary law.

Why the Formula Gives a Transition Matrix

Theorem: Let $S$ be finite and let $\pi$ be a stationary distribution for $P$. For each $i\in S_+$, the values $p^*_{ij}=\pi(j)p_{ji}/\pi(i)$, $j\in S_+$, are nonnegative and sum to one. Moreover, a chain started with distribution $\pi$ has, over any finite time interval, the same path probabilities when its states are read backward and the transitions are given by $P^*$.

Proof. Fix $i\in S_+$. Each $p^*_{ij}$ is nonnegative because $\pi(j)$, $p_{ji}$, and $\pi(i)$ are nonnegative, with $\pi(i)>0$. By stationarity, the $i$-th component of $\pi P=\pi$ is $\sum_{j\in S}\pi(j)p_{ji}=\pi(i)$. Dividing by $\pi(i)$ gives $\sum_{j\in S}p^*_{ij}=1$. Terms with $j\notin S_+$ vanish. Thus the reverse row is stochastic.

To verify the path statement, first note that $S_+$ is closed under forward transitions: if $\pi(i)>0$ and $\pi(k)=0$, then $0=\pi(k)=\sum_\ell\pi(\ell)p_{\ell k}$. Since every summand is nonnegative, $p_{ik}=0$. Thus a chain started with distribution $\pi$ stays in $S_+$ with probability one. Consider any path $x_0,\ldots,x_m$ in $S_+$. Its forward probability is $\pi(x_0)\prod_{\ell=0}^{m-1}p_{x_\ell x_{\ell+1}}$. The probability of the reversed path $x_m,\ldots,x_0$, under initial distribution $\pi$ and matrix $P^*$, is $$ \pi(x_m)\prod_{\ell=0}^{m-1} \frac{\pi(x_\ell)p_{x_\ell x_{\ell+1}}}{\pi(x_{\ell+1})} =\pi(x_0)\prod_{\ell=0}^{m-1}p_{x_\ell x_{\ell+1}}. $$ The equality follows by cancellation of the successive positive factors $\pi(x_1),\ldots,\pi(x_m)$. The path probabilities agree, including when a forward transition in the product is zero. This proves the claim for every finite path. $\square$

The formula also shows why stationarity is essential: it supplies the distribution of the state being conditioned on and the normalization that makes each reverse row sum to one. The reverse matrix describes conditional transitions under the stationary law; it is not, in general, the transpose of $P$.

Computing the Reverse Matrix

Find the stationary distribution.
Solve $\pi P=\pi$ together with $\sum_i\pi(i)=1$, and verify both conditions.

Identify the usable states.
Restrict the reverse matrix to $S_+=\{i:\pi(i)>0\}$, since the formula divides by $\pi(i)$.

Compute each entry with reversed indices.
For reverse row $i$, calculate $p^*_{ij}=\pi(j)p_{ji}/\pi(i)$ for every $j$.

Check the result.
Verify nonnegativity and that each reverse row sums to one. A useful further check is $\pi P^*=\pi$.

Worked Example: A Two-State Chain

Take $S=\{1,2\}$ and $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac12&\tfrac12\end{bmatrix}. $$ The first row sums to $\tfrac34+\tfrac14=1$, and the second sums to $\tfrac12+\tfrac12=1$. Find $\pi$ and $P^*$.

Write $\pi=(a,1-a)$. The first coordinate of $\pi P=\pi$ requires $$ a=\tfrac34a+\tfrac12(1-a)=\tfrac14a+\tfrac12. $$ Therefore $\tfrac34a=\tfrac12$, so $a=\tfrac23$ and $\pi=(\tfrac23,\tfrac13)$. Check the stationary equation directly: $$ \pi P=\left(\tfrac23\cdot\tfrac34+\tfrac13\cdot\tfrac12,\ \tfrac23\cdot\tfrac14+\tfrac13\cdot\tfrac12\right) =\left(\tfrac12+\tfrac16,\tfrac16+\tfrac16\right) =\left(\tfrac23,\tfrac13\right). $$

Now use $p^*_{ij}=\pi(j)p_{ji}/\pi(i)$. For reverse row 1, $$ p^*_{11}=\frac{\tfrac23\cdot\tfrac34}{\tfrac23}=\tfrac34,\qquad p^*_{12}=\frac{\tfrac13\cdot\tfrac12}{\tfrac23}=\tfrac14. $$ For reverse row 2, $$ p^*_{21}=\frac{\tfrac23\cdot\tfrac14}{\tfrac13}=\tfrac12,\qquad p^*_{22}=\frac{\tfrac13\cdot\tfrac12}{\tfrac13}=\tfrac12. $$ Thus $P^*=P$; both reverse rows sum to one. This equality is a feature of this two-state example, not a general rule for reversing a chain.

Worked Example: Reversing a Three-State Cycle

Let $S=\{1,2,3\}$ and $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac12&0&\tfrac12 \end{bmatrix}. $$ Each row sums to $\tfrac12+\tfrac12=1$. Each column also sums to $1$, so the uniform distribution $\pi=(\tfrac13,\tfrac13,\tfrac13)$ is stationary. In detail, each coordinate of $\pi P$ is $\tfrac13$ times the corresponding column sum, hence $\pi P=(\tfrac13,\tfrac13,\tfrac13)$; the entries of $\pi$ sum to one.

Since $\pi(i)=\pi(j)=\tfrac13$, the reverse formula reduces in this example to $p^*_{ij}=p_{ji}$. The rows are $$ P^*=\begin{bmatrix} \tfrac12&0&\tfrac12\\ \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$ For example, $p^*_{13}=\pi(3)p_{31}/\pi(1)=(\tfrac13\cdot\tfrac12)/(\tfrac13)=\tfrac12$, while $p^*_{12}=\pi(2)p_{21}/\pi(1)=0$. Each row has two entries equal to $\tfrac12$ and one zero, so each sums to one. In forward time the cycle moves from 1 to 2 to 3 to 1; in reverse time its direction is reversed.

As a stationarity check for the reverse chain, its columns also sum to one, so $\pi P^*=(\tfrac13,\tfrac13,\tfrac13)=\pi$. The path $1,2$ has forward probability $\pi(1)p_{12}=\tfrac16$; read backward, its probability is $\pi(2)p^*_{21}=\tfrac13\cdot\tfrac12=\tfrac16$, in agreement with the path calculation in the theorem.

Zero-Mass States and an Indexing Pitfall

If $\pi(i)=0$, conditioning on $X_n=i$ under the stationary law is not defined, and division by $\pi(i)$ is not allowed. Such a state is outside the stationary chain’s state space for purposes of reversal. In particular, there cannot be a positive-probability forward transition from a positive-mass state into a zero-mass state: stationarity and nonnegativity would contradict $\pi(k)=0$. This does not mean the original transition matrix has no such states; it means the stationary reverse matrix is defined on $S_+$.

Worked Example: Restricting to Positive Stationary Mass

Consider $$ P=\begin{bmatrix}1&0\\ \tfrac12&\tfrac12\end{bmatrix}. $$ The rows sum to $1$ and $\tfrac12+\tfrac12=1$. The distribution $\pi=(1,0)$ is stationary, since $\pi P=(1,0)$, and its entries sum to one. Here $S_+=\{1\}$. The reverse probability from state 1 to state 1 is $p^*_{11}=\pi(1)p_{11}/\pi(1)=1$, so the reverse matrix on the stationary support is the one-state matrix $[1]$. There is no reverse row for state 2: its stationary mass is zero, so the conditional probability given $X_n=2$ is not defined under this stationary law.

Common mistake: using $p_{ij}$ where $p_{ji}$ is required. In the next calculation, the stationary distribution is $\pi=(\tfrac4{15},\tfrac15,\tfrac8{15})$ and row 1 of the forward matrix is $(\tfrac12,\tfrac12,0)$. If one incorrectly substitutes $p_{ij}$ into the reverse formula, the proposed row 1 becomes $$ \left( \frac{\pi(1)p_{11}}{\pi(1)}, \frac{\pi(2)p_{12}}{\pi(1)}, \frac{\pi(3)p_{13}}{\pi(1)} \right) =\left(\tfrac12,\tfrac38,0\right). $$ Its sum is $\tfrac12+\tfrac38=\tfrac78$, so it is not a transition row. The correct formula uses $p_{ji}$. For instance, if $p_{21}=0$ and $p_{31}=\tfrac14$, the correct reverse row is $$ \left( \frac{\pi(1)p_{11}}{\pi(1)}, \frac{\pi(2)p_{21}}{\pi(1)}, \frac{\pi(3)p_{31}}{\pi(1)} \right) =\left(\tfrac12,0,\tfrac12\right), $$ which sums to one. A row-sum check often exposes an index error, but the indices must still be derived from the conditional probability rather than guessed from that check.

Worked Example: Full Reverse Matrix and Index Check

Use the forward matrix $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac13&\tfrac23\\ \tfrac14&0&\tfrac34 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12=1$, $0+\tfrac13+\tfrac23=1$, and $\tfrac14+0+\tfrac34=1$. We verify that $\pi=(\tfrac4{15},\tfrac15,\tfrac8{15})$ is stationary. Its first coordinate after multiplication is $$ \tfrac4{15}\cdot\tfrac12+\tfrac15\cdot0+\tfrac8{15}\cdot\tfrac14 =\tfrac2{15}+\tfrac2{15}=\tfrac4{15}. $$ The second is $$ \tfrac4{15}\cdot\tfrac12+\tfrac15\cdot\tfrac13+\tfrac8{15}\cdot0 =\tfrac2{15}+\tfrac1{15}=\tfrac15, $$ and the third is $$ \tfrac4{15}\cdot0+\tfrac15\cdot\tfrac23+\tfrac8{15}\cdot\tfrac34 =\tfrac2{15}+\tfrac6{15}=\tfrac8{15}. $$ The proposed stationary masses sum to $\tfrac4{15}+\tfrac3{15}+\tfrac8{15}=1$.

All three masses are positive. Applying the reverse formula row by row gives $$ \begin{aligned} p^*_{1,\cdot} &=\left(\frac{\tfrac4{15}\cdot\tfrac12}{\tfrac4{15}}, \frac{\tfrac15\cdot0}{\tfrac4{15}}, \frac{\tfrac8{15}\cdot\tfrac14}{\tfrac4{15}}\right) =(\tfrac12,0,\tfrac12),\\ p^*_{2,\cdot} &=\left(\frac{\tfrac4{15}\cdot\tfrac12}{\tfrac15}, \frac{\tfrac15\cdot\tfrac13}{\tfrac15}, \frac{\tfrac8{15}\cdot0}{\tfrac15}\right) =(\tfrac23,\tfrac13,0),\\ p^*_{3,\cdot} &=\left(\frac{\tfrac4{15}\cdot0}{\tfrac8{15}}, \frac{\tfrac15\cdot\tfrac23}{\tfrac8{15}}, \frac{\tfrac8{15}\cdot\tfrac34}{\tfrac8{15}}\right) =(0,\tfrac14,\tfrac34). \end{aligned} $$ The row sums are $\tfrac12+0+\tfrac12=1$, $\tfrac23+\tfrac13+0=1$, and $0+\tfrac14+\tfrac34=1$. As an additional check, $\pi P^*$ has first coordinate $\tfrac4{15}\cdot\tfrac12+\tfrac15\cdot\tfrac23+\tfrac8{15}\cdot0=\tfrac2{15}+\tfrac2{15}=\tfrac4{15}$. Its second is $\tfrac4{15}\cdot0+\tfrac15\cdot\tfrac13+\tfrac8{15}\cdot\tfrac14=\tfrac1{15}+\tfrac2{15}=\tfrac15$, and its third is $\tfrac4{15}\cdot\tfrac12+\tfrac15\cdot0+\tfrac8{15}\cdot\tfrac34=\tfrac2{15}+\tfrac6{15}=\tfrac8{15}$. Thus $\pi P^*=\pi$, as required.

Using the Reverse Matrix Correctly

The reverse matrix answers a conditional question under a stationary distribution. It should not be interpreted as the probabilities of moving backward for a chain with an arbitrary initial distribution. Nor should it be calculated by transposing $P$ unless the stationary probabilities make that result valid. The reliable procedure is to check stationarity, identify positive-mass states, use the preceding-to-current forward entry $p_{ji}$, and then verify each reverse row.

Check Your Understanding

For each question, pay attention to which state is current and which is preceding.

For a stationary chain, derive $p^*_{ij}$ by writing the joint probability of $X_{n-1}=j$ and $X_n=i$, then conditioning on $X_n=i$.
Why does stationarity imply that every reverse row indexed by $i\in S_+$ sums to one?
For the three-state cycle example, compute $p^*_{32}$ directly from the formula and check it against the displayed reverse matrix.
What does $\pi(i)=0$ imply about whether the reverse conditional probabilities given $X_n=i$ are defined?
In the full three-state example, identify the incorrect row-1 entry obtained by using $p_{12}$ instead of $p_{21}$, and explain why the resulting row cannot be a transition row.