Coursera Stochastic Processes 課程筆記, 共十篇:
- Week 0: 一些預備知識
- Week 1: Introduction & Renewal processes
- Week 2: Poisson Processes
- Week3: Markov Chains (本文)
- Week 4: Gaussian Processes
- Week 5: Stationarity and Linear filters
- Week 6: Ergodicity, differentiability, continuity
- Week 7: Stochastic integration & Itô formula
- Week 8: Lévy processes
- 整理隨機過程的連續性、微分、積分和Brownian Motion
Week 3.1: Definition of a Markov chain. Some examples
[Markov Chain Def]:
令 State space $\mathcal{S}$ which is countable. 則 $S_n$, $n=0,1,2,…$ 稱為 Markov chain 需滿足 Markov property 如下:
$\mathcal{P}\{S_n=j | S_{n-1}=i_{n-1},...,S_0=i_0\} = \mathcal{P}\{S_n=j | S_{n-1}=i_{n-1}\}$
其中 $i_0,...,i_{n-1},j\in\mathcal{S}$, and $\mathcal{P}\{S_{n-1}=i_{n-1},...,S_0=i_0\}\neq0$
如果滿足 Markov property, 則我們發現:
$$\mathcal{P}\{S_n=i_n,S_{n-1}=i_{n-1},...,S_0=i_0\} \\
= \mathcal{P}\{ S_n=i_n | S_{n-1}=i_{n-1},...,S_0=i_0 \}\cdot \mathcal{P}\{ S_{n-1}=i_{n-1},...,S_0=i_0 \} \\
= \mathcal{P}\{ S_n=i_n | S_{n-1}=i_{n-1} \}\cdot \mathcal{P}\{ S_{n-1}=i_{n-1},...,S_0=i_0 \} \\
=...\\
= \mathcal{P}\{ S_n=i_n | S_{n-1}=i_{n-1} \} \mathcal{P}\{ S_{n-1}=i_{n-1} | S_{n-2}=i_{n-2} \} ... \mathcal{P}\{ S_1=i_1 | S_0=i_0 \} \mathcal{P}\{S_0=i_0\}$$
所以是 pairwise independent
Any renewal process is also a Markov chain
[Random Walk Example]:
考慮
$$\mathcal{P}\{ S_n=j | S_{n-1}=i_{n-1} \} = \left\{
\begin{array}{rl}
p, & j=i_{n-1}+1 \\
1-p, & j=i_{n-1}-1 \\
0, & \text{otherwise}
\end{array}
\right.$$
發現只會跟前一個 state 有關
注意到 random walk 不是 renewal process, 因為 $\xi$ 可以產生負的值. 而在 renewal process, $\xi$ 為 inter-arrival time $\geq0$
[Taxis in the airport Example]:
$1$ taxi at $n$ moment, $n=1,2,3,…$
如果當下沒有乘客, taxi 就離開. 如果有乘客, taxi 當場載走一名並馬上就離開.
$X_k$: # people waiting for taxi at time $k$
$Y_k$: # people arriving at time $k$
現在說明 $X_k$ 是 Markov chain
$$X_k=Y_k+(X_{k-1}-1)_+= \left\{
\begin{array}{rl}
Y_k, & \text{if }X_{k-1}=0 \\
Y_k+X_{k-1}-1, & \text{if }X_{k-1}\geq0 \\
\end{array}
\right.$$
所以 $X_k$ 只跟 $X_{k-1}$ 有關
[Example]:
考慮以下 $X_n$, for some fixed $m\in\mathbb{N}$
$\mathcal{P}\{ X_n | X_{n-1},...,X_0 \} = \mathcal{P}\{ X_n | X_{n-1},...,X_{n-m} \}$
當下的 state 跟前 $m$ 個 states 有關, 而原本 Markov property 是只能與前 $1$ 個 state 有關.
我們定義 $S_n$ (a vector of $X_n$) 如下:
$S_n=(X_n,...,X_{n-m+1}),\text{ where } n=m-1,m,...$
則我們發現:
$$\mathcal{P}\{ X_n | X_{n-1},...,X_0 \} = \frac{\mathcal{P}\{ X_n,X_{n-1},...,X_0\}}{\mathcal{P}\{ X_{n-1},...,X_0\}} \\
= \frac
{
\mathcal{P}\{ (X_n,...,X_{n-m+1}), (X_{n-1},...,X_{n-m}),...,(X_{m-1},...,X_0) \}
}
{
\mathcal{P}\{ (X_{n-1},...,X_{n-m}),...,(X_{m-1},...,X_0)
} \\
= \frac
{\mathcal{P}\{S_n,S_{n-1},...,S_{m-1}\}}
{\mathcal{P}\{S_{n-1},...,S_{m-1}\}} = \mathcal{P}\{S_n | S_{n-1},...,S_{m-1}\} \ldots(\star) \\
\mathcal{P}\{ X_n | X_{n-1},...,X_{n-m} \} = \frac{\mathcal{P}\{ X_n,X_{n-1},...,X_{n-m}\}}{\mathcal{P}\{ X_{n-1},...,X_{n-m}\}} \\
= \frac
{
\mathcal{P}\{ (X_n,...,X_{n-m+1}), (X_{n-1},...,X_{n-m}) \}
}
{
\mathcal{P}\{ (X_{n-1},...,X_{n-m})
} \\
= \frac
{\mathcal{P}\{S_n,S_{n-1}\}}
{\mathcal{P}\{S_{n-1}\}} = \mathcal{P}\{S_n | S_{n-1}\}\ldots(\square)$$
因為 $X_n$ 是 Markov chain, 所以 $(\star)=(\square)$, 得知 $S_n$ 為 Markov chain
Week 3.2: Matrix representation of a Markov chain. Transition matrix. Chapman-Kolmogorov equation
Matrix representation 如課程上圖的說明, 這裡很容易看上圖即可.
[Thm]:
Define $p_{ij}^{(m)} = \mathcal{P}\{X_{n+m}=j | X_n=i\}$, 即 step $n$ 時在 state $i$, 且走了 $m$ steps, i.e. step $n+m$, 時在 state $j$ 的機率.
並定義 $P^{(m)}=\left( p_{ij}^{(m)} \right)$ 表示 m-step 的 transition matrix. 則我們有:
$P^{(m)}= P^m=\underbrace{PP\cdots P}_{m\text{-times}}$
定義了 stationary distribution $\vec\pi^*=\vec\pi^*P$
Week 3.3-5: Graphic representation. Classification of states
定義了 $i\rightarrow j$ 表示有一條 walk (多條 arcs 連結) from $i$ to $j$. 稱 $j$ is accesible from $i$
定義了 $i\leftrightarrow j$ 表示有一條雙向 walk 連結 $i$ and $j$. 稱 $i$ and $j$ communicate
[Equivalence Relation Def]:
給定 set $A$, 若有一個 binary operation $\sim$ 滿足以下關係則稱 $\sim$ 為 equivalence relation:
$$\begin{array}{rl}
a\sim a, a\in A & \text{reflectivity} \\
a\sim b\Rightarrow b\sim a, \forall a,b\in A & \text{symmetry} \\
a\sim b, b\sim c \Rightarrow a\sim c & \text{transtivity}
\end{array}$$
給定 set $A$ 和它的一個 equivalence relation $\sim$, 則我們可以定義出 equivalence class
The equivalence class of an element $a$ is often denoted $[a]$ or $[a]_\sim$ and is defined as the set ${ x\in A: a\sim x}$ of elements that are related to $a$ by $\sim$.
我們對 Markov chain 的圖可以定義一個 equivalence relation (by communicate $\leftrightarrow$)
$B_1,B_2,…$ 為 states 的 equivalence classes by definition below
$$\forall j\in B_i, \forall k \in \mathcal{S} \left\{
\begin{array}{rl}
k\in B_i, &k\leftrightarrow j \\
k \notin B_i, & k \nleftrightarrow j
\end{array}
\right.$$
簡單講就是拿兩個 states $j$ and $k$ 出來, 如果他們 $\leftrightarrow$ 則屬於同一個 set. 這樣會使得 state space $\mathcal{S}$ 形成 equivalence classes
課程裡的 state $4$ 只有 out going arcs, 所以 $4 \nleftrightarrow 4$, 因此不應該有一個 equivalence class $\{4\}$ 才對啊 ? 我猜應該要多補上這條: 自己跟自己一定屬於同一個 equivalence class.
[Recurrent and Transient Def]:
$i$ is recurrent if $\forall j:i\rightarrow j \Rightarrow j\rightarrow i$
$i$ is transient if $\exist j: i\rightarrow j, j\nrightarrow i$
我們說一個 state $i$ 是 recurrent 必須滿足對”所有”其他 states 都滿足 “如果 $i$ 到的了該 state, 那該 state 也到的了 $i$”
而 transient 只需滿足 “存在” 一個 state 使得 $i$ 到的了但回不來
[Thm, Nodes are ALL Recurrent or ALL Transient in An Equivalence Class]:
因此 equivalence classes:
$$\begin{array}{rl}
\{1\}, & \text{transient} \\
\{2,3\}, & \text{recurrent} \\
\{4\}, & \text{transient} \\
\{5,6\}, & \text{transient}
\end{array}$$
其實我們可以把 equivalence class 想成是一個 state 就可以. 然後如果有出去的 arc 就是 transient. 反之沒有出去的 arcs 就會是 recurrent.
[Period of a State $i$ Def]:
給定一個 Markov chain (discrete time and countable state space $\mathcal{S}$), 定義 peroid of a state $i$:
$d(i):=GCD\{n:p_{ii}^{(n)}\neq0\}$
其中 $GCD$ 為 greates common divisor, 若 $d(i)=1$ 我們稱 $i$ 為 aperiodic
假設 $n$ 為走回自己要花的步數, 所有那些 $n$ 的最大公因數就是 period
[範例]: 同樣用課程的圖
$d(1)=1$
$d(2)=d(3)=2$
$d(4)=1$, 走不回自己 period 定義為 $1$
$d(5)=GCD{2,3,…}=1$, 其中 $2$ 是因為 $5\rightarrow6\rightarrow5$, $3$ 是因為 $5\rightarrow6\rightarrow6\rightarrow5$
$d(6)=1$
$a\vdots b$ 表示 $a$ 能被 $b$ 整除
[Thm]: All elements in 1 equivalence class have the same period
[Proof]:
選定 states $i$ and $j$ 在同一個 equivalence class, 並令 $i\rightarrow j$ 走 $n$ 步, $j\rightarrow i$ 走 $m$ 步.
假定 for some $k$ 滿足:
$p_{jj}^{(k)}\neq 0 \Longrightarrow k\vdots d(j) \ldots (\star)$
表示 $j\rightarrow j$ 可以走 $k$ 步, 因此 $k$ 一定會被 $d(j)$ 整除.
如圖:
我們有如下的關係:
$$\left.
\begin{array}{r}
p_{ii}^{(n+m)}\neq0 \Longrightarrow (n+m) \vdots d(i) \\
p_{jj}^{(k)}\neq0 \Longrightarrow p_{ii}^{(n+m+k)}\neq0 \Longrightarrow (n+m+k) \vdots d(i)
\end{array}
\right\} \Longrightarrow k\vdots d(i)$$
因為 $j$ 可以走 $k$ 步回到自己, 所以 $i$ 可以走 $n+m+k$ 步也回到自己. 得到 $k$ 可以被 $d(i)$ 整除的結論.
因此對所有可能的 $k$ (那些滿足 $(\star)$ 的 $k$) 我們都可以得到被 $d(i)$ 整除的結論.
表示 $d(i)$ 是這些所有可能的 $k$ 的 “公因數”
根據定義, $d(j)$ 是這些所有可能的 $k$ 的 “最大公因數”
因此 $d(j)\geq d(i)$
同樣的流程我們 $i$ and $j$ 的腳色互換, 也可以得到 $d(i)\geq d(j)$
得到結論 $d(i)=d(j)$
Q.E.D.
課程的說明我覺得有點問題, 以下為課程的解釋:
注意到 $d(i)$ 是”某一個” $k$ 的因數, 但是 $d(j)$ 是所有可能的 $k$ 的最大公因數. 因此 $d(i)$ 一定可以被 $d(j)$ 整除 (??) :
$$d(i) \vdots d(j)$$
同樣的流程我們 $i$ and $j$ 的腳色互換, 也可以得到 $d(j)$ 會被 $d(i)$ 整除
得到結論 $d(i)=d(j)$
Week 3.6-7: Ergodic chains. Ergodic theorem
[Ergodic Markov Chain using Graphic Representation]:
我們說一個 Markov chain is ergodic, 需滿足以下條件
1. 只有一個 class of equivalence
2. 所有 nodes are recurrent
3. $d(i)=1,\forall i\in\mathcal{S}$. 所有 nodes are aperiodic
[Example]:
如果只有實線的 arcs, 則滿足 1. 只有一個 equivalence class, 2. 所有 nodes are recurrent. 但是 $d(i)=6$.
但如果包含虛線的 arc 則 $d(i)=GCD(\{5,6\})=1$
算出 equivalence class 裡的一個 node, 就等於算出了全部 nodes
[Thm of Connection between Graphic and Matrix Representation in Ergodic Markov Chain]:
Markov chain is ergodic (defined in graphic representation)
$\Longleftrightarrow \exists m\in \mathbb{N}:p_{ij}^{(m)}\neq0, \forall i,j \in \mathcal{S} \ldots (\star)$
我們舉個例子 $(\star)$ 條件不成立.
我們發現
$$\left\{m=5,11,17,...:p_{ij}^{(m)}\neq0\right\} \\
\left\{m=1,7,13,...:p_{ji}^{(m)}\neq0\right\}$$
不存在一個 $m$ 能同時滿足所有 nodes
利用以上定理我們可以寫出 matrix representation for ergodic Markov chain
[Ergodic Markov Chain using Matrix Representation]:
我們稱一個 Markov chain 是 ergodic, 如果滿足:
$p_{ij}^{(m)}\neq0, \forall i,j \in \mathcal{S}, \forall m\geq(M-1)^2+1$
其中 $M$ 是 states 數量, i.e. $|\mathcal{S}|$
課程試題:
將 graph 圖畫出來, 可以發現滿足 graphic representation of ergodic Markov chain 的三個條件
用 matrix 的定義目前還不知道怎麼驗證 $\forall m\geq26$ 都滿足
[Ergodic Theorem]:
令 $X_t$ 為一個 ergodic Markov chain, (i.e. 1-class equivalence, recurrent, and aperiodic.), 則極限值存在:
$\exists \lim_{n\rightarrow\infty}p_{ij}^{(n)} = \pi_j^* > 0$
注意到已經跟出發點的 state $i$ 無關了, 且 strictly positive. 另外 $\vec\pi$ 的定義如下:
$\vec{\pi}^* = (\vec{\pi}_1^*,...,\vec{\pi}_M^*), \text{ with } \sum_{j=1}^M \pi_j^* = 1$
$i$ transition $n$ 步到 $j$ 的機率, 當 $n\rightarrow\infty$ 時會收斂, 並且 $>0$
[Corollary]:
令 $X_t$ 為一個 ergodic Markov chain, 則 Ergodic theorem 成立, 則我們有:
1. $\vec{\pi}^*$ is stationary distribution, i.e. $\vec{\pi}^*=\vec{\pi}^*P$
2. $\lim_{n\rightarrow\infty}\mathcal{P}\{X_n=j\}=\pi_j^*$
[Proof]:
[Example]: