隨機(jī)過(guò)程馬爾科夫過(guò)程PPT課件

1、馬爾可夫 (1856年6月14日1922年7月20日）馬爾可夫?qū)?shù)學(xué)的最大貢獻(xiàn)是在概率論領(lǐng)域作出的十九世紀(jì)后二十年，他主要是沿著切比雪夫開(kāi)創(chuàng)的方向，致力于獨(dú)立隨機(jī)變量和古典極值理論的研究，從而改進(jìn)和完善了大數(shù)定律和中心極限定理 二十世紀(jì)初，他的興趣轉(zhuǎn)移到相依隨機(jī)變量序列的研究上來(lái)，從而創(chuàng)立了以他命名的著名概率模型馬爾可夫鏈第1頁(yè)/共44頁(yè)王梓坤院士(1929年)江西吉安人,1952年大學(xué)畢業(yè)后，被分派到天津南開(kāi)大學(xué)數(shù)學(xué)系任教. 是一位對(duì)我國(guó)科學(xué)和教育事業(yè)作出卓越貢獻(xiàn)的數(shù)學(xué)家和教育家，也是我國(guó)概率論研究的先驅(qū)和學(xué)術(shù)帶頭人之一。 1954年，他又以優(yōu)異的成績(jī)考取了赴蘇研究生。踏進(jìn)世界著名學(xué)府莫斯科

2、大學(xué)，在這個(gè)學(xué)府世界概率論的奠基人柯?tīng)柲缏宸蛟菏空I(lǐng)導(dǎo)看一個(gè)強(qiáng)有力的概率研究集團(tuán)?？?tīng)柲呗宸蚧垩圩R(shí)英才，非常信賴這位由中國(guó)選派的年輕人的能力，把他選作自己的研究生，去攻概率論的中心問(wèn)題隨機(jī)過(guò)程理論。 當(dāng)時(shí)中國(guó)近代數(shù)學(xué)才剛剛起步，大學(xué)也沒(méi)有概率課程。此時(shí)蘇聯(lián)的概率論水平已屆于世界最前列。王梓坤也根本不知道什么是概率，可他的研究方向又恰恰被定為概率論，著有概率論基礎(chǔ)及其應(yīng)用、隨機(jī)過(guò)程論、生滅過(guò)程與馬爾科夫鏈等9部數(shù)學(xué)著作 第2頁(yè)/共44頁(yè)馬爾可夫過(guò)程的定義馬爾可夫鏈的轉(zhuǎn)移概率與概率分布齊次馬爾可夫鏈狀態(tài)的分類(lèi)轉(zhuǎn)移概率的穩(wěn)定性能本章主要內(nèi)容第3頁(yè)/共44頁(yè) 引例(有限制隨機(jī)游動(dòng)問(wèn)題) 設(shè)質(zhì)點(diǎn)只能

