**Mumbai University > Electronics and Telecommunication Engineering > Sem 5 > Random Signal Analysis

Marks: 10M

Year: May 2016

Chapman Kolmogorov Equation / Theorem

Suppose {$X_n$} , n=0,1,2,3,.... is a homogeneous Markov Chain. Then

$$p^{m+n}_{ij} = {\sum_k}{p^m_{ik}} {p^n_{kj}}$$

That is, the conditional probability that the Markov Chain goes from state i to state j in m+n steps is equal to the sum of the conditional probabilities of reaching an intermediary state k in m steps and from k reaching state j in n steps. That is

P($X_{m+n}$=j | $X_0$=i)=${\sum_k}$ P($X_{m+n}$=j, $X_m$=k |$X_0$=i)

=${\sum_k}$ [P($X_{m+n}$=j, $X_m$=k |$X_0$=i)/ P($X_0$=i)]

=${\sum_k}$ [P($X_{m+n}$=j, $X_m$=k ,$X_0$=i)/ P($X_0$=i)]*[P($X_m$=k,$X_0$=i)/P($X_m$=k,$X_0$=i)]

=${\sum_k}$ [P($X_{m+n}$=j, $X_m$=k ,$X_0$=i)/P($X_m$=k,$X_0$=i) ]*[P($X_m$=k,$X_0$=i)/P($X_0$=i)]

=${\sum_k}$ [P($X_{m+n}$=j, $X_m$=k ,$X_0$=i)]*[P($X_m$=k,$X_0$=i)]

=${\sum_k}$ [P($X_{m+n}$=j, $X_m$=k )]*P($X_m$=k,$X_0$=i)

=RHS