第101112讲马尔可夫过程小时

1、2022-3-2北京邮电大学电子工程学院1第第1111章章 马尔可夫链马尔可夫链 1 1、马尔可夫链与转移概率、马尔可夫链与转移概率2 2、马尔可夫链的状态分类、马尔可夫链的状态分类3 3、状态空间的分解、状态空间的分解4 4、渐近性质与平稳分布、渐近性质与平稳分布 马尔可夫过程的定义马尔可夫过程的定义定义定义4.1 4.1 设设 X(t) X(t)，t t T T 为随机过程，若对为随机过程，若对任意正整数任意正整数n n及及t1 t2t1 t2tn0 X(tn-1)=xn-10，且条件分布，且条件分布PX(tn)PX(tn)xn|X(t1)=x1,xn|X(t1)=x1, X(tn-1)=

2、xn-1= , X(tn-1)=xn-1= PX(tn) PX(tn)xn|X(tn-1)=xn-1xn|X(tn-1)=xn-1，则称，则称X(t)X(t)，t t T T 为马尔可夫过程。为马尔可夫过程。 若若t1,t2,t1,t2,tn-2,tn-2表示过去，表示过去，tn-1tn-1表示现在，表示现在，tntn表示表示将来，马尔可夫过程表明：在已知现在状态的条件将来，马尔可夫过程表明：在已知现在状态的条件下，将来所处的状态与过去状态无关。下，将来所处的状态与过去状态无关。马尔可夫过程通常分为三类：马尔可夫过程通常分为三类：(1)(1)时间、状态都是离散的，称为马尔可夫链时间、状态都是离

3、散的，称为马尔可夫链(2)(2)时间连续、状态离散的，称为连续时间马尔时间连续、状态离散的，称为连续时间马尔可夫链可夫链(3)(3)时间、状态都是连续的，称为马尔可夫过程时间、状态都是连续的，称为马尔可夫过程4.1 马尔可夫链与转移概率马尔可夫链与转移概率随机过程随机过程XnXn，n nT T ，参数参数T=0,1,2,T=0,1,2,状态空间状态空间I=i0,i1,i2,I=i0,i1,i2, 定义定义4.2 4.2 若随机过程若随机过程XnXn，n nT T ，对任意，对任意n nT T和和i0,i1,i0,i1,in+1 ,in+1 I I，条件概率，条件概率PXn+1=in+1|X0=

4、i0,X1=i1,PXn+1=in+1|X0=i0,X1=i1,Xn=in,Xn=in = PXn+1=in+1|Xn=in = PXn+1=in+1|Xn=in，则称则称XnXn，n nT T 为马尔可夫链，简称马氏链。为马尔可夫链，简称马氏链。马尔可夫链的性质马尔可夫链的性质 PX0=i0,X1=i1, PX0=i0,X1=i1,Xn=in,Xn=in =PXn=in|X0=i0,X1=i1, =PXn=in|X0=i0,X1=i1,Xn-1=in-1 ,Xn-1=in-1 PX0=i0,X1=i1, PX0=i0,X1=i1,Xn-1=in-1,Xn-1=in-1 = PXn=in|Xn

5、-1=in-1 = PXn=in|Xn-1=in-1 PXn-1=in-1 |X0=i0,X1=i1, PXn-1=in-1 |X0=i0,X1=i1,Xn-2=in-2,Xn-2=in-2 PX0=i0,X1=i1, PX0=i0,X1=i1,Xn-2=in-2,Xn-2=in-2 =PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 =PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX0=i0,X1=i1, PX0=i0,X1=i1,Xn-2=in-2,Xn-2=in-2 = = =PXn=in|Xn-1=in-1PXn-1=in-1

6、|Xn-2=in-2 =PXn=in|Xn-1=in-1PXn-1=in-1 |Xn-2=in-2 PX1=i1|X0=i0PX0=i0 PX1=i1|X0=i0PX0=i0 马尔可夫链的联合分布统计特性完全由条件概率马尔可夫链的联合分布统计特性完全由条件概率PXn+1=in+1|Xn=inPXn+1=in+1|Xn=in确定。确定。定义定义4.3 4.3 称条件概率称条件概率pij(n)= PXn+1=j|Xn=i pij(n)= PXn+1=j|Xn=i 为马尔为马尔可夫链可夫链XnXn，n nT T 在时刻在时刻n n的一步转移概率，简称转移的一步转移概率，简称转移概率，其中概率，其中i

