隨機(jī)過(guò)程 馬爾科夫過(guò)程課件.ppt

第 四 章 馬 爾 可 夫 鏈 2 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 定 義 設(shè) X(t)， t T 為 隨 機(jī) 過(guò) 程 ， 若對(duì) 任 意 正 整 數(shù) 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 為 馬 爾 可 夫 過(guò) 程 。 若 t1,t2,tn-2表 示 過(guò) 去 ， tn-1表 示 現(xiàn) 在 ， tn表 示 將 來(lái) ， 馬 爾 可 夫 過(guò) 程 表 明 ： 在 已 知現(xiàn) 在 狀 態(tài) 的 條 件 下 ， 將 來(lái) 所 處 的 狀 態(tài) 與過(guò) 去 狀 態(tài) 無(wú) 關(guān) 。 3 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 馬 爾 可 夫 過(guò) 程 通 常 分 為 三 類 ：(1)時(shí) 間 、 狀 態(tài) 都 是 離 散 的 ， 稱 為 馬 爾 可夫 鏈(2)時(shí) 間 連 續(xù) 、 狀 態(tài) 離 散 的 ， 稱 為 連 續(xù) 時(shí) 間馬 爾 可 夫 鏈(3)時(shí) 間 、 狀 態(tài) 都 是 連 續(xù) 的 ， 稱 為 馬 爾 可 夫過(guò) 程 4 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率隨 機(jī) 過(guò) 程 Xn， nT ，參 數(shù) T=0, 1, 2, ,狀 態(tài) 空 間 I=i0, i1, i2, 定 義 若 隨 機(jī) 過(guò) 程 Xn， nT ， 對(duì) 任 意 nT和i0,i1,in+1 I， 條 件 概 率PXn+1=in+1|X0=i0,X1=i1,Xn=in = PXn+1=in+1|Xn=in， 則 稱 X n， nT 為 馬 爾 可 夫 鏈 ， 簡(jiǎn) 稱 馬 氏 鏈 。 5 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 馬 爾 可 夫 鏈 的 性 質(zhì) 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,X1=i1,Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2=PX n=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2 6 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率=PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX1=i1|X0=i0PX0=i0 馬 爾 可 夫 鏈 的 統(tǒng) 計(jì) 特 性 完 全 由 條 件 概 率PXn+1=in+1|Xn=in確 定 。 7 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 定 義 稱 條 件 概 率 pij(n)= PXn+1=j|Xn=i 為馬 爾 可 夫 鏈 Xn， nT 在 時(shí) 刻 n的 一 步 轉(zhuǎn) 移概 率 ， 簡(jiǎn) 稱 轉(zhuǎn) 移 概 率 ， 其 中 i,jI。 定 義 若 對(duì) 任 意 的 i,jI， 馬 爾 可 夫 鏈Xn,nT 的 轉(zhuǎn) 移 概 率 pij(n)與 n無(wú) 關(guān) ， 則 稱馬 爾 可 夫 鏈 是 齊 次 的 ， 并 記 pij(n)為 pij。 齊 次 馬 爾 可 夫 鏈 具 有 平 穩(wěn) 轉(zhuǎn) 移 概 率 ，狀 態(tài) 空 間 I=1, 2, 3, ， 一 步 轉(zhuǎn) 移 概 率 為 8 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 轉(zhuǎn) 移 概 率 性 質(zhì)(1) (2) P稱 為 隨 機(jī) 矩 陣 mnmm nnppp ppp pppP 21 22221 11211 Ijipij ,0 IipIj ij ,1 9 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 定 義 稱 條 件 概 率 = PXm+n=j|Xm=i 為 馬 爾 可 夫 鏈 Xn， nT 的 n步 轉(zhuǎn) 移 概率 (i,jI, m0, n1)。 n步 轉(zhuǎn) 移 矩 陣其 中 P(n)也 為 隨 機(jī) 矩 陣 )(nijp )(nijn pP Ijipp Ij nijnij ,1,0 )()( ji jipn PPppn ijijij ,1,00 ,1 )0( )1()1(時(shí) ， 規(guī) 定當(dāng) 時(shí)當(dāng) 10 4.1 馬 爾 可 夫 鏈 與 轉(zhuǎn) 移 概 率 定 理 4.1 設(shè) Xn， nT 為 馬 爾 可 夫 鏈 ，則 對(duì) 任 意 整 數(shù) n0,0l0 (最 大 公 約 數(shù) greatest common divisor) 如 果 d1， 就 稱 i為 周 期 的 ， 如 果 d=1， 就 稱 i為 非 周 期 的 )(niip 31 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 設(shè) 馬 爾 可 夫 鏈 的 狀 態(tài) 空 間I=1,2,9， 轉(zhuǎn) 移 概 率 如 下 圖 從 狀 態(tài) 1出 發(fā) 再 返 回 狀 態(tài) 1的 可 能 步 數(shù) 為T=4,6,8,10, ， T的 最 大 公 約 數(shù) 為 2，從 而 狀 態(tài) 1的 周 期 為 2 8 9567 2 341 3132 11111 1 1 1 32 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類注 (1)如 果 i有 周 期 d， 則 對(duì) 一 切 非 零 的 n, n0 (mod d)， 有 （ 若 ， 則 n=0 (mod d) ） (2)對(duì) 充 分 大 的 n， （ 引 理 4.1）例 題 中 當(dāng) n=1時(shí) ， 當(dāng) n1時(shí) ， 0)( n iip0)( niip 0)( ndiip 0)( nd iip 0)2()( iiii pp nd 33 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 狀 態(tài) 空 間 I=1,2,3,4， 轉(zhuǎn) 移 概 率 如 圖 ， 狀 態(tài) 2和 狀 態(tài) 3有 相 同 的 周 期 d=2， 但 狀 態(tài)2和 狀 態(tài) 3有 顯 著 的 區(qū) 別 。 當(dāng) 狀 態(tài) 2轉(zhuǎn) 移 到狀 態(tài) 3后 ， 再 不 能 返 回 到 狀 態(tài) 2， 狀 態(tài) 3總能 返 回 到 狀 態(tài) 3。 這 就 要 引 入 常 返 性 概 念 。 2 3 41 211 1121 34 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 由 i出 發(fā) 經(jīng) n步 首 次 到 達(dá) j的 概 率 (首 達(dá) 概 率 ) 規(guī) 定 由 i出 發(fā) 經(jīng) 有 限 步 終 于 到 達(dá) j的 概 率0 )0( ijf 1 |,11,)( n iXjXnvjXPf mnmvmnij 1 )(n nij ijff 35 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 若 fii=1， 稱 狀 態(tài) i為 常 返 的 ； 若 fii1， 稱 狀 態(tài) i為 非 常 返 的 i為 非 常 返 ， 則 以 概 率 1- fii不 返 回 到 i i為 常 返 ， 則 構(gòu) 成 一 概 率 分 布 ， 期 望 值 表 示 由 i出 發(fā) 再 返 回到 i的 平 均 返 回 時(shí) 間 1 )(n ni iinf 1 )()( 1,1n nn nff iiii 定 義 36 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 若 i ， 則 稱 常 返 態(tài) i為 正 常 返 的 ; 若 i =， 則 稱 常 返 態(tài) i為 零 常 返 的 ， 非 周 期 的 正 常 返 態(tài) 稱 為 遍 歷 狀 態(tài) 。 首 達(dá) 概 率 與 n步 轉(zhuǎn) 移 概 率 有 如 下關(guān) 系 式定 理 4.4 對(duì) 任 意 狀 態(tài) i, j及 1 n ， 有 )(nijf )(nijp nk kjjknnk knjjknij pfpfp ijij 0 )()(1 )()()( 定 義 37 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類證 )0( ,|,11, ,11,| |,11, | )0(0 )()(1 )()( 01 01 00)( ijnk kjjknnk kknjj kvnk kvnnk nkv nnij fpffp iXjXkvjXP jXkvjXiXjXP iXjXjXkvjXP iXjXPp ijij 38 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 引 理 4.2 周 期 的 等 價(jià) 定 義G .C.D =G .C.D 設(shè) 馬 爾 可 夫 鏈 的 狀 態(tài) 空 間 I=1,2,3，轉(zhuǎn) 移 概 率 矩 陣 為 求 從 狀 態(tài) 1出 發(fā) 經(jīng) n 步 轉(zhuǎn) 移 首 次 到 達(dá) 各 狀態(tài) 的 概 率 0,1: )( niipnn 0,1: )( n iifnn 000 33 22 11qp pq qpP 39 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 解 狀 態(tài) 轉(zhuǎn) 移 圖 如 下 ， 首 達(dá) 概 率 為 1 23 3q 2p 1p1q 2q3p 3131)4( 131)3( 31)2( 1)1( )( )( , 121212 12 qqpqf ppqf qqf pf 0,12,)( 1,2,)( 131 31131)(12 mmnppq mmnqqpqf mmn 40 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類同 理 可 得 0,12 ,)()( 1,2 ,)()( 1,0 0,12,)( 1,2,)( 231231321321 3123121321)( 121 21121)(1113 mmn qqpqqppqpp mmn ppqqqqpp nf mmnqqp mmnppqpf mm mmn mmn 41 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 以 下 討 論 常 返 性 的 判 別 與 性 質(zhì)數(shù) 列 的 母 函 數(shù) 與 卷 積an,n0為 實(shí) 數(shù) 列 ， 母 函 數(shù)bn,n0為 實(shí) 數(shù) 列 ， 母 函 數(shù)則 an與 bn的 卷 積的 母 函 數(shù) 0)( n nnsasA 0)( n nnsbsB nk knkn bac 0)()()( sBsAsC 42 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 定 理 4.5 狀 態(tài) i常 返 的 充 要 條 件 為如 i非 常 返 ， 則證 : 規(guī) 定 ， 則 由 定 理 4.4 0 )(n niip iin nii fp 1 10 )( 0,1 )0()0( iiii fp 1, 0 )()()( nfpp nk kniikiinii 43 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 )()(1)( )(,)( 1 0,1 0 )(0 )( 0 0 )()(0 )( )0()0( 1 0 )()(1 )( sFsPsP sfsFspsP sfpsp fp sfpsp n nniin nniin nnk kniikiin nnii iiii n nnk kniikiin nnii 則設(shè) 可 知由 44 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類對(duì) 0s1 0 )(0 )(0 )( 0 1 )()(0 )( )()(1 1)( 1)( n niin nniiNn nnii n iin niiniin nnii pspsPsp sFsP fffsfsF 45 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 iin niin niis n niis n niisn nii n niisNn nii fffsF psP psPpN psPps 1 )(0 )(1 0 )(1 0 )(10 )( 0 )(10 )()(lim)(lim )(lim, )(lim,1同 理 iiNn niiss fpsFsP 1 1,)(lim1 1)(lim 0 )(11 46 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 定 理 4.7 設(shè) i常 返 且 有 周 期 為 d， 則其 中 i為 i的 平 均 返 回 時(shí) 間 ， 當(dāng) i=時(shí) 推 論 設(shè) i常 返 ， 則(1) i零 常 返(2) i遍 歷 indiin dp )(lim 0lim )( ndiin p 0lim )( niin p 01lim )( iniin p 47 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 證 (1)i零 常 返 ， i=， 由 定 理 4.7知 ，對(duì) d的 非 整 數(shù) 倍 數(shù) 的 n， 從 而 子 序 列 i是 零 常 返 的 0lim )( ndiin p 0lim0 )()( niinnii pp ， 故0lim )( niin p 0lim )( ndiin p， 從 而 iindiin dp 0lim )( 48 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類(2) 子 序 列所 以 d=1， 從 而 i為 非 周 期 的 ， i是 遍 歷 的i是 遍 歷 的 ， d=1， i0,使 狀 態(tài) i與 狀 態(tài) j互 通 ， ij： ij且 ji 定 理 4.8 可 達(dá) 關(guān) 系 與 互 通 關(guān) 系 都 具 有 傳遞 性 ， 即(1)若 ij ， jk， 則 ik(2)若 i j ， j k， 則 i k0)( nijp 50 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 證 (1)ij ， 存 在 l 0， 使 jk， 存 在 m 0， 使由 C-K 方 程所 以 ik(2)由 (1)直 接 推 出 0)( lijp 0)( mjkp 0 )()()()()( s mjklijmsklismlik ppppp 51 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 定 理 4.8 如 ij， 則 (1) i與 j同 為 常 返 或 非 常 返 ， 如 為 常 返 ， 則它 們 同 為 正 常 返 或 零 常 返(2) i與 j有 相 同 的 周 期 52 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 設(shè) 馬 氏 鏈 Xn的 狀 態(tài) 空 間 為 I=0,1,2,， 轉(zhuǎn) 移 概 率 為考 察 狀 態(tài) 0的 類 型 Iippp iii ,21,21,21 01,001 2 3021 2121 2121 2121 21 53 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 可 得 出 0為 正 常 返 的由 于 ， 所 以 0的 周 期 為 d=10為 非 周 期 的 ， 從 而 為 遍 歷 狀 態(tài)對(duì) 于 其 它 狀 態(tài) i,由 于 i0,所 以 也 是 遍 歷 的 221 0,121,21 81212121,412121,21 11 )(000 100)(00 )3(00)2(00)1(00 n nn n n nnn nnf ff fff 為 常 返 狀 態(tài)故 021)1(00 p 54 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類 對(duì) 無(wú) 限 制 隨 機(jī) 游 動(dòng)由 斯 特 林 近 似 公 式可 推 出(1)當(dāng) 且 僅 當(dāng) p=q=1/2時(shí) ， 4pq=1nnnniinii pqCpp )(,0 2)2()12( nenn nn 2! 2)2( )12(1)1(44 )4( ppppq npqp nnii np nii 1)2( 55 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類狀 態(tài) i是 常 返 的狀 態(tài) i是 零 常 返 的 1 )2(1 )2(0 )12(1 )( 1 )2(1 ,1 m miim miim miin nii n niin pppp pn 從 而又 0lim,0lim,0lim )()12()2( miimniinniin ppp 所 以而 56 4.2 馬 爾 可 夫 鏈 的 狀 態(tài) 分 類(2)當(dāng) 且 僅 當(dāng) pq， 4pq1狀 態(tài) i是 非 常 返 的 1 )2(0 )12(1 )2(1 )( 1 )2(1 ,)4( m miim miim miin nii n niin n pppp pnpq 從 而 57 狀 態(tài) 分 類周 期 性 di 常 返 性 fii正 常 返 i1 非 周 期 di=1 遍 歷 非 常 返 fii1零 常 返 i=常 返 fii=1( ) 1lim niin ip ( )lim 0niin p ( )1 niin p 58 4.3 遍 歷 性 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 本 章 小 結(jié) 馬 爾 可 夫 鏈 的 定 義 一 步 及 K步 轉(zhuǎn) 移 概 率 初 始 概 率 及 絕 對(duì) 概 率 狀 態(tài) 分 類 遍 歷 性 平 穩(wěn) 分 布 典 型 例 題