第十一章 马尔可夫链.ppt

第十一章马尔可夫链 主要内容 1 定义 与记号 2 转移概率与矩阵 3 遍历性 返回目录 1 马尔可夫性的定义 语言描述 一般性解释 由时刻系统的状态 可以决定系统在t 时所处的状态 而与以前系统的历史状态无关 如微分方程的定解问题 对于随机现象 可以描述如下 系统在时刻所处的状态为已知的条件下 系统在时刻t 所处状态的条件分布与在时刻之前所处的状态无关 数学表达式 先做一些假设 随机过程设为X t 状态空间I 任选T中n个时刻 对应的状态为 则的马氏性就是这样一个条件分布函数 马尔可夫链 时间和状态都离散的马尔可夫过程称为马尔可夫链 记为 状态空间I 而相应的马尔可夫性用条件分布律示如下 2 转移概率 记上面的条件概率为 称为转移概率 它表示马氏链在时刻m处于状态的条件下 经过n步变化后 在时刻m n处于状态的条件概率 3 转移概率矩阵 当上式中 取遍状态空间I时 此时假 设I有限 会得到N N个转移概率 它们可以组成一个N N的矩阵 称为转移概率矩阵 记为 它表现了马氏链经过n步后所有可能发生的状态之间的转移 由概率的规范性 容易得到P m m n 的一个性质 每一行元素横向相加等于1 4 齐次马氏链 当 只与步数n有关 与起始时刻 m无关时 称此转移概率具有平稳性 或称此链是齐次马氏链 可以记为 我们特别要掌握一步转移概率 以及由它们组成的一步转移概率矩阵 5 例题 例2 在0 1传输系统中 设每一级的传真率为p 误码率为q 1 p 并设一个单位时间传输一级 是第一级的输入 是第n级的输出 那么 是一个马氏链 而且还是齐次的 其状态空间I 0 1 例3 一维随机游动 设一质点在图示直线的点集I 1 2 3 4 5 上作随机游动 且仅在1秒 2秒等时刻发生游动 游动的概率规则是 如果点Q现在位于点i 1 i 5 则下一时刻各以1 3的概率向左或向右移动一格 或以1 3的概率留在原处 如果Q现在位于1 或5 这点上 则下一时刻就以概率1移动到2 或4 这一点上 若以表示时刻n时Q的位置 则是一齐次马氏链 它的一步转移概率矩阵为 例4 排队模型 设服务系统由一个服务员 和只可以容纳两个人的等侯室组成 服务规则是先到先服务 后来者需在等候室排队 假定一个顾客到达系统时发现系统内已有板有3个顾客 则该顾客即离去 设时间间隔 t内有一个顾客进入系统的概率为q 有一原来被服务的顾客离开系统的概率为p 又设当 t充分小时 在这时间间隔内多于一个顾客进入或离开系统是不可能的 可用马氏链来描述这个服务系统 图形 例6 续例5 已知计算机在某一时段 15分钟 的状态为0 问在此条件下从此时段起此计算机能连续正常工作3个时段的条件概率为多少 6 齐此马氏链的有限维分布 先看初始分布 是一个离散型的随机 变量 其分布律称为初始分布 可以表为 也可以用表格式 2 再来看任意时刻n的一维分布 显然 由规范性有 另外 可以用行向量来表示分布律 初始分布律与任意时刻n的分布律之间的关系 以的各状态值分布为划分 运用全概率公式 即可得到 用矩阵乘法来表达如下 back 第二节多步转移概率的确定 内容提要 1 C K方程形式 2 方程的意义 3 方程的证明 4 例题 back 1 C K方程 设 是一齐次马氏链 对 任意的u vT 有 用矩阵表示即 P u v P u P v back 2 方程的意义 如果设初始时刻s 终止时刻是s u v 引入中间时刻s u C K方程的意义在于 从s时刻的状态出发 经u v步后转移到状态 这一事件等价于 从出发 先经u步转移到中间状态 再从经时段v转移到 的和事件 back 3 证明 back 例1 设是具有三个状态0 1 2的齐次马氏链 一步转移矩阵为 P 初始分布 试求 例2 1 在 1例2中 设p 0 9 求系统二级传输后的传真率与三级传输后的误码率 2 设初始分布 又已知系统经n级传输后输出为1 问原发字符也是1的概率是多少 back 第三节遍历性 主要内容 1 举例 2 定义 3 有限链的遍历性充分条件 4 平稳分布 5 总结 6 例题 back 1 举例 在上面例2中的一步转移矩阵 P 计算其n步转移矩阵P n 为 它存在着极限 矩阵的两行完全相同 back 2 定义 1 语言描述 对固定状态j 无论链从什 么状态出发 即与左边的列无关 经过长时间的转移后 到达状态j的概率都趋近于 这个性质称为遍历性 2 数学式子表达 或者 与i无关 特别地 将行向量提出来 由于它构成了一个分布律 即 称它为极限分布 back 3 遍历性的充分性条件 定理 对齐次马氏链 状态空间I 一步转移矩阵P 1 如果存在正整数m 使对任意的 都有 即矩阵P m 中无零元素 则此链具有遍历性 且其极限分布就是方程组 P 1 的满足的唯一解 back 4 平稳分布 在上述定理的条件下 又称为平稳分布 其意义在于 是所有状态分布中的平衡值 一旦链的状态分布达到了 则链的一维状态分布不会再发生变化了 back 5 总结 的多重意义 1 代表了遍历性的存在 2 极限分布 3 在充分条件下 也是链的平稳分布 back 6 例题 例1 试说明 1例3中的随机游动是遍历的 并求其极限分布 例2 试说明 1例4排队模型中的链是遍历的 并求其极限分布 例3 设一马氏链的一步转移矩阵为 试讨论它的遍历性 补充例题 若顾客的购买是无记忆的 现在市场上供应A B C三个不同厂家生产的50g袋装味精 用分别表示事件 顾客第n次购买A B C三厂的味精 则是一个马氏链 已知顾客第一次购买三种味精的概率依次为0 2 0 4 0 4 又知道一