數(shù)理統(tǒng)計(jì)與隨機(jī)過程馬爾科夫鏈.ppt

《數(shù)理統(tǒng)計(jì)與隨機(jī)過程馬爾科夫鏈.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)理統(tǒng)計(jì)與隨機(jī)過程馬爾科夫鏈.ppt（34頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、,,數(shù)理統(tǒng)計(jì)與隨機(jī)過程 第十一章,主講教師：程維虎教授,北京工業(yè)大學(xué)應(yīng)用數(shù)理學(xué)院,第十一章 馬爾可夫鏈,本章首先從隨機(jī)過程在不同時刻狀態(tài)之間的特殊的統(tǒng)計(jì)聯(lián)系，引入馬爾可夫(Markoff)過程的概念。然后，對馬爾可夫鏈(狀態(tài)、時間都是離散的馬爾可夫過程)的兩個基本問題，即轉(zhuǎn)移概率的確定以及遍歷性問題作不同程度的研究和介紹。 馬爾可夫過程的理論在近代物理、生物學(xué)、管理科學(xué)、經(jīng)濟(jì)、信息處理以及數(shù)字計(jì)算方法等方面都有重要應(yīng)用。,11.1 馬爾可夫過程及其概率分布,在物理學(xué)中，很多確定性現(xiàn)象遵從如下演變原則：由時刻t0系統(tǒng)或過程所處的狀態(tài)，可以決定系統(tǒng)或過程在時刻t t0所處的狀態(tài)，而無需借助于t0

2、以前系統(tǒng)或過程所處狀態(tài)的歷史資料。如微分方程問題所描繪的物理過程就屬于這類確定性現(xiàn)象。把上述原則延伸到隨機(jī)現(xiàn)象，即當(dāng)一物理系統(tǒng)或過程遵循的是某種統(tǒng)計(jì)規(guī)律時，可仿照上面的原則，引入以下的馬爾可夫性或無后效性：過程(或系統(tǒng))在時刻t0所處的狀態(tài)為已知的條件下，過程在時刻tt0所處狀態(tài)的條件分布與過程在t0之前所處的狀態(tài)無關(guān)。通俗地說，就是在已經(jīng)知道過程“現(xiàn)在”的條件下，其“將來”不依賴于“過去”。,現(xiàn)用分布函數(shù)來表述馬爾可夫性.設(shè)隨機(jī)過程X(t), t T的狀態(tài)空間為I。如果對時間t的任意n個數(shù)值t1

3、X(tn)的條件分布函數(shù)恰等于在條件X(tn-1)=xn-1下X(tn)的條件分布函數(shù),則稱過程X(t), t T具有馬爾可夫性或無后效性，并稱此過程為馬爾可夫過程。,(1.1),例1 設(shè)X(t), t 0是獨(dú)立增量過程，且X(0)=0，證明X(t), t 0是一個馬爾可夫過程。 證 由(1.1)式知，只要證明在已知X(tn-1)=xn-1的條件下X(tn)與X(tj),j=1,2, ,n-2相互獨(dú)立即可?，F(xiàn)由獨(dú)立增量過程的定義知道，當(dāng)0

4、n-1,即有 X(tj)與X(tn)-X(tn-1) 相互獨(dú)立。 再由第三章4定理知，此時X(tn)與X(tj)， j=1,2, ,n-2相互獨(dú)立。這表明X(t)具有后無效性,即X(t), t 0是一個馬爾可夫過程。 由上例知，泊松過程是時間連續(xù)狀態(tài)離散的馬氏過程；維納過程是時間狀態(tài)都連續(xù)的馬氏過程。,時間和狀態(tài)都是離散的馬爾可夫過程稱為馬爾可夫鏈，簡稱馬氏鏈，記為Xn=X(n), n =0,1,2, ，它可以看作在時間集T1=0,1,2, 上對離散狀態(tài)的馬氏過程相繼觀察的結(jié)果.我們約定記鏈的狀態(tài)空間I=a1,a2, ,ai R。在鏈的情形，馬爾可

5、夫性通常用條件分布律來表示，即對任意的正整數(shù)n,r和0t1

6、Pij(m, m+n)只與i,j及時間間距n有關(guān)時，把它記為Pij(n)，即 Pij(m, m+n)= Pij(n) 并稱此轉(zhuǎn)移概率具有平穩(wěn)性。同時也稱此鏈?zhǔn)驱R次的或時齊的。以下我們限于討論齊次馬氏鏈。,在馬氏鏈為齊次的情形下，由(1.3)式定義的轉(zhuǎn)移概率 Pij(n)= PXm+n= ajXm = ai 稱為馬氏鏈的n步轉(zhuǎn)移概率， P (n)= (Pij(n))為n步轉(zhuǎn)移概率矩陣。在以下的討論中特別重要的是一步轉(zhuǎn)移概率 Pij=Pij(1)=PXm+1= ajXm = ai 或由它們組成的一步轉(zhuǎn)移概率矩陣,在上述矩陣的左側(cè)和上邊標(biāo)上狀態(tài)a1, a2, 是為了顯示Pij是由狀態(tài)ai

