馬爾可夫過(guò)程

1、Markov過(guò)程過(guò)程第一節(jié)第一節(jié) 基本概念基本概念第二節(jié)第二節(jié) MarkovMarkov鏈的狀態(tài)分類(lèi)及性質(zhì)鏈的狀態(tài)分類(lèi)及性質(zhì)第三節(jié)第三節(jié) 極限定理及平穩(wěn)分布極限定理及平穩(wěn)分布 安德雷安德雷. .安德耶維奇安德耶維奇. .馬爾可夫馬爾可夫 (A.A.Markov): 俄數(shù)學(xué)家，俄數(shù)學(xué)家，18561922 概率和統(tǒng)計(jì)領(lǐng)域?qū)＜?。概率和統(tǒng)計(jì)領(lǐng)域?qū)＜摇?當(dāng)年當(dāng)年MarkovMarkov研究普希金詩(shī)歌里元音字母和輔音字母研究普希金詩(shī)歌里元音字母和輔音字母交替出現(xiàn)的規(guī)律時(shí)提出了交替出現(xiàn)的規(guī)律時(shí)提出了MarkovMarkov過(guò)程的數(shù)學(xué)模型過(guò)程的數(shù)學(xué)模型. . MarkovMarkov過(guò)程過(guò)程8080年代興起，

2、在現(xiàn)代工程、自然科學(xué)、年代興起，在現(xiàn)代工程、自然科學(xué)、社會(huì)科學(xué)中應(yīng)用廣泛。社會(huì)科學(xué)中應(yīng)用廣泛。Markov過(guò)程過(guò)程n例：例：A： 過(guò)紅綠燈過(guò)紅綠燈 紅燈停紅燈停 綠燈行綠燈行B：下棋：下棋 當(dāng)前棋局當(dāng)前棋局 棋風(fēng)棋風(fēng)下一步的招法下一步的招法n將來(lái)的選擇將來(lái)的選擇不僅與不僅與目前的狀態(tài)目前的狀態(tài)有關(guān)，還和該過(guò)有關(guān)，還和該過(guò)程的程的過(guò)去狀態(tài)過(guò)去狀態(tài)有關(guān)。有關(guān)。第一節(jié)第一節(jié) 基本概念基本概念n根據(jù)當(dāng)前過(guò)程的概率分布而計(jì)算未來(lái)時(shí)刻的概率根據(jù)當(dāng)前過(guò)程的概率分布而計(jì)算未來(lái)時(shí)刻的概率分布。分布。1. 1. 馬爾可夫過(guò)程概念馬爾可夫過(guò)程概念所所處處的的狀狀態(tài)態(tài)為為已已知知的的在在時(shí)時(shí)刻刻系系統(tǒng)統(tǒng)過(guò)過(guò)程程或或0

