《馬爾可夫鏈及其概率分布課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《馬爾可夫鏈及其概率分布課件.ppt（48頁珍藏版）》請在匯文網(wǎng)上搜索。

1、馬爾可夫鏈及其概率分布,引言 直觀上，過程（或系統(tǒng)）在時刻t0所處的狀態(tài)為已知的條件下,過程在時刻tt0所處狀態(tài)的條件分布與過程在時刻t0之前所處的狀態(tài)無關(guān)。 用分布函數(shù)表達此性質(zhì)，設(shè)隨機過程X(t),tT，狀態(tài)空間為，若對于t 的任意n個值t1t2tn,n3,有,則稱過程X(t),tT具有馬爾可夫性，或稱 X(t),tT為馬爾可夫過程。,一、馬爾可夫鏈及其概率分布的定義 狀態(tài)和時間參數(shù)都是離散的馬爾可夫過程稱為馬爾可夫鏈，或馬氏鏈。 記為Xn=X(n),n=0,1，2，,記鏈的狀態(tài)空間為a1，a2，aiR .在鏈的情況，馬爾可夫性通常用分布率表示。 1.馬氏鏈的定義,其中a., 稱Xn,n=

2、0,1，2，為馬氏鏈。,稱為馬氏鏈在時刻m系統(tǒng)處于狀態(tài)ai的條件下，在時刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率。,定義1若對于任意的正整數(shù)n，r和任意的,則稱Xn,n0為馬氏鏈。,定義2設(shè)Xn,n0,其狀態(tài)空間為,若對于任意的正整數(shù)n和任意的,例.記從數(shù)1,2, ,N中任取一數(shù)為X0，當n1時，記從數(shù)1,2, ,Xn-1中任取一數(shù)為Xn,證明Xn,n=0，1，2,是一個馬氏鏈。證：Xn,n=0，1，2,的狀態(tài)空間=i,1iN,可見,Xn,n=0，1，2,是一個馬氏鏈。,2轉(zhuǎn)移概率的性質(zhì) (1) Pij0；,事實上，因為鏈在m時刻從狀態(tài)ai出發(fā)，到m+n時刻必然轉(zhuǎn)移到a1，a2，狀態(tài)中的一個，從而,2

3、.,定義若對任意的正整數(shù)m,n及任意的ai，aj，有,即馬氏鏈Xn,n0的轉(zhuǎn)移概率Pij(n,n+1)與n無關(guān)，則稱轉(zhuǎn)移概率具有平穩(wěn)性，這時，馬爾可夫鏈稱為是齊次的。,稱為馬氏鏈的一步轉(zhuǎn)移概率；,齊次馬爾可夫鏈及一步轉(zhuǎn)移概率,稱為馬氏鏈的一步轉(zhuǎn)移概率矩陣；其中列為Xm的狀態(tài)，行為Xm+1的狀態(tài)。,例（01傳輸系統(tǒng)）在一個n級數(shù)字傳輸系統(tǒng)中，設(shè)每一級的傳真率為p，誤碼率為q=1-p，并設(shè)一個單位時間傳輸一級，X0是第一級的輸入, Xn是第n級的輸出（n1）,那么Xn, n=0，1，2,是一隨機過程，狀態(tài)空間=0,1.,0 0 1 1,當Xn=i, i為已知時，Xn+1所處的狀態(tài)的概率分布只與Xn

4、=i 有關(guān)，而與時刻n以前所處的狀態(tài)無關(guān)，所以它是一個馬氏鏈。,定義3 稱條件概率 為馬爾可夫鏈在時刻m處于狀態(tài)ai的條件下，在時刻m+n步轉(zhuǎn)移到狀態(tài)aj的n步轉(zhuǎn)移概率，簡稱為轉(zhuǎn)移概率。,且一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為,且是齊次馬氏鏈.,例(一維隨機游動)設(shè)一醉漢Q（或看作一隨機游動的質(zhì)點），在如圖所示直線的點集I1，2，3，4，5上作游動，僅僅在1秒、2秒等時刻發(fā)生游動。游動的概率規(guī)則是：如果Q現(xiàn)在位于點i (1i 5)，則下一時刻各以1/3的概率向左或向右移動一格，或以1/3的概率留在原處；如果Q現(xiàn)在位于1（或5）這點上，則下一時刻就以概率1移動到2（或4）點上。1和5這兩點稱為反

