工程數(shù)學(xué)第24講

1、1,工程數(shù)學(xué)第24講,本文件可從網(wǎng)址http://math.vip.sina.com上下載(單擊ppt講義后選擇'工程數(shù)學(xué)'子目錄),2,第十一章 馬爾可夫鏈,§1 馬爾可夫過(guò)程及其概率分布,3,在物理學(xué)中, 很多確定性現(xiàn)象遵從如下演變?cè)瓌t: 由時(shí)刻t0系統(tǒng)或過(guò)程所處的狀態(tài), 可以決定系統(tǒng)或過(guò)程在時(shí)刻t>t0所處的狀態(tài), 而無(wú)需借助于t0以前系統(tǒng)或過(guò)程所處狀態(tài)的歷史資料. 如微分方程初值問(wèn)題所描

2、繪的物理過(guò)程. 將這樣的原則延伸到隨機(jī)現(xiàn)象, 引入馬爾可夫性或無(wú)后效性: 過(guò)程(或系統(tǒng))在時(shí)刻t0所處的狀態(tài)為已知條件下, 過(guò)程在時(shí)刻t>t0所處狀態(tài)的條件分布與過(guò)程在時(shí)刻t0之前的狀態(tài)無(wú)關(guān). 即已經(jīng)知道過(guò)程"現(xiàn)在"的條件下, 其"將來(lái)"不依賴于"過(guò)去".,4,設(shè)隨機(jī)過(guò)程{X(t), t?T}的狀態(tài)空間為I. 如果對(duì)任意n個(gè)時(shí)間值t1<t2<...<tn

3、, n?3, ti?T, 在條件X(ti)=xi,xi?I, i=1,2,...,n-1下, P{X(tn)?xn|x(t1)=x1, X(t2)=x2,...,X(tn-1)=xn-1} =P{X(tn)?xn|X(tn-1)=xn-1}, xn?R, (1.1)或?qū)懗?則稱(chēng)過(guò)程{X(t), t?T}具有馬爾可夫性或無(wú)后效性, 并稱(chēng)此過(guò)程為馬爾可夫過(guò)程.,5,例1 設(shè){X(t),t?0}是獨(dú)立增量過(guò)程, 且X(0)=0

4、, 證明{X(t),t?0}是一個(gè)馬爾可夫過(guò)程.證 由(1.1)式知, 只要證明在已知X(tn-1)=xn-1的條件下X(tn)與X(tj), j=1,2,...,n-2相互獨(dú)立即可. 而當(dāng)0<tj<tn-1<tn, j=1,2,...,n-2時(shí), 增量X(tj)-X(0) 與 X(tn)-X(tn-1)相互獨(dú)立. 根據(jù)條件X(0)=0和X(tn-1)=xn-1, 知X(tj) 與 X(tn

5、)-xn-1相互獨(dú)立. 此時(shí)X(tn)與X(tj), j=1,2,...,n-2相互獨(dú)立. 這表明X(t)具有無(wú)后效性, 即{X(t),t?0}是一個(gè)馬爾可夫過(guò)程.,6,由此可知, 泊松過(guò)程是時(shí)間連續(xù)狀態(tài)離散的馬氏過(guò)程, 維納過(guò)程是時(shí)間狀態(tài)都連續(xù)的馬氏過(guò)程.時(shí)間和狀態(tài)都是離散的馬爾可夫過(guò)程稱(chēng)為馬爾可夫鏈, 簡(jiǎn)稱(chēng)馬氏鏈, 記為{Xn=X(n), n=0, 1, 2,...}, 它可以看作在時(shí)間集T1={0,1,2,...}上對(duì)離散狀態(tài)

