第十一章-马尔可夫链课件.ppt

1、2022-12-16100tttt0过程（或系统）,在时刻 所处的状态为已知的条件下，过程在时刻所处状态的条件分布与过程在时刻 之前所处的状态无关。通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。12(),3,niX t tTItnttt ntT设随机过程的状态空间为。如果对时间 的任意 个数值11(),1,2,1()()()iiinnnnX tx xI inX tX txX t在条件下，的条件分布函数恰等于在条件下的条件分布函数，即2022-12-162112211)|(),(),()nnnnP X txX tx X txX tx（11()|(),(1.1)nnnn

2、nP X txX txxR11|121121(,|,;,)nnt ttnnnnFx tx xxt tt或写成1|11(,|,)nnt tnnnnFx txt(),X t tT则称过程具有马尔可夫性或无后效性，并称此过马尔可程为夫过程。2022-12-163111.1)()(),1,2,2nnnjX txX tX tjn证：由（式知，只要证明在已知的条件下（与相互独立即可。现由独立增量过程的定义知道，1(),0(0)0,),0X t tXX t t例设是独立增量过程，且证明（是一个马尔可夫过程。1101,2,2()(0)()()jnnjnntttjnX tXX tX t当，时，增量与相互独立。1

3、11(0)0)()nnjnnXX txX tX tx根据条件和（，即有（与相互独立。(),1,2,2)(),0njX tX tjnX tX t t再由第三章第4节定理知，此时与（相互独立。这表明（具有无后效性，即是一个马尔可夫过程。2022-12-1641(),01,2,012nXX n nT时间和状态都是离散的马尔可夫过程称为，简称马氏链，记为它可以看作在时间集，上对离散状态的马氏过程相继观察马尔可夫链的结果。12,.iIa aaR记链的状态空间121,0;,rin rtttmt m nmT在链的情形，马尔可夫性通常用条件分布律来表示，即对任意的正整数和有1122|,|(1.2)rrm nj

4、tititimim njmiP XaXaXaXaXaP XaXa.iaI其中2022-12-165(,),(,)|(1.3)ijijm njmiijP m mnP m mnP XaXamamna记上式右端为称条件概率为马氏链在时刻 处于状态 条件下，在时刻转移到状态 的转移概率。121,(,)1,1,2,.(1.4)iijjmamna aP m mni由于链在时刻 从任何一个状态 出发，到另一时刻，必然转移到诸状态中的某一个，所以2022-12-166(,)(,)ijm mnP m mnP由转移概率组成的矩阵称为马氏链的。由（1.4)式知，此矩阵的每一行元之转移概率矩阵和等于1。(,),(),

5、(,)(),ijijijijP m mni jnP nP m mnP n当转移概率只与及时间间距 有关时，把它记为即并称此转移概率具有平稳性。同时也称此链是齐次的或时齐的。1.3)()|(1.5)()ijm njmiijP nP XaXannP nnP在马氏链为齐次的情形下，由（式定义的转移概率称为马氏链的 步转移概率，(为 步转移概率矩阵。2022-12-1671(1)|,ijijmjmipPP XaXa一步转移概率为一步转移概率矩阵为111212122212(1)jjiiijppppppppp PP记成1mX的状态Xm的状态12iaaa12jaaa12,ijija apaa在上述矩阵的左侧

6、和上边标上状态是为了显示是由状态 经一步转移到状态 的概率。2022-12-16820 111 1011-,1).,0,1,2,01nnpqpXXnnXnI0例（传输系统）在如图只传输数字和 的串联系统中，设每一级的传真率（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）为，误码率为并设一个单位时间传输一级，是第一级的输入，是第 级的输出（那么是一随机过程，状态空间，而且1,nnnXi iIXXin当为已知时，所处的状态的概率分布只与有关，而与时刻 以前所处的状态无关，所以它是一个马氏链，而且还是齐次的。2022-12-16912n0X1X2X1nXnX图11-1它的一步转移概率

7、和一步转移概率矩阵分别为1,|,0,1,ijnnp jipP Xj Xii jq jiP和01pqqp012022-12-161031,2,3,4,515)QIQiiQ 例一维随机游动设一醉汉（或看作一随机游动的质点），在如图11-2所示直线的点集上作随机游动，且仅在1秒、2秒等时刻发生游动。游动的规则是：如果 现在位于点（，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果 现在位于1（或5）这点上，则下一时刻就以概率1移动到2（或4）这一点上。1和5这两点称为反射壁。上面这种游动称为带有两个反射壁的随机游动。2022-12-161112345图11-22022-1

