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

《《随机过程及其应用随机过程及其应用》》 离散时间离散时间MarkovMarkov链链第第5 5讲讲2024/8/19郑州大学信息工程学院1内容提要•离散时间离散时间Markov链的定义、性质链的定义、性质•离散时间离散时间Markov链举例链举例2024/8/19郑州大学信息工程学院2 安德雷安德雷.安德耶维奇安德耶维奇.马尔可夫马尔可夫(A.A.Markov): 俄数学家，俄数学家，1856~1922 概率和统计领域专家概率和统计领域专家 当年当年Markov研究普希金诗歌里元音字母和辅音字母研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了交替出现的规律时提出了Markov过程的数学模型过程的数学模型 Markov过程过程80年代兴起，在现代工程、自然科学、年代兴起，在现代工程、自然科学、社会科学中应用广泛社会科学中应用广泛2024/8/19郑州大学信息工程学院31、马尔可夫过程定义马尔可夫过程定义• •定定定定义义：：设有一随机有一随机过程程{ (t),t T},t1

这些条件概率密度称为这些条件概率密度称为转移概率密度转移概率密度•马尔可夫过程马尔可夫过程{ (t),t T}可能取的值的全体组成过程的可能取的值的全体组成过程的状态状态空间空间，，  (t)可能取的值称为可能取的值称为状态状态  (t)=x代表在代表在 t 时刻过程时刻过程（或系统）处在状态（或系统）处在状态x 马尔可夫过程的状态空间可以是连马尔可夫过程的状态空间可以是连续的，也可以是离散的马尔可夫过程的参数续的，也可以是离散的马尔可夫过程的参数t可以是连续的，可以是连续的，也可以是离散的也可以是离散的•Markov过程的分类过程的分类 Markov链：状态值可数离散的链：状态值可数离散的Markov过程过程–离散时间离散时间Markov链（第二章）链（第二章）–连续时间连续时间Markov链（第三章）链（第三章）2024/8/19郑州大学信息工程学院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)所取的所取的值有关，把有关，把这类随机随机过程成程成为马尔可马尔可夫链夫链2024/8/19郑州大学信息工程学院8由定义可知由定义可知：2024/8/19郑州大学信息工程学院9一步转移概率的两个性质一步转移概率的两个性质：•（1）•（2）2024/8/19郑州大学信息工程学院10齐次马尔可夫链齐次马尔可夫链•定义：如果在马尔可夫链中定义：如果在马尔可夫链中 即从ｉ状态转移到ｊ状态的概率与ｋ无关，则称这类马尔可即从ｉ状态转移到ｊ状态的概率与ｋ无关，则称这类马尔可夫链为夫链为齐次马尔可夫链齐次马尔可夫链。

•设Ｐ代表一步转移概率设Ｐ代表一步转移概率p pijij所组成的矩阵，且状态空间Ｉ由状所组成的矩阵，且状态空间Ｉ由状态０，１，２，态０，１，２，……所组成，则所组成，则 2024/8/19郑州大学信息工程学院11一步转移概率矩阵P中每个元素为非负，每行之和均为12 2、、 切普曼切普曼- -柯尔莫哥洛夫方程式柯尔莫哥洛夫方程式（（C-K方程方程）•m步转移概率步转移概率 :•性质性质：•m=1时即一步转移概率，时即一步转移概率，m=0时规定：时规定：2024/8/19郑州大学信息工程学院12 对于对于m步转移概率矩阵有步转移概率矩阵有C-K方程方程：2024/8/19郑州大学信息工程学院13证明：2024/8/19郑州大学信息工程学院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 m步转移概率由一步转移概率所完全决定步转移概率由一步转移概率所完全决定2024/8/19郑州大学信息工程学院15马尔可夫链的分布马尔可夫链的分布：：（1）初始分布初始分布 称称 , iI为马氏氏链的初始分布的初始分布（（2））有限维分布有限维分布 定理：马尔可夫链的有限维分布由其初始分布和一步转定理：马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定移概率所完全确定2024/8/19郑州大学信息工程学院16转移移概概率率决决定定了了马氏氏链的的运运动的的统计规律律 因因此此, 确确定定马氏氏链的的任任意意n步步转移移概概率率成成为马氏氏链理理论中中的的重重要要问题之一•证明证明： 2024/8/19郑州大学信息工程学院17马尔可夫链的例子马尔可夫链的例子•例：天气预报问题例：天气预报问题 如果明天是否有雨仅与今天的天气（是否有雨）有关，如果明天是否有雨仅与今天的天气（是否有雨）有关，而与过去的天气无关，并设今日下雨，明日有雨的概率而与过去的天气无关，并设今日下雨，明日有雨的概率为为 ，今日无雨明日有雨的概率为，今日无雨明日有雨的概率为 ，又假定把有雨称为，又假定把有雨称为０状态天气，把无雨称为１状态天气；０状态天气，把无雨称为１状态天气；  (n)表示表示n时的时的状态天气，则状态天气，则 (n)是以是以{0，，1}为状态空间的齐次马尔可夫为状态空间的齐次马尔可夫链，链，它的一步转移矩阵为它的一步转移矩阵为 ：2024/8/19郑州大学信息工程学院18设 =0.7，，  =0.4，则一步转移概率矩阵为，则一步转移概率矩阵为2024/8/19郑州大学信息工程学院19四步转移概率矩阵：四步转移概率矩阵：由此可知，今日有雨且第四日仍有雨的概率为：由此可知，今日有雨且第四日仍有雨的概率为：P00(4)=0.5749则两步转移概率矩阵：则两步转移概率矩阵：2024/8/19郑州大学信息工程学院20例例解解 (1)先求出先求出2步转移概率矩阵步转移概率矩阵:2024/8/19郑州大学信息工程学院21例例 一维随机游动一维随机游动游动的概率规则游动的概率规则如果如果Q现在位于点现在位于点 i (1< i <5),则下一时刻各以则下一时刻各以1/3的概率向的概率向左或向右移动一格左或向右移动一格, 或以或以1/3的概率留在原处的概率留在原处; 2024/8/19郑州大学信息工程学院22如果如果Q现在位于现在位于1(或或5)这点上这点上, 则下一时刻就以概率则下一时刻就以概率1移动到移动到2(或或4)这一点上这一点上. 1和和5这两点称为这两点称为反射壁反射壁.上面这种游动称为上面这种游动称为带有两个带有两个反射壁反射壁的随机游动的随机游动.模拟方法模拟方法:产生均匀分布的随机数序列产生均匀分布的随机数序列13232211122…,其其中中1表示左移表示左移;2表示不动表示不动;3表示右移表示右移.2024/8/19郑州大学信息工程学院23理论分析理论分析:状态空间是状态空间是I.而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关.所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 2024/8/19郑州大学信息工程学院24一步转移概率一步转移概率2024/8/19郑州大学信息工程学院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,…}, 而其一步转移概率为：而其一步转移概率为：2024/8/19郑州大学信息工程学院26•下面求它的ｎ步转移概率下面求它的ｎ步转移概率pij(n)已知每次转移只有两种可能，已知每次转移只有两种可能，向左的概率为ｑ，向右的概率为ｐ，而ｎ次转移的结果是从ｉ向左的概率为ｑ，向右的概率为ｐ，而ｎ次转移的结果是从ｉ到ｊ。

