馬爾可夫過程

1、馬爾可夫過程神和堯一類隨機過程（數(shù)學(xué)基礎(chǔ)是隨機過程理論）。一類隨機過程（數(shù)學(xué)基礎(chǔ)是隨機過程理論）。原始模型馬爾可夫鏈，由俄國數(shù)學(xué)家原始模型馬爾可夫鏈，由俄國數(shù)學(xué)家A.A.A.A.馬爾可夫馬爾可夫于于19071907年提出。年提出。該過程具有如下特性：在已知目前狀態(tài)該過程具有如下特性：在已知目前狀態(tài) （現(xiàn)在）（現(xiàn)在）的條件下，它未來的演變的條件下，它未來的演變 （將來）不依賴于它以往（將來）不依賴于它以往的演變的演變 ( ( 過去過去 ) ) 。 例如森林中動物頭數(shù)的變化構(gòu)成例如森林中動物頭數(shù)的變化構(gòu)成馬爾可夫過馬爾可夫過程程 。在現(xiàn)實世界中，有很多過程都是馬爾可夫過程，。在現(xiàn)實世界中，有很多過

2、程都是馬爾可夫過程，如液體中微粒所作的布朗運動、傳染病受感染的人如液體中微粒所作的布朗運動、傳染病受感染的人數(shù)、車站的候車人數(shù)等，都可視為馬爾可夫過程。數(shù)、車站的候車人數(shù)等，都可視為馬爾可夫過程。馬爾可夫過程簡介馬爾可夫過程定義馬爾可夫特性馬爾可夫特性 如果一個隨機過程的概率分布函數(shù)具有以下特性如果一個隨機過程的概率分布函數(shù)具有以下特性PX(t) xn| X(tn) = xn, X(tn-1) = xn-1, , X(t0) = x0 = PX(t) x| X(tn) = xn,ttntn-1.t0則稱該隨機過程具有馬爾可夫特性。則稱該隨機過程具有馬爾可夫特性。一個具有馬爾可夫特性的隨機過程被

3、稱為馬爾可一個具有馬爾可夫特性的隨機過程被稱為馬爾可夫過程。夫過程。離散狀態(tài)空間的馬爾可夫過程也稱為馬爾可夫鏈。離散狀態(tài)空間的馬爾可夫過程也稱為馬爾可夫鏈。 值得指出的是，馬爾可夫鏈既可以是連續(xù)時間的，值得指出的是，馬爾可夫鏈既可以是連續(xù)時間的，也可以是離散時間的，它取決于系統(tǒng)參數(shù)的設(shè)定。也可以是離散時間的，它取決于系統(tǒng)參數(shù)的設(shè)定。 以離散時間的馬爾可夫鏈為例，其定義為：設(shè)一個離散以離散時間的馬爾可夫鏈為例，其定義為：設(shè)一個離散的隨機序列的隨機序列XnXn（n=1,2n=1,2，.,N.,N），若它滿足），若它滿足PXPXn+1n+1=x=xn+1n+1|X|Xn n=x=xn n，X Xn-

4、1n-1=x=xn-1n-1，.,X.,X0 0=x=x0 0=PX=PXn+1n+1=x=xn+1n+1|X|Xn n=x=xn n 則稱之為離散時間馬爾可夫鏈。則稱之為離散時間馬爾可夫鏈。馬爾可夫特性的直觀解釋為：馬爾可夫特性的直觀解釋為： 在給定在給定t t時刻隨機過程的狀態(tài)為時刻隨機過程的狀態(tài)為XnXn或或x xn n，則該過，則該過程的后續(xù)狀態(tài)及其出現(xiàn)的概率與程的后續(xù)狀態(tài)及其出現(xiàn)的概率與t t之前的狀態(tài)無關(guān)。之前的狀態(tài)無關(guān)。也就是說，過程當(dāng)前的狀態(tài)包括了過程所有的歷史也就是說，過程當(dāng)前的狀態(tài)包括了過程所有的歷史信息，該過程的進一步發(fā)展完全由當(dāng)前狀態(tài)所決定，信息，該過程的進一步發(fā)展完全

