1、馬爾可夫過程,一、馬爾可夫過程的概念,當(dāng)已知隨機過程在時刻 所處的狀態(tài)的條件下，過程在時刻 所處的狀態(tài)與過程在時刻 以前的狀態(tài)無關(guān)，而僅與過程在 所處的狀態(tài)有關(guān)，則稱該過程為馬爾可夫過程。這種特性稱為隨機過程的“無后效性”或馬爾可夫性。,分為四類： 1 T和E都取連續(xù)集時，稱為馬爾可夫過程。 2 若T取連續(xù)集而E取離散集時，稱為可列馬爾可夫過程。 3 若T取離散集而E取連續(xù)集時，稱為馬爾可夫序列。 4 若T和E都取離散集時，稱為馬爾可夫鏈。狀態(tài)可列的馬爾可夫鏈稱為可列馬爾可夫鏈；狀態(tài)有限的馬爾可夫鏈稱為有限馬爾可夫鏈。,馬爾可夫序列,一、馬爾可夫序列的定義,設(shè) 表示隨機過程 在 為整數(shù)時刻的取

2、樣的隨機序列，記為 （ 簡記為 或 ），則可按以下方式定義馬爾可夫序列。 定義33：若對于任意的n，有 則稱此 為馬爾可夫序列。這一概率密度函數(shù)稱為轉(zhuǎn)移概率密度函數(shù)。 可以推出 即聯(lián)合概率密度函數(shù)可由轉(zhuǎn)移概率密度和起始時刻的一維概率密度來確定。,二、馬爾可夫序列的性質(zhì),一個馬爾可夫序列的子序列仍為馬爾可夫序列。,證：對于馬爾可夫序列,2、 一個馬爾可夫序列按其相反方向組成的逆序列仍為馬爾可夫序列。即對于任意的整數(shù)n和k,有,證：因為,同理,根據(jù)條件概率定義和以上兩式有,所以,3 若,，并在給定,條件下，隨機變量,與,是獨立的，則有,證：因為,所以原結(jié)論成立。 證畢,4、 如果條件概率密度,與,

3、5、 如果一個馬爾可夫序列是齊次的，并且所有的隨機變量,具有相同的概率密度，則稱該馬爾可夫序列是平穩(wěn)的。,馬爾可夫序列的轉(zhuǎn)移概率滿足,此式就是有名的切普曼柯爾莫哥洛夫方程（C-K方程）。,無關(guān)，則稱該馬爾可夫序列,6、 對于,是齊次的。,三、馬爾可夫鏈,1、馬爾可夫鏈的定義,為一隨機序列，其狀態(tài)空間,，若對于任意的,，滿足,則稱,為馬爾可夫鏈（簡稱馬氏鏈）。,定義：設(shè),2、馬爾可夫鏈的轉(zhuǎn)移概率及性質(zhì),一步轉(zhuǎn)移概率 在齊次條件下，令式（1.6.9）中,時，有,稱為一步轉(zhuǎn)移概率。由所有一步轉(zhuǎn)移概率,構(gòu)成的矩陣,稱為一步轉(zhuǎn)移概率矩陣，簡稱轉(zhuǎn)移概率矩陣。,（1）,（2）,（一）,（二）n步轉(zhuǎn)移概率,在

4、齊次條件下，,時，可得到,步轉(zhuǎn)移概率,可構(gòu)成,n步轉(zhuǎn)移概率矩陣,由所有n步轉(zhuǎn)移概率,（1）,（2）,為了數(shù)學(xué)處理便利，通常規(guī)定,3切普曼-柯爾莫哥洛夫方程（C-K方程）,對于 步轉(zhuǎn)移概率，有如下的切普曼-柯爾莫哥洛夫方程的離散形式,若用概率矩陣表示，有,當(dāng),時，有,同理可推出，當(dāng),時，有,即任意 k 步轉(zhuǎn)移概率矩陣可由一步轉(zhuǎn)移概率矩陣自乘 k 次來得到。,例2-1 在某數(shù)字通信系統(tǒng)中多級傳輸0、1兩種數(shù)字信號。由于系統(tǒng)中存在干擾，在任一級輸入0、1數(shù)字信號后，其輸出不產(chǎn)生錯誤的概率為p，產(chǎn)生錯誤的概率為q=1-p ，求兩級傳輸時的概率轉(zhuǎn)移矩陣。,解：系統(tǒng)每一級的輸入狀態(tài)和輸出狀態(tài)構(gòu)成一個兩狀態(tài)