3、)(t所所處處狀狀態(tài)態(tài)的的條條件件分分布布與與過(guò)過(guò)程程在在時(shí)時(shí)刻刻條條件件下下0,tt 特特性性稱(chēng)稱(chēng)為為之之前前所所處處的的狀狀態(tài)態(tài)無(wú)無(wú)關(guān)關(guān)的的與與過(guò)過(guò)程程在在時(shí)時(shí)刻刻0t馬爾可夫性馬爾可夫性. .具有馬爾可夫性的隨機(jī)過(guò)程稱(chēng)為具有馬爾可夫性的隨機(jī)過(guò)程稱(chēng)為馬爾可夫過(guò)程馬爾可夫過(guò)程. .即即: : 過(guò)程過(guò)程“將來(lái)將來(lái)”的情況與的情況與“過(guò)去過(guò)去”的情況是無(wú)的情況是無(wú)關(guān)的，和關(guān)的，和現(xiàn)在現(xiàn)在有關(guān)有關(guān)直線上的隨機(jī)游動(dòng)直線上的隨機(jī)游動(dòng) 布朗運(yùn)動(dòng)布朗運(yùn)動(dòng)用分布函數(shù)表述馬爾可夫過(guò)程用分布函數(shù)表述馬爾可夫過(guò)程,),(:的的狀狀態(tài)態(tài)空空間間隨隨機(jī)機(jī)過(guò)過(guò)程程設(shè)設(shè)TttXI ,個(gè)個(gè)數(shù)數(shù)值值的的任任意意如如果果對(duì)對(duì)時(shí)

4、時(shí)間間nt, 3,21Ttntttin 恰有恰有)(,)(,)(|)(112211 nnnnxtXxtXxtXxtXP ,)(|)(11RxxtXxtXPnnnnn 2021-7-86 時(shí)間時(shí)間離散離散狀態(tài)狀態(tài)離散離散的的馬爾科夫鏈馬爾科夫鏈 時(shí)間時(shí)間離散離散狀態(tài)狀態(tài)連續(xù)連續(xù)的馬爾科夫序列的馬爾科夫序列 時(shí)間時(shí)間連續(xù)連續(xù)狀態(tài)狀態(tài)連續(xù)連續(xù)的馬爾科夫過(guò)程的馬爾科夫過(guò)程 時(shí)間時(shí)間連續(xù)連續(xù)狀態(tài)狀態(tài)離散離散的（的（連續(xù)時(shí)間的連續(xù)時(shí)間的） 馬爾科夫鏈馬爾科夫鏈MarkovMarkov過(guò)程過(guò)程n馬爾可夫鏈馬爾可夫鏈一、一、MarkovMarkov鏈的定義鏈的定義設(shè)隨機(jī)過(guò)程)(tX,Tt ，若對(duì)任一時(shí)刻 n，

5、以及任意狀態(tài)jiiiin,110，有,) 1(,)(|) 1(1ninXinXjnXP) 0 (,) 1 (,01iXiX)(|) 1(inXjnXP轉(zhuǎn)移概率轉(zhuǎn)移概率np pij ij(n) (n) 不僅與狀態(tài)不僅與狀態(tài) i i , j , j 有關(guān)，而且與時(shí)刻有關(guān)，而且與時(shí)刻 n n 有關(guān)。有關(guān)。n當(dāng)當(dāng) p pij ij(n) (n) 與時(shí)刻與時(shí)刻 n n 無(wú)關(guān)時(shí)，無(wú)關(guān)時(shí)，則稱(chēng)則稱(chēng)馬爾可夫鏈馬爾可夫鏈?zhǔn)驱R次是齊次的，并記為的，并記為 p pij (n)ij (n) 為為 p pij ij 。稱(chēng)稱(chēng)條件概率條件概率為馬爾可夫鏈為馬爾可夫鏈 X Xn n , , n n T T 在時(shí)刻在時(shí)刻 n

6、n 的的一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率，其中其中 i i , , j j I I ，簡(jiǎn)稱(chēng)為，簡(jiǎn)稱(chēng)為轉(zhuǎn)移概率轉(zhuǎn)移概率。 )(1iXjXPnpnnij一步轉(zhuǎn)移概率矩陣一步轉(zhuǎn)移概率矩陣性質(zhì)：性質(zhì)：nnpppppp2222111211PIipIjipIjijij , 1 )2(, , 0 )1 (n n 步轉(zhuǎn)移概率步轉(zhuǎn)移概率稱(chēng)稱(chēng)條件概率條件概率為齊次馬爾可夫鏈為齊次馬爾可夫鏈 X Xn n , , n n T T 的的 n n 步轉(zhuǎn)移概率步轉(zhuǎn)移概率，并，并稱(chēng)稱(chēng)為馬爾可夫鏈為馬爾可夫鏈 的的 n n 步轉(zhuǎn)移矩陣步轉(zhuǎn)移矩陣。) 1 , 0 ,( ,)(nmIjiiXjXPpmnmnij)()(nijnpP規(guī)定：

7、規(guī)定：jijipij , 1 , 0)0( ,)ijP m mn非齊次非齊次n n步轉(zhuǎn)移概率如何表示？步轉(zhuǎn)移概率如何表示？馬爾可夫鏈的馬爾可夫鏈的統(tǒng)計(jì)特性統(tǒng)計(jì)特性完全由完全由一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率和和初始分布初始分布決定決定：001100111100111111001111111122110000, , nnnnnnnnnnnnnnnnnnnnnnP XiXiXiP Xi XiXiXiP XiXiXiP Xi XiP XiXiXiP Xi XiP XiXiP Xi XiP Xi一步轉(zhuǎn)移概率的重要性一步轉(zhuǎn)移概率的重要性, 0)0(,0),( XttX且且是是獨(dú)獨(dú)立立增增量量過(guò)過(guò)程程設(shè)設(shè).0),