8、2-16121,0,1,2,nnnnnnXnQXXnIXi iIXXiQni若以表示时刻 时 的位置，不同的位置就是的不同状态，那么是一随机过程，状态空间就是，而且当为已知时，所处的状态的概率分布只与有关，而与 在时刻 以前如何到达 是完全无关的，它的一步转移概率和一步转移概率矩阵分别为,0,1,2,nXn 所以是一马氏链，而且还是齐次的。131,1,1,15,|1,1,25,40,|2ijnnjii iipP Xj Xiijijji 或2022-12-1613P和1234512345010001/3 1/3 1/30001/3 1/3 1/30001/3 1/3 1/30001011QP如果

9、把 这一点改为吸收壁，就是说 一旦到达 这一点，则就永远留在点1上。此时，相应链的转移概率矩阵只需把 中第1横行改为（1,0,0,0,0)。总之，改变游动的概率规则，就可得到不同方式的随机游动和相应的马氏链。2022-12-16144例排队模型设服务系统由一个服务员和只可以容纳两个人的等候室组成，见图11-3。服务规则是：先到先服务，后来者需在等候室依次排队。假定一个需要服务的顾客到达系统时发现系统内已有3个顾客（一个正在接受服务，两个在等候室排队），则该顾客离去。等候室服务台系统随机到达者离去者图11-32022-12-1615tqpt设时间间隔 内有一个顾客进入系统的概率为，有一原来被服务

10、的顾客离开系统（即服务完毕）的概率为。又设当充分小时，在这时间间隔内多于一个顾客进入或离去系统实际上是不可能的。再设有无顾客来到与服务是否完毕是相互独立的。现用马氏链来描述这个系统。()nXX n tn t设表示时刻时系统内的顾客数，即系统的状态。,0,1,2,012 32 3nXnI 是一随机过程，状态空间，而且仿照例、的分析，可知它是一个齐次马氏链。2022-12-161600001.ptpq 在系统内没有顾客的条件下，经后仍没有顾客的概率（条件概率，下同），0101.ptpq系统内没有顾客的条件下，经后有一顾客进入系统的概率，10(1).pttppq10系统内恰有一顾客正在接受服务的条件

11、下，经后系统内无人的概率，它等于在间隔内顾客因服务完毕而离去，且无人进入系统的概率，1111(1)(1).ptppqpq系统内恰有一顾客的条件下，在间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客继续要求服务，且无人进入系统的概率，2022-12-16171212(1).ppp q正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率，13130.ptp正在接受服务的顾客继续要求服务，且在间隔内有两个顾客进入系统的概率。由假设，后者实际上是不可能发生的，2132(1),pppq类似地，有22(1)(1),ppqpq23(1),pqp0(|2)ijpij3333(1).

12、pppqp一人因服务完毕而离去且另一人进入系统，或者无人离开系统的概率，2022-12-1618于是，该马氏链的一步转移概率矩阵为P01230123100(1)(1)(1)(1)00(1)(1)(1)(1)00(1)(1)qqpqpqpqqppqpqpqqppqpqp2022-12-1619515249710例某计算机机房的一台计算机经常出故障，研究者每隔分钟观察一次计算机的运行状态，收集了小时的数据（共作次观察）。用 表示正常状态，用 表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011010111

13、1011101111011111100110111111001111,2,97)nXn n 设为第（个时段的计算机状态，可以认为它是一个齐次马氏链，状态空间I=0，1。96次转移的情况是：00 801 18，次；，次；10 18，次；11，52次2022-12-1620因此，一步转移概率可用频率近似地表示为0010|0nnpP XX888 18260111|0nnpP XX18188 18261010|1nnpP XX18181852701111|1nnpP XX52521852702022-12-16216515033例（续例）已知计算机在某一时段（分钟）的状态为，问在此条件下从此时段起此计

14、算机能连续正常工作 刻钟（个时段）的条件概率为多少？0000X解：由题意，某一时段的状态为 就是初始状态为，即，由乘法公式、马氏性和齐次性得，所求条件概率为1230111|0P XXXX，012300111/0P XXXXP X，010210321000 1|0 1|101|110/0P XP XXP XXXP XXXXP X，1021321|0 1|1 1|1P XXP XXP XX011111111PPP（）（）（）18 52 520 38226 70 70.2022-12-16220(0),1,2,.jjjpP XaaI j接着，研究齐次马氏链的有限维分布。首先，记称它为马氏链的初始分布

