馬爾科夫鏈的狀態(tài)分類.ppt

《馬爾科夫鏈的狀態(tài)分類.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《馬爾科夫鏈的狀態(tài)分類.ppt（53頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、馬爾可夫鏈的狀態(tài)分類,一、互通與閉集,1互通,則稱自狀態(tài)i可到達(dá)狀態(tài)j,則稱狀態(tài)i和狀態(tài)j互通,說明,如果自狀態(tài)i不能到達(dá)狀態(tài)j，,定理1,即它滿足,（1）自反性,（2）對(duì)稱性,證,（3）傳遞性,（1），（2）顯然，下證（3）,證3,則由相通定義，,根據(jù)切普曼---柯爾莫哥洛夫方程，有,同理可證,說明,按互通關(guān)系是等價(jià)關(guān)系，可以把狀態(tài)空間 S 劃分為若干個(gè)不相交的集合（或者說等價(jià)類），并稱之為狀態(tài)類。 若兩個(gè)狀態(tài)互通，則這兩個(gè)狀態(tài)屬于同一類。 任意兩個(gè)類或不相交或者相同。,2閉集,設(shè)C為狀態(tài)空間S 的一個(gè)子集，,則C稱為閉集,注1,若C為閉集，則表示自C內(nèi)任意狀態(tài)i出發(fā)，始終不能到達(dá)C

2、以外的任何狀態(tài)j。 顯然，整個(gè)狀態(tài)空間構(gòu)成一個(gè)閉集。,吸收態(tài),指一個(gè)閉集中只含一個(gè)狀態(tài),注2,若狀態(tài)空間含有吸收狀態(tài)，那么這個(gè)吸收狀態(tài)構(gòu)成一個(gè)最小的閉集。,3不可約的,若除整個(gè)狀態(tài)空間 S 以外沒有其它的閉集， 則稱此馬氏鏈?zhǔn)遣豢杉s的。,如果閉集C的狀態(tài)都是互通的，則稱閉集C是不可約的。,例1,其一步轉(zhuǎn)移矩陣為,試研究各狀態(tài)間的關(guān)系，并畫出狀態(tài)傳遞圖。,解,先按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖,由圖可知,狀態(tài)0可到達(dá)狀態(tài)1，經(jīng)過狀態(tài)1又可到達(dá)狀態(tài)2；反之，從狀態(tài)2出發(fā)經(jīng)狀態(tài)1也可到達(dá)狀態(tài)0。,因此，狀態(tài)空間S的各狀態(tài)都是互通的。,又由于S 的任意狀態(tài)i (i = 0，1，2)不能到達(dá)S

3、以外的任何狀態(tài)，,所以S是一個(gè)閉集,而且S 中沒有其它閉集,所以此馬氏鏈?zhǔn)遣豢杉s的。,例2,其一步轉(zhuǎn)移矩陣為,試討論哪些狀態(tài)是吸收態(tài)、閉集及不可約鏈。,解,先按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖,閉集，,由圖可知,狀態(tài)3為吸收態(tài),且,閉集，,閉集，,其中 是不可約的。,又因狀態(tài)空間S有閉子集，,故此鏈為非不可約鏈。,二、首達(dá)時(shí)間和狀態(tài)分類,1首達(dá)時(shí)間,系統(tǒng)從狀態(tài)i出發(fā)， 首次到達(dá)狀態(tài)j的時(shí)刻,稱為從狀態(tài) i 出發(fā)首次進(jìn)入狀態(tài) j 的時(shí)間，,或稱自i 到j(luò) 的首達(dá)時(shí)間。,如果這樣的n不存在，就規(guī)定,說明,自狀態(tài) i出發(fā)，經(jīng)過n步首次到達(dá)狀態(tài)j 的概率,自狀態(tài)i出發(fā)，經(jīng)有窮步終于到達(dá)狀態(tài)j