6、的馬氏過(guò)程相繼觀察的結(jié)果. 我們約定記鏈的狀態(tài)空間I={a1,a2,...}, ai?R.,7,對(duì)鏈的情形, 對(duì)任意的正整數(shù)n,r和0?t1<t2<...< tr<m; ti, m, n+m?T1, 有,其中ai?I. 記上式右端為Pij(m,m+n), 稱(chēng) Pij(m,m+n)=P{Xm+n=aj|Xm=ai} (1.3)為馬氏鏈在時(shí)刻m處于狀態(tài)ai條件下, 在時(shí)刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率.

7、易知,8,轉(zhuǎn)移概率組成的矩陣P(m,m+n)=(Pij(m,m+n))稱(chēng)為馬氏鏈的轉(zhuǎn)移概率矩陣, 上式表明此矩陣的每一行元素之和等于1.當(dāng)轉(zhuǎn)移概率Pij(m,m+n)只與i,j及時(shí)間間距n有關(guān)時(shí), 把它記為Pij(n), 即Pij(m,m+n)=Pij(n)并稱(chēng)此轉(zhuǎn)移概率具有平穩(wěn)性. 同時(shí)也稱(chēng)此鏈?zhǔn)驱R次的或時(shí)齊的. 以下僅限于討論齊次馬氏鏈.,9,在馬氏鏈為齊次的情形下, 轉(zhuǎn)移概率Pij(n)=P{Xm+n=aj|Xm=ai

8、} (1.5)稱(chēng)為馬氏鏈的n步轉(zhuǎn)移概率, P(n)=(Pij(n))為n步轉(zhuǎn)移概率矩陣. 在以下的討論中特別重要的是一步轉(zhuǎn)移概率pij=Pij(1)=P{Xm+1=aj|Xm=ai}或由它們組成的一步轉(zhuǎn)移概率矩陣,10,在上述矩陣的左側(cè)和上邊標(biāo)上狀態(tài)a1,a2,...,是為了顯示pij是由狀態(tài)ai一步轉(zhuǎn)移到狀態(tài)aj的概率.,11,例2 如圖所示只傳輸數(shù)字0和1的系統(tǒng)串聯(lián)系統(tǒng)中, 設(shè)每一級(jí)傳真率為p, 誤碼率為q=1

9、-p, 設(shè)一個(gè)單位時(shí)間傳輸一級(jí), X0是第一級(jí)的輸入, Xn是第n級(jí)的輸出(n?1). 則{Xn, n=0,1,2,...}是一隨機(jī)過(guò)程, 狀態(tài)空間I={0,1}, 當(dāng)Xn=i, i?I為已知時(shí), Xn+1所處的狀態(tài)的概率分布只與Xn=i有關(guān), 而與時(shí)刻n以前的狀態(tài)無(wú)關(guān), 所以它是一個(gè)齊次的馬氏鏈.,12,它的一步轉(zhuǎn)移概率和一步轉(zhuǎn)移概率矩陣分別為,和,13,,,例3 一維隨機(jī)游動(dòng) 設(shè)一醉漢Q在如圖所示直線的點(diǎn)集I={1,2,3,4,5

10、}上作隨機(jī)游動(dòng), 且僅在1秒2秒等時(shí)刻發(fā)生游動(dòng). 游動(dòng)的概率規(guī)則是:如果Q現(xiàn)在位于點(diǎn)i(1<i<5), 則下一時(shí)刻以1/3概率向左或向右移動(dòng)一格, 或以1/3的概率留在原處; 如果Q現(xiàn)在位于1(或5)這點(diǎn)上, 則下一時(shí)刻就以概率1移動(dòng)到2(或4)上. 1和5這兩點(diǎn)稱(chēng)為反射壁. 這叫帶有兩個(gè)反射壁的隨機(jī)游動(dòng).,,,,,,,1,2,3,4,5,14,若以Xn表示時(shí)刻n時(shí)Q的位置, 不同的位置就是Xn不同的狀態(tài), 那么{Xn, n

11、=0,1,2,...}是一隨機(jī)過(guò)程, 狀態(tài)空間就是I, 而且當(dāng)Xn=i, i?I為已知時(shí), Xn+1所處的狀態(tài)的概率分別只與Xn=i有關(guān), 而與Q在時(shí)刻n以前如何到達(dá)i是完全無(wú)關(guān)的, 所以{Xn, n=0,1,2,...}是一齊次馬氏鏈, 它的一步轉(zhuǎn)移概率為,15,一步轉(zhuǎn)移概率矩陣為,如果把1這點(diǎn)改為吸收壁, 就是說(shuō)Q一旦到達(dá)1這一點(diǎn), 則就永遠(yuǎn)留在點(diǎn)1上. 此時(shí), 相應(yīng)的轉(zhuǎn)移概率矩陣只需把P中第1橫行改為(1,0,0,0,0).總之,

