第十一章馬爾科夫鏈

1、第十一章第十一章 馬爾科夫鏈馬爾科夫鏈11.1 馬爾科夫過程及其概率分布馬爾科夫過程及其概率分布1. 馬爾科夫過程馬爾科夫過程 若隨機(jī)過程若隨機(jī)過程X(t), t T對于任意的正整數(shù)對于任意的正整數(shù)n及及 t1 1 t2 2tn T, 其條件分布滿足其條件分布滿足 PX (tn) xn| X(t1 1) = x1 1, X(tn-1-1) = xn-1-1 = PX (tn) xn| X(tn-1-1) = xn-1-1, xn R 或?qū)懗苫驅(qū)懗?;|,( ),.,;,.,|,(111|1211211.|1 nnnnnttnnnnnttttxtxFtttxxxtxFnn 則稱隨機(jī)過程則稱隨機(jī)過

2、程X(t), t T 為為馬爾科夫過馬爾科夫過程程. 2. 馬爾科夫鏈馬爾科夫鏈 時間和狀態(tài)都是離散的馬爾科夫過稱時間和狀態(tài)都是離散的馬爾科夫過稱為為馬爾科夫鏈馬爾科夫鏈，簡稱馬氏鏈，簡稱馬氏鏈. 記為記為 Xn=X(n)，n = 0,1,2,. 它可以看作在時間集它可以看作在時間集T1 = 0,1,2, 上的離上的離散狀態(tài)的馬氏過程相繼觀察的結(jié)果散狀態(tài)的馬氏過程相繼觀察的結(jié)果. 鏈的狀態(tài)空間：鏈的狀態(tài)空間：I = a1 1 ,a2 2 , , ai i R.3. 轉(zhuǎn)移概率轉(zhuǎn)移概率 對任意得正整數(shù)對任意得正整數(shù)n, r和和0t1 1 t2 2 tr m; ti , m, n+m T1 1有有

3、其中其中ai I. 則稱條件概率則稱條件概率 Pij(m,m+n) = PXm+n = aj |Xm = ai 為馬氏鏈在時刻為馬氏鏈在時刻m, 處于狀態(tài)處于狀態(tài)ai條件下，在時刻條件下，在時刻 m+n轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)aj的的轉(zhuǎn)移概率轉(zhuǎn)移概率.,| ,|2211imjnmimitititjnmaXaXPaXaXaXaXaXPrr 4. 轉(zhuǎn)移概率矩陣轉(zhuǎn)移概率矩陣 由轉(zhuǎn)移概率組成的矩陣由轉(zhuǎn)移概率組成的矩陣 稱為馬氏鏈的稱為馬氏鏈的轉(zhuǎn)移概率矩陣轉(zhuǎn)移概率矩陣. 此矩陣的每此矩陣的每一行元素之和等于一行元素之和等于1. 當(dāng)轉(zhuǎn)移概率當(dāng)轉(zhuǎn)移概率Pij(m,m+n)只與只與i, j及時間距及時間距n有關(guān)時

