Recursive Equations for n-Step Probabilities

Two Directions for Computing n-Step Probabilities

An n-step transition probability can be computed by splitting the n steps at an intermediate time. When one part of the split is a single step, the Chapman–Kolmogorov equation gives a recursion: either propagate probabilities forward from the starting state, or work backward from the target state. The two approaches use the same transition matrix, but can make different calculations more convenient when many entries are zero or only one target matters.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal F,\mathbb P)$. Its natural filtration is $\mathcal F_n=\sigma(X_0,\ldots,X_n)$. Write $P=(p_{ij})$ for its row-stochastic transition matrix, so $p_{ij}=\mathbb P(X_{n+1}=j\mid X_n=i)$, and each row sums to $1$. The n-step probability is $p_{ij}^{(n)}=\mathbb P_i(X_n=j)$, where $\mathbb P_i$ denotes the chain started at $i$. Set $P^{(0)}=I$, so $p_{ij}^{(0)}=1$ if $i=j$ and $0$ otherwise.

The Chapman–Kolmogorov equation states that, for nonnegative integers $r,s$,

p_{ij}^{(r+s)}=\sum_{k\in S}p_{ik}^{(r)}p_{kj}^{(s)}.

It sums over the state $k$ occupied after the first $r$ steps. The summands are nonnegative, so the sum is well-defined for a countable state space; as a probability, it is at most $1$.

Theorem (Forward and backward recursions): For every $n\ge0$ and $i,j\in S$, $$ p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj} \qquad\text{and}\qquad p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}p_{kj}^{(n)}. $$ The first is the forward recursion; the second is the backward recursion.

Proof. For the forward recursion, apply Chapman–Kolmogorov with $r=n$ and $s=1$. Since $p_{kj}^{(1)}=p_{kj}$, this gives $p_{ij}^{(n+1)}=\sum_k p_{ik}^{(n)}p_{kj}$. For the backward recursion, take $r=1$ and $s=n$; since $p_{ik}^{(1)}=p_{ik}$, the result is $p_{ij}^{(n+1)}=\sum_k p_{ik}p_{kj}^{(n)}$. These substitutions also hold for $n=0$, by the definition of $P^{(0)}$. $\square$

In matrix notation, the same identities are $P^{(n+1)}=P^{(n)}P$ and $P^{(n+1)}=PP^{(n)}$. For a fixed starting state $i$, the forward recursion updates the row of probabilities across all destination states. For a fixed target state $j$, the backward recursion updates the probability of reaching $j$ from each possible starting state. They are identities for a time-homogeneous chain, not different assumptions about the chain.

Recursive computation rule: For a fixed target $j$, define $f_n(i)=p_{ij}^{(n)}$. Then $f_0(i)=\mathbf 1_{\{i=j\}}$ and $f_{n+1}(i)=\sum_k p_{ik}f_n(k)$. This determines $f_n$ uniquely: once $f_n$ is known at every state, the displayed sum gives exactly one value for each $f_{n+1}(i)$.

Proof. The initial values follow from $P^{(0)}=I$. Suppose the values $f_n(i)$ are specified for all $i$. The backward recursion requires $f_{n+1}(i)$ to equal the sum $\sum_k p_{ik}f_n(k)$, so it specifies at most one value at each state. Defining $f_{n+1}$ by that sum gives values satisfying the recursion. Induction from $n=0$ therefore gives a unique sequence of functions, and the backward recursion theorem shows that this sequence is $f_n(i)=p_{ij}^{(n)}$. $\square$

Working Forward from a Starting State

Write $\mu_n$ for the distribution of $X_n$, as a row vector. If $\mu_0$ is the initial distribution, the forward recursion gives $\mu_{n+1}=\mu_nP$. This updates only the distribution currently needed; it does not require writing out every entry of $P^{(n)}$. Before using a transition matrix, check that each row sums to $1$, and check that the computed distribution still sums to $1$.

Worked Example: Three Steps to a Target State

On $S=\{1,2,3\}$, let the transition matrix be

P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac13&\tfrac23\\ \tfrac14&0&\tfrac34 \end{bmatrix}.