如果ｎ次转移中向右到ｊ如果ｎ次转移中向右m1次，向左次，向左m2次，则次，则 2024/8/19郑州大学信息工程学院27•例例：有限制的随机游动问题（带有两个吸收壁的随机游动）有限制的随机游动问题（带有两个吸收壁的随机游动）2024/8/19郑州大学信息工程学院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 状态概率状态概率2024/8/19郑州大学信息工程学院29解解 :设设0

当用同样的方法可以求得乙先输光的概率当p  q时，乙先输时，乙先输光的概率为光的概率为当当p=q时，乙先输光的概率为时，乙先输光的概率为a/c2024/8/19郑州大学信息工程学院34例例2024/8/19郑州大学信息工程学院35解解2024/8/19郑州大学信息工程学院36概率为概率为2024/8/19郑州大学信息工程学院37 某计算机房的一台计算机经常出故障某计算机房的一台计算机经常出故障,研究者研究者每隔每隔15分钟观察一次计算机运行状态分钟观察一次计算机运行状态,收集了收集了24小小时的数据时的数据 (共作共作97次观察次观察) . 用用1表示正常状态表示正常状态, 用用0表示不正常状态表示不正常状态, 所得的数据序列如下所得的数据序列如下:1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111分析分析状态空间状态空间: I={0, 1}. 例例2024/8/19郑州大学信息工程学院3896 次状态转移的情况次状态转移的情况:因此因此, 一步转移概率可用频率近似地表示为一步转移概率可用频率近似地表示为:•有些问题虽然不是马尔可夫链，但经过某些处理，仍可以有些问题虽然不是马尔可夫链，但经过某些处理，仍可以把它看作马尔可夫链。

把它看作马尔可夫链•例：在天气预报问题中，认为今日是否下雨依赖于前两天例：在天气预报问题中，认为今日是否下雨依赖于前两天的天气状况，并规定：昨日、今日都下雨，明日有雨的概的天气状况，并规定：昨日、今日都下雨，明日有雨的概率为率为0.7，今日有雨、昨日无雨，明日有雨的概率为，今日有雨、昨日无雨，明日有雨的概率为0.5；昨；昨日有雨、今日无雨，明日有雨的概率为日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均；昨日、今日均无雨，明日有雨的概率为无雨，明日有雨的概率为0.2该问题不是马尔可夫链该问题不是马尔可夫链但是，经过如下处理却可以把它看作马尔可夫链是，经过如下处理却可以把它看作马尔可夫链 2024/8/19郑州大学信息工程学院39•设昨日、今日连续两天有雨称为状态设昨日、今日连续两天有雨称为状态0(RR)，昨日无雨、，昨日无雨、今日有雨称为状态今日有雨称为状态1(NR)，昨日有雨、今日无雨称为状态，昨日有雨、今日无雨称为状态2(RN)，昨日、今日均无雨称为状态，昨日、今日均无雨称为状态3(NN)，于是形成了，于是形成了四个状态的马尔可夫链，其中四个状态的马尔可夫链，其中2024/8/19郑州大学信息工程学院40•其中其中R代表有雨，代表有雨，N代表无雨。

于是它的一步转移概率代表无雨于是它的一步转移概率矩阵为矩阵为2024/8/19郑州大学信息工程学院41有了一步转移概率矩阵就可以对今后的天气进行预报有了一步转移概率矩阵就可以对今后的天气进行预报•例如，若星期一、星期二均下雨，求星期四下雨的概率例如，若星期一、星期二均下雨，求星期四下雨的概率•从一步转移概率矩阵可以计算出两步转移概率矩阵从一步转移概率矩阵可以计算出两步转移概率矩阵2024/8/19郑州大学信息工程学院42星期四下雨意味着过程所处的状态为星期四下雨意味着过程所处的状态为0或或1，因此星期一、二，因此星期一、二连续下雨，星期四下雨的概率为连续下雨，星期四下雨的概率为。