4、，把它記為有關(guān)時，把它記為Pij(n), 即即 并稱轉(zhuǎn)移概率具有并稱轉(zhuǎn)移概率具有平穩(wěn)性平穩(wěn)性，同時也稱此鏈，同時也稱此鏈 是是齊次的或時齊的齊次的或時齊的.)(),(nPnmmPijij ),(),(nmmPnmmPij 5. n步轉(zhuǎn)移概率和步轉(zhuǎn)移概率和n步轉(zhuǎn)移矩陣步轉(zhuǎn)移矩陣 n步轉(zhuǎn)移概率步轉(zhuǎn)移概率 : n步轉(zhuǎn)移概率矩陣步轉(zhuǎn)移概率矩陣: 一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率: 一步轉(zhuǎn)移概率矩陣一步轉(zhuǎn)移概率矩陣 : |)(imjnmijaXaXPnP )()(nPnPij imjmijijaXaXPPp 1)1(的的狀狀態(tài)態(tài)1 mXp1111p1212p1j1jp2121p2222p2j2jpi1i1pi2

5、i2pijija1 1 a2 2 aj j a1 1 a2 2 . .ai i .態(tài)態(tài)狀狀的的mX.) 1 (PP 例例1. （0-1傳輸系統(tǒng)）傳輸系統(tǒng)）在如下圖只傳輸數(shù)字在如下圖只傳輸數(shù)字0和和1的串聯(lián)系統(tǒng)中，的串聯(lián)系統(tǒng)中，1.設(shè)每一級的傳真率為設(shè)每一級的傳真率為p，誤碼率為，誤碼率為q = 1-p（輸出與輸入數(shù)字（輸出與輸入數(shù)字相同的概率稱為系統(tǒng)的傳真率，相反情形稱為誤碼率）相同的概率稱為系統(tǒng)的傳真率，相反情形稱為誤碼率）;2.設(shè)一個單位時間傳輸一級設(shè)一個單位時間傳輸一級, X0 0是第一級的輸入，是第一級的輸入，Xn n是第是第n級級的輸出的輸出(n1), 那么那么 是一隨機(jī)過程是一隨機(jī)

6、過程.3.狀態(tài)空間狀態(tài)空間I=0,1，而且當(dāng)，而且當(dāng)Xn n=i , iI為已知時，為已知時， Xn+1n+1所處所處的狀態(tài)的概率分布只的狀態(tài)的概率分布只與與Xn n= i有關(guān)，而與時刻有關(guān)，而與時刻n以前所處的以前所處的狀態(tài)無關(guān)，所以它是一個馬氏鏈，而且還是齊次的狀態(tài)無關(guān)，所以它是一個馬氏鏈，而且還是齊次的. 它的它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為 ,.2,1 ,0, nXn12nX0 0X1 1Xn nX2 2Xn-1n-1 和和 例例2 一維隨機(jī)游動一維隨機(jī)游動 設(shè)一醉漢設(shè)一醉漢Q在如下圖點集在如下圖點集I=1,2,3,4,5上上作隨機(jī)游動，并且

7、僅僅在作隨機(jī)游動，并且僅僅在1秒、秒、2秒秒等時刻發(fā)生游動等時刻發(fā)生游動.規(guī)律是：規(guī)律是：(1) 如果如果Q現(xiàn)在位于點現(xiàn)在位于點i(1i5), 則下一時刻各以則下一時刻各以1/3的概率向左的概率向左或向右移動一格，或以或向右移動一格，或以1/3的概率留在原處；的概率留在原處； (2) 如果如果Q現(xiàn)在位于現(xiàn)在位于1（或（或5）這點上，則下一時刻就以概率）這點上，則下一時刻就以概率1移移動動2（或（或4）這一點上）這一點上. 1和和5這兩點稱為這兩點稱為反射壁反射壁. 上面這種游動上面這種游動稱為稱為帶有兩個反射壁的隨機(jī)游動帶有兩個反射壁的隨機(jī)游動. 1 ,0, ,1 jiijqijpiXjXpp

8、nnij pqqpp100 1 2 , 0, 4, 52, 1 , 1, 51 , 1, 1,31|1ijjijiiiiijiXjXPpnnij或或 若以若以Xn表示時刻表示時刻n時時Q的位置，不同的位置就是的位置，不同的位置就是Xn的不同狀的不同狀態(tài)，那么態(tài)，那么 Xn , n=0,1,2,是一隨機(jī)過程，狀態(tài)空間就是是一隨機(jī)過程，狀態(tài)空間就是I，而且而且Xn=i, i I為已知時，為已知時， Xn+1+1所處的狀態(tài)的概率分布只與所處的狀態(tài)的概率分布只與Xn= i 有關(guān)，而與有關(guān)，而與Q在時刻在時刻n以前如何達(dá)到是完全無關(guān)的，所以前如何達(dá)到是完全無關(guān)的，所以以 Xn , n = 0,1,2,

9、是一馬氏鏈，而且還是齊次的，它的是一馬氏鏈，而且還是齊次的，它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為 如果把一這一點改為吸收壁，即是說如果把一這一點改為吸收壁，即是說Q一旦到達(dá)一旦到達(dá)1這一這一點，則就永遠(yuǎn)留在點一上，相應(yīng)鏈的轉(zhuǎn)移概率矩陣只點，則就永遠(yuǎn)留在點一上，相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把須把p中的第一橫行改為（中的第一橫行改為（1，0，0，0，0）. 總之改變總之改變游動的概率規(guī)則，就可得到不同方式的隨機(jī)游動和相游動的概率規(guī)則，就可得到不同方式的隨機(jī)游動和相應(yīng)的馬氏鏈應(yīng)的馬氏鏈. 隨機(jī)游動的思想在數(shù)值計算方法方面有重要應(yīng)用隨機(jī)游動的思想在數(shù)值計算方法方面有

10、重要應(yīng)用.010001/31/31/30001/31/31/30001/31/31/3000101 2 3 4 512345例例3 排隊模型排隊模型 服務(wù)系統(tǒng)組成服務(wù)系統(tǒng)組成：服務(wù)員（：服務(wù)員（1個）個）, 等候室（等候室（2人）人）.服務(wù)規(guī)則服務(wù)規(guī)則：先到先服務(wù)：先到先服務(wù). 假定一顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)假定一顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有內(nèi)已有3個顧客，則該顧客即離去個顧客，則該顧客即離去.1.設(shè)時間間隔設(shè)時間間隔t內(nèi)，有一個顧客進(jìn)入系統(tǒng)的概率為內(nèi)，有一個顧客進(jìn)入系統(tǒng)的概率為q，有一，有一原來被服務(wù)的顧客離開系統(tǒng)的概率為原來被服務(wù)的顧客離開系統(tǒng)的概率為p.2.設(shè)當(dāng)設(shè)當(dāng)t充分小時，在這個時間間