4、的概率,注1,對(duì)于首次到達(dá)時(shí)間,表示從狀態(tài) i出發(fā)首次返回狀態(tài)i所需的時(shí)間,相應(yīng)的 便是從狀態(tài)i出發(fā)，經(jīng)有限步終于返回狀態(tài) i的概率，,2首次到達(dá)分解式,定理2,證,設(shè)系統(tǒng)從狀態(tài)i經(jīng)n步轉(zhuǎn)移到狀態(tài)j，,由條件概率及馬氏性得,說明,( m =1，2，，n),的所有可能值進(jìn)行分解，,定理3,證,充分性,由定理2得,從而,所以,必要性,由定理2得,所以,推論,3常返態(tài)與瞬時(shí)態(tài),則稱狀態(tài)i為常返態(tài),則稱狀態(tài)i為瞬時(shí)態(tài),注,“常返”一詞，有時(shí)又稱“返回”、“常駐”或“持久”,“瞬時(shí)”也稱“滑過” 或“非常返”,定理4,證,則系統(tǒng)從狀態(tài)i出發(fā)，經(jīng)過有限次轉(zhuǎn)移之后，必定以概率1返回狀態(tài)i。,再由馬氏性,系

5、統(tǒng)返回狀態(tài)i要重復(fù)發(fā)生,這樣，系統(tǒng)從狀態(tài)i出發(fā)，又返回，再出發(fā)，再返回，隨著時(shí)間的無限推移，將無限次訪問狀態(tài)i。,將“不返回i”稱為成功，,則首次成功出現(xiàn)的次數(shù)服從幾何分布，,這就是說,也就是說以概率1只有有窮次返回i。,定理5,證,令,n = 0，1，2，,因此，從狀態(tài)i出發(fā)，訪問狀態(tài)i的平均次數(shù)為,由定理4，得證。,說明,本定理的等價(jià)形式：,i為瞬時(shí)態(tài)，當(dāng)且僅當(dāng),定理6,證,如果i為常返態(tài)，且 ，則j也是常返態(tài)。,因,由切普曼---可爾莫哥洛夫方程得,上式兩邊對(duì)所有的s相加，得,又因?yàn)閕為常返態(tài)，,所以,故得,從而,即狀態(tài)j也是常返態(tài),定理7,所有常返態(tài)構(gòu)成一個(gè)閉集,證,設(shè)i為常返態(tài)

6、，,即i和j相通。,這是因?yàn)?若自j出發(fā)不能到達(dá)i，那么從i出發(fā)到達(dá)j后，就不能再返回i，這與i是常返態(tài)的 相矛盾。,再由定理6知，j也是常返態(tài)，,這就是說，,自常返態(tài)出發(fā)，只能到達(dá)常返態(tài)，不能到達(dá)瞬時(shí)態(tài)。,故常返態(tài)全體構(gòu)成一個(gè)閉集,4狀態(tài)空間的分解,如果已知類中有一個(gè)常返態(tài)，則這個(gè)類中其它狀態(tài)都是常返的；,若類中有一個(gè)瞬時(shí)態(tài)，則類中其它狀態(tài)都是瞬時(shí)態(tài)。,若對(duì)不可約馬氏鏈，則要么全是常返態(tài)，要么全是瞬時(shí)態(tài)。,定理8,任一馬氏鏈的狀態(tài)空間S必可分解為,其中N是瞬時(shí)態(tài)集，,而且,證,記C為全體常返態(tài)所構(gòu)成的集合，,則由定理7知C為閉集,將C按互通關(guān)系分類：,那么再從余下的狀態(tài)中任取一個(gè)狀態(tài),

7、如此進(jìn)行下去 ，,并且顯然滿足條件（1）和（2）。,5正常返態(tài)與零常返態(tài),平均返回時(shí)間,從狀態(tài)i出發(fā)，首次返回狀態(tài)i的平均時(shí)間,稱為狀態(tài)i平均返回時(shí)間.,根據(jù) 的值是有限或無限，可把常返態(tài)分為兩類：,設(shè)i是常返態(tài)，,則稱i為正常返態(tài)；,則稱i為零常返態(tài)。,定理9,設(shè)i是常返態(tài)，則,（1）i是零常返態(tài)的充要條件是,（2）i是正常返態(tài)的充要條件是,證明（略）,推論,證,因?yàn)?由定理9，上式第一項(xiàng)有,從而推論得證。,說明,用極限判斷狀態(tài)類型的準(zhǔn)則,（2）i是零常返態(tài),（2）i是正常返態(tài),（1）i是瞬時(shí)態(tài),且,且,定理10,證明,由切普曼---可爾莫哥洛夫方程得,由此可知,由定理9知,6有限馬氏鏈,對(duì)