12、 改變游動(dòng)的概率規(guī)則, 就可得到不同方式的隨機(jī)游動(dòng)和相應(yīng)的馬氏鏈.,16,例4 排隊(duì)模型 設(shè)服務(wù)系統(tǒng)由一個(gè)服務(wù)員和只可以容納兩個(gè)人的等候室組成, 如圖所示. 服務(wù)規(guī)則是:先到先服務(wù),后來(lái)者在等候室依次排隊(duì), 假定一個(gè)需要服務(wù)的顧客到達(dá)系統(tǒng)時(shí)發(fā)現(xiàn)系統(tǒng)內(nèi)已有3個(gè)顧客(一個(gè)正在接受服務(wù),兩個(gè)在等候室排隊(duì)), 則該顧客就離去.,17,設(shè)時(shí)間間隔Dt內(nèi)有一個(gè)顧客進(jìn)入系統(tǒng)的概率為q, 有一原來(lái)被服務(wù)的顧客離開(kāi)系統(tǒng)(即服務(wù)完畢)的概率為p. 又設(shè)當(dāng)

13、Dt充分小時(shí), 在這時(shí)間間隔內(nèi)多于一個(gè)顧客進(jìn)入或離開(kāi)系統(tǒng)實(shí)際上是不可能的. 再設(shè)有無(wú)顧客來(lái)到與服務(wù)是否完畢是相互獨(dú)立的. 現(xiàn)用馬氏鏈來(lái)描述這個(gè)系統(tǒng).設(shè)Xn=X(nDt)表示時(shí)刻nDt時(shí)系統(tǒng)內(nèi)的顧客數(shù), 即系統(tǒng)的狀態(tài). {Xn, n=0,1,2,...}是一隨機(jī)過(guò)程, 狀態(tài)空間I={0,1,2,3}, 易知它是一馬氏鏈, 下面計(jì)算一步轉(zhuǎn)移概率.,18,p00: 在系統(tǒng)內(nèi)沒(méi)有顧客的條件下, 經(jīng)Dt后仍然沒(méi)有顧客的概率(此處是條件概率,以下

14、同)p00=1-q.p01:系統(tǒng)內(nèi)沒(méi)有顧客的條件下, 經(jīng)Dt后有一顧客進(jìn)入系統(tǒng)的概率, p01=q.p10:系統(tǒng)內(nèi)恰 有一顧客正在接受服務(wù)的條件下, 經(jīng)Dt后系統(tǒng)內(nèi)無(wú)人的概率. 它等于在Dt間隔內(nèi)顧客因服務(wù)完畢而離去, 且無(wú)人進(jìn)入系統(tǒng)的概率, p10=p(1-q).,19,類(lèi)似地有p11=pq+(1-p)(1-q)p12=(1-p)qp13=0p21=p32=p(1-q), p22=pq+(1-p)(1-q)p23=q(

15、1-p)pij=0(|i-j|?2)p33=pq+(1-p).,20,于是一步轉(zhuǎn)移概率矩陣為,21,在實(shí)際問(wèn)題中, 一步轉(zhuǎn)移概率通?？赏ㄟ^(guò)統(tǒng)計(jì)試驗(yàn)確定, 下面看一實(shí)例.例5 某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障, 研究者每隔15分鐘觀察一次計(jì)算機(jī)的運(yùn)行狀態(tài), 收集了24小時(shí)的數(shù)據(jù)(共作97次觀察). 用1表示正常狀態(tài), 用0表示不正常狀態(tài), 所得的數(shù)據(jù)序列如下:11100100111111100111101111110011111