15、。nT1再看马氏链在任一时刻的一维分布：1(),1,2,.(1.6)()1.jnjjjjp nP XaaI jp n显然，应有又有01,njinjiP XaP Xa Xa001|,njiiiP XaXa P Xa1()(0)(),1,2,(1.7)jiijip npP nj或即2022-12-1623121.6)()(),(),(),)(1.6)jnp np np np一维分布（也可以用行向量表示成1.7)I这样，利用矩阵乘法（是可列无限集时，仍用有限阶矩阵乘法的规则确定矩阵之积的元），（式可写成()(0)()(1.7)nnppP12121,nniiiittt tTa aaIn此式表明，马氏链

16、在任一时刻以及状态，马氏链的 维分布：2022-12-16241122,nntititiP XaXaXa112211112211|,nnnntititititititiP XaP XaXaP XaXaXaXa11221111|nnnntititititiP XaP XaXaP XaXa11 211211()()().(1.8)nnii iiinnp t PttPtt1.7)(1.7)由此，并结合（或可知：马氏链的有限维分布同样完全由初始分布和转移概率确定。2022-12-16252 多步转移概率的确定1),0,1,2,X n nu vT设（是一齐次马氏链，则对任意的，有1()()(),1,2,

17、.(2.1)ijikkjkP uvP u P v i jChapman-Kolmogorov方程（就是著名的切普曼科尔莫戈罗夫（)方程，简称C-K方程。,)()()(1,2,),iijjikkjCKsaX sauvaX suvaX saua kava方程基于下述事实，即“从时刻 所处的状态即（出发，经时段转移到状态，即这一事件可分解成“从出发，先经时段 转移到中间状态再从经时段 转移到状态这样一些事件的和事件（见图11-4）。2022-12-162612.1),kaIsT方程（的证明如下：先固定和由条件概率定义和乘法定理，有),()|()jkiP X suvaX suaX sa（()|()()

18、|(),()kijkiP X suaX saP X suvaX suaX sa()().(2.2)ikkjP u P v马氏性和齐次性）（(),1,2,kX suak又由于事件组“”构成一划分，故有()()|()ijjiP uvP X suvaX sa1(),()|()jkikP X suvaX suaX sa2022-12-1627(2.2)CK将式代入上式，即得所要证明的方程。()()()CKuvuvPPP方程也可写成矩阵形式：(2.1)(2.1)1,1,CKnuvn利用方程容易确定 步转移概率。事实上，在式中令得递推关系：()(1)(1)(1)nnnPPPPP().(2.3)nn PP从

19、而可得nn就是说，对齐次马氏链而言，步转移概率矩阵是一步转移概率矩阵的 次方。2022-12-16281,00,1,2nXn 例设是具有三个状态的齐次马氏链，一步转移概率矩阵为P0123/41/401/41/21/403/41/40120022(0)1/3,0,1,2.i)0,1;(ii)1.ipP XiiP XXP X初始分布试求（解：先求出二步转移概率矩阵2022-12-16292(2)PP0120125/85/161/165/161/23/163/169/161/4020200,10 1|0P XXP XP XX于是(i)55100131648(0)(2);pP 12(ii)1.7)(2

20、)1pP X由（式，001111221(0)(2)(0)(2)(0)(2)pPpPpP15193 1621611242022-12-16301000220.9(0)1,(0)01.ppP XpP Xn 例在第一节例 中，(i)设,求系统二级传输后的传真率与三级传输后的误码率；（ii）设初始分布又已知系统经 级传输后输出为1，问原发字符也是1的概率是多少？().nnn PP解：先求出 步转移概率矩阵由于P01pqqp01(1)qp 121,pqP有相异的特征值由线性代数知识，可将 表示成对角阵2022-12-16311200 100pq12的相似矩阵。具体做法是：求出，对应的特征向量11/2,1

21、/2 e21/2,1/2 e12,He e令1/21/2,1/21/21.PHH则，于是，容易算得2022-12-16321()nnPHH1nH H011111222211112222()()()()nnnnpqpqpqpq01(2.4)(i)2.4)0.9p 由（式可知，当时，系统经过二级传输后的传真率与三级传输后的误码率分别为1100(2)(2)PP21122(0.90.1)0.8201001(3)(3)PP31122(0.90.1)0.244;2022-12-1633(ii)11n根据贝叶斯公式，当已知系统经 级传输后输出为，原发字符也是 的概率为01|1nP XX001 1|11nnP

