马尔可夫链的概念及转移概率-修改

1、马尔可夫链的概马尔可夫链的概念及转移概率念及转移概率第四章 马尔可夫链马尔可夫链的概念及转移概率马尔可夫链的概念及转移概率1马尔可夫链的状态分类2342021-10-152信息工程学院四系三教状态空间的分解 的渐进性质与平稳分布( )( )n nijijp p马氏性的等价形式v马氏性马氏性(4.1)式等价于：式等价于： 对任意的对任意的 及及 只要只要就有就有1 11 1 , ,1 1| |, , , , , ,1 1| | , , ( (4 4. . 1 1) )n nk kn nn nk kn nm mn nk km mm mn nm mn nk km mn nP P X Xi ik kl

2、 l X Xi iX Xi iP P X Xi ik kl l X Xi i+ + + + += = = = = = =L L1 11 11 11 1 , , , , , 0 0, ,n nn nm mm mn nm mn nP P X Xi iX Xi iX Xi i- - -= = = = L L0 01 1, , , , ,n nl li ii ii iI I+ + L L1 10 0, ,n nn nl lm mm mm m+ + = = , ,i i j jI I 1 11 1 | | | | n nn nm mm mP P X Xj j X Xi iP P X Xj j X Xi

3、i+ + += = = = = =齐次性齐次马尔可夫链2021-10-1511信息工程学院四系三教齐次马尔可夫链v注：注：（1）马氏性马氏性表示已知表示已知“现在现在”的条件下，的条件下， “将来将来”和和“过去过去”是独立的。是独立的。（2）齐次性齐次性要求过程从状态要求过程从状态i 经一步转移经一步转移 到状态到状态 j 的概率与的概率与起始时刻起始时刻 n 无关无关。2021-10-15信息工程学院四系三教12以后若无特别声明，我们以后若无特别声明，我们仅讨论齐次马氏链仅讨论齐次马氏链！一步转移概率及一步转移概率矩阵v定义定义 4.3 在齐次马氏链中，对在齐次马氏链中，对 ，记，记1 1

4、1 10 0 | | | | i i j jn nn np pP P X Xj j X Xi iP P X Xj j X Xi i+ += = = = = = =称称 为齐次马氏链为齐次马氏链的的一步转移概率。一步转移概率。ijp( ( ) )11121111212122221222P Pn nijnijnpppppppppppppp轾轾犏犏犏犏=犏犏犏犏犏犏臌臌LLLLLLLLLLLLLLLLLL 称为齐次马氏链的称为齐次马氏链的一步转移概率矩阵。一步转移概率矩阵。, ,i i j jI I 2021-10-1513信息工程学院四系三教一步转移概率及一步转移概率矩阵v 一步转移概率矩阵一步转

5、移概率矩阵P具有如下性质：具有如下性质： 称具有上述性质的矩阵为称具有上述性质的矩阵为随机矩阵。随机矩阵。(1)0, ,(1)0, ,ijijpi jIpi jI澄澄(2)1,(2)1,ijijj Ij IpiIpiI = 2021-10-1514信息工程学院四系三教n步转移概率及n步转移概率矩阵v定义定义4.4 设齐次马氏链设齐次马氏链 的状态空间为的状态空间为I , 为整数，记为整数，记 称称 为齐次马氏链为齐次马氏链 的的n 步转移概率。步转移概率。它表示随机质点从状态它表示随机质点从状态 i 出发经出发经n步到达状步到达状态态j的概率。的概率。,0,1,0,1,n nXnXn= =L

6、L1 1n n ( ( ) ) | | , , ( (, , ,0 0, ,1 1) )n ni i j jm mn nm mp pP P X Xj j X Xi ii ij jI I m mn n+ += = = =纬纬( )( )n nijijp p,0,1,0,1,n nXnXn= =L L2021-10-1515信息工程学院四系三教n步转移概率及n步转移概率矩阵v并称并称 为齐次马氏链的为齐次马氏链的n 步转移步转移概率矩阵。概率矩阵。由于由于( ( ) )( ( ) )P P( () )n nn ni ij jp p= =( ( ) )( ( ) )0 0, ,1 1. .n nn

