隨機過程第5講(馬爾科夫鏈定義和性質(zhì)).ppt

1、隨機過程及其應(yīng)用 離散時間Markov鏈,第5講,2020/11/7,鄭州大學(xué)信息工程學(xué)院,1,內(nèi)容提要,離散時間Markov鏈的定義、性質(zhì) 離散時間Markov鏈舉例,2020/11/7,鄭州大學(xué)信息工程學(xué)院,2,安德雷.安德耶維奇.馬爾可夫(A.A.Markov): 俄數(shù)學(xué)家，18561922 概率和統(tǒng)計領(lǐng)域?qū)＜摇?當年Markov研究普希金詩歌里元音字母和輔音字母交替出現(xiàn)的規(guī)律時提出了Markov過程的數(shù)學(xué)模型 Markov過程80年代興起，在現(xiàn)代工程、自然科學(xué)、社會科學(xué)中應(yīng)用廣泛。,2020/11/7,鄭州大學(xué)信息工程學(xué)院,3,1、馬爾可夫過程定義,定義：設(shè)有一隨機過程(t),tT,t

2、1t2t3tmtm+1 T，若在t1、t2、t3、tm、tm+1 時對(t)觀測得到相應(yīng)的觀測值x1,x2,x3,xm,xm+1滿足條件： 則稱這類過程為具有馬爾可夫性質(zhì)的隨機過程或馬爾可夫過程,2020/11/7,鄭州大學(xué)信息工程學(xué)院,4,Markov過程也可表示為如下形式：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,5,2020/11/7,鄭州大學(xué)信息工程學(xué)院,6,該式表明(t)的n維概率密度等于一些條件概率密度與t1時初始概率密度的乘積。這些條件概率密度稱為轉(zhuǎn)移概率密度。,馬爾可夫過程(t),tT可能取的值的全體組成過程的狀態(tài)空間， (t)可能取的值稱為狀態(tài)。 (t)=x代表在 t 時刻

3、過程（或系統(tǒng)）處在狀態(tài)x 。馬爾可夫過程的狀態(tài)空間可以是連續(xù)的，也可以是離散的。馬爾可夫過程的參數(shù)t可以是連續(xù)的，也可以是離散的。 Markov過程的分類 Markov鏈：狀態(tài)值可數(shù)離散的Markov過程 離散時間Markov鏈（第二章） 連續(xù)時間Markov鏈（第三章）,2020/11/7,鄭州大學(xué)信息工程學(xué)院,7,馬爾可夫鏈的定義,(n),n=0,1,2,是離散狀態(tài)（狀態(tài)空間為I）、參數(shù)為非負整數(shù)的隨機過程，且(n)滿足條件： 即在參數(shù)n=0,1,2,n，狀態(tài)取(0)=i0, (1)=i1, (n-1)=in-1, (n)=i的條件下， (n+1)=j的條件概率與(0), (1) , (n

4、-1)無關(guān)而僅與(n)所取的值有關(guān)，把這類隨機過程成為馬爾可夫鏈,2020/11/7,鄭州大學(xué)信息工程學(xué)院,8,由定義可知：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,9,一步轉(zhuǎn)移概率的兩個性質(zhì)：,（1） （2）,2020/11/7,鄭州大學(xué)信息工程學(xué)院,10,齊次馬爾可夫鏈,定義：如果在馬爾可夫鏈中 即從狀態(tài)轉(zhuǎn)移到狀態(tài)的概率與無關(guān)，則稱這類馬爾可夫鏈為齊次馬爾可夫鏈。 設(shè)代表一步轉(zhuǎn)移概率pij所組成的矩陣，且狀態(tài)空間由狀態(tài)，所組成，則,2020/11/7,鄭州大學(xué)信息工程學(xué)院,11,一步轉(zhuǎn)移概率矩陣P中每個元素為非負，每行之和均為1。,2、 切普曼-柯爾莫哥洛夫方程式（C-K方程）,m步轉(zhuǎn)移

5、概率 : 性質(zhì)： m=1時即一步轉(zhuǎn)移概率，m=0時規(guī)定：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,12,對于m步轉(zhuǎn)移概率矩陣有C-K方程：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,13,證明：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,14,這一事件可分解成:,件的和事件,如下圖所示:,C-K方程是指(n)在n時處于狀態(tài)i的條件下經(jīng)過m+r步轉(zhuǎn)移與n+m+r時到達狀態(tài)j，可以先在n時從狀態(tài)i出發(fā)，經(jīng)過m步于n+m時到達某種中間狀態(tài)k，再在n+m時從狀態(tài)k出發(fā)經(jīng)過r步轉(zhuǎn)移于n+m+r時到達最終狀態(tài)j，而中間狀態(tài)k要取遍整個狀態(tài)空間。 C-K方程也可以用矩陣形式表示： r=1時,可得： 一直推