11、隔內(nèi)多于一個顧客進(jìn)入或充分小時，在這個時間間隔內(nèi)多于一個顧客進(jìn)入或離開系統(tǒng)實際上是不可能的離開系統(tǒng)實際上是不可能的.3.設(shè)有無顧客來到與服務(wù)是否完畢是相互獨立的設(shè)有無顧客來到與服務(wù)是否完畢是相互獨立的.等候室服務(wù)臺隨機(jī)到達(dá)者離去者系 統(tǒng) 設(shè)設(shè)Xn = X(nt )表示時刻表示時刻 nt 時系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀時系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀態(tài)態(tài). 是一隨機(jī)過程，狀態(tài)空間是一隨機(jī)過程，狀態(tài)空間I=0,1,2,3 ，由前例的分析，由前例的分析, 可知它是一個齊次馬氏鏈可知它是一個齊次馬氏鏈. 下面下面來計算此馬氏鏈的一步轉(zhuǎn)移概率來計算此馬氏鏈的一步轉(zhuǎn)移概率. p00 00 表示在系統(tǒng)內(nèi)沒有顧客的

12、條件下，經(jīng)表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)t 后仍沒有顧客后仍沒有顧客的概率（此處是條件概率，以下同）的概率（此處是條件概率，以下同） p0000 = 1- -q. p01 01 表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)t 后有一顧客進(jìn)后有一顧客進(jìn)入系統(tǒng)的概率，入系統(tǒng)的概率，p0101 = q. p10 10 系統(tǒng)內(nèi)恰有一個顧客正在接受服務(wù)的條件下，經(jīng)系統(tǒng)內(nèi)恰有一個顧客正在接受服務(wù)的條件下，經(jīng)t 后后 .,2 , 1 ,0, nXn 系統(tǒng)內(nèi)無人的概率，它等于在系統(tǒng)內(nèi)無人的概率，它等于在t 間隔內(nèi)顧客因服務(wù)完畢而間隔內(nèi)顧客因服務(wù)完畢而離去離去 ，且無人進(jìn)入系統(tǒng)的概率，且無

13、人進(jìn)入系統(tǒng)的概率，p1010 = p(1 q) p1111系統(tǒng)內(nèi)恰有一顧客的條件下，在系統(tǒng)內(nèi)恰有一顧客的條件下，在t 間隔內(nèi)，他因服務(wù)間隔內(nèi)，他因服務(wù)完畢而離去，而另一顧客進(jìn)入系統(tǒng)，或者正在接受服務(wù)的完畢而離去，而另一顧客進(jìn)入系統(tǒng)，或者正在接受服務(wù)的顧客將繼續(xù)要求服務(wù)，且無人進(jìn)入系統(tǒng)的概率，顧客將繼續(xù)要求服務(wù)，且無人進(jìn)入系統(tǒng)的概率， p1111 = pq + (1-p)(1-q). p1212 正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且另一個顧客進(jìn)正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且另一個顧客進(jìn)入系統(tǒng)的概率入系統(tǒng)的概率, p1212 = (1-p)q. p1313正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且在正在

14、接受服務(wù)的顧客繼續(xù)要求服務(wù)，且在t 間隔內(nèi)有間隔內(nèi)有兩個顧客進(jìn)入系統(tǒng)的概率兩個顧客進(jìn)入系統(tǒng)的概率 ，由假設(shè)，后者實際上是不可能，由假設(shè)，后者實際上是不可能發(fā)生的，發(fā)生的， p1313 =0.類似地，有類似地，有p2121 = p3232 = p(1-q), p2222 = pq + (1-p)(1-q) , p2323 = q(1-p), pij = 0, (|i-j |2).p3333 : : 或者一人將離去且另一人將進(jìn)入系統(tǒng)，或者無人離開或者一人將離去且另一人將進(jìn)入系統(tǒng)，或者無人離開的概率，的概率， p3333 = pq + (1-p).于是該馬氏鏈的一步轉(zhuǎn)移概率矩陣為于是該馬氏鏈的一步轉(zhuǎn)

15、移概率矩陣為 1-qq00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p) 在實際問題中，一步轉(zhuǎn)移概率通?？赏ㄟ^統(tǒng)計實驗確定在實際問題中，一步轉(zhuǎn)移概率通常可通過統(tǒng)計實驗確定. 例例4 某計算機(jī)機(jī)房的一臺計算機(jī)經(jīng)常出故障，研究者每某計算機(jī)機(jī)房的一臺計算機(jī)經(jīng)常出故障，研究者每隔隔15分鐘觀察一次計算機(jī)的運行狀態(tài)，收集了分鐘觀察一次計算機(jī)的運行狀態(tài)，收集了24小時的數(shù)據(jù)小時的數(shù)據(jù)(共作共作97次觀察次觀察). 用用1表示正常狀態(tài)，用表示正常狀態(tài)，用0表示不正常狀態(tài)，表示不正常狀態(tài)，所得的數(shù)據(jù)序列如下：