8、(是是一一個(gè)個(gè)馬馬爾爾可可夫夫過(guò)過(guò)程程證證明明 ttX性質(zhì)性質(zhì)泊松過(guò)程是時(shí)間連續(xù)狀態(tài)離散的馬氏過(guò)程泊松過(guò)程是時(shí)間連續(xù)狀態(tài)離散的馬氏過(guò)程; ;馬爾可夫鏈的幾個(gè)簡(jiǎn)單例子馬爾可夫鏈的幾個(gè)簡(jiǎn)單例子二進(jìn)制對(duì)稱(chēng)信道模型二進(jìn)制對(duì)稱(chēng)信道模型離散無(wú)記憶離散無(wú)記憶信道模型。信道模型。假設(shè)某級(jí)信道輸入假設(shè)某級(jí)信道輸入0, 10, 1數(shù)字信號(hào)后，其數(shù)字信號(hào)后，其輸出正確的概率為輸出正確的概率為p p，產(chǎn)生錯(cuò)誤的概，產(chǎn)生錯(cuò)誤的概率為率為q q，則該級(jí)信道輸入狀態(tài)和輸出，則該級(jí)信道輸入狀態(tài)和輸出狀態(tài)構(gòu)成一個(gè)狀態(tài)構(gòu)成一個(gè)兩狀態(tài)的齊次馬爾可夫兩狀態(tài)的齊次馬爾可夫鏈鏈。0011ppqq一步轉(zhuǎn)移概率矩陣一步轉(zhuǎn)移概率矩陣：) 1

9、, 0,( , ,jijiqjippijpqqpP二步轉(zhuǎn)移概率矩陣二步轉(zhuǎn)移概率矩陣：22222)2(22qppqpqqpPP具有吸收壁和反射壁的隨機(jī)游動(dòng)具有吸收壁和反射壁的隨機(jī)游動(dòng)設(shè)一質(zhì)點(diǎn)在線段設(shè)一質(zhì)點(diǎn)在線段1，5 上隨機(jī)游動(dòng)，狀態(tài)空間上隨機(jī)游動(dòng)，狀態(tài)空間I=1，2，3，4，5，每秒鐘發(fā)生一次隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：，每秒鐘發(fā)生一次隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：（1）若移動(dòng)前在）若移動(dòng)前在2，3，4處，則均以概率處，則均以概率1/3向左向左 或向右移動(dòng)一單位，或停留在原處；或向右移動(dòng)一單位，或停留在原處；（2）若移動(dòng)前在）若移動(dòng)前在1處，則以概率處，則以概率1移到移到2處；處；（3）若移動(dòng)前在）若移

10、動(dòng)前在5處，則以概率處，則以概率1移到移到4處。處。用nX表示在時(shí)刻n質(zhì)點(diǎn)的位置，則nX，0n是一個(gè)有限齊次馬氏鏈，試寫(xiě)出一步轉(zhuǎn)移矩陣試寫(xiě)出一步轉(zhuǎn)移矩陣.分分析析555453525145444342413534333231252423222115141312111pppppppppppppppppppppppppP01000313131000313131000313131000101P故故12345其一步轉(zhuǎn)其一步轉(zhuǎn)移矩陣為移矩陣為10000210210002102100021021000011P若將移動(dòng)規(guī)則改為若將移動(dòng)規(guī)則改為（1）若移動(dòng)前在）若移動(dòng)前在2，3，4處，則均以概率處，則均以概率1

11、/2向左或向右向左或向右 移動(dòng)一單位；移動(dòng)一單位；（2）若移動(dòng)前在）若移動(dòng)前在1，5處，則以概率處，則以概率1停留在原處。停留在原處。因?yàn)橘|(zhì)點(diǎn)在因?yàn)橘|(zhì)點(diǎn)在1，5兩點(diǎn)被兩點(diǎn)被“吸收吸收”，故稱(chēng)故稱(chēng)有兩個(gè)吸收壁的隨機(jī)游動(dòng)有兩個(gè)吸收壁的隨機(jī)游動(dòng)設(shè)設(shè) X Xn n , , n n T T 是一個(gè)馬爾可夫鏈，其狀態(tài)空間是一個(gè)馬爾可夫鏈，其狀態(tài)空間 I I = = a a, , b b, , c c ，轉(zhuǎn)移矩陣為轉(zhuǎn)移矩陣為05/25/33/103/24/14/12/1P求：求： )2(;, ) 1 (204321bXcXPcXcXaXcXbXPnn, ) 1 (04321cXcXaXcXbXP/ 0001

12、122334cXPcXPcXbXPbXcXPcXaXPaXcXPcbbccaacPPPP50152315341/,043210cXPcXaXcXbXcXP05/25/33/103/24/14/12/1P解： )2(2bXcXPnn二步轉(zhuǎn)移概率矩陣：二步轉(zhuǎn)移概率矩陣：901720330176110315824540930172)2(PP61)2(bcP甲有賭資甲有賭資a元，乙有賭資元，乙有賭資b元，賭一局輸者給贏元，賭一局輸者給贏者者1元，無(wú)和局。甲贏的概率為元，無(wú)和局。甲贏的概率為p，乙贏的概，乙贏的概率為率為q=1- -p，求甲，求甲輸光的輸光的概率。概率。解解 狀態(tài)空間狀態(tài)空間I=0,1,

13、2,c，c=a+bq pa- -1 a a+10 a+b (賭徒輸光問(wèn)題賭徒輸光問(wèn)題) 設(shè)設(shè)ui表示甲從狀態(tài)表示甲從狀態(tài)i出發(fā)轉(zhuǎn)移到狀態(tài)出發(fā)轉(zhuǎn)移到狀態(tài)0的的概率，求概率，求ua 顯然顯然u0 =1，uc =0(u0表示已知表示已知甲輸光甲輸光情形情形下甲輸光的概率，下甲輸光的概率，uc表示已知表示已知乙輸光乙輸光情情形下甲輸光的概率形下甲輸光的概率) ui =pui+1 + qui-1 (i=1,2,c-1)（甲在狀態(tài)（甲在狀態(tài)i下輸光：甲贏一局后輸光或甲下輸光：甲贏一局后輸光或甲輸一局后輸光）輸一局后輸光） (賭徒輸光問(wèn)題賭徒輸光問(wèn)題) 1, 2 , 1)()()()(111111ciuup

14、quuuuquupqupuuqpiiiiiiiiiii 21, 1 (1)012111uuuuuuuuqppqiiiiii即即 baaubabcauciiuccuiiuuiuuiuuuuuuuubaiciiiiiiii同同理理可可得得即即,111101) 1(1) 1() 1() 1()( )()()(0101012111 rrruuuruuruuuuruurpqqppqckckiiiickikciiii1) 1( )()()(, 1 (2)10111111設(shè)設(shè)即即 ccbcbbccacaacckckkcccrrrrrruurrrrrruurrrrrruurrurrruuuk11) 1(11)