5、的馬氏鏈，其一步轉(zhuǎn)移概率矩陣為,于是，兩級傳輸時的概率轉(zhuǎn)移矩陣等效于兩步轉(zhuǎn)移概率矩陣為,4初始分布與絕對分布,定義 設(shè),為一馬氏鏈，其狀態(tài)空間,或為有限子集。令,，且對任意的,（1）,（2）,則稱 為該馬氏鏈的初始分布，也稱初始概率。初始概率是馬氏鏈在初始時間 時處于狀態(tài),i的概率。,當(dāng) 時，馬氏鏈處于狀態(tài)i的概率稱為絕對概率或絕對分布。,，均有,定義36 設(shè),為一馬氏鏈，其狀態(tài)空間,或為有限子集。令,，且對任意的,（1）,（2）,則稱 為該馬氏鏈的絕對分布，也稱絕對概率。,均有,定理3 馬氏鏈的絕對概率由初始分布和相應(yīng)的轉(zhuǎn)移概率唯一確定。,為一馬氏鏈，,為狀態(tài)集，則對任意,時馬氏鏈處于狀態(tài),

6、的概率為,即:,時,絕對概率,由初始概率,及一步轉(zhuǎn)移概率,唯一確定。,時，絕對概率由下式確定：,即:絕對概率 由初始概率 及n步轉(zhuǎn)移概率 唯一確定。,利用C-K方程，則n步轉(zhuǎn)移矩陣可由一步轉(zhuǎn)移矩陣唯一確定。,證：設(shè),當(dāng),由馬氏鏈的轉(zhuǎn)移概率和初始分布，不僅可以完全確定其絕對分布，也可以完全確定其有限維分布。,5、 馬爾科夫鏈的有限維分布,四、馬爾科夫鏈中的狀態(tài)分類,可達(dá)與相通 定義（可達(dá)定義）：如果對于狀態(tài) 與 ，總存在某個 使得 ，則稱自 i 狀態(tài)經(jīng)過 n 步可以到達(dá) j 狀態(tài)，并記為,反之，若對所有的 有 ，則稱自 i 狀態(tài)不可以到達(dá) j 狀態(tài)，并記為,可達(dá)具有傳遞性，即若 , ,則,定義（

7、相通或互達(dá)定義）：若自狀態(tài) i 可達(dá)狀態(tài) j，同時自狀態(tài) j 也可達(dá)狀態(tài) i，則稱狀態(tài) i 和狀態(tài) j 相通，記為,相通具有以下等價關(guān)系：,（1） ,自返性,（2）若 ，則 ，對稱性,（3）若 ， ，則 ，傳遞性,例2 設(shè)一兩狀態(tài) 的馬氏鏈具有以下轉(zhuǎn)移概率矩陣,解：要討論這一馬氏鏈兩個狀態(tài)的到達(dá)性，可先求出它的n步轉(zhuǎn)移概率矩陣。由于,對于所有的 n, ，故狀態(tài)“1”不能到達(dá)狀態(tài)“0”；,而存在n，使得 ， 故狀態(tài)“0”可以到達(dá)狀態(tài)“1”。,討論其狀態(tài)的可達(dá)性。,2狀態(tài)的分類,定義1 設(shè) 為一馬氏鏈，對任一狀態(tài)i與j，稱,為 自狀態(tài) i 出發(fā)首次進(jìn)入狀態(tài) j 的時刻，或稱為自 i到 j 的首達(dá)時

