隨機(jī)過(guò)程Ch4_馬爾可夫鏈

1、第四章 馬爾可夫鏈14.1 馬爾可夫鏈與轉(zhuǎn)移概率 定義 設(shè) X(t)，t T 為隨機(jī)過(guò)程，若對(duì)任意正整數(shù)n及t1 t20，且條件分布PX(tn)xn|X(t1)=x1, X(tn-1)=xn-1= PX(tn) xn|X(tn-1)=xn-1，則稱(chēng)X(t)，t T 為馬爾可夫過(guò)程。若t1,t2,tn-2表示過(guò)去，tn-1表示現(xiàn)在，tn表示將來(lái)，馬爾可夫過(guò)程表明：在已知現(xiàn)在狀態(tài)的條件下，將來(lái)所處的狀態(tài)與過(guò)去狀態(tài)無(wú)關(guān)。24.1 馬爾可夫鏈與轉(zhuǎn)移概率常見(jiàn)馬爾可夫過(guò)程通常有三類(lèi)：(1)時(shí)間、狀態(tài)都是離散的，稱(chēng)為馬爾可夫鏈(2)時(shí)間連續(xù)、狀態(tài)離散的，稱(chēng)為連續(xù)時(shí)間馬爾可夫鏈(3)時(shí)間、狀態(tài)都是連續(xù)的，稱(chēng)為

2、馬爾可夫過(guò)程（時(shí)間離散、狀態(tài)連續(xù)的馬爾可夫過(guò)程，通常用泛函中二元函數(shù)的范數(shù)進(jìn)行研究）3隨機(jī)過(guò)程Xn，nT ，參數(shù)T=0, 1, 2, ,狀態(tài)空間I=i0, i1, i2, 定義 若隨機(jī)過(guò)程Xn，nT ，對(duì)任意nT和i0,i1,in+1 I，條件概率PXn+1=in+1|X0=i0,X1=i1,Xn=in = PXn+1=in+1|Xn=in， 則稱(chēng)Xn，nT 為馬爾可夫鏈，簡(jiǎn)稱(chēng)馬氏鏈。4.1 馬爾可夫鏈與轉(zhuǎn)移概率44.1 馬爾可夫鏈與轉(zhuǎn)移概率馬爾可夫鏈的性質(zhì) PX0=i0, X1=i1, , Xn=in=PXn=in|X0=i0, X1=i1, , Xn-1=in-1 PX0=i0, X1=i

3、1, , Xn-1=in-1= PXn=in|Xn-1=in-1 PXn-1=in-1 |X0=i0,X1=i1,Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2=PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-254.1 馬爾可夫鏈與轉(zhuǎn)移概率=PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX1=i1|X0=i0PX0=i0 馬爾可夫鏈的統(tǒng)計(jì)特性完全由條件概率PXn+1=in+1|Xn=in確定。64.1 馬爾可夫鏈與轉(zhuǎn)移概率定義 稱(chēng)條件概率pij(n)= PXn+1=j|Xn

4、=i 為馬爾可夫鏈Xn，nT 在時(shí)刻n的一步轉(zhuǎn)移概率，簡(jiǎn)稱(chēng)轉(zhuǎn)移概率，其中i,jI。定義 若對(duì)任意的i,jI，馬爾可夫鏈Xn,nT 的轉(zhuǎn)移概率pij(n)與n無(wú)關(guān)，則稱(chēng)馬爾可夫鏈?zhǔn)驱R次的，并記pij(n)為pij。齊次馬爾可夫鏈具有平穩(wěn)轉(zhuǎn)移概率，狀態(tài)空間I=1, 2, 3, ，一步轉(zhuǎn)移概率為74.1 馬爾可夫鏈與轉(zhuǎn)移概率轉(zhuǎn)移概率性質(zhì)(1) (2) P稱(chēng)為隨機(jī)矩陣8Markov過(guò)程狀態(tài)為已知的條件下, 過(guò)程在時(shí)刻tt0所處狀態(tài)的條件分布與過(guò)程在時(shí)刻t0之前所處的狀態(tài)無(wú)關(guān). 無(wú)后效性亦稱(chēng)馬爾可夫性. 無(wú)后效性是說(shuō),在已知過(guò)程“現(xiàn)在”的條件下, 過(guò)程的“將來(lái)”與過(guò)程的“過(guò)去”無(wú)關(guān),只與“現(xiàn)在”有關(guān).如