5、由當(dāng)前狀態(tài)所決定，與當(dāng)前狀態(tài)之前的歷史無關(guān)，這種性質(zhì)也稱為無后與當(dāng)前狀態(tài)之前的歷史無關(guān)，這種性質(zhì)也稱為無后效性或無記憶性。效性或無記憶性。 此特性也可以理解為：隨機過程此特性也可以理解為：隨機過程XnXn在在“現(xiàn)在現(xiàn)在”狀態(tài)已知的條件下，過程狀態(tài)已知的條件下，過程“將來將來”的情況與的情況與“過去過去”無關(guān)?；蛘哒f，過去只影響現(xiàn)在，而不影響將來。無關(guān)?；蛘哒f，過去只影響現(xiàn)在，而不影響將來。PP將來將來| |現(xiàn)在、過去現(xiàn)在、過去=P=P將來將來| |現(xiàn)在現(xiàn)在 馬爾可夫過程分類按其狀態(tài)空間按其狀態(tài)空間E E和時間參數(shù)集和時間參數(shù)集T T是連續(xù)還是離散可分成四類：是連續(xù)還是離散可分成四類：（1 1）

6、時間離散、狀態(tài)離散的馬爾可夫過程）時間離散、狀態(tài)離散的馬爾可夫過程馬爾可夫鏈。馬爾可夫鏈。 參數(shù)集參數(shù)集T=0,1,2,T=0,1,2,狀態(tài)空間狀態(tài)空間E=E=整數(shù)整數(shù) （2 2）時間連續(xù)、狀態(tài)離散的馬爾可夫過程）時間連續(xù)、狀態(tài)離散的馬爾可夫過程可列馬爾可夫過可列馬爾可夫過程、連續(xù)參數(shù)馬爾可夫鏈。程、連續(xù)參數(shù)馬爾可夫鏈。 參數(shù)集參數(shù)集T=0, ,T=0, ,狀態(tài)空間狀態(tài)空間E=E=整數(shù)整數(shù) （3 3）時間離散、狀態(tài)連續(xù)的馬爾可夫過程）時間離散、狀態(tài)連續(xù)的馬爾可夫過程馬爾可夫序列。馬爾可夫序列。 參數(shù)集參數(shù)集T= 0,1,2,T= 0,1,2,狀態(tài)空間狀態(tài)空間E= (-, +)E= (-, +)

7、（4 4）時間連續(xù)、狀態(tài)連續(xù)的馬爾可夫過程。）時間連續(xù)、狀態(tài)連續(xù)的馬爾可夫過程。 參數(shù)集參數(shù)集T= 0, ,T= 0, ,狀態(tài)空間狀態(tài)空間E= (-, +)E= (-, +) 分類分類 名稱名稱 E T離散離散連續(xù)連續(xù)離散離散（n=0,1,2,.,n)n=0,1,2,.,n)馬爾可夫鏈馬爾可夫鏈馬爾可夫序列馬爾可夫序列連續(xù)連續(xù)（n=0,1,2,.,n)n=0,1,2,.,n)可列馬爾可夫過程可列馬爾可夫過程馬爾可夫過程馬爾可夫過程表表1 1 馬爾可夫過程的分類馬爾可夫過程的分類 馬爾可夫特性要求系統(tǒng)處于任何狀態(tài)的時間分布具馬爾可夫特性要求系統(tǒng)處于任何狀態(tài)的時間分布具有無記憶性。有無記憶性。對于

8、連續(xù)型隨機變量對于連續(xù)型隨機變量X X，滿足無記憶特性的概率分布函數(shù)為：，滿足無記憶特性的概率分布函數(shù)為：PXPXt+t+|X|Xt=t=PXPX 它的密度函數(shù)為指數(shù)分布它的密度函數(shù)為指數(shù)分布f(x)=ef(x)=e-x-x 無記憶性要求在連續(xù)時間馬爾科夫鏈狀態(tài)的駐留時間為無記憶性要求在連續(xù)時間馬爾科夫鏈狀態(tài)的駐留時間為服從指數(shù)分布的隨機變量。同樣的，對于離散時間馬爾科服從指數(shù)分布的隨機變量。同樣的，對于離散時間馬爾科夫鏈，駐留時間必定是滿足幾何分布的隨機變量。夫鏈，駐留時間必定是滿足幾何分布的隨機變量。以以s s表示隨機過程在一個狀態(tài)表示隨機過程在一個狀態(tài)i i的駐留時間，則有的駐留時間，則