15、 1(11) 1(1111) 1(0,1111010從而從而則則令令二、基本性質(zhì)二、基本性質(zhì)性質(zhì)性質(zhì)1 1設(shè)0, nXn為馬氏鏈，其狀態(tài)空間為I，表明表明若已知現(xiàn)在，則過(guò)去與未來(lái)是獨(dú)立的。若已知現(xiàn)在，則過(guò)去與未來(lái)是獨(dú)立的。若nrs0，則在rriX的條件下，有|,rrssnniXiXiXP=|rrnniXiXP|rrssiXiXP ,|,/|,/|/|nnssrrnnssrrrrnnssrrssrrrrnnrrssrrrrrrnnrrssrrP XiXi XiP XiXi XiP XiP XiXi XiP Xi XiP XiP XiXiP XiXiP XiP XiP XiXiP XiXi證明n

16、步轉(zhuǎn)移概率 的性質(zhì))(nijp 定理定理 設(shè)設(shè) X Xn n , , n n T T 為馬爾可夫鏈，則對(duì)于任意整數(shù)為馬爾可夫鏈，則對(duì)于任意整數(shù)n n ，mm 0, 0, 和和 i i , , j j I I ，n n 步轉(zhuǎn)移概率步轉(zhuǎn)移概率 具有下列性具有下列性質(zhì)：質(zhì)：)(nijp (1) nmnmijikkjkIpppIkjkkkikIknijnnpppp112111)( )2()( )(3) mnmnPPPnnPP)( )4(C-K方程方程例例甲、乙兩人進(jìn)行比賽，設(shè)每局比賽中甲勝的概率是甲、乙兩人進(jìn)行比賽，設(shè)每局比賽中甲勝的概率是p p，乙勝的概率是，乙勝的概率是q q，和局的概率是，和局的

17、概率是r r , ,（ p+q+rp+q+r=1=1）。設(shè)每局比賽后，勝者記）。設(shè)每局比賽后，勝者記“+1”+1”分，分，負(fù)者記負(fù)者記“-1”-1”分，和局不記分。當(dāng)兩人中有一人獲分，和局不記分。當(dāng)兩人中有一人獲得得2 2分結(jié)束比賽。以分結(jié)束比賽。以 表示比賽至第表示比賽至第n n局時(shí)甲獲局時(shí)甲獲得的分?jǐn)?shù)。得的分?jǐn)?shù)。nX（1）寫(xiě)出狀態(tài)空間；）寫(xiě)出狀態(tài)空間；（3）問(wèn)在甲獲得）問(wèn)在甲獲得1分的情況下，再賽二局可以結(jié)束比分的情況下，再賽二局可以結(jié)束比賽的概率是多少？賽的概率是多少？解解（1） 記甲獲得記甲獲得“負(fù)負(fù)2分分”為狀態(tài)為狀態(tài)1，獲得，獲得“負(fù)負(fù)1分分”為狀態(tài)為狀態(tài)2，獲得，獲得“0分分”為