7、經(jīng)一步轉(zhuǎn)移到狀態(tài)aj的概率。,例2 （0-1傳輸系統(tǒng)）在如下圖只傳傳輸數(shù)字0和1的串聯(lián)系統(tǒng)中，設(shè)每一級的傳真率（輸出與輸入數(shù)字相同的概率稱為系統(tǒng)的傳真率，相反情形稱為誤碼率）為p，誤碼率為q=1-p，并設(shè)一個單位時間傳輸一級， X0是第一級的輸入，Xn是第n級的輸出(n1)，那么Xn, n =0,1,2, 是一隨機(jī)過程，狀態(tài)空間I=0,1，而且當(dāng)Xn=i , iI為已知時, Xn+1所處的狀態(tài)的概率分布只與Xn=i 有關(guān)，而與時刻n以前所處的狀態(tài)無關(guān)，所以它是一個馬氏鏈，而且還是齊次的。它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率分別為,和,例2 一維隨機(jī)游動 設(shè)一醉漢Q在如下圖所示直線的點(diǎn)集I=1,2,3

8、,4,5上作隨機(jī)游動，且僅在1秒、2秒等時刻發(fā)生游動。游動的概率規(guī)則是：如果Q現(xiàn)在位于點(diǎn)i(1

9、是一馬氏鏈，而且還是齊次的，它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為,1 2 3 4 5,1 2 3 4 5,,和,P=,如果把1這一點(diǎn)改為吸收壁，即是說Q一旦到達(dá)1這一點(diǎn)，則就永遠(yuǎn)留在點(diǎn)1上，此時，相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把P中的第一橫行改為(1,0,0,0,0)?？傊淖冇蝿拥母怕室?guī)則,就可得到不同方式的隨機(jī)游動和相應(yīng)的馬式鏈。 隨機(jī)游動的思想在數(shù)值計(jì)算方法方面有重要應(yīng)用。,例4 排隊(duì)模型 設(shè)服務(wù)系統(tǒng)由一個服務(wù)員和只可以容納兩個人的等候室組成，見圖11-3。服務(wù)規(guī)則是：先到先服務(wù)，后來者首先需在等候室。假定一顧客到達(dá)系統(tǒng)時發(fā)現(xiàn)系統(tǒng)內(nèi)已有3個顧客(一個正在接受服務(wù)，兩個在等

10、候室排隊(duì))，則該顧客即離去。設(shè)時間間隔t內(nèi)有一個顧客進(jìn)入系統(tǒng)的概率為q，有一原來被服務(wù)的顧客離開系統(tǒng)(即服務(wù)完畢)的概率為p。又設(shè)當(dāng)t充分小時，在這時間間隔內(nèi)多于一個顧客進(jìn)入或離開系統(tǒng)實(shí)際上是不可能的。再設(shè)有無顧客來到與服務(wù)是否完畢是相互獨(dú)立?，F(xiàn)用馬氏鏈來描述這個服務(wù)系統(tǒng)。,圖11-3,設(shè)Xn=X(nt)表示時刻nt 時系統(tǒng)內(nèi)的顧客數(shù)，即系統(tǒng)的狀態(tài), Xn , n=0,1,2 是一隨機(jī)過程,狀態(tài)空間I=0,1,2,3,可知它是一個齊次馬氏鏈。下面來計(jì)算此馬氏鏈的一步轉(zhuǎn)移概率。 p00 在系統(tǒng)內(nèi)沒有顧客的條件下，經(jīng)t 后仍沒有顧客的概率(此處是條件概率，以下同) p00=1-q. p01

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

12、概率 ，由假設(shè)，后者實(shí)際上是不可能發(fā)生的，p13 =0. 類似地，有p21 = p32=p(1-q), p22 =pq+(1-p)(1-q), p23= q(1-p), pij =0(|i-j|2). p33 一人因服務(wù)完畢而離去且另一人將進(jìn)入系統(tǒng)，或者無人離開系統(tǒng)的概率， p33 = pq+(1-p),于是該馬氏鏈的一步轉(zhuǎn)移概率矩陣為,在實(shí)際問題中，一步轉(zhuǎn)移概率通?？赏ㄟ^統(tǒng)計(jì)試驗(yàn)確定，下面看一實(shí)例。,例5 計(jì)算機(jī)機(jī)房的一臺計(jì)算機(jī)經(jīng)常出故障，研究者每隔15分鐘觀察一次計(jì)算機(jī)的運(yùn)行狀態(tài)，收集了24小時的數(shù)據(jù)（共作97次觀察）。用1表示正常狀態(tài)，用0表示不正常狀態(tài)，所得的數(shù)據(jù)序列如下： 111