5、何辨識(shí)馬爾可夫過(guò)程?1.若X(t),tT是一獨(dú)立隨機(jī)過(guò)程,且對(duì)于n個(gè)t1,t2,tnT,隨機(jī)變量X(t1),X(t2),X(tn)總體獨(dú)立,則X(t),tT是馬爾可夫過(guò)程. 因?yàn)橛蓷l件,隨機(jī)事件X(t1)=x1,X(t2)=x2,X(tn)=xn,X(t)x相互獨(dú)立,故有PX(t)x|X(t1)=x1,X(t2)=x2,X(tn)=xn=PX(t)x=PX(t)x|X(tn)=xn. 類(lèi)似以上的討論,還有9Markov過(guò)程2. 設(shè)狀態(tài)空間I為實(shí)數(shù)集合R,Y(n),n1是獨(dú)立隨機(jī)序列,令X(1)=Y(1),X(n)= Y(k),則X(n),n1是馬爾可夫過(guò)程.3. 若X(t),tT是一獨(dú)立增量過(guò)

6、程, 且PX(0)=x0=1(是常數(shù)),則X(t),tT是馬爾可夫過(guò)程.馬爾可夫鏈的概念.泊松過(guò)程,維納過(guò)程都是時(shí)間連續(xù)的馬爾可夫過(guò)程.4. 馬爾可夫過(guò)程Xn,nT的參數(shù)集T=0,1,2,狀態(tài)集I=i1,i2,可以是0,1,2,或0,1,2,或0,1,2,n. 在以上設(shè)定下,稱(chēng)隨機(jī)過(guò)程Xn,nT為馬爾可夫鏈或馬氏鏈,如果對(duì)于任意的整數(shù)nT和任意的i0,i1,in+1I,10Markov過(guò)程有PXn+1=in+1|X0=i0,X1=i1,X2=i2,Xn=in=PXn+1=in+1|Xn=in.5. 條件概率pij(m)=PXm+1=j|Xm=i稱(chēng)為馬氏鏈Xn,nT在時(shí)刻m的一步轉(zhuǎn)移概率. 條件

7、概率pij(k)(m)=PXm+k=j|Xm=i稱(chēng)為馬氏鏈Xn,nT在時(shí)刻m的k步轉(zhuǎn)移概率.6.馬爾可夫鏈Xn,nT的轉(zhuǎn)移概率pij(k)(m)具有性質(zhì): (1) pij(k)(m)0, i,jI; (2) pij(k)(m)=1, i,jI且規(guī)定pij(0)(m)=7. 如果對(duì)于任意的i,jI,馬爾可夫鏈Xn,nT的轉(zhuǎn)移概率只與i,j有關(guān),而與時(shí)刻n無(wú)關(guān),則稱(chēng)Xn,nT是時(shí)齊的或齊次的,并記pij(m)=pij.1, i=j,0, ij.11Markov過(guò)程8. 一步轉(zhuǎn)移概率pij所排成的矩陣稱(chēng)為轉(zhuǎn)移概率矩陣. 轉(zhuǎn)移概率矩陣具有性質(zhì): (1) P(n)=PP(n-1); (2) P(n)=P

