# Chapman-Kolmogorov Equation

Jump to navigation
Jump to search

## Theorem

Let $X$ be a discrete state-space Markov Chain with with $n$-step transition probability matrix:

- $\mathbf P^{\paren n} = \sqbrk {\map {p^{\paren n} } {j, k} }_{j, k \mathop \in S}$

where:

- $\map {p^{\paren n} } {j, k} = \mathbb P \sqbrk {X_{m + n} = k \mid X_m = j} = {p_{j k} }^{\paren n}$ is the $n$-step transition probability.

Then:

- $\mathbf P^{\paren {n + m} } = \mathbf P^{\paren n} \mathbf P^{\paren m}$

or equivalently:

- $\displaystyle {p_{i j} }^{\paren {n + m} } = \sum_{k \mathop \in S} {p_{i k} }^{\paren n} {p_{k j} }^{\paren m}$

## Proof

We consider the conditional probability on the left hand side:

\(\displaystyle \) | \(\) | \(\displaystyle \mathbb P \sqbrk {X_{m + n} = j \mid X_0 = i}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \mathbb P \left[{\paren {\bigcup_{k \mathop \in S} \sqbrk {X_{n + m} = j, X_n = k} } } \ \middle \vert \ {X_0 = i}\right]\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{k \mathop \in S} \mathbb P \sqbrk {X_{n + m} = j, X_n = k \mid X_0 = i}\) | Definition:Countable Additivity | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{k \mathop \in S} \mathbb P \sqbrk {X_{n + m} = j \mid X_n = k, X_0 = i} \times \mathbb P \sqbrk {X_n = k \mid X_0 = i}\) | Chain Rule for Probability | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{k \mathop \in S} \mathbb P \sqbrk {X_{n + m} = j \mid X_n = k} \times \mathbb P \sqbrk {X_n = k \mid X_0 = i}\) | Markov Property | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{k \mathop \in S} {p_{i k} }^{\paren n} {p_{k j} }^{\paren m}\) | Definition:Stationary Transition Probabilities |

$\blacksquare$

## Source of Name

This entry was named for Sydney Chapman and Andrey Nikolaevich Kolmogorov.