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