马尔科夫链例题整理PPT课件.ppt

若表示质点在时刻n所处的位置 分析它的概率特性 例1 直线上带吸收壁的随机游动 醉汉游动 设一质点在线段 1 5 上随机游动 每秒钟发生一次随机游动 移动的规则是 1 若移动前在2 3 4处 则均以概率向左或向右移动一单位 2 若移动前在1 5处 则以概率1停留在原处 质点在1 5两点被 吸收 前言 马尔可夫过程的描述分类 1 首页 无记忆性 未来处于某状态的概率特性只与现在状态有关 而与以前的状态无关 这种特性叫无记忆性 无后效性 例4布朗运动 2 若表示质点在时刻n所处的位置 求一步转移概率 引例 例1直线上带吸收壁的随机游动 醉汉游动 设一质点在线段 1 5 上随机游动 每秒钟发生一次随机游动 移动的规则是 1 若移动前在2 3 4处 则均以概率向左或向右移动一单位 2 若移动前在1 5处 则以概率1停留在原处 质点在1 5两点被 吸收 一步转移概率矩阵的计算 3 首页 有两个吸收壁的随机游动 其一步转移矩阵为 状态空间I 1 2 3 4 5 参数集T 1 2 3 4 例2 带有反射壁的随机游动 设随机游动的状态空间I 0 1 2 移动的规则是 1 若移动前在0处 则下一步以概率p向右移动一个单位 以概率q停留在原处 p q 1 2 若移动前在其它点处 则均以概率p向右移动一个单位 以概率q向左移动一个单位 设表示在时刻n质点的位置 则 是一个齐次马氏链 写出其一步转移概率 首页 5 首页 6 首页 7 例3 一个圆周上共有N格 按顺时针排列 一个质点在该圆周上作随机游动 移动的规则是 质点总是以概率p顺时针游动一格 以概率逆时针游动一格 试求转移概率矩阵 首页 8 4 一个质点在全直线的整数点上作随机游动 移动的规则是 以概率p从i移到i 1 以概率q从i移到i 1 以概率r停留在i 且 试求转移概率矩阵 首页 9 5 设袋中有a个球 球为黑色的或白色的 今随机地从袋中取一个球 然后放回一个不同颜色的球 若在袋里有k个白球 则称系统处于状态k 试用马尔可夫链描述这个模型 称为爱伦菲斯特模型 并求转移概率矩阵 解这是一个齐次马氏链 其状态空间为 I 0 1 2 a 一步转移矩阵是 首页 10 练习题 扔一颗色子 若前n次扔出的点数的最大值为j 就说试问是否为马氏链 求一步转移概率矩阵 I 1 2 3 4 5 6 首页 11 12 例1 甲 乙两人进行比赛 设每局比赛中甲胜的概率是p 乙胜的概率是q 和局的概率是 设每局比赛后 胜者记 1 分 负者记 1 分 和局不记分 当两人中有一人获得2分结束比赛 以表示比赛至第n局时甲获得的分数 1 写出状态空间 3 问在甲获得1分的情况下 再赛二局可以结束比赛的概率是多少 首页 13 解 1 记甲获得 负2分 为状态1 获得 负1分 为状态2 获得 0分 为状态3 获得 正1分 为状态4 获得 正2分 为状态5 则状态空间为 一步转移概率矩阵 首页 14 2 二步转移概率矩阵 首页 15 3 从而结束比赛的概率 从而结束比赛的概率 所以题中所求概率为 首页 16 分析 例2赌徒输光问题 赌徒甲有资本a元 赌徒乙有资本b元 两人进行赌博 每赌一局输者给赢者1元 没有和局 直赌至两人中有一人输光为止 设在每一局中 甲获胜的概率为p 乙获胜的概率为 求甲输光的概率 这个问题实质上是带有两个吸收壁的随机游动 从甲的角度看 他初始时刻处于a 每次移动一格 向右移 即赢1元 的概率为p 向左移 即输1元 的概率为q 如果一旦到达0 即甲输光 或a b 即乙输光 这个游动就停止 这时的状态空间为 0 1 2 c c a b 现在的问题是求质点从a出发到达0状态先于到达c状态的概率 首页 17 考虑质点从j出发移动一步后的情况 解 同理 根据全概率公式有 这一方程实质上是一差分方程 它的边界条件是 首页 18 于是 设 则可得到两个相邻差分间的递推关系 于是 欲求 先求 需讨论r 首页 19 当 而 两式相比 首页 20 故 当 而 因此 故 首页 21 用同样的方法可以求得乙先输光的概率 由以上计算结果可知 首页 22 例3排队问题 顾客到服务台排队等候服务 在每一个服务周期中只要服务台前有顾客在等待 就要对排在前面的一位提供服务 若服务台前无顾客时就不能实施服务 则有 求其转移矩阵 在第n周期已有一个顾客在服务 到第n 1周期已服务完毕 23 解 先求出转移概率 首页 24 所以转移矩阵为 首页 25 证 26 定理4 3马尔科夫链的有限维分布 27 练习 马氏链的状态空间I 1 2 3 初始概率为 28 例4 市场占有率预测 设某地有1600户居民 某产品只有甲 乙 丙3厂家在该地销售 经调查 8月份买甲 乙 丙三厂的户数分别为480 320 800 9月份里 原买甲的有48户转买乙产品 有96户转买丙产品 原买乙的有32户转买甲产品 有64户转买丙产品 原买丙的有64户转买甲产品 有32户转买乙产品 用状态1 2 3分别表示甲 乙 丙三厂 试求 1 转移概率矩阵 2 9月份市场占有率的分布 3 12月份市场占有率的分布 29 解 1 E 1 2 3 状态1 2 3分别表示甲 乙 丙的用户 一步转移概率矩阵为 2 以1600除8月份甲 乙 丙的户数 得初始概率分布 即初始市场占有率 30 所以9月份市场占有率分布为 3 12月份市场占有率分布为 31 2020 1 8 32 例1 其一步转移矩阵为 试研究各状态间的关系 并画出状态传递图 解 先按一步转移概率 画出各状态间的传递图 首页 33 由图可知 状态0可到达状态1 经过状态1又可到达状态2 反之 从状态2出发经状态1也可到达状态0 因此 状态空间I的各状态都是互通的 又由于I的任意状态i i 0 1 2 不能到达I以外的任何状态 所以I是一个闭集 而且I中没有其它闭集 所以此马氏链是不可约的 首页 34 例2 其一步转移矩阵为 试讨论哪些状态是吸收态 闭集及不可约链 解 先按一步转移概率 画出各状态间的传递图 首页 35 闭集 由图可知 状态3为吸收态 且 闭集 闭集 其中是不可约的 又因状态空间I有闭子集 故此链为非不可约链 首页 36 3 常返态与瞬时态 则称状态i为常返态 则称状态i为瞬时态 注 常返 一词 有时又称 返回 常驻 或 持久 瞬时 也称 滑过 或 非常返 定理4 定理5 定理6 如果i为常返态 且 则j也是常返态 定理7 所有常返态构成一个闭集 37 5 正常返态与零常返态 平均返回时间 从状态i出发 首次返回状态i的平均时间 称为状态i平均返回时间 根据的值是有限或无限 可把常返态分为两类 设i是常返态 则称i为正常返态 则称i为零常返态 首页 38 例 其一步转移矩阵如下 是对I进行分解 I可分解为 C1 2 3 4 C2 5 6 7 两个闭集及N 1 即I N C1 C2 39 用极限判断状态类型的准则 2 i是零常返态 3 i是正常返态 1 i是瞬时态 且 且 首页 40 例3 转移矩阵 试对其状态分类 解 按一步转移概率 画出各状态间的传递图 首页 41 从图可知 此链的每一状态都可到达另一状态 即4个状态都是相通的 考虑状态1是否常返 于是状态1是常返的 又因为 所以状态1是正常返的 此链所有状态都是正常返的 42 三 状态的周期与遍历 1 周期状态 对于任意的 令 其中GCD表示最大公约数 则称为周期态 则称为非周期态 定理11 2 遍历状态 若状态i是正常返且非周期 则称i为遍历状态 43 例4 设马氏链的状态空间I 0 1 2 转移概率为 试讨论各状态的遍历性 解 根据转移概率作出状态传递图 首页 44 从图可知 对任一状态都有 故由定理可知 I中的所以状态都是相通的 因此只需考虑状态0是否正常返即可 故 从而0是常返态 又因为 所以状态0为正常返 又由于 故状态0为非周期的 从而状态0是遍历的 故所有状态i都是遍历的 45 例5 设马氏链的状态空间I 1 2 3 4 其一步转移矩阵为 解 试对其状态分类 按一步转移概率 画出各状态间的传递图 它是有限状态的马氏链 故必有一个常返态 又链中四个状态都是互通的 因此 所有状态都是常返态 这是一个有限状态不可约的马氏链 可继续讨论是否为正常返态 46 可讨论状态1 47 状态1是常返态 状态1是正常返态 所以 全部状态都是正常返态 首页 48 例1 其一步转移矩阵为 试证此链具有遍历性 并求平稳分布和各状态的平均返回时间 解 由于 首页 49 所以 因此 该马氏链具有遍历性 解得 所以马氏链的平稳分布为 各状态的平均返回时间 50 例2 设有6个球 其中2个红球 4个白球 分放于甲 乙两个盒子中 每盒放3个 今每次从两个盒中各任取一球并进行交换 以表示开始时甲盒中红球的个数 表示经n次交换后甲盒中的红球数 1 求马氏链 的转移概率矩阵 2 证明 是遍历的 3 求 4 求 首页 51 解 其一步转移矩阵为 甲 乙 红球0白球3 红球2白球1 红球1白球2 红球1白球2 红球2白球1 红球0白球3 52 由状态传递图 2 由于它是一个有限马氏链 故必有一个常返态 又链中三个状态0 1 2都相通 所以每个状态都是常返态 所以是一个不可约的有限马氏链 从而每个状态都是正常返的 所以此链为非周期的 故此链是不可约非周期的正常返链 即此链是遍历的 首页 53 也可以利用定理1证明遍历性 首页 54 解之得 故得 首页 55 4 首页 56 例3 市场占有率预测 设某地有1600户居民 某产品只有甲 乙 丙3厂家在该地销售 经调查 8月份买甲 乙 丙三厂的户数分别为480 320 800 9月份里 原买甲的有48户转买乙产品 有96户转买丙产品 原买乙的有32户转买甲产品 有64户转买丙产品 原买丙的有64户转买甲产品 有32户转买乙产品 用状态1 2 3分别表示甲 乙 丙三厂 试求 1 转移概率矩阵 2 9月份市场占有率的分布 3 12月份市场占有率的分布 4 当顾客流如此长期稳定下去市场占有率的分布 5 各状态的平均返回时间 首页 57 解 1 由题意得频数转移矩阵为 再用频数估计概率 得转移概率矩阵为 2 以1600除以N中各行元素之和 得初始概