8、間。,是一隨機變量。,定義2 (首達(dá)概率)設(shè) 為一馬氏鏈，對任一狀態(tài)i與j，稱,為 自狀態(tài)i出發(fā)經(jīng)過n步首次到達(dá)狀態(tài)j的概率。,顯然有,從而,定義3 設(shè) 為一馬氏鏈，對任一狀態(tài)i與j，稱,為 自狀態(tài)i出發(fā)遲早要到達(dá)狀態(tài)j的概率。,顯然有,定理4 對任何狀態(tài),， 有,證明：因為,定義4 如果 ，則稱狀態(tài)j是常返的。如果 ，則稱狀 態(tài)j是非常返的（或稱為瞬時的）。如果馬爾可夫鏈的任一狀態(tài)都是常返的，則稱此鏈為常返馬爾可夫鏈。,定理5,的充要條件是,證明：充分性：若 ，則根據(jù)到達(dá)的定義，總存在某個 ，使,所以,這樣 ，至少有一個為正（不為0），,必要性：若,，則由,至少有一個,使,，故,表示自狀態(tài)

9、i 出發(fā)，在有限步內(nèi)遲早要返回狀態(tài) i 的概率， 是在0與1之間的一個數(shù)。,所以,定理6 狀態(tài)i為常返（ ）的充要條件為,證明：充分性：因為,有,所以,現(xiàn)已知,，則上式左邊極限為1，于是有,狀態(tài)j是常返態(tài)。,令,從而,狀態(tài)i為非常返（ ）時,如果狀態(tài)j是非常返的，則必有,設(shè)i是一常返態(tài)，則從i出發(fā)可經(jīng)過n 步首次返回i， 在 的條件下的分布列為,由數(shù)學(xué)期望的定義，可得,稱 為狀態(tài) i 的平均返回時間。,狀態(tài) 的平均返回時間,定義 設(shè) i 是常返態(tài)，如果 ，則稱狀態(tài) i 是正常返態(tài)；如果 ，則稱狀態(tài) i 是零常返態(tài)。,定理7 設(shè) j 為常返狀態(tài)，有周期 ,則,如果 j 是常返態(tài)，則,（1）,j

10、零常返當(dāng)且僅當(dāng),（2）j 遍歷當(dāng)且僅當(dāng),定義 對于狀態(tài) i ，若正整數(shù)集合 非空，則稱該集合的最大公約數(shù) L 為狀態(tài) i 的周期。若 ，則稱狀態(tài) i 是周期的，若 ，則稱狀態(tài) i 是非周期的。如果狀態(tài) i 是非周期且正常返的，則稱狀態(tài) i 是遍歷的。,馬氏狀態(tài)分類圖,狀態(tài)分類判別法：,（1） i非常返,（2）i零常返,且,且,（4）i遍歷,且,（3）i正常返,引理1 對任意i和j，若 ，則存在正數(shù) 、及正整數(shù)l、m，使對任一正整數(shù)n，有,、,定理8 若 ，則 （1）i與j同為常返或同為非常返； （2）若i與j常返，則i與j同為正常返或同為零常返； （3）i與j或同為非周期的，或同為周期的且有相

11、同的周期。,3遍歷性與平穩(wěn)分布,定義45：設(shè)齊次馬氏鏈 的狀態(tài)空間為E，若對一切 ，存在不依賴于i的極限,則稱馬爾可夫鏈具有遍歷性。并 稱為狀態(tài)j的穩(wěn)態(tài)概率。,定理9 對于一有限狀態(tài)的馬氏鏈 ，若存在一正整數(shù)m，使,（對所有的狀態(tài) ）,則此鏈?zhǔn)潜闅v性的，且 是,的滿足條件 的唯一解。,對平穩(wěn)分布 ，有,=,一個非周期，不可約的馬氏鏈?zhǔn)浅７档?，它存在一個平穩(wěn)分布 ，即 ，即平穩(wěn)分布就是極限分布。,遍歷的馬氏鏈一定具有平穩(wěn)性，但平穩(wěn)的馬氏鏈不一定具有遍歷性（不遍歷的馬氏鏈也可具有平穩(wěn)性）。,例1-23設(shè)馬爾可夫鏈的狀態(tài)空間 ，一步轉(zhuǎn)移概率矩陣,試對該鏈進(jìn)行分類，并說明其遍歷性。,解：根據(jù)一步轉(zhuǎn)移概