22、 XP XXP X111001111(0)()(0)()(0)()pP npPnpP n()1(21)()nnpqpq2022-12-1634对于只有两个状态的马氏链，一步转移概率矩阵一般可以表示为P0111aabb01,0,1.a b2n利用类似于例 的方法，可得 步转移概率矩阵为()nn PP0100011011()()()()PnPnPnP n011(1)1,2,nbaaaabbabbababn(2.5)2022-12-16353 遍 历 性2.5)0,1()ija bP n对于一般的两个状态的马氏链，由（式可知，当时，有极限0010lim()lim()nnPnPn0bab0111lim

23、()lim()nnPnP n1aab01.jjij上述极限的意义是：对固定的状态，不管链在某一时刻从什么状态（或）出发，通过长时间的转移，到达状态的概率都趋近于这就是所谓的遍历性。2022-12-163601011),又由于，所以（,记作构成一分布律，称它为链的极限分布。().ijjnnP n另外，如若我们能用其他简便的方法直接由一步转移概率求得极限分布，则反过来，当1时，就可得到 步转移概率的近似值：,()ijijIa aIP n一般，设齐次马氏链的状态空间为，若对于所有转移概率存在极限lim()()ijjnP ni不依赖于2022-12-16371212()12()jjnnjn PP或12

24、1,jj则称此链具有遍历性。又若则同时称（，）为链的极限分布。2022-12-16381212,1,()0,1,2,(3.1),),nNijijNXnIa aama aIP mi jN P定理设齐次马氏链的状态空间为是它的一步转移概率矩阵，如果存在正整数，使对任意的都有则此链具有遍历性，且有极限分布（11,1,2,(3.2)0,1(3.3)NjiijiNjjjpjNP它是方程组或即的满足条件的唯一解。2022-12-163913.2)3.2)11mNjjmmNP依照定理，为证有限链是遍历的，只需找一正整数，使 步转移概率矩阵无零元。而求极限分布 的问题，化为求解方程组（的问题。注意，方程组（中

25、仅个未知数是独立的，而唯一解可用归一条件确定.1(0)()nTnpp在定理的条件下，马氏链的极限分布又是平稳分布。意即，若用 作为链的初始分布，即,则链在任一时刻的分布永远与 一致。11.7)(2.3)3.2)()(0)().nnnnppPPPP事实上，由（、和（式，有2022-12-16401例试说明第一节例3中，带有两个反射壁的随机游动是遍历的，并求其极限分布（平稳分布）。3P解：为简便计，以符号“”代表转移概率矩阵的正的元。于是，由例 中的一步转移概率矩阵，得2000000000000(2)0000000000000000PP000000 4000000(4)000000 PP 2022

26、-12-164125(4),)P1即无零元。由定理，链是遍历的。在根据（3.2)和(3.3)式，写出极限分布=(,满足的方程组122123323443455412345(1/3),(1/3)(1/3),(1/3)(1/3)(1/3),(1/3)(1/3),(1/3),1.23453.1先由前四个方程，解得：352341/113/111将它们代入归一条件，即最后一个方程，解之，得唯一解：，。2022-12-16421/113/113/113/111/11所以极限分布为（，）。(15)3/11151/11Qii 这个分布表明：经过长时间游动后，醉汉 位于点的概率约为，位于点 或 的概率约为。202

27、2-12-16432例试说明第一节例4（排队模型）中的链是遍历的，并求其极限分布。3012314(3)(,)PPP解：依照例，由第一节例 中的一步转移概率矩阵，可算得无零元。根据定理，链是遍历的。而极限分布满足下列方程组：0011012212332301231)(1),(1)(1)(1)(1)(1)(1)(1)(1)(1),1.qpqqpqpqpqqppqpqpqqppqp（2022-12-1644330(1)/,pqC解之，得唯一解22(1)(1)/,pqqpC3322232(1)(1)(1)(1)(1).Cpqp qqpqqpqp其中01231/2,1/70.14,2/70.29,1/7

28、2/7 2/7 2/7pq假若则可算得即此时极限分布为（，）。即经过相当长的时间后，系统中无人的情形约占14%的时间，而系统中有一人、二人、三人的情形约各占29%的时间。221(1)/,p qqC323(1)/,qpC2022-12-1645301/201/21/201/2001/201/21/201/20P例设一马氏链的一步转移概率矩阵为试讨论它的遍历性。21/201/2001/201/2(2)1/201/2001/201/2PP解：先算得2022-12-1646()(1);()(2).1,2,3,4),lim()ijnnnnnjP nPPPPP进一步可验证：当 为奇数时，为偶数时，这表明对任一固定的（极限都不存在。按定义，此链不具遍历性。