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

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

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

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

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

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

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

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

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

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

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

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

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

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

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