隨機過程 馬爾科夫過程

1、第四章第四章 馬爾可夫鏈馬爾可夫鏈 24.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率 定義定義 設設 X(t)，t T 為隨機過程，若為隨機過程，若對任意正整數對任意正整數n及及t1 t20，且條件分且條件分布布PX(tn) xn|X(t1)=x1, X(tn- -1)=xn- -1= PX(tn) xn|X(tn- -1)=xn- -1，則稱則稱 X(t)，t T 為為馬爾可夫過程馬爾可夫過程。若若t1,t2,tn- -2表示過去，表示過去，tn- -1表示現在，表示現在，tn表示將來，馬爾可夫過程表明：表示將來，馬爾可夫過程表明：在已知在已知現在狀態(tài)的條件下，將來所處的狀態(tài)與現在狀態(tài)的條

2、件下，將來所處的狀態(tài)與過去狀態(tài)無關。過去狀態(tài)無關。34.1 馬爾可夫鏈與轉移概率 馬爾可夫過程通常分為三類：馬爾可夫過程通常分為三類：(1)(1)時間、狀態(tài)都是離散的，稱為時間、狀態(tài)都是離散的，稱為馬爾可馬爾可夫鏈夫鏈(2)時間連續(xù)時間連續(xù)、狀態(tài)離散的，稱為連續(xù)時間狀態(tài)離散的，稱為連續(xù)時間馬爾可夫鏈馬爾可夫鏈(3)時間、狀態(tài)都是連續(xù)的，稱為時間、狀態(tài)都是連續(xù)的，稱為馬爾可夫馬爾可夫過程過程44.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率隨機過程隨機過程 Xn，n T ，參數參數T=0, 1, 2, , ,狀態(tài)空間狀態(tài)空間I=i0, i1, i2, 定義定義 若隨機過程若隨機過程 Xn，n T

3、 ，對任意，對任意n T和和i0,i1,in+1 I，條件概率條件概率PXn+1=in+1|X0=i0,X1=i1,Xn=in = PXn+1=in+1|Xn=in， 則稱則稱 Xn，n T 為為馬爾可夫鏈馬爾可夫鏈，簡稱，簡稱馬氏鏈馬氏鏈。54.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率 馬爾可夫鏈的馬爾可夫鏈的性質性質 PX0=i0, X1=i1, , Xn=in=PXn=in|X0=i0, X1=i1, , Xn- -1=in- -1 PX0=i0, X1=i1, , Xn- -1=in- -1= PXn=in|Xn- -1=in- -1 PXn- -1=in- -1 |X0=i0,X

4、1=i1,Xn- -2=in- -2 PX0=i0,X1=i1,Xn- -2=in- -2=PXn=in|Xn- -1=in- -1PXn- -1=in- -1 |Xn- -2=in- -2 PX0=i0,X1=i1,Xn- -2=in- -264.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率=PXn=in|Xn- -1=in- -1PXn- -1=in- -1 |Xn- -2=in- -2 PX1=i1|X0=i0PX0=i0 馬爾可夫鏈的統計特性完全由條件概率馬爾可夫鏈的統計特性完全由條件概率PXn+1=in+1|Xn=in確定。確定。74.1 馬爾可夫鏈與轉移概率 定義定義 稱條件概率稱

5、條件概率pij(n)= PXn+1=j|Xn=i 為為馬爾可夫鏈馬爾可夫鏈 Xn，n T 在時刻在時刻n的的一步轉移一步轉移概率概率，簡稱簡稱轉移概率轉移概率，其中其中i, ,j I。 定義定義 若對任意的若對任意的i, ,j I，馬爾可夫鏈馬爾可夫鏈 Xn,n T 的轉移概率的轉移概率pij(n)與與n無關，則稱無關，則稱馬爾可夫鏈是齊次的馬爾可夫鏈是齊次的，并記，并記pij(n)為為pij。 齊次馬爾可夫鏈具有平穩(wěn)轉移概率，齊次馬爾可夫鏈具有平穩(wěn)轉移概率，狀態(tài)空間狀態(tài)空間I=1, 2, 3, ，一步一步轉移概率為轉移概率為84.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率 轉移概率轉移概率