9、有Ps=i=pPs=i=pi-1i-1（1-p1-p）（）（i=1,2,3i=1,2,3，.） 駐留時間是檢驗隨機過程是否屬于馬爾可夫過程的駐留時間是檢驗隨機過程是否屬于馬爾可夫過程的重要標(biāo)志。重要標(biāo)志。檢驗一個隨機過程是否滿足馬爾可夫特性；檢驗一個隨機過程是否滿足馬爾可夫特性；狀態(tài)駐留時間是否是無記憶的；狀態(tài)駐留時間是否是無記憶的；過程從一個狀態(tài)到另一個狀態(tài)的概率是否僅依賴過程從一個狀態(tài)到另一個狀態(tài)的概率是否僅依賴于要離開的狀態(tài)和目的狀態(tài)。于要離開的狀態(tài)和目的狀態(tài)。馬爾可夫過程的形式化定義為：馬爾可夫過程的形式化定義為： 設(shè)設(shè)X(t),tX(t),t00是取值為是取值為E=0E=0，1 1，

10、2 2，.離散狀離散狀態(tài)空間的一個隨機過程，若對任意自然數(shù)態(tài)空間的一個隨機過程，若對任意自然數(shù)n n以及以及n n個時刻個時刻點，均有點，均有X(tX(tn n)=i)=in n|X(t|X(t1 1)=i)=i1,1,X(tX(t2 2)=i)=i2,.2,.X(tX(tn-1n-1)=i)=in-1n-1 =X(t =X(tn n)=i)=in n|X(t|X(tn-1n-1)=i)=in-1n-1 i i1 1，i,2i,2，.i.in n E 其中，其中，X(ti)=ti表示處于表示處于ti（i=1,2，.n)時刻的狀態(tài)，時刻的狀態(tài)，則稱則稱X(t),tX(t),t00為離散狀態(tài)空間為

11、離散狀態(tài)空間E E上的連續(xù)時間馬爾可上的連續(xù)時間馬爾可夫過程。夫過程。轉(zhuǎn)移概率函數(shù)轉(zhuǎn)移概率函數(shù)若對任意若對任意t t，u u00，均有，均有PX(t+u)=j|X(u)=i=PPX(t+u)=j|X(u)=i=Pijij(t) i,j(t) i,j E與與u u無關(guān)，則稱馬爾可夫過程無關(guān)，則稱馬爾可夫過程X(t),tX(t),t00是齊次的。是齊次的。即即P Pijij(t)(t)只與時間差只與時間差t t有關(guān)，而與時間起點有關(guān)，而與時間起點u u的位置無關(guān)。的位置無關(guān)。一般如不作一般如不作特別說明，馬爾可夫過程均假設(shè)是齊次的。特別說明，馬爾可夫過程均假設(shè)是齊次的。 對固定對固定i,ji,j

12、E，函數(shù)，函數(shù)P Pijij(t)(t)稱為轉(zhuǎn)移概率函數(shù)。稱為轉(zhuǎn)移概率函數(shù)。 P(T)=(PP(T)=(Pijij(t)(t)稱為轉(zhuǎn)移概率矩陣。稱為轉(zhuǎn)移概率矩陣。 此處，假定馬爾可夫過程是正則的，即有此處，假定馬爾可夫過程是正則的，即有 ,01 ()( )0 ()limi jijtijPtijijijikkjijjjkkj113)=tj jtj=tj Ek Ek EPPPPPPPPP轉(zhuǎn)移概率函數(shù)具有以下性質(zhì)：）（t) 02)（t)（u) （v)=（u+v)若令（t) PX()= ， E。它表示時刻系統(tǒng)處于狀態(tài)的概率，則有（t)（0) （)狀態(tài)轉(zhuǎn)移圖和狀態(tài)轉(zhuǎn)移率矩陣狀態(tài)轉(zhuǎn)移圖和狀態(tài)轉(zhuǎn)移率矩陣馬爾

