Chapman-Kolmogorov Equation

Topics: Markov Chain - Transition Matrix - Transition Probabilities in a Markov Chain

---

(theorem)

Given a Markov chain, we can obtain its transition probabilities with the Chapman-Kolmogorov equation.

To obtain n step transition probabilities:

$$p_{ij}^{(n)}=\sum _{k=0}^s{p}_{ik}^{(m)}{p}_{kj}^{(n-m)}$$

…for every $i,j,n$ and $0\le m\le n$.

Explanation

This equation is derived from the fact that we can calculate the probability of going from the state $i$ to the state $j$ by:

• Calculating the probability of going from $i$ to another intermediate state $k$ in $m$ steps ($m\le n$)
• Calculating the probability of going from that other intermediate state $k$ to $j$ in $n-m$ steps
• Multiplying these two probabilities so that we obtain the probability of both happening
• Adding up all these probabilities for every possible $k$