8、有限狀態(tài)的馬氏鏈我們給出不加證明的性質(zhì),定理11,（1）瞬時(shí)態(tài)集N不可能是閉集； （2）至少有一個(gè)常返態(tài)； （3）不存在零常返態(tài)； （4）若鏈?zhǔn)遣豢杉s的，那么狀態(tài)都是正常返的 （5）其狀態(tài)空間可分解為,是互不相交的由正常返態(tài)組成的閉集。,例3,轉(zhuǎn)移矩陣,試對(duì)其狀態(tài)分類。,解,按一步轉(zhuǎn)移概率， 畫出各狀態(tài)間的傳遞圖,從圖可知，此鏈的每一狀態(tài)都可到達(dá)另一狀態(tài)，即4個(gè)狀態(tài)都是互通的。,考慮狀態(tài)1是否常返，,類似地可求得,所以,于是狀態(tài)1是常返的。,又因?yàn)?所以狀態(tài)1是正常返的。,由定理可知，此鏈所有狀態(tài)都是正常返的。,例4,設(shè)馬氏鏈的狀態(tài)空間S=0,1,2,，其一步轉(zhuǎn)移概率為,其中,試證此馬氏鏈?zhǔn)且?/p>

9、個(gè)不可約常返態(tài)鏈,證,先證S不可約,設(shè)i，j是I中任意兩個(gè)狀態(tài)，,則有,類似地可證,所以,即I中任意兩個(gè)狀態(tài)都是相通的。,因此，S是一個(gè)不可約的閉集,再證S中狀態(tài)0是一個(gè)常返態(tài)：,由狀態(tài)的轉(zhuǎn)移規(guī)則，得,所以,由定義知狀態(tài)0為常返態(tài)。,因此，由定理知S中所有狀態(tài)都是常返態(tài)。,故此馬氏鏈為不可約常返鏈。,三、狀態(tài)的周期與遍歷,1周期狀態(tài),對(duì)于任意的 ，令,其中GCD表示最大公約數(shù),則稱 為周期態(tài)，,則稱 為非周期態(tài)。,定理12,證,所以存在正整數(shù)m、n，使,則有,則有,因此有,類似地可證得,故,（2）,所以,從而i為非周期態(tài)。,又因?yàn)轳R氏鏈不可約，,所以j也是非周期態(tài)，,從而該馬氏鏈?zhǔn)欠侵?/p>

10、期鏈。,2遍歷狀態(tài),若狀態(tài)i是正常返且非周期，則稱i為遍歷狀態(tài)。,例5,設(shè)馬氏鏈的狀態(tài)空間S = 0,1,2,，轉(zhuǎn)移概率為,試討論各狀態(tài)的遍歷性。,解,根據(jù)轉(zhuǎn)移概率作出狀態(tài)傳遞圖,從圖可知，對(duì)任一狀態(tài) 都有 ，,故由定理可知，S中的所以狀態(tài)都是相通的，,因此只需考慮狀態(tài)0是否正常返即可。,,故,從而0是常返態(tài)。,又因?yàn)?所以狀態(tài)0為正常返。,又由于,故狀態(tài)0為非周期的,從而狀態(tài)0是遍歷的。,故所有狀態(tài)i都是遍歷的。,習(xí)題課,1帶有兩個(gè)反射壁的隨機(jī)游動(dòng),如果狀態(tài)空間S = 0，1，2，，m，移動(dòng)的規(guī)則是： （1）若移動(dòng)前在0處，則下一步以概率p向右移動(dòng)一個(gè)單位，以概率q停留在原處（p

