随机过程及其应用随机过程及其应用 离散时间离散时间MarkovMarkov链链第第5 5讲讲2024/9/11随机过程第5讲(马尔科夫链定义和性质)内容提要离散时间离散时间Markov链的定义、性质链的定义、性质离散时间离散时间Markov链举例链举例2024/9/12随机过程第5讲(马尔科夫链定义和性质) 安德雷安德雷.安德耶维奇安德耶维奇.马尔可夫马尔可夫(A.A.Markov): 俄数学家，俄数学家，18561922 概率和统计领域专家。概率和统计领域专家。 当年当年Markov研究普希金诗歌里元音字母研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了和辅音字母交替出现的规律时提出了Markov过程过程的数学模型的数学模型 Markov过程过程80年代兴起，在现代工程、自年代兴起，在现代工程、自然科学、社会科学中应用广泛。然科学、社会科学中应用广泛。2024/9/13随机过程第5讲(马尔科夫链定义和性质)1、马尔可夫过程定义马尔可夫过程定义 定定定定义义义义：设设有一随机有一随机过过程程 (t),t T,t1t2t3tmtm+1 T，若在，若在t1、t2、t3、tm、tm+1 时对时对 (t)观测观测得到相得到相应应的的观测值观测值x1,x2,x3,xm,xm+1满满足条件：足条件：则则称称这类过这类过程程为为具有具有马马尔尔可夫性可夫性质质的随机的随机过过程或程或马马尔尔可可夫夫过过程程2024/9/14随机过程第5讲(马尔科夫链定义和性质)Markov过程也可表示为如下形式：过程也可表示为如下形式：2024/9/15随机过程第5讲(马尔科夫链定义和性质) 该式表明该式表明 (t)的的n维概率密度等于一些条件概率密度与维概率密度等于一些条件概率密度与t1时时初始概率密度的乘积初始概率密度的乘积。这些条件概率密度称为。这些条件概率密度称为转移概率密度转移概率密度。2024/9/16随机过程第5讲(马尔科夫链定义和性质)马尔可夫过程马尔可夫过程 (t),t T可能取的值的全体组成过程的可能取的值的全体组成过程的状态状态空间空间， (t)可能取的值称为可能取的值称为状态状态。 (t)=x代表在代表在 t 时刻过程时刻过程（或系统）处在状态（或系统）处在状态x 。马尔可夫过程的状态空间可以是连。马尔可夫过程的状态空间可以是连续的，也可以是离散的。马尔可夫过程的参数续的，也可以是离散的。马尔可夫过程的参数t可以是连续的，可以是连续的，也可以是离散的。也可以是离散的。Markov过程的分类过程的分类 Markov链：状态值可数离散的链：状态值可数离散的Markov过程过程离散时间离散时间Markov链（第二章）链（第二章）连续时间连续时间Markov链（第三章）链（第三章）2024/9/17随机过程第5讲(马尔科夫链定义和性质)马尔可夫链的定义马尔可夫链的定义 (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/9/18随机过程第5讲(马尔科夫链定义和性质)由定义可知由定义可知：2024/9/19随机过程第5讲(马尔科夫链定义和性质)一步转移概率的两个性质一步转移概率的两个性质：（1）（2）2024/9/110随机过程第5讲(马尔科夫链定义和性质)齐次马尔可夫链齐次马尔可夫链定义：如果在马尔可夫链中定义：如果在马尔可夫链中 即从状态转移到状态的概率与无关，则称这类马尔可即从状态转移到状态的概率与无关，则称这类马尔可夫链为夫链为齐次马尔可夫链齐次马尔可夫链。设代表一步转移概率设代表一步转移概率p pijij所组成的矩阵，且状态空间由状所组成的矩阵，且状态空间由状态，态，所组成，则所组成，则 一步转移概率矩阵P中每个元素为非负，每行之和均为1。2024/9/111随机过程第5讲(马尔科夫链定义和性质)2 2、 切普曼切普曼- -柯尔莫哥洛夫方程式柯尔莫哥洛夫方程式（C-K方程方程）m步转移概率步转移概率 :性质性质：m=1时即一步转移概率，时即一步转移概率，m=0时规定：时规定：2024/9/112随机过程第5讲(马尔科夫链定义和性质) 对于对于m步转移概率矩阵有步转移概率矩阵有C-K方程方程：证明：2024/9/113随机过程第5讲(马尔科夫链定义和性质)这一事件可分解成这一事件可分解成:件的和事件, 如下图所示:2024/9/114随机过程第5讲(马尔科夫链定义和性质)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/9/115随机过程第5讲(马尔科夫链定义和性质)马尔可夫链的分布马尔可夫链的分布：（1）初始分布初始分布 称称 , iI为马为马氏氏链链的初始分布的初始分布（2）有限维分布有限维分布 定理：马尔可夫链的有限维分布由其初始分布和一步转定理：马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定移概率所完全确定。转转移移概概率率决决定定了了马马氏氏链链的的运运动动的的统统计计规规律律。 因因此此, 确确定定马马氏氏链链的的任任意意n步步转转移移概概率率成成为为马马氏氏链链理理论论中中的的重重要要问问题题之一。之一。2024/9/116随机过程第5讲(马尔科夫链定义和性质)证明证明： 2024/9/117随机过程第5讲(马尔科夫链定义和性质)马尔可夫链的例子马尔可夫链的例子例：天气预报问题例：天气预报问题 如果明天是否有雨仅与今天的天气（是否有雨）有关，如果明天是否有雨仅与今天的天气（是否有雨）有关，而与过去的天气无关，并设今日下雨，明日有雨的概率而与过去的天气无关，并设今日下雨，明日有雨的概率为为 ，今日无雨明日有雨的概率为，今日无雨明日有雨的概率为 ，又假定把有雨称为，又假定把有雨称为状态天气，把无雨称为状态天气；状态天气，把无雨称为状态天气； (n)表示表示n时的时的状态天气，则状态天气，则 (n)是以是以0，1为状态空间的齐次马尔可夫为状态空间的齐次马尔可夫链，链，它的一步转移矩阵为它的一步转移矩阵为 ：设 =0.7， =0.4，则一步转移概率矩阵为，则一步转移概率矩阵为2024/9/118随机过程第5讲(马尔科夫链定义和性质)四步转移概率矩阵：四步转移概率矩阵：由此可知，今日有雨且第四日仍有雨的概率为：由此可知，今日有雨且第四日仍有雨的概率为：P00(4)=0.5749则两步转移概率矩阵：则两步转移概率矩阵：2024/9/119随机过程第5讲(马尔科夫链定义和性质)例例解解 (1)先求出先求出2步转移概率矩阵步转移概率矩阵:2024/9/120随机过程第5讲(马尔科夫链定义和性质)例例 一维随机游动一维随机游动游动的概率规则游动的概率规则如果如果Q现在位于点现在位于点 i (1 i 5),则下一时刻各以则下一时刻各以1/3的概率向的概率向左或向右移动一格左或向右移动一格, 或以或以1/3的概率留在原处的概率留在原处; 2024/9/121随机过程第5讲(马尔科夫链定义和性质)如果如果Q现在位于现在位于1(或或5)这点上这点上, 则下一时刻就以概率则下一时刻就以概率1移动到移动到2(或或4)这一点上这一点上. 1和和5这两点称为这两点称为反射壁反射壁.上面这种游动称为上面这种游动称为带有两个带有两个反射壁反射壁的随机游动的随机游动.模拟方法模拟方法:产生均匀分布的随机数序列产生均匀分布的随机数序列,其中其中1表示左表示左移移;2表示不动表示不动;3表示右移表示右移.2024/9/122随机过程第5讲(马尔科夫链定义和性质)理论分析理论分析:状态空间是状态空间是I.而与时刻而与时刻 n 以前所处的状态无关以前所处的状态无关.所以它是一个马氏链所以它是一个马氏链, 且是齐次的且是齐次的. 2024/9/123随机过程第5讲(马尔科夫链定义和性质)一步转移概率一步转移概率2024/9/124随机过程第5讲(马尔科夫链定义和性质)一一步步转转移移概概率率矩矩阵阵说明说明:改变游动的概率规则改变游动的概率规则, 就可得到不同方式的就可得到不同方式的随机游动和相应的马氏链随机游动和相应的马氏链. 如果把点如果把点 1 改为改为吸收壁吸收壁, 相应链的转移概率矩阵只须把相应链的转移概率矩阵只须把P 中第中第1行改为行改为2024/9/125随机过程第5讲(马尔科夫链定义和性质)例：无限制随机游动问题例：无限制随机游动问题 质点在直线上做随机游动。如某一时刻质点位于，则质点在直线上做随机游动。如某一时刻质点位于，则下一步质点以概率向右移动一格到达。或以概率下一步质点以概率向右移动一格到达。或以概率向左移一格到达。若以向左移一格到达。若以 (n) 表示时刻时质表示时刻时质点的位置，则点的位置，则 (n),n=0,1,2,是一个随机过程。而且当是一个随机过程。而且当 (n) =i时，时， (n+1), (n+2), (n+k),等时刻后质点所处的状态等时刻后质点所处的状态只与只与 (n)=i有关，而与质点在以前是如何到达的完有关，而与质点在以前是如何到达的完全无关。所以它是一个齐次马尔可夫链，其状态空间为全无关。所以它是一个齐次马尔可夫链，其状态空间为I: ,-2,-1,0,1,2, 而其一步转移概率为：而其一步转移概率为：2024/9/126随机过程第5讲(马尔科夫链定义和性质)下面求它的步转移概率下面求它的步转移概率pij(n)。已知每次转移只有两种可能，。已知每次转移只有两种可能，向左的概率为，向右的概率为，而次转移的结果是从向左的概率为，向右的概率为，而次转移的结果是从到。如果次转移中向右到。如果次转移中向右m1次，向左次，向左m2次，则次，则 2024/9/127随机过程第5讲(马尔科夫链定义和性质)例例：有限制的随机游动问题（带有两个吸收壁的随机游动）有限制的随机游动问题（带有两个吸收壁的随机游动） 随机游动的状态空间为I：0，1，2， a，0、 a 两状态为吸收态。该过程仍是齐次马尔可夫链，它的一步转移概率矩阵为2024/9/128随机过程第5讲(马尔科夫链定义和性质)例：赌徒输光问题例：赌徒输光问题两个赌徒甲、乙进行一系列赌博。在每一局中甲获胜的概两个赌徒甲、乙进行一系列赌博。在每一局中甲获胜的概率为率为p ，乙获胜的概率为，乙获胜的概率为q，p+q=1，每一局后，负者要付一，每一局后，负者要付一元给胜者。如果起始时甲有资本元给胜者。如果起始时甲有资本a 元，乙有资本元，乙有资本b 元，元，a+b=c元，两人赌博直到甲输光或乙输光为止，求甲输光的元，两人赌博直到甲输光或乙输光为止，求甲输光的概率。概率。这个问题实质上是带有两个吸收壁的随机游动。这时的状这个问题实质上是带有两个吸收壁的随机游动。这时的状态空间为态空间为0，1，2，, c , c=a+b, a 1,b 1。现在的问题是。现在的问题是求质点从求质点从a 点出发到达点出发到达0状态先于到达状态先于到达c 状态概率。状态概率。解解 :设设0jc，设，设uj为质点从为质点从j 出发到达出发到达0状态先于到达状态先于到达c状态状态的概率。根据全概率公式有的概率。根据全概率公式有:2024/9/129随机过程第5讲(马尔科夫链定义和性质)考虑质点从考虑质点从j出发移动一步后的情况。在以概率出发移动一步后的情况。在以概率p移到移到j+1的假设的假设下，到达下，到达0状态先于到达状态先于到达 c状态的概率为状态的概率为uj+1 。同理，在以概率。同理，在以概率q移到移到j-1的前提下，到达的前提下，到达0先于到达先于到达c的概率为的概率为uj-1。利用全概率定。利用全概率定理就可以得到上述方程。这一方程实质上是一差分方程，它的理就可以得到上述方程。这一方程实质上是一差分方程，它的边界条件是边界条件是: 2024/9/130随机过程第5讲(马尔科夫链定义和性质)2024/9/131随机过程第5讲(马尔科夫链定义和性质)因此：因此：故故当当r=1时时 u0-uc=1=cd0而而 uj=(c-j)d0 因此因此 故故2024/9/132随机过程第5讲(马尔科夫链定义和性质)由以上计算结果可知，当由以上计算结果可知，当r 1即即p q时，甲先输光的概率为时，甲先输光的概率为当当r=1即即p=q时，甲先输光的概率为时，甲先输光的概率为b/c用同样的方法可以求得乙先输光的概率。当用同样的方法可以求得乙先输光的概率。当p q时，乙先输时，乙先输光的概率为光的概率为当当p=q时，乙先输光的概率为时，乙先输光的概率为a/c2024/9/133随机过程第5讲(马尔科夫链定义和性质)例例2024/9/134随机过程第5讲(马尔科夫链定义和性质)解解2024/9/135随机过程第5讲(马尔科夫链定义和性质)概率为概率为2024/9/136随机过程第5讲(马尔科夫链定义和性质) 某计算机房的一台计算机经常出故障某计算机房的一台计算机经常出故障,研究者研究者每隔每隔15分钟观察一次计算机运行状态分钟观察一次计算机运行状态,收集了收集了24小小时的数据时的数据 (共作共作97次观察次观察) . 用用1表示正常状态表示正常状态, 用用0表示不正常状态表示不正常状态, 所得的数据序列如下所得的数据序列如下:111001000011110111111001111111110001101101111011011010111101110111101111110011011111100111分析分析状态空间状态空间: I=0, 1. 例例2024/9/137随机过程第5讲(马尔科夫链定义和性质)96 次状态转移的情况次状态转移的情况:因此因此, 一步转移概率可用频率近似地表示为一步转移概率可用频率近似地表示为:2024/9/138随机过程第5讲(马尔科夫链定义和性质)有些问题虽然不是马尔可夫链，但经过某些处理，仍可以有些问题虽然不是马尔可夫链，但经过某些处理，仍可以把它看作马尔可夫链。把它看作马尔可夫链。例：在天气预报问题中，认为今日是否下雨依赖于前两天例：在天气预报问题中，认为今日是否下雨依赖于前两天的天气状况，并规定：昨日、今日都下雨，明日有雨的概的天气状况，并规定：昨日、今日都下雨，明日有雨的概率为率为0.7，今日有雨、昨日无雨，明日有雨的概率为，今日有雨、昨日无雨，明日有雨的概率为0.5；昨；昨日有雨、今日无雨，明日有雨的概率为日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均；昨日、今日均无雨，明日有雨的概率为无雨，明日有雨的概率为0.2。该问题不是马尔可夫链。但。该问题不是马尔可夫链。但是，经过如下处理却可以把它看作马尔可夫链。是，经过如下处理却可以把它看作马尔可夫链。 2024/9/139随机过程第5讲(马尔科夫链定义和性质)设昨日、今日连续两天有雨称为状态设昨日、今日连续两天有雨称为状态0(RR)，昨日无雨、，昨日无雨、今日有雨称为状态今日有雨称为状态1(NR)，昨日有雨、今日无雨称为状态，昨日有雨、今日无雨称为状态2(RN)，昨日、今日均无雨称为状态，昨日、今日均无雨称为状态3(NN)，于是形成了，于是形成了四个状态的马尔可夫链，其中四个状态的马尔可夫链，其中2024/9/140随机过程第5讲(马尔科夫链定义和性质)其中其中R代表有雨，代表有雨，N代表无雨。于是它的一步转移概率代表无雨。于是它的一步转移概率矩阵为矩阵为有了一步转移概率矩阵就可以对今后的天气进行预报。有了一步转移概率矩阵就可以对今后的天气进行预报。2024/9/141随机过程第5讲(马尔科夫链定义和性质)例如，若星期一、星期二均下雨，求星期四下雨的概率。例如，若星期一、星期二均下雨，求星期四下雨的概率。从一步转移概率矩阵可以计算出两步转移概率矩阵从一步转移概率矩阵可以计算出两步转移概率矩阵星期四下雨意味着过程所处的状态为星期四下雨意味着过程所处的状态为0或或1，因此星期一、二，因此星期一、二连续下雨，星期四下雨的概率为连续下雨，星期四下雨的概率为2024/9/142随机过程第5讲(马尔科夫链定义和性质)