第7章 馬爾可夫鏈與泊松過程

1、隨機(jī)信號(hào)分析隨機(jī)信號(hào)分析電氣學(xué)院電氣學(xué)院 電子工程系電子工程系林霏林霏2第第7章章 馬爾可夫鏈與泊松過程馬爾可夫鏈與泊松過程 馬爾可夫過程是研究信號(hào)多級(jí)傳輸、馬爾可夫過程是研究信號(hào)多級(jí)傳輸、分子的布朗運(yùn)動(dòng)、顧客服務(wù)、計(jì)算機(jī)網(wǎng)絡(luò)分子的布朗運(yùn)動(dòng)、顧客服務(wù)、計(jì)算機(jī)網(wǎng)絡(luò)流量等等諸多問題時(shí)使用的經(jīng)典模型。流量等等諸多問題時(shí)使用的經(jīng)典模型。 本章討論：本章討論：1）馬爾可夫過程的基本概念）馬爾可夫過程的基本概念2）轉(zhuǎn)移概率與）轉(zhuǎn)移概率與C-K方程方程3）狀態(tài)分類及極限特性）狀態(tài)分類及極限特性4）獨(dú)立增量過程定義及性質(zhì)）獨(dú)立增量過程定義及性質(zhì)5）泊松過程定義及相關(guān)問題）泊松過程定義及相關(guān)問題3第第7章章 馬

2、爾可夫鏈與泊松過程馬爾可夫鏈與泊松過程7.1 馬爾可夫鏈馬爾可夫鏈7.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類7.3 獨(dú)立增量過程獨(dú)立增量過程7.4 泊松過程泊松過程41. 馬爾可夫性馬爾可夫性(無后效性無后效性)所所處處的的狀狀態(tài)態(tài)為為已已知知的的在在時(shí)時(shí)刻刻系系統(tǒng)統(tǒng)過過程程或或0)(t所所處處狀狀態(tài)態(tài)的的條條件件分分布布與與過過程程在在時(shí)時(shí)刻刻條條件件下下0,tt 特特性性稱稱為為之之前前所所處處的的狀狀態(tài)態(tài)無無關(guān)關(guān)的的與與過過程程在在時(shí)時(shí)刻刻0t馬爾可夫性馬爾可夫性或或無后效性無后效性.即即: 過程過程“將來將來”的情況與的情況與“過去過去”的情況是無的情況是無關(guān)的關(guān)的.52. 馬爾

3、可夫過程的定義馬爾可夫過程的定義具有馬爾可夫性的隨機(jī)過程稱為具有馬爾可夫性的隨機(jī)過程稱為馬爾可夫過程馬爾可夫過程.用分布函數(shù)表述馬爾可夫過程用分布函數(shù)表述馬爾可夫過程,),(:的的狀狀態(tài)態(tài)空空間間隨隨機(jī)機(jī)過過程程設(shè)設(shè)TttXI ,個(gè)個(gè)數(shù)數(shù)值值的的任任意意如如果果對(duì)對(duì)時(shí)時(shí)間間nt, 3,21Ttntttin 恰有恰有)(,)(,)(|)(112211 nnnnxtXxtXxtXxtXP ,)(|)(11RxxtXxtXPnnnnn 下下的的條條件件分分布布函函數(shù)數(shù)在在條條件件iinxtXtX )()(下下的的條條件件分分布布函函數(shù)數(shù)在在條條件件11)()( nnnxtXtX6或?qū)懗苫驅(qū)懗?,;,