5、射壁。上面這種游動稱為帶有兩個反射壁的隨機游動。,若以Xn表示時刻n時Q的位置，不同的位置就是Xn的不同狀態(tài)，那么Xn,n=0，1,2,是一隨機過程，狀態(tài)空間就是I，而且當Xn=i,iI為已知時,Xn+1所處的狀態(tài)的概率分布只與Xn=i有關(guān)，而與Q在時刻n以前如何到達i是完全無關(guān)的，所以Xn,n=0，1,2, 是一馬氏鏈，且是齊次的。它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為,如果把1這一點改為吸收壁，即Q一旦到達1，就永遠留在點1上。此時，相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把P中第1橫行改為（1，0，0，0，0）?？傊?，改變游動的概率規(guī)則，就可得到不同方式的游動和相應(yīng)的馬氏鏈。,例 設(shè)Xn,n=0，1，

6、2,是獨立同分布的隨機變量列,記Xn可能取值的全體為I=i,i 1,則Xn為馬氏鏈，并求其一步轉(zhuǎn)移概率。解 對任意的n及,所以Xn為馬氏鏈。,由于Xn, n=0，1，2,獨立同分布，因而,所以Xn為齊次馬氏鏈。其一步轉(zhuǎn)移概率P:,/例3 排隊模型設(shè)服務(wù)系統(tǒng)由一個服務(wù)員和只可以容納兩個人的等候室組成，見圖73。服務(wù)規(guī)則是：先到先服務(wù)，后來者需在等候室依次排隊。假定一個需要服務(wù)的顧客到達系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有3個顧客（一個正在接受服務(wù)，兩個在等候室排隊）則該顧客即離去。設(shè)時間間隔t內(nèi)將有一個顧客進入系統(tǒng)的概率為q，有一原來被服務(wù)的顧客離開系統(tǒng)（即服務(wù)完畢）的概率為p。又設(shè)當t充分小時，在這時間間隔內(nèi)

7、多于一個顧客進入或離開系統(tǒng)實際上是不可能的。再設(shè)有無顧客來到與服務(wù)是否完畢是相互獨立的?，F(xiàn)用馬氏鏈來描述這個服務(wù)系統(tǒng)。,設(shè)P表示一步轉(zhuǎn)移概率Pij所組成的矩陣，則 稱P為一步轉(zhuǎn)移概率矩陣，它具有如下性質(zhì) （1） （2） （2）式中對j求和是對狀態(tài)空間I的所有可能的狀態(tài)進行的。此性質(zhì)說明，一步轉(zhuǎn)移概率矩陣中任一行元素之和為1。,表示時刻 時，系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀態(tài)。xn, n=0，1，2,是一隨機過程，狀態(tài)空間I0，1，2，3，而且仿照例1、例2的分析，可知它是一個齊次馬氏鏈。下面來計算此馬氏鏈的一步轉(zhuǎn)移概率。 p00在系統(tǒng)內(nèi)沒有顧客的條件下，以 后仍沒有顧客的概率（此處是條件概率，以下同

8、），p00=1-q. p01系統(tǒng)內(nèi)沒有顧客的條件下, 經(jīng) 后有一顧客進入系統(tǒng)的概率, p01=q.,10系統(tǒng)內(nèi)恰有一顧客正在接受服務(wù)的條件下，經(jīng) 后系統(tǒng)內(nèi)無人的概率，它等于在 間隔內(nèi)顧客因服務(wù)完畢而離去，且無人進入系統(tǒng)的概率，p10=p(1-q).p11系統(tǒng)內(nèi)恰有一顧客的條件下，在 間隔內(nèi)，他因服務(wù)完畢而離去，而另一顧客進入系統(tǒng)，或者正在接受服務(wù)的顧客將繼續(xù)要求服務(wù)，且無人進入系統(tǒng)的概率，這p11pq(1-p) (1-q). p12正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且另一個顧客進入系統(tǒng)的概率，p12=q(1-p).,13正在接受服務(wù)的顧客繼續(xù)要求服務(wù)，且在 間隔內(nèi)有兩個顧客進入系統(tǒng)的概率。由假設(shè)