16、1111000110110111101101101011101110111101111110011011111100111設(shè)Xn為第n(n=1,2,...,97)個(gè)時(shí)段的計(jì)算機(jī)狀態(tài),,22,可以認(rèn)為它是一個(gè)齊次馬氏鏈, 狀態(tài)空間I={0,1}. 96次狀態(tài)轉(zhuǎn)移的情況是:0?0:8次; 0?1:18次; 1?0:18次; 1?1:52次.因此, 一步轉(zhuǎn)移概率可用頻率近似地表示為,23,例6 前例中計(jì)算機(jī)從某狀態(tài)0的條件下能連續(xù)正常工

17、作3個(gè)時(shí)段的條件概率為多少?解 由題意可得P{X1=1,X2=1,X3=1|X0=0}=P{X0=0,X1=2,X2=1,X3=1}/P{X0=0}=P{X0=0}P{X1=1|X0=0}P{X2=1|X1=1,X0=0}?P{X3=1|X2=1,X1=1,X0=0}/P{X0=0}=P{X1=1|X0=0}P{X2=1|X1=1}P{X3=1|X2=1},24,現(xiàn)在研究齊次馬氏鏈的有限維分布. 首先, 記pj(0)=P

18、{X0=aj}, aj?I, j=1,2,....稱(chēng)它為馬氏鏈的初始分布. 再看馬氏鏈在任一時(shí)刻n?T1的一維分布:pj(n)=P{Xn=aj}, aj?I, j=1,2,.... (1.6),又有,25,一維分布(1.6)也可用行向量表示成p(n)=(p1(n),p2(n),...,pj(n),...). (1.6)'這樣, 利用矩陣乘法(I是可列無(wú)限集時(shí), 仍用有限階矩陣乘法的規(guī)則確定矩陣之

19、積的元),p(n)=p(0)P(n).(1.7)'此式表明, 馬氏鏈在任一時(shí)刻n?T1時(shí)的一維分布由初始分布p(0)和n步轉(zhuǎn)移矩陣所確定.,26,又, 對(duì)于任意n個(gè)時(shí)刻t1<t2<...<tn, ti?T1,以及狀,27,由此, 并結(jié)合(1.7)或(1.7)'可知: 馬氏鏈的有限維分布同樣完全由初始分布和轉(zhuǎn)移概率所確定.總之, 轉(zhuǎn)移概率決定了馬氏鏈運(yùn)動(dòng)的統(tǒng)計(jì)規(guī)律.因此, 確定馬氏鏈的任意

20、n步轉(zhuǎn)移概率就成為馬氏鏈理論中的重要問(wèn)題之一.,28,§2 多步轉(zhuǎn)移概率的確定,29,設(shè){X(n),n=0,1,2,...}是一齊次馬氏鏈, 則對(duì)于任意的u,v?T1, 有,這是切普曼-科爾莫戈羅夫方程,簡(jiǎn)稱(chēng)C-K方程.,,,,,,,,,,,,,,,ai,ak,aj,s,s+u,s+u+v,t,O,30,C-K方程基于下述事實(shí), 即"從時(shí)刻t所處的狀態(tài)ai, 即X(s)=ai出發(fā), 經(jīng)時(shí)段u+v轉(zhuǎn)移到狀態(tài)aj, 即

