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 23. Markov Chains
23.1 Introduction
Definition 23-1
{Xn}n≥1がMarkov chain
⇔ X(Ω)=Xはたかだか可算集合で,
P(Xn=xn|Xn−1=xn−1,Xn−2=xn−2,...,X1=x1)=P(Xn=xn|Xn−1=xn−1)
Xをstatesといい,Xn=s∈Xなら,{Xn}はnにおいてstate sをとる という. 特に無限であると言わない場合,|X|<∞の場合を考える.このときX={1,...,N}として一般性を失わない.
Proposition 23-1
Markov chain {Xn}n≥1について,
(a) 任意のs,x1,...,xn∈Xとm∈Nについて,
P(Xn+m=s|Xn−1=xn−1,Xn−2=xn−2,...,X1=x1)=P(Xn+m=s|Xn−1=xn−1)(b) 任意のx1,...,xn∈Xとk∈{1,...,n}について,
P(Xn=xn|Xn−1=xn−1,...,X1=x1|Xk=xk)=P(Xn=xn,Xn−1−xn−1,...,Xk+1=xk+1|Xk=xk)P(Xk−1=xk−1,...,X1=x1|Xk=xk)
23.2 Examples
random walkはMarkov chainの一つである.
サイコロを繰り返しふって,Xnはn回の試行で過去出た出目6の回数とする. このときP(Xn=x+1|Xn−1=x)=1/6,P(Xn=x|Xn−1=x)=5/6であり,またy≠x,x+1なら P(Xn=y|Xn−1=x)=0である.これは右へ進む確率1/6,その場にとどまる確率1/6のrandom walkとみなせる.
23.3 Homogeneous Finite State Markov Chain
Definition 23-2
Markov chain {Xn}がhomogeneousである
⇔∀n P(Xn+1=y|Xn=x)=P(X2=y|X1=x)
p(x,y)=P(Xn+1=y|Xn=x)と書くようにすると,N×N行列P=(pi,j)という行列ができる.これを{Xn}のtransition matrixという. ∑jpi,j=1である. 任意の行について,その行の要素の和が1であり,全ての要素が非負な行列を stochastic matrixという.
さて,
P(Xn+2=j|Xn=i)=∑1≤k≤NP(Xn+2=j|Xn+1=k,Xn=i)P(Xn+1=k|Xn=i)=∑1≤k≤NP(Xn+2=j|Xn+1=k)P(Xn+1=k|Xn=i)=∑1≤k≤Npk,jpi,k
だから,P2の(i,j)成分(p(2)i,jと書く)は,{Xn}を1つ飛ばしにしたMarkov chainのtransition matrixと考えることが出来る. 同じ論法でr∈Nに,Prはr−1飛ばしのMarkov chainのtransition matrixである. Prのr→∞での振る舞いを理解するのは大切である. Markov chainの多くを占めるクラスで,jのみによってlimr→∞pri,jが存在することを後で見る.この性質をmixingという.
ejでRNのj番目の標準基底ベクトルを表すことにする.またeを全ての要素が1であるN次元ベクトルとする. X0=iとすると, Xnのprobability vectorはeTiPnであり,X0がprobability vector μによって決まるなら, Xのprobability vectorはμTPnになる.
23.4 Stationary Distribution
X={1,2},p1,1,=p1,2=1/2,p2,1=1,p2,2=0という単純なMarkov chainを考える. μ1=P(X0=1)=2/3,μ2=P(X0=2)=1/3なるμ=(μ1,μ2)Tからn=0でのstateが生成されるとき,P(X1=1)=(1/2)P(X0=1)+P(X0=2)=2/3,P(X1=2)=1−P(X1=1)=1/3.
よってP(X0=i)=P(X1=i) i=1,2で,X0,X1は同じ分布を持つと言える.これは任意のnも言える.
Definition 23-2
probability vector π=(πi),1≤i≤Nがstationary distribution
⇔P(X0)=πiと初期状態を決めると∀1≤i≤N,1≤n, P(Xn=i)=πi
さらにこのとき(Markov chain{Xn}にsteady stateがあって,初期状態がそれによって決められたとき){Xn}はsteady stateにあるという.
定義から,πがsteady stateである必要十分条件は,πi≥0,∑πi=1かつ
∀i πi=∑1≤k≤Npk,iπk
が成り立つことである. これはベクトル形式で書くと
πT=πTP
である.
Theorem 23-4
X<∞なMarkov chainは少なくとも１つのstationary distributionをもつ.
proof. 略 linear programming(線形計画法)の知識が必要らしい・・・ あとで確率論的な証明を与える.
23.5 Classification of States, Rucurrennt and Transient States
state 有限, homogeneousなMarkov chainがtransition matrix Pを持っているとき, 有向グラフが作れる.
ノード集合V=X, pi,j>0なるi,j∈Vはedge集合の元;(i,j)∈Eとする. iからjへ至るpathがあるときiはjとコミュニケートする(i communicates with j)といい,i→jと書く. これは∑np(n)i,j>0ということである. i→jだがj→iでないというのは,chainがiから始まってjに至ると,再びiに戻ることはほとんど必ずないということである.
Definition 23-5
i∈Xがtransient
⇔i→jだがj↛iなるj∈Xが存在する
iがtransientでないとき,recurrentであるという.
i→j,j→iなるときi↔jと書く.この関係は同値関係である.recurrent statesは同値類R1,...,Rrに分割でき,Tをtransient stateの集合とすると,
X=T∪R1∪...∪Rrと,互いに素な集合の和集合として書ける.
0 件のコメント:
コメントを投稿