Tutorials › Stochastic Processes › From Chapman-Kolmogorov to Matrix Powers

Home  /  Tutorials  /  Chapman-Kolmogorov Equations and n-Step Transitions

Chapman-Kolmogorov Equations and n-Step Transitions · Tutorial 111 of 994

From Chapman-Kolmogorov to Matrix Powers

Learn how Chapman–Kolmogorov turns repeated one-step transitions into matrix powers, with careful index conventions and checked examples.

Intermediate 9 min read

What You'll Learn

  • Define n-step transition probabilities, including the zero-step case.
  • Match the intermediate-state sum in Chapman–Kolmogorov to matrix multiplication.
  • Prove by induction that the n-step transition matrix is P raised to the nth power.
  • Use matrix powers to compute exact multistep transition probabilities.
  • Recognize and correct an index-order error in a two-step calculation.

From a Transition Rule to Repeated Transitions

A one-step transition matrix records where a Markov chain can move in a single step. To find the probability of moving from \(i\) to \(j\) in several steps, one must account for every possible state visited between them. The Chapman–Kolmogorov equation does this by summing over an intermediate state. Matrix multiplication performs exactly that sum, which is why powers of the one-step transition matrix encode multiple steps.

Let \((X_n)_{n\ge0}\) be a time-homogeneous 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_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\) for the one-step transition probability, which does not depend on \(n\). The matrix \(P=(p_{ij})\) is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). We use \(\mathbb{P}_i\) for the law of the chain started at state \(i\), so the transition probabilities are defined even if a particular state has probability zero under some other initial distribution.

Definition: For \(n\ge0\), the \(n\)-step transition probability from \(i\) to \(j\) is \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)\). At \(n=0\), \(p_{ij}^{(0)}=\mathbf{1}_{\{i=j\}}\): the chain is at its starting state before making any transitions. Write \(P^{(n)}=(p_{ij}^{(n)})\).

For \(n,m\ge0\), the Chapman–Kolmogorov equation is \(p_{ij}^{(n+m)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}^{(m)}\). The sum ranges over every possible state \(k\) occupied after the first \(n\) steps. In a countable state space it is a sum of nonnegative terms; it is well-defined, and its value is at most \(1\), because it is a probability obtained by conditioning on \(X_n\). For a finite state space, the sum is finite.

Why the Chapman–Kolmogorov Sum Is a Matrix Product

For matrices indexed by \(S\), the row-\(i\), column-\(j\) entry of a product \(AB\) is \((AB)_{ij}=\sum_{k\in S}A_{ik}B_{kj}\), whenever this sum is defined. Thus in the Chapman–Kolmogorov equation the first factor in each summand has indices \(i,k\), and the second has indices \(k,j\). These are precisely the column and row indices that must match in matrix multiplication. In particular, the intermediate state is an index being summed out; it is not the final destination.

Theorem: For every integer \(n\ge0\), the \(n\)-step transition matrix satisfies \(P^{(n)}=P^n\), where \(P^0=I\) and \(I\) is the identity matrix indexed by \(S\).

Proof. We use induction on \(n\). For \(n=0\), the definition gives \(p_{ij}^{(0)}=\mathbf{1}_{\{i=j\}}=I_{ij}\), so \(P^{(0)}=I=P^0\). Now suppose \(P^{(n)}=P^n\). Applying Chapman–Kolmogorov with \(m=1\), for every \(i,j\in S\) we have \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). By the induction hypothesis this is \(\sum_{k\in S}(P^n)_{ik}P_{kj}\), which is the \((i,j)\) entry of \(P^nP=P^{n+1}\). Therefore \(P^{(n+1)}=P^{n+1}\). The base case and induction step establish the assertion for all \(n\ge0\). \(\square\)

This argument also explains the order of the factors: the first \(n\) steps are represented by \(P^n\), followed by one more step represented by \(P\). The formula is not an assertion that probabilities are multiplied without summing. Each product describes one route through an intermediate state; the sum combines the mutually exclusive possibilities for that state.

Corollary (Splitting a run of steps): For integers \(r,s\ge0\), \(P^{(r+s)}=P^{(r)}P^{(s)}\).