6、下去可得： 結(jié)論：馬爾可夫鏈的m步轉(zhuǎn)移概率由一步轉(zhuǎn)移概率所完全決定,2020/11/7,鄭州大學(xué)信息工程學(xué)院,15,馬爾可夫鏈的分布：,（1）初始分布 稱 , iI為馬氏鏈的初始分布 （2）有限維分布 定理：馬爾可夫鏈的有限維分布由其初始分布和一步轉(zhuǎn)移概率所完全確定。,2020/11/7,鄭州大學(xué)信息工程學(xué)院,16,轉(zhuǎn)移概率決定了馬氏鏈的運動的統(tǒng)計規(guī)律。 因此, 確定馬氏鏈的任意n步轉(zhuǎn)移概率成為馬氏鏈理論中的重要問題之一。,證明：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,17,馬爾可夫鏈的例子,例：天氣預(yù)報問題 如果明天是否有雨僅與今天的天氣（是否有雨）有關(guān)，而與過去的天氣無關(guān)，并設(shè)今日下雨

7、，明日有雨的概率為，今日無雨明日有雨的概率為，又假定把有雨稱為狀態(tài)天氣，把無雨稱為狀態(tài)天氣； (n)表示n時的狀態(tài)天氣，則(n)是以0，1為狀態(tài)空間的齊次馬爾可夫鏈，它的一步轉(zhuǎn)移矩陣為 ：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,18,設(shè)=0.7， =0.4，則一步轉(zhuǎn)移概率矩陣為,2020/11/7,鄭州大學(xué)信息工程學(xué)院,19,四步轉(zhuǎn)移概率矩陣：,由此可知，今日有雨且第四日仍有雨的概率為：P00(4)=0.5749,則兩步轉(zhuǎn)移概率矩陣：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,20,例,解,(1)先求出2步轉(zhuǎn)移概率矩陣:,2020/11/7,鄭州大學(xué)信息工程學(xué)院,21,例 一維隨機游動,游

8、動的概率規(guī)則,如果Q現(xiàn)在位于點 i (1 i 5),則下一時刻各以1/3的概率向左或向右移動一格, 或以1/3的概率留在原處;,2020/11/7,鄭州大學(xué)信息工程學(xué)院,22,如果Q現(xiàn)在位于1(或5)這點上, 則下一時刻就以概率1移動到2(或4)這一點上. 1和5這兩點稱為反射壁.,上面這種游動稱為帶有兩個反射壁的隨機游動.,模擬方法:產(chǎn)生均勻分布的隨機數(shù)序其中1表示左移;2表示不動;3表示右移.,2020/11/7,鄭州大學(xué)信息工程學(xué)院,23,理論分析:,狀態(tài)空間是I.,而與時刻 n 以前所處的狀態(tài)無關(guān).,所以它是一個馬氏鏈, 且是齊次的.,2020/11/7,鄭州

9、大學(xué)信息工程學(xué)院,24,一步轉(zhuǎn)移概率,2020/11/7,鄭州大學(xué)信息工程學(xué)院,25,一步轉(zhuǎn)移概率矩陣,說明:改變游動的概率規(guī)則, 就可得到不同方式的,隨機游動和相應(yīng)的馬氏鏈. 如果把點 1 改為吸收壁,相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把P 中第1行改為,例：無限制隨機游動問題 質(zhì)點在直線上做隨機游動。如某一時刻質(zhì)點位于，則下一步質(zhì)點以概率向右移動一格到達?；蛞愿怕氏蜃笠埔桓竦竭_。若以(n) 表示時刻時質(zhì)點的位置，則(n),n=0,1,2,是一個隨機過程。而且當(n) =i時， (n+1), (n+2), (n+k),等時刻后質(zhì)點所處的狀態(tài)只與 (n)=i有關(guān)，而與質(zhì)點在以前是如何到達的完全無關(guān)。所以

