《第四章马尔可夫链》由会员分享，可在线阅读，更多相关《第四章马尔可夫链（39页珍藏版）》请在金锄头文库上搜索。
1、第四章马尔可夫链 1 马尔可夫性 无后效性 一 马尔可夫链的定义和转移概率 当已知随机过程在时刻所处的状态的条件下 过程 将来 的情况和 过去 的情况无关 过程在t ti 所处的状态与过程在时刻ti以前所处的 这种特性称为马尔可夫性或 无后效性 具有马尔可夫性的随机过程称为马尔可夫过程 状态无关 2020年2月4日星期二 参数和状态都是离散的马尔可夫过程称为马尔 可夫链 2 马尔可夫链的定义和转移概率 马氏链的马尔可夫性可具体描述为 Pij表示处于状态i的过程下一步转移到状态j的概率 2020年2月4日星期二 Pij称为一步转移概率 由所有的一步转移概率构成 的矩阵 称为一步转移概率矩阵 显然
2、有 具有这种平稳转移概率的马尔可夫链称为齐次的 2020年2月4日星期二 例1一维随机游动 游动的概率规则 3 马尔可夫链举例 2020年2月4日星期二 1和5这两点称为反射壁 上面这种游动称为带有两个反射壁的随机游动 理论分析 2020年2月4日星期二 单击图形播放 暂停ESC键退出 一维随机游动的演示 2020年2月4日星期二 一步转移概率 一步转移概率矩阵 2020年2月4日星期二 说明 改变游动的概率规则 随机游动和相应的马氏链 就可得到不同方式的 如果把1改为吸收壁 即一旦到达1点 将永 远留在1点 相应链的转移概率矩阵只需把P的第 一行改成 2020年2月4日星期二 例2取球问题
3、有甲 乙两袋球 开始时甲袋有3只球 乙袋有 则 Xn n 1 2 是一随机过程 2球 以后 每次任取一袋 并从袋中取出一球放入 另一袋 若袋中无球则不取 以Xn表示第n次抽取后甲袋的球数 n 1 2 其一步转移概率矩阵为 且当Xn i时 Xn 1 j的概率只与i有关 与n时刻 I 0 1 2 3 4 5 之前的结果是无关的 从而是一个齐次马氏链 2020年2月4日星期二 2020年2月4日星期二 4 齐次马氏链的性质 定义 记 称为齐次马氏链的初始分布 定理 齐次马氏链完全由其初始分布和一步转移 概率矩阵确定 证 2020年2月4日星期二 5 切普曼 柯尔莫哥洛夫方程 在齐次条件下 可得到n步
4、转移概率 由所有的n步转移概率就可得到n步转移概率矩阵 显然有 2020年2月4日星期二 切普曼 柯尔莫哥洛夫方程 C K方程 对任意的m n 0 有 即n步转移概率矩阵等于一步转移概率矩阵自乘n次 为了数学处理便利 通常规定 2020年2月4日星期二 一步转移概率矩阵为 例3 2020年2月4日星期二 解 先求出二步转移概率矩阵 于是 2020年2月4日星期二 2020年2月4日星期二 解 例4 2020年2月4日星期二 2020年2月4日星期二 2020年2月4日星期二 课堂练习 2020年2月4日星期二 解 3 2020年2月4日星期二 设 Xn n 0 是齐次马尔可夫链 pij为转移概
5、率 i j I I 1 2 为状态空间 pi i I 为初始分布 状态i的周期d d G C D n n 1 0 最大公约数greatestcommondivisor 如果d 1 就称i为周期的 如果d 1 就称i为非周期的 定义 二 马尔可夫链的状态分类 2020年2月4日星期二 例5设马尔可夫链的状态空间I 1 2 3 4 转移概率如下图 易得状态2和3有相同的周期d 2 但是从状态3出发 经两步必定返回状态3 而从状态2出发一旦转移 到状态3后再也不能返回状态2 为了区别这两种状态 下面引入常返性概念 2020年2月4日星期二 由状态i出发经n步首次到达j的概率 首达概率 规定 由i出发
6、经有限步终于到达j的概率 2020年2月4日星期二 若fii 1 称状态i为常返的 若fii 1 称状态i为非常返的 定义 注 表示由i出发再返回到i的平均返回时间 步数 1 若状态i为非常返的 则由该状态出发将 以1 fii的概率永不返回 2 若状态i为常返的 则构成一概率分布 其期望值为 2020年2月4日星期二 若 i 则称常返态i为正常返的 若 i 则称常返态i为零常返的 非周期的正常返态称为遍历状态 设i为常返态 定义 例 判断下面马氏链各状态的类型 2020年2月4日星期二 马氏链状态分类图 2020年2月4日星期二 如果存在n 0 使 称自状态i可达状态j 状态的可达与互通 并记
7、为 注 可达关系与互通关系都具有传递性 1 若i j j k 则i k 2 若i j j k 则i k 2020年2月4日星期二 定理若i j 则 1 i与j同为常返或非常返 如为常返 则它们同为正常返或零常返 2 i与j有相同的周期 2020年2月4日星期二 例6设马氏链 Xn 的状态空间I 0 1 2 转移概率为 试讨论各状态的常返性和周期性 解 根据题意作出状态转移图如下 2020年2月4日星期二 从而是遍历状态 对于其它状态i 由于i 0 故也都是遍历状态 可见0是正常返态 所以0为非周期的 对互通状态的识别 只需对最简单的状态判断即可 2020年2月4日星期二 状态空间I的子集C称为
8、闭集 如对任意i C及k C都有pik 0 如果闭集C的状态互通 称C为不可约的 如果马氏链 Xn 的状态空间不可约 称其为不可约的 三 状态空间的分解 注 1 闭集的意思是自C的内部不能到达C的外部 2 如果pii 1 则称状态i为吸收的 定义 2020年2月4日星期二 例7设马氏链 Xn 的状态空间为I 1 2 3 4 5 转移概率矩阵为 状态3是吸收的 故 3 是闭集 1 4 1 3 4 1 2 3 4 其中 3 1 4 是不可约的 I含有闭子集 故 Xn 不是不可约的链 都是闭集 2020年2月4日星期二 任一马氏链的状态空间I 可唯一地分解成有限个或可列个互不相交的子集D C1 C2
9、 之和 使得 1 每一Cn是常返态组成的不可约闭集 2 Cn中的状态同类型 或全是正常返 或全是零常返 它们有相同的周期 且fij 1 i j Cn 3 D由全体非常返态组成 自Cn中状态不能到达D中的状态 由于自常返态只能到达常返态 因此I中全体常返 态组成一闭集C 在C中根据互通关系可进一步分类 分解定理 2020年2月4日星期二 例8马氏链的状态空间I 1 2 3 4 5 6 转移概率矩阵 其中Cn是由常返态组成的不可约闭集 称为 基本常返闭集 试分解此链并指出各状态的常返性及周期性 2020年2月4日星期二 同理对状态6 解 由状态转移图知 又状态3 5和1互通 C1 1 3 5 故状态3与5也是周期为3的 可见1为正常返态且周期为3 正常返态 包含1的基本常返闭集为 故f11 1 故f66 1 2020年2月4日星期二 于是I可分解为I D C1 C2 C2 2 6 非周期的正常返态 因此状态6为 即遍历态 又状态2和6互通 故状态2也是遍历态 包含6的基本常返闭集为 4 1 3 5 2 6 从而 4是一个非常返态 2020年2月4日星期二 设状态空间为I 1 2 3 4 的马氏链的转移概率矩阵 1 画出状态转移图 2 对状态进行分类 3 对状态空间进行分解 练习题