8、n.9. 切普曼-柯?tīng)柲缏宸?Chapman-Kolmogorov)方程: 對(duì)于任意正整數(shù)s,t有 pij(s+t)(u+v)= pir(s)(u)prj(t)(v).10. 設(shè)Xn,nT為馬爾可夫鏈,稱(chēng) pj=PX0=j和pj(n)=PXn=j,jI為Xn,nT的初始概率和絕對(duì)概率, 并分別稱(chēng)pj,jI和pj(n),jI為Xn,nT的初始分布和絕對(duì)分布,簡(jiǎn)記為pj和pj(n).p11 p12 p1n p21 p22 p2n pn1 pn2 pnn P=12Markov過(guò)程稱(chēng)概率向量PT(n)=(p1(n),p2(n),), n0,為n時(shí)刻的絕對(duì)概率向量. 稱(chēng)PT(0)=(p1,p2,)為初

9、始概率向量. 對(duì)于任意jI和n1,絕對(duì)概率pj(n)具有性質(zhì): pj(n)= pi(n-1)pij.絕對(duì)概率向量具有性質(zhì): (1) PT(n)=PT(0)P(n); (2) PT(n)=PT(n-1)P.11.設(shè)Xn,nT為馬爾可夫鏈,則對(duì)任意的i1,i2,inI和n1有 PX1=i1,X2=i2,Xn=in= .134.1 馬爾可夫鏈與轉(zhuǎn)移概率例4.1 賭博問(wèn)題。甲乙二人進(jìn)行一系列賭博，甲有a元，乙的賭本無(wú)限，每賭一局輸者給贏者1元，沒(méi)有和局，如果甲輸光，再輸則賭本為負(fù)。設(shè)在每一局中，甲贏的概率為p，輸?shù)母怕蕿閝=1-p。設(shè)Xn表示第n次賭博結(jié)束后甲的賭本，則Xn，n1是馬爾科夫鏈，求Xn的

10、轉(zhuǎn)移矩陣144.1 馬爾可夫鏈與轉(zhuǎn)移概率例4.1 無(wú)限制隨機(jī)游動(dòng)q p-1 0 1 i-1 i i+1 一步轉(zhuǎn)移概率:154.1 馬爾可夫鏈與轉(zhuǎn)移概率n步轉(zhuǎn)移概率:i經(jīng)過(guò)k步進(jìn)入j,向右移了x步,向左移了y步則164.1 馬爾可夫鏈與轉(zhuǎn)移概率例4.4 具有吸收壁和反射壁的隨機(jī)游動(dòng)狀態(tài)空間1,2,3,4，1為吸收壁，4為反射壁 狀態(tài)轉(zhuǎn)移圖 狀態(tài)轉(zhuǎn)移矩陣174.1 馬爾可夫鏈與轉(zhuǎn)移概率定義 稱(chēng)條件概率 = PXm+n=j|Xm=i 為馬爾可夫鏈Xn，nT 的n步轉(zhuǎn)移概率(i,jI, m0, n1)。n步轉(zhuǎn)移矩陣其中 P(n)也為隨機(jī)矩陣184.1 馬爾可夫鏈與轉(zhuǎn)移概率定理4.1 設(shè)Xn，nT 為馬

11、爾可夫鏈，則對(duì)任意整數(shù)n0,0l0 (最大公約數(shù)greatest common divisor)如果d1，就稱(chēng)i為周期的，如果d=1，就稱(chēng)i為非周期的484.2 馬爾可夫鏈的狀態(tài)分類(lèi)例4.6 設(shè)馬爾可夫鏈的狀態(tài)空間I=1,2,9，轉(zhuǎn)移概率如下圖 從狀態(tài)1出發(fā)再返回狀態(tài)1的可能步數(shù)為T(mén)=4,6,8,10, ，T的最大公約數(shù)為2，從而狀態(tài)1的周期為2494.2 馬爾可夫鏈的狀態(tài)分類(lèi)注(1)如果i有周期d，則對(duì)一切非零的n, n0 mod d，有 （若 ，則n=0 mod d ） (2)對(duì)充分大的n， （引理4.1）例題中當(dāng)n=1時(shí)， 當(dāng)n1時(shí)，504.2 馬爾可夫鏈的狀態(tài)分類(lèi)例4.7 狀態(tài)空間I=