16、所得的數(shù)據(jù)序列如下： 1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111 設(shè)設(shè)Xn為第為第n (n =1,2,97)個時段的計算機(jī)狀態(tài)，可以認(rèn)為它個時段的計算機(jī)狀態(tài)，可以認(rèn)為它是一個馬氏鏈，狀態(tài)空間是一個馬氏鏈，狀態(tài)空間I=0, 1. 96次狀態(tài)轉(zhuǎn)移的情況是：次狀態(tài)轉(zhuǎn)移的情況是： 0 0, 80 0, 8次；次； 0 1, 180 1, 18次；次； 1 0, 181 0, 18次次; 1 1, 52; 1 1, 52次次. . 因此，一步轉(zhuǎn)移概率可用

17、頻率近似地表示為因此，一步轉(zhuǎn)移概率可用頻率近似地表示為 ,268188800100 nnXXPp ,26181881801101 nnXXPp ,701852181810110 nnXXPp .705252185211111 nnXXPp6.齊次馬氏鏈的有限維分布齊次馬氏鏈的有限維分布. 馬氏鏈的初始分布為馬氏鏈的初始分布為: 1) 馬氏鏈在任一時刻馬氏鏈在任一時刻 n T1 1 的一維分布：的一維分布：顯然，應(yīng)有顯然，應(yīng)有 由全概率公式得由全概率公式得即即 .1)(1 npjj, |100 iijnijnaXaXPaXPaXP,2,1 ),()0()(1 jnPpnpijiij,2, 1 ,

18、 ,)0(0 jIaaXPpjjj,2, 1 , ,)( jIaaXPnpjjnj一維分布也可用行向量表示成一維分布也可用行向量表示成p(n) = ( p1 1(n), p2 2(n),pj j(n),)這樣，利用矩陣乘法（這樣，利用矩陣乘法（I是可列無限集時，仍用有限階）矩是可列無限集時，仍用有限階）矩陣乘法的規(guī)則確定矩陣之積的元素，可寫成陣乘法的規(guī)則確定矩陣之積的元素，可寫成p(n) = p(0)P(n) (矩陣矩陣)結(jié)論結(jié)論：馬氏鏈在任一時刻：馬氏鏈在任一時刻 n T1 1 時的一維分布由初始分布時的一維分布由初始分布 p(0) 和和 n 步轉(zhuǎn)移概率矩陣所確定步轉(zhuǎn)移概率矩陣所確定. 對于

19、任意對于任意 n 個時刻個時刻 t1 1t2 2 t tn, ti T1 1以及狀態(tài)以及狀態(tài) 有：有： 2)馬氏鏈的馬氏鏈的 n維分布維分布：,.,21Iaaaniii 由乘法公式由乘法公式,2211nnitititaXaXaXP )()()(| |,| 1121121111112211112211 nniiiiiitiiitititititititttPttPtpaXaXPaXaXPaXPaXaXaXaXPnnnnnnnnnn結(jié)論結(jié)論：由此可知，馬氏鏈的有限維分布同樣完全由初始分：由此可知，馬氏鏈的有限維分布同樣完全由初始分布和轉(zhuǎn)移概率確定布和轉(zhuǎn)移概率確定.總之總之,轉(zhuǎn)移概率決定了馬氏鏈的統(tǒng)

20、計規(guī)律轉(zhuǎn)移概率決定了馬氏鏈的統(tǒng)計規(guī)律. 因此因此,確定馬氏鏈確定馬氏鏈的任意的任意n步轉(zhuǎn)移概率就成為馬氏鏈理論中的重要問題之一步轉(zhuǎn)移概率就成為馬氏鏈理論中的重要問題之一.,2211nnitititaXaXaXP |112211itititaXaXPaXP 例例5（續(xù)例（續(xù)例4）若計算機(jī)在前一段（）若計算機(jī)在前一段（15分鐘）的狀態(tài)為分鐘）的狀態(tài)為0，問從時段起此計算機(jī)能連續(xù)正常工作一小時（問從時段起此計算機(jī)能連續(xù)正常工作一小時（4個時段）的個時段）的概率為多少？概率為多少？ 解解 由題意，前一時段的狀態(tài)為由題意，前一時段的狀態(tài)為0就是初始分布就是初始分布 p0 0(0) =PX0 0= 0=1

21、. 計算機(jī)能連續(xù)正常工作計算機(jī)能連續(xù)正常工作4個時段的概率為個時段的概率為 PX0 0 = 0, X1 1= 1, X2 2 = 1, X3 3 = 1, X4 4 = 1 = PX0 0 = 0PX1 1= 1| X0 0 = 0PX2 2 = 1| X1 1= 1 PX3 3 = 1| X2 2 = 1PX4 4 = 1| X3 3 = 1 = p0 0 (0) P0101 (1) P1111 (1) P1111 (1) P1111 (1) .284.070527052705226181 11.2 多步轉(zhuǎn)移概率的確定多步轉(zhuǎn)移概率的確定 為了確定齊次馬氏鏈的為了確定齊次馬氏鏈的 n 步轉(zhuǎn)移概

22、率步轉(zhuǎn)移概率 首先介紹首先介紹 所滿足的基本方程所滿足的基本方程. 設(shè)設(shè)X(n), n T1 1是一齊次馬氏鏈，則對任意的是一齊次馬氏鏈，則對任意的u,v T1 1 ,有有 這就是著名的切普曼這就是著名的切普曼-柯莫哥洛夫柯莫哥洛夫 (Chapman-Kolmogorov)方程，簡稱方程，簡稱C-K方程方程.),(nPij)1 . 2( 2 , 1, ),()()(1 jivPuPvuPkjkikij)(nPijC-K方程的實際背景方程的實際背景 C-K方程基于下述事實，即方程基于下述事實，即“從時刻從時刻 s 所處的狀態(tài)所處的狀態(tài) ai，即即 X (s) = ai 出發(fā)，經(jīng)時段出發(fā)，經(jīng)時段

23、u + v 轉(zhuǎn)移轉(zhuǎn)移 到狀態(tài)到狀態(tài) aj , 即即 X(s + u + v) = aj”這一事件可分解成這一事件可分解成“從從X(s) = ai”出發(fā)，出發(fā)，先經(jīng)時段先經(jīng)時段 u 轉(zhuǎn)移到中間狀態(tài)轉(zhuǎn)移到中間狀態(tài) ak k(k = 1,2)，再從，再從 ak 經(jīng)經(jīng)時段時段 v 轉(zhuǎn)移轉(zhuǎn)移 到狀態(tài)到狀態(tài) aj”這樣一些事件的和事件這樣一些事件的和事件.(如下圖如下圖)aiajOss+us+u+vt 方程（方程（2.1）的證明如下：先固定）的證明如下：先固定 和和 由于事件組由于事件組“X(s + u) = ak”, k = 1,2,構(gòu)成一劃分構(gòu)成一劃分,故有故有 Pij(u+v) = PX(s+u+v

24、)= aj|X(s)=ai又由條件概率定義和乘法定理，有又由條件概率定義和乘法定理，有 (馬氏鏈的齊次性馬氏鏈的齊次性) 將上式代入將上式代入(2.2) ，即得所要證明的，即得所要證明的 C-K 方程方程. ikjasXausXavusXP )()(,)( ).()()(,)()()()(vPuPasXausXavusXPasXausXPkjikikjik Iak 1Ts C-K方程的證明方程的證明(2.2) ,)(|)(,)(1ikjkasXausXavusXP C-K方程也可寫成矩陣形式：方程也可寫成矩陣形式：P(u+v) = P(u)P (v) 利用利用C-K方程我們?nèi)菀状_定方程我們?nèi)菀?/p>

