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

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

2、1t2t3tmtm+1 T，若在t1、t2、t3、tm、tm+1 时对(t)观测得到相应的观测值x1,x2,x3,xm,xm+1满足条件： 则称这类过程为具有马尔可夫性质的随机过程或马尔可夫过程,2020/9/14,郑州大学信息工程学院,4,Markov过程也可表示为如下形式：,2020/9/14,郑州大学信息工程学院,5,2020/9/14,郑州大学信息工程学院,6,该式表明(t)的n维概率密度等于一些条件概率密度与t1时初始概率密度的乘积。这些条件概率密度称为转移概率密度。,马尔可夫过程(t),tT可能取的值的全体组成过程的状态空间， (t)可能取的值称为状态。 (t)=x代表在 t 时刻

3、过程（或系统）处在状态x 。马尔可夫过程的状态空间可以是连续的，也可以是离散的。马尔可夫过程的参数t可以是连续的，也可以是离散的。 Markov过程的分类 Markov链：状态值可数离散的Markov过程 离散时间Markov链（第二章） 连续时间Markov链（第三章）,2020/9/14,郑州大学信息工程学院,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

4、-1)无关而仅与(n)所取的值有关，把这类随机过程成为马尔可夫链,2020/9/14,郑州大学信息工程学院,8,由定义可知：,2020/9/14,郑州大学信息工程学院,9,一步转移概率的两个性质：,（1） （2）,2020/9/14,郑州大学信息工程学院,10,齐次马尔可夫链,定义：如果在马尔可夫链中 即从状态转移到状态的概率与无关，则称这类马尔可夫链为齐次马尔可夫链。 设代表一步转移概率pij所组成的矩阵，且状态空间由状态，所组成，则,2020/9/14,郑州大学信息工程学院,11,一步转移概率矩阵P中每个元素为非负，每行之和均为1。,2、 切普曼-柯尔莫哥洛夫方程式（C-K方程）,m步转移

5、概率 : 性质： m=1时即一步转移概率，m=0时规定：,2020/9/14,郑州大学信息工程学院,12,对于m步转移概率矩阵有C-K方程：,2020/9/14,郑州大学信息工程学院,13,证明：,2020/9/14,郑州大学信息工程学院,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时,可得： 一直推

6、下去可得： 结论：马尔可夫链的m步转移概率由一步转移概率所完全决定,2020/9/14,郑州大学信息工程学院,15,马尔可夫链的分布：,（1）初始分布 称 , iI为马氏链的初始分布 （2）有限维分布 定理：马尔可夫链的有限维分布由其初始分布和一步转移概率所完全确定。,2020/9/14,郑州大学信息工程学院,16,转移概率决定了马氏链的运动的统计规律。 因此, 确定马氏链的任意n步转移概率成为马氏链理论中的重要问题之一。,证明：,2020/9/14,郑州大学信息工程学院,17,马尔可夫链的例子,例：天气预报问题 如果明天是否有雨仅与今天的天气（是否有雨）有关，而与过去的天气无关，并设今日下雨

7、，明日有雨的概率为，今日无雨明日有雨的概率为，又假定把有雨称为状态天气，把无雨称为状态天气； (n)表示n时的状态天气，则(n)是以0，1为状态空间的齐次马尔可夫链，它的一步转移矩阵为 ：,2020/9/14,郑州大学信息工程学院,18,设=0.7， =0.4，则一步转移概率矩阵为,2020/9/14,郑州大学信息工程学院,19,四步转移概率矩阵：,由此可知，今日有雨且第四日仍有雨的概率为：P00(4)=0.5749,则两步转移概率矩阵：,2020/9/14,郑州大学信息工程学院,20,例,解,(1)先求出2步转移概率矩阵:,2020/9/14,郑州大学信息工程学院,21,例 一维随机游动,游

8、动的概率规则,如果Q现在位于点 i (1 i 5),则下一时刻各以1/3的概率向左或向右移动一格, 或以1/3的概率留在原处;,2020/9/14,郑州大学信息工程学院,22,如果Q现在位于1(或5)这点上, 则下一时刻就以概率1移动到2(或4)这一点上. 1和5这两点称为反射壁.,上面这种游动称为带有两个反射壁的随机游动.,模拟方法:产生均匀分布的随机数序其中1表示左移;2表示不动;3表示右移.,2020/9/14,郑州大学信息工程学院,23,理论分析:,状态空间是I.,而与时刻 n 以前所处的状态无关.,所以它是一个马氏链, 且是齐次的.,2020/9/14,郑州