4、|,(121121|11 nnnnttttttxxxtxFnn),|,(11|1 nnnntttxtxFnn.),(性性具具馬馬爾爾可可夫夫性性或或無無后后效效這這時(shí)時(shí)稱稱過過程程TttX 并稱此過程并稱此過程為為馬爾可夫過程馬爾可夫過程.3. 馬爾可夫鏈的定義馬爾可夫鏈的定義 時(shí)間和狀態(tài)都是離散的馬爾可夫過程稱為時(shí)間和狀態(tài)都是離散的馬爾可夫過程稱為馬爾馬爾可夫鏈可夫鏈, ., 2 , 1 , 0),( nnXXn簡(jiǎn)記為簡(jiǎn)記為7 1.馬爾可夫鏈馬爾可夫鏈 時(shí)間離散，狀態(tài)離散；時(shí)間離散，狀態(tài)離散；2.離散馬爾可夫過程離散馬爾可夫過程 時(shí)間連續(xù)，狀態(tài)離散；時(shí)間連續(xù)，狀態(tài)離散；3.馬爾可夫序列馬爾可

5、夫序列 時(shí)間離散，狀態(tài)連續(xù)；時(shí)間離散，狀態(tài)連續(xù)；4.連續(xù)馬爾可夫過程連續(xù)馬爾可夫過程 時(shí)間連續(xù)，狀態(tài)連續(xù)時(shí)間連續(xù)，狀態(tài)連續(xù)。馬爾可夫過程分類：馬爾可夫過程分類：王梓坤院士王梓坤院士馬爾可夫馬爾可夫8研究時(shí)間和狀態(tài)都是離散的隨機(jī)序列研究時(shí)間和狀態(tài)都是離散的隨機(jī)序列.,(21RaaaIi 狀狀態(tài)態(tài)空空間間為為, 2, 1 , 0),( nnXXn1. 用分布律描述馬爾可夫性用分布律描述馬爾可夫性;0,21mtttrnr 和和對(duì)對(duì)任任意意的的正正整整數(shù)數(shù),iiTmnmt 有有1122|,rrm njtititimiP XaXa XaXaXa , |imjnmaXaXP . Iai 其其中中9稱條件概

6、率稱條件概率 |),(imjnmijaXaXPnmmP nmami 在在時(shí)時(shí)刻刻條條件件下下處處于于狀狀態(tài)態(tài)為為馬馬氏氏鏈鏈在在時(shí)時(shí)刻刻,.的的轉(zhuǎn)轉(zhuǎn)移移概概率率轉(zhuǎn)轉(zhuǎn)移移到到狀狀態(tài)態(tài)ja說明說明: 轉(zhuǎn)移概率具有特點(diǎn)轉(zhuǎn)移概率具有特點(diǎn) ., 2 , 1, 1),(1 jijinmmP2. 轉(zhuǎn)移概率轉(zhuǎn)移概率由轉(zhuǎn)移概率組成的矩陣由轉(zhuǎn)移概率組成的矩陣),(),(nmmPnmmPij 稱為馬氏鏈的稱為馬氏鏈的轉(zhuǎn)移概率矩陣轉(zhuǎn)移概率矩陣.此矩陣的每一行元此矩陣的每一行元素之和等于素之和等于1.它是隨機(jī)矩陣它是隨機(jī)矩陣.102、馬爾可夫鏈的一般特性、馬爾可夫鏈的一般特性狀態(tài)概率狀態(tài)概率：( )jnjp nP xa

7、TNnpnpnpn)()()()(21p概率分布列概率分布列：( , )ijnjmip m nP xaxa轉(zhuǎn)移概率：轉(zhuǎn)移概率：1111( , )( , )( , )( , )( , )NNNNP m nPm nm nPm nPm nP轉(zhuǎn)移矩陣：轉(zhuǎn)移矩陣：11Njjnp11)(性質(zhì)性質(zhì): (1)11(, )1NNijnjmijjpm nP xaxa(2)1( )( , )()Njijiipnpm n p m(3)( )(, ) ()Tnm nmpPp(4)或或: ( )()(, )nmm nppPp161 (7.13)121( )( , )( )Njijiip np m n p m(3)1( )

8、,Njnjmiip np XaXa1/Nnjmimiip XaXa p Xa1( , )( )Nijiipm n p m133. 平穩(wěn)性平穩(wěn)性njinmmPij及及時(shí)時(shí)間間間間距距只只與與當(dāng)當(dāng)轉(zhuǎn)轉(zhuǎn)移移概概率率,),( 有關(guān)時(shí)有關(guān)時(shí), 稱轉(zhuǎn)移概率具有齊次性稱轉(zhuǎn)移概率具有齊次性.同時(shí)也稱此鏈?zhǔn)峭瑫r(shí)也稱此鏈?zhǔn)驱R次的齊次的或或時(shí)齊的時(shí)齊的.),(),(,nPnmmPijij 記記此時(shí)此時(shí) . |)(imjnmijaXaXPnP 稱為馬氏鏈的稱為馬氏鏈的n步轉(zhuǎn)移概率步轉(zhuǎn)移概率.)()(步轉(zhuǎn)移概率矩陣步轉(zhuǎn)移概率矩陣為為nnPnPij 14一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率.|()1(1imjmijijaXaXPPp

9、 特別的特別的, 當(dāng)當(dāng) n=1 時(shí)時(shí),一步轉(zhuǎn)移概率矩陣一步轉(zhuǎn)移概率矩陣的狀態(tài)的狀態(tài)1 mX的狀態(tài)的狀態(tài)mXiaaa21jaaa21 ijiijjppppppppp211222111211)1(P 記為記為P)1(P1516171819例例 一維隨機(jī)游動(dòng)一維隨機(jī)游動(dòng).21,5 , 4 , 3 , 2 , 1等時(shí)刻發(fā)生游動(dòng)等時(shí)刻發(fā)生游動(dòng)秒秒秒、秒、并且僅僅在并且僅僅在上作隨機(jī)游動(dòng)上作隨機(jī)游動(dòng)在如圖所示直線的點(diǎn)集在如圖所示直線的點(diǎn)集一隨機(jī)游動(dòng)的質(zhì)點(diǎn)一隨機(jī)游動(dòng)的質(zhì)點(diǎn) I12345游動(dòng)的概率規(guī)則游動(dòng)的概率規(guī)則1/3的概率向左或向右移動(dòng)一格的概率向左或向右移動(dòng)一格, 或以或以1/3的概率留的概率留在原處在

10、原處; 如果如果Q現(xiàn)在位于點(diǎn)現(xiàn)在位于點(diǎn) i (1 i 5),則下一時(shí)刻各以則下一時(shí)刻各以2012345以概率以概率1移動(dòng)到移動(dòng)到2(或或4)這一點(diǎn)上這一點(diǎn)上.如果如果Q現(xiàn)在位于現(xiàn)在位于1(或或5)這點(diǎn)上這點(diǎn)上, 則下一時(shí)刻就則下一時(shí)刻就1和和5這兩點(diǎn)稱為這兩點(diǎn)稱為反射壁反射壁.上面這種游動(dòng)稱為上面這種游動(dòng)稱為帶有兩個(gè)帶有兩個(gè)反射壁反射壁的隨機(jī)游動(dòng)的隨機(jī)游動(dòng).12345模擬方法模擬方法:產(chǎn)生均勻分布的隨機(jī)數(shù)序列產(chǎn)生均勻分布的隨機(jī)數(shù)序其中其中1表示左移表示左移;2表示不動(dòng)表示不動(dòng);3表示右移表示右移.21理論分析理論分析:.的位置的位置時(shí)時(shí)表示時(shí)刻表示時(shí)刻以以QnXn.,

11、 2 , 1 , 0,是是一一隨隨機(jī)機(jī)過過程程則則 nXn狀態(tài)空間就是狀態(tài)空間就是I.,為為已已知知時(shí)時(shí)且且當(dāng)當(dāng)IiiXn ,1有有關(guān)關(guān)所所處處的的狀狀態(tài)態(tài)分分布布只只與與iXXnn 而與時(shí)刻而與時(shí)刻 n 以前所處的狀態(tài)無關(guān)以前所處的狀態(tài)無關(guān).所以它是一個(gè)馬氏鏈所以它是一個(gè)馬氏鏈, 且是齊次的且是齊次的. 22一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率|1iXjXPpnnij 1,1, ,1,153 1,1,25,40,2.jii iiijijji 或23 010003/13/13/10003/13/13/10003/13/13/10001054321P5 4 3 2 1說明說明:相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把相應(yīng)

12、鏈的轉(zhuǎn)移概率矩陣只須把P 中第中第1行改為行改為改變游動(dòng)的概率規(guī)則改變游動(dòng)的概率規(guī)則, 就可得到不同方式的就可得到不同方式的隨機(jī)游動(dòng)和相應(yīng)的馬氏鏈隨機(jī)游動(dòng)和相應(yīng)的馬氏鏈. 如果把點(diǎn)如果把點(diǎn) 1 改為改為吸收壁吸收壁, ).0 , 0 , 0 , 0 , 1(一步轉(zhuǎn)移概率矩陣一步轉(zhuǎn)移概率矩陣241( , )( , )( , )Nijikkjkpm npm r pr nnrm，定理定理7.1（切普曼（切普曼-科爾莫戈羅夫方程：科爾莫戈羅夫方程：C-K方程方程）：）： 馬爾可夫鏈的轉(zhuǎn)移概率矩陣滿足馬爾可夫鏈的轉(zhuǎn)移概率矩陣滿足說明說明C-K 方程基于下列事實(shí)方程基于下列事實(shí):,( ).ijjman m

13、a X na“從時(shí)刻所處的狀態(tài)出發(fā) 經(jīng)時(shí)段轉(zhuǎn)移到狀態(tài)”25這一事件可分解成這一事件可分解成:( ),iX mau“從出發(fā) 先經(jīng)時(shí)段 轉(zhuǎn)移到中間狀態(tài)”等事”等事轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)經(jīng)時(shí)段經(jīng)時(shí)段在從在從jkkavaka),2, 1( 件的和事件件的和事件.tommumuvniakaja如下圖所示如下圖所示:26證明證明,1TsIak 和和先先固固定定,njmimiP xaxaP xa( , )ijnjmipm nP xaxa1,NnjrkmirkmikrkmimiP xaxaxaP xaxaP xaxaP xa1/,/NnjrkmirkmikP xaxaxaP xaxa27若齊次，若齊次，C-K

14、方程也可寫成矩陣形式方程也可寫成矩陣形式: ).()()(vPuPvuP 1/, /NnjrkmirkmikP xaxa xa P xaxa馬氏性馬氏性1/ /NnjrkrkmikP xaxaP xaxa1( , )( , )Nikkjkp m r p r n28利用利用 C-K 方程我們?nèi)菀状_定方程我們?nèi)菀状_定 n 步轉(zhuǎn)移概率步轉(zhuǎn)移概率.得遞推關(guān)系得遞推關(guān)系: , 1, 1 ,)()()( nvuvPuPvuP令令中中在在),1()1()1()( nPPnPPnP( ).nP nP從而可得從而可得 馬氏鏈的馬氏鏈的n步轉(zhuǎn)移概率是一步轉(zhuǎn)移概率的步轉(zhuǎn)移概率是一步轉(zhuǎn)移概率的 n 次次方方,鏈的有限

15、維分布可由鏈的有限維分布可由初始分布初始分布和和一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率完全確定完全確定.結(jié)論結(jié)論29定理定理7.2 齊次馬氏鏈滿足齊次馬氏鏈滿足1(1)( )(0)nnn PP30 某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障某計(jì)算機(jī)房的一臺(tái)計(jì)算機(jī)經(jīng)常出故障,研究者研究者每隔每隔15分鐘觀察一次計(jì)算機(jī)運(yùn)行狀態(tài)分鐘觀察一次計(jì)算機(jī)運(yùn)行狀態(tài),收集了收集了24小小時(shí)的數(shù)據(jù)時(shí)的數(shù)據(jù) (共作共作97次觀察次觀察) . 用用1表示正常狀態(tài)表示正常狀態(tài), 用用0表示不正常狀態(tài)表示不正常狀態(tài), 所得的數(shù)據(jù)序列如下所得的數(shù)據(jù)序列如下:111001001111111001111011111100111111111000110

16、1101分析分析,)97, 2, 1(個(gè)時(shí)段的計(jì)算機(jī)狀態(tài)個(gè)時(shí)段的計(jì)算機(jī)狀態(tài)為第為第設(shè)設(shè) nnXn狀態(tài)空間狀態(tài)空間: I=0, 1. 例例1110110110101111011101111011111100110111111001113196 次狀態(tài)轉(zhuǎn)移的情況次狀態(tài)轉(zhuǎn)移的情況: ;8, 00次次;18, 01次次因此因此, 一步轉(zhuǎn)移概率可用頻率近似地表示為一步轉(zhuǎn)移概率可用頻率近似地表示為:,26818880|0100 nnXXPp,2618188180|1101 nnXXPp,70185218181|0110 nnXXPp.70525218521|1111 nnXXPp;18, 10 次次.52

17、, 11次次32?55,35,15.1,. )10(,1,0.,21,31,于于多多少少日日為為雨雨天天的的概概率率各各等等月月日日為為晴晴天天月月問問天天日日為為晴晴月月又又已已知知的的一一步步轉(zhuǎn)轉(zhuǎn)移移概概率率矩矩陣陣試試寫寫出出馬馬氏氏鏈鏈或或天天狀狀態(tài)態(tài)表表示示第第表表示示雨雨天天狀狀態(tài)態(tài)以以表表示示晴晴天天狀狀態(tài)態(tài)以以為為逆逆事事件件任任一一天天晴晴或或雨雨是是互互晴晴天天轉(zhuǎn)轉(zhuǎn)雨雨天天的的概概率率為為雨雨天天轉(zhuǎn)轉(zhuǎn)晴晴天天的的概概率率為為設(shè)設(shè)任任意意相相繼繼的的兩兩天天中中 nXnXnn解解為逆事件且雨天轉(zhuǎn)為逆事件且雨天轉(zhuǎn)由于任一天晴或雨是互由于任一天晴或雨是互轉(zhuǎn)轉(zhuǎn)移移概概率率矩矩陣陣分

18、分別別為為故故一一步步轉(zhuǎn)轉(zhuǎn)移移概概率率和和一一步步,21,31晴晴天天轉(zhuǎn)轉(zhuǎn)雨雨天天的的概概率率為為晴晴天天的的概概率率為為例例33 1, 0,210, 0,211, 1,320, 1,311jijijijiiXjXPnn 323121211010P又由于又由于 181118712712510102P34,6003. 03997. 05995. 04005. 010104 P又又由由于于日日為為雨雨天天的的概概率率為為月月日日為為晴晴天天月月故故55,15.5995. 0)4(01 P日日為為晴晴天天的的概概率率為為月月日日為為晴晴天天月月故故35,15,4167. 0125)2(00 P35

19、步步轉(zhuǎn)轉(zhuǎn)移移概概率率矩矩陣陣為為一一馬馬氏氏鏈鏈?zhǔn)鞘蔷呔哂杏腥齻€(gè)個(gè)狀狀態(tài)態(tài)的的齊齊次次設(shè)設(shè),0, nXn.1)2(;1,0)1(:,2,1,0,31)0(2200 XPXXPiiXPpi求求初初始始分分布布,4143041214104143 P解解(1)先求出先求出2步轉(zhuǎn)移概率矩陣步轉(zhuǎn)移概率矩陣:例例1.411691631632116516116585)2(2 PP020,1P XX0|10020 XXPXP)2()0(010pp ,48516531 36 步步轉(zhuǎn)轉(zhuǎn)移移概概率率矩矩陣陣為為一一馬馬氏氏鏈鏈?zhǔn)鞘蔷呔哂杏腥齻€(gè)個(gè)狀狀態(tài)態(tài)的的齊齊次次設(shè)設(shè),0, nXn.1)2(;1,0)1(:,2

20、,1,0,31)0(2200 XPXXPiiXPpi求求初初始始分分布布,4143041214104143 P解解例例11(2) (2)p12 XP001111221(0)(2)(0)(2)(0)(2)pppppp.2411)16921165(31 1( ),Njnjmiip np Xa Xa1/Nnjmimiip Xa Xa p Xa1(,)()Nijiipm n pm37,( 1).,1 ,1 ,.2.,1.npqr pqrXn 甲乙兩人進(jìn)行某種比賽 設(shè)每局比賽中甲勝的概率為乙勝的概率為平局的概率為設(shè)每局比賽后 勝者得 分 負(fù)者得分 平局不記分 當(dāng)兩人中有一個(gè)人得到 分時(shí)比賽結(jié)束以為齊次馬

21、爾可夫鏈.2,1)3(;2)2(;)1(結(jié)結(jié)束束的的概概率率局局可可以以最最多多再再賽賽分分的的情情況況下下問問在在甲甲獲獲得得步步轉(zhuǎn)轉(zhuǎn)移移概概率率求求寫寫出出狀狀態(tài)態(tài)空空間間例例338解解 .2, 1, 0, 1, 2)1( S 1121012)1(21012)2(prqprqprqP39222222222101212 .22221qrprpqprpPqrqrpqprpqqrrpqppr所所求求甲甲勝勝局局再再賽賽分分的的情情況況下下在在甲甲獲獲得得,2,1)3(概率為概率為. )1()2(12rpprppp 21012404142（3）狀態(tài)轉(zhuǎn)移圖為）狀態(tài)轉(zhuǎn)移圖為：0 1 2 3 4 012

22、3.43444546(3)4748495000( )(0)1X tX令初始值為 ，即121( )()()nnnnnnX tX tXX tXX 11(0)nniiiiXXX5152, 0)0(,0),( XttX且且是是獨(dú)獨(dú)立立增增量量過過程程設(shè)設(shè).0),(是是一一個(gè)個(gè)馬馬爾爾可可夫夫過過程程證證明明 ttX證明證明由獨(dú)立增量過程的定義知由獨(dú)立增量過程的定義知,2, 2 , 1,01時(shí)時(shí)當(dāng)當(dāng) njtttnnj.)()()0()(1相互獨(dú)立相互獨(dú)立與與增量增量 nnjtXtXXtX,)(0)0(11 nnxtXX與與根根據(jù)據(jù)條條件件即有即有.)()(1相互獨(dú)立相互獨(dú)立與與 nnjxtXtX例例15

23、3.2, 2 , 1),()(相相互互獨(dú)獨(dú)立立與與此此時(shí)時(shí) njtXtXjn是是一一個(gè)個(gè)即即具具有有無無后后效效性性這這表表明明0),(,)( ttXtX馬爾可夫過程馬爾可夫過程.說明說明:泊松過程是時(shí)間連續(xù)狀態(tài)離散的馬氏過程泊松過程是時(shí)間連續(xù)狀態(tài)離散的馬氏過程;維納過程是時(shí)間狀態(tài)都連續(xù)的馬氏過程維納過程是時(shí)間狀態(tài)都連續(xù)的馬氏過程.5455泊松過程泊松過程 考慮下列隨時(shí)間推移遲早會(huì)重復(fù)出現(xiàn)考慮下列隨時(shí)間推移遲早會(huì)重復(fù)出現(xiàn)的事件的事件: :(i) (i) 自電子管陰極發(fā)射的電子到達(dá)陽極自電子管陰極發(fā)射的電子到達(dá)陽極; ;(ii) (ii) 意外事故或意外差錯(cuò)的發(fā)生意外事故或意外差錯(cuò)的發(fā)生; ;(

24、iii) (iii) 要求服務(wù)的顧客到達(dá)服務(wù)站。要求服務(wù)的顧客到達(dá)服務(wù)站。 此處此處 顧客顧客 與與 服務(wù)站服務(wù)站 的含義也是相當(dāng)廣的含義也是相當(dāng)廣泛的泛的. . 例如例如, , 顧客顧客 可以是電話的呼叫可以是電話的呼叫, , 服務(wù)服務(wù)站站 是是120120急救臺(tái)急救臺(tái); ; 顧客顧客 可以是來領(lǐng)配件的汽車可以是來領(lǐng)配件的汽車維修工維修工, , 服務(wù)站服務(wù)站 是維修站配件倉(cāng)庫(kù)的管理員是維修站配件倉(cāng)庫(kù)的管理員, , 顧客顧客 也可以是聯(lián)網(wǎng)的個(gè)人電腦也可以是聯(lián)網(wǎng)的個(gè)人電腦, , 服務(wù)站服務(wù)站 是某是某網(wǎng)站的主頁(yè)等等網(wǎng)站的主頁(yè)等等. .56為建立一般模型方便起見為建立一般模型方便起見, , 把電子把電子, , 顧客等看作顧客等看作時(shí)間軸上的質(zhì)點(diǎn)時(shí)間軸上的質(zhì)點(diǎn), ,