2021/3/91第四章第四章 马尔可夫链马尔可夫链 2021/3/924.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表示将来，马尔可夫过程表明：表示将来，马尔可夫过程表明：在已知在已知现在状态的条件下，将来所处的状态与现在状态的条件下，将来所处的状态与过去状态无关过去状态无关2021/3/934.1 马尔可夫链与转移概率 马尔可夫过程通常分为三类：马尔可夫过程通常分为三类：(1)(1)时间、状态都是离散的，称为时间、状态都是离散的，称为马尔可马尔可夫链夫链(2)时间连续时间连续、状态离散的，称为连续时间状态离散的，称为连续时间马尔可夫链马尔可夫链(3)时间、状态都是连续的，称为时间、状态都是连续的，称为马尔可夫马尔可夫过程过程2021/3/944.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 为为马尔可夫链马尔可夫链，简称，简称马氏链马氏链。
2021/3/954.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-22021/3/964.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确定2021/3/974.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,，一步一步转移概率为转移概率为2021/3/984.1 马尔可夫链与转移概率马尔可夫链与转移概率 转移概率转移概率性质性质(1)(2)P称为随机矩阵称为随机矩阵mnmmnnpppppppppP212222111211Ijipij,0IipIjij,12021/3/994.1 马尔可夫链与转移概率马尔可夫链与转移概率 定义定义 称条件概率称条件概率 =PXm+n=j|Xm=i 为为马尔可夫链马尔可夫链 Xn，n T 的的n步转移概步转移概率率(i,j I,m 0,n 1)n步转移矩阵步转移矩阵其中其中 P(n)也为也为随机矩阵随机矩阵)(nijp)(nijnpP IjippIjnijnij,1,0)()(jijipnPPppnijijij,1,00,1)0()1()1(时时，规规定定当当时时当当2021/3/9104.1 马尔可夫链与转移概率马尔可夫链与转移概率 定理定理4.1 设设 Xn，n T 为为马尔可夫链，马尔可夫链，则对任意整数则对任意整数n 0,0 l0 (最大公约数最大公约数greatest common divisor)如果如果d1，就称就称i为周期的，为周期的，如果如果d=1，就称就称i为非周期的为非周期的)(niip2021/3/9314.2 马尔可夫链的状态分类马尔可夫链的状态分类 设马尔可夫链的设马尔可夫链的状态空间状态空间I=1,2,9，转移概率如下图转移概率如下图 从状态从状态1出发再返回状态出发再返回状态1的可能步数为的可能步数为T=4,6,8,10,，T的的最大公约数为最大公约数为2，从而从而状态状态1的周期为的周期为28956723413132111111112021/3/9324.2 马尔可夫链的状态分类马尔可夫链的状态分类注注(1)如果如果i有周期有周期d，则对一切非零的则对一切非零的n,n 0(mod d)，有有 （若若 ，则，则n=0(mod d)）(2)对充分大的对充分大的n，（引理引理4.1）例题中当例题中当n=1时，时，当当n1时，时，0)(niip0)(niip0)(ndiip0)(ndiip0)2()(iiiippnd2021/3/9334.2 马尔可夫链的状态分类马尔可夫链的状态分类 状态空间状态空间I=1,2,3,4，转移概率如图转移概率如图，状态状态2和状态和状态3有相同的周期有相同的周期d=2，但状态但状态2和状态和状态3有显著的区别。
当状态有显著的区别当状态2转移到转移到状态状态3后，再不能返回到状态后，再不能返回到状态2，状态，状态3总总能返回到状态能返回到状态3这就要引入这就要引入常返性常返性概念234121111212021/3/9344.2 马尔可夫链的状态分类马尔可夫链的状态分类 由由i出发经出发经n步首次到达步首次到达j的概率的概率(首达概率首达概率)规定规定 由由i出发经有限步终于到达出发经有限步终于到达j的概率的概率0)0(ijf1|,11,)(niXjXnvjXPfmnmvmnij1)(nnijijff2021/3/9354.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若fii=1，称状态称状态i为为常返的常返的；若若fii1，称状态称状态i为为非常返的非常返的 i为非常返，则以概率为非常返，则以概率1-fii不返回到不返回到i i为常返，则为常返，则 构成一概率分布，构成一概率分布，期望值期望值 表示由表示由i出发再返回出发再返回到到i的平均返回时间的平均返回时间1)(nniiinf 1)()(1,1nnnnffiiii定义定义2021/3/9364.2 马尔可夫链的状态分类马尔可夫链的状态分类 若若 i ，则称常返态则称常返态i为正常返的为正常返的;若若 i=，则称常返态则称常返态i为零常返的，为零常返的，非周期的正常返态称为遍历状态。
非周期的正常返态称为遍历状态首达概率首达概率 与与n步转移概率步转移概率 有如下有如下关系式关系式定理定理4.4 对任意状态对任意状态i,j及及1 n ，有有)(nijf)(nijpnkkjjknnkknjjknijpfpfpijij0)()(1)()()(定义定义2021/3/9374.2 马尔可夫链的状态分类马尔可夫链的状态分类证证)0(,|,11,11,|,11,|)0(0)()(1)()(010100)(ijnkkjjknnkkknjjkvnkkvnnknkvnnijfpffpiXjXkvjXPjXkvjXiXjXPiXjXjXkvjXPiXjXPpijij2021/3/9384.2 马尔可夫链的状态分类马尔可夫链的状态分类 引理引理4.2 周期的等价定义周期的等价定义G.C.D =G.C.D 设马尔可夫链的状态空间设马尔可夫链的状态空间I=1,2,3，转移概率矩阵为转移概率矩阵为 求从状态求从状态1出发经出发经n 步转移首次到达各状步转移首次到达各状态的概率态的概率0,1:)(niipnn0,1:)(niifnn000332211qpppP2021/3/9394.2 马尔可夫链的状态分类马尔可夫链的状态分类 解解 状态转移图如下状态转移图如下，首达概率为，首达概率为 1233q2p1p1q2q3p3131)4(131)3(31)2(1)1()()(,12121212pqfppqffpf0,12,)(1,2,)(13131131)(12mmnppqmmnpqfmmn2021/3/9404.2 马尔可夫链的状态分类马尔可夫链的状态分类同理可得同理可得0,12 ,)()(1,2 ,)()(1,00,12,)(1,2,)(2312313213213123121321)(12121121)(1113mmnpppqppmmnppppnfmmnpmmnppqpfmmmmnmmn2021/3/9414.2 马尔可夫链的状态分类马尔可夫链的状态分类 以下讨论常返性的判别与性质以下讨论常返性的判别与性质数列的母函数与卷积数列的母函数与卷积an,n 0为实数列，母函数为实数列，母函数bn,n 0为实数列，母函数为实数列，母函数则则an与与bn的卷积的卷积的母函数的母函数0)(nnnsasA0)(nnnsbsBnkknknbac0)()()(sBsAsC2021/3/9424.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理定理4.5 状态状态i常返的充要条件为常返的充要条件为如如i非常返，则非常返，则证证:规定规定 ，则由定理，则由定理4.40)(nniipiinniifp110)(0,1)0()0(iiiifp1,0)()()(nfppnkkniikiinii2021/3/9434.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 )()(1)()(,)(10,10)(0)(00)()(0)()0()0(10)()(1)(sFsPsPsfsFspsPsfpspfpsfpspnnniinnniinnnkkniikiinnniiiiiinnnkkniikiinnnii 则则设设可知可知由由2021/3/9444.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类对对0 s10)(0)(0)(01)()(0)()()(11)(1)(nniinnniiNnnniiniinniiniinnniipspsPspsFsPfffsfsF2021/3/9454.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 iinniinniisnniisnniisnniinniisNnniifffsFpsPpsPpNpsPps1)(0)(10)(10)(10)(0)(10)()(lim)(lim)(lim,)(lim,1同理同理iiNnniissfpsFsP11,)(lim11)(lim0)(112021/3/9464.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理定理4.7 设设i常返且有周期为常返且有周期为d，则则其中其中 i为为i的平均返回时间，当的平均返回时间，当 i=时时 推论推论 设设i常返，则常返，则(1)i零常返零常返(2)i遍历遍历indiindp)(lim0lim)(ndiinp0lim)(niinp01lim)(iniinp 2021/3/9474.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 证证(1)i零常返，零常返，i=，由定理由定理4.7知，知，对对d的非整数倍数的的非整数倍数的n，从而子序列从而子序列 i是零常返的是零常返的0lim)(ndiinp0lim0)()(niinniipp，故，故0lim)(niinp0lim)(ndiinp，从而，从而iindiindp 0lim)(2021/3/9484.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)(nijp2021/3/9504.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 证证(1)ij，存在，存在l 0，使使 jk，存在存在m 0，使使由由C-K方程方程所以所以ik(2)由由(1)直接推出直接推出0)(lijp0)(mjkp0)()()()()(smjklijmsklismlikppppp2021/3/9514.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 定理定理4.8 如如ij，则，则(1)i与与j同为常返或非常返，如为常返，则同为常返或非常返，如为常返，则它们同为正常返或零常返它们同为正常返或零常返(2)i与与j有相同的周期有相同的周期2021/3/9524.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 设马氏链设马氏链Xn的状态空间为的状态空间为 I=0,1,2,，转移概率为转移概率为考察状态考察状态0的类型的类型Iipppiii,21,21,2101,00123021212121212121212021/3/9534.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 可得出可得出0为正常返的为正常返的由于由于 ，所以，所以0的周期为的周期为d=10为非周期的，从而为遍历状态为非周期的，从而为遍历状态对于其它状态对于其它状态i,由于由于i0,所以也是遍历的所以也是遍历的 2210,121,2181212121,412121,2111)(000100)(00)3(00)2(00)1(00nnnnnnnnnnffffff 为常返状态为常返状态故故021)1(00p2021/3/9544.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类 对无限制随机游动对无限制随机游动由斯特林近似公式由斯特林近似公式可推出可推出(1)当且仅当当且仅当p=q=1/2时，时，4pq=1nnnniiniipqCpp)(,02)2()12(nennnn2!2)2()12(1)1(44)4(ppppqnpqpnnii npnii1)2(2021/3/9554.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类状态状态i是常返的是常返的状态状态i是零常返的是零常返的1)2(1)2(0)12(1)(1)2(1,1mmiimmiimmiinniinniinpppppn从而从而又又 0lim,0lim,0lim)()12()2(miimniinniinppp所所以以而而2021/3/9564.2 4.2 马尔可夫链的状态分类马尔可夫链的状态分类(2)当且仅当当且仅当p q，4pq1状态状态i是非常返的是非常返的1)2(0)12(1)2(1)(1)2(1,)4(mmiimmiimmiinniinniinnpppppnpq从而从而 2021/3/957状态分类状态分类周期性di常返性fii正常返正常返i1非周期di=1 遍历遍历非常返非常返fii1零常返零常返i=常返常返fii=1()1limniinip()lim0niinp()1niinp 2021/3/9584.3 遍历性遍历性2021/3/9592021/3/9602021/3/9612021/3/9622021/3/9632021/3/9642021/3/9652021/3/9662021/3/9672021/3/9682021/3/9692021/3/9702021/3/9712021/3/9722021/3/9732021/3/9742021/3/9752021/3/9762021/3/9772021/3/9782021/3/9792021/3/9802021/3/9812021/3/9822021/3/9832021/3/9842021/3/9852021/3/9862021/3/9872021/3/9882021/3/9892021/3/9902021/3/991本章小结 马尔可夫链的定义 一步及K步转移概率 初始概率及绝对概率 状态分类 遍历性 平稳分布 典型例题2021/3/992放映结束 感谢各位的批评指导！谢谢 谢！谢！让我们共同进步。