13、0010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111,設(shè)Xn為第n( n =1,2,97)個時段的計(jì)算機(jī)狀態(tài),可以認(rèn)為它是一個馬氏鏈,狀態(tài)空間I=0，1.96次狀態(tài)轉(zhuǎn)移的情況是: 0 0,8次； 0 1,18次； 1 0,18次； 1 1,52次. 因此，一步轉(zhuǎn)移概率可用頻率近似地表示為,例6（續(xù)例5） 若計(jì)算機(jī)在前一段(15分鐘)的狀態(tài)為0，問在此條件下從此時段起此計(jì)算機(jī)能連續(xù)正常工作3刻鐘(3個時段)的概率為多少？ 解 由題意，某一時段

14、的狀態(tài)為0就是初始狀態(tài)為0，即 X 0= 0。由乘法公式、馬氏性和齊次性得，所求條件概率為,接著，我們來研究齊次馬氏鏈的有限維分布。首先，記,稱它為馬氏鏈的初始分布。再看馬氏鏈在任意時刻n T1的一維分布：,顯然，應(yīng)有 由全概率公式,即,(1.6),(1.7),一維分布(1.6)也可用行向量表示成 p(n)=( p1(n), p2(n), pj(n),) 這樣，利用矩陣乘法(I是可列無限集時，仍用有限階矩陣乘法的規(guī)則確定矩陣之積的元)，(1.7)式可寫成 p(n) = p(0)P(n) 此式表明，馬氏鏈在任一時刻nT1時的一維分布由初始分布

15、 p(0)和n 步轉(zhuǎn)移概率矩陣所確定。,(1.6) ,(1.7) ,又,對于任意n個時刻t1

16、)就是著名的切普曼-柯莫哥洛夫(Chapman-Kolmogorov)方程，簡稱C-K方程。,C-K方程基于下述事實(shí)，即“從時刻s所處的狀態(tài)ai，即X(s)=ai出發(fā)，經(jīng)時段u+v轉(zhuǎn)移到狀態(tài) aj ,即X(s+u+v）=aj”這一事件可分解成“從X(s)=ai 出發(fā)，先經(jīng)時段u轉(zhuǎn)移到中間狀態(tài)ak(k,=1,2)，再從ak經(jīng)時段v轉(zhuǎn)移到狀態(tài) aj”這樣一些事件和事件(見圖11-4)。,圖 11-4,方程(2.1)的證明如下：先固定ak I 和sT1，由條件概率定義和乘法定理，有,(2.2),又由于事件組“X(s+u)= ak”,k=1,2,構(gòu)成一劃分，故有,將(2.2)式代入上式，即得所要證明的

17、C-K方程。 C-K方程也可寫成矩陣形式： P(u+v)=P(u)P (v) (2.1) 利用C-K方程我們?nèi)菀状_定n步轉(zhuǎn)移概率。事實(shí)上，在(2.1) 式中令u=1,v=n-1，得遞推關(guān)系： P(n)= P(1) P(n-1) =PP(n-1), 從而可得 P(n)= Pn. (2.3) 就是說，對齊次馬氏鏈而言，n步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的n次方。 進(jìn)而可知，齊次馬氏鏈的有限維分布可由初始與一步轉(zhuǎn)移概率完全確定。,例1 設(shè)Xn,n0是具有三個狀態(tài)0,1,2的齊次馬氏鏈，一步轉(zhuǎn)移概率矩陣為,初始分布pi(0

18、)=PX0=i=1/3, i=0,1,2. 試求: (i) PX0=0, X2=1; (ii) PX2=1,解 先求出二步轉(zhuǎn)移概率矩陣,于是 (i),(ii) 由(1.7)式，,例2 在1例2中,(i)設(shè)p=0.9 , 求系統(tǒng)二級傳輸后的傳真率與三級傳輸后的誤碼率；(ii)設(shè)初始分布P1 (0)= PX0 =1= ， P0 (0) =P X0 = 0=1- ，又已知系統(tǒng)經(jīng)n級傳輸后輸出為1，問原發(fā)字符也是1的概率是多少？ 解 先求出n步轉(zhuǎn)移概率矩陣P(n)= Pn。由于,有相異的特征值1=1,2=p-q,由線形代數(shù)知識，可將P表示成對角陣 的相似矩陣。具體做法是：求出1, 2對應(yīng)的特征相量