11、+q=1）； （2）若移動(dòng)前在m處，則下一步以概率q向左移動(dòng)一個(gè)單位，以概率p停留在原處； （3）若移動(dòng)前在其它點(diǎn)處，則均以概率p向右移動(dòng)一個(gè)單位，以概率q向左移動(dòng)一個(gè)單位。,設(shè) 表示在時(shí)刻n質(zhì)點(diǎn)的位置，則 ， 是一個(gè)齊次馬氏鏈，寫出其一步轉(zhuǎn)移概率矩陣。,,2帶有反射壁的隨機(jī)游動(dòng),設(shè)隨機(jī)游動(dòng)的狀態(tài)空間S = 0，1，2，，移動(dòng)的規(guī)則是： （1）若移動(dòng)前在0處，則下一步以概率p向右移動(dòng)一個(gè)單位，以概率q停留在原處（p+q=1）； （2）若移動(dòng)前在其它點(diǎn)處，則均以概率p向右移動(dòng)一個(gè)單位，以概率q向左移動(dòng)一個(gè)單位。,設(shè) 表示在時(shí)刻n質(zhì)點(diǎn)的位置，則 ， 是一個(gè)齊次馬氏鏈，寫出其

12、一步轉(zhuǎn)移概率。,3一個(gè)圓周上共有N格（按順時(shí)針排列），一個(gè)質(zhì)點(diǎn)在該圓周上作隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：質(zhì)點(diǎn)總是以概率p順時(shí)針游動(dòng)一格， 以概率 逆時(shí)針游動(dòng)一格。試求轉(zhuǎn)移概率矩陣。,4一個(gè)質(zhì)點(diǎn)在全直線的整數(shù)點(diǎn)上作隨機(jī)游動(dòng)，移動(dòng)的規(guī)則是：以概率p從i移到i-1，以概率q從i移到i+1，以概率r停留在i，且 ，試求轉(zhuǎn)移概率矩陣。,5設(shè)袋中有a個(gè)球，球?yàn)楹谏幕虬咨?，今隨機(jī)地從袋中取一個(gè)球，然后放回一個(gè)不同顏色的球。若在袋里有k個(gè)白球，則稱系統(tǒng)處于狀態(tài)k，試用馬爾可夫鏈描述這個(gè)模型（稱為愛倫菲斯特模型），并求轉(zhuǎn)移概率矩陣。,解 這是一個(gè)齊次馬氏鏈，其狀態(tài)空間為,S=a，a+1

13、，，1，0，1，2，，a,一步轉(zhuǎn)移矩陣是,6設(shè)馬氏鏈的狀態(tài)空間S=1，2，3，4，其一步轉(zhuǎn)移矩陣為,解,試對(duì)其狀態(tài)分類。,按一步轉(zhuǎn)移概率，畫出各狀態(tài)間的傳遞圖,它是有限狀態(tài)的馬氏鏈，故必有一個(gè)常返態(tài)，又鏈中四個(gè)狀態(tài)都是互通的。因此，所有狀態(tài)都是常返態(tài)，這是一個(gè)有限狀態(tài)不可約的馬氏鏈。,可繼續(xù)討論是否為正常返態(tài),可討論狀態(tài)1,狀態(tài)1是常返態(tài),狀態(tài)1是正常返態(tài),所以，全部狀態(tài)都是正常返態(tài),7設(shè)馬氏鏈的狀態(tài)空間S=1，2，3，4，5，其一步轉(zhuǎn)移矩陣為,試研究各狀態(tài)的類及周期性,解,各狀態(tài)間的傳遞圖,對(duì)于任意 有， 即S為不可再分閉集。,所以S中每一個(gè)狀態(tài)都是常返態(tài)， 且此馬氏鏈為有限狀態(tài)不可約 常返鏈。,所以狀態(tài)1的周期為3，由定理知，S中所有狀態(tài)都為周期態(tài)，且周期都為3。因此，這個(gè)馬氏鏈又是以3為周期的周期鏈。,又因?yàn)轳R氏鏈為有限狀態(tài)不可約鏈，所以所有狀態(tài)都是正常返狀態(tài)。,8設(shè)馬氏鏈的狀態(tài)空間為S = 1，2，3，其一步轉(zhuǎn)移矩陣為,試研究各狀態(tài)間的關(guān)系。,解,可繼續(xù)討論正常返,9設(shè)馬氏鏈的狀態(tài)空間為S = 1，2，3，4，其一步轉(zhuǎn)移矩陣為,試研究各狀態(tài)間的關(guān)系。,解,狀態(tài)空間為S分兩個(gè)部分：= 1，2，3， =4,是閉集,中狀態(tài)4可到達(dá) 中各狀態(tài)，且它非吸收狀態(tài)，所以 不是閉集。,