18、狀態(tài)為狀態(tài)3，獲得獲得“正正1分分”為狀態(tài)為狀態(tài)4，獲得，獲得“正正2分分”為為狀態(tài)狀態(tài)5，則狀態(tài)空間為，則狀態(tài)空間為54321，I一步轉(zhuǎn)移概率矩陣一步轉(zhuǎn)移概率矩陣10000000000000011prqprqprqP（2）二步轉(zhuǎn)移概率矩陣）二步轉(zhuǎn)移概率矩陣 221PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq（3）在2P中)2(45p是在甲得 1 分的情況下經(jīng)二步轉(zhuǎn)移至 2 分從而結(jié)束比賽的概率；)2(41p是在甲得 1 分的情況下經(jīng)二步轉(zhuǎn)移至2 分（即乙得 2 分）從而結(jié)束比賽的概率。所以題中所求概率為)2(45p)2(41p)1

19、 (0)(rprpp絕對(duì)概率絕對(duì)概率稱(chēng)為馬氏鏈的稱(chēng)為馬氏鏈的絕對(duì)分布絕對(duì)分布或稱(chēng)或稱(chēng)絕對(duì)概率絕對(duì)概率計(jì)算公式計(jì)算公式絕對(duì)概率由初始分布和絕對(duì)概率由初始分布和n n維轉(zhuǎn)移概率完全確定維轉(zhuǎn)移概率完全確定)(0)()(nijIinpipjp絕對(duì)概率絕對(duì)概率 pj(n) 的性質(zhì)的性質(zhì)定理定理 設(shè)設(shè) Xn , n T 為馬爾可夫鏈，則對(duì)于任意整數(shù)為馬爾可夫鏈，則對(duì)于任意整數(shù)n 1 和和 j I ，絕對(duì)概率，絕對(duì)概率 pj (n) 具有下列性質(zhì)：具有下列性質(zhì)： ()()(1) ( )0(2) ( )(1)(3) ( )(0)(3) ( )(1)njiijiIjiijiITTnTTpnpppnpnpnnnP

20、PPPPP馬氏鏈狀態(tài)的極限分布馬氏鏈狀態(tài)的極限分布n知道了多步轉(zhuǎn)移矩陣，已知初始分布可計(jì)算馬氏知道了多步轉(zhuǎn)移矩陣，已知初始分布可計(jì)算馬氏鏈多步后取某個(gè)狀態(tài)的概率鏈多步后取某個(gè)狀態(tài)的概率 n如果時(shí)間無(wú)限長(zhǎng)，取某個(gè)狀態(tài)的概率是多少？如果時(shí)間無(wú)限長(zhǎng)，取某個(gè)狀態(tài)的概率是多少？反反射壁問(wèn)題為例射壁問(wèn)題為例 隨著時(shí)間無(wú)限長(zhǎng)，出現(xiàn)隨著時(shí)間無(wú)限長(zhǎng)，出現(xiàn)5 5種狀態(tài)的種狀態(tài)的概率趨于穩(wěn)定。概率趨于穩(wěn)定。n多步轉(zhuǎn)移概率當(dāng)步數(shù)趨于無(wú)窮時(shí)的極限問(wèn)題多步轉(zhuǎn)移概率當(dāng)步數(shù)趨于無(wú)窮時(shí)的極限問(wèn)題n如果上述極限存在且和初始狀態(tài)無(wú)關(guān)，則馬爾可如果上述極限存在且和初始狀態(tài)無(wú)關(guān)，則馬爾可夫鏈?zhǔn)潜闅v的。夫鏈?zhǔn)潜闅v的。n只要找到一個(gè)正整數(shù)

21、只要找到一個(gè)正整數(shù)mm，使得，使得mm步轉(zhuǎn)移概率矩陣步轉(zhuǎn)移概率矩陣無(wú)零元素，則該馬氏鏈就是遍歷的無(wú)零元素，則該馬氏鏈就是遍歷的。10100011100333111 003331110033300010P 反 射 壁110000110002211 00022110002200001P 吸收壁反射壁反射壁 遍歷遍歷 ；吸收壁；吸收壁非遍歷非遍歷。計(jì)算。計(jì)算一個(gè)問(wèn)題：社會(huì)學(xué)家如何確定社會(huì)階層高職業(yè)階層或較低階層一個(gè)問(wèn)題：社會(huì)學(xué)家如何確定社會(huì)階層高職業(yè)階層或較低階層在社會(huì)中的比例？在社會(huì)中的比例？馬爾可夫極限概率的應(yīng)用馬爾可夫極限概率的應(yīng)用0010121220.450.480.070.050.70.2