9、大学信息工程学院,24,一步转移概率,2020/9/14,郑州大学信息工程学院,25,一步转移概率矩阵,说明:改变游动的概率规则, 就可得到不同方式的,随机游动和相应的马氏链. 如果把点 1 改为吸收壁,相应链的转移概率矩阵只须把P 中第1行改为,例：无限制随机游动问题 质点在直线上做随机游动。如某一时刻质点位于，则下一步质点以概率向右移动一格到达。或以概率向左移一格到达。若以(n) 表示时刻时质点的位置，则(n),n=0,1,2,是一个随机过程。而且当(n) =i时， (n+1), (n+2), (n+k),等时刻后质点所处的状态只与 (n)=i有关，而与质点在以前是如何到达的完全无关。所以

10、它是一个齐次马尔可夫链，其状态空间为I: ,-2,-1,0,1,2, 而其一步转移概率为：,2020/9/14,郑州大学信息工程学院,26,下面求它的步转移概率pij(n)。已知每次转移只有两种可能，向左的概率为，向右的概率为，而次转移的结果是从到。如果次转移中向右m1次，向左m2次，则,2020/9/14,郑州大学信息工程学院,27,例：有限制的随机游动问题（带有两个吸收壁的随机游动）,2020/9/14,郑州大学信息工程学院,28,随机游动的状态空间为I：0，1，2， a，0、 a 两状态为吸收态。该过程仍是齐次马尔可夫链，它的一步转移概率矩阵为,例：赌徒输光问题,两个赌徒甲、乙进行一系列

11、赌博。在每一局中甲获胜的概率为p ，乙获胜的概率为q，p+q=1，每一局后，负者要付一元给胜者。如果起始时甲有资本a 元，乙有资本b 元，a+b=c元，两人赌博直到甲输光或乙输光为止，求甲输光的概率。 这个问题实质上是带有两个吸收壁的随机游动。这时的状态空间为0，1，2，, c , c=a+b, a1,b 1。现在的问题是求质点从a 点出发到达0状态先于到达c 状态概率。,2020/9/14,郑州大学信息工程学院,29,解 :设0jc，设uj为质点从j 出发到达0状态先于到达c状态的概率。根据全概率公式有:,考虑质点从j出发移动一步后的情况。在以概率p移到j+1的假设下，到达0状态先于到达 c

12、状态的概率为uj+1 。同理，在以概率q移到j-1的前提下，到达0先于到达c的概率为uj-1。利用全概率定理就可以得到上述方程。这一方程实质上是一差分方程，它的边界条件是:,2020/9/14,郑州大学信息工程学院,30,2020/9/14,郑州大学信息工程学院,31,因此：,2020/9/14,郑州大学信息工程学院,32,故,当r=1时 u0-uc=1=cd0 而 uj=(c-j)d0 因此,故,由以上计算结果可知，当r1即p q时，甲先输光的概率为,2020/9/14,郑州大学信息工程学院,33,当r=1即p=q时，甲先输光的概率为b/c 用同样的方法可以求得乙先输光的概率。当p q时，乙

13、先输光的概率为 当p=q时，乙先输光的概率为a/c,2020/9/14,郑州大学信息工程学院,34,例,2020/9/14,郑州大学信息工程学院,35,解,2020/9/14,郑州大学信息工程学院,36,概率为,2020/9/14,郑州大学信息工程学院,37,某计算机房的一台计算机经常出故障,研究者 每隔15分钟观察一次计算机运行状态,收集了24小 时的数据 (共作97次观察) . 用1表示正常状态, 用0 表示不正常状态, 所得的数据序列如下:,1110010011111110011110111111001111111110001101101,111011011010111101110111

14、101111110011011111100111,分析,状态空间: I=0, 1.,例,2020/9/14,郑州大学信息工程学院,38,96 次状态转移的情况:,因此, 一步转移概率可用频率近似地表示为:,有些问题虽然不是马尔可夫链，但经过某些处理，仍可以把它看作马尔可夫链。 例：在天气预报问题中，认为今日是否下雨依赖于前两天的天气状况，并规定：昨日、今日都下雨，明日有雨的概率为0.7，今日有雨、昨日无雨，明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2。该问题不是马尔可夫链。但是，经过如下处理却可以把它看作马尔可夫链。,2020/9/14,郑州大学信息工程学院,39,设昨日、今日连续两天有雨称为状态0(RR)，昨日无雨、今日有雨称为状态1(NR)，昨日有雨、今日无雨称为状态2(RN)，昨日、今日均无雨称为状态3(NN)，于是形成了四个状态