Chapman-Kolmogorov Equation

Definition

The Chapman-Kolmogorov Equation gives the transition probability to go from state $i$ to $j$ in $n+m$ steps:

$P_{ij}^{(n+m)}={\sum }_{k=0}^N{P}_{ik}^{(n)}{P}_{kj}^{(m)}$

Where $N$ is the number of all states.

Interpretation

To get somewhere in multiple steps, you must pass through some intermediate state. The equation formalizes: the probability of going from $i$ to $j$ in $n+m$ steps equals the sum over all possible intermediate states $k$ of the probability of going $i\to k$ in $n$ steps, then $k\to j$ in $m$ steps.

Example

5-step transition from rain to rain =

• (2 steps to rain, then 3 steps rain→rain) +
• (2 steps to sunny, then 3 steps sunny→rain)

Proof

$$\begin{array}{rl}{P}_{ij}^{n+m}& =P\{X_{n+m}=j\mid X_0=i\}\\ & =\sum _{k=0}^{\infty }P\{X_{n+m}=j,X_n=k\mid X_0=i\}\\ & =\sum _{k=0}^{\infty }P\{X_{n+m}=j\mid X_n=k,X_0=i\}P\{X_n=k\mid X_0=i\}\\ & =\sum _{k=0}^{\infty }{P}_{kj}^m{P}_{ik}^n\end{array}$$

Related

• n-step Transition Matrix
• n-step Transition Matrix Identity