3、在0，1，2，a中的各點(diǎn)上作隨機(jī) 游動(dòng)，移動(dòng)規(guī)則如下：11,2,1ia（）移動(dòng)前處; 1, 0,rqprqp0000,0,1p rprii+1i-1pqr010p0r20i （ ）移動(dòng)前處3ia（ ）移動(dòng)前處a-1aqaar,0,1aaaaq rqr設(shè)Xn表示質(zhì)點(diǎn)在n時(shí)刻所處的位置第4頁(yè)/共44頁(yè)1馬爾可夫過(guò)程的定義一.一. 基本概念基本概念1馬爾可夫性馬爾可夫性通俗地說(shuō)，就是在知道過(guò)程現(xiàn)在的條件下，其將來(lái)的條件分布不依賴于過(guò)去，則稱(chēng)),(TttX具有馬爾可夫（Markov)性。定義設(shè)),(TttX是一個(gè)隨機(jī)過(guò)程，如果),(TttX在t0時(shí)刻所處的狀態(tài)為已知，它在時(shí)刻0tt 所處狀態(tài)的條件分布

4、與其在 t0 之前 所處的狀態(tài)無(wú)關(guān)。0tt現(xiàn)在0tt將來(lái)0tt過(guò)去第5頁(yè)/共44頁(yè)2. 馬爾可夫過(guò)程定義 設(shè)),(TttX的狀態(tài)空間為S,122,nntttT 如果對(duì)( ),1,2,1iiiX txxSin在條件下)(ntX的條件分布函數(shù)恰好等于11()nnX tx在條件下的條件分布函數(shù),即11221111( ),( ),()( )(,)()nnnnnnnnnP X txP X txX txX txX txXRtxx( ),X t tT馬爾則稱(chēng)為可夫過(guò)程.第6頁(yè)/共44頁(yè)3.馬爾可夫鏈定義 參數(shù)集和狀態(tài)空間都是離散的馬爾可夫過(guò)程稱(chēng)為馬爾可夫鏈。注 只討論馬爾可夫鏈的狀態(tài)空間為有限或可列無(wú)限.則

5、馬爾可夫性可表示為12122, , ,nnntttT i iiS 對(duì)11111122()( ),( )( )(),),nnnnnnnnnP X tiP X tixX tiX tiRX tiX ti有第7頁(yè)/共44頁(yè)特別對(duì)取T=0,1,2,的馬爾可夫鏈，記為0),(nnX或0,nXn此時(shí)的馬爾可夫性為011, , ,nni iiS 對(duì)有0111(1)(1)(0),(1( )( ),nnnnP X niPXiXiX niXX niin10110111,),()nnnnnnnnXP XiP XXiXiiXii或今后,記1,2,3,0,1,2,ST,0nXn 馬爾可夫鏈記為馬氏鏈也稱(chēng),或系統(tǒng)第8頁(yè)/共

6、44頁(yè)二 馬爾可夫鏈的轉(zhuǎn)移概率1. 轉(zhuǎn)移概率定義 設(shè)0,nXn是馬爾可夫鏈,稱(chēng)條件概率,0nXnni(它表示系統(tǒng)在 時(shí)處于狀態(tài)的條件下經(jīng)過(guò)k步轉(zhuǎn)移,于n+k時(shí)到達(dá)狀態(tài)j的條件概率).( )( )(,0,)1kijn knpnP Xj Xi jS nik,0nXn 為在n時(shí)的k步轉(zhuǎn)移概率.( )( )kijipnj稱(chēng)以為第 行底 列元素的矩陣)()()()(npnkijkP,0nXn 為系統(tǒng)在n時(shí)的k步轉(zhuǎn)移概率矩陣.第9頁(yè)/共44頁(yè)( )( )ijnp nP記為特別 當(dāng)k=1時(shí)，(1)( )ijnpn 為系統(tǒng)在 時(shí)的一步轉(zhuǎn)移概率,(1)(1)( )( )ijnpnP為系統(tǒng)的一步轉(zhuǎn)移概率矩陣( )

7、ijpn記為第10頁(yè)/共44頁(yè)定義 稱(chēng)可數(shù)維的矩陣)(ijpP 為隨機(jī)矩陣，如果0,(, )1,()ijijjpi jpi顯然，0,nXn在n時(shí)的k步轉(zhuǎn)移概率矩陣)()(nkP是一隨機(jī)矩陣.特別k時(shí)，約定(0)1,00ijijijpi jS nij(0)( )I.Pn 此時(shí)為單位矩陣第11頁(yè)/共44頁(yè)實(shí)際中常會(huì)碰到具有時(shí)齊性的馬氏鏈若對(duì)任意的狀態(tài)i, j和時(shí)刻n，均有( )(1)(2)ijijijpnpnpn則稱(chēng)馬氏鏈X具有時(shí)齊性，或稱(chēng)X為其次馬爾科夫鏈，簡(jiǎn)稱(chēng)齊次馬氏鏈.第12頁(yè)/共44頁(yè) 引理(有限制隨機(jī)游動(dòng)問(wèn)題) 設(shè)質(zhì)點(diǎn)只能在0，1，2，a中的各點(diǎn)上作隨機(jī) 游動(dòng)，移動(dòng)規(guī)則如下：11,2,1

8、ia（）移動(dòng)前處; 1, 0,rqprqp0000,0,1p rprii+1i-1pqr010p0r20i （ ）移動(dòng)前處3ia（ ）移動(dòng)前處a-1aqaar,0,1aaaaq rqr第13頁(yè)/共44頁(yè)設(shè)Xn表示質(zhì)點(diǎn)在n時(shí)刻所處的位置，則其一步轉(zhuǎn)移概率矩陣為,00,1, nXnSa是以為狀態(tài)空間的齊次馬爾可夫鏈.aarqprqprqprqpr000000000000000000000000P第14頁(yè)/共44頁(yè)例(天氣預(yù)報(bào)問(wèn)題) 如果明天是否有雨僅與今天的天氣(是否有雨)有關(guān)，而與過(guò)去的天氣無(wú)關(guān). 并設(shè)今天下雨、明天有雨的概率為a，今天無(wú)雨而明天有雨的概率為b，又假設(shè)有雨稱(chēng)為0狀態(tài)天氣，無(wú)雨稱(chēng)為

9、1狀態(tài)天氣. Xn表示時(shí)刻n時(shí)的天氣狀態(tài)，則0,nXn是以1 , 0S為狀態(tài)空間的齊次馬爾可夫鏈.其一步轉(zhuǎn)移概率矩陣為bbaa11P第15頁(yè)/共44頁(yè)天氣的變化過(guò)程還可以用不同的馬爾科夫鏈來(lái)描述，假設(shè)任意一天的天氣與前一天的天氣有關(guān)，即如果昨天和今天都為晴天，明天為晴天的概率為，昨天和今天分別為晴天和陰天，明天為晴天的概率為，昨天和今天分別為陰天和晴天，明天為晴天的概率為，如果昨天和今天都為陰天，明天為晴天的概率為。如果將陰天和晴天分別記為0,10,1，則昨天和今天的所有天氣情況可以用數(shù)對(duì)表示為集合S=S=（1,11,1），（1,01,0），（0,10,1），（1,11,1） ，由此，將數(shù)對(duì)看

10、做狀態(tài)，天氣的變化過(guò)程可用狀態(tài)空間為S S上的其次馬爾科夫鏈描述，一步轉(zhuǎn)移概率矩陣為：第16頁(yè)/共44頁(yè)100001100001P第17頁(yè)/共44頁(yè)練習(xí)天氣預(yù)報(bào)問(wèn)題，其模型是：今天是否下雨依賴于前三天是否有雨（即一連三天有雨；前面兩天有雨，第三天晴天.),問(wèn)能否把這一問(wèn)題歸納為一馬爾科夫鏈，如果可以，問(wèn)該過(guò)程的狀態(tài)有幾個(gè)？如果過(guò)去一連三天有雨，今天有雨的概率為0.8；過(guò)去連續(xù)為晴天，而今天有雨的概率為0.2；在其他天氣情況，今天的天氣和昨天相同的概率為0.6，求這個(gè)馬兒科夫鏈的轉(zhuǎn)移概率.第18頁(yè)/共44頁(yè)例2 （埃倫菲斯特模型）設(shè)一個(gè)壇子中裝有m個(gè)球，它們或是紅色的，或是黑色的，從壇子中隨機(jī)的

