第四章馬爾可夫鏈講稿

第四章馬爾可夫鏈講稿第1頁，共18頁，2023年，2月20日，星期三計(jì)算公式顯然有

定義設(shè)為一馬氏鏈，對任一狀態(tài)i與j，稱經(jīng)有限步（遲早）到達(dá)狀態(tài)j的概率。

為自狀態(tài)i出發(fā)定義如果，則稱狀態(tài)i是常返的。如果，則稱狀態(tài)i是非常返的（或稱為瞬時的）。如果馬爾可夫鏈的任一狀態(tài)都是常返的，則稱此鏈為常返馬爾可夫鏈。第2頁，共18頁，2023年，2月20日，星期三定義設(shè)i是一常返態(tài)，則從i出發(fā)可經(jīng)過n步首次返回i，在的條件下的分布列為12…nP………由數(shù)學(xué)期望的定義，可得

稱為狀態(tài)i的平均返回時間。

定義設(shè)i是常返態(tài)，如果，則稱狀態(tài)i是正常返態(tài)；如果,則稱狀態(tài)i是零常返態(tài)。如果狀態(tài)i是非周期且正常返的，則稱狀態(tài)i是遍歷的。第3頁，共18頁，2023年，2月20日，星期三定理對任何狀態(tài)，有證明：因?yàn)?/p>

第4頁，共18頁，2023年，2月20日，星期三定理

狀態(tài)i是常返（）的充要條件為系：如果狀態(tài)i是非常返的充要條件是系：如果i是常返態(tài)，則（1）i零常返當(dāng)且僅當(dāng)（2）i遍歷當(dāng)且僅當(dāng)定理：設(shè)i為常返狀態(tài)，有周期,則此時有第5頁，共18頁，2023年，2月20日，星期三馬氏狀態(tài)分類圖

狀態(tài)分類判別法：

（1）i非常返（2）i零常返且且（4）i遍歷

且（3）i正常返第6頁，共18頁，2023年，2月20日，星期三二、馬氏鏈中的狀態(tài)關(guān)系定義

（可達(dá)）：如果對于狀態(tài)i和j,總存在某個，使得，則稱自i狀態(tài)經(jīng)過n步可以到達(dá)j狀態(tài)，并記為反之，若對所有的有，則自i狀態(tài)不可以到達(dá)j狀態(tài)，并記為可達(dá)具有傳遞性，即若,,則證明:由知，存在使得再由C-K方程可知，因此可達(dá)與互通第7頁，共18頁，2023年，2月20日，星期三

例設(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á)特性。注：此題畫狀態(tài)轉(zhuǎn)移圖更直觀第8頁，共18頁，2023年，2月20日，星期三定義（互通）：若自狀態(tài)i可達(dá)狀態(tài)j，同時自狀態(tài)j也可達(dá)狀態(tài)i，則稱狀態(tài)和狀態(tài)互通，記為

互通是一種等價關(guān)系，即滿足：

（1）若，則,自返性（2）若，則，對稱性（3）若，，則，傳遞性我們把任何兩個互通的狀態(tài)歸為一類。然后定義：定義若Markov鏈只存在一個類，就稱它是不可約的；否則稱為可約的。第9頁，共18頁，2023年，2月20日，星期三例無限制的隨機(jī)游走問題?？紤]一個質(zhì)點(diǎn)在直線上作隨機(jī)游走．如果在某一時刻質(zhì)點(diǎn)位于i,則下一步質(zhì)點(diǎn)將以概率向前游走一步到達(dá)i+1處，或以概率向后游走一步到達(dá)i-1處。現(xiàn)規(guī)定，這一質(zhì)點(diǎn)只能“向前”或“向后”游走一步，并且經(jīng)過一個單位時間它必須“向前”或“向后”游走。討論其狀態(tài)的互通性。解：如果以表示n時刻質(zhì)點(diǎn)的位置，則是一個隨機(jī)過程。而且，當(dāng)時，等在時刻n后質(zhì)點(diǎn)所處的狀態(tài)僅與有關(guān)，而與質(zhì)點(diǎn)在時刻n以前是如何到達(dá)i的無關(guān)．故它是一個齊次馬爾可夫鏈。狀態(tài)空間，一步轉(zhuǎn)移概率為從而一步轉(zhuǎn)移概率矩陣為第10頁，共18頁，2023年，2月20日，星期三下面求n步轉(zhuǎn)移概率如在n次轉(zhuǎn)移的結(jié)果是從i到j(luò),n次轉(zhuǎn)移中恰好向前游走m次，向后游走k次，則有

聯(lián)立上兩式求解可得根據(jù)概率法則，不難求得n步轉(zhuǎn)移概率為其中時，反映了在n，i，j之間存在的一種約束關(guān)系。由于對于滿足要求的n，i，j，，所以無限制的隨機(jī)游走中的各個狀態(tài)是互通的。第11頁，共18頁，2023年，2月20日，星期三引理1對任意i和j，若，則存在正數(shù)、及正整數(shù)l、m，使對任一正整數(shù)n，有、定理若，則（1）i與j同為常返或同為非常返；（2）若i與j常返，則i與j同為正常返或同為零常返；（3）i與j或同為非周期的，或同為周期的且有相同的周期。第12頁，共18頁，2023年，2月20日，星期三定理的充要條件是證明：充分性：若，則根據(jù)到達(dá)的定義，總存在某個，使所以這樣，至少有一個為正（不為0），所以必要性：若，則由至少有一個使，故表示自狀態(tài)i出發(fā)，在有限步內(nèi)遲早要返回狀態(tài)i的概率，是在0與1之間的一個數(shù)。第13頁，共18頁，2023年，2月20日，星期三三、狀態(tài)空間分解定義設(shè)，若從V中任一狀態(tài)出發(fā)不能到達(dá)V外的任一狀態(tài)，則稱V為閉集。顯然，對一切和有

若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)部的狀態(tài)之間轉(zhuǎn)移。定理馬爾可夫鏈的所有常返狀態(tài)構(gòu)成的集合是一閉集。第14頁，共18頁，2023年，2月20日，星期三有限狀態(tài)分解定理第15頁，共18頁，2023年，2月20日，星期三定理（分解定理）狀態(tài)空間E必可分解為

其中N是全體非常返態(tài)組成的集合，是互不相交的常返態(tài)閉集組成。而且（1）對每一確定的k,內(nèi)任意兩狀態(tài)相通；（2）與()中的狀態(tài)之間不相通；第16頁，共18頁，2023年，2月20日，星期三例設(shè)齊次馬氏鏈的狀態(tài)空間，其一步轉(zhuǎn)移概率矩陣如下，試對該空間進(jìn)行分解。解：根據(jù)一步轉(zhuǎn)移概率矩陣，可畫出如圖所示的狀態(tài)轉(zhuǎn)移圖。由圖可知，，而當(dāng)時，，所以，可見狀態(tài)1為正常返，且周期。含有狀態(tài)1的常返閉集為第17頁，共18頁，2023年，2月20日，星期三同理，因?yàn)椋?，?/p>