10、它是一個齊次馬爾可夫鏈，其狀態(tài)空間為I: ,-2,-1,0,1,2, 而其一步轉(zhuǎn)移概率為：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,26,下面求它的步轉(zhuǎn)移概率pij(n)。已知每次轉(zhuǎn)移只有兩種可能，向左的概率為，向右的概率為，而次轉(zhuǎn)移的結(jié)果是從到。如果次轉(zhuǎn)移中向右m1次，向左m2次，則,2020/11/7,鄭州大學(xué)信息工程學(xué)院,27,例：有限制的隨機游動問題（帶有兩個吸收壁的隨機游動）,2020/11/7,鄭州大學(xué)信息工程學(xué)院,28,隨機游動的狀態(tài)空間為I：0，1，2， a，0、 a 兩狀態(tài)為吸收態(tài)。該過程仍是齊次馬爾可夫鏈，它的一步轉(zhuǎn)移概率矩陣為,例：賭徒輸光問題,兩個賭徒甲、乙進行一系列

11、賭博。在每一局中甲獲勝的概率為p ，乙獲勝的概率為q，p+q=1，每一局后，負者要付一元給勝者。如果起始時甲有資本a 元，乙有資本b 元，a+b=c元，兩人賭博直到甲輸光或乙輸光為止，求甲輸光的概率。 這個問題實質(zhì)上是帶有兩個吸收壁的隨機游動。這時的狀態(tài)空間為0，1，2，, c , c=a+b, a1,b 1?，F(xiàn)在的問題是求質(zhì)點從a 點出發(fā)到達0狀態(tài)先于到達c 狀態(tài)概率。,2020/11/7,鄭州大學(xué)信息工程學(xué)院,29,解 :設(shè)0jc，設(shè)uj為質(zhì)點從j 出發(fā)到達0狀態(tài)先于到達c狀態(tài)的概率。根據(jù)全概率公式有:,考慮質(zhì)點從j出發(fā)移動一步后的情況。在以概率p移到j(luò)+1的假設(shè)下，到達0狀態(tài)先于到達 c

12、狀態(tài)的概率為uj+1 。同理，在以概率q移到j(luò)-1的前提下，到達0先于到達c的概率為uj-1。利用全概率定理就可以得到上述方程。這一方程實質(zhì)上是一差分方程，它的邊界條件是:,2020/11/7,鄭州大學(xué)信息工程學(xué)院,30,2020/11/7,鄭州大學(xué)信息工程學(xué)院,31,因此：,2020/11/7,鄭州大學(xué)信息工程學(xué)院,32,故,當r=1時 u0-uc=1=cd0 而 uj=(c-j)d0 因此,故,由以上計算結(jié)果可知，當r1即p q時，甲先輸光的概率為,2020/11/7,鄭州大學(xué)信息工程學(xué)院,33,當r=1即p=q時，甲先輸光的概率為b/c 用同樣的方法可以求得乙先輸光的概率。當p q時，乙

13、先輸光的概率為 當p=q時，乙先輸光的概率為a/c,2020/11/7,鄭州大學(xué)信息工程學(xué)院,34,例,2020/11/7,鄭州大學(xué)信息工程學(xué)院,35,解,2020/11/7,鄭州大學(xué)信息工程學(xué)院,36,概率為,2020/11/7,鄭州大學(xué)信息工程學(xué)院,37,某計算機房的一臺計算機經(jīng)常出故障,研究者 每隔15分鐘觀察一次計算機運行狀態(tài),收集了24小 時的數(shù)據(jù) (共作97次觀察) . 用1表示正常狀態(tài), 用0 表示不正常狀態(tài), 所得的數(shù)據(jù)序列如下:,1110010011111110011110111111001111111110001101101,111011011010111101110111

14、101111110011011111100111,分析,狀態(tài)空間: I=0, 1.,例,2020/11/7,鄭州大學(xué)信息工程學(xué)院,38,96 次狀態(tài)轉(zhuǎn)移的情況:,因此, 一步轉(zhuǎn)移概率可用頻率近似地表示為:,有些問題雖然不是馬爾可夫鏈，但經(jīng)過某些處理，仍可以把它看作馬爾可夫鏈。 例：在天氣預(yù)報問題中，認為今日是否下雨依賴于前兩天的天氣狀況，并規(guī)定：昨日、今日都下雨，明日有雨的概率為0.7，今日有雨、昨日無雨，明日有雨的概率為0.5；昨日有雨、今日無雨，明日有雨的概率為0.4；昨日、今日均無雨，明日有雨的概率為0.2。該問題不是馬爾可夫鏈。但是，經(jīng)過如下處理卻可以把它看作馬爾可夫鏈。,2020/11/7,鄭州大學(xué)信息工程學(xué)院,39,設(shè)昨日、今日連續(xù)兩天有雨稱為狀態(tài)0(RR)，昨日無雨、今日有雨稱為狀態(tài)1(NR)，昨日有雨、今日無雨稱為狀態(tài)2(RN)，昨日、今日均無雨稱為狀態(tài)3(NN)，于是形成了四個狀態(tài)