The row sums are $\tfrac12+\tfrac12+0=1$, $0+\tfrac13+\tfrac23=1$, and $\tfrac14+0+\tfrac34=1$. Starting at state $1$, the one-step distribution is $\mu_1=(\tfrac12,\tfrac12,0)$. Apply the forward recursion to find the two-step distribution:

\begin{aligned} p_{11}^{(2)}&=\tfrac12\cdot\tfrac12+\tfrac12\cdot0+0\cdot\tfrac14=\tfrac14,\\ p_{12}^{(2)}&=\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac13+0\cdot0=\tfrac14+\tfrac16=\tfrac5{12},\\ p_{13}^{(2)}&=\tfrac12\cdot0+\tfrac12\cdot\tfrac23+0\cdot\tfrac34=\tfrac13. \end{aligned}

The entries sum to $\tfrac14+\tfrac5{12}+\tfrac13=\tfrac3{12}+\tfrac5{12}+\tfrac4{12}=1$. One more forward update gives the probability of being at state $3$ after three steps:

p_{13}^{(3)} =\tfrac14\cdot0+\tfrac5{12}\cdot\tfrac23+\tfrac13\cdot\tfrac34 =\tfrac5{18}+\tfrac14 =\tfrac{10}{36}+\tfrac9{36} =\tfrac{19}{36}.

Check using the backward recursion. First compute the two-step probabilities of reaching state $3$ from each possible state: $p_{13}^{(2)}=\tfrac13$, as above; $p_{23}^{(2)}=0\cdot0+\tfrac13\cdot\tfrac23+\tfrac23\cdot\tfrac34=\tfrac29+\tfrac12=\tfrac{13}{18}$; and $p_{33}^{(2)}=\tfrac14\cdot0+0\cdot\tfrac23+\tfrac34\cdot\tfrac34=\tfrac9{16}$. The backward recursion now gives $p_{13}^{(3)}=\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac{13}{18}+0\cdot\tfrac9{16}=\tfrac16+\tfrac{13}{36}=\tfrac{19}{36}$, agreeing with the forward calculation.

Working Backward from a Target State

When the question asks for the probability of reaching one particular state after n steps, it can be efficient to keep just the values $f_n(i)=p_{ij}^{(n)}$ for that target $j$. Start at time $0$, when the probability is $1$ if the starting state is already $j$ and $0$ otherwise. Each backward update combines the current values using the one-step probabilities out of the starting state. In a sparse transition matrix, each update may use only a few terms.

Worked Example: A Four-State Chain in Three Steps

Let $S=\{0,1,2,3\}$, and use the following transition probabilities: from $0$, move to $0$ or $1$ with probability $\tfrac12$ each; from $1$, move to $0,1,2$ with probabilities $\tfrac14,\tfrac12,\tfrac14$; from $2$, move to $1,2,3$ with probability $\tfrac13$ each; from $3$, move to $2$ or $3$ with probability $\tfrac12$ each. The rows, in state order $0,1,2,3$, sum respectively to $\tfrac12+\tfrac12=1$, $\tfrac14+\tfrac12+\tfrac14=1$, $\tfrac13+\tfrac13+\tfrac13=1$, and $\tfrac12+\tfrac12=1$.

Find $p_{03}^{(3)}$. For target $3$, the time-zero values are $f_0=(0,0,0,1)$. One backward update gives $f_1=(0,0,\tfrac13,\tfrac12)$, since only states $2$ and $3$ can move to $3$ in one step. A second update gives the two values needed from states $0$ and $1$:

f_2(0)=\tfrac12 f_1(0)+\tfrac12 f_1(1)=0,\qquad f_2(1)=\tfrac14 f_1(0)+\tfrac12 f_1(1)+\tfrac14 f_1(2)=\tfrac1{12}.

Thus $p_{03}^{(3)}=f_3(0)=\tfrac12 f_2(0)+\tfrac12 f_2(1)=0+\tfrac1{24}=\tfrac1{24}$. Only the values needed for the requested starting state had to be carried through the final update.