12、1,2,3,4，轉(zhuǎn)移概率如圖， 狀態(tài)2和狀態(tài)3有相同的周期d=2，但狀態(tài)2和狀態(tài)3有顯著的區(qū)別。當(dāng)狀態(tài)2轉(zhuǎn)移到狀態(tài)3后，再不能返回到狀態(tài)2，狀態(tài)3總能返回到狀態(tài)3。這就要引入常返性概念。514.2 馬爾可夫鏈的狀態(tài)分類(lèi)由i出發(fā)經(jīng)n步首次到達(dá)j的概率(首達(dá)概率)規(guī)定由i出發(fā)經(jīng)有限步終于到達(dá)j的概率524.2 馬爾可夫鏈的狀態(tài)分類(lèi) 若fii=1，稱(chēng)狀態(tài)i為常返的； 若fii1，稱(chēng)狀態(tài)i為非常返的i為非常返，則以概率1- fii不返回到ii為常返，則 構(gòu)成一概率分布，期望值 表示由i出發(fā)再返回到i的平均返回時(shí)間定義534.2 馬爾可夫鏈的狀態(tài)分類(lèi) 若i ，則稱(chēng)常返態(tài)i為正常返的; 若 i =，則稱(chēng)常

13、返態(tài)i為零常返的， 非周期的正常返態(tài)稱(chēng)為遍歷狀態(tài)。例：判斷下面馬氏鏈各狀態(tài)的類(lèi)型定義設(shè)i為常返544.2 馬爾可夫鏈的狀態(tài)分類(lèi)引理4.2 周期的等價(jià)定義G.C.D =G.C.D例4.8 設(shè)馬爾可夫鏈的狀態(tài)空間I=1,2,3，轉(zhuǎn)移概率矩陣為 求從狀態(tài)1出發(fā)經(jīng)n 步轉(zhuǎn)移首次到達(dá)各狀態(tài)的概率554.2 馬爾可夫鏈的狀態(tài)分類(lèi)解 狀態(tài)轉(zhuǎn)移圖如下 ，首達(dá)概率為 564.2 馬爾可夫鏈的狀態(tài)分類(lèi)同理可得574.2 馬爾可夫鏈的狀態(tài)分類(lèi)首達(dá)概率 與n步轉(zhuǎn)移概率 有如下關(guān)系式定理4.4 對(duì)任意狀態(tài)i, j及1 n ，有584.2 馬爾可夫鏈的狀態(tài)分類(lèi)證P(A,B|C)= P(B|A,C) P(A|C)59123

14、11例：已知馬氏鏈轉(zhuǎn)移圖如下，求從狀態(tài)1出發(fā)再返回1的n步轉(zhuǎn)移概率，n=1,2,8604.2 馬爾可夫鏈的狀態(tài)分類(lèi)定理4.5 狀態(tài)i常返的充要條件為如i非常返，則以下討論常返性的判別與性質(zhì)614.2 馬爾可夫鏈的狀態(tài)分類(lèi)數(shù)列的母函數(shù)與卷積an,n0為實(shí)數(shù)列，母函數(shù)bn,n0為實(shí)數(shù)列，母函數(shù)則an與bn的卷積的母函數(shù)624.2 馬爾可夫鏈的狀態(tài)分類(lèi)定理4.5 狀態(tài)i常返的充要條件為如i非常返，則證: 規(guī)定 ，則由定理4.4634.2 馬爾可夫鏈的狀態(tài)分類(lèi)644.2 馬爾可夫鏈的狀態(tài)分類(lèi)對(duì)0s1654.2 馬爾可夫鏈的狀態(tài)分類(lèi)664.2 馬爾可夫鏈的狀態(tài)分類(lèi)定理4.7 設(shè)i常返且有周期為d，則其中

