1、馬爾可夫過程,碩士研究生學位課程應用數學基礎,主講教師 段禪倫 2008年秋季學期,(演示文稿),(Markoff process),第四章 馬爾可夫鏈,馬爾可夫鏈是最簡明的馬爾可夫過程, 它是狀態(tài)、時 間都是離散量的馬爾可夫過程. 馬爾可夫過程是隨機過程中歷史最悠久且充滿活力的 一類隨機過程.自20世紀初俄羅斯數學家A.A.MapkoB等人 開始研究馬爾可夫過程以來,可以說久盛不衰. 它有極為 深厚的理論基礎,如拓撲學、函數論、泛函分析、近世代 數和幾何學; 又有廣泛的應用空間,如近代物理、隨機分 形、公共事業(yè)中的服務系統(tǒng)、電子信息、計算機技術等. 自然界很多現象遵從這樣的演變規(guī)則:由時刻t

2、0系統(tǒng)或 過程所處的狀態(tài)(現在)可以決定系統(tǒng)或過程在時刻tt0 所處的狀態(tài)(將來),而無需借助于t0以前系統(tǒng)或過程所處 狀態(tài)(過去)的歷史資料. 如微分方程初值問題即屬于此.,馬爾可夫鏈的概念及轉移概率,4.1 馬爾可夫鏈的概念及轉移概率 1.馬爾可夫鏈的定義 設隨機過程Xn,nT的參數集T=0,1,2,Xn可能 取值的全體組成的狀態(tài)空間為I=i1,i2,i3,. 定義4.1 設有隨機過程Xn,nT,若對于任意的整數n T和任意的i0,i1,in+1I,條件概率滿足 PXn+1=in+1|X0=i0,X1=i1,Xn=in =PXn+1=in+1|Xn=in (4.1) 則稱Xn,nT為馬爾可

3、夫鏈,簡稱馬氏鏈. (4.1)是馬爾可夫鏈的馬氏性(也稱無后效性)的數學表達 式. 利用積事件的概率及上述定義知:,馬爾可夫鏈的概念及轉移概率,PX0=i0,X1=i1,Xn=in =PXn=in|X0=i0,X1=i1,Xn-1=in-1PX0=i0,X1=i1, Xn-1=in-1 =PXn=in|Xn-1=in-1PX0=i0,X1=i1,Xn-1=in-1 = =PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2PX1=i1| X0=i0PX0=i0. 即馬爾可夫鏈的統(tǒng)計特性完全由條件概率 PXn+1=in+1|Xn=in 所決定. 如何確定這個條件概率,是馬爾可

4、夫鏈理論和應 用中的重要問題之一.,馬爾可夫鏈的概念及轉移概率,2.轉移概率 條件概率PXn+1=j|Xn=i的直觀含義是:系統(tǒng)在時刻n處 于狀態(tài)i的條件下,在時刻n+1系統(tǒng)處于狀態(tài)j的概率.這相 當于隨機游動的質點在時刻n處于狀態(tài)i的條件下,下一步 轉移到狀態(tài)j的概率. 記此條件概率為pij(n),其嚴格定義 是: 定義4.2 稱條件概率 pij(n)=PXn+1=j|Xn=i 為馬爾可夫鏈Xn,nT在時刻n的一步轉移概率,簡稱 為轉移概率,其中i,jI. 一般, 轉移概率pij(n)不僅與狀態(tài)i,j有關,而且與時刻 n有關.當pij(n)不依賴時刻n時,表示馬爾可夫鏈具有平穩(wěn),馬爾可夫鏈的

5、概念及轉移概率,轉移概率. 定義4.3 若對任意的i,jI, 馬爾可夫鏈Xn,nT的轉 移概率pij(n)與時間n無關,則稱馬爾可夫鏈是齊次的, (亦稱是時齊的,即具有平穩(wěn)轉移概率)并記pij(n)為pij. 下面只討論齊次馬爾可夫鏈,并將齊次兩字省略. 設P為一步轉移概率pij所組成的矩陣,狀態(tài)空間I=1,2, ,則 P= 稱為系統(tǒng)狀態(tài)的一步轉移概率矩陣. 一步轉移概率矩陣具有性質:,p11 p12 p1n p21 p22 p2n pi1 pi2 pin ,馬爾可夫鏈的概念及轉移概率,(1) pij0, i,jI; (2) pij=1, iI. (2)式中對j求和,是對狀態(tài)空間I的所有可能狀

