第五章马尔可夫过程ppt课件.ppt

马尔可夫过程的概念离散参数马尔可夫链连续参数马尔可夫链生灭过程及应用,5 马尔可夫过程,有限维概率分布(簇)转移概率 绝对概率 极限分布 平稳分布状态空间的性质,5 马尔可夫过程,5.1 马尔可夫过程的概念5.1.1 有关定义随机过程马尔可夫性：（物理描述） 当随机过程在时刻 ti 所处的状态为已知的条件下，过程在时刻 t(ti)所处的状态，与过程在ti时刻以前的状态无关，而仅与在ti时刻的状态有关。这种已知“现在”状态的条件下，“将来”状态与“过去”状态无关的性质，称为马尔可夫性或无后效性。 具有马尔可夫性或无后效性的随机过程，即是马尔可夫过程。,5.1 马尔可夫过程的概念5.1.1 有关定义马尔可夫过程定义：（条件概率） 给定随机过程X(t), tT,若对于任意n(3)个时刻t1t2 tn-1 tn T, 有 PX(tn) xn | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn) xn | X(tn-1) = xn-1或 Fxn | x1, x2, , xn-1; t1, t2, , tn-1= Fxn; tn| xn-1 ; tn-1或 fxn | x1, x2, , xn-1; t1, t2, , tn-1= fxn; tn| xn-1 ; tn-1则称随机过程X(t), tT为马尔可夫过程。,5.1 马尔可夫过程的概念5.1.1 有关定义例1 直线上的随机游动。例2 电话交换站在某时刻接到的呼唤次数。 0,t=0,tm+(tm,t 次数(t)=次数(tm)+次数(tm,t) 例3 布朗运动。,5.1 马尔可夫过程的概念5.1.1 有关定义转移概率分布函数和转移概率密度的定义： 把马尔可夫过程X(t), tT的条件概率分布函数， F(x2 ; t2 | x1 ; t1= PX(t2) x2 | X(t1) = x1称为马尔可夫过程的(状态）转移概率函数。 如果 则称f(x; t| x0 ; t0) 为马尔可夫过程的转移概率密度。,5.1 马尔可夫过程的概念5.1.1 有关定义齐次马尔可夫过程的定义： 如果马尔可夫过程的转移概率函数或转移概率密度,只与转移前后的状态及相应的二个时刻的时间差有关，而与二个时刻无关，即 F(x2 ; t2 | x1 ; t1)= F(x2 | x1 ; t2 -t1) f(x2 ; t2 | x1 ; t1)= f(x2 | x1 ; t2 -t1)称具有这种特性的马尔可夫过程为齐次马尔可夫过程。,5.1 马尔可夫过程的概念5.1.1 有关定义高阶马尔可夫过程的定义： 如果马尔可夫过程在tn时刻的状态，只与tn时刻以前的tn-1, tn-2, tn-k这k个时刻的状态有关，而与更前时刻的状态无关，即 F(xn ; tn | xn-1, xn-2, xn-k , xn-k-1 , x2 , x1 ;tn-1, tn-2, tn-k , tn-k-1 , t2 , t1 )= F(xn ; tn | xn-1, xn-2, xn-k;tn-1, tn-2, tn-k)或 f(xn ; tn | xn-1, xn-2, xn-k , xn-k-1 , x2 , x1 ;tn-1, tn-2, tn-k , tn-k-1 , t2 , t1 )= f(xn ; tn | xn-1, xn-2, xn-k;tn-1, tn-2, tn-k)则称具有这种特性的马尔可夫过程为k阶马尔可夫过程。,5.1 马尔可夫过程的概念5.1.2 切普曼柯尔莫哥洛夫方程定理：马尔可夫过程的转移概率密度之间有下列关系：其中， tktrtn 。此式称为切普曼柯尔莫哥洛夫(Chapman-Kolmogorov)方程。证 利用由联合概率密度求边缘概率密度公式得根据条件概率密度公式，上式的被积函数可表示成,5.1 马尔可夫过程的概念5.1.2 切普曼柯尔莫哥洛夫方程带入上式右端有,5.1 马尔可夫过程的概念5.1.3 马尔可夫过程的分类（1）时间离散、状态离散的马尔可夫过程马尔可夫链。 参数集T=0,1,2,状态空间E=整数（2）时间连续、状态离散的马尔可夫过程可列马尔可夫过程、连续参数马尔可夫链。 参数集T=0, ,状态空间E=整数（3）时间离散、状态连续的马尔可夫过程马尔可夫序列。 参数集T= 0,1,2,状态空间E= (-, +)（4）时间连续、状态连续的马尔可夫过程。 参数集T= 0, ,状态空间E= (-, +),5.1 马尔可夫过程的概念 例1 独立过程是马尔可夫过程。 证 设X(t), tT是一独立过程，随机事件X(t1)=x1, X(t2)=x2, X(tn-1)=xn-1, X(tn) xn相互独立，所以 PX(tn) xn | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn) xn = PX(tn) xn | X(tn-1) = xn-1因此， X(t), tT是马尔可夫过程。,5.1 马尔可夫过程的概念 例2 独立增量过程是马尔可夫过程。 证 设X(t), tT是一独立增量过程，且X(0)=0，有X(t1)- X(0) = X(t1) , X(t2)- X(t1), , X(tn-1)- X(tn-2), X(tn)- X(tn-1) 相互独立。在X(tn-1)已知的条件下， X(tn)- X(tn-1) 与X(t1) ，X(t2) =X(t2)- X(t1)+ X(t1), X(t3) =X(t3)- X(t2)+ X(t2), X(tn-1) =X(tn-1)- X(tn-2)+ X(tn-2)相互独立。 PX(tn) xn | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn)- X(tn-1) xn- xn-1 | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn)- X(tn-1) xn- xn-1 = PX(tn) xn | X(tn-1) = xn-1因此， X(t), tT是马尔可夫过程。,5.1 马尔可夫过程的概念例3 维纳过程W(t), t0是独立增量过程，且W(0) = 0，所以，维纳过程是马尔可夫过程。例4 泊松过程N(t), t0是独立增量过程，且N(0) = 0，所以，泊松过程是马尔可夫过程。思考：马尔可夫过程的无前效性。,5.2 马尔可夫链5.2.1 马尔可夫链的概念 马尔可夫链是参数集T和状态空间E皆离散的马尔可夫过程。 T=0,1,2,，E=i1,i2,.马尔可夫链定义： 设随机序列X(n), n=0,1,2,的离散状态空间为E=i1, i2, ,若对于任意的非负整数k和n1n2 nm,以及任意i1, i2, , im, im+kE, 有 PX(nm+k) = im+k | X(n1) = i1, X(n2) = i2, , X(nm) = im = PX(nm+k) = im+k | X(nm) = im则称随机序列X(n), n=0,1,2,为马尔可夫链。,5.2 马尔可夫链5.2.1 马尔可夫链的概念马尔可夫链的状态转移和状态转移矩阵：,C-K,5.2 马尔可夫链5.2.1 马尔可夫链的概念马尔可夫链的转移概率及其矩阵： 马尔可夫链 X(n), n=0,1,2,在时刻m处于状态i的条件下，在时刻m+k处于状态j的条件概率，称为马尔可夫链在m时刻的k步转移概率，记为 pij (m,k)=PX(m+k) = j | X(m) = i 当k=1时， pij =pij (m,1)=PX(m+1) = j | X(m) = i称为马尔可夫链在m时刻的一步转移概率，简称转移概率。k为转移步长。显然， 0 pij (m,k) 1 。,5.2 马尔可夫链5.2.1 马尔可夫链的概念马尔可夫链的转移概率及其矩阵： 对于有限状态空间E=1,2,N,由马尔可夫链 X(n), n=0,1,2,在时刻m的k步转移概率pij (m,k)形成的下列矩阵称为马尔可夫链在m时刻的k步转移矩阵。当k=1时，称为一步转移矩阵，简称转移矩阵。,5.2 马尔可夫链5.2.2 齐次马尔可夫链齐次马尔可夫链及其转移概率： 如果马尔可夫链 X(n), n=0,1,2,的转移概率pij (m,k)与m无关，即 pij (m,k)=PX(m+k) = j | X(m) = i= pij (k)则称为齐次马尔可夫链, pij (k)称为k步转移概率。 一步转移概率简写为 pij = pij (1) =PX(m+1) = j | X(m) = i 规定 显然， 0pij (k) 1 。,5.2 马尔可夫链5.2.2 齐次马尔可夫链齐次马尔可夫链转移矩阵： 对于有限状态空间E=1,2,N,齐次马尔可夫链 X(n), n=0,1,2, 的k步转移矩阵为且 0pij (k) 1， 随机矩阵。,随机矩阵定义： 若 ,且满足 则称矩阵为随机矩阵。,5.2 马尔可夫链5.2.2 齐次马尔可夫链齐次马尔可夫链转移矩阵： 对于无限状态空间E=1,2,齐次马尔可夫链 X(n), n=0,1,2, 的k步转移矩阵为且 0pij (k) 1， 。,5.2 马尔可夫链5.2.2 齐次马尔可夫链齐次马尔可夫链转移矩阵： 对于有限状态空间E=1,2,N,齐次马尔可夫链 X(n), n=0,1,2, 的一步转移矩阵为且 0pij 1， 随机矩阵。,5.2 马尔可夫链5.2.2 齐次马尔可夫链:转移矩阵例1：直线上带两个吸收壁的随机游动 状态空间E=1,2,3,4,5, 1和5为吸收壁状态。 转移概率：当i=1,5时，p11=1, p1j=0(j1), p55=1, p5j=0(j5) 当i=2,3,4时， pi,i+1=p, pi,i-1=q, pi,j=0 (ji-1,i+1) 所以一步转移矩阵为,5.2 马尔可夫链5.2.2 齐次马尔可夫链:转移矩阵例2：直线上带两个弹性壁的随机游动 状态空间E=1,2,3,4,5, 1和5为弹性壁状态。当质点处于2、3、4位置时，下一时刻向左和向右移动的概率分别为q和p；当处于1位置时，下一时刻留在原位的概率为q，右移一格的概率为p；当处于5位置时，下一时刻留在原位的概率为p ，左移一格的概率为q 。转移概率为： 转移矩阵为： p11=q, p12=p, p1j=0(j=3,4,5), p55=p, p54=q, p5j=0(j=1,2,3) 当i=2,3,4时， pi,i+1=p, pi,i-1=q, pi,j=0 (ji-1,i+1),5.2 马尔可夫链5.2.2 齐次马尔可夫链齐次马尔可夫链转移概率之间的关系： 齐次马尔可夫链X(n), n=0,1,2, 的转移概率满足切普曼柯尔莫哥洛夫方程：证,5.2 马尔可夫链5.2.2 齐次马尔可夫链齐次马尔可夫链转移概率之间的关系： 齐次马尔可夫链的切普曼柯尔莫哥洛夫方程写成矩阵形式： P(k+l)=P(k)P(l)当k=1, l=1时， P(2)=P(1)P(1)=P(1)2当k=2, l=1时， P(3)=P(2)P(1)=P(1)3一般地有 P(n)= P(1)n = Pn可见，n步转移概率（矩阵）等于n个一步转移概率（矩阵）的乘积。,5.2 马尔可夫链5.2.2 齐次马尔可夫链：转移概率例：天气预报问题。设明天是否有雨，仅与今天的天气有关，而与过去的天气无关。今天下雨明天也下雨的概率为p,今天无雨明天有雨的概率为q。有雨天气为状态0，无雨天气为状态1。若p=0.7,q=0.4,求今天有雨且第四天有雨的概率。解 一步转移概率矩阵：二步转移概率矩阵：四步转移概率矩阵：,5.2 马尔可夫链5.2.2 齐次马尔可夫链初始概率和绝对概率： 齐次马尔可夫链X(n), n=0,1,2,在初始时刻取各状态的概率分布： pi= pi(0) =PX(0)=i, i=1,2,称为齐次马尔可夫链的初始概率分布。显然， 0pi 1， 齐次马尔可夫链X(n), n=0,1,2,在第n时刻取各状态的概率分布： pi(n)=PX(n)=i, i=1,2,称为齐次马尔可夫链在时刻n的绝对概率分布。显然， 0pi(n) 1，当n=0时，绝对概率分布变为初始概率分布。,5.2 马尔可夫链5.2.2 齐次马尔可夫链绝对概率与初始概率和转移概率之间的关系：可见，齐次马尔可夫链的绝对概率分布完全由初始概率分布和转移概率分布所确定。,5.2 马尔可夫链5.2.2 齐次马尔可夫链有限维概率分布与初始概率和转移概率之间的关系：定理：齐次马尔可夫链的有限维概率分布完全由初始概率分布和转移概率分布所确定，即证,5.2 马尔可夫链5.2.2 齐次马尔可夫链,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布几个定义： 有限马尔可夫链：具有有限多个状态的马尔可夫链。 E=1, 2, , N 无限马尔可夫链：具有无限多个状态的马尔可夫链。 E=1, 2, 概率分布：若有限或无限数列pi, i=1, 2, 满足条件： pi 0; 则称pi, i=1, 2, 是概率分布。,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布遍历性定义： 若一个齐次马尔可夫链对于一切状态i与j的转移概率的极限存在，且与i无关，则称此马尔可夫链具有遍历性。 对于有限马尔可夫链，显然有 j 0; 此时，称j , j=1, 2, , N是该马尔可夫链的极限分布。,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布遍历性定义： 转移矩阵的极限,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布有限马尔可夫链具有遍历性充分条件定理： 对于一有限马尔可夫链，若存在一正整数m，使得 则此链是遍历的；而且其极限分布1, 2, , N是方程组满足条件的唯一解。,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布遍历马尔可夫链绝对概率的极限： 可见，对于遍历马尔可夫链，绝对概率的极限与转移概率的极限相同。,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布例：直线上带弹性壁的随机游动，若只取1,2,3三个点，其一步转移概率矩阵为二步转移概率矩阵为 其中的所有元素都大于零，所以此链是遍历的。极限分布存在，,5.2 马尔可夫链5.2.3 马尔可夫链的遍历性与极限分布例：求极限分布j , j=1, 2, 3 ： 根据有,5.2 马尔可夫链5.2.4 马尔可夫链的平稳分布平稳分布定义： 若齐次马尔可夫链的一个概率分布vj , jE满足则称vj , jE为该链的平稳分布。 一般地，若vj , jE为平稳分布，则有,5.2 马尔可夫链5.2.4 马尔可夫链的平稳分布平稳分布性质： 如果齐次马尔可夫链的初始概率分布pj , jE为平稳分布，则该链在任意时刻n的绝对概率分布都等于初始概率分布，即,5.2 马尔可夫链5.2.4 马尔可夫链的平稳分布平稳分布性质： 遍历的齐次马尔可夫链的极限分布等于平稳分布。证 若齐次马尔可夫链具有遍历性，其极限分布为,