15、i為i的平均返回時(shí)間，當(dāng)i=時(shí)推論 設(shè)i常返，則(1) i零常返(2) i遍歷6712311例：已知馬氏鏈轉(zhuǎn)移圖如下，求從狀態(tài)1出發(fā)再返回1的n步轉(zhuǎn)移概率，n=1,2,8684.2 馬爾可夫鏈的狀態(tài)分類(lèi)證(1)i零常返， i=，由定理4.7知，對(duì)d的非整數(shù)倍數(shù)的n， 從而子序列 i是零常返的694.2 馬爾可夫鏈的狀態(tài)分類(lèi)(2) 子序列所以d=1，從而i為非周期的，i是遍歷的i是遍歷的，d=1，i，704.2 馬爾可夫鏈的狀態(tài)分類(lèi)例4.10 對(duì)無(wú)限制隨機(jī)游動(dòng)由斯特林近似公式可推出(1)當(dāng)且僅當(dāng)p=q=1/2時(shí)，4pq=1714.2 馬爾可夫鏈的狀態(tài)分類(lèi)狀態(tài)i是常返的狀態(tài)i是零常返的724.2

16、馬爾可夫鏈的狀態(tài)分類(lèi)(2)當(dāng)且僅當(dāng)pq，4pq0,使?fàn)顟B(tài)i與狀態(tài)j互通，ij：ij且ji 定理4.8 可達(dá)關(guān)系與互通關(guān)系都具有傳遞性，即(1)若ij ，jk，則ik(2)若i j ，j k，則i k4.3 狀態(tài)空間的分解754.2 馬爾可夫鏈的狀態(tài)分類(lèi)證 (1)ij ，存在l 0，使 jk，存在m 0，使由C-K方程所以ik(2)由(1)直接推出764.2 馬爾可夫鏈的狀態(tài)分類(lèi)定理4.9 如ij，則 (1) i與j同為常返或非常返，如為常返，則它們同為正常返或零常返(2) i與j有相同的周期774.2 馬爾可夫鏈的狀態(tài)分類(lèi) 例4.9 設(shè)馬氏鏈Xn的狀態(tài)空間為 I=0,1,2,，轉(zhuǎn)移概率為考察狀

17、態(tài)0的類(lèi)型784.2 馬爾可夫鏈的狀態(tài)分類(lèi) 可得出0為正常返的由于 ，所以0的周期為d=10為非周期的，從而為遍歷狀態(tài)對(duì)于其它狀態(tài)i,由于i0,所以也是遍歷的 794.3 狀態(tài)空間的分解定義 狀態(tài)空間I 的子集C稱(chēng)為閉集，如對(duì)任意iC及kC都有pik=0; 閉集C稱(chēng)為不可約的，如C的狀態(tài)互通； 馬氏鏈Xn稱(chēng)為不可約的，如其狀態(tài)空間不可約引理4.4 C是閉集的充要條件為對(duì)iC及kC都有804.3 狀態(tài)空間的分解證 充分性顯然成立必要性（數(shù)學(xué)歸納法）設(shè)C為閉集，由定義當(dāng)n=1時(shí)結(jié)論成立設(shè)n=m時(shí)， ，iC及kC ，則注：如pii=1，稱(chēng)狀態(tài)i為吸收的，等價(jià)于 單點(diǎn)集i為閉集。814.3 狀態(tài)空間的