11、摸出一球，并換入一個(gè)相反顏色的球.其一步轉(zhuǎn)移概率矩陣為01000001010000000202000001010000010mmmmmmmmmP,0nXn 是以, 1 , 0mS為狀態(tài)空間的齊次馬爾可夫鏈.設(shè)經(jīng)過(guò)n次摸換,壇中黑球數(shù)為Xn,則第19頁(yè)/共44頁(yè)例3（群體增長(zhǎng)）某種生物群體的每個(gè)個(gè)體在其生存期內(nèi)彼此獨(dú)立地產(chǎn)生后代，假設(shè)每個(gè)個(gè)體都以概率pk產(chǎn)生k個(gè)后代，且有00,(1,2,)1kkkpkp用Xn表示第n代生物群體的總數(shù)，它是生物群體的第n-1代的每個(gè)個(gè)體的后代個(gè)數(shù)的總和，因此第n+1代的個(gè)體總數(shù)僅依賴于第n代的個(gè)體總數(shù)，所以X=Xn, n=0,1,2,是一個(gè)馬爾科夫鏈，狀態(tài)空間為S

12、=0,1,2，第20頁(yè)/共44頁(yè)則馬氏鏈的一步轉(zhuǎn)移概率為：1()nnP Xj Xi如果記第n代的生物群體個(gè)數(shù)nXi記i個(gè)個(gè)體各自產(chǎn)生的后代數(shù)分別記為隨機(jī)變量 ，且 有概率分布12,i (0,1, )lli(),0,1,2lkPkpk故一步轉(zhuǎn)移概率為112()()nniP Xj XiPj第21頁(yè)/共44頁(yè)例4（卜里耶模型）設(shè)一個(gè)壇子里有b個(gè)黑球和r個(gè)紅球，每次隨機(jī)地從壇子中摸出一個(gè)球后再放回去，并加入c個(gè)與摸出球同顏色的球。重復(fù)以上步驟將摸球進(jìn)行下去，設(shè)Xn表示第n次摸球放回后壇子中的黑球數(shù)，試寫(xiě)出其一步轉(zhuǎn)移概率矩陣和狀態(tài)空間1( )(),1,0,ijnnpnP Xj Xiijicbrnciji