7、ni ij ji ij ji i I Ip pp p = = 当当n =1时，时， 此即为一步转移概率此即为一步转移概率( (1 1) )i ij ji ij jp pp p= =( (0 0) )0 0, , ,1 1, ,. .i ij ji ij jp pi ij j = = = = 故故 也为随机矩阵。也为随机矩阵。( )( )P Pn n 规定规定2021-10-1516信息工程学院四系三教n步转移概率的性质v定理定理4.1 设设 为马氏链，则为马氏链，则对任意整数对任意整数 和和 n 步步转移概率转移概率 具有如下性质：具有如下性质：,0,1,0,1,n nXnXn= =L L0

8、0, , 0 0n nl ln n常常 , , ,i i j jI I 1 11 1 2 21 11 11 1( ( ) )( (2 2) ) n nn nn ni ij ji ik kk k k kk kj jk kI Ik kI Ip pp pp pp p- - -挝挝= =邋邋L LL L( ( ) )( (1 1) )( (3 3) ) P PP PP Pn nn n- -= =( )( )(4) PP(4) PPnnnn= =( )( )n nijijp p( ( ) )( ( ) )( () )( (1 1) ) n nl ln nl li ij ji ik kk kj jk kI

9、 Ip pp pp p- - = = C CK K方程方程n n步转移概率完步转移概率完全由一步转移全由一步转移概率决定概率决定2021-10-1517信息工程学院四系三教n步转移概率的性质证明证明 (1)对对0 l n,利用利用全概率公式全概率公式及及马氏性马氏性( )()( )()| | |. .mlmmnmlmlmmnmlkIkIlnllnlikkjikkjkIkIP XkXi P Xj XkP XkXi P Xj Xkpppp+ - - = = ( ( ) ) | | n ni ij jm mn nm mp pP P X Xj j X Xi i+ += = = = , ,| | m m

10、l lm mn nm mk k I IP P X Xk k X Xj j X Xi i+ + + = = = = = | | | |, , m ml lm mm mn nm mm ml lk k I IP P X Xk k X Xi iP P X Xj j X Xi iX Xk k+ + + + = = = = = = = 2021-10-1518信息工程学院四系三教n步转移概率的性质v(2) 在在(1)中令中令 得得 这是一个递推公式，故可递推得到这是一个递推公式，故可递推得到v(3),(4)是是(1),(2)的矩阵表示。的矩阵表示。1 11 1, ,l lk kk k= = =1 11 1

11、1 1( () )( (1 1) )n nn ni ij ji ik kk k j jk kI Ip pp pp p- - = = 1 11 1 2 21 11 11 1( ( ) )n nn nn ni ij ji ik kk k k kk kj jk kI Ik kI Ip pp p p pp p- - -挝挝= =邋邋L LL L2021-10-1519信息工程学院四系三教(1)式称为切普曼柯尔莫哥洛夫(Chapman-Kolmogorov)方程，简称C-K方程。Markov链应用举例v例例（通信系统中的马氏链）（通信系统中的马氏链）设在传送数字设在传送数字0和和1的通信系统中每个被传的

12、通信系统中每个被传送的数字必须经过若干级，而在每一级数送的数字必须经过若干级，而在每一级数字被正确传送的概率均为字被正确传送的概率均为p，0 p 1就称就称i为为周期的周期的，如，如 d =1就称就称i为为非周期的非周期的。( ( ) ) : :1 1, ,0 0 n ni ii in nn np p ( ( ) )( ( ) ). . . . : :0 0 n ni ii id dd d i iG G C C D Dn np p= = = 2021-10-1540信息工程学院四系三教v但反之不成立。即若但反之不成立。即若 不一定有不一定有状态的周期v注：注：如果如果 i 的周期为的周期为 d

13、，则对一切非零的，则对一切非零的 都有都有0 0( (m m o od d ) ), ,n nd d ( )( )0.0.n niiiip p= =, ,m mn nd d= =如前例中的状态如前例中的状态1的的d (1) = 2，但，但(2)(2)11110 0p p= =()()0 0m miiiip p 2021-10-1541信息工程学院四系三教状态的周期v引理引理4.1 如如 i 的周期为的周期为d，则存在正整数，则存在正整数M对一切对一切 ，有，有 ()()0.0.ndndiiiip p n nM M 2021-10-1542信息工程学院四系三教常返的定义及其分类v例例4.7 设设