18、分解 例4.11 設(shè)馬氏鏈Xn的狀態(tài)空間為 I=1, 2, 3, 4, 5，轉(zhuǎn)移概率矩陣為狀態(tài)3是吸收的，故3是閉集，1,4，1,3,4，1,2,3,4都是閉集，其中3，1,4是不可約的。I含有閉子集，故Xn不是不可約的鏈。824.3 狀態(tài)空間的分解 例4.12 無(wú)限制隨機(jī)游動(dòng)為不可約馬氏鏈，各狀態(tài)的周期為2，當(dāng)p=q=1/2時(shí)，是零常返的，當(dāng)pq時(shí)，是非常返的。834.3 狀態(tài)空間的分解定理4.10 任一馬氏鏈的狀態(tài)空間I，可唯一地分解成有限個(gè)或可列個(gè)互不相交的子集D,C1,C2,之和，使得：(1)每一Cn是常返態(tài)組成的不可約閉集；(2)Cn中的狀態(tài)同類(lèi)型，或全是正常返，或全是零常返，它們有

19、相同的周期，且fij=1，i,jCn；(3)D由全體非常返態(tài)組成，自Cn中狀態(tài)不能到達(dá)D中的狀態(tài)。844.3 狀態(tài)空間的分解 例4.13 馬氏鏈的狀態(tài)空間I =1,2,3,4,5,6,狀態(tài)轉(zhuǎn)移矩陣為分解此鏈并指出各狀態(tài)的常返性及周期性。854.3 狀態(tài)空間的分解解 由狀態(tài)轉(zhuǎn)移圖知可見(jiàn)1為正常返狀態(tài)且周期為3，含1的基本常返閉集為 C1=k:1k=1,3,5，從而狀態(tài)3及5也為正常返狀態(tài)且周期為3。同理可知6為正常返狀態(tài)，6=3/2，周期為1。含6的基本常返閉集為 C2=k:6k =2,6，可見(jiàn)2，6為遍歷狀態(tài)。864.3 狀態(tài)空間的分解 于是I可分解為 I=DC1C2 =41,3,52,6定義

20、4.10 稱(chēng)矩陣A=(aij)為隨機(jī)矩陣，若顯然k步轉(zhuǎn)移矩陣 為隨機(jī)矩陣。874.3 狀態(tài)空間的分解引理4.5 設(shè)C為閉集，G是C上所得的k步轉(zhuǎn)移子矩陣，則G仍是隨機(jī)矩陣。證 任取iC，由引理4.4有從而且 ，故 是隨機(jī)矩陣。884.3 狀態(tài)空間的分解注：對(duì)I的一個(gè)閉子集，可考慮C上的原馬氏鏈的子馬氏鏈，其狀態(tài)空間為C，轉(zhuǎn)移矩陣為G=(pij)，i,jC是原馬氏鏈的轉(zhuǎn)移矩陣為P=(pij)，i,jI的子矩陣。894.3 狀態(tài)空間的分解定理4.11 周期為d的不可約馬氏鏈，其狀態(tài)空間C可唯一地分解為d個(gè)互不相交的子集之和，即 且使得自Gr中任一狀態(tài)出發(fā)，經(jīng)一步轉(zhuǎn)移必進(jìn)入Gr+1中(Gd = G0

21、)。注：任取一狀態(tài)i，對(duì)每一r=0,1,d-1定義集9012311例：已知馬氏鏈轉(zhuǎn)移圖如下，求從狀態(tài)1出發(fā)再返回1的n步轉(zhuǎn)移概率，n=1,2,8914.3 狀態(tài)空間的分解 例4.14 設(shè)不可約馬氏鏈的狀態(tài)空間為C=1, 2, 3, 4, 5, 6，轉(zhuǎn)移矩陣為924.3 狀態(tài)空間的分解934.3 狀態(tài)空間的分解由狀態(tài)轉(zhuǎn)移圖可知各狀態(tài)的周期d=3,固定狀態(tài)i=1，令故C=G0G1G2 =1,4,63,52944.3 狀態(tài)空間的分解定理4.12 設(shè)Xn,n0是周期為d的不可約馬氏鏈，則在定理4.11的結(jié)論下有(1)如只在0,d,2d,上考慮Xn，即得一新馬氏鏈Xnd ，其轉(zhuǎn)移矩陣 ，對(duì)此新鏈，每一Gr是不可約閉集，且Gr中的狀態(tài)