From BoykinWiki

Jump to: navigation, search

EEL6507 Spring 2009, Lecture 08, Monday 2008/01/26 (Notes created by Yonggang Liu)

Introduce Chapman Kolmogorov Equation.
Derive memoryless aspect of continuous time Markov Chain.

Multi-step Inhomogeneous Probability

We use:

Integralization $P\left(a\right) = \sum_{b:all\ values} P\left(a, b\right)\$
Conditional Probability $P\left(a,b\right) = P\left(b\right)P\left(a|b\right),\ \ P\left(a,b|c\right) = P\left(b|c\right)P\left(a|b,c\right)$
Markov Probability $P\left(X_n=x_n|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},...\right) = P\left(X_n=x_n|X_{n-1}=x_{n-1}\right)$

Define

$P_{ij}\left(m,n\right)=Pr\left[X_n=j|X_m=i\right]$

where i,j are states, and m,n are steps.

Suppose we stop at q:

$m \le q \le n$

Modulization:

$\begin{align} P_{ij}(m,n) &= \Pr[X_n= j|X_m=i] \\ &= \sum_{k}Pr[X_n=j,X_q=k|X_m=i] \\ &=\sum_{k}Pr[X_q=k|X_m=i]Pr[X_n=j|X_q=k,X_m=i] \\ \end{align}$

Because $q \ge m$ , from property of Markov Process we get:

$Pr\left[X_n=j|X_q=k,X_m=i\right]=Pr[X_n=j|X_q=k]=P_{kj}(q,n)$

Finally, we get

$P_{ij}\left(m,n\right)=\sum_{k}P_{i,k}(m,q)P_{k,j}(q,n)$

This format is the same as matrix multiplication.

Chapman Kolmogorov Equation

We define $[H\left(m,n\right)]_{i,j}=P_{ij}\left(m,n\right)$ , then

$H\left(m,n\right)=H(m,q)H(q,n)$ $H\left(m,m\right)=I$ $[P\left(n\right)]_{ij}=P_{ij}(n,n+1)=P[X_{n+1}=j|X_n=i]$ $H\left(n,n+1\right)=P(n)$

Forward Chapman Kolmogorov Equation:

$H\left(m,n\right)=H(m,n-1)H(n-1,n)=H(m,n-1)P(n-1)$

Backward Chapman Kolmogorov Equation:

$H\left(m,n\right)=H(m,m+1)H(m+1,n)=P(m)H(m+1,n)$

Derivation of $\vec \pi(n)$

Given initial $Pr\left[X_0=j\right]$ , i.e., $\pi_j\left(0\right)$ , how to get $Pr\left[X_n=i\right]$ , i.e., $\pi_i\left(n\right)$ ?

$\begin{align} Pr[X_n=i] &= \sum_{j}Pr[X_n=i,X_0=j] \\ &= \sum_{j}Pr[X_n=i|X_0=j]Pr[X_0=j] \\ &= \sum_{j}P_{ji}(0,n) \pi_{j}(0) \\ \end{align}$

From Forward Chapman Kolmogorov Equation:

$\begin{align} \vec \pi(n) &= \vec \pi(0) H(0,n) \\ &= \vec \pi(0)H(0,n-1)P(n-1) \\ & ... \\ &= \vec \pi(0)P(0)P(1)...P(n-1) \\ &= \vec \pi(0)\prod_{l=0}^{n-1}P(l) \\ \end{align}$

Alternatively, from Backward Chapman Kolmogorov Equation:

$\begin{align} \vec \pi(n) &= \vec \pi(0) H(0,n) \\ &= \vec \pi(0)P(0)H(1,n) \\ & ... \\ &= \vec \pi(0)P(0)P(1)...P(n-1) \\ &= \vec \pi(0)\prod_{l=0}^{n-1}P(l) \\ \end{align}$

In conclusion, we get

$\vec \pi\left(n\right) = \vec \pi(0)\prod_{l=0}^{n-1}P(l)$ $H\left(m,n\right)=\prod_{i=m}^{n-1}P(i)$

Special Form of Chapman Kolmogorov Equation

From

$H\left(m,n+1\right)=H(m,n)P(n)$

we get

$\begin{align} H\left(m,n+1\right)-H(m,n)&=H(m,n)P(n)-H(m,n) \\ &=H(m,n)[P(n)-I] \\ \end{align}$

Define $Q\left(n\right)=P(n)-I$ , then we get the derivative equation:

$H\left(m,n+1\right)-H(m,n)=H(m,n)Q(n)$

Continuous Time Memorylessness

$\begin{align} Pr\left(\tau > s+t|\tau > s \right) &= h(t),\ independent\ of\ s \\ &= \frac {Pr[\tau > s+t, \tau > s]}{Pr[\tau > s]} \\ &= \frac {Pr[\tau > s+t]}{Pr[\tau > s]}\ \ \ (*) \\ \end{align}$

If s=0, and the process starts at time 0, then