Derivation of the Chapman-Kolmogorov Equation
Theorem
For the transition probabilities $p_{ij}^{(n)}$, $p_{ij}(t)$ and transition probability matrices $P^{(n)}$, $P(t)$ of a stochastic process, the following equations hold.
Discrete Stochastic Process
$$ \begin{align*} p_{ ij }^{ (n+m) } =& \sum _{ k } p_{ ik }^{ (n) } p _{ kj }^{ (m) } \\ P^{(n+m)} =& P^{(n)} P^{(m)} \end{align*} $$
Continuous Stochastic Process
$$ \begin{align*} p_{ij} (t + s) =& \sum _{ k } p_{ ik } \left( t \right) p _{ kj } \left( s \right) \\ P(t+s) =& P(t) P(s) \end{align*} $$
Explanation
It means that the $n+m$ steps taken to go from state $i$ to $j$ can be expressed by splitting them into $n$ and $m$. Even without a formal proof, thinking about it intuitively, if we consider the probability of taking $n$ steps from $i$ to $k$ and the probability of taking $m$ steps from $k$ to $j$, that would be the probability of going from $i$ to $j$ via $k$, and the sum of these probabilities over all states $k$ would ultimately be the probability of going from $i$ to $j$, regardless of what was passed through in between.
Derivation
Strategy: We prove it only for the discrete stochastic process. By assuming $X_0$ to be $i$ at the start, we can avoid needlessly mentioning ‘starting from $i$’ afterwards. The expression inside the sigma is handled just like how, from the conditional probability $P(A|B)=P(AB)/P(B)$, multiplying both sides by $P(B)$ gives $P(AB)=P(A|B)P(B)$.
Assume $ { X }_{ 0 }=i$, then $$ \begin{align*} { p } _{ ij }^{ (n+m) } =& P({ X }_{ n+m }=j ) \\ =& \sum _{ k }^{ }{ P({ X }_{ m }=j , { X }_{ n }=k) } \\ =& \sum _{ k }^{ }{ P({ X }_{ m }=j | { X }_{ n }=k)P({ X }_{ n }=k) } \\ =& \sum _{ k }^{ }{ { p }_{ ik }^{ (n) } { p }_{ kj }^{ (m) } } \end{align*} $$
■