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

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