19、,(q=1-p),(q=1-p),令,則,(2.4),(i)由(2.4)式可知，當(dāng)p=0.9時，系統(tǒng)經(jīng)二級傳輸后的傳真率與三級傳輸?shù)恼`碼率分別為,(ii)根據(jù)貝葉斯公式，當(dāng)已知系統(tǒng)經(jīng)n級傳輸后輸出為1，原發(fā)字符也是1的概率為,對于只有兩個狀態(tài)的馬氏鏈，一步轉(zhuǎn)移概率矩陣一般可表示為：,利用類似于例2的方法，可得n步轉(zhuǎn)移概率矩陣為,11.3 遍歷性,對于一般的兩個狀態(tài)的馬氏鏈，由(2.5)式可知,當(dāng)0

20、0+ 1=1，所以( 0, 1)= 構(gòu)成一分布律，稱它為鏈的極限分布。另外，如若我們能用其他簡便的方法直接由一步轉(zhuǎn)移概率求得極限分布 ，則反過來，當(dāng)n1 時就可得到n步轉(zhuǎn)移概率的近似值： pij(n) j,一般，設(shè)齊次馬氏鏈的狀態(tài)空間為 I，若對于所有ai,ajI，轉(zhuǎn)移概率Pij (n)存在極限,或,則稱此鏈具有遍歷性，又若 ，則同時稱 為鏈的極限分布。 齊次馬氏鏈在什么條件下才具有遍歷性？如何求出它的極限分布？這問題在理論上已經(jīng)完滿解決,下面僅就只有有限個狀態(tài)的鏈,即有限鏈的遍歷性給出一個充分條件。,定理 設(shè)齊次馬氏鏈Xn ,n 1的狀態(tài)空間為I= a1 ,a2 ,,

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

22、的，而唯一解可用歸一條件 確定。,在定理的條件下，馬氏鏈的極限分布又是平穩(wěn)分布。意即，若用作為鏈的初始分布，即p(0)= ,則鏈在任一時刻nT1的分布p(n)永遠(yuǎn)與一致。事實(shí)上，有 p(n)= p(0) p(n)= pn = pn-1 = = p = ,例1 試說明1例2中，帶有兩個放射壁的隨機(jī)游動是遍歷的，并求其極限分布(平穩(wěn)分布)。 解 為簡便計(jì)，以符號“”代表轉(zhuǎn)移概率矩陣的正元素，于是，由1例2中的一步轉(zhuǎn)移概率矩陣 P，得,即P(4)無零元。由定理，鏈?zhǔn)潜闅v的。再根據(jù)(3.2)和(3.3)式,寫出極限分布 = ( 1, 2,, 5)滿足的方程組 先由前四個方程，解得：3 1

23、= 2= 3= 4=3 5 ，將它們代入歸一條件，即最后一個方程，解之，得唯一解： 1= 5=1/11, 2= 3= 4=3/11 所以極限分布為 =(1/11,3/11,3/11,3/11,1/11)。這個分布表明：經(jīng)過長時間游動之后，醉漢Q位于i點(diǎn)(1

24、p = q = 1/2，則可算得 0 = 1/7 0.14, 1= 2= 3=2/7 0.29,即此時極限分布為 =(1/7,2/7,2/7,2/7).這就是說，經(jīng)過相當(dāng)長的時間后，系統(tǒng)中無人的情形約占14%的時間，而系統(tǒng)中有一人、二人、三人的情形各占29%的時間。,例3 設(shè)一馬氏鏈的一步轉(zhuǎn)移概率矩陣為 試討論它的遍歷性。,解 先算得,進(jìn)一步可驗(yàn)證：當(dāng)n為奇數(shù)時， P(n)=P(1)=P；n為偶數(shù)時，P(n)=P(2) 。這表明對任一固定的 j (=1,2,3,4)，極限 都不存在。按定義，此鏈不具遍歷性。,馬氏過程的內(nèi)容除了討論最簡情形馬氏鏈之外，還研究狀態(tài)離散、時間連續(xù)的馬氏過程和狀態(tài)、時間都連續(xù)的馬氏過程，它們都有比較完善的理論，而且討論的主題也都是從各自場合的C-K方程出發(fā)，研究轉(zhuǎn)移概率的確定方法和性質(zhì)。本書除前面介紹的泊松過程和維納過程這兩個具體的馬氏過程模型外不再作一般的介紹。,