22、50.010.50.490.07 0.620.31PP富中低 1 1 基本概念基本概念2 2 狀態(tài)類(lèi)別的劃分和判別狀態(tài)類(lèi)別的劃分和判別3 3 狀態(tài)間的關(guān)系狀態(tài)間的關(guān)系 l返回概率返回概率l平均返回時(shí)間平均返回時(shí)間l周期周期l分類(lèi)分類(lèi)l判別判別第二節(jié)第二節(jié) MarkovMarkov鏈的狀態(tài)分類(lèi)及性質(zhì)鏈的狀態(tài)分類(lèi)及性質(zhì)l定義（可達(dá)、互通）定義（可達(dá)、互通）l性質(zhì)性質(zhì)l互通的兩個(gè)狀態(tài)之間的關(guān)系互通的兩個(gè)狀態(tài)之間的關(guān)系n狀態(tài)分類(lèi)的原因狀態(tài)分類(lèi)的原因瞬態(tài)分析瞬態(tài)分析 某一固定時(shí)刻的概率特性某一固定時(shí)刻的概率特性 n n步轉(zhuǎn)移概率步轉(zhuǎn)移概率 或絕對(duì)概率或絕對(duì)概率穩(wěn)態(tài)分析穩(wěn)態(tài)分析 n n趨于無(wú)窮大時(shí)系統(tǒng)的概

23、率特性，這種概趨于無(wú)窮大時(shí)系統(tǒng)的概率特性，這種概 率特性與狀態(tài)的關(guān)系如何率特性與狀態(tài)的關(guān)系如何需要對(duì)狀態(tài)進(jìn)行需要對(duì)狀態(tài)進(jìn)行分類(lèi)分類(lèi) MarkovMarkov鏈的狀態(tài)分類(lèi)鏈的狀態(tài)分類(lèi)一、基本概念一、基本概念1.返回概率返回概率( )0,1,2,1|nijnkfP Xj Xj knXi自狀態(tài)自狀態(tài) i i出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)n n步首次到達(dá)步首次到達(dá)狀態(tài)狀態(tài)j j 的概率的概率自狀態(tài)自狀態(tài)i i出發(fā)，經(jīng)出發(fā)，經(jīng)有限步終于到達(dá)有限步終于到達(dá)狀態(tài)狀態(tài)j j的概率的概率( )1nijijnff返回概率返回概率-自狀態(tài)自狀態(tài)i i出發(fā)，經(jīng)有限步終于出發(fā)，經(jīng)有限步終于返返回回狀態(tài)狀態(tài) i i的的概率概率ii