Proof. Fix states \(i,j\). The Chapman–Kolmogorov equation gives \(p_{ij}^{(r+s)}=\sum_{k\in S}p_{ik}^{(r)}p_{kj}^{(s)}\). By the definition of matrix multiplication, the right-hand side is the \((i,j)\) entry of \(P^{(r)}P^{(s)}\). Since this holds for every pair \(i,j\), the matrices are equal. The cases \(r=0\) or \(s=0\) are included: the identity matrix leaves the other factor unchanged. \(\square\)

By the theorem, the corollary can also be written \(P^{r+s}=P^rP^s\). Its probabilistic meaning is that a run of \(r+s\) steps may be cut after any \(r\) steps, and the state at the cut is summed over. This is useful when a long transition is easier to compute in shorter blocks.

Worked Matrix Powers

Worked Example: A Two-State Chain Through Three Steps

Consider \(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 to \(\tfrac12+\tfrac12=1\), so the transition matrix is row-stochastic. Compute \(P^{(2)}\) and \(P^{(3)}\).

For the two-step matrix, each entry is a row of \(P\) dotted with a column of \(P\). The four calculations are

$$ \begin{aligned} p_{11}^{(2)}&=\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac12 =\tfrac9{16}+\tfrac2{16}=\tfrac{11}{16},\\ p_{12}^{(2)}&=\tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac12 =\tfrac3{16}+\tfrac2{16}=\tfrac5{16},\\ p_{21}^{(2)}&=\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac12 =\tfrac38+\tfrac14=\tfrac58,\\ p_{22}^{(2)}&=\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac12 =\tfrac18+\tfrac14=\tfrac38. \end{aligned} $$

Thus \(P^{(2)}=\begin{bmatrix}\tfrac{11}{16}&\tfrac5{16}\\[2pt]\tfrac58&\tfrac38\end{bmatrix}\). Its first row sums to \(\tfrac{11}{16}+\tfrac5{16}=1\), and its second to \(\tfrac58+\tfrac38=1\). To find the third power, multiply this matrix by \(P\):

$$ \begin{aligned} p_{11}^{(3)}&=\tfrac{11}{16}\cdot\tfrac34+\tfrac5{16}\cdot\tfrac12 =\tfrac{33}{64}+\tfrac{10}{64}=\tfrac{43}{64},\\ p_{12}^{(3)}&=\tfrac{11}{16}\cdot\tfrac14+\tfrac5{16}\cdot\tfrac12 =\tfrac{11}{64}+\tfrac{10}{64}=\tfrac{21}{64},\\ p_{21}^{(3)}&=\tfrac58\cdot\tfrac34+\tfrac38\cdot\tfrac12 =\tfrac{30}{64}+\tfrac{12}{64}=\tfrac{21}{32},\\ p_{22}^{(3)}&=\tfrac58\cdot\tfrac14+\tfrac38\cdot\tfrac12 =\tfrac{10}{64}+\tfrac{12}{64}=\tfrac{11}{32}. \end{aligned} $$

Therefore \(P^{(3)}=\begin{bmatrix}\tfrac{43}{64}&\tfrac{21}{64}\\[2pt]\tfrac{21}{32}&\tfrac{11}{32}\end{bmatrix}\). The first row sums to \(\tfrac{43}{64}+\tfrac{21}{64}=1\), and the second to \(\tfrac{21}{32}+\tfrac{11}{32}=1\). As a direct check on one entry, \(p_{12}^{(3)}=\tfrac{43}{64}\cdot\tfrac14+\tfrac{21}{64}\cdot\tfrac12=\tfrac{43}{256}+\tfrac{42}{256}=\tfrac{85}{256}\) would not be correct: that calculation mistakenly uses \(P^{(3)}\) as the first factor. The correct check uses \(P^{(2)}\), as above, and gives \(\tfrac{21}{64}\).

Worked Example: Three States and Two-Step Routes

Let \(S=\{1,2,3\}\) and \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\\\tfrac12&0&\tfrac12\end{bmatrix}\). Each row sums to \(1\): the three sums are \(\tfrac12+\tfrac12+0\), \(0+\tfrac12+\tfrac12\), and \(\tfrac12+0+\tfrac12\), respectively. Find \(p_{13}^{(2)}\) and the full matrix \(P^{(2)}\).

To go from \(1\) to \(3\) in two steps, the intermediate state can be \(1,2,\) or \(3\). The three route contributions are \(\tfrac12\cdot0\), \(\tfrac12\cdot\tfrac12\), and \(0\cdot\tfrac12\). Hence \(p_{13}^{(2)}=0+\tfrac14+0=\tfrac14\). For the full matrix, the columns of \(P\) are \((\tfrac12,0,\tfrac12)\), \((\tfrac12,\tfrac12,0)\), and \((0,\tfrac12,\tfrac12)\). Taking each row of \(P\) against these three columns gives