25、確定 n 步轉(zhuǎn)移概率步轉(zhuǎn)移概率, 事實上事實上, 在在(2.1)式式中令中令u = 1, v = n- -1，得遞推關(guān)系：，得遞推關(guān)系： P(n)= P(1) P(n- -1) =P P(n- -1), 從而可得從而可得 P(n)= Pn, 就是說，對齊次馬氏鏈而言，就是說，對齊次馬氏鏈而言， n步轉(zhuǎn)移概率矩陣是步轉(zhuǎn)移概率矩陣是一一步轉(zhuǎn)移步轉(zhuǎn)移概率矩陣的概率矩陣的 n 次方次方. 進(jìn)而可知，齊次馬氏鏈的有限維分布可進(jìn)而可知，齊次馬氏鏈的有限維分布可由初始分布與由初始分布與一一步轉(zhuǎn)移概率完全確定步轉(zhuǎn)移概率完全確定. 例例1 設(shè)設(shè)Xn,n0是具有三個狀態(tài)是具有三個狀態(tài)0, 1, 2的齊次馬氏鏈，的

26、齊次馬氏鏈，一一步步轉(zhuǎn)移概率矩陣為轉(zhuǎn)移概率矩陣為 初始分布初始分布pi(0) = PX0 0 = i = 1/3, i = 0,1,2. 試求試求 (i) PX0 0 = 0, X2 2 = 1; (ii) PX2 2 = 1 解解 先求出二步轉(zhuǎn)移概率矩陣先求出二步轉(zhuǎn)移概率矩陣于是于是(i) PX0 0= 0 ,X2 2=1 = PX0 0=0 PX2 2=1| X0 0=0 = p0 0(0) P0101(2)0120123/41/401/41/21/403/41/4P=0 1 25/85/161/165/161/23/63/169/161/4P(2) = P2 =0 1 2.4851653

27、1 3/4 1/401/4 1/2 1/403/4 1/43/4 1/401/4 1/2 1/403/4 1/4=(ii) 由由(1.7)式，式，p1 1(2) = PX2 2=1 = p0 0(0) P0101(2) + p1 1(0)P1111(2) + p2 2(0) P2121(2) = 例例2 在在1例例2中中, (i) 設(shè)設(shè) p = 0.9, 求系統(tǒng)二級傳輸后的傳真率求系統(tǒng)二級傳輸后的傳真率與三級傳輸后的誤碼率；與三級傳輸后的誤碼率； (ii) 設(shè)初始分布設(shè)初始分布 p1 1(0) = PX0 0 = 1 = , p0 0 (0) = P X0 0 = 0 = 1 - ，又已知系統(tǒng)