7、,ji,jI I。定义定义4.4 4.4 若对任意的若对任意的i,ji,jI I，马尔可夫链，马尔可夫链Xn,nXn,nT T 的转移概率的转移概率pij(n)pij(n)与与n n无关，则称马尔可夫链是齐次的，无关，则称马尔可夫链是齐次的，并记并记pij(n)pij(n)为为pijpij。齐次马尔可夫链具有平稳转移概率，齐次马尔可夫链具有平稳转移概率， 状态空间状态空间I=1,2,3,I=1,2,3, ，一步转移概率为，一步转移概率为mnmmnnpppppppppP212222111211转移概率性质转移概率性质(1) (1) (2) (2) P P称为随机矩阵称为随机矩阵Ijipij, 0

8、IipIjij, 1定义定义4.5 4.5 称条件概率称条件概率 = PXm+n=j|Xm=i = PXm+n=j|Xm=i为马为马尔可夫链尔可夫链XnXn，n nT T 的的n n步转移概步转移概(i,j(i,jI,mI,m0,n0,n1)1)。n n步转移矩阵步转移矩阵其中其中 P(n) P(n)也为随机矩阵也为随机矩阵)(nijp)(nijnpP IjippIjnijnij, 1,0)()(jijipnPPppnijijij,1,00,1)0()1()1(时时，规规定定当当时时当当定理定理4.1 4.1 设设XnXn，n nT T 为马尔可夫链，则对为马尔可夫链，则对任任意整数意整数n

9、n0,00,0lnl0 d=G.C.Dn: 0 ( (最大公约数最大公约数greatest common divisor)greatest common divisor)如果如果d1d1，就称，就称i i为周期的，为周期的，如果如果d=1d=1，就称，就称i i为非周期的为非周期的)(niip例例4.5 4.5 设马尔可夫链的状态空间设马尔可夫链的状态空间I=1,2,I=1,2,9,9，转移概率如下图，转移概率如下图 从状态从状态1 1出发再返回状态出发再返回状态1 1的可能步数为的可能步数为T=4,6,8,10, T=4,6,8,10, ，T T的最大公约数为的最大公约数为2 2，从而，从而

10、状态状态1 1的周期为的周期为2 2895672341313211111111注注(1)(1)如果如果i i有周期有周期d d，则对一切非零，则对一切非零n, nn, n0 mod d0 mod d，有有 （若（若 ，则，则n=0 mod d n=0 mod d ） (2) (2)对充分大的对充分大的n n， （引理（引理4.14.1）0)(niip0)(niip0)(ndiip例例4.6 4.6 状态空间状态空间I=1,2,3,4I=1,2,3,4，转移概率如图，转移概率如图，状态状态2 2和状态和状态3 3有相同的周期有相同的周期d=2d=2，但状态，但状态2 2和状态和状态3 3有显著的

11、区别。当状态有显著的区别。当状态2 2转移到状态转移到状态3 3后，再不后，再不能返回到状态能返回到状态2 2，状态，状态3 3总能返回到状态总能返回到状态3 3。这就。这就要引入常返性概念。要引入常返性概念。23412111121由由i i出发经出发经n n步首次到达步首次到达j j的概率的概率( (首达概率首达概率) )规定规定由由i i出发经有限步终于到达出发经有限步终于到达j j的概率的概率0)0(ijf1 |, 11 ,)(niXjXnvjXPfmnmvmnij1)(nnijijff 若若fii=1，称状态，称状态i为常返的；为常返的； 若若fii1，称状态，称状态i为非常返的为非常

12、返的i为非常返，则以概率为非常返，则以概率1- fii不返回到不返回到ii为常返，则为常返，则 构成一概率分布，构成一概率分布，期望值期望值 表示由表示由i出发再返回到出发再返回到i的平的平均返回时间均返回时间1)(nniiinf 1)()(1, 1nnnnffiiii定义定义4.8 若若ii，则称常返态，则称常返态i i为正常返的，为正常返的， 若若I=I=，则称常返态，则称常返态i i为零常返的，发生为零常返的，发生在无限状态空间。在无限状态空间。 非周期的正常返态称为遍历状态。非周期的正常返态称为遍历状态。首达概率首达概率 与与n n步转移概率步转移概率 有如下关系式有如下关系式定理定理

13、4.4 4.4 对任意状态对任意状态i,ji,j及及1 1nn，有，有)(nijf)(nijpnkkjjknnkknjjknijpfpfpijij0)()(1)()()(定义定义4.94.9证证)0( ,|, 11 , 11 ,|, 11 ,|)0(0)()(1)()(010100)(ijnkkjjknnkkknjjkvnkkvnnknkvnnijfpffpiXjXkvjXPjXkvjXiXjXPiXjXjXkvjXPiXjXPpijij引理引理4.2 4.2 周期的等价定义周期的等价定义G.C.DG.C.D =G.C.D =G.C.D例例4.7 4.7 设马尔可夫链的状态空间设马尔可夫链的状

14、态空间I=1,2,3I=1,2,3，转，转移移概率矩阵为概率矩阵为 求从状态求从状态1 1出发经出发经n n 步转移首次到达各状态的概步转移首次到达各状态的概率率0, 1:)(niipnn0, 1:)(niifnn000332211qppqqpP解解 状态转移图如下状态转移图如下 ，首达概率为，首达概率为 1233q2p1p1q2q3p3131)4(131)3(31)2(1)1()()(,12121212qqpqfppqfqqfpf0, 12,)(1,2,)(13131131)(12mmnppqmmnqqpqfmmn同理可得同理可得0, 12 ,)()(1,2 ,)()(1,00, 12,)(

15、1,2,)(2312313213213123121321)(12121121)(1113mmnqqpqqppqppmmnppqqqqppnfmmnqqpmmnppqpfmmmmnmmn3学时学时以下讨论常返性的判别与性质以下讨论常返性的判别与性质数列的母函数与卷积数列的母函数与卷积an,nan,n00为实数列，母函数为实数列，母函数bn,nbn,n00为实数列，母函数为实数列，母函数则则anan与与bnbn的卷积的卷积的母函数的母函数0)(nnnsasA0)(nnnsbsBnkknknbac0)()()(sBsAsC定理定理4.5 4.5 状态状态i i常返的充要条件为常返的充要条件为如如i

16、i非常返，则非常返，则证证: : 规定规定 ，则由定理，则由定理4.44.40)(nniipiinniifp110)(0, 1)0()0(iiiifp1,0)()()(nfppnkkniikiinii )()(1)()(,)(10, 10)(0)(00)()(0)()0()0(10)()(1)(sFsPsPsfsFspsPsfpspfpsfpspnnniinnniinnnkkniikiinnniiiiiinnnkkniikiinnnii 则则设设可知可知由由对对0 0s1s10)(0)(0)(01)()(0)()()(11)(1)(nniinnniiNnnniiniinniiniinnniip

17、spsPspsFsPfffsfsFiinniinniisnniisnniisnniinniisNnniifffsFpsPpsPpNpsPps1)(0)(10)(10)(10)(0)(10)()(lim)(lim)(lim,)(lim, 1同理同理iiNnniissfpsFsP11,)(lim11)(lim0)(11定理定理4.6 4.6 设设i i常返且有周期为常返且有周期为d d，则，则其中其中i i为为i i的平均返回时间，当的平均返回时间，当i=i=时时推论推论 设设i i常返，则常返，则(1) i(1) i零常返零常返(2) i(2) i遍历遍历indiindp )(lim0lim)(

18、ndiinp0lim)(niinp01lim)(iniinp 证证(1)(1)i i零常返，零常返， i=i=，由定理，由定理4.64.6知，知，对对d d的非整数倍数的的非整数倍数的n n， 从而子序列从而子序列 i i是零常返的是零常返的0lim)(ndiinp0lim0)()(niinniipp，故，故0lim)(niinp0lim)(ndiinp，从而，从而iindiindp 0lim)(2) (2) 子序列子序列 所以所以d=1d=1，从而，从而i i为非周期的，为非周期的，i i是遍历的是遍历的i i是遍历的，是遍历的，d=1d=1，ii0,n0,使使状态状态i i与状态与状态j