24、f 與 的關(guān)系上式可用來(lái)求從狀態(tài)上式可用來(lái)求從狀態(tài) i 經(jīng)經(jīng) n 步首次到達(dá)狀態(tài)步首次到達(dá)狀態(tài) j 的概率：的概率：)(nijp)(nijf定理 對(duì)任意對(duì)任意狀態(tài)狀態(tài) i , j I 及及 1 n 1,1,稱(chēng)稱(chēng)i i是周期的；若是周期的；若d di i = =1,1,稱(chēng)稱(chēng)i i是非周期的。是非周期的。( )gcd :1,0, common dividorniiidn npgreat說(shuō)明說(shuō)明1 13.3.周期周期d di i體現(xiàn)系統(tǒng)的發(fā)展變化中狀態(tài)體現(xiàn)系統(tǒng)的發(fā)展變化中狀態(tài)i i重復(fù)出現(xiàn)的概率周期。重復(fù)出現(xiàn)的概率周期。說(shuō)明說(shuō)明2 2若若i i的周期是的周期是d di i，并不是對(duì)所有的，并不是對(duì)所

25、有的n n滿(mǎn)足滿(mǎn)足 ()0indiip說(shuō)明說(shuō)明3 3( )gcd :1,0niiidn nf例例設(shè)設(shè)MCMC：0 0，1 1，2 2，3 3，轉(zhuǎn)移概率矩陣如下，轉(zhuǎn)移概率矩陣如下，試求狀態(tài)試求狀態(tài)0 0的周期。的周期。001/21/2001/21/21/21/2001/21/200P求下列馬爾可夫鏈的周期求下列馬爾可夫鏈的周期786951112/31/3111111234狀態(tài)1周期？ 4 6 8 10 。 Gcd=2二、狀態(tài)類(lèi)別的劃分及判別二、狀態(tài)類(lèi)別的劃分及判別1 1. .狀態(tài)類(lèi)別的劃分狀態(tài)類(lèi)別的劃分狀態(tài)狀態(tài) i iiif非常返態(tài)（暫態(tài)）非常返態(tài)（暫態(tài)）常返態(tài)常返態(tài)零常返態(tài)零常返態(tài)正常返態(tài)正常

26、返態(tài)周期周期非周期（遍歷態(tài)）非周期（遍歷態(tài)）iiid常返態(tài)常返態(tài)非常返態(tài)非常返態(tài)1iif1iif正常返態(tài)正常返態(tài)零常返態(tài)零常返態(tài)ii ii iif -有 限 次 返 回 概 率ii 平 均 返 回 時(shí) 間狀態(tài)狀態(tài)i i再次最終再進(jìn)入再次最終再進(jìn)入i i的概率為的概率為1-1-常返態(tài)常返態(tài)在在有限狀態(tài)馬爾科夫鏈有限狀態(tài)馬爾科夫鏈中，一切中，一切常返態(tài)都是正常返常返態(tài)都是正常返的的常返性的定義常返性的定義稱(chēng)期望值稱(chēng)期望值 為狀態(tài)為狀態(tài) i i 的的平均返回平均返回時(shí)間時(shí)間。( )1niiinnf若若 f fii ii = 1 = 1，則稱(chēng)狀態(tài)，則稱(chēng)狀態(tài) i i 是是常返常返的；若的；若 f fii

27、 ii 1 1，則，則稱(chēng)狀態(tài)稱(chēng)狀態(tài) i i 是是非常返非常返的。的。若若 i i 0, 0, 使得使得 p pij ij( (n n) ) 0 0 ，則稱(chēng)自狀態(tài)，則稱(chēng)自狀態(tài) i i 可達(dá)可達(dá)狀態(tài)狀態(tài) j j ，并記為，并記為 i i j j 。（2 2）若）若 i i j j , , 且且 j j i , i , 則稱(chēng)狀態(tài)則稱(chēng)狀態(tài) i i 與狀態(tài)與狀態(tài) j j 互通互通，并記為，并記為 i i j j 。定理1 若若 i j , 且且 j k , 則則 i k 。若若 i j , 且且 j k , 則則 i k 。 定理定理2 2 若若 i i j j , , 則則（1 1）i i 與與 j

28、j 同為同為常返或非常返常返或非常返；（2 2）i i 與與 j j 同為同為正常返或零常返正常返或零常返；（3 3）i i 與與 j j 有有相同的周期相同的周期。傳遞性互通關(guān)系的狀態(tài)是同一類(lèi)型例 設(shè)馬氏鏈的狀態(tài)空間設(shè)馬氏鏈的狀態(tài)空間 I = 0, 1, 2, ，其轉(zhuǎn)移概率，其轉(zhuǎn)移概率為為分析狀態(tài)分析狀態(tài)0的類(lèi)型。的類(lèi)型。,21)1(00f解：Iipppiii ,21 ,21 ,2101,00先考查狀態(tài)先考查狀態(tài)0 0，,412121)2(00f,21)(00nnf, 121100nnf可見(jiàn)狀態(tài)可見(jiàn)狀態(tài)0 0為為正常返正常返，且，且是非周期是非周期，因而是，因而是遍歷遍歷的。的。因?yàn)橐驗(yàn)?i

29、 i 0 0 ，故，故 i i 也是遍歷的。也是遍歷的。000011112121112100211,21, 1 111111111112,222112nnnnnnnnnnnnnnnnunfnxxxnxnxnxxxxxnxxxun 而令正常返證明：狀態(tài)空間的分解 定義定義 狀態(tài)空間狀態(tài)空間 I I 的子集的子集 C C，若，若對(duì)于任意對(duì)于任意 i i C C 及及 k k C C 都有都有 p pik ik = 0 = 0 ，則稱(chēng)，則稱(chēng)子集子集 C C 為（隨機(jī)）為（隨機(jī)）閉集閉集。若閉集若閉集 C C 的狀態(tài)互通，則稱(chēng)的狀態(tài)互通，則稱(chēng) C C 為為不可約不可約的。的。若馬氏鏈若馬氏鏈 X Xn

30、 n 的狀態(tài)空間是不可約的，則稱(chēng)該馬氏鏈為的狀態(tài)空間是不可約的，則稱(chēng)該馬氏鏈為不可約不可約。例 （例（例4.11）設(shè)馬氏鏈設(shè)馬氏鏈 Xn 的狀態(tài)空間的狀態(tài)空間 I = 1, 2, 3, 4, 5 ，轉(zhuǎn)移矩陣為，轉(zhuǎn)移矩陣為P，試分析其閉集及不可約性。，試分析其閉集及不可約性。000100000100100005 . 005 . 005 . 0005 . 0P1/21/21/211/211狀態(tài)狀態(tài) 3為吸收態(tài)，故為吸收態(tài)，故 3 是閉集；是閉集； 1, 4 ， 1, 4, 3 ， 1, 4, 2, 3 都是閉集；都是閉集； 3 和和 1, 4 是不可約閉集；是不可約閉集；因?yàn)橐驗(yàn)?I 含有（含有（