13、brnc 其他第22頁(yè)/共44頁(yè)例5：設(shè) 是相互獨(dú)立同分布的隨機(jī)變量序列，且:0nn(1),(1)1,0,0nnPpPppn 令隨機(jī)序列：0,0nnkkXn驗(yàn)證：隨機(jī)序列X=Xn: n0是一個(gè)齊次馬氏鏈.第23頁(yè)/共44頁(yè)例6（網(wǎng)頁(yè)瀏覽）用集合 表示因特網(wǎng)中的所有網(wǎng)頁(yè)，假設(shè)網(wǎng)頁(yè) 上的超級(jí)鏈接數(shù)為 ，對(duì)應(yīng)的網(wǎng)頁(yè)集合為 ，用戶進(jìn)入網(wǎng)頁(yè) 后，按照以下規(guī)則進(jìn)入新的網(wǎng)頁(yè)；以概率p進(jìn)入網(wǎng)頁(yè)集合S中任何一個(gè)網(wǎng)頁(yè)或者以概率q進(jìn)入 的任一個(gè)超級(jí)鏈接，令Xn表示用戶在n次選取后所在的網(wǎng)頁(yè)，問(wèn)Xn是非是一馬氏鏈，若是的話，寫(xiě)出其一步轉(zhuǎn)移概率.12=NS， ，i(1)iillN()iiS SSii+,=,jiiijj

14、iqpSlNppSN第24頁(yè)/共44頁(yè). 馬爾科夫鏈的概率分布定理 (C-K方程)()( )()( )( )(),0, ,k mkmijilljlpnpn pnkn m ki jS或矩陣形式)()()()()()(knnnmkmkPPP（解決了k步轉(zhuǎn)移概率與一步轉(zhuǎn)移概率間的關(guān)系）證明()( )k mijn k mnpnP Xj Xi ,()n kmnln kPXjliXX ,)()n k mnn klPXj XliX,)()n k mnnlkPXj XiXl 第25頁(yè)/共44頁(yè))(,)(nn k mnnn klkPXiP Xj XXlXil )()nn k mn kn klPXiPllXXj

15、X ( )()( )()kmilljlpn pnk系統(tǒng)在n 時(shí)從狀態(tài)i的出發(fā),經(jīng)過(guò)k+m步轉(zhuǎn)移,于n+k+m時(shí)到達(dá)狀態(tài)j,可以先在n時(shí)從狀態(tài)i出發(fā)，經(jīng)過(guò)k步轉(zhuǎn)移于n+k時(shí)到達(dá)某種中間狀態(tài)l,再在n+k時(shí)從中間狀態(tài)l出發(fā)經(jīng)過(guò)m步轉(zhuǎn)移于n+k+m時(shí)到達(dá)最終狀態(tài)j,而中間狀態(tài)l要取遍整個(gè)狀態(tài)空間S.C-K方程的直觀意義：第26頁(yè)/共44頁(yè)定理 馬爾可夫鏈的k 步轉(zhuǎn)移概率由其一步轉(zhuǎn)移概率 所完全確定.若取m=1,則由C-K方程的矩陣形式:)()()()()()(knnnmkmkPPP得(1)( )(1)( )( )()kknnnkPPP(1)( )(1)()knnknkPPP( )(1)(1)()nn

16、nknkPPPP分量形式11 212(1)( )( )(1)()kkkijijj jj jjjjpnpnpnpnk ( ,0)n k ( ,0, ,)n ki jS第27頁(yè)/共44頁(yè)齊次馬爾可夫鏈為方便，一般假定時(shí)間起點(diǎn)為零即對(duì)齊次馬爾可夫鏈，k步轉(zhuǎn)移概率也與起始時(shí)刻n無(wú)關(guān)記為( )kijp( )0(),0kijkpP Xj Xii jS k相應(yīng)的k步與一步轉(zhuǎn)移概率矩陣分別記為(k)PP與第28頁(yè)/共44頁(yè)例：設(shè)Xn, n0是描述天氣變化的齊次馬爾科夫鏈，狀態(tài)空間為S=0,1,其中0,1分別表示有雨和無(wú)雨，X的一步轉(zhuǎn)移概率矩陣為0.70.30.40.6P試對(duì)任意的i, jS,計(jì)算三步轉(zhuǎn)移概率(

17、3)ijp20.610.390.520.48P320.5830.4170.5560.444PPP第29頁(yè)/共44頁(yè)1）初始分布(0)0(),iqP XiiS稱(chēng)為馬爾可夫鏈的初始分布3.馬爾可夫鏈 的分布0,nXn稱(chēng) 第i個(gè)分量為)0(iq的(行)向量)0(q為馬爾可夫鏈的初始分布向量. 即)()0()0(iqq2）有限維分布定理 馬爾可夫鏈0,nXn的有限維分布由其初始分布和一步轉(zhuǎn)移概率所完全確定.證明12121, 0, , , ,nnnttt i ii iS 對(duì)第30頁(yè)/共44頁(yè)1212,ntttnP Xi XiXi12120,(),ntnittPXi XiXiiX12201,(),ntti

18、tnPXi XXiiXi12012(,)ntttniPXi XiXiXi121110200,()()()tttiXiXiPP XXiiP XiXi11110(,)nntnttnXiP XiXiXi12100121()()()tttiXiXiPP XiP Xi Xi11()nntntnP Xi Xi112111 21(0)11(0)( )().nninntttttiii iiiniqpptpt第31頁(yè)/共44頁(yè)又因?yàn)轳R爾可夫鏈的k步轉(zhuǎn)移概率由一步轉(zhuǎn)移概率所完全確定.所以馬爾可夫鏈的有限維分布由其初始分布和一步轉(zhuǎn)移概率所完全確定.第32頁(yè)/共44頁(yè)3）絕對(duì)分布( )(),0,njnqP XjnjS

