16 - Chapman-Kolmogorov Equations

Chapman-Kolmogorov Equations

$$p_{ij}^{(n+m)}=\sum _{k\in I}{p}_{ik}^{(n)}{p}_{kj}^{(m)}$$

$$p_{ij}^{(n)}=(P^n{)}_{i,j}$$

where $P^n$ is the $n$-th power of Transition Matrix

Proof

(1) Partition by value of intermediate state $X_n$, and apply Law of Total Probability

$$\begin{array}{rl}\mathbb{P}(X_{n+m}=j\mid X_0=i)& =\sum _k\mathbb{P}(X_n=k\mid X_0=i)\mathbb{P}(X_{n+m}=j\mid X_n=k,X_0=i)\\ & =\sum _k\mathbb{P}(X_n=k\mid X_0=i)\mathbb{P}(X_{n+m}=j\mid X_n=k)\\ & =\sum _k{p}_{ik}^{(n)}{p}_{kj}^{(m)}\end{array}$$

(2) Inductively

$$\begin{array}{rl}{p}_{ij}^{(2)}& =\sum _k{p}_{ik}{p}_{kj}=(P^2{)}_{i,j}\\ p_{ij}^{(3)}& =\sum _k{p}_{ik}^{(2)}{p}_{kj}^{(1)}=\sum _k(P^2{)}_{i,k}(P{)}_{k,j}=(P^{2}P{)}_{i,j}=(P^3{)}_{i,j}\end{array}$$

and so on