随机过程 马尔科夫过程PPT课件

1、14.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、过去状态无关。第1页/共91页24.1 马尔可夫链与转移概率马尔可夫链与转移概率 马尔可夫过程通常分为三类：马尔可夫过程通常分为三类：(1)(1)时间、状态都是离散的，称为时间、状态都是离散的，称为马尔可夫链马尔可夫链(2)时间连续时间连续、状态离散的，称为连续时间状态离散的，称为连续时间马尔可夫链马尔可夫链(3)时间、状态都是连续的，称为时间、状态都是连续的，称为马尔可夫过程马尔可夫过程第2页/共91页34.1 马尔可夫链与转移概率马尔可夫链与转移概率随机过程随机过程 Xn，n T ，参数参数T=0, 1, 2, , ,状态空间状态空间I=i0, i1, i2, 定义定义 若随机过程若随机过

3、程 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 为为马尔可夫链马尔可夫链，简称，简称马氏马氏链链。第3页/共91页44.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

4、=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- -2第4页/共91页54.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确定。确定。第5页

5、/共91页64.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, ，一步一步转移

6、概率转移概率为为第6页/共91页74.1 马尔可夫链与转移概率马尔可夫链与转移概率 转移概率转移概率性质性质(1) (2) P称为随机矩阵称为随机矩阵mnmmnnpppppppppP212222111211Ijipij, 0IipIjij, 1第7页/共91页84.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 称条件概率称条件概率 = PXm+n=j|Xm=i 为为马尔可夫链马尔可夫链 Xn，n T 的的n步转移概率步转移概率(i, ,j I, m 0, n 1)。n步转移矩阵步转移矩阵其中其中 P(n)也为也为随机矩阵随机矩阵)(nijp)(nijnpP IjippIjnijnij

7、, 1,0)()(jijipnPPppnijijij,1,00,1)0()1()1(时，规定时，规定当当时时当当第8页/共91页94.1 马尔可夫链与转移概率马尔可夫链与转移概率 定理定理4.1 设设 Xn，n T 为为马尔可夫链，则对任意整数马尔可夫链，则对任意整数n 0,0 l0 (最大公约数最大公约数greatest common divisor) 如果如果d1，就称就称i为周期的，为周期的， 如果如果d=1，就称就称i为非周期的为非周期的)(niip第29页/共91页304.2 马尔可夫链的状态分类马尔可夫链的状态分类 设马尔可夫链的设马尔可夫链的状态空间状态空间I=1,2,9，转移概

8、率如下图转移概率如下图 从状态从状态1出发再返回状态出发再返回状态1的可能步数为的可能步数为T=4,6,8,10, ，T的的最大公约最大公约数为数为2，从而，从而状态状态1的周期为的周期为2895672341313211111111第30页/共91页314.2 马尔可夫链的状态分类马尔可夫链的状态分类注注(1)如果如果i有周期有周期d，则对一切非零的则对一切非零的n, , n 0 (mod d)，有有 （若若 ，则，则n=0 (mod d) ） (2)对充分大的对充分大的n， （引理引理4.1）例题中当例题中当n=1时，时， 当当n1时，时，0)(niip0)(niip0)(ndiip0)(n

9、diip0)2()(iiiippnd第31页/共91页324.2 马尔可夫链的状态分类马尔可夫链的状态分类 状态空间状态空间I=1,2,3,4，转移概率如图转移概率如图， 状态状态2和状态和状态3有相同的周期有相同的周期d=2，但状态但状态2和状态和状态3有显著的区别。当状态有显著的区别。当状态2转移到状态转移到状态3后，再不能返回到状态后，再不能返回到状态2，状态，状态3总能返回到状态总能返回到状态3。这就要引。这就要引入入常返性常返性概念。概念。23412111121第32页/共91页334.2 马尔可夫链的状态分类马尔可夫链的状态分类 由由i出发经出发经n步首次到达步首次到达j的概率的概

10、率(首达概率首达概率) 规定规定 由由i出发经有限步终于到达出发经有限步终于到达j的概率的概率0)0(ijf1 |, 11 ,)(niXjXnvjXPfmnmvmnij1)(nnijijff第33页/共91页344.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若fii=1，称状态称状态i为为常返的常返的； 若若fii1，称状态称状态i为为非常返的非常返的i为非常返，则以概率为非常返，则以概率1- - fii不返回到不返回到ii为常返，则为常返，则 构成一概率分布，构成一概率分布， 期望值期望值 表示由表示由i出发再返回到出发再返回到i的平均返回时间的平均返回时间1)(nniiinf 1)(

11、)(1, 1nnnnffiiii定义定义第34页/共91页354.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若 i ，则称常返态则称常返态i为正常返的为正常返的; 若若 i = ，则称常返态则称常返态i为零常返的，为零常返的， 非周期的正常返态称为遍历状态。非周期的正常返态称为遍历状态。 首达概率首达概率 与与n步转移概率步转移概率 有如下关系式有如下关系式定理定理4.4 对任意状态对任意状态i, j及及1 n ，有有)(nijf)(nijpnkkjjknnkknjjknijpfpfpijij0)()(1)()()(定义定义第35页/共91页364.2 马尔可夫链的状态分类马尔可夫链的状

12、态分类证证)0( ,|, 11 , 11 ,|, 11 ,|)0(0)()(1)()(010100)(ijnkkjjknnkkknjjkvnkkvnnknkvnnijfpffpiXjXkvjXPjXkvjXiXjXPiXjXjXkvjXPiXjXPpijij第36页/共91页374.2 马尔可夫链的状态分类马尔可夫链的状态分类 引理引理4.2 周期的等价定义周期的等价定义G.C.D =G.C.D 设马尔可夫链的状态空间设马尔可夫链的状态空间I=1,2,3，转移概率矩阵为转移概率矩阵为 求从状态求从状态1出发经出发经n 步转移首次到达各状态的概率步转移首次到达各状态的概率0, 1:)(niipn

13、n0, 1:)(niifnn000332211qppqqpP第37页/共91页384.2 马尔可夫链的状态分类马尔可夫链的状态分类 解解 状态转移图如下状态转移图如下 ，首达概率为，首达概率为 1233q2p1p1q2q3p3131)4(131)3(31)2(1)1()()(,12121212qqpqfppqfqqfpf0, 12,)(1,2,)(13131131)(12mmnppqmmnqqpqfmmn第38页/共91页394.2 马尔可夫链的状态分类马尔可夫链的状态分类同理可得同理可得0, 12 ,)()(1,2 ,)()(1,00, 12,)(1,2,)(2312313213213123

14、121321)(12121121)(1113mmnqqpqqppqppmmnppqqqqppnfmmnqqpmmnppqpfmmmmnmmn第39页/共91页404.2 马尔可夫链的状态分类马尔可夫链的状态分类 以下讨论常返性的判别与性质以下讨论常返性的判别与性质数列的母函数与卷积数列的母函数与卷积an,n 0为实数列，母函数为实数列，母函数bn,n 0为实数列，母函数为实数列，母函数则则an与与bn的卷积的卷积的母函数的母函数0)(nnnsasA0)(nnnsbsBnkknknbac0)()()(sBsAsC第40页/共91页414.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理

15、定理4.5 状态状态i常返的充要条件为常返的充要条件为如如i非常返，则非常返，则证证: 规定规定 ，则由定理，则由定理4.40)(nniipiinniifp110)(0, 1)0()0(iiiifp1,0)()()(nfppnkkniikiinii第41页/共91页424.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 )()(1)()(,)(10, 10)(0)(00)()(0)()0()0(10)()(1)(sFsPsPsfsFspsPsfpspfpsfpspnnniinnniinnnkkniikiinnniiiiiinnnkkniikiinnnii 则则设设可知可知由由第42页/共

16、91页434.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类对对0 s10)(0)(0)(01)()(0)()()(11)(1)(nniinnniiNnnniiniinniiniinnniipspsPspsFsPfffsfsF第43页/共91页444.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 iinniinniisnniisnniisnniinniisNnniifffsFpsPpsPpNpsPps1)(0)(10)(10)(10)(0)(10)()(lim)(lim)(lim,)(lim, 1同理同理iiNnniissfpsFsP11,)(lim11)(lim0)(11第44

17、页/共91页454.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理定理4.7 设设i常返且有周期为常返且有周期为d，则则其中其中 i为为i的平均返回时间，当的平均返回时间，当 i= 时时 推论推论 设设i常返，则常返，则(1) i零常返零常返(2) i遍历遍历indiindp )(lim0lim)(ndiinp0lim)(niinp01lim)(iniinp 第45页/共91页464.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 证证(1)i零常返，零常返， i= ，由定理由定理4.7知，知，对对d的非整数倍数的的非整数倍数的n， 从而子序列从而子序列 i是零常返的是零常返

18、的0lim)(ndiinp0lim0)()(niinniipp，故，故0lim)(niinp0lim)(ndiinp，从而，从而iindiindp 0lim)(第46页/共91页474.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 k0)(nijp第48页

19、/共91页494.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 证证 (1)ij ，存在，存在l 0，使使 jk，存在存在m 0，使使由由C-K方程方程所以所以ik(2)由由(1)直接推出直接推出0)(lijp0)(mjkp0)()()()()(smjklijmsklismlikppppp第49页/共91页504.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理定理4.8 如如ij，则，则 (1) i与与j同为常返或非常返，如为常返，则它们同为正常返或零常返同为常返或非常返，如为常返，则它们同为正常返或零常返(2) i与与j有相同的周期有相同的周期第50页/共91页514.2

20、 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 设马氏链设马氏链Xn的状态空间为的状态空间为 I=0,1,2,，转移概率为转移概率为考察状态考察状态0的类型的类型Iipppiii,21,21,2101,0012302121212121212121第51页/共91页524.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 可得出可得出0为正常返的为正常返的由于由于 ，所以，所以0的周期为的周期为d=10为非周期的，从而为遍历状态为非周期的，从而为遍历状态对于其它状态对于其它状态i,由于由于i0,所以也是遍历的所以也是遍历的 2210, 121,2181212121,412121,2111

21、)(000100)(00)3(00)2(00)1(00nnnnnnnnnnffffff 为常返状态为常返状态故故021)1(00p第52页/共91页534.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 对无限制随机游动对无限制随机游动由斯特林近似公式由斯特林近似公式可推出可推出(1)当且仅当当且仅当p=q=1/2时，时，4pq=1nnnniiniipqCpp)(, 02)2()12(nennnn2!2)2() 12(1)1 (44)4( ppppqnpqpnnii npnii1)2(第53页/共91页544.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类状态状态i是常返的是常返的状态状态i是零常返的是零常返的1)2(1)2(0)12(1)(1)2(1,1mmiimmiimmiinniinniinpppppn从而从而又又 0lim, 0lim, 0lim)()12()2(miimniinniinppp所以