Check using forward distributions. Starting at $0$, the distributions after one and two steps are $\mu_1=(\tfrac12,\tfrac12,0,0)$ and $\mu_2=(\tfrac38,\tfrac12,\tfrac18,0)$. For the second distribution, the entries are $ \tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac14=\tfrac38$, $\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12=\tfrac12$, $\tfrac12\cdot0+\tfrac12\cdot\tfrac14=\tfrac18$, and $0$; they sum to $1$. Its next-step probability at state $3$ is $\tfrac38\cdot0+\tfrac12\cdot0+\tfrac18\cdot\tfrac13+0\cdot\tfrac12=\tfrac1{24}$, as found backward.

Worked Example: Repeated Updates with an Absorbing Target

Consider states $A,B,C$, with transitions $A\to B$ with probability $1$, $B\to A$ or $C$ with probability $\tfrac12$ each, and $C\to C$ with probability $1$. The row sums are $1$, $\tfrac12+\tfrac12=1$, and $1$. Compute the probability of being at $C$ after four steps when starting at $A$.

For target $C$, $f_0(A)=0$, $f_0(B)=0$, and $f_0(C)=1$. The backward recursion gives, step by step,

\begin{aligned} f_1(A)&=f_0(B)=0,& f_1(B)&=\tfrac12f_0(A)+\tfrac12f_0(C)=\tfrac12,& f_1(C)&=1,\\ f_2(A)&=f_1(B)=\tfrac12,& f_2(B)&=\tfrac12f_1(A)+\tfrac12f_1(C)=\tfrac12,& f_2(C)&=1,\\ f_3(A)&=f_2(B)=\tfrac12,& f_3(B)&=\tfrac12f_2(A)+\tfrac12f_2(C)=\tfrac34,& f_3(C)&=1,\\ f_4(A)&=f_3(B)=\tfrac34. \end{aligned}

Therefore $p_{AC}^{(4)}=\tfrac34$. The calculation uses only the backward values for states that can be reached in one step from the current state.

Check using forward updates. The successive distributions from $A$ are $\mu_1=(0,1,0)$, $\mu_2=(\tfrac12,0,\tfrac12)$, $\mu_3=(0,\tfrac12,\tfrac12)$, and $\mu_4=(\tfrac14,0,\tfrac34)$. Each sums to $1$; in particular, the probability at $C$ after four steps is $\tfrac34$, matching the backward result.

Choosing a Recursion and Avoiding a Pitfall

Use the forward recursion when the distribution from a specified initial state is needed across several states or times. Use the backward recursion when one target is fixed and the question concerns probabilities from selected starting states. Either identity is valid; choosing one does not change the probability being calculated. For a finite state space, these are ordinary matrix-product updates. For a countable state space, the same equations hold with sums over all states, though a practical calculation may require exploiting structure to handle those sums.

Common mistake: omitting an intermediate state. In the three-state example, a mistaken calculation of $p_{12}^{(2)}$ might keep only the route through state $1$, giving $p_{11}p_{12}=\tfrac12\cdot\tfrac12=\tfrac14$. That is incomplete: the chain can also be at state $2$ after one step and remain there. The forward recursion includes both intermediate states with nonzero contributions:

p_{12}^{(2)} =p_{11}p_{12}+p_{12}p_{22}+p_{13}p_{32} =\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac13+0\cdot0 =\tfrac14+\tfrac16 =\tfrac5{12}.

The incorrect value $\tfrac14$ is not repaired by renormalizing the row: the missing probability belongs specifically to the transition from state $2$ to state $2$. The reliable procedure is to sum over every possible intermediate state, even when some terms are zero, and then check that the resulting distribution has total probability $1$.

Check Your Understanding

For each question, identify which recursion is useful and show the intermediate-state terms needed for your calculation.

Write the forward and backward recursions for $p_{ij}^{(n+1)}$, and state which one fixes the starting state and which one fixes the target.
For the three-state matrix in the first worked example, compute $p_{11}^{(2)}$ using the backward recursion.
For the four-state chain, use the backward recursion to find $p_{13}^{(2)}$.
Why is it necessary to include every possible intermediate state in a Chapman–Kolmogorov sum, including states whose contribution is zero?
Explain how a forward calculation can be checked by verifying that the updated distribution sums to $1$.

Recursive Equations for n-Step Probabilities

What You'll Learn