13、可夫模型常使用狀態(tài)轉(zhuǎn)移圖來描述系統(tǒng)的運行情況。馬爾可夫模型常使用狀態(tài)轉(zhuǎn)移圖來描述系統(tǒng)的運行情況。圖1 馬爾可夫過程的狀態(tài)轉(zhuǎn)移圖修復(fù)（q）故障（p）1-p1-qSF 圖圖1 1所示為一個可修復(fù)系統(tǒng)的狀態(tài)轉(zhuǎn)移圖，系統(tǒng)所示為一個可修復(fù)系統(tǒng)的狀態(tài)轉(zhuǎn)移圖，系統(tǒng)存在存在“正常（正常（S)”S)”和和“故障（故障（F)”F)”兩種狀態(tài)。當(dāng)出兩種狀態(tài)。當(dāng)出現(xiàn)故障時，系統(tǒng)將從現(xiàn)故障時，系統(tǒng)將從“S”“S”狀態(tài)轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到“F”“F”狀態(tài)；狀態(tài)；一旦修復(fù)成功，系統(tǒng)將會由一旦修復(fù)成功，系統(tǒng)將會由“F”“F”狀態(tài)轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到“S”“S”狀態(tài)。由于這兩種狀態(tài)出現(xiàn)的概率及其持續(xù)時間具狀態(tài)。由于這兩種狀態(tài)出現(xiàn)的概率

14、及其持續(xù)時間具有隨機性，它們的轉(zhuǎn)移規(guī)律只能按照某種概率轉(zhuǎn)移。有隨機性，它們的轉(zhuǎn)移規(guī)律只能按照某種概率轉(zhuǎn)移。圖圖1 1中中p p、q q為狀態(tài)的轉(zhuǎn)移概率。顯然，為狀態(tài)的轉(zhuǎn)移概率。顯然，0 0 p 1,0 q 1。根據(jù)上述分析，還可以得到系統(tǒng)狀態(tài)的轉(zhuǎn)移率矩陣：根據(jù)上述分析，還可以得到系統(tǒng)狀態(tài)的轉(zhuǎn)移率矩陣：11ppAqq 系統(tǒng)經(jīng)過多次轉(zhuǎn)移后，通常會達到一個與時間系統(tǒng)經(jīng)過多次轉(zhuǎn)移后，通常會達到一個與時間無關(guān)的穩(wěn)定狀態(tài)。此時，系統(tǒng)在狀態(tài)轉(zhuǎn)移過程中，無關(guān)的穩(wěn)定狀態(tài)。此時，系統(tǒng)在狀態(tài)轉(zhuǎn)移過程中，在各狀態(tài)逗留的概率不再發(fā)生變化。求解系統(tǒng)處于在各狀態(tài)逗留的概率不再發(fā)生變化。求解系統(tǒng)處于各種狀態(tài)的穩(wěn)態(tài)概率是研究離

15、散事件系統(tǒng)特性的重各種狀態(tài)的穩(wěn)態(tài)概率是研究離散事件系統(tǒng)特性的重要手段。要手段。穩(wěn)態(tài)概率及其求法穩(wěn)態(tài)概率及其求法 系統(tǒng)在各狀態(tài)的穩(wěn)定概率通常有以下兩種解法：系統(tǒng)在各狀態(tài)的穩(wěn)定概率通常有以下兩種解法：已知瞬態(tài)概率，求極限已知瞬態(tài)概率，求極限lim S (t)iitAP式中式中 S Si i（t t）-系統(tǒng)系統(tǒng)i i狀態(tài)的瞬態(tài)概率；狀態(tài)的瞬態(tài)概率； A Ai i-i-i狀態(tài)的穩(wěn)態(tài)概率。狀態(tài)的穩(wěn)態(tài)概率。同構(gòu)法同構(gòu)法 當(dāng)系統(tǒng)達到穩(wěn)定狀態(tài)以后，各種狀態(tài)將持續(xù)轉(zhuǎn)當(dāng)系統(tǒng)達到穩(wěn)定狀態(tài)以后，各種狀態(tài)將持續(xù)轉(zhuǎn)移，但是每種狀態(tài)出現(xiàn)的概率基本不變，從而形成移，但是每種狀態(tài)出現(xiàn)的概率基本不變，從而形成一個穩(wěn)定的狀態(tài)空間。

