10 马尔科夫链.ppt

第10章马尔可夫链 10 1马尔可夫链及其转移概率 10 2多步转移概率的确定 10 3马氏链的有限维分布 10 4遍历性 10 1马尔可夫链及转移概率 10 1 1马尔可夫链的定义 10 1 2马尔可夫链的转移概率 10 1 3一步转移概率及其矩阵 10 1 1马尔可夫链的定义 1 马尔可夫性 无后效性 马尔可夫过程是目前发展很快 应用甚广的一种重要随机过程 马尔可夫性或无后效性 具有马尔可夫性的随机过程称为马尔可夫过程 无后效性用通俗的话来说 就是 已知过程的现在 就可以决定过程的将来 而将来与过去无关 马尔可夫过程在近代物理 生物 公用事业 信息处理 自动控制以及数字计算方法等方面都有重要作用 通信 控制系统中的噪声与信号 通信网络的传输现象等也常用马氏过程来模拟 2 马尔可夫过程的定义 具有马尔可夫性的随机过程称为马尔可夫过程 用分布函数表述马尔可夫过程 并称此过程为马尔可夫过程 2 马尔可夫链的定义 马尔可夫过程按照其状态和时间参数是连续还是离散进行划分 其中状态和时间参数都是离散的马尔可夫过程称为马尔可夫链 这一节我们着重讨论马尔可夫链 简称马氏链 10 1 2马尔可夫过程的概率分布 说明 平稳性 下面我们只讨论齐次马氏链 并习惯上常将 齐次 两字省略 10 1 3n步转移概率矩阵 由n步转移概率组成的矩阵 称为马氏链的n步转移概率矩阵 称任一具有上述两个性质的元素组成的矩阵为随机矩阵 这个矩阵的每行元素之和等于1 这个矩阵具有以下两个性质 一步转移概率矩阵 记为P 的状态 例10 1一维随机游动 游动的概率规则 如果Q现在位于点1 2或者3时 则下一时刻都以1 3的概率向左移动一格或以2 3的概率向右移动一格 如果Q现在位于0这点上 则下一时刻就以概率1移动到1 当Q到达4点时 它以概率1停留在该点上 0称为反射壁 4称为吸收壁 上面这种游动称为带有1个反射壁的随机游动 状态空间就是I 0 1 2 3 4 所以它是一个马氏链 且是齐次的 游动的概率规则 一步转移概率矩阵 说明 如果把点0改为吸收壁 4改为反射壁相应链的转移概率矩阵只须把P中第1行改为 1 0 0 0 0 改变游动的概率规则 就可得到不同方式的随机游动和相应的马氏链 一步转移概率矩阵 设一个单位时间传输一级 设每一级的传真率为p 误码率为q 1 p 只传输数字0和1的串联系统 0 1 传输系统 如图 分析 例10 2 所以它是一个马氏链 且是齐次的 一步转移概率矩阵 一步转移概率矩阵 10 2多步转移概率的确定 10 2 1C K方程 10 2 3应用举例 10 2 2多步转移概率的确定 称为切普曼 柯尔莫哥洛夫方程 简称C K方程 说明 C K方程基于下列事实 10 2 1切普曼 柯尔莫哥洛夫方程 这一事件可分解成 如下图所示 证明 利用全概率公式及马尔可夫性 有 10 2 2多步转移概率的确定 利用C K方程我们容易确定n步转移概率 得递推关系 马氏链的n步转移概率是一步转移概率的n次方 链的有限维分布可由初始分布和一步转移概率完全确定 结论 因此 在马氏链中 一步转移概率是最基本的 它完全确定链的状态转移的统计规律 10 3马氏链的有限维分布 向量表示形式 向量表示形式 10 3 1初始概率与绝对概率 定理10 2 绝对概率与初始概率的关系 表明绝对分布可由初始分布和n步转移概率矩阵确定 绝对分布与初始分布的关系可写为 10 3 2马氏链的有限维分布律 推论10 2 由定理10 3不难得到 解 例10 3 一步转移概率为 例10 4 解 先求出二步转移概率矩阵 于是 在0 1传输系统中 系统经n级传输后输出为1 问原发字符也是1的概率是多少 例10 5 2 在 1 的条件下某步传输 那么又接连两步都传输出 的概率是多少 1 数字1经三步传输出1的概率是多少 解以Xn表示第n步传输出的数字 则 Xn n 0 是一齐次马氏链 其状态空间为 I 0 1 一步转移矩阵为 由此可求得二步及三步转移矩阵分别为 从P 3 中得到 所以数字1经三步传输出1的概率为0 756 1 数字1经三步传输出1的概率是多少 2 在 1 的条件下某步传输 那么又接连两步都传输出 的概率是 4 根据贝叶斯公式 当系统经n级传输后输出为1 原发字符也是1的概率为 先求出n步转移概率矩阵 一步转移矩阵为 有相异的特征值 所以可将P表示成对角阵 所以根据贝叶斯公式 当系统经n级传输后输出为1 原发字符也是1的概率为 说明 n步转移概率矩阵为 对于只有两个状态的马氏链 一步转移概率矩阵一般可表示为 10 4遍历性 10 4 1遍历性的概念 10 4 3应用举例 10 4 2 有限链 遍历性的充分条件 定义 则称此链具有遍历性 10 4 1遍历性的概念 意义 对固定的状态j 不管链在某一时刻的什么状态i出发 通过长时间的转移到达状态j的概率都趋近于 j 另外如果我们能用其他简便的方法直接由一步转移概率求得极限分布 则反过来 当n很大时就可得到n步转移概率的近似值 研究遍历性问题的中心是要确定在什么样的条件下马氏链才具有遍历性 以及如何求得 j 这个问题已彻底解决 问题 10 4 2有限链马氏链遍历性的充分条件 定理给出了判别有限马氏链具有遍历性的一个简单充分条件 以及求 j的方法 2 求极限分布 j可转化为求解方程组 3 定理仅是充分条件 要想说明不具有遍历性 必须用定义 设一马氏链的一步转移概率矩阵为 试讨论它的遍历性 并求出其极限分布 例10 6 所以此链是遍历链 解 设其极限分布为 可列出如下方程 可得解为 即 这说明 当通信系统的级数无限增大时 离开系统时的数字为0或1的概率是相同的 这与原发概率大小无关 特别地 若当进入系统的数字是等可能的 即马氏链的初始分布为p0 0 p1 0 1 2时 则系统在任何步取0或1的概率都为1 2 在前面例中 我们已得到了n步转移矩阵为 这与用方程得出的结果是一致的 这说明 当通信系统的级数无限增大时 离开系统时的数字为0或1的概率是相同的 这与原发概率大小无关 特别 若当进入系统的数字是等可能的 即马氏链的初始分布为p0 0 p1 0 1 2时 则系统在任何步取0或1的概率都为1 2 一步转移概率为 例10 7 试证明该链是遍历的 并求其极限分布 解 二步转移概率矩阵为 P2中无零元 故此链是遍历的 在直线上带有反射壁的随机游动 如果质点只能取1 2 3三个点 一步转移概率矩阵为 讨论它是否为遍历链 解 例10 8 所以此链是遍历链 设其极限分布为 所以极限分布为 10 4 3平稳分布 对于遍历的有限马氏链 不管初始分布如何 当n趋于无穷时 它的绝对概率pj n 趋于 j 因此 j 称为极限分布或最终分布 即对遍历的有限马氏链 当n趋向无穷时 它的概率分布趋向稳定 即系统趋向平稳 定义中平稳性的直观含义是过程在任何时刻处于状态aj的概率都相等 事实上由 在定理的条件下 马氏链的极限分布就是平稳分布 且是唯一的 设一马氏链的一步转移概率阵为 试讨论它的遍历性 解 例10 8 表明 此链不具遍历性 一步转移概率为 例10 9 证明该链不是遍历的 解 二步转移概率矩阵为 故P n Pn极限存在 但是 与i有关 故此链不是遍历的 在直线上带有完全反射壁的随机游动 如果质点只能取1 2 3三个点 一步转移概率矩阵为 讨论它