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

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

2、繪的物理過程. 將這樣的原則延伸到隨機現(xiàn)象, 引入馬爾可夫性或無后效性: 過程(或系統(tǒng))在時刻t0所處的狀態(tài)為已知條件下, 過程在時刻t>t0所處狀態(tài)的條件分布與過程在時刻t0之前的狀態(tài)無關(guān). 即已經(jīng)知道過程"現(xiàn)在"的條件下, 其"將來"不依賴于"過去".,4,設(shè)隨機過程{X(t), t?T}的狀態(tài)空間為I. 如果對任意n個時間值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ū)懗?則稱過程{X(t), t?T}具有馬爾可夫性或無后效性, 并稱此過程為馬爾可夫過程.,5,例1 設(shè){X(t),t?0}是獨立增量過程, 且X(0)=0

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

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

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

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

8、} (1.5)稱為馬氏鏈的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è)和上邊標上狀態(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è)每一級傳真率為p, 誤碼率為q=1

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

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

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

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

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

14、同)p00=1-q.p01:系統(tǒng)內(nèi)沒有顧客的條件下, 經(jīng)Dt后有一顧客進入系統(tǒng)的概率, p01=q.p10:系統(tǒng)內(nèi)恰 有一顧客正在接受服務(wù)的條件下, 經(jīng)Dt后系統(tǒng)內(nèi)無人的概率. 它等于在Dt間隔內(nèi)顧客因服務(wù)完畢而離去, 且無人進入系統(tǒng)的概率, p10=p(1-q).,19,類似地有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,在實際問題中, 一步轉(zhuǎn)移概率通?？赏ㄟ^統(tǒng)計試驗確定, 下面看一實例.例5 某計算機房的一臺計算機經(jīng)常出故障, 研究者每隔15分鐘觀察一次計算機的運行狀態(tài), 收集了24小時的數(shù)據(jù)(共作97次觀察). 用1表示正常狀態(tài), 用0表示不正常狀態(tài), 所得的數(shù)據(jù)序列如下:11100100111111100111101111110011111

16、1111000110110111101101101011101110111101111110011011111100111設(shè)Xn為第n(n=1,2,...,97)個時段的計算機狀態(tài),,22,可以認為它是一個齊次馬氏鏈, 狀態(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 前例中計算機從某狀態(tài)0的條件下能連續(xù)正常工

17、作3個時段的條件概率為多少?解 由題意可得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,....稱它為馬氏鏈的初始分布. 再看馬氏鏈在任一時刻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是可列無限集時, 仍用有限階矩陣乘法的規(guī)則確定矩陣之

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

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

21、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"這樣一些事件的和事件.先固定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方程也可寫成矩陣形式: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)就是說, 對齊次馬氏鏈而言, n步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的n次方.進而可知, 鏈的有限維分布可由初始分布與一步轉(zhuǎn)移概率完全確定.,33,例1 設(shè){Xn,

24、n?0}是具有三個狀態(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)二級傳輸后的傳真率與三級傳輸后的誤碼率; (ii)設(shè)初始分布p1

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

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

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

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

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

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

31、(p1,p2,...,p5)滿足的方程組.,48,先由前四個方程, 解得3p1=p2=p3=p4=3p5. 將它們代入最后一個方程, 解得極限分布為p=(1/11,3/11,3/11,3/11,1/11).,49,例2 試說明§1例4(排隊模型)中的鏈是遍歷的, 并求其極限分布.解 依照例1, 由中的一步轉(zhuǎn)移概率矩陣P, 可算得P(3)=P3無零元. 根據(jù)定理, 鏈是遍歷的, 而極限分布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, 則可算得此時的極限分布為p=(1/7,2/7,2/7,2/7). 這就是說, 經(jīng)過相當(dāng)長時間后, 系統(tǒng)中無人的情形約占14%的時間, 而系