14、I = 1, 2, 3, 4,转移概率如图转移概率如图4.4，易见状态易见状态2与状态与状态3有相同的周期有相同的周期d = 2。但。但由状态由状态3出发经两步必定返回到出发经两步必定返回到3，而状态，而状态2则不然，当则不然，当2转移到转移到3后，它再也不能返回后，它再也不能返回到到2。为区别这两种状态，我们引入。为区别这两种状态，我们引入常返性常返性概念。概念。2021-10-15信息工程学院四系三教433 31 12 21 11 12 24 41 12 21 11 1常返的定义及其分类v首达时的定义首达时的定义 称称为首达状态为首达状态j的的首达时首达时。其中约定。其中约定 v此时此时i

15、 i n nf f 1 1 : : , ,j jn nn nX Xj jt t= = = =i i n nf f = = 1 11 1 , , , , . .j jn nn nn nX Xj jX Xj j X Xj jt t- -= = =构构= =L L2021-10-1544信息工程学院四系三教常返的定义及其分类v首达（首中）概率的定义首达（首中）概率的定义表示质点从表示质点从i 出发，经出发，经n步首次到达步首次到达j的概率。的概率。表示质点从表示质点从i出发，经有限步首次出发，经有限步首次终于终于到达到达j的概率。的概率。2021-10-15信息工程学院四系三教45( ( ) )0

16、01 11 10 0 | | ( (, , , , ,| |) )n ni i j jj jn nn nf fP Pn n X Xi iP P X Xj jX Xj jX Xj j X Xi it t- -= = = = =构构= = =L L( )( )1 1n nijijijijn nffff = = = 常返的定义及其分类0 01 1( (| |) )j jP PX Xi it t = =( )( )1 1. .n nijijijijn nffff = = 0 01 1(|)(|)j jn nPnXiPnXit t = = 0 01 1( (, ,1 11 1, ,| |) )v vn

17、nn nP P X Xj jv vn nX Xj j X Xi i = = =梗梗= = = 质点从质点从 i 出发经出发经有限步终于到达有限步终于到达 j 的概率的概率2021-10-1546信息工程学院四系三教注：注：由定义由定义4.7知，若知，若i是非常返态，则由是非常返态，则由i出出发将以正概率发将以正概率 永远不再返回永远不再返回i；若；若i是是常返时，上述现象不会出现。常返时，上述现象不会出现。1 1iiiif f- -常返的定义及其分类v定义定义4.7 若若 ，称状态，称状态 i 为为常返的常返的，若，若 ；称状态；称状态 i 为为非常返的（滑过态）非常返的（滑过态），1 1ii

18、iif f= =1 1iiiif f 2021-10-1547信息工程学院四系三教常返的定义及其分类v对对常返态常返态 i，由定义知，由定义知 构成一构成一概率分布概率分布。此分布的期望值。此分布的期望值表示由表示由i出发再返回到出发再返回到i的的平均返回时间平均返回时间。 ( () )1 1n ni ii ii in nn n f fm m = = = ( ( ) ) , ,1 1, ,2 2, , n ni ii if fn n= =L L2021-10-1548信息工程学院四系三教常返的定义及其分类v定义定义4.8 对常返态对常返态i，若，若 ，则称常，则称常返态返态i为为正常返的正常返

19、的；若；若 ，则称常返，则称常返态态i为为零常返的零常返的。非周期的正常返态称为非周期的正常返态称为遍历状态遍历状态。 i为遍历状态为遍历状态i im m i im m= = 11iiiifd 2021-10-1549信息工程学院四系三教常返的定义及其分类v例例 设齐次马氏链设齐次马氏链 的状态空间的状态空间 ，其状态转移如下图：，其状态转移如下图： 可见，可见， 故状态故状态4是是非常返的非常返的。 又又 故状态故状态3也是也是非常返非常返的。的。 , ,1 1 n nX Xn n 1 1, ,2 2, ,3 3, ,4 4 I I= =( )( )44441,0,1,0,n nnfnf=(

20、1)( )(1)( )333333332 2,0,0,3 3n nffff=2021-10-1550信息工程学院四系三教1 12 21 13 34 41 12 21 12 21 12 21 12 21 13 32 23 3常返的定义及其分类而而故常态故常态1与状态与状态2是常返的。是常返的。(1)(2)(1)(2)111111111111(2)(3)(2)(3)2222222222232311111,1,2222111111 1, 1,2 22222ffffffffffff=+=+=+=+=+=+=+=+=L LL L2021-10-1551信息工程学院四系三教常返的定义及其分类v 和和 有如

