马尔可夫过程.ppt

应用随机过程 杜勇宏2005年5月25日联系方式 电话mail yonghongdu 马尔可夫链 3 4 1马尔可夫链与转移概率4 2马尔可夫链的状态分类4 3状态空间的分解4 4渐近性质与平稳分布4 5连续时间马尔可夫链4 6柯尔莫哥洛夫微分方程 4 马尔可夫过程的定义 定义4 1设 X t t T 为随机过程 若对任意正整数n及t10 且条件分布P X tn xn X t1 x1 X tn 1 xn 1 P X tn xn X tn 1 xn 1 则称 X t t T 为马尔可夫过程 若t1 t2 tn 2表示过去 tn 1表示现在 tn表示将来 马尔可夫过程表明 在已知现在状态的条件下 将来所处的状态与过去状态无关 5 马尔可夫过程的定义 马尔可夫过程通常分为三类 1 时间 状态都是离散的 称为马尔可夫链 2 时间连续 状态离散的 称为连续时间马尔可夫链 3 时间 状态都是连续的 称为马尔可夫过程 6 马尔可夫链的一个应用 含体制变化的时间序列建模 如果人们观察宏观经济或金融时间序列足够长时期 则可以看到类似的戏剧性中断 时间序列的这种明显变化可能源于战争 金融恐慌或政府政策的显著变化 一个有吸引力的例子是墨西哥银行美元帐户的比索值对墨西哥银行美元帐户的比索值之比率 Rogers 1992 7 墨西哥银行美元帐户的比索值对墨西哥银行美元帐户的比索值之比率 月度数据 1978 1985 78 79 82 81 80 84 85 83 8 马尔可夫链的一个应用 含体制变化的时间序列建模 对于一个具体的时间序列过程 我们如何建模呢 一个简单的想法可能是1982年自回归的常数项发生了变化 对于1982年前的数据 我们可使用模型如yt 1 yt 1 1 t而1982年后的数据则可描述作yt 2 yt 1 2 t 9 马尔可夫链的一个应用 含体制变化的时间序列建模 上面的模型看起来是对数据的一个可行描述 但作为一个时间序列模型并不令人满意 如果过去的过程发生了变化 显然它在将来也可能发生变化 所以在预测是应考虑到这一点 另外 体制的变化肯定不能视做完全可预见的 确定性事件 还有 体制变化本身是一个随机变量 因而一个完整的时间序列模型应该包括参数从 1到 2之变化的概率规律 10 马尔可夫链的一个应用 含体制变化的时间序列建模 上述观察表明 我们应该考虑未被观察到的随机变量s t 的影响 s t 表示过程在时刻t的状态或体制 如果s t 1 则过程处在体制1 而s t 2则意味着过程处于体制2 则上面的模型可等价写作yt s t yt 1 s t t其中描述这类离散性随机变量s t 的最简单而有效的时间序列模型是马尔可夫链 见hamilton 时间序列分析 1998 11 4 1马尔可夫链与转移概率 随机过程 Xn n T 参数T 0 1 2 状态空间I i0 i1 i2 定义4 2若随机过程 Xn n T 对任意n T和i0 i1 in 1 I 条件概率P Xn 1 in 1 X0 i0 X1 i1 Xn in P Xn 1 in 1 Xn in 则称 Xn n T 为马尔可夫链 简称马氏链 12 4 1马尔可夫链与转移概率 马尔可夫链的性质P X0 i0 X1 i1 Xn in P Xn in X0 i0 X1 i1 Xn 1 in 1 P X0 i0 X1 i1 Xn 1 in 1 P Xn in Xn 1 in 1 P Xn 1 in 1 X0 i0 X1 i1 Xn 2 in 2 P X0 i0 X1 i1 Xn 2 in 2 P Xn in Xn 1 in 1 P Xn 1 in 1 Xn 2 in 2 P X0 i0 X1 i1 Xn 2 in 2 13 4 1马尔可夫链与转移概率 P Xn in Xn 1 in 1 P Xn 1 in 1 Xn 2 in 2 P X1 i1 X0 i0 P X0 i0 马尔可夫链的统计特性完全由条件概率P Xn 1 in 1 Xn in 确定 14 4 1马尔可夫链与转移概率 定义4 3称条件概率pij n P Xn 1 j Xn i 为马尔可夫链 Xn n T 在时刻n的一步转移概率 简称转移概率 其中i j I 定义4 4若对任意的i j I 马尔可夫链 Xn n T 的转移概率pij n 与n无关 则称马尔可夫链是齐次的 并记pij n 为pij 齐次马尔可夫链具有平稳转移概率 状态空间I 1 2 3 一步转移概率为 15 4 1马尔可夫链与转移概率 转移概率性质 1 2 P称为随机矩阵 16 4 1马尔可夫链与转移概率 定义4 5称条件概率 P Xm n j Xm i 为马尔可夫链 Xn n T 的n步转移概率 i j I m 0 n 1 n步转移矩阵其中P n 也为随机矩阵 17 4 1马尔可夫链与转移概率 定理4 1设 Xn n T 为马尔可夫链 则对任意整数n 0 0 l n和i j I n步转移概率具有性质 1 2 3 P n PP n 1 4 P n Pn 18 4 1马尔可夫链与转移概率 证 1 19 4 1马尔可夫链与转移概率 2 在 1 中令l 1 k k1 得由此可递推出公式 3 矩阵乘法 4 由 3 推出说明 1 此为C K方程 切普曼 柯尔莫哥洛夫 2 n步转移概率由一步转移概率确定 n步转移概率矩阵由一步转移概率矩阵确定 n次幂 20 4 1马尔可夫链与转移概率 初始概率绝对概率初始分布绝对分布初始概率向量绝对概率向量 定义4 6 21 4 1马尔可夫链与转移概率 设 Xn n T 为马尔可夫链 则对任意整数j I和n 1 绝对概率pj n 具有性质 1 2 3 PT n PT 0 P n 4 PT n PT n 1 P 定理4 2 22 4 1马尔可夫链与转移概率 证 1 23 4 1马尔可夫链与转移概率 2 3 4 为 1 2 的矩阵表示 24 定理4 3设 Xn n T 为马尔可夫链 则对任意整数i1 i2 in I和n 1 有性质证 25 4 1马尔可夫链与转移概率 例4 1无限制随机游动 qp 101ii 1i 1 一步转移概率 26 4 1马尔可夫链与转移概率 n步转移概率 i经过k步进入j 向右移了x步 向左移了y步则 27 4 1马尔可夫链与转移概率 例4 2赌徒输光问题甲有赌资a元 乙有赌资b元 赌一局输者给赢者1元 无和局 甲赢的概率为p 乙赢的概率为q 1 p 求甲输光的概率 解状态空间I 0 1 2 c c a b qp a 1aa 1 0a b 28 4 1马尔可夫链与转移概率 设ui表示甲从状态i出发转移到状态0的概率 求ua显然u0 1 uc 0 u0表示已知甲输光情形下甲输光的概率 uc表示已知乙输光情形下甲输光的概率 ui pui 1 qui 1 i 1 2 c 1 甲在状态i下输光 甲赢一局后输光或甲输一局后输光 29 4 1马尔可夫链与转移概率 30 4 1马尔可夫链与转移概率 31 4 1马尔可夫链与转移概率 32 4 1马尔可夫链与转移概率 33 4 1马尔可夫链与转移概率 例4 3天气预报问题RR表示连续两天有雨 记为状态0NR表示第1天无雨第2天有雨 记为状态1RN表示第1天有雨第2天无雨 记为状态2NN表示连续两天无雨 记为状态3p00 P R今R明 R昨R今 P R明 R昨R今 0 7p01 P N今R明 R昨R今 0p02 P R今N明 R昨R今 P N明 R昨R今 0 3p03 P N今N明 R昨R今 0 34 4 1马尔可夫链与转移概率 类似地得到其他转移概率 于是转移概率矩阵为若星期一 星期二均下雨 求星期四下雨的概率 35 4 1马尔可夫链与转移概率 星期四下雨的情形如右 星期四下雨的概率2步转移概率矩阵为 36 4 1马尔可夫链与转移概率 例4 4具有吸收壁和反射壁的随机游动状态空间 1 2 3 4 1为吸收壁 4为反射壁状态转移图状态转移矩阵 37 4 2马尔可夫链的状态分类 Xn n 0 是离散马尔可夫链 pij为转移概率 i j I I 0 1 2 为状态空间 pj j I 为初始分布定义4 7状态i的周期d d G C D n 0 最大公约数greatestcommondivisor 如果d 1 就称i为周期的 如果d 1 就称i为非周期的 38 4 2马尔可夫链的状态分类 例4 5设马尔可夫链的状态空间I 1 2 9 转移概率如下图从状态1出发再返回状态1的可能步数为T 4 6 8 10 T的最大公约数为2 从而状态1的周期为2 39 4 2马尔可夫链的状态分类 注 1 如果i有周期d 则对一切非零的n n 0modd 有 若 则n 0modd 2 对充分大的n 引理4 1 例题中当n 1时 当n 0时 40 4 2马尔可夫链的状态分类 例4 6状态空间I 1 2 3 4 转移概率如图 状态2和状态3有相同的周期d 2 但状态2和状态3有显著的区别 当状态2转移到状态3后 再不能返回到状态2 状态3总能返回到状态3 这就要引入常返性概念 41 4 2马尔可夫链的状态分类 由i出发经n步首次到达j的概率 首达概率 规定由i出发经有限步终于到达j的概率 42 4 2马尔可夫链的状态分类 若fii 1 称状态i为常返的 若fii 1 称状态i为非常返的i为非常返 则以概率1 fii不返回到ii为常返 则构成一概率分布 期望值表示由i出发再返回到i的平均返回时间 定义4 8 43 4 2马尔可夫链的状态分类 若 i 则称常返态i为正常返的 若 I 则称常返态i为零常返的 非周期的正常返态称为遍历状态 首达概率与n步转移概率有如下关系式定理4 4对任意状态i j及1 n 有 定义4 9 44 4 2马尔可夫链的状态分类 证 45 4 2马尔可夫链的状态分类 引理4 2周期的等价定义G C D G C D例4 7设马尔可夫链的状态空间I 1 2 3 转移概率矩阵为求从状态1出发经n步转移首次到达各状态的概率 46 4 2马尔可夫链的状态分类 解状态转移图如下 首达概率为 47 4 2马尔可夫链的状态分类 同理可得 48 4 2马尔可夫链的状态分类 以下讨论常返性的判别与性质数列的母函数与卷积 an n 0 为实数列 母函数 bn n 0 为实数列 母函数则 an 与 bn 的卷积的母函数 49 4 2马尔可夫链的状态分类 定理4 5状态i常返的充要条件为如i非常返 则证 规定 则由定理4 4 50 4 2马尔可夫链的状态分类 51 4 2马尔可夫链的状态分类 对0 s 1 52 4 2马尔可夫链的状态分类 53 4 2马尔可夫链的状态分类 定理4 6设i常返且有周期为d 则其中 i为i的平均返回时间 当 i 时推论设i常返 则 1 i零常返 2 i遍历 54 4 2马尔可夫链的状态分类 证 1 i零常返 i 由定理4 6知 对d的非整数倍数的n 从而子序列i是零常返的 55 4 2马尔可夫链的状态分类 2 子序列所以d 1 从而i为非周期的 i是遍历的 i是遍历的 d 1 i 56 4 2马尔可夫链的状态分类 状态的可达与互通状态i可达状态j i j 存在n 0 使状态i与状态j互通 i j i j且j I定理4 7可达关系与互通关系都具有传递性 即 1 若i j j k 则i k 2 若i j j k 则i k 57 4 2马尔可夫链的状态分类 证 1 i j 存在l 0 使j k 存在m 0 使由C K方程所以i k 2 由 1 直接推出 58 4 2马尔可夫链的状态分类 定理4 8如i j 则 1 i与j同为常返或非常返 如为常返 则它们同为正常返或零常返 2 i与j有相同的周期 59 4 2马尔可夫链的状态分类 例4 8设马氏链 Xn 的状态空间为I 0 1 2 转移概率为考察状态0的类型 60 4 2马尔可夫链的状态分类 可得出0为正常返的由于 所以0的周期为d 10为非周期的 从而为遍历状态对于其它状态i 由于i 0 所以也是遍历的 61 4 2马尔可夫链的状态分类 例4 9对无限制随机游动由斯特林近似公式可推出 1 当且仅当p q 1 2时 4pq 1 62 4 2马尔可夫链的状态分类 状态i是常返的状态i是零常返的 63 4 2马尔可夫链的状态分类 2 当且仅当p q 4pq 1状态i是非常返的 64 4 3状态空间的分解 定义4 10状态空间I的子集C称为闭集 如对任意i C及k C都有pik 0 闭集C称为不可约的 如C的状态互通 马氏链 Xn 称为不可约的 如其状态空间不可约引理4 3C是闭集的充要条件为对i C及k C都有 65 4 3状态空间的分解 证充分性显然成立必要性 数学归纳法 设C为闭集 由定义当n 1时结论成立设n m时 i C及k C 则注 如pii 1 称状态i为吸收的 等价于单点集 i 为闭集 66 4 3状态空间的分解 例4 10设马氏链 Xn 的状态空间为I 1 2 3 4 5 转移概率矩阵为状态3是吸收的 故 3 是闭集 1 4 1 3 4 1 2 3 4 都是闭集 其中 3 1 4 是不可约的 I含有闭子集 故 Xn 不是不可约的链 67 4 3状态空间的分解 例4 11无限制随机游动为不可约马氏链 各状态的周期为2 当p q 1 2时 是零常返的 当p q时 是非常返的 68 4 3状态空间的分解 定理4 9任一马氏链的状态空间I 可唯一地分解成有限个或可列个互不相交的子集D C1 C2 之和 使得 1 每一Cn是常返态组成的不可约闭集 2 Cn中的状态同类型 或全是正常返 或全是零常返 它们有相同的周期 且fij 1 i j Cn 3 D由全体非常返态组成 自Cn中状态不能到达D中的状态 69 4 3状态空间的分解 例4 12马氏链的状态空间I 1 2 3 4 5 6 状态转移矩阵为分解此链并指出各状态的常返性及周期性 70 4 3状态空间的分解 解由状态转移图知可见1为正常返状态且周期为3 含1的基本常返闭集为C1 k 1 k 1 3 5 从而状态3及5也为正常返状态且周期为3 同理可知6为正常返状态 6 3 2 周期为1 含6的基本常返闭集为C2 k 6 k 2 6 可见2 6为遍历状态 71 4 3状态空间的分解 于是I可分解为I D C1 C2 4 1 3 5 2 6 定义4 11称矩阵A aij 为随机矩阵 若显然k步转移矩阵为随机矩阵 72 4 3状态空间的分解 引理4 4设C为闭集 G是C上所得的k步转移子矩阵 则G仍是随机矩阵 证任取i C 由引理4 3有从而且 故是随机矩阵 73 4 3状态空间的分解 注 对I的一个闭子集 可考虑C上的原马氏链的子马氏链 其状态空间为C 转移矩阵为G pij i j C是原马氏链的转移矩阵为P pij i j I的子矩阵 74 4 3状态空间的分解 定理4 10周期为d的不可约马氏链 其状态空间C可唯一地分解为d个互不相交的子集之和 即且使得自Gr中任一状态出发 经一步转移必进入Gr 1中 Gd G0 注 任取一状态i 对每一r 0 1 d 1定义集 75 4 3状态空间的分解 例4 13设不可约马氏链的状态空间为C 1 2 3 4 5 6 转移矩阵为 76 4 3状态空间的分解 由状态转移图可知各状态的周期d 3 固定状态i 1 令故C G0 G1 G2 1 4 6 3 5 2 此在C中的运动如下图所示 77 4 3状态空间的分解 78 4 3状态空间的分解 定理4 11设 Xn n 0 是周期为d的不可约马氏链 则在定理4 10的结论下有 1 如只在0 d 2d 上考虑 Xn 即得一新马氏链 Xnd 其转移矩阵 对此新链 每一Gr是不可约闭集 且Gr中的状态是非周期的 2 如原马氏链 Xn 常返 则新马氏链 Xnd 也常返 79 4 3状态空间的分解 例4 14设 Xn 为例4 13中的马氏链 已知d 3 则 Xnd n 0 的转移矩阵为 80 4 3状态空间的分解 由子链 X3n 的状态转移图可知G0 1 4 6 G1 3 5 G2 2 各形成不可约闭集 周期为1 81 4 4渐近性质与平稳分布 考虑渐近性质定理4 12如j非常返或零常返 则证若j非常返 则由定理4 5 从而若j零常返 则由定理4 6推论 82 4 4渐近性质与平稳分布 由定理4 4 对N n 有固定N 先令n 则 83 4 4渐近性质与平稳分布 84 4 4渐近性质与平稳分布 推论1有限状态的马氏链 不可能全是非常返状态 也不可能含有零常返状态 从而不可约的有限状态的马氏链必为正常返的 证设I 0 1 N 如I全是非常返状态 则对任意i j I 由定理4 12知故矛盾 85 4 4渐近性质与平稳分布 如I含有零常返状态i 则C j i j 是有限不可约闭集 由定理4 9知 C中均为零常返状态 由定理4 12知 由引理4 4知所以 86 4 4渐近性质与平稳分布 推论2如马氏链有一个零常返状态 则必有无限多个零常返状态 证设i为零常返状态 则C j i j 是不可约闭集 C中均为零常返状态 故C不能是有限集 否则 87 4 4渐近性质与平稳分布 当j是正常返状态时 不一定存在 即使存在也可能与i有关 我们考虑 88 4 4渐近性质与平稳分布 定理4 13如j是正常返状态 周期为d 则对任意i及0 r d 1 有证对d的非正整数倍数的n 定理4 4 及设v r md 则v md r 89 4 4渐近性质与平稳分布 于是 对1 N n有固定N 先令n 再令N 由定理4 6可得从而 90 4 4渐近性质与平稳分布 推论设不可约 正常返 周期为d的马氏链 其状态空间为C 则对一切i j C有其中为定理4 10中所给出当d 1时 则对一切i j有 91 4 4渐近性质与平稳分布 定理4 14对任意状态i j有推论如 Xn 不可约 常返 则对任意i j有 92 4 4渐近性质与平稳分布 下面考虑平稳分布设是 Xn n 0 齐次马尔可夫链 状态空间为I 转移概率为pij定义4 12称概率分布 j j I 为马尔可夫链的平稳分布 若 93 4 4渐近性质与平稳分布 注 1 若初始概率分布 pj j I 是平稳分布 则pj pj 1 pj 2 pj n 2 对平稳分布 j j I 有矩阵形式 P n 其中 j P n 94 4 4渐近性质与平稳分布 定理4 15不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布 且此平稳分布就是极限分布推论1有限状态的不可约非周期马尔可夫链必存在平稳分布 推论2若不可约马尔可夫链的所有状态是非常返或零常返 则不存在平稳分布 95 4 4渐近性质与平稳分布 推论3若 j j I 是马尔可夫链的平稳分布 则例4 15设马尔可夫链的转移概率矩阵为求马尔可夫链的平稳分布及各状态的平均返回时间 96 4 4渐近性质与平稳分布 解因为马尔可夫链是不可约非周期有限状态的 所以平稳分布存在 设 1 2 3 则 P 1 2 3 1即各状态的平均返回时间为 97 4 4渐近性质与平稳分布 例4 16设马尔可夫链具有状态空间I 0 1 2 转移概率为pi i 1 pi pii ri pi i 1 qi i 0 其中q0 0 pi qi 0 pi ri qi 1 此马尔可夫链为生灭链 它是不可约的 记a0 1 证此马尔可夫链存在平稳分布的充要条件为 98 4 4渐近性质与平稳分布 证设 j j I 是平稳分布 99 4 4渐近性质与平稳分布 100 4 4渐近性质与平稳分布 例4 17设马尔可夫链转移概率矩阵为求每一个不可约闭集的平稳分布 101 4 4渐近性质与平稳分布 解从状态转移图看出 状态空间可分解为两个不可约常返闭集C1 2 3 4 和C2 5 6 7 一个非常返集N 1 在常返集上求平稳分布 102 4 4渐近性质与平稳分布 在C1上 对应的转移概率矩阵为C1上的平稳分布为 0 0 4 0 2 0 4 0 0 0 同理可求得C2上的平稳分布为 0 0 0 0 1 3 1 3 1 3 103 4 5连续时间马尔可夫链 定义4 13设随机过程 X t t 0 状态空间I 0 1 2 若对任意0 t1 t2 tn 1及非负整数i1 i2 in 1 有P X tn 1 in 1 X t1 i1 X t2 i2 X tn in P X tn 1 in 1 X tn in 则称 X t t 0 为连续时间马尔可夫链 104 转移概率 在s时刻处于状态i 经过时间t后转移到状态j的概率pij s t P X s t j X s i 定义4 14齐次转移概率 与起始时刻s无关 只与时间间隔t有关 pij s t pij t 此时有转移概率矩阵P t pij t i j I t 0 105 4 5连续时间马尔可夫链 记 i为过程在状态转移之前停留在状态i的时间 则对s t 0有 1 2 i服从指数分布证 1 事实上 106 4 5连续时间马尔可夫链 s s t 0 i i i i t i 107 4 5连续时间马尔可夫链 108 4 5连续时间马尔可夫链 2 设 i的分布函数为F x x 0 则生存函数G x 1 F x 由此可推出G x 为指数函数 G x e x 则F x 1 G x 1 e x为指数分布函数 109 4 5连续时间马尔可夫链 过程在状态转移之前处于状态i的时间 i服从指数分布 1 当 i 时 状态i的停留时间 i超过x的概率为0 则称状态i为瞬时状态 2 当 i 0时 状态i的停留时间 i超过x的概率为1 则称状态i为吸收状态 110 4 5连续时间马尔可夫链 定理4 16齐次马尔可夫过程的转移概率具有下列性质 1 pij t 0 2 3 证由概率的定义 1 2 显然成立 下证 3 111 4 5连续时间马尔可夫链 112 4 5连续时间马尔可夫链 注 此为转移概率的正则性条件 113 4 5连续时间马尔可夫链 定义4 15 1 初始概率 2 绝对概率 3 初始分布 4 绝对分布定理4 17齐次马尔可夫过程的绝对概率及有限维概率分布具有下列性质 114 4 5连续时间马尔可夫链 1 pj t 0 2 3 4 5 115 4 5连续时间马尔可夫链 例4 18证明泊松过程 X t t 0 为连续时间齐次马尔可