$$ P^{(2)}= \begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac14&\tfrac14&\tfrac12\\ \tfrac12&\tfrac14&\tfrac14 \end{bmatrix}. $$

For example, the second row is obtained from \((0,\tfrac12,\tfrac12)\): its entries are \(0\cdot\tfrac12+\tfrac12\cdot0+\tfrac12\cdot\tfrac12=\tfrac14\), \(0\cdot\tfrac12+\tfrac12\cdot\tfrac12+\tfrac12\cdot0=\tfrac14\), and \(0\cdot0+\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12=\tfrac12\). The row sums of the result are \(\tfrac14+\tfrac12+\tfrac14=1\), \(\tfrac14+\tfrac14+\tfrac12=1\), and \(\tfrac12+\tfrac14+\tfrac14=1\). The selected entry agrees with the direct route calculation: \(p_{13}^{(2)}=\tfrac14\).

Worked Example: A Deterministic Three-State Cycle

Suppose the chain moves from \(1\) to \(2\), from \(2\) to \(3\), and from \(3\) to \(1\), each with probability \(1\). Its transition matrix is \(P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\). Each row has one entry equal to \(1\) and two equal to \(0\), so every row sums to \(1\). Multiplying once gives \(P^{(2)}=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}\): for instance, the first row of \(P\) selects the second row of \(P\), which is \((0,0,1)\), and the other rows select the third and first rows, respectively.

Now multiply \(P^{(2)}P\). The first row \((0,0,1)\) selects the third row of \(P\), giving \((1,0,0)\); the second row \((1,0,0)\) selects the first row, giving \((0,1,0)\); and the third row \((0,1,0)\) selects the second row, giving \((0,0,1)\). Thus \(P^{(3)}=I\). Every row of \(P^{(2)}\) and \(P^{(3)}\) sums to \(1\), as each is a row with exactly one \(1\). Since \(P^{(4)}=P^{(3)}P=IP=P\), four steps have the same destination pattern as one step. This matches the path itself: after three moves the chain returns to its starting state, and the fourth move advances to the next state.

Index Checks and a Common Mistake

Matrix powers are sensitive to index order. For a two-step transition from \(i\) to \(j\), the correct contribution through \(k\) is \(p_{ik}p_{kj}\): first move from \(i\) to \(k\), then from \(k\) to \(j\). Reversing either pair changes the question. In the two-state example, an incorrect calculation of \(p_{12}^{(2)}\) might use \(p_{11}p_{21}+p_{12}p_{22}\), giving \(\tfrac34\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac38+\tfrac18=\tfrac12\). This uses \(p_{21}\) for a move from \(1\) to \(2\), even though its indices describe a move from \(2\) to \(1\). The correct sum is \(p_{11}p_{12}+p_{12}p_{22}=\tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac3{16}+\tfrac2{16}=\tfrac5{16}\), which agrees with the \((1,2)\) entry of \(P^2\).

A reliable calculation has three checks: use the row as the starting state, use the column as the destination, and sum over the shared intermediate index. When evaluating a full product, check each resulting row sum against \(1\). These checks do not replace the matrix multiplication; they help detect a transposed matrix, a mismatched index, or an omitted route.

Check Your Understanding

Use the index order in the Chapman–Kolmogorov equation, and verify computed entries by substitution into the matrix product.

  1. For a chain with \(p_{12}=\tfrac13\), \(p_{11}=\tfrac23\), \(p_{21}=\tfrac14\), and \(p_{22}=\tfrac34\), calculate \(p_{12}^{(2)}\). First check that both rows sum to \(1\).
  2. Explain why \(P^{(0)}=I\), rather than a matrix whose entries are all \(1\).
  3. Write the sum over intermediate states for \(p_{31}^{(2)}\) on a three-state space, using the symbols \(p_{ij}\).
  4. For the deterministic three-state cycle, what is \(p_{23}^{(4)}\)? Verify it from \(P^{(4)}=P\).
  5. State in words why the order of factors in the product \(P^{(n)}P\) represents \(n\) steps followed by one step.

Previous

Next

Back to Tutorials