MIT OCW, Fundamentals of Probability 23日目 Markov Chain II

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

• Lecture 24. Markov Chains II. Mean Reccurence Time
  • 24.1 Markov Chains with a Single Recurrence Class
    • • Lemma 24.1
      • Lemma 24.2
      • Exercise 1.
      • Exercise 2.
    • 24.2 Uniqueness of the Stationary Distibution
      • Theorem 24-3 (証明略)
    • 24.3 Ergodic Theorem
      • Theorem 24-9 (証明略)

Lecture 24. Markov Chains II. Mean Reccurence Time

24.1 Markov Chains with a Single Recurrence Class

前章でrecurrenceの関係$\leftrightarrow$は同値関係であり,$\mathcal{T}$をtransientの集合とすると,$\mathcal{X} \backslash \mathcal{T}$は$\leftrightarrow$によって同値類別できることを見た.また同値類は$R_1, ..., R_r$とする.$\leftrightarrow$でできた同値類のそれぞれをclassとよぶことにする

Lemma 24.1

任意の同値類$R_k$において,$i \in R_k$かつ$j \notin R_k$ならば$p_{i,j}=0$
すなわち,一旦ある同値類$R_k$に入ったら,その後どう遷移しようと$R_k$からは抜け出せない.

proof.

$p_{i, j} > 0 \Rightarrow i \rightarrow j$. $i$はrecurrentだから$j \rightarrow i$であり,$j \in R_{k}$. これは矛盾.

$$T_i = \min \{n \geq 1: X_n=i|X_0=i\}$$
というrandom variableを,$\infty$を許して導入する.これをthe first passage timeという.

Lemma 24.2

任意の$i \in \mathcal{T}$に, $P(X_n=i, i.o.)=0$である. すなわち,有限時間ステップの経過後にchainが$i$に戻ってくることは殆ど全く無く,また$E[T_i]= \infty$である.

proof.

定義より$i \rightarrow j, j\nrightarrow i$なる$j \notin \mathcal{T}$がある. ゆえに$P(T_i = \infty)>0$であって,$T_i\geq 0$だから$E[T_i]=\infty$が成立する.
$I_{i,m}$を, chainが少なくとも$m$回$i$に戻ってくるというeventとする. $P(I_{i, 1})=P(T_i < \infty)$である.またLemma24.1から$P(I_{i,1})<1.$
state $i$に$m-1$回目に到達したときから見て,次に$i$に到達する確率というのは,$i$から$i$に1回推移する確率に等しいというのがMarkov性から言えるので,$(I_{i,m}|I_{i,{m-1}})=P(T_i < \infty)$が成り立ち,また明らかに$I_{i, m} \subset I_{i, m-1}$であって, $P(I_{i,m})=P(I_{i,m}|I_{i,m-1})P(I_{i,m-1})=P(T_i < \infty)P(I_{i,m-1}) =\cdots =P(T_i<\infty)^m$. $P(T_i<\infty)<1$だから,probabilityの連続性を使って,$P(\cap_m I_{i,m})=\lim P(I_{i,m})=\lim_m P(T_i<\infty)^m = 0$.$X_n=i , \text{ i.o.}$は$\cap _m I_{i,m}$と一致するから,補題が示せた.

Exercise 1.

$\mathcal{T} \neq \mathcal{X}$を示せ.

答案.

$\mathcal{X} = \mathcal{T}$を仮定する. $P(X_n=i, \text{ i.o.})=0$が任意の$i \in \mathcal{X} = \{1, ...,N\}$に成立するから,$P(X_n\in \mathcal{X}, \text{ i.o.})=0$つまり有限時間ステップの後,殆ど必ずこのMarkov chainはどのstateにも到達していない. これは不合理.

Exercise 2.

$i\in \mathcal{T}$で $\pi$は任意のstationary distributionとする. $\pi_i = 0$を示せ.

答案.

$\pi_i >0$を仮定する.$\pi_i = \sum_{1 \leq k \leq N} p_{k,i}\pi_k$である.$i \in \mathcal{T}$なら,少なくともひとつの$\pi_k>0,p_{k,i}>0$なる$k$がある.$k \in {R}$ならば$i \leftrightarrow k$で$k \in \mathcal{T}$に反するから$k \in \mathcal{T}$である.$\pi_k >0$なので，同じ論法で$k \leftarrow l \in \mathcal{T}$なる$l$があって,$l\neq i, k$.繰り返して,$i \leftarrow k \leftarrow l \leftarrow \cdots \leftarrow l_n \leftarrow \cdots$なる$\{l_n\} \subset \mathcal{T}$がある. $|\mathcal{T}|<|\mathcal{X}|<\infty$から,この列はいつか終わり,その終点$l_M$では$0 \neq \pi_{l_M} = \sum_{1 \leq j \leq N} p_{j, l_M}\pi_j = \sum 0 \pi_j = 0$ これは矛盾.

Exercise 3.

M.c. $\{X_n\}$がrecurrent class $R$をもち,$i \in R$ならば$P(X_n=i, \text{ i.o.})=1$を示せ.また,$P(T_i > t) \leq Cq^t$が任意の$t \geq 0$になりたつような$0<q<1, C>0$が存在することを示し,最後に$E[T_i]<\infty$を示せ.

答案.

ある$j \in i$があって$i \rightarrow j \rightarrow i$だから,$P(T_i < \infty)=1$. Lemma 24.2の証明と同じ論法で$P(X_n=i \text{ i.o.})=P(\cup_m I_{i, m})=\lim_m P(T_i <\infty))^m=1$.
ビーンもうダメ

recurrent class　がただ一つであるMarkov chainの例をいくつか挙げる. 特に$\mathcal{T}=\phi$であるとき,このMarkov chainはirreducibleという.$\mu_i = E[T_i]$を$\infty$を許して定義するとき,これを$i$におけるmean recurrence timeという.

24.2 Uniqueness of the Stationary Distibution

Theorem 24-3 (証明略)

recurrence class がただ一つしか無い有限Markov chainは固有のstationary distribution $\pi$をもち,$\pi_i = 1/ \mu_i$である.特に$i$がrecurrentであるとき,またそのときにのみ$\pi_i>0$となる.

24.3 Ergodic Theorem

$N_i(t)$を,$0, 1, ..., t$の間に$i \in \mathcal{X}$にchain が到達した回数とする. $N_i(t)/t \rightarrow \pi_i$である.このように,$t$に依存する確率変数を$t$で割った確率変数の極限のもつ性質をergodic properties(エルゴード性)という. これは,chaihの時間的な平均$N_i(t)/t$が,空間的な平均$\pi_i$に近づくという著しい主張である.

Theorem 24-9 (証明略)

任意の$k \in \mathcal{X}$を初期状態$X_0=k$として, また任意の$i \in \mathcal{X}$に,$\lim_{t \rightarrow \infty} N_i(t)/t = \pi_i\ \ \text{a.s.}$であり, $\lim_{t \rightarrow \infty} E[N_i(t)]/t = \pi_i$である.

正直わからないのでなにかいい本を探してじっくり読みたい(願望)