随机过程第5讲(马尔科夫链定义和性质).ppt

随机过程及其应用 离散时间Markov链 第5讲 2020 1 29 郑州大学信息工程学院 1 内容提要 离散时间Markov链的定义 性质离散时间Markov链举例 2020 1 29 郑州大学信息工程学院 2 安德雷 安德耶维奇 马尔可夫 A A Markov 俄数学家 1856 1922概率和统计领域专家 当年Markov研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了Markov过程的数学模型Markov过程80年代兴起 在现代工程 自然科学 社会科学中应用广泛 2020 1 29 郑州大学信息工程学院 3 1 马尔可夫过程定义 定义 设有一随机过程 t t T t1 t2 t3 tm tm 1 T 若在t1 t2 t3 tm tm 1时对 t 观测得到相应的观测值x1 x2 x3 xm xm 1满足条件 则称这类过程为具有马尔可夫性质的随机过程或马尔可夫过程 2020 1 29 郑州大学信息工程学院 4 Markov过程也可表示为如下形式 2020 1 29 郑州大学信息工程学院 5 2020 1 29 郑州大学信息工程学院 6 该式表明 t 的n维概率密度等于一些条件概率密度与t1时初始概率密度的乘积 这些条件概率密度称为转移概率密度 马尔可夫过程 t t T 可能取的值的全体组成过程的状态空间 t 可能取的值称为状态 t x代表在t时刻过程 或系统 处在状态x 马尔可夫过程的状态空间可以是连续的 也可以是离散的 马尔可夫过程的参数t可以是连续的 也可以是离散的 Markov过程的分类Markov链 状态值可数离散的Markov过程离散时间Markov链 第二章 连续时间Markov链 第三章 2020 1 29 郑州大学信息工程学院 7 马尔可夫链的定义 n n 0 1 2 是离散状态 状态空间为I 参数为非负整数的随机过程 且 n 满足条件 即在参数n 0 1 2 n 状态取 0 i0 1 i1 n 1 in 1 n i的条件下 n 1 j的条件概率与 0 1 n 1 无关而仅与 n 所取的值有关 把这类随机过程成为马尔可夫链 2020 1 29 郑州大学信息工程学院 8 由定义可知 2020 1 29 郑州大学信息工程学院 9 一步转移概率的两个性质 1 2 2020 1 29 郑州大学信息工程学院 10 齐次马尔可夫链 定义 如果在马尔可夫链中即从 状态转移到 状态的概率与 无关 则称这类马尔可夫链为齐次马尔可夫链 设 代表一步转移概率pij所组成的矩阵 且状态空间 由状态 所组成 则 2020 1 29 郑州大学信息工程学院 11 一步转移概率矩阵P中每个元素为非负 每行之和均为1 2 切普曼 柯尔莫哥洛夫方程式 C K方程 m步转移概率 性质 m 1时即一步转移概率 m 0时规定 2020 1 29 郑州大学信息工程学院 12 对于m步转移概率矩阵有C K方程 2020 1 29 郑州大学信息工程学院 13 证明 2020 1 29 郑州大学信息工程学院 14 这一事件可分解成 件的和事件 如下图所示 C K方程是指 n 在n时处于状态i的条件下经过m r步转移与n m r时到达状态j 可以先在n时从状态i出发 经过m步于n m时到达某种中间状态k 再在n m时从状态k出发经过r步转移于n m r时到达最终状态j 而中间状态k要取遍整个状态空间 C K方程也可以用矩阵形式表示 r 1时 可得 一直推下去可得 结论 马尔可夫链的m步转移概率由一步转移概率所完全决定 2020 1 29 郑州大学信息工程学院 15 马尔可夫链的分布 1 初始分布称 i I为马氏链的初始分布 2 有限维分布定理 马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定 2020 1 29 郑州大学信息工程学院 16 转移概率决定了马氏链的运动的统计规律 因此 确定马氏链的任意n步转移概率成为马氏链理论中的重要问题之一 证明 2020 1 29 郑州大学信息工程学院 17 马尔可夫链的例子 例 天气预报问题如果明天是否有雨仅与今天的天气 是否有雨 有关 而与过去的天气无关 并设今日下雨 明日有雨的概率为 今日无雨明日有雨的概率为 又假定把有雨称为 状态天气 把无雨称为 状态天气 n 表示n时的状态天气 则 n 是以 0 1 为状态空间的齐次马尔可夫链 它的一步转移矩阵为 2020 1 29 郑州大学信息工程学院 18 设 0 7 0 4 则一步转移概率矩阵为 2020 1 29 郑州大学信息工程学院 19 四步转移概率矩阵 由此可知 今日有雨且第四日仍有雨的概率为 P00 4 0 5749 则两步转移概率矩阵 2020 1 29 郑州大学信息工程学院 20 例 解 1 先求出2步转移概率矩阵 2020 1 29 郑州大学信息工程学院 21 例一维随机游动 游动的概率规则 如果Q现在位于点i 1 i 5 则下一时刻各以1 3的概率向左或向右移动一格 或以1 3的概率留在原处 2020 1 29 郑州大学信息工程学院 22 如果Q现在位于1 或5 这点上 则下一时刻就以概率1移动到2 或4 这一点上 1和5这两点称为反射壁 上面这种游动称为带有两个反射壁的随机游动 模拟方法 产生均匀分布的随机数序列13232211122 其中1表示左移 2表示不动 3表示右移 2020 1 29 郑州大学信息工程学院 23 理论分析 状态空间是I 而与时刻n以前所处的状态无关 所以它是一个马氏链 且是齐次的 2020 1 29 郑州大学信息工程学院 24 一步转移概率 2020 1 29 郑州大学信息工程学院 25 一步转移概率矩阵 说明 改变游动的概率规则 就可得到不同方式的 随机游动和相应的马氏链 如果把点1改为吸收壁 相应链的转移概率矩阵只须把P中第1行改为 例 无限制随机游动问题质点在直线上做随机游动 如某一时刻质点位于 则下一步质点以概率 向右移动一格到达 或以概率 向左移一格到达 若以 n 表示时刻 时质点的位置 则 n n 0 1 2 是一个随机过程 而且当 n i时 n 1 n 2 n k 等 时刻后质点所处的状态只与 n i有关 而与质点在 以前是如何到达 的完全无关 所以它是一个齐次马尔可夫链 其状态空间为I 2 1 0 1 2 而其一步转移概率为 2020 1 29 郑州大学信息工程学院 26 下面求它的 步转移概率pij n 已知每次转移只有两种可能 向左的概率为 向右的概率为 而 次转移的结果是从 到 如果 次转移中向右m1次 向左m2次 则 2020 1 29 郑州大学信息工程学院 27 例 有限制的随机游动问题 带有两个吸收壁的随机游动 2020 1 29 郑州大学信息工程学院 28 随机游动的状态空间为I 0 1 2 a 0 a两状态为吸收态 该过程仍是齐次马尔可夫链 它的一步转移概率矩阵为 例 赌徒输光问题 两个赌徒甲 乙进行一系列赌博 在每一局中甲获胜的概率为p 乙获胜的概率为q p q 1 每一局后 负者要付一元给胜者 如果起始时甲有资本a元 乙有资本b元 a b c元 两人赌博直到甲输光或乙输光为止 求甲输光的概率 这个问题实质上是带有两个吸收壁的随机游动 这时的状态空间为 0 1 2 c c a b a 1 b 1 现在的问题是求质点从a点出发到达0状态先于到达c状态概率 2020 1 29 郑州大学信息工程学院 29 解 设0 j c 设uj为质点从j出发到达0状态先于到达c状态的概率 根据全概率公式有 考虑质点从j出发移动一步后的情况 在以概率p移到j 1的假设下 到达0状态先于到达c状态的概率为uj 1 同理 在以概率q移到j 1的前提下 到达0先于到达c的概率为uj 1 利用全概率定理就可以得到上述方程 这一方程实质上是一差分方程 它的边界条件是 2020 1 29 郑州大学信息工程学院 30 2020 1 29 郑州大学信息工程学院 31 因此 2020 1 29 郑州大学信息工程学院 32 故 当r 1时u0 uc 1 cd0而uj c j d0因此 故 由以上计算结果可知 当r 1即p q时 甲先输光的概率为 2020 1 29 郑州大学信息工程学院 33 当r 1即p q时 甲先输光的概率为b c用同样的方法可以求得乙先输光的概率 当p q时 乙先输光的概率为当p q时 乙先输光的概率为a c 2020 1 29 郑州大学信息工程学院 34 例 2020 1 29 郑州大学信息工程学院 35 解 2020 1 29 郑州大学信息工程学院 36 概率为 2020 1 29 郑州大学信息工程学院 37 某计算机房的一台计算机经常出故障 研究者每隔15分钟观察一次计算机运行状态 收集了24小时的数据 共作97次观察 用1表示正常状态 用0表示不正常状态 所得的数据序列如下 1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111 分析 状态空间 I 0 1 例 2020 1 29 郑州大学信息工程学院 38 96次状态转移的情况 因此 一步转移概率可用频率近似地表示为 有些问题虽然不是马尔可夫链 但经过某些处理 仍可以把它看作马尔可夫链 例 在天气预报问题中 认为今日是否下雨依赖于前两天的天气状况 并规定 昨日 今日都下雨 明日有雨的概率为0 7 今日有雨 昨日无雨 明日有雨的概率为0 5 昨日有雨 今日无雨 明日有雨的概率为0 4 昨日 今日均无雨 明日有雨的概率为0 2 该问题不是马尔可夫链 但是 经过如下处理却可以把它看作马尔可夫链 2020 1 29 郑州大学信息工程学院 39 设昨日 今日连续两天有雨称为状态0 RR 昨日无雨 今日有雨称为状态1 NR 昨日有雨 今日无雨称为状态2 RN 昨日 今日均无雨称为状态3 NN 于是形成了四个状态的马尔可夫链 其中 2020 1 29 郑州大学信息工程学院 40 其中R代表有雨 N代表无雨 于是它的一步转移概率矩阵为 2020 1 29 郑州大学信息工程学院 41 有了一步转移概率矩阵就可以对今后的天气进行预报 例如 若星期一 星期二均下雨 求星期四下雨的概率 从一步转移概率矩阵可以计算出两步转移概率矩阵 2020 1 29 郑州大学信息工程学院 42 星期四下雨意味着过程所处的状态为0或1 因此星期一 二连续下雨 星期四下雨的概率为