21、X(s+u+v)=aj" 這一事件可分解成"從X(s)=ai出發(fā), 先經(jīng)時(shí)段u轉(zhuǎn)移到中間狀態(tài)ak(k=1,2,...), 再?gòu)腶k經(jīng)時(shí)段v轉(zhuǎn)移到狀態(tài)aj"這樣一些事件的和事件.先固定ak?I和s?T1, 由條件概率和乘法定理,P{X(s+u+v)=aj, X(s+u)=ak|X(s)=ai}=P{X(s+u)=ak|X(s)=ai}?P{X(s+u+v)=aj|X(s+u)=ak, X(s)=ai}

22、=Pik(u)Pkj(v). (2.2),31,又由于事件組"X(s+u)=ak",k=1,2,...構(gòu)成一劃分, 故有Pij(u+v)=P{X(s+u+v)=aj|X(s)=ai},將(2.2)式代入上式, 即得所要證明的C-K方程.C-K方程也可寫(xiě)成矩陣形式:P(u+v)=P(u)P(v).(2.1)',

23、32,P(u+v)=P(u)P(v).(2.1)'利用C-K方程容易確定n步轉(zhuǎn)移概率. 在(2.1)'式中令u=1, v=n-1, 得遞推關(guān)系P(n)=P(1)P(n-1)=PP(n-1),從而可得 P(n)=Pn.(2.3)就是說(shuō), 對(duì)齊次馬氏鏈而言, n步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的n次方.進(jìn)而可知, 鏈的有限維分布可由初始分布與一步轉(zhuǎn)移概率完全確定.,33,例1 設(shè){Xn,

24、n?0}是具有三個(gè)狀態(tài)0,1,2的齊次馬氏鏈, 一步轉(zhuǎn)移概率矩陣為,初始分布pi(0)=P{X0=i}=1/3, i=0,1,2. 試求(i)P{X0=0,X2=1}; (ii)P{X2=1}.,34,解 先求出二步轉(zhuǎn)移概率矩陣,于是(i)P{X0=0,X2=1}=P{X0=0}P{X2=1|X0=0},35,例2 在§1例2中, (i)設(shè)p=0.9, 求系統(tǒng)二級(jí)傳輸后的傳真率與三級(jí)傳輸后的誤碼率; (ii)設(shè)初始分布p1

25、(0)=P{X0=1}=a, p0(0)=P{X0=0}=1-a. 又已知系統(tǒng)經(jīng)n級(jí)傳輸后輸出為1, 問(wèn)原發(fā)字符是1的概率是多少?解 先求出n步轉(zhuǎn)移概率矩陣P(n)=Pn. 由于,有相異的特征值l1=1, l2=p-q,,36,由線性代數(shù)知識(shí), 可將P表示成對(duì)角陣,的相似矩陣. 具體做法是:求出l1,l2對(duì)應(yīng)的特征向量,37,則P=HLH-1. 于是, 容易算得Pn=(HLH-1)n=HLnH-1,38,(i) 因此, 當(dāng)p=0.

26、9時(shí), 系統(tǒng)二級(jí)傳輸后的傳真率與三級(jí)傳輸后的誤碼率分別為,(ii)根據(jù)貝葉斯公式有,39,對(duì)于只有兩個(gè)狀態(tài)的馬氏鏈, 一步轉(zhuǎn)移概率矩陣一般可表示為,利用類(lèi)似于例2的方法, 可得n步轉(zhuǎn)移概率矩陣為,40,§3 遍歷性,41,對(duì)于一般的兩個(gè)狀態(tài)的馬氏鏈, 由(2.5)式可知, 當(dāng)0<a,b<1時(shí), Pij(n)有極限,即對(duì)于固定的狀態(tài)j, 不管鏈在某一時(shí)刻從什么狀態(tài)(i=0或1)出發(fā), 通過(guò)長(zhǎng)時(shí)間的轉(zhuǎn)移, 到達(dá)狀態(tài)j的