31、非非不可約的不可約的）閉子集，故馬氏鏈）閉子集，故馬氏鏈 Xn 不不是不可約鏈。是不可約鏈。pij(n)的漸近性質(zhì)與平穩(wěn)分布是否存在？是否存在？是否與是否與 i 有關(guān)？有關(guān)？)(limnijnp對(duì)于轉(zhuǎn)移概率對(duì)于轉(zhuǎn)移概率 pij (n) 的極限的極限（1）pij(n)的漸近性質(zhì)推論 不可約的有限馬氏鏈必為正常返的。不可約的有限馬氏鏈必為正常返的。有限狀態(tài)的馬氏鏈，有限狀態(tài)的馬氏鏈，不可能全是非常返態(tài)不可能全是非常返態(tài)，也不可能，也不可能含有零常返態(tài)；含有零常返態(tài)；定理 若若 j 非常返或零常返非常返或零常返，則，則Iipnijn , 0lim)(（2）平穩(wěn)分布定義 稱(chēng)絕對(duì)概率分布稱(chēng)絕對(duì)概率分布

32、j , j I 為齊次馬氏鏈的為齊次馬氏鏈的平穩(wěn)分布，若它滿(mǎn)足，若它滿(mǎn)足0 , 1 jIiiIiijijpPPTijTip , , 則令平穩(wěn)分布平穩(wěn)分布 定理定理 不可約非周期不可約非周期馬氏鏈?zhǔn)邱R氏鏈?zhǔn)钦７档恼７档某湟獥l件：存充要條件：存在平穩(wěn)分布，且此平穩(wěn)分布就是極限分布在平穩(wěn)分布，且此平穩(wěn)分布就是極限分布 ,1 Ijj平均返回時(shí)間和平穩(wěn)分布互為倒數(shù)平均返回時(shí)間和平穩(wěn)分布互為倒數(shù)例 （例例4.16）設(shè)馬爾可夫鏈設(shè)馬爾可夫鏈的轉(zhuǎn)移概率矩陣為的轉(zhuǎn)移概率矩陣為P，求馬，求馬氏鏈的平穩(wěn)分布及各狀態(tài)的平均返回時(shí)間。氏鏈的平穩(wěn)分布及各狀態(tài)的平均返回時(shí)間。9 . 005. 005. 01 . 08

33、. 01 . 02 . 01 . 07 . 0P解：因?yàn)樵撘驗(yàn)樵擇R氏鏈?zhǔn)邱R氏鏈?zhǔn)遣豢杉s的非不可約的非周期周期有有限狀態(tài)限狀態(tài)，所以存在平穩(wěn)分布。所以存在平穩(wěn)分布。各狀態(tài)的平均返回時(shí)間分別各狀態(tài)的平均返回時(shí)間分別為：為：1 0.90.1 2 . 00.050.8 1 . 00.050.1 7 . 032132133212211平穩(wěn)分布為：平穩(wěn)分布為：5882.0 ,2353.0 ,1765.032170.11 ,25.41 ,67.51332211例例 設(shè)有狀態(tài)空間設(shè)有狀態(tài)空間S=0,1,2,3,4,5,6S=0,1,2,3,4,5,6的齊次馬爾可夫鏈，的齊次馬爾可夫鏈， 其一步轉(zhuǎn)移概率矩陣為其

34、一步轉(zhuǎn)移概率矩陣為0.50.50000002/ 31/ 300001/ 302/ 300000000.50.5000000.50.500000001011111117777777P(1)(1)試對(duì)試對(duì)S S進(jìn)行分類(lèi)，并說(shuō)明各狀態(tài)類(lèi)型進(jìn)行分類(lèi)，并說(shuō)明各狀態(tài)類(lèi)型(2) (2) 求平穩(wěn)分布，其平穩(wěn)分布是否唯一？求平穩(wěn)分布，其平穩(wěn)分布是否唯一？121713121712122312501634132312(1) 123SDCCC+=UUU60,1,23,45=UUU不可約閉子集不可約閉子集(2)(2) 由由(1)(1)知知, ,該鏈有三個(gè)不同的正常返不可約閉集該鏈有三個(gè)不同的正常返不可約閉集所以平穩(wěn)分布不唯一所以平穩(wěn)分布不唯一三個(gè)閉集對(duì)應(yīng)的轉(zhuǎn)移概率矩陣分別為三個(gè)閉集對(duì)應(yīng)的轉(zhuǎn)移概率矩陣分別為1122213311233000P驏= 桫112221122P驏=桫()31P =(2) 由由(1)知知,該鏈有三個(gè)不同的正常返不可約閉集該鏈有三個(gè)不同的正常返不可約閉集解方程組解方程組(1)(1)1(1)(1)(1)1231(2)(2)2(2)(