28、經(jīng)，又已知系統(tǒng)經(jīng) n 級傳輸后級傳輸后輸出為輸出為 1，問原發(fā)字符也是，問原發(fā)字符也是1的概率是多少？的概率是多少？ 解解 先求出先求出n步轉(zhuǎn)移概率矩陣步轉(zhuǎn)移概率矩陣P(n) = Pn . 由于由于 則令則令 得得 1 1 = 1， 2 2 = p- -q 則可將則可將P表示成對角矩陣表示成對角矩陣 的相似矩陣的相似矩陣. 0124111692116531 P=0 1 qp001, 00 ,11 0| pqqpPE pqqp 求出求出1 1， 2 2 的特征向量是的特征向量是 方法是令方法是令(1 1E-P)X = 0及及(2 2E- -P)X = 0,就可以求得就可以求得 e1 1, e2

29、2 令令H=e1 1,e2 2 則有則有 2/12/11e 2/12/12e,2/ 12/ 12/ 12/ 1 2/12/12/12/10012/12/12/12/1)(11nnnnqpHHHHP 2/ 12/ 12/ 12/ 11H nnnnnnnqpqpqpqpqpqpqp)(2121)(2121)(2121)(21212/12/12/12/1)(2121)(21212/12/12/12/1)(0012/12/12/12/1(i) 由此可知，當(dāng)由此可知，當(dāng) p = 0.9時，系統(tǒng)經(jīng)二級傳輸后的傳真率與時，系統(tǒng)經(jīng)二級傳輸后的傳真率與三級傳輸?shù)恼`碼率發(fā)表分別為三級傳輸?shù)恼`碼率發(fā)表分別為 P11

30、11(2) = P0000 (2) = P1010(3) = P0101(3) = (ii) 根據(jù)貝葉斯公式，當(dāng)已知系統(tǒng)經(jīng)根據(jù)貝葉斯公式，當(dāng)已知系統(tǒng)經(jīng) n 級傳輸后輸出為級傳輸后輸出為1，原發(fā)字符也是原發(fā)字符也是1的概率為的概率為,820.0)1.09.0(21212 ;244.0)1 .09 .0(21213 111111000 nnnXPXXPXPXXPnnqpqpnPpnPpnPp)(12(1)()()0()()0()()0(111010111 對于只有兩個狀態(tài)的馬氏鏈，一步轉(zhuǎn)移概率矩陣一般可表示為：對于只有兩個狀態(tài)的馬氏鏈，一步轉(zhuǎn)移概率矩陣一般可表示為： 利用類似于例利用類似于例2的方

31、法，可得的方法，可得 n 步轉(zhuǎn)移概率矩陣為步轉(zhuǎn)移概率矩陣為 11.3 遍歷性遍歷性 對于一般的兩個狀態(tài)的馬氏鏈，當(dāng)對于一般的兩個狀態(tài)的馬氏鏈，當(dāng)0a, b1 時就可得到時就可得到 n 步轉(zhuǎn)移概率步轉(zhuǎn)移概率的近似值：的近似值： 遍歷性和極限分布的意義遍歷性和極限分布的意義：設(shè)齊次馬氏鏈的狀態(tài)空間為：設(shè)齊次馬氏鏈的狀態(tài)空間為 I , 如果對于所有如果對于所有ai ajI, 轉(zhuǎn)移概率轉(zhuǎn)移概率Pij (n)存在極限存在極限 (不依賴于不依賴于i)jp110 p pp pp pp pp p ),(10.)(jijnPp p jijnnPp p )(lim 則稱此鏈具有則稱此鏈具有遍歷性遍歷性，又若，又若

32、 則同時稱則同時稱 為鏈的為鏈的極限分布極限分布. 齊次馬氏鏈在什么條件下才具有遍歷性？齊次馬氏鏈在什么條件下才具有遍歷性？ 如何求出它的極限分布？如何求出它的極限分布？ 這問題在理論上已經(jīng)完滿解決，下面僅就只有有限個這問題在理論上已經(jīng)完滿解決，下面僅就只有有限個狀態(tài)的鏈，即有限的遍歷性給出一個充分條件狀態(tài)的鏈，即有限的遍歷性給出一個充分條件. .)(212121)(jjjnnPnPp pp pp pp pp pp pp pp pp p,1 jjp p,.),(21p pp pp p 定理定理 設(shè)齊次馬氏鏈設(shè)齊次馬氏鏈Xn,n 1的狀態(tài)空間為的狀態(tài)空間為I= a1 1, a2 2,aN , P

33、是它的一步轉(zhuǎn)移概率矩陣，如果存在正整數(shù)是它的一步轉(zhuǎn)移概率矩陣，如果存在正整數(shù) m ，使對任意，使對任意的的ai i ,ajI，都有，都有 Pij(m) 0, i, j = 1, 2, , N, 則此鏈具有遍歷性；且有極限分布則此鏈具有遍歷性；且有極限分布 它是方程組它是方程組 = P 或即或即 的滿足條件的滿足條件 的唯一解的唯一解. 依照定理，為證有限鏈?zhǔn)潜闅v的，只需要找一正整數(shù)依照定理，為證有限鏈?zhǔn)潜闅v的，只需要找一正整數(shù)m，使，使m步轉(zhuǎn)移概率矩陣步轉(zhuǎn)移概率矩陣 Pm無零元無零元. 而求極限分布而求極限分布的問題，化為求的問題，化為求解方程組的問題解方程組的問題. 注意，方程組中僅注意，方

