随机过程-马尔科夫过程PPT幻灯片课件.ppt

第四章第四章 马尔可夫链马尔可夫链 1 4.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 设设 X(t)，t T 为随机过程，若为随机过程，若对任意正整数对任意正整数n及及t1 t20，且条件分且条件分布布PX(tn)xn|X(t1)=x1,X(tn-1)=xn-1=PX(tn)xn|X(tn-1)=xn-1，则称则称 X(t)，t T 为为马尔可夫过程马尔可夫过程。若若t1,t2,tn-2表示过去，表示过去，tn-1表示现在，表示现在，tn表示将来，马尔可夫过程表明：表示将来，马尔可夫过程表明：在已知在已知现在状态的条件下，将来所处的状态与现在状态的条件下，将来所处的状态与过去状态无关。过去状态无关。2 4.1 马尔可夫链与转移概率马尔可夫过程通常分为三类：马尔可夫过程通常分为三类：(1)(1)时间、状态都是离散的，称为时间、状态都是离散的，称为马尔可马尔可夫链夫链(2)时间连续时间连续、状态离散的，称为连续时状态离散的，称为连续时间间马尔可夫链马尔可夫链(3)时间、状态都是连续的，称为时间、状态都是连续的，称为马尔可马尔可夫过程夫过程3 4.1 马尔可夫链与转移概率马尔可夫链与转移概率随机过程随机过程 Xn，n T ，参数参数T=0,1,2,状态空间状态空间I=i0,i1,i2,定义定义 若随机过程若随机过程 Xn，n T ，对任意，对任意n T和和i0,i1,in+1 I，条件概率条件概率PXn+1=in+1|X0=i0,X1=i1,Xn=in =PXn+1=in+1|Xn=in，则称则称 Xn，n T 为为马尔可夫链马尔可夫链，简称，简称马氏链马氏链。4 4.1 马尔可夫链与转移概率马尔可夫链与转移概率马尔可夫链的马尔可夫链的性质性质 PX0=i0,X1=i1,Xn=in=PXn=in|X0=i0,X1=i1,Xn-1=in-1 PX0=i0,X1=i1,Xn-1=in-1=PXn=in|Xn-1=in-1 PXn-1=in-1|X0=i0,X1=i1,Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-2=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX0=i0,X1=i1,Xn-2=in-25 4.1 马尔可夫链与转移概率马尔可夫链与转移概率=PXn=in|Xn-1=in-1PXn-1=in-1|Xn-2=in-2 PX1=i1|X0=i0PX0=i0 马尔可夫链的统计特性完全由条件概率马尔可夫链的统计特性完全由条件概率PXn+1=in+1|Xn=in确定。确定。6 4.1 马尔可夫链与转移概率定义定义 称条件概率称条件概率pij(n)=PXn+1=j|Xn=i 为为马马尔可夫链尔可夫链 Xn，n T 在时刻在时刻n的的一步转移概一步转移概率率，简称简称转移概率转移概率，其中其中i,j I。定义定义 若对任意的若对任意的i,j I，马尔可夫链马尔可夫链 Xn,n T 的转移概率的转移概率pij(n)与与n无关，则称无关，则称马尔可夫链是齐次的马尔可夫链是齐次的，并记，并记pij(n)为为pij。齐次马尔可夫链具有平稳转移概率，齐次马尔可夫链具有平稳转移概率，状态空间状态空间I=1,2,3,，一步一步转移概率为转移概率为7 4.1 马尔可夫链与转移概率马尔可夫链与转移概率转移概率转移概率性质性质(1)(2)P称为随机矩阵称为随机矩阵8 4.1 马尔可夫链与转移概率马尔可夫链与转移概率定义定义 称条件概率称条件概率 =PXm+n=j|Xm=i 为为马尔可夫链马尔可夫链 Xn，n T 的的n步转移概步转移概率率(i,j I,m 0,n 1)。n步转移矩阵步转移矩阵其中其中 P(n)也为也为随机矩阵随机矩阵9 4.1 马尔可夫链与转移概率马尔可夫链与转移概率定理定理4.1 设设 Xn，n T 为为马尔可夫链，马尔可夫链，则对任意整数则对任意整数n 0,0 l0 (最大公约数最大公约数greatest common divisor)如果如果d1，就称就称i为周期的，为周期的，如果如果d=1，就称就称i为非周期的为非周期的30 4.2 马尔可夫链的状态分类马尔可夫链的状态分类例例4.6 设马尔可夫链的设马尔可夫链的状态空间状态空间I=1,2,9，转移概率如下图转移概率如下图 从状态从状态1出发再返回状态出发再返回状态1的可能步数为的可能步数为T=4,6,8,10,，T的的最大公约数为最大公约数为2，从，从而而状态状态1的周期为的周期为231 4.2 马尔可夫链的状态分类马尔可夫链的状态分类注注(1)如果如果i有周期有周期d，则对一切非零的则对一切非零的n,n 0(mod d)，有有 （若若 ，则，则n=0(mod d)）(2)对充分大的对充分大的n，（引理引理4.1）例题中当例题中当n=1时，时，当当n1时，时，32 4.2 马尔可夫链的状态分类马尔可夫链的状态分类例例4.7 状态空间状态空间I=1,2,3,4，转移概率如图转移概率如图，状态状态2和状态和状态3有相同的周期有相同的周期d=2，但状态但状态2和状态和状态3有显著的区别。当状态有显著的区别。当状态2转移到状转移到状态态3后，再不能返回到状态后，再不能返回到状态2，状态，状态3总能总能返回到状态返回到状态3。这就要引入。这就要引入常返性常返性概念。概念。33 4.2 马尔可夫链的状态分类马尔可夫链的状态分类由由i出发经出发经n步首次到达步首次到达j的概率的概率(首达概率首达概率)规定规定由由i出发经有限步终于到达出发经有限步终于到达j的概率的概率34 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若fii=1，称状态称状态i为为常返的常返的；若若fii1，称状态称状态i为为非常返的非常返的i为非常返，则以概率为非常返，则以概率1-fii不返回到不返回到ii为常返，则为常返，则 构成一概率分布，构成一概率分布，期望值期望值 表示由表示由i出发再返回出发再返回到到i的平均返回时间的平均返回时间定义定义35 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若 i ，则称常返态则称常返态i为正常返的为正常返的;若若 i=，则称常返态则称常返态i为零常返的，为零常返的，非周期的正常返态称为遍历状态。非周期的正常返态称为遍历状态。首达概率首达概率 与与n步转移概率步转移概率 有如下关有如下关系式系式定理定理4.4 对任意状态对任意状态i,j及及1 n ，有有定义定义36 4.2 马尔可夫链的状态分类马尔可夫链的状态分类证证37 4.2 马尔可夫链的状态分类马尔可夫链的状态分类引理引理4.2 周期的等价定义周期的等价定义G.C.D =G.C.D例例4.8 设马尔可夫链的状态空间设马尔可夫链的状态空间I=1,2,3，转移概率矩阵为转移概率矩阵为 求从状态求从状态1出发经出发经n 步转移首次到达各状步转移首次到达各状态的概率态的概率38 4.2 马尔可夫链的状态分类马尔可夫链的状态分类解解 状态转移图如下状态转移图如下，首达概率为，首达概率为 39 4.2 马尔可夫链的状态分类马尔可夫链的状态分类同理可得同理可得40 4.2 马尔可夫链的状态分类马尔可夫链的状态分类以下讨论常返性的判别与性质以下讨论常返性的判别与性质数列的母函数与卷积数列的母函数与卷积an,n 0为实数列，母函数为实数列，母函数bn,n 0为实数列，母函数为实数列，母函数则则an与与bn的卷积的卷积的母函数的母函数41 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类定理定理4.5 状态状态i常返的充要条件为常返的充要条件为如如i非常返，则非常返，则证证:规定规定 ，则由定理，则由定理4.442 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 43 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类对对0 s144 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 45 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类定理定理4.7 设设i常返且有周期为常返且有周期为d，则则其中其中 i为为i的平均返回时间，当的平均返回时间，当 i=时时推论推论 设设i常返，则常返，则(1)i零常返零常返(2)i遍历遍历46 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类证证(1)i零常返，零常返，i=，由定理由定理4.7知，知，对对d的非整数倍数的的非整数倍数的n，从而子序列从而子序列 i是零常返的是零常返的47 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类(2)子序列子序列所以所以d=1，从而从而i为非周期的，为非周期的，i是遍历的是遍历的i是遍历的，是遍历的，d=1，i0,使使状态状态i与状态与状态j互通互通，ij：ij且且ji 定理定理4.8 可达关系与互通关系都具有传可达关系与互通关系都具有传递性，即递性，即(1)若若ij，jk，则则ik(2)若若i j，j k，则则i k49 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类证证(1)ij，存在，存在l 0，使使 jk，存在存在m 0，使使由由C-K方程方程所以所以ik(2)由由(1)直接推出直接推出50 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类定理定理4.8 如如ij，则，则(1)i与与j同为常返或非常返，如为常返，则同为常返或非常返，如为常返，则它们同为正常返或零常返它们同为正常返或零常返(2)i与与j有相同的周期有相同的周期51 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 例例4.9 设马氏链设马氏链Xn的状态空间为的状态空间为 I=0,1,2,，转移概率为转移概率为考察状态考察状态0的类型的类型52 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 可得出可得出0为正常返的为正常返的由于由于 ，所以，所以0的周期为的周期为d=10为非周期的，从而为遍历状态为非周期的，从而为遍历状态对于其它状态对于其它状态i,由于由于i0,所以也是遍历的所以也是遍历的 53 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类例例4.10 对无限制随机游动对无限制随机游动由斯特林近似公式由斯特林近似公式可推出可推出(1)当且仅当当且仅当p=q=1/2时，时，4pq=154 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类状态状态i是常返的是常返的状态状态i是零常返的是零常返的55 4.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类(2)当且仅当当且仅当p q，4pq1状态状态i是非常返的是非常返的56 状态分类状态分类周期性di常返性fii正常返正常返i1非周期di=1 遍历遍历非常返非常返fii1零常返零常返i=常返常返fii=157 4.3 遍历性遍历性58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 本章小结马尔可夫链的定义一步及K步转移概率初始概率及绝对概率状态分类遍历性平稳分布典型例题91