《马尔可夫链》PPT课件.ppt

第四章马尔可夫链 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表示将来 马尔可夫过程表明 在已知现在状态的条件下 将来所处的状态与过去状态无关 4 1马尔可夫链与转移概率 常见马尔可夫过程通常有三类 1 时间 状态都是离散的 称为马尔可夫链 2 时间连续 状态离散的 称为连续时间马尔可夫链 3 时间 状态都是连续的 称为马尔可夫过程 时间离散 状态连续的马尔可夫过程 通常用泛函中二元函数的范数进行研究 随机过程 Xn n T 参数T 0 1 2 状态空间I i0 i1 i2 定义若随机过程 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 为马尔可夫链 简称马氏链 4 1马尔可夫链与转移概率 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 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 确定 4 1马尔可夫链与转移概率 定义称条件概率pij n P Xn 1 j Xn i 为马尔可夫链 Xn n T 在时刻n的一步转移概率 简称转移概率 其中i j I 定义若对任意的i j I 马尔可夫链 Xn n T 的转移概率pij n 与n无关 则称马尔可夫链是齐次的 并记pij n 为pij 齐次马尔可夫链具有平稳转移概率 状态空间I 1 2 3 一步转移概率为 4 1马尔可夫链与转移概率 转移概率性质 1 2 P称为随机矩阵 4 1马尔可夫链与转移概率 例4 1赌博问题 甲乙二人进行一系列赌博 甲有a元 乙的赌本无限 每赌一局输者给赢者1元 没有和局 如果甲输光 再输则赌本为负 设在每一局中 甲赢的概率为p 输的概率为q 1 p 设Xn表示第n次赌博结束后甲的赌本 则Xn n 1是马尔科夫链 求Xn的转移矩阵 4 1马尔可夫链与转移概率 例4 1无限制随机游动 qp 101i 1ii 1 一步转移概率 4 1马尔可夫链与转移概率 n步转移概率 i经过k步进入j 向右移了x步 向左移了y步则 4 1马尔可夫链与转移概率 例4 4具有吸收壁和反射壁的随机游动状态空间 1 2 3 4 1为吸收壁 4为反射壁状态转移图状态转移矩阵 4 1马尔可夫链与转移概率 定义称条件概率 P Xm n j Xm i 为马尔可夫链 Xn n T 的n步转移概率 i j I m 0 n 1 n步转移矩阵其中P n 也为随机矩阵 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 4 1马尔可夫链与转移概率 证 1 4 1马尔可夫链与转移概率 2 在 1 中令l 1 k k1 得由此可递推出公式 3 矩阵乘法 4 由 3 推出说明 1 此为C K方程 切普曼 柯尔莫哥洛夫 2 n步转移概率由一步转移概率确定 n步转移概率矩阵由一步转移概率矩阵确定 n次幂 4 1马尔可夫链与转移概率 初始概率绝对概率初始分布绝对分布初始概率向量绝对概率向量 定义 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 例如 设马氏链的状态空间I 1 2 那么时刻n的绝对概率分布应满足 PT n p1 n p2 n PT n PT 0 P n 4 1马尔可夫链与转移概率 证 1 4 1马尔可夫链与转移概率 2 3 4 为 1 2 的矩阵表示 4 1马尔可夫链与转移概率 定理4 3设 Xn n T 为马尔可夫链 则对任意整数i1 i2 in I和n 1 有性质证 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 4 1马尔可夫链与转移概率 设ui表示甲从状态i出发转移到状态0的概率 求ua显然u0 1 uc 0 u0表示已知甲输光情形下甲输光的概率 uc表示已知乙输光情形下甲输光的概率 ui pui 1 qui 1 i 1 2 c 1 甲在状态i下输光 甲赢一局后输光或甲输一局后输光 4 1马尔可夫链与转移概率 4 1马尔可夫链与转移概率 4 1马尔可夫链与转移概率 4 1马尔可夫链与转移概率 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 4 1马尔可夫链与转移概率 类似地得到其他转移概率 于是转移概率矩阵为若星期一 星期二均下雨 求星期四下雨的概率 4 1马尔可夫链与转移概率 星期四下雨的情形如右 星期四下雨的概率2步转移概率矩阵为 4 2马尔可夫链的状态分类 Xn n 0 是离散马尔可夫链 pij为转移概率 i j I I 0 1 2 为状态空间 pj j I 为初始分布定义4 3状态i的周期d d G C D n 0 最大公约数greatestcommondivisor 如果d 1 就称i为周期的 如果d 1 就称i为非周期的 4 2马尔可夫链的状态分类 例4 6设马尔可夫链的状态空间I 1 2 9 转移概率如下图从状态1出发再返回状态1的可能步数为T 4 6 8 10 T的最大公约数为2 从而状态1的周期为2 4 2马尔可夫链的状态分类 注 1 如果i有周期d 则对一切非零的n n 0modd 有 若 则n 0modd 2 对充分大的n 引理4 1 例题中当n 1时 当n 1时 4 2马尔可夫链的状态分类 例4 7状态空间I 1 2 3 4 转移概率如图 状态2和状态3有相同的周期d 2 但状态2和状态3有显著的区别 当状态2转移到状态3后 再不能返回到状态2 状态3总能返回到状态3 这就要引入常返性概念 4 2马尔可夫链的状态分类 由i出发经n步首次到达j的概率 首达概率 规定由i出发经有限步终于到达j的概率 4 2马尔可夫链的状态分类 若fii 1 称状态i为常返的 若fii 1 称状态i为非常返的i为非常返 则以概率1 fii不返回到ii为常返 则构成一概率分布 期望值表示由i出发再返回到i的平均返回时间 定义 4 2马尔可夫链的状态分类 若 i 则称常返态i为正常返的 若 i 则称常返态i为零常返的 非周期的正常返态称为遍历状态 例 判断下面马氏链各状态的类型 定义 设i为常返 4 2马尔可夫链的状态分类 引理4 2周期的等价定义G C D G C D例4 8设马尔可夫链的状态空间I 1 2 3 转移概率矩阵为求从状态1出发经n步转移首次到达各状态的概率 4 2马尔可夫链的状态分类 解状态转移图如下 首达概率为 4 2马尔可夫链的状态分类 同理可得 4 2马尔可夫链的状态分类 首达概率与n步转移概率有如下关系式定理4 4对任意状态i j及1 n 有 4 2马尔可夫链的状态分类 证 P A B C P B A C P A C 例 已知马氏链转移图如下 求从状态1出发再返回1的n步转移概率 n 1 2 8 4 2马尔可夫链的状态分类 定理4 5状态i常返的充要条件为如i非常返 则 以下讨论常返性的判别与性质 4 2马尔可夫链的状态分类 数列的母函数与卷积 an n 0 为实数列 母函数 bn n 0 为实数列 母函数则 an 与 bn 的卷积的母函数 4 2马尔可夫链的状态分类 定理4 5状态i常返的充要条件为如i非常返 则证 规定 则由定理4 4 4 2马尔可夫链的状态分类 4 2马尔可夫链的状态分类 对0 s 1 4 2马尔可夫链的状态分类 4 2马尔可夫链的状态分类 定理4 7设i常返且有周期为d 则其中 i为i的平均返回时间 当 i 时推论设i常返 则 1 i零常返 2 i遍历 例 已知马氏链转移图如下 求从状态1出发再返回1的n步转移概率 n 1 2 8 4 2马尔可夫链的状态分类 证 1 i零常返 i 由定理4 7知 对d的非整数倍数的n 从而子序列i是零常返的 4 2马尔可夫链的状态分类 2 子序列所以d 1 从而i为非周期的 i是遍历的 i是遍历的 d 1 i 4 2马尔可夫链的状态分类 例4 10对无限制随机游动由斯特林近似公式可推出 1 当且仅当p q 1 2时 4pq 1 4 2马尔可夫链的状态分类 状态i是常返的状态i是零常返的 4 2马尔可夫链的状态分类 2 当且仅当p q 4pq 1状态i是非常返的 4 1马尔可夫链与转移概率 例4 1无限制随机游动 p 101i 1ii 1 一步转移概率 p p p q q q q 状态的可达与互通状态i可达状态j i j 存在n 0 使状态i与状态j互通 i j i j且j i定理4 8可达关系与互通关系都具有传递性 即 1 若i j j k 则i k 2 若i j j k 则i k 4 3状态空间的分解 4 2马尔可夫链的状态分类 证 1 i j 存在l 0 使j k 存在m 0 使由C K方程所以i k 2 由 1 直接推出 4 2马尔可夫链的状态分类 定理4 9如i j 则 1 i与j同为常返或非常返 如为常返 则它们同为正常返或零常返 2 i与j有相同的周期 4 2马尔可夫链的状态分类 例4 9设马氏链 Xn 的状态空间为I 0 1 2 转移概率为考察状态0的类型 4 2马尔可夫链的状态分类 可得出0为正常返的由于 所以0的周期为d 10为非周期的 从而为遍历状态对于其它状态i 由于i 0 所以也是遍历的 4 3状态空间的分解 定义状态空间I的子集C称为闭集 如对任意i C及k C都有pik 0 闭集C称为不可约的 如C的状态互通 马氏链 Xn 称为不可约的 如其状态空间不可约引理4 4C是闭集的充要条件为对i C及k C都有 4 3状态空间的分解 证充分性显然成立必要性 数学归纳法 设C为闭集 由定义当n 1时结论成立设n m时 i C及k C 则注 如pii 1 称状态i为吸收的 等价于单点集 i 为闭集 4 3状态空间的分解 例4 11设马氏链 Xn 的状态空间为I 1 2 3 4 5 转移概率矩阵为状态3是吸收的 故 3 是闭集 1 4 1 3 4 1 2 3 4 都是闭集 其中 3 1 4 是不可约的 I含有闭子集 故 Xn 不是不可约的链 4 3状态空间的分解 例4 12无限制随机游动为不可约马氏链 各状态的周期为2 当p q 1 2时 是零常返的 当p q时 是非常返的 4 3状态空间的分解 定理4 10任一马氏链的状态空间I 可唯一地分解成有限个或可列个互不相交的子集D C1 C2 之和 使得 1 每一Cn是常返态组成的不可约闭集 2 Cn中的状态同类型 或全是正常返 或全是零常返 它们有相同的周期 且fij 1 i j Cn 3 D由全体非常返态组成 自Cn中状态不能到达D中的状态 4 3状态空间的分解 例4 13马氏链的状态空间I 1 2 3 4 5 6 状态转移矩阵为分解此链并指出各状态的常返性及周期性 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为遍历状态 4 3状态空间的分解 于是I可分解为I D C1 C2 4 1 3 5 2 6 定义4 10称矩阵A aij 为随机矩阵 若显然k步转移矩阵为随机矩阵 4 3状态空间的分解 引理4 5设C为闭集 G是C上所得的k步转移子矩阵 则G仍是随机矩阵 证任取i C 由引理4 4有从而且 故是随机矩阵 4 3状态空间的分解 注 对I的一个闭子集 可考虑C上的原马氏链的子马氏链 其状态空间为C 转移矩阵为G pij i j C是原马氏链的转移矩阵为P pij i j I的子矩阵 4 3状态空间的分解 定理4 11周期为d的不可约马氏链 其状态空间C可唯一地分解为d个互不相交的子集之和 即且使得自Gr中任一状态出发 经一步转移必进入Gr 1中 Gd G0 注 任取一状态i 对每一r 0 1 d 1定义集 例 已知马氏链转移图如下 求从状态1出发再返回1的n步转移概率 n 1 2 8 4 3状态空间的分解 例4 14设不可约马氏链的状态空间为C 1 2 3 4 5 6 转移矩阵为 4 3状态空间的分解 4 3状态空间的分解 由状态转移图可知各状态的周期d 3 固定状态i 1 令故C G0 G1 G2 1 4 6 3 5 2 4 3状态空间的分解 定理4 12设 Xn n 0 是周期为d的不可约马氏链 则在定理4 11的结论下有 1 如只在0 d 2d 上考虑 Xn 即得一新马氏链 Xnd 其转移矩阵 对此新链 每一Gr是不可约闭集 且Gr中的状态是非周期的 2 如原马氏链 Xn 常返 则新马氏链 Xnd 也常返 4 3状态空间的分解 例4 15设 Xn 为例4 14中的马氏链 已知d 3 则 Xnd n 0 的转移矩阵为 4 3状态空间的分解 由子链 X3n 的状态转移图可知G0 1 4 6 G1 3 5 G2 2 各形成不可约闭集 周期为1 4 3状态空间的分解 4 4渐近性质与平稳分布 考虑渐近性质定理4 13如j非常返或零常返 则证若j非常返 则由定理4 5 从而若j零常返 则由定理4 7推论 4 4渐近性质与平稳分布 由定理4 4 对N n 有固定N 先令n 则 4 4渐近性质与平稳分布 4 4渐近性质与平稳分布 推论1有限状态的马氏链 不可能全是非常返状态 也不可能含有零常返状态 从而不可约的有限状态的马氏链必为正常返的 证设I 0 1 N 如I全是非常返状态 则对任意i j I 由定理4 13知故矛盾 4 4渐近性质与平稳分布 如I含有零常返状态i 则C j i j 是有限不可约闭集 由定理4 10知 C中均为零常返状态 由定理4 13知 由引理4 5知所以 4 4渐近性质与平稳分布 推论2如马氏链有一个零常返状态 则必有无限多个零常返状态 证设i为零常返状态 则C j i j 是不可约闭集 C中均为零常返状态 故C不能是有限集 否则 4 4渐近性质与平稳分布 当j是正常返状态时 不一定存在 即使存在也可能与i有关 例如下面的马氏链中 不存在 4 4渐近性质与平稳分布 我们考虑 4 4渐近性质与平稳分布 定理4 14如j是正常返状态 周期为d 则对任意i及0 r d 1 有证对d的非正整数倍数的n 定理4 4 及设v r md 则v md r 4 4渐近性质与平稳分布 于是 对1 N n有固定N 先令n 再令N 由定理4 7可得从而 4 4渐近性质与平稳分布 推论设不可约 正常返 周期为d的马氏链 其状态空间为C 则对一切i j C有其中为定理4 11中所给出当d 1时 则对一切i j有 例 已知马氏链的转移矩阵 P 2 0 51000 49000 42000 5800P 3 0 44700 55300 47400 5260 P 4 0 46590 53410 45780 5422P 8 0 46160 53840 46150 5385 4 4渐近性质与平稳分布 定理4 15对任意状态i j有推论如 Xn 不可约 常返 则对任意i j有 4 4渐近性质与平稳分布 下面考虑平稳分布设是 Xn n 0 齐次马尔可夫链 状态空间为I 转移概率为pij定义称概率分布 j j I 为马尔可夫链的平稳分布 若 例如 设马氏链的状态空间I 1 2 那么平稳分布应满足 1 2 1 2 1 P 4 1马尔可夫链与转移概率 初始概率绝对概率初始分布绝对分布初始概率向量绝对概率向量 定义 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 4 4渐近性质与平稳分布 注 1 若初始概率分布 pj j I 是平稳分布 则p