34、程組中僅N-1個未知數(shù)，是獨立的，個未知數(shù)，是獨立的，而唯一解可用歸一條件而唯一解可用歸一條件 確定確定.),(21Np pp pp pp p NjpijNiij, 2 , 1 ,1 p pp p1, 01 Njjjp pp p11 njjp p 在定理的條件下，馬氏鏈的極限分布又是在定理的條件下，馬氏鏈的極限分布又是平穩(wěn)分布平穩(wěn)分布.即，即，若用若用作為鏈的初始分布，即作為鏈的初始分布，即p(0) = , 則鏈在任一時刻則鏈在任一時刻n T1 1的分布的分布p(n)永遠(yuǎn)與永遠(yuǎn)與一致一致. 事實上事實上, 有有 p(n) = p(0)P(n) = Pn = Pn-1 = = P = 例例1 試

35、說明試說明 1例例2中，帶有兩個放射壁的隨機(jī)游中，帶有兩個放射壁的隨機(jī)游動是遍歷的，并求其極限分布動是遍歷的，并求其極限分布(平穩(wěn)分布平穩(wěn)分布). 解解 為簡便計，以符號為簡便計，以符號“”代表轉(zhuǎn)移概率矩陣代表轉(zhuǎn)移概率矩陣 的的正元素，于是，由正元素，于是，由 1例例2中的一步轉(zhuǎn)移概率矩陣中的一步轉(zhuǎn)移概率矩陣 P，得得 000000000000)4(0000000000000000000000000000000000)2(42PPPP 即即p(4)無零元無零元. 由定理，鏈?zhǔn)潜闅v的由定理，鏈?zhǔn)潜闅v的. 寫出極限分布寫出極限分布 = (1 1，2 2, 5)5)滿足的方程組滿足的方程組 先由前四

36、個方程，解得：先由前四個方程，解得： 將它們將它們代入歸一條件，得唯一解：代入歸一條件，得唯一解： 所以極限分布為所以極限分布為 = (1/11, 3/11, 3/11, 3/11, 1/11), 這個這個分布表明：經(jīng)過長時間游動之后，醉漢分布表明：經(jīng)過長時間游動之后，醉漢Q位于點位于點i(1i5)的概率約為的概率約為3/11, 位于點位于點1或或5的概率約為的概率約為1/11. .1,)3/1(,)3/1()3/1()3/1()3/1()3/1(,)3/1()3/1(,)3/1(54321455434,4323321221p pp pp pp pp pp pp pp pp pp pp pp

37、pp pp pp pp pp pp pp pp pp p,3354321p pp pp pp pp p .11/3 ,11/143251 p pp pp pp pp p11.1 例例3 排隊模型排隊模型 服務(wù)系統(tǒng)組成服務(wù)系統(tǒng)組成：服務(wù)員（：服務(wù)員（1個）個）, 等候室（等候室（2人）人）.服務(wù)規(guī)則服務(wù)規(guī)則：先到先服務(wù)：先到先服務(wù). 假定一顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)假定一顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有內(nèi)已有3個顧客，則該顧客即離去個顧客，則該顧客即離去.1.設(shè)時間間隔設(shè)時間間隔t內(nèi)，有一個顧客進(jìn)入系統(tǒng)的概率為內(nèi)，有一個顧客進(jìn)入系統(tǒng)的概率為q，有一，有一原來被服務(wù)的顧客離開系統(tǒng)的概率為原來被服務(wù)的顧客離

38、開系統(tǒng)的概率為p.2.設(shè)當(dāng)設(shè)當(dāng)t充分小時，在這個時間間隔內(nèi)多于一個顧客進(jìn)入或充分小時，在這個時間間隔內(nèi)多于一個顧客進(jìn)入或離開系統(tǒng)實際上是不可能的離開系統(tǒng)實際上是不可能的.3.設(shè)有無顧客來到與服務(wù)是否完畢是相互獨立的設(shè)有無顧客來到與服務(wù)是否完畢是相互獨立的.等候室服務(wù)臺隨機(jī)到達(dá)者離去者系 統(tǒng) 設(shè)設(shè)Xn = X(nt )表示時刻表示時刻 nt 時系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀時系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀態(tài)態(tài). 是一隨機(jī)過程，狀態(tài)空間是一隨機(jī)過程，狀態(tài)空間I=0,1,2,3 ，由前例的分析，由前例的分析, 可知它是一個齊次馬氏鏈可知它是一個齊次馬氏鏈. 下面下面來計算此馬氏鏈的一步轉(zhuǎn)移概率來計算此馬氏鏈

