马尔可夫预测方法PPT课件.ppt

第6章马尔可夫预测方法 6 1马尔可夫预测的基本原理6 2马尔可夫预测的应用 思考与练习 1 6 1马尔可夫预测的基本原理 6 1 1马尔可夫链 为了表征一个系统在变化过程中的特性 状态 可以用一组随时间进程而变化的变量来描述 如果系统在任何时刻上的状态是随机的 则变化过程就是一个随机过程 设有参数集T 如果对任意的t T 总有一随机变量Xt与之对应 则称 Xt t T 为一随机过程 如若T为离散集 不妨设T t0 t1 t2 tn 同时Xt的取值也是离散的 则称 Xt t T 为离散型随机过程 2 设有一离散型随机过程 它所有可能处于的状态的集合为S 1 2 N 称其为状态空间 系统只能在时刻t0 t1 t2 改变它的状态 为简便计 以下将Xtn等简记为Xn 一般地说 描述系统状态的随机变量序列不一定满足相互独立的条件 也就是说 系统将来的状态与过去时刻以及现在时刻的状态是有关系的 在实际情况中 也有具有这样性质的随机系统 系统在每一时刻 或每一步 上的状态 仅仅取决于前一时刻 或前一步 的状态 这个性质称为无后效性 即所谓马尔可夫假设 具备这个性质的离散型随机过程 称为马尔可夫链 用数学语言来描述就是 3 如果对任一n 1 任意的i1 i2 in 1 j S 恒有 P Xn j X1 i1 X2 i2 Xn 1 in 1 P Xn j Xn 1 in 1 6 1 则称离散型随机过程 Xt t T 为马尔可夫链 例如 在荷花池中有N张荷叶 编号为1 2 N 假设有一只青蛙随机地从这张荷叶上跳到另一张荷叶上 青蛙的运动可看作一随机过程 在时刻tn 青蛙所在的那张荷叶 称为青蛙所处的状态 那么 青蛙在未来处于什么状态 只与它现在所处的状态i i 1 2 N 有关 与它以前在哪张荷叶上无关 此过程就是一个马尔可夫链 由于系统状态的变化是随机的 因此 必须用概率描述状态转移的各种可能性的大小 4 6 1 2状态转移矩阵 马尔可夫链是一种描述动态随机现象的数学模型 它建立在系统 状态 和 状态转移 的概念之上 所谓系统 就是我们所研究的事物对象 所谓状态 是表示系统的一组记号 当确定了这组记号的值时 也就确定了系统的行为 并说系统处于某一状态 系统状态常表示为向量 故称之为状态向量 例如 已知某月 A B C三种牌号洗衣粉的市场占有率分别是0 3 0 4 0 3 则可用向量P 0 3 0 4 0 3 来描述该月市场洗衣粉销售的状况 5 当系统由一种状态变为另一种状态时 我们称之为状态转移 例如 洗衣粉销售市场状态的转移就是各种牌号洗衣粉市场占有率的变化 显然 这类系统由一种状态转移到另一种状态完全是随机的 因此必须用概率描述状态转移的各种可能性的大小 如果在时刻tn系统的状态为Xn i的条件下 在下一个时刻tn 1系统状态为Xn 1 j的概率pij n 与n无关 则称此马尔可夫链是齐次马尔可夫链 并pij P Xn 1 j Xn i i j 1 2 N称pij为状态转移概率 显然 我们有 6 转移矩阵设系统的状态转移过程是一齐次马尔可夫链 状态空间S 1 2 N 为有限 状态转移概率为pij 则称矩阵 为该系统的状态转移概率矩阵 简称转移矩阵 为了论述和计算的需要 引入下述有关概念 6 2 7 概率向量对于任意的行向量 或列向量 如果其每个元素均非负且总和等于1 则称该向量为概率向量 概率矩阵由概率向量作为行向量所构成的方阵称为概率矩阵 对于一个概率矩阵P 若存在正整数m 使得Pm的所有元素均为正数 则称矩阵P为正规概率矩阵 例如 矩阵 中每个元素均非负 每行元素之和皆为1 行数和列数相同 为2 2方阵 故矩阵A为概率矩阵 8 概率矩阵有如下性质 如果A B皆是概率矩阵 则AB也是概率矩阵 如果A是概率矩阵 则A的任意次幂Am m 0 也是概率矩阵 对k 1 记 p k ij P Xn k j Xn i P k p k ij N N称p k ij为k步状态转移概率 P k 为k步状态转移概率矩阵 它们均与n无关 从式 6 4 也可看出 特别地 当k 1时 p 1 ij pij为1步状态转移概率 马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出 6 3 9 由全概率公式可知 对k 1 有 其中P 0 表示单位矩阵 p k ij P Xn k j Xn i P Xn k 1 l Xn i P Xn k j Xn k 1 l p k 1 ilplj i j 1 2 N其中用到马尔可夫链的 无记忆性 和齐次性 用矩阵表示 即为p k P k 1 P 从而可得 p k Pkk 1记t0为过程的开始时刻 pi 0 P X0 X t0 i 则称 P 0 p1 0 p2 0 pN 0 6 4 10 为初始状态概率向量 如已知齐次马尔可夫链的转移矩阵P pij 以及初始状态概率向量P 0 则任一时刻的状态概率分布也就确定了 对k 1 记pi k P Xk i 则由全概率公式有 pi k pj 0 p k ji i 1 2 N k 1 6 5 若记向量P k p1 k p2 k pN k 则上式可写为 P k P 0 P k P 0 Pk 6 6 由此可得 P k P k 1 P 6 7 11 例6 1考察一台机床的运行状态 机床的运行存在正常和故障两种状态 由于出现故障带有随机性 故可将机床的运行看作一个状态随时间变化的随机系统 可以认为 机床以后的状态只与其以前的状态有关 而与过去的状态无关 即具有无后效性 因此 机床的运行可看作马尔可夫链 设正常状态为1 故障状态为2 即机床的状态空间由两个元素组成 机床在运行过程中出现故障 这时从状态1转移到状态2 处于故障状态的机床经维修 恢复到正常状态 即从状态2转移到状态1 12 现以1个月为时间单位 经观察统计 知从某月份到下月份机床出现故障的概率为0 2 即p12 0 2 其对立事件 保持正常状态的概率为p11 0 8 在这一时间 故障机床经维修返回到正常状态的概率为0 9 即p21 0 9 不能修好的概率为p22 0 1 机床的状态转移情形见图6 1 13 图6 1机床的状态转移 14 由机床的一步转移概率得状态转移概率矩阵 若已知本月机床的状态向量P 0 0 85 0 15 现要预测机床两个月后的状态 先求出两步转移概率矩阵 矩阵的第一行表明 本月处于正常状态的机床 两个月后仍处于正常状态的概率为0 82 转移到故障状态的概率为0 18 第二行说明 本月处于故障状态的机床 两个月后转移到正常状态的概率为0 81 仍处于故障状态的概率为0 19 15 于是 两个月后机床的状态向量6 1 3稳态概率矩阵1 平稳分布 若存在非零概率向量X x1 x2 xN 使得XP X 其中P为一概率矩阵 则称X为P的固定概率向量 特别地 设X x1 x2 xN 为一状态概率向量 P为状态转移概率矩阵 若XP X 16 即 则称X为马尔可夫链的一个平稳分布 若随机过程某时刻的状态概率向量P k 为平稳分布 则称过程处于平衡状态 一旦过程处于平衡状态 则过程经过一步或多步状态转移之后 其状态概率分布保持不变 也就是说 过程一旦处于平衡状态后将永远处于平衡状态 对于我们所讨论的状态有限 即N个状态 的马尔可夫链 平稳分布必定存在 特别地 当状态转移矩阵为正规概率矩阵时 平稳分布惟一 此时 求解方程 6 8 即可得到系统的平稳分布 j 1 2 N 17 2 稳态分布 对概率向量 1 2 N 如对任意的i j S 均有或这也是称 为稳态分布的理由 设存在稳态分布 1 2 N 则由于下式恒成立 P k P k 1 P 18 令k 就得 P 6 10 即有限状态马尔可夫链的稳态分布如存在 那么它也是平稳分布 对任一状态i 如果 k p k ii 0 的公约数为1 则称状态i为非周期状态 如果一个马尔可夫链的所有状态均是非周期的 则称此马尔可夫链是非周期的 对非周期的马尔可夫链 稳态分布必存在 对不可约非周期的马尔可夫链 稳态分布和平稳分布相同且均惟一 19 例6 2设一马尔可夫链的状态转移矩阵为 求其平稳分布及稳态分布 解 1 P不可约 pij 0 仅当i 2且j 2时 又p 2 22 0 由定义可知 P是不可约的 20 2 P非周期 由p 1 11 0 p 2 11 0 而1 2的公约数为1 故状态1为非周期状态 同理可得状态2 3均为非周期状态 故P是非周期的 3 由于P不可约且是非周期的 求解如下方程组 得X 0 40 20 4 这就是该马尔可夫链的稳态分布 而且也是平稳分布 21 6 2马尔可夫预测的应用 6 2 1市场占有率的预测 我们结合例题来说明如何预测市场占有率 例6 3伍迪公司 布卢杰 里维公司 雷恩公司 分别用符号 A B C 代表 是美国中西部地区生产灭虫剂的三家主要厂商 根据历史资料得知 公司A B C产品销售额的市场占有率分别为50 30 20 由于C公司实行了改善销售与服务方针的经营管理决策 使其产品销售额逐期稳定上升 而A公司的产品销售额却在下降 通过市场调查发现三个公司间的顾客流动情况如表6 1所示 22 其中产品销售周期是季度 现在的问题是 按照目前的趋势发展下去 A公司的产品销售额或客户转移的影响将严重到何种程度 更全面地 三个公司的产品销售额的占有率将如何变化 23 表6 1A B C三公司的顾客流动情况 24 将表6 1中的数据化为转移概率将对研究分析未来若干周期的顾客流向更为有利 表6 2列出了各公司顾客流动的转移概率 表6 2中的数据是每家厂商在一个周期中的顾客数与前一周期的顾客数相除所得 表中每一行表示某公司从一个周期到下一个周期将能保住的顾客数的百分比 以及将要丧失给竞争对手的顾客数的百分比 表中每一列表示各公司在下一周期将能保住的顾客数的百分比 以及该公司将要从竞争对手那里获得顾客数的百分比 25 表6 2顾客流动的转移概率 26 如用矩阵来表示表6 2中的数据 就得到了如下的状态转移矩阵 P中数据表示一个随机挑选的某公司的顾客 到下一个周期购买该公司或另一公司产品的可能性或概率 如随机挑选一名A公司的顾客 他在下一周期仍购买A公司产品的概率为0 7 购买B公司产品的概率为0 1 购买C公司产品的概率为0 2 6 11 27 1 未来各周期市场占有率的计算 以A B C公司作为我们要分析的系统的状态 那么状态概率向量就分别为三家公司的产品销售额的市场占有率 初始状态概率向量为 P 0 p1 0 p2 0 p3 0 0 5 0 3 0 2 转移矩阵由式 6 11 给出 于是可用式 6 6 来计算未来各期的市场占有率 如状态转移一次后第1周期的市场占有率向量为 28 2 稳态市场占有率 计算未来各期的市场占有率向量P k 可以看出 A公司的市场占有率将逐期下降 而 C 公司的市场占有率则将逐期上升 从经营决策和管理的角度来看 自然希望了解各公司的市场占有率最终将达到什么样的水平 亦即需要知道稳态市场占有率 29 2019 12 30 30 由于式 6 11 中的P是不可约非周期的 因此稳态市场占有率即为平衡状态下的市场占有率 亦即马尔可夫链的平稳分布 由前面的讨论知道 我们求解如下方程组 31 解得 x1 0 1765 x2 0 2353 x3 0 5882 亦即 A B C三家公司的市场占有率最终将分别达到17 65 23 53 58 82 对本例来说 当销售份额达到平衡时 各公司分别占总销售额中的那一部分均保持不变 但在某些情况下 参与竞争的公司或厂商中可能会有一个或多个被完全逐出市场 例如对于转移矩阵 32 3 销售策略对市场占有率的影响 1 保留策略 指尽力保留公司原有顾客的各种经营方针与对策 如采用提供优质服务或对连续两期购货的顾客实行折价优惠等方法 设 公司采用这样的保留策略后 减少了其原有顾客向 公司的流失 使保留率从原来的70 提高到85 则转移矩阵成为 33 新的平衡状态下 三公司的市场占有率分别为31 6 26 3 42 1 公司的市场占有率从17 65 提高到31 6 2 争取策略 指从竞争者拥有的顾客中争取顾客的各种经营方针与对策 如通过广告等方法 设 公司通过争取策略 能从上一周期内向另外两家公司购货的顾客中各争取15 则转移矩阵成为 34 6 2 2期望报酬预测 在一个与经济有关的马尔可夫型随机系统中 系统获得的报酬 或称收益 也会随状态的不同而不同 设有一台机器 它在第n周期的状态用Xn表示 0第n周期正常 1第n周期失效进一步假定 机器正常时 每一个周期可带来v元的收益 并且在下一周期失效的概率为p Xn 35 当机器失效时 需对其进行更换 更换的费用为d 修理时间为一个周期 下一个周期初修好并开始正常工作 于是 Xn 是一个齐次马尔可夫链 其状态空间为S 0 1 转移矩阵为但这是一个带报酬 或称收益 费用 的马尔可夫链 36 一般地 设 Xn 是状态空间为S 1 2 N 的齐次马尔可夫链 其转移矩阵为P pij N N 设r i 表示某周期系统处于状态i时获得的报酬 我们称如此的马尔可夫链是具有报酬的 显然 r i 0时 称为盈利 报酬 收益等 r i 0时 称为亏损 费用等 对于这样一个带报酬的马尔可夫链 n时的报酬是一个随机变量 1 有限时段期望总报酬 记vk i 表示初始状态为i的条件下 到第k步状态转移前所获得的期望总报酬 k 1 i S 37 若记列向量Vk vk 1 vk 2 vk N T r r 1 r 2 r N T 则上式可写为 6 12 38 这里 I表示单位矩阵 进而 可证明有如下递推式 v0 i 0i 1 2 N 于是可用上式递推求得vk i 2 无限时段单位时间平均报酬 对i S 定义初始状态为i的无限时段单位时间平均报酬为 k 0 i 1 2 N 6 13 39 记矩阵P p ij 则由式 6 12 可证得 于是为求v i 只须求得P 即可 但一般地要求出P 并不是件容易的事 这里我们只讨论如下的特殊情况 我们考虑稳态分布 1 2 N 存在的这种特殊情况 i j 1 2 N 6 14 40 由上节可知 转移矩阵P非周期即可保证 存在 当 存在时 它也是平稳分布 注意到数学分析中的一个结论 设数列an有极限a 则于是 我们有如下结论 结论设所考虑的马尔可夫链存在稳态分布 则p ij j j 1 2 N 进而若式 6 10 有惟一解X x1x2 xN 则有 p ij j x jj 1 2 N 6 15 41 实际上 如果 存在 当式 6 10 有惟一解X时 由于稳态分布必为平稳分布 故 j xj 特别地 对于不可约非周期的马尔可夫链 式 6 15 恒成立 于是可先求解式 6 10 得X 进而由式 6 15 求得v i 3 无限时段期望折扣总报酬 在现实生活中 今年的一元钱将大于明年的一元钱 其实将钱存于银行即可 也就是说明年的一元钱折算到现在计算 就不值一元钱了 如为 0 1 这个 就称为折扣因子 实际上 在企业管理中当考虑贷款 折旧等时都必须考虑到钱的增值问题 42 如将钱存于银行 年息为 则 与 有如下关系 如果一个周期为一个月 那么只须将 理解为月息即可 这里折扣因子 一般在区间 0 1 中 对有报酬的马尔可夫链 定义从状态i出发的无限时段期望折扣总报酬为 6 16 6 17 43 若记向量V v 1 v 2 v N T 则上式的向量或矩阵形式为与有限时段中的式 6 13 类似 由式 6 17 可得 6 18 6 19 44 例6 4最佳维修策略的选择 我们研究一化工企业对循环泵进行季度维修的过程 该化工企业对泵进行定期检查 每次检查中 把泵按其外壳及叶轮的腐蚀程度定为五种状态中的一种 这五种状态是 状态1 优秀状态 无任何故障或缺陷 状态2 良好状态 稍有腐蚀 状态3 及格状态 轻度腐蚀 状态4 可用状态 大面积腐蚀 状态5 不可运行状态 腐蚀严重 该公司可采用的维修策略有以下几种 45 单状态策略 泵处于状态5时才进行修理 每次修理费用为500元 两状态策略 泵处于状态4和5时进行修理 处于状态4时的修理费用每次为250元 处于状态5时的每次修理费用为500元 三状态策略 泵处于状态3 4 5时进行修理 处于状态3时的每次修理费用为200元 处于状态4和5时的修理费用同前 目前 该公司采用的维修策略为 单状态 策略 假定不管处于何种状态 只要进行修理 泵的状态都将在本周期内恢复为状态1 已知在不进行任何修理时的状态转移概率 如表6 3中所示 46 表6 3不修理时的状态转移概率 47 现在我们要确定哪个策略的费用最低 目标为长期运行单位时间平均报酬 容易看出 在单状态 两状态 三状态下的转移概率矩阵分别为 48 49 下面我们分别来求三种策略下的v i 1 单状态策略 此时r 1 r 2 r 3 r 4 0 r 5 500 将P1代入式 6 8 可解得惟一的平稳分布为X x1 x2 x5 0 199 0 170 0 180 0 252 0 199 而P1显然是不可约非周期的 从而X亦为稳态分布 由此及式 6 14 6 15 可得 50 2 两状态策略 r 1 r 2 r 3 0 r 4 250 r 5 500 与 1 中类似 可知 X 0 266 0 228 0 241 0 168 0 097 从而由式 6 14 6 15 有 3 三状态策略 r 1 r 2 0 r 3 200 r 4 250 r 5 500 于是X 0 35 0 30 0 19 0 095 0 065 v i xjr j 0 19 200 0 095 250 0 065 500 94 25 元 51 因此 两状态策略为最优策略 平均每周期的费用为90 50元 从上面的计算发现 v i 均与i无关 其实 若式 6 15 成立 则由式 6 14 知v i 总与i无关 亦即单位时间平均报酬 或费用 与起始状态无关 52 思考与练习 马尔可夫链应具备哪些性质 如何描述系统状态的转移情况 试用无限时间期望折扣总报酬准则讨论例6