第2章_马尔可夫链.ppt

CHAPTER2马尔可夫链 第一节基本概念一 马尔可夫链的定义及例子1 定义 随机过程称为马尔可夫链 若它只取有限或可列个值 称为过程的状态 记为0 1 2 并且 对任意及状态 有 2 分类 按马尔可夫过程参数空间和状态空间的不同可分为 定义 称 为n时刻的一步转移概率 若 即pij与n无关 则称 Xn n 0 为齐次马尔可夫链 记P pij 称P为 Xn n 0 的一步转移概率矩阵 3 转移概率 我们来看马尔可夫链的分布 可见 马尔可夫链的分布由其初始分布和其一步转移概率完全决定 4 马尔可夫链的例子 例1独立随机变量和的序列设 Yn n 1 为独立同分布随机变量序列 且Yn取值为非负整数 其概率分布为P Yn i ai i 0 1 2 令X0 0 Xn Y1 Yn 则易证 Xn n 0 是一马尔可夫链 且 显然 Yn n 1 也是一马尔可夫链 例2M G 1排队系统若以X t 记在t时刻系统中的顾客数 X t t 0 则不具马尔可夫性 Xn 第n个顾客走后剩下的顾客数 Yn 第n 1个顾客接受服务期间来到的顾客数 则 容易证明 Yn n 1 独立同分布 且 因此 Xn n 1 是马尔可夫链 其转移概率为 例3G M 1排队系统来到时间间隔分布为G 服务时间分布为指数分布 参数为 且与顾客到达过程独立 Xn 第n个顾客来到时见到系统中的顾客数 包括该顾客 则 Xn n 1 是马尔可夫链 记 Yn 第n个顾客来到时刻到第n 1个顾客来到时刻之间系统服务完的顾客数 则 pi0公式略有不同 它是服务台由有i个顾客转为空闲的概率 例4直线上的随机游动 1 无限制的随机游动设有一质点在数轴上随机游动 每隔一单位时间移动一次 每次只能向左或向右移动一单位 或原地不动 设质点在0时刻的位置为a 向右移动的概率为p 向左移动的概率为q 原地不动的概率为r p q r 1 且各次移动相互独立 以Xn表示质点经n次移动后所处的位置 则 Xn n 0 是一马尔可夫链 转移概率为Pi i 1 p Pi i 1 q Pi i r 其余Pi j 0 2 带吸收壁的随机游动设 1 中的随机游动限制在S 0 1 2 b 当质点移动到状态0或b后就永远停留在该位置 即p00 1 pbb 1 其余pij 1 i j b 1 同 1 这时 Xn n 0 称为带两个吸收壁0和b的随机游动 它是一有限状态马尔可夫链 例5Polya 波利亚 模型 罐中有b只黑球及r只红球 每次随机地取出一只后把原球放回 并加入与抽出球同色的球c只 再第二次随机地取球重复上面步骤进行下去 Xn i 表示第n回摸球放回操作完成后 罐中有i只黑球这一事件 所以 这是一个非齐次的马尔可夫链 在传染病研究中有用 下面的定理提供了一个非常有用的获得马尔可夫链的方法 并可用于检验一随机过程是否为马尔可夫链 定理 设随机过程 Xn n 0 满足 1 Xn f Xn 1 Yn n 1 其中f S S S 且Yn取值在S上 2 Yn n 1 为独立同分布随机变量 且X0与 Yn n 1 也相互独立 则 Xn n 0 是马尔可夫链 其一步转移概率为pij P f i Y1 j 证明 设n 1 则Yn 1与X0 X1 Xn相互独立 事实上 因为X1 f X0 Y1 Y2与X0 Y1独立 所以 Y2与X1 X0独立 同理 X2 f X1 Y2 f f X0 Y1 Y2 所以 Y3与X2 X1 X0独立 归纳可得Yn 1与X0 X1 Xn相互独立 所以 Xn n 0 是马尔可夫链 且 所以有 二 切普曼 柯尔莫哥洛夫方程 1 随机矩阵定义 称矩阵A aij S S为随机矩阵 若aij 0 且 显然马尔可夫链 Xn n 0 的一步转移概率矩阵P为随机矩阵 2 n步转移概率定义 设 Xn n 0 是一马尔可夫链 称 为马尔可夫链 Xn n 0 的n步转移概率 记 称 为n时刻Xn的概率分布向量 称为马尔可夫链 Xn n 0 的初始分布向量 结论 一个马尔可夫链的特性完全由它的一步转移概率矩阵及初始分布向量决定 事实上 类似地可以证明马尔可夫链任意个时刻的联合分布也完全由一步转移概率矩阵及初始分布向量决定 3 定理 切普曼 柯尔莫哥洛夫方程 C K方程 或 其中 为马尔可夫链 Xn n 0 的n步转移概率矩阵 证明 例 马尔可夫预测 P82解一阶转移矩阵为 初始分布为 则 半年后A种鲜奶的市场占有率为 例 甲 乙两人进行比赛 设每局比赛中甲胜的概率是p 乙胜的概率是q 和局的概率是 设每局比赛后 胜者记 1 分 负者记 1 分 和局不记分 当两人中有一人获得2分结束比赛 以表示比赛至第n局时甲获得的分数 1 写出状态空间 2 求P 2 3 问在甲获得1分的情况下 再赛二局可以结束比赛的概率是多少 解 1 记甲获得 负2分 为状态1 获得 负1分 为状态2 获得 0分 为状态3 获得 正1分 为状态4 获得 正2分 为状态5 则状态空间为 一步转移概率矩阵 2 二步转移概率矩阵 3 从而结束比赛的概率 从而结束比赛的概率 所以题中所求概率为 第二节状态的分类及性质 定义1 若存在某个n使得 则称从状态i可达状态j 记为i j 如果i j且j i 则称i与j相通 记为 若一马尔可夫链的任意两个状态都是相通的 则称该马尔可夫链是不可约的 若pii 1 则称状态i为吸收态 定理 相通是一种等价关系 即 定义2 若集合 则称该数集的最大公约数d i 为状态i的周期 若d i 1 称i为周期的 若d i 1 称i为非周期的 定理 则d i d j 证明 若i与j相通 则存在m n 使得 假设有s使得 则 因为d i 是i的周期 所以d i 应同时整除n m和n m s 则d i 一定整除s 而d j 是j的周期 所以d i 整除d j 反过来也可证明d j 整除d i 于是d i d j 定义3 首达时间定义为 若右边为空集 则令Tij表示从i出发首次到达j的时间 Tii表示从i出发首次回到i的时间 定义4 首达概率定义为 表示从i经n步首次到达j的概率 显然有 定义5 fij表示过程从i出发在有限时间内能够到达j的概率 或者说从i出发迟早转移到状态j的概率 fii表示过程从i出发迟早转移到状态i的概率 定义6 若fii 1 则称i为常返状态 若fii 1 则称i为非常返状态 或瞬时状态或称滑过的 定义7 若i为常返状态 即fii 1 记 称为从状态i出发再回到i的平均回转时间 或平均回转步数 若 称为正常返状态 若 称为零常返状态 定义8 若状态i是正常返的并且是非周期的 则称状态i为遍历状态 定理 与有如下关系 定理 状态i是常返状态 当且仅当 状态i是非常返状态 当且仅当 证明 约定 的含义 则 表示过程到达i的次数 所以 表示过程从i出发返回到i的平均次数 若状态i是滑过的 非常返的 则 即滑过状态i只能有限次到达i 从而有限状态的马尔可夫链不可能全部状态都是滑过的 即有限状态的马尔可夫链至少有一个状态是常返的 定理 若 则i j同为常返的和非常返的 即常返性具有类性质 若为常返的 则它们同为正常返状态或零常返状态 证明 由 知存在n m 使得 由C K方程总有 所以 相互控制 同为无穷或有限 从而同为常返或非常返 定理 若 且j 或i 是常返的 则fij 1 或fji 1 证明 假如fij0 使得从i出发不能在有限步内回到j 而 这意味着系统中存在着一个正概率 使得它从j出发不能在有限步内回到j 因为若从j出发能够在有限步内回到j 则从i出发也能在有限步内回到j 从而fjj 1 与j是常返的相矛盾 以Nj t 记到时刻t为止转移到j的次数 若j是常返的 且X0 j 则因为一旦转移到j 过程在概率上重新从头开始 故 Nj t t 0 是一个来到时间间隔分布为的更新过程 若X0 i 且j是常返的 则 Nj t t 0 是一个延迟更新过程 其初始来到时间间隔分布为 例考虑直线上无限制的随机游动 状态空间为 转移概率为 则对于状态0 有 由斯特林 Stirling 公式可知 当n充分大时有 所以 注意到 所以 当时 此时 状态0是常返的 当时 此时 状态0是滑过的 由于过程的各个状态都是相通的 由此可判断其它状态的常返性 例 转移矩阵 试对其状态分类 解 按一步转移概率 画出各状态间的传递图 从图可知 此链的每一状态都可到达另一状态 即4个状态都是相通的 考虑状态1是否常返 类似地可求得 所以 于是状态1是常返的 又因为 所以状态1是正常返的 由定理可知 此链所有状态都是正常返的 例 设马氏链的状态空间I 0 1 2 其一步转移概率为 其中 试证此马氏链是一个不可约常返态链 证 先证I不可约 设i j是I中任意两个状态 则有 类似地可证 所以 即I中任意两个状态都是相通的 因此 I是一个不可约的闭集 再证I中状态0是一个常返态 由状态的转移规则 得 所以 1 0 2 3 4 5 由定义知状态0为常返态 因此 由定理知I中所有状态都是常返态 故此马氏链为不可约常返链 第三节极限定理及平稳分布 一 极限定理 例设马尔可夫链的转移概率矩阵为 现在来计算 令 则 所以 定理 若i与j相通 则 3 若j是非周期的 则 4 若j有周期d 则 推论 如i是常返的 则i为零常返的充要条件是 推论 如i是遍历的 正常返的并且是非周期的 则 记 则 如i是常返的 当时为正常返的 当时为零常返的 推论 有限状态的马尔可夫链 不可能全为非常返状态 也不可能有零常返状态 从而不可约的有限马尔可夫链的状态全为正常返的 推论 遍历性定理 1 若j为非常返或零常返的 则 有 2 若j为常返的且周期为d 则 有 推论 若马尔可夫链有一个零常返态 则必有无限个零常返态 状态性质判别法 i非常返 i零常返 i正常返 i遍历的 i正常返 i正常返且非周期 即遍历 i正常返且周期为d 二 平稳分布与极限分布 1 定义 设pij是马尔可夫链 Xn n 1 的转移概率 若概率分布 pj j 0 满足 则称 pj j 0 为 Xn n 1 的平稳分布 记 则平稳分布可表示为如下矩阵形式 显然有 即 若马尔可夫链 Xn n 0 的初始分布pj P X0 j 是平稳分布 则对任意的n 有 即Xn与X0有相同的分布 这说明过程 Xn n 0 是平稳过程 这也是称分布pj P X0 j 为平稳分布的原因 2 定义 若马尔可夫链是遍历的 即所有状态相通且均为周期为1的正常返态 则极限 称为马尔可夫链的极限分布 显然此时 定理 一个不可约非周期的马尔可夫链属于下列两种情况之一 1 状态或全是滑过的 非常返的 或全是零常返的 此时对一切的i j有 因而不存在平稳分布 2 状态全是正常返态 即 此时 是平稳分布 且不存在任何其它的平稳分布 此时极限分布即是平稳分布 只证2 若马尔可夫链是遍历的 则 存在 且 证明 1 显然 利用C K方程 从而 是平稳分布 再证 是惟一的平稳分布 假设另外还 有一个平稳分布 则 注 1 对于不可约的遍历链 不可约 正常返 周期为1 因为 所以 可被解释为马尔可夫链长时间之后处于状态的的时间所占的比率 2 对于不可约的遍历链 因为极限分布存在且等于平稳分布 这意味着当n充分大时有 即 Xn n 0 是一渐近平稳序列 平稳过程 这在实际问题中是很有意义的 例 设马氏链的状态空间I 0 1 2 转移概率为 试讨论各状态的遍历性 解 根据转移概率作出状态传递图 从图可知 对任一状态都有 故由定理可知 I中的所以状态都是相通的 因此只需考虑状态0是否正常返即可 故 从而0是常返态 又因为 所以状态0为正常返 又由于 故状态0为非周期的 从而状态0是遍历的 故所有状态i都是遍历的 例 设有6个球 其中2个红球 4个白球 分放于甲 乙两个盒子中 每盒放3个 今每次从两个盒中各任取一球并进行交换 以表示开始时甲盒中红球的个数 表示经n次交换后甲盒中的红球数 1 求马氏链 的转移概率矩阵 2 证明 是遍历的 3 求 4 求 解 其一步转移矩阵为 甲 乙 红球0白球3 红球2白球1 红球1白球2 红球1白球2 红球2白球1 红球0白球3 并作出状态传递图 2 由于它是一个有限马氏链 故必有一个常返态 又链中三个状态0 1 2都相通 所以每个状态都是常返态 所以是一个不可约的有限马氏链 从而每个状态都是正常返的 所以此链为非周期的 故此链是不可约非周期的正常返链 即此链是遍历的 2 可以利用定理证明遍历性 解之得 故得 4 讨论对时间连续状态离散的马尔可夫过程 取时间参数 状态空间I 0 1 2 第五节时间连续马尔可夫链 一 定义及性质 时间连续的马尔可夫链 转移概率 齐次马氏链 转移概率仅由t决定而与s无关 2 性质 性质1 切普曼 柯尔莫哥洛夫方程 性质2 连续时间齐次马氏链的有限维概率分布由它的初始分布和转移矩阵所确定 注 性质3 注 对时间来说是可逆性 性质4 已知现在 那么过去与将来是独立 注 性质5 遍历性定理 马尔可夫定理 设 是状态空间I 0 1 2 s 的时间连续的齐次马氏链 则 的满足条件 的唯一解 例1 考虑一个电话总机接到的呼唤流 以表示这个总机在 0 t 中接到的呼唤次数 由于呼唤流在不相交的时间区间中接到的呼唤次数是相互独立的 且服从泊松分布 所以是一个时间连续状态离散的马氏过程 而且是齐次的 写出它的转移概率 当呼唤次数时 转移概率 当时 其状态空间I 0 1 2 转移概率为 1 随机连续 则称 是随机连续的 定理1 二 可尔莫哥洛夫微分方程 时间连续的齐次马氏链 是随机连续的充要条件为 对任意的 有 随机连续直观意义 当系统经过很短时间 其状态几乎不变 标准转移概率 若时间连续的齐次马氏链是随机连续的 则称其转移概率是标准的 并且满足性质 2 转移概率的性质 性质1 性质2 定理2 并且对任意 有 2 对时间连续的齐次有限马氏链 有 若 注1 推论 则对任意 有 即为吸收态 等价 它表明系统从状态i出发 是继续留在状态i 还是跳跃到状态j 在不计一个高阶无穷小时 决定于与 注2 等价 跳跃强度 与称为跳跃强度 3 密度矩阵 由跳跃强度构成的矩阵 若对一切 有 由定理2推论可知 也称时间连续马氏链是保守的 矩阵保守 时间连续的齐次有限马氏链是保守的 4 可尔莫哥洛夫定理