27、概率都趨近于pj. 這就是所謂的遍歷性. 又由于p0+p1=1, 所以(p0,p1)=p構(gòu)成一分布律, 稱(chēng)它為鏈的極限分布.,42,設(shè)齊次馬氏鏈的狀態(tài)空間為I, 若對(duì)于所有ai,aj?I, 轉(zhuǎn)移概率Pij(n)存在極限,則稱(chēng)此鏈具有遍歷性, 又若 , 則同時(shí)稱(chēng)p=(p1,p2,...)為鏈的極限分布.,43,齊次馬氏鏈在什么條件下才具有普遍性?如何求出它的極限分布?這問(wèn)題在理論上已經(jīng)圓滿解決, 但敘述它

28、需要較多篇幅. 下面僅就只有有限個(gè)狀態(tài)的鏈, 即有限鏈的遍歷性給出一個(gè)充分條件.,44,定理 設(shè)齊次馬氏鏈{Xn, n?1}的狀態(tài)空間為I={a1,a2,...,aN}. P是它的一步轉(zhuǎn)移概率矩陣, 如果存在正整數(shù)m, 使對(duì)任意的ai,aj?I, 都有Pij(m)>0, i,j=1,2,...,N, (3.1)則此鏈具有遍歷性, 且有極限分布p=(p1,p2,...,pN), 它是方程組

29、p=pP或即,的滿足條件,的唯一解.,45,依照定理, 為證有限鏈?zhǔn)潜闅v的, 只需找一正整數(shù)m, 使m步轉(zhuǎn)移概率矩陣Pm無(wú)零元. 而求極限分布p的問(wèn)題, 化為求解方程組(3.2)的問(wèn)題. 注意, 方程組(3.2)中僅N-1個(gè)未知數(shù)是獨(dú),在定理的條件下, 馬氏鏈的極限分布又是平穩(wěn)分布. 意即, 若用p作為鏈的初始分布, 即p(0)=p, 則鏈在任一時(shí)刻n?T1的分布p(n)永遠(yuǎn)與p一致. 事實(shí)上, 由(1.7)',(2.3)和(3

30、.2)式有 p(n)=p(0)P(n)=pPn=pPn-1=...=pP=p.,46,例1 試說(shuō)明§1例3中, 帶有兩個(gè)反射壁的隨機(jī)游動(dòng)是遍歷的, 并求其極限分布(平穩(wěn)分布).解 為簡(jiǎn)便計(jì), 以符號(hào)"?"代表轉(zhuǎn)移概率矩陣的正的元. 于是, 由例3中的一步轉(zhuǎn)移概率矩陣P(2)=P2=,47,P(4)=P4=,即P(4)無(wú)零元, 由定理, 鏈?zhǔn)潜闅v的. 再根據(jù)(3.2)和(3.3)式, 寫(xiě)出極限分布p=

31、(p1,p2,...,p5)滿足的方程組.,48,先由前四個(gè)方程, 解得3p1=p2=p3=p4=3p5. 將它們代入最后一個(gè)方程, 解得極限分布為p=(1/11,3/11,3/11,3/11,1/11).,49,例2 試說(shuō)明§1例4(排隊(duì)模型)中的鏈?zhǔn)潜闅v的, 并求其極限分布.解 依照例1, 由中的一步轉(zhuǎn)移概率矩陣P, 可算得P(3)=P3無(wú)零元. 根據(jù)定理, 鏈?zhǔn)潜闅v的, 而極限分布p=(p0,p1,p2,p3)滿足下

32、列方程組:,50,解出的唯一解為p0=p3(1-q)3/C, p1=p2q(1-q)2/C,p2=pq2(1-q)(1-p)/C, p3=q3(1-p)2/C,其中C=p3(1-q)3+p2q(1-q)2+pq2(1-q)(1-p)+q3(1-p)2.假若在此例中, p=q=1/2, 則可算得此時(shí)的極限分布為p=(1/7,2/7,2/7,2/7). 這就是說(shuō), 經(jīng)過(guò)相當(dāng)長(zhǎng)時(shí)間后, 系統(tǒng)中無(wú)人的情形約占14%的時(shí)間, 而系