12、率矩陣可畫出如圖1-12所示的狀態(tài)轉(zhuǎn)移圖。從圖中可知，和都是非周期的正常返狀態(tài)，、 狀態(tài)都是非常返狀態(tài)。,由于,說明 存在（i=1,2,3,4）,但與i有關(guān)，所以該鏈不是遍歷的。,五、狀態(tài)空間分解,定義46 設(shè) ，若從V中任一狀態(tài)出發(fā)不能到達(dá)V外的任一狀態(tài)，則稱V為閉集。,顯然，對一切 和 有,若中僅含有單個狀態(tài)，則此閉集稱為吸收態(tài)。它構(gòu)成了一個較小的閉集。而整個空間構(gòu)成一個較大的閉集。除了整個狀態(tài)空間外，沒有別的閉集的馬爾可夫鏈稱為不可約的馬爾可夫鏈。此時整個空間的所有狀態(tài)皆是相通的。閉集內(nèi)任一狀態(tài)，不論轉(zhuǎn)移多少步，都不能轉(zhuǎn)移到閉集之外的狀態(tài)上去，即隨著時間的推移，閉集內(nèi)任一狀態(tài)只能在閉集內(nèi)

13、部的狀態(tài)之間轉(zhuǎn)移。,定理10 馬爾可夫鏈的所有常返狀態(tài)構(gòu)成的集合是一閉集。,定理11 （分解定理）狀態(tài)空間E必可分解為 其中N是全體非常返態(tài)組成的集合， 是互不相交的常返態(tài)閉集組成。而且,（1）對每一確定的k, 內(nèi)任意兩狀態(tài)相通；,（2） 與 ( )中的狀態(tài)之間不相通；,例1-25 設(shè)齊次馬氏鏈 的狀態(tài)空間 ，其一步轉(zhuǎn)移概率矩陣為,試對該空間進(jìn)行分解。,解：根據(jù)一步轉(zhuǎn)移概率矩陣，可畫出如圖所示的狀態(tài)轉(zhuǎn)移圖。,由圖可知， ，而當(dāng) 時， ，所以 ， 可見狀態(tài)1為正常返，且周期 。含有狀態(tài)1的常返閉集為,同理，因為 ， ，在 時， ，所以,可見狀態(tài)6為正常返，且是非周期的。含有狀態(tài)6的常返閉集為,狀

14、態(tài)2，6為遍歷狀態(tài).,由于 ，在 時， ，所以 。可見狀態(tài)4為非常返。,故,1.7 泊松過程,獨立增量過程,設(shè)有一個隨機過程 ，如果對任意時刻 ，過程的增量 、 、 是相互獨立的隨機變量，則稱 為獨立增量過程，又稱為可加過程。,泊松過程,設(shè)隨機過程 ， ，其狀態(tài)只取非負(fù)整數(shù)值，若滿足下列三個條件：,（2） 為均勻獨立增量過程；,（1）,（3）對任意時刻 ， ，相應(yīng)的隨機變量的增量服從數(shù)學(xué)期望為 的泊松分布，即對于k=0,1,2,.,有,其中， 則稱 為泊松過程。,一、泊松過程的一般概念,泊松過程 滿足如下條件：,（1）對于任意時刻,，出現(xiàn)事件次數(shù),是相互獨立的；,（2）對于充分小的,，在,內(nèi)出

