Chapman–Kolmogorov equation

Statement

Let $(X_n)_{n \ge 0}$ be a time-homogeneous Markov chain on a countable state space $S$. For $n \ge 0$, let $p^{(n)}_{ij} = P(X_{m+n} = j \mid X_m = i)$ be the $n$-step transition probabilities. Then for all $m, n \ge 0$ and $i, j \in S$, $$p^{(m+n)}_{ij} = \sum_{k \in S} p^{(m)}_{ik} \, p^{(n)}_{kj}.$$ In matrix form, $P^{(m+n)} = P^{(m)} P^{(n)}$, so $P^{(n)} = P^n$ for the transition matrix $P$.

Remarks

Proof: condition on the state $X_m = k$ at the intermediate time, with the law of total probability, and use the Markov property. The equation says that to go from $i$ to $j$ in $m + n$ steps, the chain must be at some state $k$ after $m$ steps. For a Markov process with transition kernels $p_{s,t}(x, dy)$, the equation reads $p_{s,u}(x, A) = \int p_{s,t}(x, dy) \, p_{t,u}(y, A)$ for $s \le t \le u$.

History

The equation is named after Sydney Chapman and Andrey Kolmogorov.

Explanations

L1 human

The chances for several steps come from multiplying the one-step transition matrix with itself. For example, the chance of rain in two days, given sun today, sums over the two possible states of tomorrow.