馬爾柯夫狀態(tài)轉(zhuǎn)移圖與轉(zhuǎn)移矩陣

1、馬爾柯夫過程潘爾順 副教授上海交通大學(xué)工業(yè)工程與管理系12/9/2021主要內(nèi)容n基本概念n馬爾柯夫過程n馬爾柯夫狀態(tài)轉(zhuǎn)移圖n馬 柯夫轉(zhuǎn)移矩陣12/9/2021基本概念隨機過程（Random Process）隨機事件的變化過程。隨機過程無確定的變化形式及必然的變化規(guī)律，因而不可能用精確的數(shù)學(xué)關(guān)系式來表達，但可用隨機函數(shù)來描述。隨機函數(shù)X(t)在時間t1時的取值，稱為X(t)在t=t1時的狀態(tài)，它也是隨機變量，而t則稱為過程參數(shù)。兩者所有可能值的集合，分別稱為“狀態(tài)空間”和“參數(shù)空間”12/9/2021基本概念當(dāng)系統(tǒng)完全由定義狀態(tài)的變量值來描述時，則稱這個系統(tǒng)處于一種狀態(tài)。當(dāng)描述系統(tǒng)的變量從一種

2、狀態(tài)的特定值變化到另一種狀態(tài)的特定值時，則稱改系統(tǒng)實現(xiàn)了狀態(tài)的轉(zhuǎn)移。馬爾柯夫過程就是研究系統(tǒng)的“狀態(tài)”與“狀態(tài)”間的相互轉(zhuǎn)移關(guān)系的。狀態(tài)轉(zhuǎn)移圖-圖15-412/9/2021馬爾柯夫過程在系統(tǒng)可靠性的研究中，值得注意的一種性質(zhì)就是隨機變量X(t)在任意時刻tn時的狀態(tài)X(tn)與過去所有時刻ti(1 in-1)時的狀態(tài)X(ti)間的關(guān)系。對于這一性質(zhì)，可用下述條件概率來描述：當(dāng)隨機過程中出現(xiàn)的系統(tǒng)狀態(tài)已定時，則出現(xiàn)下一個系統(tǒng)狀態(tài)X(tn)=xn的條件概率為則稱112211)(,)(,)(nnxtXxtXxtXnnnnntttxtXxtXxtXxtXP211122110)(,)(,)(|)(有關(guān)，

3、與)(,)()()(121nntXtXtXtX12/9/2021馬爾柯夫過程當(dāng)條件概率為時，則稱X(tn)與過去歷史無關(guān)，即為獨立隨機過程當(dāng)條件概率為時，則稱X(tn)僅與前一狀態(tài)X(tn-1)有關(guān)而與更前的狀態(tài)無關(guān)。這一隨機過程就是最簡單的馬爾柯夫過程，稱為“一步馬爾柯夫過程”或“簡單馬爾柯夫過程”)()(,)(,)(|)(112211nnnnnnxtXPxtXxtXxtXxtXP)(|)()(,)(,)(|)(11112211nnnnnnnnxtXxtXPxtXxtXxtXxtXP12/9/2021馬爾柯夫過程將上述過程推廣到一般，則馬爾柯夫過程是這樣一種隨機過程，即其隨機變量在任意時刻t

4、n時的狀態(tài)X(tn)，僅與其前有限次數(shù)之內(nèi)的狀態(tài)X(tn-i-1), X(tn-i-2), ,X(tn-i)有關(guān)，而與以前的狀態(tài)無關(guān)。馬爾柯夫過程所具有的這種更以前的各種狀態(tài)不影響現(xiàn)狀態(tài)X(tn)的性質(zhì)，稱為“馬氏性”或“無后效性”，“無記憶性”。而馬爾柯夫過程又稱為“無記憶過程”。12/9/2021馬爾柯夫過程為了方便，現(xiàn)將狀態(tài)X(tn)記為j, X(tn-1)記為i，則式可寫為條件概率Pij稱為過程從狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率。如果馬爾可夫過程從一個給定狀態(tài)向另一個狀態(tài)轉(zhuǎn)移的概率僅與兩狀態(tài)的相對時間有關(guān)，而與觀測時刻無關(guān)，或具體觀測時間變化時其轉(zhuǎn)移概率值仍不變，即則稱為“穩(wěn)態(tài)馬而可夫過程”，

5、“平穩(wěn)”，“齊次”。ijnnPitXjtXP)(|)(1constPitXjtXPijnn)(|)(112/9/2021馬爾柯夫狀態(tài)轉(zhuǎn)移圖馬爾可夫的狀態(tài)轉(zhuǎn)移，可用馬爾可夫狀態(tài)轉(zhuǎn)移圖來說明例：一臺可修復(fù)的設(shè)備存在著正常運行狀態(tài)i和故障狀態(tài)j間的狀態(tài)轉(zhuǎn)移問題。如果該設(shè)備在運行了一段時間后處于狀態(tài)i的概率為2/3，則它轉(zhuǎn)移到狀態(tài)j的概率為1-2/3=1/3。簡記為Pii=2/3，Pij=1/3。反之，如果該設(shè)備處于狀態(tài)j而經(jīng)過維修后轉(zhuǎn)移到狀態(tài)i的概率是3/4，那么它處于狀態(tài)j的概率則為1-3/4=1/4，簡記為Pji=3/4,Pjj=1/412/9/2021馬爾柯夫狀態(tài)轉(zhuǎn)移圖用馬爾可夫狀態(tài)轉(zhuǎn)移圖可以

6、簡單而清晰地反映這一過程。因此，在用馬爾可夫過程求解系統(tǒng)或設(shè)備的狀態(tài)概率時，應(yīng)首先作出相應(yīng)的狀態(tài)轉(zhuǎn)移圖，并填入有關(guān)概率值，則會一目了然并方便求解。ij3/1ijP4/3jiP4/3jjP3/2iiP圖2 馬爾可夫狀態(tài)轉(zhuǎn)移圖12/9/2021馬爾柯夫轉(zhuǎn)移矩陣圖2所示的馬爾可夫狀態(tài)轉(zhuǎn)移過程，也可用馬爾可夫轉(zhuǎn)移矩陣或簡稱“轉(zhuǎn)移矩陣”，“概率矩陣”來表達：矩陣中的元素均為轉(zhuǎn)移概率，例如，Pij為由狀態(tài)i至狀態(tài)j的轉(zhuǎn)移概率。矩陣行的位置為狀態(tài)轉(zhuǎn)移的起始位置，矩陣列的位置為狀態(tài)轉(zhuǎn)移的達到位置。4/14/33/13/2jiPPPPjiPjjjiijiijiji 12/9/2021馬爾柯夫轉(zhuǎn)移矩陣對于n狀態(tài)的

7、系統(tǒng)，若可能產(chǎn)生的狀態(tài)為S1,S2,Sn，且在狀態(tài)Si產(chǎn)生后，狀態(tài)j產(chǎn)生的條件概率為Pij（轉(zhuǎn)移概率），若由最初的分布中隨機地選出Si的概率為ai，則當(dāng)此事件群的條件概率為一定值且關(guān)系式成立時，稱此關(guān)系式為馬爾可夫鏈。當(dāng)可能產(chǎn)生的狀態(tài)為有限個時，又稱為有限馬爾可夫鏈。mnijinmjiPPaSSSSP,12/9/2021馬爾柯夫轉(zhuǎn)移矩陣且有njijijnii,n, iPnjiPa1121 1, 2 , 1, 01 n狀態(tài)系統(tǒng)的轉(zhuǎn)移矩陣為nn的方陣nnnnnnPPPPPPPPPP 212222111211轉(zhuǎn)移矩陣的各元素均為不大于1的非負元素，而每一行中的各元素之和均等于1。12/9/2021馬

8、爾柯夫轉(zhuǎn)移矩陣nnnPPPPPPPPPPPPP)0() 1()()0() 1 ()2()0() 1 (2系統(tǒng)初始狀態(tài)的概率向量由分量組成：當(dāng)從某一狀態(tài)I開始時，通常取該狀態(tài)的概率分量Pi=1,而其它分量取為0初始狀態(tài)的概率向量次轉(zhuǎn)移矩陣；二次轉(zhuǎn)移矩陣一次轉(zhuǎn)移矩陣；)0(2PPPPnnnPPP21)0(P12/9/2021例題某系統(tǒng)的狀態(tài)轉(zhuǎn)移圖如圖所示。若該系統(tǒng)的初始狀態(tài)的概率向量 ，求各次轉(zhuǎn)移后系統(tǒng)所處的狀態(tài)。當(dāng) 又該如何？馬爾柯夫轉(zhuǎn)移矩陣解：由圖可知轉(zhuǎn)移矩陣為 01)0(FSPPP 10)0(FSPPP5/35/22/12/1P12/9/2021由 得 馬爾柯夫轉(zhuǎn)移矩陣 01)0(FSPPP

9、 9594)0() 1()(20112095/35/22/12/12/12/1)0()2(5 . 05 . 02/12/15/35/22/12/101)0() 1 (2nnnPPPPPPPPPPP12/9/2021當(dāng) 時 馬爾柯夫轉(zhuǎn)移矩陣 10)0(FSPPP9594)0() 1()(524152115/35/22/12/15/35/2)0()2(5/35/25/35/22/12/110)0() 1 (2nnnPPPPPPPPPPP12/9/2021馬爾柯夫轉(zhuǎn)移矩陣隨著轉(zhuǎn)移步數(shù)n的增加，狀態(tài)趨于穩(wěn)定。穩(wěn)定狀態(tài)的概率稱為極限概率。例如上題中最后穩(wěn)定在：正常狀態(tài)為4/9；故障狀態(tài)為5/9，這是極限

10、狀態(tài)概率。馬爾可夫過程的特性之一，就是它的極限狀態(tài)矩陣與初始狀態(tài)無關(guān)或極限狀態(tài)概率與初始狀態(tài)無關(guān)。這種過程稱為“各態(tài)歷經(jīng)過程”或“遍歷過程”，其狀態(tài)轉(zhuǎn)移矩陣稱為“遍歷矩陣”。12/9/2021馬爾柯夫轉(zhuǎn)移矩陣例題試檢驗矩陣 是否為遍歷矩陣解：將大于0的元素均以x表示，檢驗經(jīng)n次方計算后矩陣的各元素是否均大于002/12/1100010P00000 xxxxPxxxxxxxxxxxxx000000000000002P12/9/2021馬爾柯夫轉(zhuǎn)移矩陣可見矩陣P為遍歷矩陣xxxxxxxxxxxxxxxxxx0000000004Pxxxxxxxxxxxxxxxxxxxxxxxxx008P12/9/2021馬爾柯夫轉(zhuǎn)移矩陣當(dāng)概率矩陣P為正規(guī)的遍歷矩陣時，則具有以下性質(zhì)：Pn隨著轉(zhuǎn)移步數(shù)n的增加而趨于某一穩(wěn)定矩陣。即各態(tài)轉(zhuǎn)移的概率趨于穩(wěn)定；穩(wěn)定矩陣的各元素均大于0；穩(wěn)定矩陣的各行是同一概率向量：且21nxxxX11niix12/9/2021馬爾柯夫轉(zhuǎn)移矩陣既然極限狀態(tài)概率向量不再變化，因此，即使再轉(zhuǎn)移一步，其狀態(tài)概率也是不會變的，故有XPX也是穩(wěn)定矩陣的行向量的固有向量