庄伯金 bjzhuang@bupt.edu.cn 概率论与随机过程 第13章 马尔可夫链 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 主要内容 马尔可夫过程的概念 马尔可夫过程的概率分布 多步转移概率 遍历性 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 马尔可夫过程的概念 马尔可夫性：随机过程在时刻 所处状态已知的前提下，过程在 所处的状态与 时刻之前所处的状态无关。也称为无后效性。 马尔可夫性意味着随机过程在已知“现在”的状态下，跟“过去”无关。“过去”的影响已经作用在“现在”上了。 马尔可夫过程：设随机过程 ，若对于时间 的任意 个数值 ，在条件 下， 的分布函数恰等于 条件下 的分布函数，即 则称随机过程 为马尔可夫过程。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 马尔可夫过程的概念 设 是独立增量过程，且 ，则 是马尔可夫过程。 证明：由题可知 和 相互独立 即 和 相互独立。 由独立性即可知 只与 有关，而与 无关，即可得该过程为马尔可夫过程。 泊松过程和维纳过程都是马尔可夫过程。 马尔可夫链：时间和状态都是离散值的马尔可夫过程称为马尔可夫链，简称马氏链。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 设马氏链 ，状态空间 ，记条件概率 称为马氏链在 时刻处于状态 条件下，在时刻 转移到状态 的转移概率。 由转移概率组成的矩阵 称为转移矩阵。 注：转移矩阵每行元素之和为1。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 平稳的转移概率：若对于任意不同的 ，都有 即转移概率只跟 和 有关，则称转移概率具有平稳性，记为 称此马尔可夫链为齐次的。 若马氏链是齐次的，则称转移概率 为 步转移概率，转移矩阵 为 步转移矩阵。 特别的一步转移概率记为 ，一步转移矩阵记为 。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 一维随机游动：设一醉汉Q，在直线的点集 上作随机游动，且仅在整数秒时随机游动。游动的规则如下： 若Q现在位于点 处，则下一时刻他各以1/3的概率向左或右移动1格，以1/3的概率停留在原处； Q现在位于点1（或5）处，则下一时刻他以概率1游动到点2（或4）处。 转移概率 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 转移矩阵 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 例：某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机运行的状态，收集了24小时的数据（共97次观察），用1表示正常，0表示故障，所得的数据如下：111001001111111001111011111100111111110001101101111011011010111101110111101111110011011111100111。设 为第 个时段的计算机状态，并假定其为齐次马氏链，状态空间 。 转移概率可通过统计频率近似获得： 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 上例中，若计算机在某一时段内状态为0，问在此条件下，下面连续正常工作3刻钟的条件概率是多少？ 解：条件概率 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 转移概率与转移矩阵 定理：设 为马氏链， 为任意 个时刻，则有马氏链的 维分布律 推论：若 为齐次马氏链， 为任意 个时刻，则有齐次马氏链的 维分布律： 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 多步转移概率 设 是齐次马氏链，考察马氏链的多步转移概率 有 基本推导过程 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 多步转移概率 切尔曼-柯尔莫哥洛夫方程(C-K方程)：设 是齐次马氏链，则对任意的 ，有 由C-K方程可知，齐次马氏链的多步转移概率矩阵满足如下关系： 进一步的，可得 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 两个状态的齐次马氏链 设 为齐次马氏链，状态空间 ，一步转移概率矩阵为 计算 步转移概率矩阵 。 考察矩阵 的特征值及合同分解形式 ： 则 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 遍历性 考察上述两个状态的齐次马氏链的多步转移概率极限 注：不管从什么时刻什么状态出发，经过长时间的转移，到达状态 的概率都趋近相同。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 遍历性 定义：设齐次马氏链的状态空间为 ，若对所有的 ，转移概率 存在极限 或 则称此马氏链具有遍历性。又若 ，则称 为链的极限分布。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 遍历性 充分条件定理：设齐次马氏链的状态空间为 ，一步转移矩阵为 ，如果存在正整数 ，使得对任意的 ，都有 则此马氏链具有遍历性，且有极限分布 ，极限分布为方程组 在限制条件 下的唯一解。 庄伯金 bjzhuang@bupt.edu.cn

庄伯金 bjzhuang@bupt.edu.cn 作业1 P333 1 P333 4 P334 8 庄伯金 bjzhuang@bupt.edu.cn