39、的一步轉(zhuǎn)移概率. p00 00 表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)t 后仍沒有顧客后仍沒有顧客的概率（此處是條件概率，以下同）的概率（此處是條件概率，以下同） p0000 = 1- -q. p01 01 表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)表示在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)t 后有一顧客進(jìn)后有一顧客進(jìn)入系統(tǒng)的概率，入系統(tǒng)的概率，p0101 = q. p10 10 系統(tǒng)內(nèi)恰有一個顧客正在接受服務(wù)的條件下，經(jīng)系統(tǒng)內(nèi)恰有一個顧客正在接受服務(wù)的條件下，經(jīng)t 后后 .,2 , 1 ,0, nXn 系統(tǒng)內(nèi)無人的概率，它等于在系統(tǒng)內(nèi)無人的概率，它等于在t 間隔內(nèi)顧客因服務(wù)完畢而間隔內(nèi)

40、顧客因服務(wù)完畢而離去離去 ，且無人進(jìn)入系統(tǒng)的概率，且無人進(jìn)入系統(tǒng)的概率，p1010 = p(1 q) p1111系統(tǒng)內(nèi)恰有一顧客的條件下，在系統(tǒng)內(nèi)恰有一顧客的條件下，在t 間隔內(nèi)，他因服務(wù)間隔內(nèi)，他因服務(wù)完畢而離去，而另一顧客進(jìn)入系統(tǒng)，或者正在接受服務(wù)的完畢而離去，而另一顧客進(jìn)入系統(tǒng)，或者正在接受服務(wù)的顧客將繼續(xù)要求服務(wù)，且無人進(jìn)入系統(tǒng)的概率，顧客將繼續(xù)要求服務(wù)，且無人進(jìn)入系統(tǒng)的概率， p1111 = pq + (1-p)(1-q). p1212 正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且另一個顧客進(jìn)正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且另一個顧客進(jìn)入系統(tǒng)的概率入系統(tǒng)的概率, p1212 = (1-p)q

41、. p1313正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且在正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且在t 間隔內(nèi)有間隔內(nèi)有兩個顧客進(jìn)入系統(tǒng)的概率兩個顧客進(jìn)入系統(tǒng)的概率 ，由假設(shè)，后者實際上是不可能，由假設(shè)，后者實際上是不可能發(fā)生的，發(fā)生的， p1313 =0.類似地，有類似地，有p2121 = p3232 = p(1-q), p2222 = pq + (1-p)(1-q) , p2323 = q(1-p), pij = 0, (|i-j |2).p3333 : : 或者一人將離去且另一人將進(jìn)入系統(tǒng)，或者無人離開或者一人將離去且另一人將進(jìn)入系統(tǒng)，或者無人離開的概率，的概率， p3333 = pq + (1-p)

42、.于是該馬氏鏈的一步轉(zhuǎn)移概率矩陣為于是該馬氏鏈的一步轉(zhuǎn)移概率矩陣為 1-qq00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p)(1-q)q(1-p)00p(1-q)pq + (1-p) 例例2 試說明試說明 1例例3中的鏈?zhǔn)潜闅v的，并求其極限分布中的鏈?zhǔn)潜闅v的，并求其極限分布. 解解 依照例依照例1， 由由 1例例3中的一步轉(zhuǎn)移概率矩陣中的一步轉(zhuǎn)移概率矩陣P，可算得，可算得P(3)= P3無零元無零元. 根據(jù)定理，鏈?zhǔn)潜闅v的，根據(jù)定理，鏈?zhǔn)潜闅v的， 而極限分布而極限分布 滿足下列方程組滿足下列方程組 解之解之 ，得唯一解，得唯一解),(3210p p

43、p pp pp pp p . 1,)1()1(,)1()1)(1()1(,)1()1)(1(,)1()1(321032332122101100p pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pppqpqqpqppqpqqpqppqqqpqCqqpCqp/)1 ( ,/)1 (221330 p pp pCpqCpqpq/)1( ,/ )1)(1(23322 p pp p 其中其中 假若在此例中，設(shè)假若在此例中，設(shè)p = q = 1/2,則可算得則可算得 0 0 = 1/7 0.14, 1 1 = 2 2 = 3 3 = 2/7 0.29, 即此時極限分布為即此時極限分布為 =(1/7，2/7，2/7，2/7). 這就這就是說，經(jīng)過相當(dāng)長的時間后，系統(tǒng)中無人的情形約占是說，經(jīng)過相當(dāng)長的時間后，系統(tǒng)中無人的情形約占14%的時間，的時間，而系統(tǒng)中有一人，二人，三人的情形各占而系統(tǒng)中有一人，二人，三人的情形各占29%的時間的時間. 例例3 設(shè)一馬氏鏈的一步轉(zhuǎn)移概率矩陣為設(shè)一馬氏鏈的一步轉(zhuǎn)移概率矩陣為 試討論它的遍歷性試討論它的遍歷性 解解 先算得先算得2322233)1 ()1)(1 ()1 ()1 (pqpqpqqqpqpC 02/ 102/ 12/ 102/ 1002/ 102/ 12/ 102/ 10P 2/ 1