16、求解狀態(tài)空間方程組，就可一個穩(wěn)定的狀態(tài)空間。求解狀態(tài)空間方程組，就可得到系統(tǒng)在各種狀態(tài)的穩(wěn)態(tài)概率。得到系統(tǒng)在各種狀態(tài)的穩(wěn)態(tài)概率。 通常，穩(wěn)態(tài)概率空間的表達式不易求出，該解通常，穩(wěn)態(tài)概率空間的表達式不易求出，該解法適合于解決一些比較簡單系統(tǒng)的穩(wěn)態(tài)狀態(tài)概率問法適合于解決一些比較簡單系統(tǒng)的穩(wěn)態(tài)狀態(tài)概率問題。題。例例1 1 以圖以圖1 1所示模型為例，求解穩(wěn)態(tài)概率。所示模型為例，求解穩(wěn)態(tài)概率。圖1 馬爾可夫過程的狀態(tài)轉(zhuǎn)移圖修復(fù)（q）故障（p）1-p1-qS（1）F（2）設(shè)系統(tǒng)處于正常狀態(tài)的穩(wěn)態(tài)概率為設(shè)系統(tǒng)處于正常狀態(tài)的穩(wěn)態(tài)概率為1 1和處于故障狀和處于故障狀態(tài)的穩(wěn)態(tài)概率為態(tài)的穩(wěn)態(tài)概率為2 2，則有，則

17、有11222112(1)(1)1pqqp 顯然，前兩個方程是線性相關(guān)的，可以刪掉一個。解顯然，前兩個方程是線性相關(guān)的，可以刪掉一個。解方程組得：方程組得：12qpqppq例例2 2 設(shè)任意相繼的兩天中，雨天轉(zhuǎn)晴天的概率為設(shè)任意相繼的兩天中，雨天轉(zhuǎn)晴天的概率為1/31/3，晴天轉(zhuǎn)雨天的概率為晴天轉(zhuǎn)雨天的概率為1/21/2，任一天晴或雨是互為逆事件。，任一天晴或雨是互為逆事件。以以0 0表示晴天狀態(tài)，以表示晴天狀態(tài)，以1 1表示雨天狀態(tài)，表示雨天狀態(tài)，XnXn表示第表示第n n天狀天狀態(tài)（態(tài)（0 0或或1 1）。又已知）。又已知5 5月月1 1日為晴天，問日為晴天，問5 5月月3 3日為晴天，日為

18、晴天，5 5月月5 5日為雨天的概率各等于多少？日為雨天的概率各等于多少？解：分析解：分析分析狀態(tài)轉(zhuǎn)移過程，求出系統(tǒng)狀態(tài)轉(zhuǎn)移率矩陣；分析狀態(tài)轉(zhuǎn)移過程，求出系統(tǒng)狀態(tài)轉(zhuǎn)移率矩陣；確定某狀態(tài)下的轉(zhuǎn)移概率矩陣；確定某狀態(tài)下的轉(zhuǎn)移概率矩陣；求解。求解。晴轉(zhuǎn)雨（1/2）1-1/21-1/3晴天晴天雨天雨天雨轉(zhuǎn)晴（1/3）狀態(tài)轉(zhuǎn)移圖：狀態(tài)轉(zhuǎn)移圖：111112222111213333A得到系統(tǒng)狀態(tài)轉(zhuǎn)移率矩陣為：得到系統(tǒng)狀態(tài)轉(zhuǎn)移率矩陣為：則則5 5月月2 2日狀態(tài)轉(zhuǎn)移概率矩陣為：日狀態(tài)轉(zhuǎn)移概率矩陣為：1111221010122233A1111115722122222121233A則則5 5月月3 3日狀態(tài)轉(zhuǎn)移概率矩陣為：日狀態(tài)轉(zhuǎn)移概率矩陣為：因此因此5 5月月3 3日為晴天的概率為日為晴天的概率為5/125/12。由以上求解由以上求解5 5月月3