随机过程 马尔科夫过程课件.ppt

第 四 章 马 尔 可 夫 链 2 4.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表 示 将 来 ， 马 尔 可 夫 过 程 表 明 ： 在 已 知现 在 状 态 的 条 件 下 ， 将 来 所 处 的 状 态 与过 去 状 态 无 关 。 3 4.1 马 尔 可 夫 链 与 转 移 概 率 马 尔 可 夫 过 程 通 常 分 为 三 类 ：(1)时 间 、 状 态 都 是 离 散 的 ， 称 为 马 尔 可夫 链(2)时 间 连 续 、 状 态 离 散 的 ， 称 为 连 续 时 间马 尔 可 夫 链(3)时 间 、 状 态 都 是 连 续 的 ， 称 为 马 尔 可 夫过 程 4 4.1 马 尔 可 夫 链 与 转 移 概 率随 机 过 程 Xn， nT ，参 数 T=0, 1, 2, ,状 态 空 间 I=i0, i1, i2, 定 义 若 随 机 过 程 Xn， nT ， 对 任 意 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 为 马 尔 可 夫 链 ， 简 称 马 氏 链 。 5 4.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,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 马 尔 可 夫 链 与 转 移 概 率=PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX1=i1|X0=i0PX0=i0 马 尔 可 夫 链 的 统 计 特 性 完 全 由 条 件 概 率PXn+1=in+1|Xn=in确 定 。 7 4.1 马 尔 可 夫 链 与 转 移 概 率 定 义 称 条 件 概 率 pij(n)= PXn+1=j|Xn=i 为马 尔 可 夫 链 Xn， nT 在 时 刻 n的 一 步 转 移概 率 ， 简 称 转 移 概 率 ， 其 中 i,jI。 定 义 若 对 任 意 的 i,jI， 马 尔 可 夫 链Xn,nT 的 转 移 概 率 pij(n)与 n无 关 ， 则 称马 尔 可 夫 链 是 齐 次 的 ， 并 记 pij(n)为 pij。 齐 次 马 尔 可 夫 链 具 有 平 稳 转 移 概 率 ，状 态 空 间 I=1, 2, 3, ， 一 步 转 移 概 率 为 8 4.1 马 尔 可 夫 链 与 转 移 概 率 转 移 概 率 性 质(1) (2) P称 为 随 机 矩 阵 mnmm nnppp ppp pppP 21 22221 11211 Ijipij ,0 IipIj ij ,1 9 4.1 马 尔 可 夫 链 与 转 移 概 率 定 义 称 条 件 概 率 = PXm+n=j|Xm=i 为 马 尔 可 夫 链 Xn， nT 的 n步 转 移 概率 (i,jI, m0, n1)。 n步 转 移 矩 阵其 中 P(n)也 为 随 机 矩 阵 )(nijp )(nijn pP Ijipp Ij nijnij ,1,0 )()( ji jipn PPppn ijijij ,1,00 ,1 )0( )1()1(时 ， 规 定当 时当 10 4.1 马 尔 可 夫 链 与 转 移 概 率 定 理 4.1 设 Xn， nT 为 马 尔 可 夫 链 ，则 对 任 意 整 数 n0,0l0 (最 大 公 约 数 greatest common divisor) 如 果 d1， 就 称 i为 周 期 的 ， 如 果 d=1， 就 称 i为 非 周 期 的 )(niip 31 4.2 马 尔 可 夫 链 的 状 态 分 类 设 马 尔 可 夫 链 的 状 态 空 间I=1,2,9， 转 移 概 率 如 下 图 从 状 态 1出 发 再 返 回 状 态 1的 可 能 步 数 为T=4,6,8,10, ， T的 最 大 公 约 数 为 2，从 而 状 态 1的 周 期 为 2 8 9567 2 341 3132 11111 1 1 1 32 4.2 马 尔 可 夫 链 的 状 态 分 类注 (1)如 果 i有 周 期 d， 则 对 一 切 非 零 的 n, n0 (mod d)， 有 （ 若 ， 则 n=0 (mod d) ） (2)对 充 分 大 的 n， （ 引 理 4.1）例 题 中 当 n=1时 ， 当 n1时 ， 0)( n iip0)( niip 0)( ndiip 0)( nd iip 0)2()( iiii pp nd 33 4.2 马 尔 可 夫 链 的 状 态 分 类 状 态 空 间 I=1,2,3,4， 转 移 概 率 如 图 ， 状 态 2和 状 态 3有 相 同 的 周 期 d=2， 但 状 态2和 状 态 3有 显 著 的 区 别 。 当 状 态 2转 移 到状 态 3后 ， 再 不 能 返 回 到 状 态 2， 状 态 3总能 返 回 到 状 态 3。 这 就 要 引 入 常 返 性 概 念 。 2 3 41 211 1121 34 4.2 马 尔 可 夫 链 的 状 态 分 类 由 i出 发 经 n步 首 次 到 达 j的 概 率 (首 达 概 率 ) 规 定 由 i出 发 经 有 限 步 终 于 到 达 j的 概 率0 )0( ijf 1 |,11,)( n iXjXnvjXPf mnmvmnij 1 )(n nij ijff 35 4.2 马 尔 可 夫 链 的 状 态 分 类 若 fii=1， 称 状 态 i为 常 返 的 ； 若 fii1， 称 状 态 i为 非 常 返 的 i为 非 常 返 ， 则 以 概 率 1- fii不 返 回 到 i i为 常 返 ， 则 构 成 一 概 率 分 布 ， 期 望 值 表 示 由 i出 发 再 返 回到 i的 平 均 返 回 时 间 1 )(n ni iinf 1 )()( 1,1n nn nff iiii 定 义 36 4.2 马 尔 可 夫 链 的 状 态 分 类 若 i ， 则 称 常 返 态 i为 正 常 返 的 ; 若 i =， 则 称 常 返 态 i为 零 常 返 的 ， 非 周 期 的 正 常 返 态 称 为 遍 历 状 态 。 首 达 概 率 与 n步 转 移 概 率 有 如 下关 系 式定 理 4.4 对 任 意 状 态 i, j及 1 n ， 有 )(nijf )(nijp nk kjjknnk knjjknij pfpfp ijij 0 )()(1 )()()( 定 义 37 4.2 马 尔 可 夫 链 的 状 态 分 类证 )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 马 尔 可 夫 链 的 状 态 分 类 引 理 4.2 周 期 的 等 价 定 义G .C.D =G .C.D 设 马 尔 可 夫 链 的 状 态 空 间 I=1,2,3，转 移 概 率 矩 阵 为 求 从 状 态 1出 发 经 n 步 转 移 首 次 到 达 各 状态 的 概 率 0,1: )( niipnn 0,1: )( n iifnn 000 33 22 11qp pq qpP 39 4.2 马 尔 可 夫 链 的 状 态 分 类 解 状 态 转 移 图 如 下 ， 首 达 概 率 为 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 马 尔 可 夫 链 的 状 态 分 类同 理 可 得 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 马 尔 可 夫 链 的 状 态 分 类 以 下 讨 论 常 返 性 的 判 别 与 性 质数 列 的 母 函 数 与 卷 积an,n0为 实 数 列 ， 母 函 数bn,n0为 实 数 列 ， 母 函 数则 an与 bn的 卷 积的 母 函 数 0)( n nnsasA 0)( n nnsbsB nk knkn bac 0)()()( sBsAsC 42 4.2 马 尔 可 夫 链 的 状 态 分 类 定 理 4.5 状 态 i常 返 的 充 要 条 件 为如 i非 常 返 ， 则证 : 规 定 ， 则 由 定 理 4.4 0 )(n niip iin nii fp 1 10 )( 0,1 )0()0( iiii fp 1, 0 )()()( nfpp nk kniikiinii 43 4.2 马 尔 可 夫 链 的 状 态 分 类 )()(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 则设 可 知由 44 4.2 马 尔 可 夫 链 的 状 态 分 类对 0s1 0 )(0 )(0 )( 0 1 )()(0 )( )()(1 1)( 1)( n niin nniiNn nnii n iin niiniin nnii pspsPsp sFsP fffsfsF 45 4.2 马 尔 可 夫 链 的 状 态 分 类 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 马 尔 可 夫 链 的 状 态 分 类 定 理 4.7 设 i常 返 且 有 周 期 为 d， 则其 中 i为 i的 平 均 返 回 时 间 ， 当 i=时 推 论 设 i常 返 ， 则(1) i零 常 返(2) i遍 历 indiin dp )(lim 0lim )( ndiin p 0lim )( niin p 01lim )( iniin p 47 4.2 马 尔 可 夫 链 的 状 态 分 类 证 (1)i零 常 返 ， i=， 由 定 理 4.7知 ，对 d的 非 整 数 倍 数 的 n， 从 而 子 序 列 i是 零 常 返 的 0lim )( ndiin p 0lim0 )()( niinnii pp ， 故0lim )( niin p 0lim )( ndiin p， 从 而 iindiin dp 0lim )( 48 4.2 马 尔 可 夫 链 的 状 态 分 类(2) 子 序 列所 以 d=1， 从 而 i为 非 周 期 的 ， i是 遍 历 的i是 遍 历 的 ， d=1， i0,使 状 态 i与 状 态 j互 通 ， ij： ij且 ji 定 理 4.8 可 达 关 系 与 互 通 关 系 都 具 有 传递 性 ， 即(1)若 ij ， jk， 则 ik(2)若 i j ， j k， 则 i k0)( nijp 50 4.2 马 尔 可 夫 链 的 状 态 分 类 证 (1)ij ， 存 在 l 0， 使 jk， 存 在 m 0， 使由 C-K 方 程所 以 ik(2)由 (1)直 接 推 出 0)( lijp 0)( mjkp 0 )()()()()( s mjklijmsklismlik ppppp 51 4.2 马 尔 可 夫 链 的 状 态 分 类 定 理 4.8 如 ij， 则 (1) i与 j同 为 常 返 或 非 常 返 ， 如 为 常 返 ， 则它 们 同 为 正 常 返 或 零 常 返(2) i与 j有 相 同 的 周 期 52 4.2 马 尔 可 夫 链 的 状 态 分 类 设 马 氏 链 Xn的 状 态 空 间 为 I=0,1,2,， 转 移 概 率 为考 察 状 态 0的 类 型 Iippp iii ,21,21,21 01,001 2 3021 2121 2121 2121 21 53 4.2 马 尔 可 夫 链 的 状 态 分 类 可 得 出 0为 正 常 返 的由 于 ， 所 以 0的 周 期 为 d=10为 非 周 期 的 ， 从 而 为 遍 历 状 态对 于 其 它 状 态 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 为 常 返 状 态故 021)1(00 p 54 4.2 马 尔 可 夫 链 的 状 态 分 类 对 无 限 制 随 机 游 动由 斯 特 林 近 似 公 式可 推 出(1)当 且 仅 当 p=q=1/2时 ， 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 马 尔 可 夫 链 的 状 态 分 类状 态 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 马 尔 可 夫 链 的 状 态 分 类(2)当 且 仅 当 pq， 4pq1状 态 i是 非 常 返 的 1 )2(0 )12(1 )2(1 )( 1 )2(1 ,)4( m miim miim miin nii n niin n pppp pnpq 从 而 57 状 态 分 类周 期 性 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 本 章 小 结 马 尔 可 夫 链 的 定 义 一 步 及 K步 转 移 概 率 初 始 概 率 及 绝 对 概 率 状 态 分 类 遍 历 性 平 稳 分 布 典 型 例 题