19、稱(chēng)為馬爾可夫鏈 的絕對(duì)分布0,nXn稱(chēng) 第j個(gè)分量為)(njq的(行)向量)0(q為馬爾可夫鏈0,nXn的絕對(duì)分布向量. 即)()()(njnqq絕對(duì)分布、初始分布和n步轉(zhuǎn)移概率有如下關(guān)系：( )(0)( )(0)0, ,nnjiijiqqpni jS或矩陣形式)0()()0()(nnPqq第33頁(yè)/共44頁(yè)( )()njnqP Xj(0)( )(0)0, ,niijiqpni jS0(),)niPXiXj0(,)niPXi Xj0(,)niP Xi Xj00()()niP XiP Xj Xi第34頁(yè)/共44頁(yè)( )( )(0)(1),0;(2),0;(3) ,0kkkknkkXnPPqqP的

20、有限維分布由其初始分布和一步轉(zhuǎn)移概率所完全確定齊次馬氏鏈有相應(yīng)的結(jié)果第35頁(yè)/共44頁(yè)例 設(shè)0,nXn是具有三個(gè)狀態(tài)0，1，2的齊次馬爾可夫鏈，其一步轉(zhuǎn)移概率矩陣為3104411142431044P初始分布, 2 , 1 , 0,31)0(iqi試求：022(1) (0,1);(2) (1).P XXP X第36頁(yè)/共44頁(yè)解020201(0,1)(0(10)P XXP XP XX（）)(2)0113p(2)01p其中為一個(gè)兩步轉(zhuǎn)移概率，在兩步轉(zhuǎn)移概率矩陣中是第一行第二列的元素.22PP（ ）5181 65131 621 63911 611 6645(2)01516p02(0,1)P XX15

21、53 1648第37頁(yè)/共44頁(yè)(0)(2)21(2)(1)iiiP Xqp(2)(2)(2)0111211()3ppp1 519()3 162161124第38頁(yè)/共44頁(yè)例：如果將社會(huì)家庭中個(gè)體的收入分為低收入、中等收入和高收入三個(gè)等級(jí)，則早在20世紀(jì)50年代，社會(huì)學(xué)研究者發(fā)現(xiàn)個(gè)體收入的等級(jí)在很大程度上取決于其父代收入的等級(jí)。如果令Xn表示一個(gè)家庭第n代個(gè)體的收入等級(jí)，并用1,2,3分別表示低收入，中等收入和高收入，則一個(gè)家庭中相繼的后代收入等級(jí)的變化可以用其次馬爾科夫鏈來(lái)描述，狀態(tài)空間為S=1,2,3，并且有以下的轉(zhuǎn)移的概率矩陣0.650.280.070.150.670.180.120.360.52P第39頁(yè)/共44頁(yè)如果當(dāng)前收入等級(jí)為3，試分析經(jīng)過(guò)三代后個(gè)體收入等級(jí)轉(zhuǎn)變?yōu)?的可能性，進(jìn)一步分析經(jīng)過(guò)n代后個(gè)體收入等級(jí)的概率分布，并具體計(jì)算n=10時(shí)個(gè)體收入等級(jí)的概率分布。(3)3032(23)0.49P XXp(10)(10)