6、性質性質(1) (2) P稱為隨機矩陣稱為隨機矩陣mnmmnnpppppppppP212222111211Ijipij, 0IipIjij, 194.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率 定義定義 稱條件概率稱條件概率 = PXm+n=j|Xm=i 為為馬爾可夫鏈馬爾可夫鏈 Xn，n T 的的n步轉移概步轉移概率率(i, ,j I, m 0, n 1)。 n步轉移矩陣步轉移矩陣其中其中 P(n)也為也為隨機矩陣隨機矩陣)(nijp)(nijnpP IjippIjnijnij, 1,0)()(jijipnPPppnijijij,1,00,1)0()1()1(時，規(guī)定時，規(guī)定當當時時當當1

7、04.1 馬爾可夫鏈與轉移概率馬爾可夫鏈與轉移概率 定理定理4.1 設設 Xn，n T 為為馬爾可夫鏈，馬爾可夫鏈，則對任意整數則對任意整數n 0,0 l0 (最大公約數最大公約數greatest common divisor) 如果如果d1，就稱就稱i為周期的，為周期的， 如果如果d=1，就稱就稱i為非周期的為非周期的)(niip314.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 設馬爾可夫鏈的設馬爾可夫鏈的狀態(tài)空間狀態(tài)空間I=1,2,9，轉移概率如下圖轉移概率如下圖 從狀態(tài)從狀態(tài)1出發(fā)再返回狀態(tài)出發(fā)再返回狀態(tài)1的可能步數為的可能步數為T=4,6,8,10, ，T的的最大公約數為最大公約數

8、為2，從而從而狀態(tài)狀態(tài)1的周期為的周期為2895672341313211111111324.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類注注(1)如果如果i有周期有周期d，則對一切非零的則對一切非零的n, , n 0 (mod d)，有有 （若若 ，則，則n=0 (mod d) ） (2)對充分大的對充分大的n， （引理引理4.1）例題中當例題中當n=1時，時， 當當n1時，時，0)(niip0)(niip0)(ndiip0)(ndiip0)2()(iiiippnd334.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 狀態(tài)空間狀態(tài)空間I=1,2,3,4，轉移概率如圖轉移概率如圖， 狀態(tài)狀態(tài)2和

9、狀態(tài)和狀態(tài)3有相同的周期有相同的周期d=2，但狀態(tài)但狀態(tài)2和狀態(tài)和狀態(tài)3有顯著的區(qū)別。當狀態(tài)有顯著的區(qū)別。當狀態(tài)2轉移到轉移到狀態(tài)狀態(tài)3后，再不能返回到狀態(tài)后，再不能返回到狀態(tài)2，狀態(tài)，狀態(tài)3總總能返回到狀態(tài)能返回到狀態(tài)3。這就要引入。這就要引入常返性常返性概念。概念。23412111121344.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 由由i出發(fā)經出發(fā)經n步首次到達步首次到達j的概率的概率(首達概率首達概率) 規(guī)定規(guī)定 由由i出發(fā)經有限步終于到達出發(fā)經有限步終于到達j的概率的概率0)0(ijf1 |, 11 ,)(niXjXnvjXPfmnmvmnij1)(nnijijff354.2

10、馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 若若fii=1，稱狀態(tài)稱狀態(tài)i為為常返的常返的； 若若fii1，稱狀態(tài)稱狀態(tài)i為為非常返的非常返的 i為非常返，則以概率為非常返，則以概率1- - fii不返回到不返回到i i為常返，則為常返，則 構成一概率分布，構成一概率分布， 期望值期望值 表示由表示由i出發(fā)再返回出發(fā)再返回到到i的平均返回時間的平均返回時間1)(nniiinf 1)()(1, 1nnnnffiiii定義定義364.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 若若 i ，則稱常返態(tài)則稱常返態(tài)i為正常返的為正常返的; 若若 i = ，則稱常返態(tài)則稱常返態(tài)i為零常返的，為零常返的，

11、非周期的正常返態(tài)稱為遍歷狀態(tài)。非周期的正常返態(tài)稱為遍歷狀態(tài)。 首達概率首達概率 與與n步轉移概率步轉移概率 有如下有如下關系式關系式定理定理4.4 對任意狀態(tài)對任意狀態(tài)i, j及及1 n ，有有)(nijf)(nijpnkkjjknnkknjjknijpfpfpijij0)()(1)()()(定義定義374.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類證證)0( ,|, 11 , 11 ,|, 11 ,|)0(0)()(1)()(010100)(ijnkkjjknnkkknjjkvnkkvnnknkvnnijfpffpiXjXkvjXPjXkvjXiXjXPiXjXjXkvjXPiXjXPpi

12、jij384.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 引理引理4.2 周期的等價定義周期的等價定義G.C.D =G.C.D 設馬爾可夫鏈的狀態(tài)空間設馬爾可夫鏈的狀態(tài)空間I=1,2,3，轉移概率矩陣為轉移概率矩陣為 求從狀態(tài)求從狀態(tài)1出發(fā)經出發(fā)經n 步轉移首次到達各狀步轉移首次到達各狀態(tài)的概率態(tài)的概率0, 1:)(niipnn0, 1:)(niifnn000332211qppqqpP394.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 解解 狀態(tài)轉移圖如下狀態(tài)轉移圖如下 ，首達概率為，首達概率為 1233q2p1p1q2q3p3131)4(131)3(31)2(1)1()()(,12121

13、212qqpqfppqfqqfpf0, 12,)(1,2,)(13131131)(12mmnppqmmnqqpqfmmn404.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類同理可得同理可得0, 12 ,)()(1,2 ,)()(1,00, 12,)(1,2,)(2312313213213123121321)(12121121)(1113mmnqqpqqppqppmmnppqqqqppnfmmnqqpmmnppqpfmmmmnmmn414.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 以下討論常返性的判別與性質以下討論常返性的判別與性質數列的母函數與卷積數列的母函數與卷積an,n 0為實數列，母

14、函數為實數列，母函數bn,n 0為實數列，母函數為實數列，母函數則則an與與bn的卷積的卷積的母函數的母函數0)(nnnsasA0)(nnnsbsBnkknknbac0)()()(sBsAsC424.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 定理定理4.5 狀態(tài)狀態(tài)i常返的充要條件為常返的充要條件為如如i非常返，則非常返，則證證: 規(guī)定規(guī)定 ，則由定理，則由定理4.40)(nniipiinniifp110)(0, 1)0()0(iiiifp1,0)()()(nfppnkkniikiinii434.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 )()(1)()(,)(10,

15、10)(0)(00)()(0)()0()0(10)()(1)(sFsPsPsfsFspsPsfpspfpsfpspnnniinnniinnnkkniikiinnniiiiiinnnkkniikiinnnii 則則設設可知可知由由444.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類對對0 s10)(0)(0)(01)()(0)()()(11)(1)(nniinnniiNnnniiniinniiniinnniipspsPspsFsPfffsfsF454.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 iinniinniisnniisnniisnniinniisNnniifffsFps

16、PpsPpNpsPps1)(0)(10)(10)(10)(0)(10)()(lim)(lim)(lim,)(lim, 1同理同理iiNnniissfpsFsP11,)(lim11)(lim0)(11464.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 定理定理4.7 設設i常返且有周期為常返且有周期為d，則則其中其中 i為為i的平均返回時間，當的平均返回時間，當 i= 時時 推論推論 設設i常返，則常返，則(1) i零常返零常返(2) i遍歷遍歷indiindp )(lim0lim)(ndiinp0lim)(niinp01lim)(iniinp 474.2 4.2 馬爾可夫鏈的狀態(tài)分類

17、馬爾可夫鏈的狀態(tài)分類 證證(1)i零常返，零常返， i= ，由定理由定理4.7知，知，對對d的非整數倍數的的非整數倍數的n， 從而子序列從而子序列 i是零常返的是零常返的0lim)(ndiinp0lim0)()(niinniipp，故，故0lim)(niinp0lim)(ndiinp，從而，從而iindiindp 0lim)(484.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類(2) 子序列子序列所以所以d=1，從而從而i為非周期的，為非周期的，i是遍歷的是遍歷的i是遍歷的，是遍歷的，d=1， i0,使使 狀態(tài)狀態(tài)i與狀態(tài)與狀態(tài)j互通互通，ij：ij且且ji 定理定理4.8 可達關系與

18、互通關系都具有傳可達關系與互通關系都具有傳遞性，即遞性，即(1)若若ij ，jk，則則ik(2)若若i j ，j k，則則i k0)(nijp504.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 證證 (1)ij ，存在，存在l 0，使使 jk，存在存在m 0，使使由由C-K方程方程所以所以ik(2)由由(1)直接推出直接推出0)(lijp0)(mjkp0)()()()()(smjklijmsklismlikppppp514.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 定理定理4.8 如如ij，則，則 (1) i與與j同為常返或非常返，如為常返，則同為常返或非常返，如為常返，

19、則它們同為正常返或零常返它們同為正常返或零常返(2) i與與j有相同的周期有相同的周期524.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 設馬氏鏈設馬氏鏈Xn的狀態(tài)空間為的狀態(tài)空間為 I=0,1,2,，轉移概率為轉移概率為考察狀態(tài)考察狀態(tài)0的類型的類型Iipppiii,21,21,2101,0012302121212121212121534.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 可得出可得出0為正常返的為正常返的由于由于 ，所以，所以0的周期為的周期為d=10為非周期的，從而為遍歷狀態(tài)為非周期的，從而為遍歷狀態(tài)對于其它狀態(tài)對于其它狀態(tài)i,由于由于i0,所以也是遍歷的所以也是遍歷的 2210, 121,2181212121,412121,2111)(000100)(00)3(00)2(00)1(00nnnnnnnnnnffffff 為常返狀態(tài)為常返狀態(tài)故故021)1(00p544.2 4.2 馬爾可夫鏈的狀態(tài)分類馬爾可夫鏈的狀態(tài)分類 對無限制隨機游動對無限制