21、下关系：有如下关系：v定理定理4.4 对任意状态对任意状态i, j及及1n1就称就称i为为周期的周期的，如，如 d =1就称就称i为为非周期的非周期的。( ( ) ) : :1 1, ,0 0 n ni ii in nn np p ( ( ) )( ( ) ). . . . : :0 0 n ni ii id dd d i iG G C C D Dn np p= = = 2021-10-1555信息工程学院四系三教( ( ) )0 0( (m m o od d) ) 0 0n ni ii in nd dp p罐罐= =( )( )0(m od )0|0(m od )0|n niiiinpt d

22、npt dt t罐=罐=知识回顾常返的定义及其分类2021-10-15信息工程学院四系三教56( )( )1 1n nijijijijn nffff = = = 1,1,= =常常返返1 1 ，非非常常返返( () )1 1n ni ii ii in nn n f fm m = = = , , 正正常常返返, ,= = 零零常常返返知识回顾v 和和 有如下关系：有如下关系：v定理定理4.4 对任意状态对任意状态i, j及及1n=2021-10-1558信息工程学院四系三教( )( )( )( ). . :1,0. . :1,0. . :1,0. . :1,0n niiiin niiiidG C

23、 DnnpdG C DnnptG C DnnftG C Dnnf=( ( ) )( ( ) ), ,n nn ni ii ii ii ip pf f 1 1. .d dt t周期的等价定义v另一方面，若另一方面，若t =1, 则则 若若t 1, 只需证明只需证明t | d，即对任意，即对任意 当当 时，时， 现假设现假设 时时 则则2021-10-15信息工程学院四系三教591 1. .d dt t= = =0 0m m o od d , ,n nt t ( ( ) )0 0. .n ni ii ip p= =n nt t 1时，时， 的的极限不存在极限不存在。因为因为d 1，当，当m不能被不

24、能被d 整除时，整除时，这样这样 存在两个收敛子列，一个子列存在两个收敛子列，一个子列另一个子列收敛到另一个子列收敛到0.因此，因此， 不存在。不存在。( )( )n niiiip p()()0.0.m miiiip p= =( ( ) )n ni ii ip p()()l i m. l i m. ndndiiiin ni id dp pm m= =( ( ) )l l i i m mn ni ii in np p2021-10-1568信息工程学院四系三教常返性的判别及其性质v推论推论 设设i常返，则常返，则 (1) i 零常返零常返( )lim0;niinp (2) i 遍历遍历( )1l