15、現(xiàn)時間一次的概率為,其中,是在,時關(guān)于,的高階無窮小量；常數(shù),，,稱為過程 的強度；,（3）對于充分小的,，在,內(nèi)出現(xiàn)事件兩次及兩次以上的概率為,這就是說，一個隨機過程 如果能滿足上述三個條件，則它為泊松過程。,圖1-14（a）給出了泊松過程,的示意圖。由圖可見，泊松過程,的每一個樣本函數(shù),都呈階梯形，它在每個隨機點,的階躍（即：步長為“1”）。對于給定的,，,等于在時間間隔,隨機點數(shù)。如果用計數(shù)器記錄各隨機時刻,射出的電子數(shù)目，則在時刻,，計數(shù)器的指示數(shù)即為,。,處產(chǎn)生單位為“1”,內(nèi)的,圖1-14 （a）泊松過程得示意圖；（b）泊松增量；（c）泊松沖激序列,二、泊松過程的統(tǒng)計量,對于給定的

16、時刻,和,，且,，式（1.7.1）可改寫成,先來討論服從泊松分布的隨機變量,及,的數(shù)學(xué)期望，方差和相關(guān)函數(shù)等統(tǒng)計量。,1數(shù)學(xué)期望 令,，因此，均值為,=,2. 均方值與方差 令 ，故均方值為,=,而方差為,=,3.相關(guān)函數(shù),若,，則時間間隔,和,因此，隨機變量,與,的數(shù)學(xué)期望等于它們各自數(shù)學(xué)期望之積，即,互不交疊（圖1-15(a)），,統(tǒng)計獨立，故它們之積,若 ，則時間間隔 和 相重疊（圖1-15b），因此，上式不再成立。,圖1-15 時間位置圖,經(jīng)過簡單運算后，可得,式中，,就是間隔,與,我們可推導(dǎo)出泊松過程,的數(shù)學(xué)期望和相關(guān)函數(shù)。,交疊部分的長度。然后，運用上述結(jié)果，,令,，可得,的數(shù)學(xué)期

17、望為,令,，可得的相關(guān)函數(shù)為,若隨機點具有非均勻密度,，我們用,代替,則前述結(jié)果仍然是成立的。即有,，,三、泊松增量,由泊松過程X(t)在給定的時間間隔 內(nèi)的增量與 之比，我們構(gòu)成一個新的隨機過程,稱它為泊松增量。,為了確定Y(t)的自相關(guān)函數(shù)，需要分別考慮兩種情況：,若 ，則間隔 與 是不重疊的,或,若 ，則間隔 與 相交疊,或,圖1-16 時間位置圖,對于,，我們也能得到與上式類似的結(jié)果。于是,圖1-17示出了 作為 的函數(shù)的圖形。由圖可見，這個函數(shù)是常數(shù) 與面積等于 的三角形之和。當(dāng) 時，此三角形趨近于沖擊,圖1-17 作為 的函數(shù)之曲線,四、泊松沖激序列,階梯性的泊松過程X(t)對時間

18、t求導(dǎo)，便可得到與時間軸上的隨機點 相對應(yīng)的沖擊序列Z(t),稱此離散隨機過程為泊松沖激序列。其表示式為,不難看出,其中X(t)和 Y(t)在前面都已經(jīng)定義過。這樣Z(t)的數(shù)學(xué)期望和相關(guān)函數(shù)可分別由式（1.7.23）和式(1.7.24)取 的極限求得，即,由此可見，泊松沖擊序列是平穩(wěn)的。,五、過濾的泊松過程與散粒噪聲,設(shè)有一泊松沖激脈沖序列 經(jīng)過線形時不變?yōu)V波器，則此濾波器輸出是隨機過程X(t)（如圖1-18所示）由圖可見,，,圖1-18 過濾的泊松過程示意圖,式中h(t)為濾波器的沖激響應(yīng)； 為第i個沖激脈沖出現(xiàn)的時間； 為在 內(nèi)輸入到濾波器的沖激脈沖的個數(shù)，它服從泊松分布，即,，,式中 為單位時間內(nèi)的平均脈沖數(shù)。,我們稱滿足式（1.7.29）的隨機過程為過濾的泊松過程。,（1.7.29）,經(jīng)分析可知，若在0,T)內(nèi)輸入到濾波器的沖激脈沖數(shù)N(T)為k，則該k個沖激脈沖出現(xiàn)的時間均為獨立同分布的隨機變量，且此隨機