19、j互通，互通，i ij j：i ij j且且j jI I定理定理4.7 4.7 可达关系与互通关系都具有传递性，可达关系与互通关系都具有传递性，即即(1)(1)若若i ij j ，j jk k，则，则i ik k(2)(2)若若i i j j ，j j k k，则，则i i k k0)(nijp证证 (1)i (1)ij j ，存在，存在l 0l 0，使，使 j jk k，存在，存在m 0m 0，使，使由由C-KC-K方程方程所以所以i ik k(2)(2)由由(1)(1)直接推出直接推出0)(lijp0)(mjkp0)()()()()(smjklijmsklismlikppppp定理定理4.

20、8 4.8 如如i ij j，则，则 (1) i(1) i与与j j同为常返或非常返，如为常返，则它同为常返或非常返，如为常返，则它们同为正常返或零常返们同为正常返或零常返(2) i(2) i与与j j有相同的周期有相同的周期例例4.8 4.8 设马氏链设马氏链XnXn的状态空间为的状态空间为 I=0,1,2, I=0,1,2, ，转移概率为，转移概率为考察状态考察状态0 0的类型的类型Iipppiii,21,21,2101,0012302121212121212121 可得出0为正常返的由于 ，所以0的周期为d=10为非周期的，从而为遍历状态对于其它状态i,由于i0,所以也是遍历的 2210

21、, 121,2181212121,412121,2111)(000100)(00)3(00)2(00)1(00nnnnnnnnnnffffff 为常返状态为常返状态故故021)1(00p 设设C是状态空间是状态空间E的一个子集，若的一个子集，若C外的任一状外的任一状态不可能从态不可能从C的任一状态到达，即对任意的的任一状态到达，即对任意的iC， j C 有有pij(n)0称称C为一个闭集。为一个闭集。1）整个状态空间）整个状态空间E是最大闭集。是最大闭集。若一个马氏链的状态空间若一个马氏链的状态空间E不能再分解出较不能再分解出较小的闭集（空集除外）小的闭集（空集除外）,称此马氏链为不可称此马氏

22、链为不可约马氏链。约马氏链。2）若）若pii=1称状态称状态i为吸收状态，任一吸收状态为吸收状态，任一吸收状态构构 成最小闭集。成最小闭集。4.3 状态空间的分解状态空间的分解等效定义等效定义4.10 4.10 状态空间状态空间I I 的子集的子集C C称为闭集，称为闭集，如对任意如对任意i iC C及及k kC C都有都有pik=0;pik=0; 闭集闭集C C称为不可约的，如称为不可约的，如C C的状态互通；的状态互通； 马氏链马氏链XnXn称为不可约的，如其状态空间不可称为不可约的，如其状态空间不可约约引理引理4.3 C4.3 C是闭集的充要条件为对是闭集的充要条件为对i iC C及及k

23、 kC C都都有有0, 0)(npnik证证 充分性显然成立充分性显然成立必要性（数学归纳法）必要性（数学归纳法）设设C C为闭集，由定义当为闭集，由定义当n=1n=1时结论成立时结论成立设设n=mn=m时，时， ，i iC C及及k kC C ，则，则注：如注：如pii=1pii=1，称状态，称状态i i为吸收的，等价于单点集为吸收的，等价于单点集ii为闭集。为闭集。0)(mikp引理得证引理得证, 000)()()()1(CjjkCjmijCjjkmijCjjkmijmikppppppp马氏链为不可约马氏链任何两个状态相通。例例4.10 4.10 设马氏链设马氏链XnXn的状态空间为的状态

24、空间为 I=1,2,3,4,5 I=1,2,3,4,5，转移概率矩阵为，转移概率矩阵为状态状态3 3是吸收的，故是吸收的，故33是闭集，是闭集，1,41,4，1,3,41,3,4，1,2,3,41,2,3,4都是闭集，其中都是闭集，其中33，1,41,4是不可约的。是不可约的。I I含有闭子集，故含有闭子集，故XnXn不不是不可约的链。是不可约的链。00010000010010000000021212121P1254321212121111定理定理4.9 4.9 任一马氏链的状态空间任一马氏链的状态空间I I，可唯一，可唯一地分解成有限个或可列个互不相交的子集地分解成有限个或可列个互不相交的子

25、集D,C1,C2,D,C1,C2,之和，使得：之和，使得：(1)(1)每一每一CnCn是常返态组成的不可约闭集；是常返态组成的不可约闭集；(2)Cn(2)Cn中的状态同类型，或全是正常返，或全中的状态同类型，或全是正常返，或全是零常返，它们有相同的周期，且是零常返，它们有相同的周期，且fij=1fij=1，i,ji,jCnCn；(3)D(3)D由全体非常返态组成，自由全体非常返态组成，自CnCn中状态不能中状态不能到达到达D D中的状态。中的状态。例例4.12 4.12 马氏链的状态空间马氏链的状态空间I =1,2,3,4,5,6,I =1,2,3,4,5,6,状态转移矩阵为状态转移矩阵为分解

26、此链并指出各状态的常返性及周期性。分解此链并指出各状态的常返性及周期性。21213131310000000001000010000100000000100P21365421213131311111解解 由状态转移图知由状态转移图知可见可见1 1为正常返状态且周期为为正常返状态且周期为3 3，含，含1 1的基本常的基本常返闭集为返闭集为 C1=k:1 C1=k:1k=1,3,5k=1,3,5，从而状态，从而状态3 3及及5 5也为正常返状态且周期为也为正常返状态且周期为3 3。同理可知同理可知6 6为正常返状态，为正常返状态，6=3/26=3/2，周期为，周期为1 1。含含6 6的基本常返闭集为

27、的基本常返闭集为 C2=k:6 C2=k:6k =2,6k =2,6，可见可见2 2，6 6为遍历状态。为遍历状态。3, 3, 0, 11)(111)(11)3(11nnnnfnff 故故 于是I可分解为 I=DC1C2 =41,3,52,6, 14, 1, 0,)(4431)1(44非非常常返返周周期期为为故故由由于于nffn10jijijaa且且定义定义4.11 4.11 称矩阵称矩阵A=(aij)A=(aij)为随机矩阵，若为随机矩阵，若显然显然k k步转移矩阵为随机矩阵。步转移矩阵为随机矩阵。10jijijaa且且 有限马尔可夫链有限马尔可夫链 当一个马氏链的状态空间是一个有限集合时，

28、我当一个马氏链的状态空间是一个有限集合时，我们称此马氏链是有限马氏链。们称此马氏链是有限马氏链。1 1）所有非常返态所组成的集合不可能是闭集。）所有非常返态所组成的集合不可能是闭集。2 2）没有零常返态。）没有零常返态。3 3）必有正常返态。）必有正常返态。4 4）状态空间可分解为）状态空间可分解为: :kC.CCNE 21定理定理4.10 4.10 周期为周期为d d的不可约马氏链，其状的不可约马氏链，其状态空间态空间C C可唯一地分解为可唯一地分解为d d个互不相交的子集个互不相交的子集之和，即之和，即且使得自且使得自GrGr中任一状态出发，经一步转移必中任一状态出发，经一步转移必进入进入

29、Gr+1Gr+1中中(Gd = G0)(Gd = G0)。注：任取一状态注：任取一状态i i，对每一，对每一r=0,1,r=0,1,d-1,d-1定义定义集集srGGGCsrdrr,100, 0:)(rndijrpnjG对对某某个个例例4.13 4.13 设不可约马氏链的状态空间为设不可约马氏链的状态空间为C=1,2,3,4,5,6C=1,2,3,4,5,6，转移矩阵为，转移矩阵为0000000010000100000010000000043413131312121P由状态转移图可知各状态的周期由状态转移图可知各状态的周期d=3,d=3,固定状态固定状态i=1i=1，令，令故故C=G0G1G2

30、 =1,4,63,52C=G0G1G2 =1,4,63,52此在此在C C中的运动如下图所示。中的运动如下图所示。20, 0:530, 0:6410, 0:)23(12)13(11)3(10njnjnjpnjGpnjGpnjG有有对某个对某个，有有对某个对某个，有有对某个对某个 2136541,4,623,521214341313131111定理定理4.11 4.11 设设Xn,nXn,n00是周期为是周期为d d的不可约马的不可约马氏链，则在定理氏链，则在定理4.104.10的结论下有的结论下有(1)(1)如只在如只在0,d,2d,0,d,2d,上考虑上考虑XnXn，即得一新马，即得一新马氏

31、链氏链Xnd Xnd ，其转移矩阵，其转移矩阵 ，对此新链，对此新链，每一每一GrGr是不可约闭集，且是不可约闭集，且GrGr中的状态是非周期中的状态是非周期的；的；(2)(2)如原马氏链如原马氏链XnXn常返，则新马氏链常返，则新马氏链XndXnd也也常返。常返。)()(dijdpP例例4.14 4.14 设设XnXn为例为例4.134.13中的马氏链，已知中的马氏链，已知d=3d=3，则，则Xnd,nXnd,n00的转移矩阵为的转移矩阵为3131311251273131311251273131313)3(00000000000000000010000PP由子链 X3n的状态转移图可知 G0

32、=1,4,6，G1=3,5，G2=2各形成不可约闭集，周期为11643523131313131313131311271271251251考虑考虑 渐近性质渐近性质定理定理4.12 4.12 如如j j非常返或零常返，则非常返或零常返，则证证 若若j j非常返，则由定理非常返，则由定理4.54.5， 从而从而若若j j零常返，则由定理零常返，则由定理4.64.6推论，推论，)(nijpIipnijn, 0lim)(1)(nnijp0lim)(njjnp0lim)(njjnp4.4 4.4 渐近性质与平稳分布渐近性质与平稳分布由定理由定理4.44.4，对，对NnN0, pi +ri+qi=1qi 0, pi +ri+qi=1。此马尔可夫链。此马尔可夫链为生灭链，它是不可约的。记为生灭链，它是不可约的。记a0=