3.2 The Chapman–Kolmogorov Equations
The \(n\)-step transition probabilities are \[P_{ij}^{(n)} = P(X_{m + n} = j\mid X_m = i) = P(X_n = j\mid X_0 = i),\qquad n\geq 0,\] with \(P_{ij}^{(0)} = 1\) if \(i = j\) and \(0\) otherwise.
Theorem 3.2.1 (Chapman–Kolmogorov equations). For all \(m, n\geq 0\) and all states \(i, j\), \[P_{ij}^{(m + n)} = \sum _kP_{ik}^{(m)}P_{kj}^{(n)} .\] In matrix form, the \(n\)-step transition matrix is \(P^{(n)} = P^n\), the \(n\)th power of \(P\).
Proof. Condition on the state at time \(m\): \begin {align*} P_{ij}^{(m + n)} &= P(X_{m + n} = j\mid X_0 = i) = \sum _kP(X_{m + n} = j, X_m = k\mid X_0 = i)\\ &= \sum _kP(X_{m + n} = j\mid X_m = k, X_0 = i)\,P(X_m = k\mid X_0 = i)\\ &= \sum _kP_{kj}^{(n)}P_{ik}^{(m)}, \end {align*}
where the last step uses the Markov property (given \(X_m = k\), the value of \(X_0\) is irrelevant) and homogeneity. The matrix statement is the definition of matrix multiplication, and induction on \(n\) gives \(P^{(n)} = P^n\). □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.