25、im0niinip 2021-10-1569信息工程学院四系三教常返性的判别及其性质v证明证明（1）如）如i零常返，则零常返，则 由定由定理理4.7知知( () )l li im m0 0, ,n n d di ii in ni id dd dp pm m= = = =+ + ( () )l li im m0 0. .n ni ii in np p= =, ,i im m= + = + 但当但当 时，时， 。故。故 0 0( (m m o od d( ( ) ) )n nd d ( )( )0 0n niiiip p= =2021-10-1570信息工程学院四系三教常返性的判别及其性质v反之，

26、如反之，如i是常返，且是常返，且 ，则，则( () )l l i i m m0 0, ,n nd di ii in ni id dp pm m= = =( () )l li im m0 0n ni ii in np p= =故故 因此因此i是零常返。是零常返。, ,i im m= = + + ( () )l li im m0 0n n d di ii in np p= =从而从而2021-10-1571信息工程学院四系三教常返性的判别及其性质v（2）设）设 ，这说明，这说明i为正为正常返常返, 且且( () )1 1l l i i m mn nd di ii in ni ip pm m= =(

27、 ( ) )1 1l l i i m m0 0n ni ii in ni ip pm m= = 反之若反之若I 遍历，则遍历，则 d =1，且，且 由定由定理理4.7知知, ,i im m + 与（与（4.26）比较得）比较得d =1，故，故i遍历；遍历；2021-10-1572信息工程学院四系三教状态可达和互通v称称自状态自状态i 可达状态可达状态 j，并记为，并记为 如果存如果存在在n 0,使使( )( )0;0;n nijijp p v称称状态状态i 与与j互通互通，并记为，并记为 ，若，若 且且 i ij j , ,i ij j . .jiji , ,i ij j 2021-10-15

28、73信息工程学院四系三教3 31 12 21 11 12 24 41 12 21 11 1状态可达和互通v可达和互通的状态具有下述性质：可达和互通的状态具有下述性质：定理定理4.8 可达与互通关系都具有传递性，即可达与互通关系都具有传递性，即 如果如果 ， ,则则 ； 如果如果 ， ,则则 。i ij j j jk k i ik k i ij j j jk k i ik k 备注：若状态不具有常返性，可达关系和互通关系就不具有自反性。2021-10-1574信息工程学院四系三教互通状态的性质v证明证明 若若 ，则存在，则存在 ，使得，使得i ij j 1 1l l ( )( )0,0,l li

29、jijp p 若若 ，则存在，则存在 , 使得使得j jk k 1 1m m ( () )0 0, ,m mj jk kp p ( () )( ( ) )( () )( ( ) )( () )0 0, ,m ml ll lm ml lm mi ik ki ir rr rk ki ij jj jk kr rp pp pp pp pp p+ += = 且且 ，所以，所以 。1 1lmlm+i ik k 由由C-K方程方程2021-10-1575信息工程学院四系三教互通状态的性质v定理定理4.9 如如 ，则，则(1) i与与j同为同为常返常返或或非常返非常返，如为常返，则，如为常返，则它们同为它们同

30、为正常返正常返或或零常返零常返；(2) i与与j有相同的有相同的周期周期。i ij j 互通的状态具有相同的常返性和周期。2021-10-1576信息工程学院四系三教互通状态的性质v证明证明（1）由于）由于 ，由可达定义知存在，由可达定义知存在 和和 ，使得，使得由由C-K方程，对任意方程，对任意 ，总有，总有i ij j 1 1l l 1 1n n ( ( ) )( ( ) )0 0, ,0 0. .l ln ni ij jj ji ip pp pa ab b= = = = ( () )( ( ) )( () )( ( ) )( () ); ; ( (4 4. . 2 27 7) )l l

31、m mn nl lm mn nm mi ii ii ij jj jj jj ji ij jj jp pp p p pp pp pa a b b+ + + = =( () )( ( ) )( () )( ( ) )( () ). . ( (4 4. . 2 28 8) )n nm ml ln nm ml lm mj jj jj ji ii ii ii ij ji ii ip pp pp pp pp pa a b b+ + + = =1 1m m 2021-10-1577信息工程学院四系三教互通状态的性质v将上两式的两边对将上两式的两边对m从从1到到求和，得求和，得()()()()1111; ;l

32、 mnml mnmiijjiijjmmmmppppa ba b+= 邋邋( () )( () )1 11 1. .l l m mn nm mj jj ji ii im mm mp pp pa a b b+ + += = = 邋邋可见，可见， 与与 相互控制，所以相互控制，所以它们同为无穷或同为有限。由定理它们同为无穷或同为有限。由定理4.5知知i, j同为常返或同为非常返同为常返或同为非常返。()()1 1m miiiim mp p = = ()()1 1m mjjjjm mp p = = 2021-10-1578信息工程学院四系三教互通状态的性质v今设今设j为零常返，据定理为零常返，据定理4.7之推论知之推论知 于是由于是由(4.28)式知式知 ，故，故i也是零也是零常返。常返。同理可证若同理可证若i是零常返是零常返,由由(4.27)式可证式可证 j为零为零常返。此说明常返。此说明i , j有有一个为零常返，则另一一个为零常返，则另一个也为