9、，后者實際上是不可能發(fā)生的，p13=0. 類似地，有p21= p32 = p(1-q), p22 = pq+(1-p) (1-q), p23=q(1-p), pij= 0( | i-j |2 ).p33或者一人將離去且另一人將進入系統(tǒng)，或者無人離開系統(tǒng)的概率，p33= pq+(1-p).,于是該馬氏鏈的一步轉(zhuǎn)移概率矩陣為,例4 某計算機機房的一臺計算機經(jīng)常出故障，研究者每隔15分鐘觀察一次計算機的運行狀態(tài)，收集了24小時的數(shù)據(jù)（共作97次觀察），用1表示正常狀態(tài)，用0表示不正常狀態(tài)，所得的數(shù)據(jù)序列如下：1110010011111110011110111111001111111110001101

10、101111011011010111101110111101111110011011111100111設(shè)Xn為第n (n=1,2,97)個時段的計算機狀態(tài)，可以認為它是一個齊次馬氏鏈，狀態(tài)空間I=0,1, 96次狀態(tài)轉(zhuǎn)移的情況是： 00，8次，01，18次； 10，18次，11，52次。,因此，一步轉(zhuǎn)移概率可用頻率近似地表示為,/為了進一步討論馬爾可夫鏈的統(tǒng)計性質(zhì)，我們需討論多步轉(zhuǎn)移概率和有限維分布，為此我們先給出幾個概念，n步轉(zhuǎn)移概率，初始概率分布，絕對 概率分布。/,3.多步轉(zhuǎn)移概率及C-K方程 若Xn為齊次馬氏鏈，則對任意非負整數(shù)m，任意正整數(shù)n,及,，,因此，馬氏鏈的齊次性可寫為,定義

11、 稱條件概率,為馬氏鏈Xn,n0的n步轉(zhuǎn)移概率，并稱由Pij(n)組成的矩陣,為馬爾可夫鏈的n步轉(zhuǎn)移概率矩陣。,定義 設(shè)Xn,n=0,1,為馬爾可夫鏈，稱X0的分布 pj(0)=PX0=j, j為Xn,n=0,1,的初始分布.,稱Xn的分布pj(n)=PXn=j, j 為Xn,n=0,1,的絕對分布，初始分布和任一時刻 n的絕對分布可用向量表示 q(0)=(p1(0),p2(0), ) q(n)=(p1(n),p2(n), ),定理 設(shè)Xn，n=0,1,為馬氏鏈，則對于任意的正整數(shù)k,m，有,此方程稱為Chapman-kolmogorov(切普曼柯爾莫哥洛夫)方程,簡稱C-K方程.,證：,既:

12、“從Xn=ai出發(fā)，經(jīng)時刻m轉(zhuǎn)移到中間狀態(tài)ar,再從ar經(jīng)k時段轉(zhuǎn)移到aj狀態(tài)”這樣一些事件的和事件。,如果把轉(zhuǎn)移概率寫成矩陣的形式，那么CK方程具有以下簡單的形式 P(m+k)=P(m)P(k) m, k0 特別地，P(n)=Pn, n步轉(zhuǎn)移概率由一步轉(zhuǎn)移概率完全決定。,例 求帶有兩個反射壁的一維隨機游動的兩步轉(zhuǎn)移概率矩陣。,例 在n級0-1傳輸系統(tǒng)中，設(shè)p=0.9，求系統(tǒng)二級傳輸后的傳真率與三級傳輸后的誤碼率.解 先求出n步轉(zhuǎn)移概率矩陣P(n)=Pn。,有相異特征值1=1，2=p-q ,由線性代數(shù),知識，可將矩陣P表示為對角陣,的相似矩陣。,具體做法是：求出 1 ,2對應(yīng)的特征向量,則PH