6、態(tài)進行的, 此性質說明一步轉移概率矩陣中任一行元素之和為1. 通 常稱滿足(1)、(2)性質的矩陣為隨機矩陣. 為進一步討論馬爾可夫鏈的統(tǒng)計性質, 還須了解n步轉 移概率,初始概率和絕對概率的概念. 定義4.4 稱條件概率 pij(n)=PXm+n=j|Xm=i,i,jI,m0,n1 為馬爾可夫鏈Xn,nT的n步轉移概率,并稱 P(n)=(pij(n) 為馬爾可夫鏈的n步轉移矩陣,其中pij(n)0, pij(n)=,馬爾可夫鏈的概念及轉移概率,1,即P(n)也是隨機矩陣. 當n=1時,pij(1)=pij,此時一步轉移矩陣P(1)=P. 此外規(guī) 定pij(0)= (P(0)是單位矩陣). 例

7、4.1 (一維隨機游動) 設一醉漢Q(即一隨機游動的質點), 在如右上圖所示的 直線點集I=1,2,3,4,5作隨機游動,并且僅僅在1秒,2秒 等時刻發(fā)生游動.游動的概率規(guī)則是:如果Q現在位于點 i(1i5), 則下一時刻各以1/3的概率向左或向右移動 一格,或以1/3的概率留在原處; 如果Q現在位于點1(或5) 上,則下一時刻就以概率1移動到點2(或4)上.點1與5稱為 反射壁.并稱上述這種游動為帶有兩個反射壁的隨機游動. 若以Xn表示時刻n時Q的位置, 不同的位置就是Xn的不同,0,ij,1,i=j .,1,2,3,4,5,馬爾可夫鏈的概念及轉移概率,狀態(tài),則Xn,n=0,1,2,是一隨機

8、過程, 狀態(tài)空間就是I, 而且當Xn=i,iI為已知時,Xn+1所處的狀態(tài)的概率分布只 與Xn=i有關,而與Q在時刻n以前,如何到達i是完全無關的, 所以Xn,n=0,1,2,是一馬氏鏈,而且還是齊次的.這一 齊次馬氏鏈的一步轉移概率和一步轉移概率矩陣分別為: pij=PXn+1=j|Xn=i= P= .,1/3,j=i-1,i,i+1,1i5,1,i=1,j=2或i=5,j=4,0,|j-i|2.,1 2 3 4 5,1 0 1 0 0 0 2 1/3 1/3 1/3 0 0 3 0 1/3 1/3 1/3 0 4 0 0 1/3 1/3 1/3 5 0 0 0 1 0,改變游動的概率規(guī)則,

9、可以 得到不同方式的隨機游動和相 應的馬氏鏈.如當把點1(及5)改 為吸收壁,Q一旦到達點1(5),則 將永遠留在點1(5)上.此時相應,馬爾可夫鏈的概念及轉移概率,鏈的轉移概率矩陣只須在上述矩陣P中將第一行改為(1,0, 0,0,0),第五行改為(0,0,0,0,1)即可. 例4.2 (排隊模型) 設服務系統(tǒng),由一個服務員和只可能容納兩個人的等候 室組成,見右下圖.服務規(guī)則是: 先到先服務,后來者需在 等候室依次排隊. 假定一個需 要服務的顧客到達系統(tǒng)時, 發(fā) 現系統(tǒng)內已有3個顧客(一個正 在接受服務, 兩個在等候室排 隊),則該顧客即離去. 設時間間隔t內將有一個顧客進 入系統(tǒng)的概率為q,

10、有一原來被服務的顧客離開系統(tǒng)(即服 務完畢)的概率為p.又設當t充分小時,在這時間間隔內,等候室,服務臺,系統(tǒng),離去者,隨機 到達 者,馬爾可夫鏈的概念及轉移概率,多于一個顧客進入或離開系統(tǒng)實際上是不可能的.再設有 無顧客來到與服務是否完畢是相互獨立的. 如何用馬氏鏈描述這一服務系統(tǒng)? 設定XnX(nt),表示時間nt時系統(tǒng)內的顧客數,即 系統(tǒng)的狀態(tài).則Xn,n=0,1,2,是一隨機過程,狀態(tài)空間 I=0,1,2,3.由于當Xn=i,iI為已知時,Xn+1所處的狀態(tài) 的概率分布只與Xn=i有關,而與時間nt以前所處的狀態(tài) 無關,所以該隨機過程是一個齊次馬氏鏈. 怎樣計算此馬氏鏈的一步轉移概率?

11、 記 p00為:在系統(tǒng)內沒有顧客的條件下,經t后仍無顧客的 概率(顯然p00是條件概率,以下與此同), p00=1-q.,馬爾可夫鏈的概念及轉移概率,p01為:在系統(tǒng)內沒有顧客的條件下,經t后有一顧客進 入系統(tǒng)的概率, p01=q. p10為:系統(tǒng)內恰有一顧客正在接受服務的條件下,經t 后系統(tǒng)內無人進入的概率, 它等于在t間隔內顧客因服 務完畢而離去,且無人進入系統(tǒng)的概率, p10=p(1-q). p11為:系統(tǒng)內恰有一顧客的條件下,在t間隔內, 他因 服務完畢而離去,而另一顧客進入系統(tǒng), 或者正在接受服 務的顧客將繼續(xù)要求服務,且無人進入系統(tǒng)的概率,p11=pq +(1-p)(1-q). p

12、12為:正在接受服務的顧客將繼續(xù)要求服務, 且另一顧 客進入系統(tǒng)的概率, p12=q(1-p). p13為:正在接受服務的顧客繼續(xù)要求服務,且在t間隔,馬爾可夫鏈的概念及轉移概率,內有兩個顧客進入系統(tǒng)的概率.由假設這種情況是不可能 發(fā)生的, p13=0. 考慮到系統(tǒng)內有一顧客正在接受服務,有一顧客正在排 隊,在t間隔內顧客因服務完畢離去,但再無顧客進入;以 及系統(tǒng)內有一顧客正在接受服務,有兩顧客正在排隊, 在 t間隔內顧客因服務完畢離去, 但再無顧客進入的概率 相等,故有p21=p32=p(1-q). 又系統(tǒng)內有兩顧客,其中一人正在接受服務,在t間隔 內,他因服務完畢而離去,而另一顧客進入系統(tǒng)

13、,或者正在 接受服務的顧客將繼續(xù)要求服務,且再無人進入系統(tǒng)的概 率為:p22=pq+(1-p)(1-q). 類似地,系統(tǒng)內有兩顧客, 正在接受服務的顧客將繼續(xù),馬爾可夫鏈的概念及轉移概率,要求服務,且另一顧客進入系統(tǒng)的概率為:p23=q(1-p). 而且,顯然有:當|i-j|2時,pij=0. p33為:系統(tǒng)內有三位顧客, 或者一人將離去另一人將進 入系統(tǒng); 或者無人離開的概率, p33=pq+(1-p). 于是得該馬氏鏈的一步轉移概率矩陣: P= . 在實際問題中,一步轉移概率矩陣通?？赏ㄟ^統(tǒng)計試驗 確定.下面是一實例. 例4.3 某計算機機房的一臺計算機經常出故障,研究者每,0 1 2 3

14、,(1-q) q 0 0 p(1-q) pq+(1-p)(1-q) q(1-p) 0 0 p(1-q) pq+(1-p)(1-q) q(1-p) 0 0 p(1-q) pq+(1-p),0 1 2 3,馬爾可夫鏈的概念及轉移概率,隔15分鐘觀察一次計算機的運行狀態(tài),收集了24小時的數 據(共做97次觀察).用1表示正常狀態(tài),0表示不正常狀態(tài), 所得的數據序列為: 設Xn為第n(n=1,2,97)次觀測的計算機狀態(tài),可以認 為它是一個齊次馬氏鏈,狀態(tài)空間I=0,1.96次狀態(tài)轉移 的情況是: 00,8次;01,18次;10,18次;11,52次. 因此,一步轉移概率可用頻率近似地表示為: p00

15、=PXn+1=0|Xn=08/(8+18)=4/13, p01=PXn+1=1|Xn=018/(8+18)=9/13, p10=PXn+1=0|Xn=118/(18+52)=9/35, p11=PXn+1=1|Xn=152/(18+52)=26/35.,1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111.,0 1 0 4/13 9/13 1 9/35 26/35,P=,馬爾可夫鏈的概念及轉移概率,定理4.1 設Xn,nT是馬爾可夫鏈,則對任意整數n0

16、, 0ln和i,jI,n步轉移概率pij(n)具有下列性質: (1) pij(n)= pik(l )pkj(n-l ); (2) pij(n)= ; (3) P(n)=PP(n-1); (4) P(n)=Pn. 證明:(1)利用條件概率公式及馬爾可夫性,有 pij(n)=PXm+n=j|Xm=i= = ,馬爾可夫鏈的概念及轉移概率,= PXm+n=j|Xm+l =kPXm+l =k|Xm =i = pkj(n-l )(m+l )pik(l )(m)= pik(l )pkj(n-l ). (2)在(1)中,令l =1,k=k1,得 pij(n)= ; 這是一個遞推公式,遞推可得 pij(n)=

17、. (3)在(1)中,令l =1,利用矩陣乘法可證. (4)由(3),利用歸納法可證. 定理4.1中的(1)式,稱切普曼-柯爾莫哥洛夫(Chapman-,馬爾可夫鏈的概念及轉移概率,Kolmogorov)方程, 這一方程一般簡稱為C-K方程,它在 馬爾可夫鏈的轉移概率計算中起著重要的作用. 而(2) 式說明n步轉移概率完全由一步轉移概率決定.(4)式說 明齊次馬爾可夫鏈的n步轉移概率矩陣是一步轉移概率 矩陣的n次方. 定義4.5 設Xn,nT是馬爾可夫鏈,稱 pj=PX0=j和pj(n)=PXn=j, jI 為Xn,nT的初始概率和絕對概率,并分別稱 pj,jI和pj(n),jI 為Xn,nT

18、的初始分布和絕對分布,簡記為 pj和pj(n). 稱概率向量PT(n)=(p1(n),p2(n),)(n0)為n時刻的,馬爾可夫鏈的概念及轉移概率,絕對概率向量, 而稱 PT(0)=(p1,p2,) 為初始概率向量. 例4.4(接例4.3) 若計算機在前一段(15分鐘)的狀態(tài)為0, 問從本時段起,此計算機能連續(xù)正常工作一小時(4個時 段)的概率是多少? 解:由題意,前一時段的狀態(tài)為0,就是初始分布p0(0)=PX0 =0=1. 于是計算機能正常工作4個時段的概率為: PX0=0,X1=1,X2=1,X3=1,X4=1 =p0(0)p01(1)p11(1)p11(1)p11(1) = 0.28.

19、,馬爾可夫鏈的概念及轉移概率,關于切普曼-柯莫哥洛夫(Chapman-Kolmogorov)方程 設Xn,nT是一齊次馬氏鏈,則對任意的i,jI及T 中n0,0ln有 Pij(n)= Pik(l )Pkj(n-l ). 這一方程基于這樣的事實:“從某時刻所處的狀態(tài)i(即X =i)出發(fā), 經過時段n轉移到狀態(tài)j(即X=j)”這一事件可分 解成“從X=i出發(fā), 先經時段l 轉移到中間狀k(kI),再從 k經時段轉n-l 移到狀態(tài)j”.如下圖所示: 后一階段的狀態(tài)轉移與前一階段的狀 態(tài)轉移獨立, 所以兩個階段的轉移概率 是相乘的關系. 但經過l 步到達的狀態(tài) k不受任何限制,因而要對全部的k求和.,

20、t,o,i,k,j,:,l,n- l,n,馬爾可夫鏈的概念及轉移概率,例4.5 設Xn,n0是具有3個狀態(tài)0,1,2的齊次馬氏鏈,一 步轉移概率矩陣如右所示: 初始分布pi(0)=PX0=i=1/3,i=0,1,2. 試求(1) PX0=0,X2=1; (2) PX2=1. 解: 先求出二步轉移概率矩陣(如右下): 于是有 (1) PX0=0,X2=1 =PX0=0PX2=1|X0=0 =p0(0)p01(2)=(1/3)(5/16)=5/48; (2) p1(2)=PX2=1 =p0(0)p01(2)+p1(0)p11(2)+p2(0)p21(2) =(1/3)(5/16+1/2+9/16)

21、=11/24.,0 1 2 0 0 ,0 1 2,0 1 2 5/8 5/16 1/16 5/16 1/2 3/16 3/16 9/16 1/4,P2=,0 1 2,馬爾可夫鏈的概念及轉移概率,定理4.2 設Xn,nT為馬爾可夫鏈,則對任意jI和n 1,絕對概率pj(n)具有下列性質: (1) pj(n)= pipij(n); (2) pj(n)= pi(n-1)pij ; (3) PT(n)=PT(0)P(n); (4) PT(n)=PT(n-1)P. 證明:(1) pj(n)=PXn=j= PX0=i,Xn=j = PX0=i,Xn=j|X0=iPX0=i= pipij(n). (2) p

22、j(n)=PXn=j= PXn=j,Xn-1=i,馬爾可夫鏈的概念及轉移概率,= PXn=j|Xn-1=iPXn-1=i = pi(n-1)pij. (3)與(4)式是(1)與(2)式的矩陣形式,顯然成立. 定理4.3 設Xn,nT為馬爾可夫鏈,則對任意i1,in I和n1,有 PX1=i1,Xn=in= . 證明: 由條件概率公式及馬氏性,有 PX1=i1,Xn=in=P X0=i,X1=i1,Xn=in = PX0=i,X1=i1,Xn=in= PX0=iPX1=i1| X0=iPXn=in|X0=i,X1=i1,Xn-1=in-1,馬爾可夫鏈的概念及轉移概率,= PX0=iPX1=i1|

23、X0=iPXn=in|Xn-1=in-1 = . 定理4.2表明, 絕對概率pj(n)也具有類似于n步轉移概 率的性質.定理4.3則進一步說明,馬爾可夫鏈的有限維 分布完全由它的初始概率和一步轉移概率所決定.因此 只要知道初始概率和一步轉移概率,就可以描述馬爾可 夫鏈的統(tǒng)計特性. 3.馬爾可夫鏈的應用舉例 在討論馬爾可夫鏈的應用之前, 再對定理4.3的馬爾可 夫過程的概率意義,做一必要的說明.,馬爾可夫鏈的概念及轉移概率,對于齊次馬爾可夫鏈Xn,nT, 其有限維分布函數由 它的初始分布和一步轉移概率惟一確定. 因為: PX1=i1,X2=i2,Xn=in =P X0=i0,X1=i1,X2=i

24、2,Xn=in = PX0=i0,X1=i1,X2=i2,Xn=in = PX0=i0PX1=i1|X0=i0PXn=in|X0=i0,Xn-1=in-1 = PX0=i0PX1=i1|X0=i0PXn=in|Xn-1=in-1 = . 反之,若一個隨機變量序列Xn,nT的有限維分布由上 式給出,其中pi,iI為一概率分布, pij為轉移概率,則 Xn,nT是一馬爾可夫鏈(即具有馬爾可夫性), (pij)是 其轉移概率矩陣, pi是其初始分布.,馬爾可夫鏈的應用舉例,例4.6 (無限制隨機游動) 設質點在數軸上移動,每次移動一格, 向右移動的概率 為p,向左移動的概率q=1-p(這種運動稱無限

25、制隨機游動). 以Xn表示時刻n質點所處的位置, 則Xn,nT是一個齊次 馬爾可夫鏈.試寫出Xn,nT的一步和k步轉移概率. 解:Xn,nT的狀態(tài)空間I=0,1,2,其一步轉移 概率矩陣為: 設在第k步轉移中向右移了x 步,向左移了y步,且經過k步轉 移狀態(tài)從i進入j,則 ,從而x= ,y= .由于x,y只能,P=, q 0 p 0 0 q 0 p ,x+y=k x-y=j-i,馬爾可夫鏈的應用舉例,取整數,所以k(j-i)必為偶數. 考慮到在k步中哪x步 向右,哪y步向左是任意的,選取的方法有 種,故有 pij(k)= . 例4.7 (賭徒輸光問題) 兩賭徒甲、乙進行一系列賭博.賭徒甲有a元

26、,賭徒乙有 b元,每賭一局輸者給贏者1元,沒有和局,直到兩人中有 一人輸光為止. 設在每一局中,甲贏的概率為p,輸的概 率為q=1-p,求甲輸光的概率. 解: 與例4.1帶有兩個反射壁的一維隨機游動相比, 這個 問題實質上是帶有兩個吸收壁的隨機游動,其狀態(tài)空間 I=0,1,2,c(c=a+b). 所以問題是要求質點從a點出,pxqy, k+(j-i)為偶數 0, k+(j-i)為奇數,馬爾可夫鏈的應用舉例,發(fā)到達0狀態(tài)先于到達c狀態(tài)的概率. 解: 設ui表示甲從狀態(tài)i出發(fā)轉移到狀態(tài)0的概率,我們的 任務是計算ua. 由于0和c是 吸收狀態(tài),故u0=1, uc=0.由 條件概率公式:ui=pui

27、+1+qui-1,i=1,2,c-1.(此式的含 義是:甲從有a元開始賭博到輸光的概率等于“他接下去 贏了一局(概率為p),處于狀態(tài)i+1后再輸光”; 和“他接 下去輸了一局(概率為q), 處于狀態(tài)i-1后再輸光”這兩 個事件的和事件的概率.) 由于p+q=1,所以ui=pui+1+qui-1,i=1,2,c-1實質上 是一個差分方程: ui+1-ui=r(ui-ui-1),i=1,2,c-1.,o,a-1,a,a+1,a+b,q,p,馬爾可夫鏈的應用舉例,其中r=q/p,其邊界條件為u0=1,uc=0. 如果r=1,即p=q=1/2, 此時ui+1-ui=ui-ui-1,令i=1,2, ,c

28、-1及u1=u0+,則有 u2=u1+=u0+2, u3=u2+=u0+3, ui=ui-1+=u0+i, uc=uc-1+=u0+c. 將u0=1,uc=0代入最后一式,得參數=-1/c. 于是有 ui=1-i/c, i=1,2,c-1. 令i=a,求得甲輸光的概率: ua=1- a/c= . 此結果,馬爾可夫鏈的應用舉例,表明,在p=q的情況下(即甲、乙每局比賽中輸贏等可能) 甲輸光的概率與乙的賭本b成正比, 換言之,賭本小(對 方賭本大)者輸光的可能性大. 由于甲、乙的地位是對稱的,故乙輸光的概率為 ub= . ua+ub=1,表明甲、乙中必有一人要輸光,賭博遲早要結束. 如果r1,即p

29、q的情況,由ui+1-ui=r(ui-ui-1),i=1, 2,c-1式得 uc-uk= r(ui-ui-1)= ri(u1-u0) =(u1-1) .,馬爾可夫鏈的應用舉例,令k=0,由于uc=0,有: 1=(1-u1) ,即(1-u1)= . 代入uc-uk=(u1-1) 得 uk= ,k=1,2,c-1. 令k=a,得甲輸光的概率: ua= . 由對稱性,乙輸光的概率為: ub= ,其中r1=p/q. 由于ua+ub=1,因而在r1時,即pq時, 兩個人中也總 有一個人要輸光.,馬爾可夫鏈的應用舉例,例4.8 (天氣預報問題) 設昨日、今日都下雨,明日有雨的概率為0.7;昨日無雨, 今日

30、有雨,明日有雨的概率為0.5;昨日有雨,今日無雨,明 日有雨的概率為0.4;昨日、今日都無雨,明日有雨的概率 為0.2. 若星期一、星期二均下雨,求星期四下雨的概率. 解: 設昨日、今日連續(xù)兩天有雨稱為狀態(tài)0(RR), 昨日無 雨、今日有雨稱為狀態(tài)1(NR), 昨日有雨、今日無雨稱 為狀態(tài)2(RN), 昨日、今日無雨稱為狀態(tài)3(NN),于是天 氣預報模型可看作一個四狀態(tài)的馬爾可夫鏈,其轉移概 率為(解述中的R、N分別代表有雨和無雨): p00=PR今R明|R昨R今=P連續(xù)三天有雨 =R明|R昨R今=0.7,馬爾可夫鏈的應用舉例,p01=PN今R明|R昨R今=0(不可能事件), p02=PR今N

31、明|R昨R今=PN明|R昨R今=1-0.7=0.3, p03=PN今N明|R昨R今=0(不可能事件); 類似地,有: p10=0.5, p11=0, p12=0.5, p13=0; p20=0, p21=0.4, p22=0, p23=0.6; p30=0, p31=0.2, p32=0, p33=0.8. 并得該問題的一步轉移概率矩陣: P= = ;,p00 p01 p02 p03 p10 p11 p12 p03 p20 p21 p22 p23 p30 p31 p32 p33,0.7 0 0.3 0 0.5 0 0.5 0 0 0.4 0 0.6 0 0.2 0 0.8,馬爾可夫鏈的應用舉例

32、,和兩步轉移概率矩陣: P(2)=PP= . 星期四下雨,意味著過程所處的狀態(tài)為0(RR;RR)或1(RR, NR),故星期一、星期二連續(xù)下雨,星期四下雨的概率為 p=p00(2)+p01(2)=0.49+0.12=0.61. 例4.9 在例4.1中,設質點在線段1,4上作具有一個吸收 壁1和一個反射壁4的隨機運動, 且假設它只能在時刻n T發(fā)生移動,若以Xn表示質點在時刻n所處的位置, 則 Xn,nT是一個齊次馬爾可夫過程, 其轉移概率矩陣,0.49 0.12 0.21 0.18 0.35 0.20 0.15 0.30 0.20 0.12 0.20 0.48 0.10 0.16 0.10 0

33、.64,馬爾可夫鏈的應用舉例,為: P= 各狀態(tài)之間的轉移關系及相應的轉移概率如上圖所示. 例4.10 (生滅鏈) 觀察某種生物群體,以Xn表示在時刻n群體的數目,設為 i個數量單位, 如在時刻n+1增生到i+1個數量單位的概 率為bi,減少到i-1個數量單位的概率為ai,保持不變的 概率為ri=1-(ai+bi), 則Xn,n0為齊次馬爾可夫鏈, I=0,1,2,其轉移概率為: pij= 稱此馬氏鏈為生滅鏈.,1 0 0 0 1/3 1/3 1/3 0 0 1/3 1/3 1/3 0 0 1 0,1,2,3,4,1/3,1/3,1/3,1,1/3,1,1/3,1/3,bi, j=i+1, r

34、i, i=j, ai, j=i-1,(a0=0).,馬爾可夫鏈的狀態(tài)分類,4.2 馬爾可夫鏈的狀態(tài)分類 1.狀態(tài)的分類 假設Xn,n0是齊次馬爾可夫鏈,其狀態(tài)空間I=0,1, 2,轉移概率是pij,i,jI,初始分布為pj,jI.如 何依概率性質對狀態(tài)進行分類呢? 例4.11 設馬爾可夫鏈的狀態(tài)空間I=1,2,9, 狀態(tài)間 的轉移概率如右圖所示. 由圖可見:自狀態(tài)1出發(fā), 再返回狀態(tài)1的可能步數 (時刻)為:T=4,6,8,10, ,T的最大公約數為2,但2 T,即由1出發(fā)經2步不能 返回1. 這個2,即狀態(tài)1的周期.,1,3,7,8,9,2,6,5,4,1,1,1,1,1,1,1,1/3,1

35、,2/3,馬爾可夫鏈的狀態(tài)分類,定義4.6 若集合n|n1,pii(n)0非空, 則稱該集合的 最大公約數d=d(i)=GCDn|n1,pii(n)0為狀態(tài)i的周 期. 若d1,則稱i是周期的;若d=1,則稱i為非周期的. 由定義4.6知,如果i有周期d,則對一切非零的 n0(mod d) 都有pii(n)=0. 但這并不是說,對任意的nd,有 pii(nd)0. 這在例4.11中已經看到: 狀態(tài)1的周期d=2,而p11(2)=0. 但是,以下結論成立: 引理4.1 若狀態(tài)i的周期為d,則存在正整數M,對一切nM, 有:pii(nd)0. 證明: 設n|n1,pii(n)0=n1,n2,令,馬

36、爾可夫鏈的狀態(tài)分類,tk=GCDn1,n2,nk 則t1t2d1,故存在正整數N,使得tN=tN+1=d, 因此,d=GCDn1,n2,nN.從而存在正整數M,對一切n M,成立 nd= knk, k為正整數. 于是,當nM時 pii(nd)= = 0. 在例4.11中,n|pii(n)0=4,6,8,10,t1t2=d= 2,N=2; nd=2n=41+62即n=21+32,對1與2的各 種正整數組合,可以驗證:當M=7,n7時,恒有p11(2n)0.,馬爾可夫鏈的狀態(tài)分類,例4.12 設I=1,2,3,4, 轉移概率如圖: 考慮圖中的狀態(tài)2和3:易見狀態(tài)2與3有 相同的周期d=2. 但是,

37、從狀態(tài)3出發(fā),經2步必定返回到 3;而狀態(tài)2則不然:當2轉移到3后,便再也不能返回到2. 為區(qū)別例4.12中的狀態(tài)2和3,需要引入概念常返性. 首達概率 記fij(n)=PXm+vj,1vn-1,Xm+n=j|Xm=i,n1且 fij(0)=0. 表示質點由i出發(fā),經n步首次到達j的概率,稱首達概率. 顯然,由馬氏性和齊次性知,等式右端與m無關, 即首 達概率也可以這樣定義(由i出發(fā)在時刻n首次轉移到j): fij(n)=PXn=j,Xkj,k=1,2,n-1|X0=i,fij(0)=0.,1,2,3,4,1,1,1,1/2,1/2,馬爾可夫鏈的狀態(tài)分類,記fij= fij(n),表示質點由i

38、出發(fā)遲早轉移到j的概率. 定義4.7 稱狀態(tài)i為常返的,如果fii=1; 稱狀態(tài)i為非常返 (或滑過)的,如果fii1. 可見,若i是非常返態(tài),則由i出發(fā)將以正概率1-fii永遠 不再返回到i; 若i是常返的,則上述現象不會發(fā)生. 對 常返態(tài)i,fii(n),n1構成一概率分布.該分布的期望 值i= nfii(n),表示由i出發(fā)再返回到i的平均返回時 間. 定義4.8 若i,則稱常返態(tài)i為正常返的; 若i=, 則稱常返態(tài)i為零常返的; 非周期的正常返態(tài)稱為遍歷 狀態(tài). 對任意正整數n,首達概率與n步轉移概率有下述關系:,馬爾可夫鏈的狀態(tài)分類,定理4.4 對任意狀態(tài)i,j及1n有 pij(n)=

39、 fij(k)pjj(n-k)= fij(n-k)pjj(k). 證明: pij(n)=PXn=j|X0=i = PXvj,1vk-1,Xk=j,Xn=j|X0=i(k為首達) = PXn=j|X0=i,Xvj,1vk-1,Xk=jPXvj, 1vk-1,Xk=j|X0=i = pjj(n-k)fij(k)= fij(k)pjj(n-k). C-K方程及定理4.4中等式是馬氏鏈的關鍵公式,它們可 以把pii(n)分解成較低步的轉移概率之和的形式.,馬爾可夫鏈的狀態(tài)分類,例4.13 設I=1,2,3,4,其一步轉移概率 矩陣如右所示. 試對其狀態(tài)進行分類, 確定哪些狀態(tài)是常返態(tài),并確定其周期.

40、解: 狀態(tài)傳遞圖為: 從圖中易見,對一切n1,f44(n)=0, 即 f44=01. 因而知狀態(tài)4是非常返的. 又,f33(1)=2/3且當n2時,f33(n)=0.所以f33=2/31.從 而知狀態(tài)3也是非常返態(tài). 由f11=f11(1)+f11(2)=1/2+1/2=1(P2的(1,1)=1/2); 及 f22=f22(1)+f22(2)+=0+1/2+1/22+=(1/2)/(1-1/2)=1 知,狀態(tài)1和狀態(tài)2是常返態(tài). 從1=11/2+21/2=3/2+,2=10+21/2+31/22+,P=,1/2 1/2 0 0 1 0 0 0 0 1/3 2/3 0 1/2 0 1/2 0,1

41、,2,4,3,1,1/2,1/2,1/2,1/2,1/3,2/3,馬爾可夫鏈的狀態(tài)分類,=3+,可見常返態(tài)1和2是正常返態(tài);而且由于其周期 都為1因而是非周期的,所以狀態(tài)1和狀態(tài)2還是遍歷態(tài). 為什么2=3? 因為:當記 f(n)=21/2+31/22+41/23+51/24+61/25+n1/2n-1, g(n)=1/2+1/22+1/23+1/24+1/25+1/2n-1時, 有 f(n)-g(n)=1/2+(1/2)f(n)-n/2n-1. 即f(n)=1+2g(n)-n/2n-1并當n+時,g(n)=1,f(n)=3. 由定理4.4可以推出狀態(tài)周期的等價定義: 引理4.2 GCDn|n

42、1,pii(n)0=GCDn|n1,fii(n)0. 證明: 令 d=GCDn|n1,pii(n)0, t=GCDn|n1,fii(n)0 由定義,容易知pii(n)fii(n), 故n|n1,pii(n)0,馬爾可夫鏈的狀態(tài)分類,n|n1,fii(n)0, 從而1dt. 若t=1,則d=t=1.若t1,需要證明dt.為此只需證明t 是n|pii(n)0的公約數即可. 換言之,如若n0(mod t),則必有pii(n)=0. 由t的定義 及定理4.4中公式知,對一切nt,都有 pii(n)= fij(k)pii(n-k)=0(fij(k)=0). 今假設當n=mt+r,m=0,1,2,N-1時

43、,pii(n)=0, 則由定 理4.4、以及注意到如若n0(mod t),則fii(n)=0,我們 有: pii(Nt+r)=fii(t)pii(N-1)t+r+fii(2t)pii(N-2)t+r+ fii(Nt)pii(r)=0, 由歸納法,即知dt. 綜上所述,證得d=t.,馬爾可夫鏈的狀態(tài)分類,例4.14 設馬爾可夫鏈的狀態(tài)空間I=1,2,3,其轉移概率 矩陣如右所示.求從狀態(tài)1出發(fā),經n步 轉移到達各狀態(tài)的概率. 解: 使用fij(n)定義式計算,比較簡單. 特別通過狀態(tài)轉移圖進行計算,顯得 直接簡明. 運用歸納法,我們得: f12(n)= 同理可得: f13(n)= f11(n)=

44、,P=,0 P1 q1 q2 0 p2 p3 q3 0,1,2,3,(q1p3)m-1q1q3,n=2m,m1,(q1p3)mp1, n=2m+1,m0.,(p1q2)mp1p2,n=2m,m1,(p1q2)mq1,n=2m+1,m0.,p1(p2q3)m-1q2+q1(q3p2)m-1p3,n=2m,m1,p1(p2q3)m-1p2p3+q1(q3p2)m-1q3q2,n=2m+1,m1.,0, n=1,q1,P1,q2,p2,p3,q3,對“狀態(tài)的分類”的小結,齊次馬氏鏈的狀態(tài)分類 1.稱d=d(i)=GCDn:n1,pii(n)0為狀態(tài)i的周期. (1) d1,稱狀態(tài)i為周期的; (2)

45、 d=1,稱狀態(tài)i為非周期的. 事實. (1)若i有周期d,則對一切非零的n0(mod d)都 有pii(n)=0, 但并非對任意nd,有pii(nd)0; (2)若i的周期為d,則存在正整數M,對一切nM, 有pii(nd)0. 首達概率 fij(n)=PXn=j,Xkj,k=1,2,n-1|X0=i,fij(0)=0. 及 過程由i出發(fā),經有限步遲早到達j的概率 fij= fij(n).,對“狀態(tài)的分類”的小結,2.當fii=1時,稱狀態(tài)i是常返的;當fii1時,稱狀態(tài)i是 非常返的. 事實. (1)若i是非常返態(tài),則由i出發(fā)將以正概率1-fii 永遠不再返回到i;對常返態(tài)此現象不會發(fā)生;

46、 (2)對常返態(tài)i,fii(n),n1構成一概率分布,該 分布的期望值i= nfii(n),表示過程由i出 發(fā)再返回到i的平均返回時間. 3.設狀態(tài)i為常返態(tài),若i,則稱常返態(tài)i是正常返 的;若i=,則稱常返態(tài)i是零常返的; 非周期的正 常返態(tài)稱為遍歷狀態(tài). 事實.(1)對任意i,jI,n1有pij(n)= fij(k)pjj(n-k). (2)GCDn|n1,pii(n)0=GCDn|n1,fii(n)0.,對“狀態(tài)的分類”的小結,非常返態(tài) 狀態(tài) 零常返態(tài) 常返態(tài) 是周期的 正常返態(tài) 是非周期的 遍歷態(tài) 為什么要對馬爾可夫鏈的狀態(tài)進行分類? 對齊次馬氏鏈代表的系統(tǒng)進行研究時要討論兩個問題:

47、(1)在某一固定時刻n時的概率特性即求n步轉移概率或 絕對概率pj(n)=PXn=j(稱瞬態(tài)分析); (2)當n后系統(tǒng)的概率特性, 即n時,pij(n)的極 限是否存在, 若存在又與狀態(tài)的關系如何,極限概率能否 構成概率分布. 解決此類問題需要對狀態(tài)(狀態(tài)空間)進行分類(分解).,馬爾可夫鏈的狀態(tài)分類,2.常返性的判斷及其性質 以下討論如何用pij(n)來判別常返態(tài)和常返態(tài)的性質. 設an,n0是實數序列,考慮an,n0的母函數 A(s)= ansn. 顯然,若an,n0有界,則對一切|s|1,A(s)收斂.進而 如果an,n0與bn,n0的母函數分別是A(s)和B(s), 且對一切|s|1收

48、斂,則an,n0與bn,n0的卷積 Cn= anbn-k,n=0,1,2, 的母函數C(s)=A(s)B(s). 定理4.5 狀態(tài)i常返的充要條件是 pii(n)=.,馬爾可夫鏈的狀態(tài)分類,如i非常返,則 pii(n)= . 證明: 規(guī)定 pii(0)=1, fii(0)=0. 由定理4.4知 pii(n)= pii(k)fii(n-k),n1. 兩邊同乘sn,并對n1求和.記pii(n)與fii(n)的母函 數分別為P(s)和F(s),與段比較,得 P(s)-1=P(s)F(s). 注意到0s1時, F(s)fii1. 因此 P(s)= ,0s1.,馬爾可夫鏈的狀態(tài)分類,考慮到對任意正整數N

49、都有 pii(n)snP(s) pii(n),0s1 且當s1時P(s)不減,故在上式中可先取s1,再令N ,便有 lim P(s)= pii(n). 同理可得 lim F(s)= fii(n)=fii. 于是,在式中,令s1,即有定理4.5的結論(對常返和 非常返). 定理4.5表示,當i常返時,返回i的次數是無限多次; 當 i非常返時,返回i的次數只能有限多次. 為了進一步深化刻畫該特性,以下給出超限概率的概念.,s1,s1,馬爾可夫鏈的狀態(tài)分類,超限概率 gij=P有無限多個n使Xn=j|X0=i Pi有無限多個n使Xn=j =Pi (Xn=j). 引理4.3 對任意狀態(tài)i,有 gij=

50、 證明: 令Ak=e|至少有k個n使Xn(e)=j,易見Ak+1 Ak. 并 有 lim Pi(Ak)=gij. 另一方面Pi(Ak+1)=Pi (Xvj,0vm,Xm=j且至少有 k個n使Xm+n=j)= Pi(Xvj,0vm,Xm=j)Pj(至少有,fij, 若j是常返態(tài), 0, 若j是非常返態(tài).,k,馬爾可夫鏈的狀態(tài)分類,k個n使Xn=j)= fij(m)Pj(Ak)=fijPj(Ak). 由i的任意性, 反復迭代式并注意到Pj(A1)=fjj, 有 Pi(Ak+1)=fijfjj Pj(Ak-1)=fij(fjj )k. 令k,由式及式,便有 gij= 由以上引理4.3,得: 定理4.

51、6 狀態(tài)i常返,當且僅當gii=1; 若狀態(tài)i非常返,則 gii=0. 對于常返態(tài)i,如何判別它是遍歷的或零常返的呢? 定理4.7 設i常返且有周期d,則lim pij(nd)= ,其中i,fij, 若fjj=1, 0, 若fjj1.,n,馬爾可夫鏈的狀態(tài)分類,為i的平均返回時間.當i 為時, =0. 推論 設i常返,則 (1)i零常返 lim pii(n)=0; (2)i遍歷 lim pii(n)= 0. 證明:(1)若i零常返,由定理4.7知lim pii(nd)=0.但當n 0(mod d)時,pii(n)=0.故lim pii(n)=0.反之若lim pii(n) =0,而i是正常返,

52、則由定理4.7得lim pii(nd)0. 矛盾. (2)設lim pii(n)= 0,這說明i為正常返且lim pii(nd) = .與定理4.7比較得d=1.故i遍歷. 反之,由定理4.7 即知.,n,n,n,n,n,n,n,n,定理證明參見毛用才,胡奇英 隨機過程定理5.3.2,P112-113,馬爾可夫鏈的狀態(tài)分類,可達與互通 稱狀態(tài)i可達狀態(tài)j,記為ij,如果存在n0使pij(n) 0; 稱狀態(tài)i與狀態(tài)j互通,記為i j,如果ij且ji. 定理4.8 可達關系與互通關系都具有傳遞性,即 (1) 若ij,jk,則ik; (2) 若i j,j k,則i k. 證明: (1)設ij,則存在

53、s1,有pij(s)0;設jk,則存 在t1,有pjk(t)0. 由C-K方程 pik(s+t)= pil(s)pl k(t)pij(s)pjk(t)0. 注意到s+t1,故有ik. (2)將可達關系的證明,正向用一次,反向再用一次 就是對互通關系傳遞性的證明.,(因而互通關系是等價關系),馬爾可夫鏈的狀態(tài)分類,互通關系具有相同的類型 定理4.9 若i j,則 (1)i與j同為常返態(tài)或非常返態(tài),若為常返態(tài),則 它們同為正常返態(tài)或零常返態(tài); (2)i與j有相同的周期. 證明:(1)設i j,則由可達定義知,存在l 1和n1,使有 pij(l )=0, pji(n)=0. 由C-K方程,知有 pi

54、i(l +m+n)pij(l )pjj(m)pji(n)=pjj(m), pjj(n+m+l)pji(n)pii(m)pij(l )=pii(m). 將以上兩式的兩邊關于m從1到求和,得,馬爾可夫鏈的狀態(tài)分類,Pii(l +m+n) Pjj(m); Pjj(l +m+n) Pii(m). 可見, Pii(k)與Pjj(k)相互控制,所以它們同為無窮或同為有限.由定理4.5知,i,j同為常返或同為非常返. 對與兩式的兩邊分別關于m取極限,又有 lim Pii(l +m+n)lim Pjj(m); lim Pjj(l +m+n)lim Pii(m). 可見,lim Pii(k)與lim Pjj(k

55、)同為零或同為正. 由定理 4.7的推論知,i,j同為零常返或同為正常返.,m,m,m,m,m,m,馬爾可夫鏈的狀態(tài)分類,(2)仍令pij(l )=0, pji(n)=0. 設i的周期為d,j的周期為t. 由(1)證中的式知,對 任一使pjj(m)0的m,必有pii(l +m+n)0,從而d除盡l +m+ n, 但 pii(l +n)pij(l )pji(n)=0. 所以d也能除盡l +n.于是d就可除盡m,此說dt.利用 式,類似可證dt. 因而得d=t. 例4.15 設馬氏鏈Xn的狀態(tài)空間I=0,1,2,轉移概 率為p00=1/2,pi,i+1=1/2, pi0=1/2,iI. 考察狀態(tài)0

56、的常返性、周期性和遍歷性.,1,0,2,3,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,馬爾可夫鏈的狀態(tài)分類,解: 由題圖知: f00(1)=1/2, f00(2)=(1/2)(1/2)=1/4, f00(3)=(1/2)(1/2)(1/2)=1/8, 一般,有 f00(n)=1/(2n). 故 f00= 1/(2n)=1, 0= n2-n. 可見0為正常 返狀態(tài); 由于f00(1)=1/20, 所以0是非周期的; 因 而是遍歷的. 對其它狀態(tài)i求fii(n)比較煩瑣.但利用定理4.9,由i 0 即知i也是遍歷的. 換言之對互通狀態(tài)的識別,只需對最簡單的狀態(tài)進行判 斷即可. 例1.16 設Xn為生滅鏈(例4.10),其中X0=1,ai0(i1),馬爾可夫鏈的狀態(tài)分類,bi0(i0).如果 =, 則Xn的所有狀態(tài)都是常返的. 解: 實際上Xn的狀態(tài)是互通的.所以我們只需驗證狀態(tài) 0是常返的. 定義:j=minn|Xn=j. 對固定的狀態(tài)k,記 U(i)=Pi(0k)P(0k|X0=i), 0ik. 則由條件概率公式 U(i)=biU(i+1)+aiU(i-1)+riU(i), 0ik. 因為ri=1-ai-bi,故而上