13、H-1。于是，容易算得,由上式可知，當p=0.9時，系統(tǒng)經(jīng)二級傳輸后的傳真率 與三級傳輸后的誤碼率分別為,對于只有兩個狀態(tài)的馬氏鏈，一步轉(zhuǎn)移概率矩陣一 般可表示為：,利用類似的方法，可得n步轉(zhuǎn)移概率矩陣為,n=1,2,.,四、有限維分布及遍歷性 1有限維分布 設(shè)馬氏鏈Xn,n0,狀態(tài)空間，n步轉(zhuǎn)移概率矩陣P(n).,(1)一維分布,設(shè)鏈的,一維分布可用行向量表示p(n)=(p1(n),p2(n),pj(n),), 利用矩陣的乘法：p(n)= p(0)P(n) 說明馬氏鏈在任一時刻n的一維分布由初始分布與n步 轉(zhuǎn)移概率矩陣確定。,(2)n維分布 對任意n個時刻 0t1t2tn及ai1,ai2,a

14、in ,馬氏鏈的n維分布,所以，馬氏鏈的有限維分布完全由初始分布和轉(zhuǎn)移概率確定。,例: 設(shè)Xn, n0是具有三個狀態(tài)0，1，2的齊次馬氏鏈，一步轉(zhuǎn)移概率矩陣為,初始分布pi(0)=PX0=i=1/3, i=0,1,2.試求(1) PX0=0,X2=1；(2) PX2=1. 解: 先求出二步轉(zhuǎn)移概率矩陣,于是(1) PX0=0,X2=1=PX0=0PX2=1|X0=0 = p0(0)p01(2) =,(2) PX2=1= p0(0)p01(2)+p1(0) p11(2)+ p2(0) p21(2),例2: 在例中進一步求(2)設(shè)初始分布p1(0)=PX0=1=,p0(0)=PX0=0=1-，又已

15、知系統(tǒng)經(jīng)n級傳輸后輸出為1，問原發(fā)字符也是1的概率是多少？ 解: （2）根據(jù)貝葉斯公式，當已知系統(tǒng)經(jīng)n級傳輸后輸出為1，原發(fā)字符也是1的概率為,五、遍歷性 對于一般的兩個狀態(tài)的馬氏鏈，有,當0a，b1時，Pij(n)有極限,當n1時就可得到n步轉(zhuǎn)移概率的近似值：,1.定義 設(shè)馬爾可夫鏈的狀態(tài)空間為，如果對于所有的ai , aj, 轉(zhuǎn)移概率pij(n) ,當n時，存在不依賴于i的極限,則稱此鏈具有遍歷性，又若 ,稱 =(1,2,)為鏈的極限分布。,2.遍歷性的定理 定理 設(shè)齊次馬氏鏈Xn,n0的狀態(tài)空間為a1, a2,an，P是它的一步轉(zhuǎn)移概率矩陣，如果存在正整數(shù)m，使對任意的ai ,aj，都有

16、 Pij(m)0, i , j =1,2,N 則此鏈具有遍歷性，且有極限分布=(1,2, N)，它是方程組,的滿足條件j0, 的唯一解。,在定理的條件下，馬氏鏈的極限分布又是平穩(wěn)分布，意即若用作為鏈的初始分布，即p(0)=，則鏈在任一時刻n的分布p(n)永遠與一致.因為,例1: 試說明例2中，帶有兩個反射壁的隨機游動是遍歷的，并求其極限分布。 解: 為簡便，以符號“”代表轉(zhuǎn)移概率矩陣的正元素。于是，由例2中的一步轉(zhuǎn)移概率矩陣P，得,即P(4)無零元。由定理，鏈是遍歷的。再根據(jù)定理，極限分布滿足的方程組,先由前四個方程，解得 31=2=3=4=35.將它們代入歸一條件，即最后一個方程，解之得唯一解： 1=5=1/11, 2=3=4=3/11,所以極限分布為 =(1/11, 3/11, 3/11, 3/11, 1/11). 例2 設(shè)一馬氏鏈的一步轉(zhuǎn)移概率矩陣為,試討論它的遍歷性。,解: 先算得,進一步可驗證：當n為奇數(shù)時，P(n)=P(1)=P； n為偶數(shù)時，P(n)P(2)。 這表明對任一固定的 j(=1,2,3,4)，極限 都不存在。按定義，此鏈不具遍歷性。,