马尔科夫链

关键词：马尔可夫性时齐马尔可夫链n步转移概率C-K方程马氏链的有限维分布律常返暂留正常返零常返互达周期不可约平稳分布第十一章马尔可夫链1马尔可夫链的定义§813484.(),111.0{4|1,1,2}{4|2},npqpSnPSSSSPSS例1甲乙两人游戏每一局甲赢元的概率为，输元的概率为假设一开始甲带了元钱。令表示局后甲所拥有的钱数。计算和它们是随机游动否相等？浙江大学随机过程3813484134{4|1,1,2}{2|1,1,2}PSSSSPSSSSS解：84{2}PSS34pq84844{4|2}{2|2}PSSPSSS34pq84{2}PSS813484{4|1,1,2}{4|2}PSSSSPSS1011011,010111,..{|,..,,...,..,,}{|},kkkkknnkknknnnPSjSiSiSiPSknnniiiijjSi更一般地：状态Markov性浙江大学随机过程44:Markov性的直观含义1{}............knCSj将来{}.............knBSi现在0101{,...,.}.......knnkASiSi令过去(|Markov:)(|)PCABPCB性,已知到现在为止的所有信息来预测将来则只与现在状态有关,与过去状态无关.浙江大学随机过程5:Markov性的直观含义(|)(|)(|)PACBPABPCB在已知现在状态的条件下,过去与将来相互独立.浙江大学随机过程6;0101{0,1,2,...},Markov1,...,...,,,nkkXnknnmniiij如果是状态离散的随机过程并且具有性，即对任何任何状态定义：，有010-1{|,...,,}{|}knnnkmnmPXjXiXiXiPXjXi{01...}MarkovchainnXn马尔则称；，，是可夫链（）.浙江大学随机过程7:(,)0,(,)1ijijjIpmnpmn性质(|)minj(,)inmjpmnPXjXi记为＝＝在时处于状态的条件下,到时转移到状态的转移概率((,)(,)n)ijIIpmmPmmnn记为对应的步转移矩阵:1各元素非负性，每行之和为质浙江大学随机过程81,,(|,Markov{}nnnijPXjXinX如果对任何状态）不依赖于则称是时齐的定义：链1(|nijnPXiipjXj：）称为从到的一步转移概率ijIIpP（）称为一步转移概率浙江大学随机过程91|,0,1ijnnpjipPXjXiijqji……n21X0X1X2XnXn-1pqPqp一步转移矩阵，状态转移图：001n1npqpXXn只传输和1的串联系统中，设每一级的传真率为,误码率为。以表示第一级的输入，表示第级的输出（）。{}Markov{0,1}nXI则是一时齐链，状态空间，012.传例（输系统）ppqq01浙江大学随机过程1013452.随例3（机游动）{12345}5),Iii设一醉汉在，，，，作随机游动：如果现在位于点（1则下一时刻各以1/3概率向左或向右移动一格，或以概率1/3呆在原处；如果现在位于点1（或点5），则下一时刻以概率1移到点2（或点4）。15和两点称为反射壁，这种游动称为带两个反射壁的随机游动。nXn用表示时刻醉汉所在的位置。{}MarkovnX则是一时齐链，1/31/312345111/31/31/31/31/31/3浙江大学随机过程1111133311133311133312345110000200300400500010P11133311133311133312345101000200300400500010P13452如果把1这点改为吸收壁，即Q一旦到达1这一点，则永远留在点1时，此时的转移概率矩阵为：浙江大学随机过程12例4：排队模型设服务系统由一个服务员和只可以容纳两个人的等候室组成。服务规则为：先到先服务，后来者需在等候室依次排队，假设一个需要服务的顾客到达系统时发现系统内已有3个顾客，则该顾客立即离去。设时间间隔⊿t内有一个顾客进入系统的概率为q，有一接受服务的顾客离开系统(即服务完毕)的概率为p,又设当⊿t充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的，再设有无顾客来到与服务是否完毕是相互独立的。等候室服务台系统随机到达者离去者浙江大学随机过程13现用马氏链来描述这个服务系统：设Xn=X(n⊿t)表示时刻n⊿t时系统内的顾客数，即系统的状态。{Xn,n=0,1,2…}是一随机过程，状态空间I={0,1,2,3},且如前例1、例2的分析可知，它是一个时齐马氏链，它的一步转移概率矩阵为：012301001(1)(1)(1)(1)020(1)(1)(1)(1)300(1)(1)qqpqpqpqqpPpqpqpqqppqpqp等候室服务台系统随机到达者离去者浙江大学随机过程14例5：设甲、乙两袋共装5个球，每次任取一袋,并从袋中取出一球放入另一袋(若袋中无球则不取)。Xn表示第n次抽取后甲袋的球数，n=1,2,….{Xn,n=1,2,…}是一随机过程，状态空间I={0,1,2,3,4,5},当Xn=i时，Xn+1=j的概率只与i有关，与n时刻之前如何取到i值是无关的，这是时齐马氏链，一步转移矩阵为：112211221122112211221122012345000000000100002000030000400005P甲乙浙江大学随机过程15例6：卜里耶（Polya)罐子模型。设一罐子装有r个红球，t个黑球，现随机从罐中取出一球，记录其颜色，然后将球放回，并加入a个同色球。持续进行这一过程，Xn表示第n次试验结束时罐中的红球数，n=0，1,2,….{Xn,n=0，1,2,…}是一随机过程，状态空间I={r,r+a,r+2a,…},当Xn=i时，Xn+1=j的概率只与i有关，与n时刻之前如何取到i值是无关的，这是一马氏链，但不是时齐的,一步转移概率为：1()10nnijiartnaiPXjXijirtna其它浙江大学随机过程1612,201210.1(12|2,7),(12|7)(2){}nnnnnXnYXXnPYYYPYYYMarkov例7：独立重复地掷骰子，用表示第次掷出的点数，令（）计算判断是否是链？浙江大学随机过程17201341231(12|2,7)(6|1,1,6)1/6PYYYPXXXXX（）1221131234662336(7,12)(12|7)(7)()(1,6)1(7)36PYYPYYPYPXXXPXX链。不是MarkovYYYPYYYPn}{)7|12()7,2|12()2(12102浙江大学随机过程1811aman例8甲乙两人玩抛硬币游戏，一开始甲带有元钱，乙带有元钱，独立重复抛一枚均匀硬币，若第次出现正面，则甲赢元，否则甲输元。游戏一直到某人输光结束。计算最后.赌徒输光甲输光问题：的概率。浙江大学随机过程1900,1,1{}Markov{0,1,...,},1,0.5,0.nnmmiiiiSnSmppppim解：以表示抛次硬币后甲所拥有的钱数。则是一时齐链，状态空间是一步转移概率为：00101010112(|),1,0,(|)(|,)(|)(),0.imijijiijhPSihhhPSjSiPSjSipPSjhhim令输光则输光输光11,0..iiiimmiiihhhhim{h}h即所以是等差数列，所以i元钱1i元钱1i元钱输光1/21/21ih1ih浙江大学随机过程20MarkovMarkov性当链有两个吸收态时，我们可以利用和全概率公式建立方程，计算被某一个特定吸收态吸收的概率。m上例中有两个吸收态0和，我们需要计算的是最终被状态0吸收的概率浙江大学随机过程213,7)inii例9如下图，假设猫不动，老鼠从2号房间出发在迷宫中作随机游动：如果时老鼠呆在（号房间，则下一时刻老鼠等可能地移到相邻的房间（即有门与号房间相连的房间);一旦老鼠到达7号房间，就被猫吃掉；一旦到达3号房间，老鼠就吃掉奶酪。计算老鼠在吃掉奶酪前被.迷宫中的老鼠：猫吃掉的概率？987654321猫奶酪浙江大学随机过程22n{}Markov{1,2,...,9},37nnXX解：一旦老鼠跑到3号或7号房间，我们就认为老鼠将永远呆在那个房间。用表示时老鼠所在的位置。则是一时齐链，状态空间是和是两个吸收态。所求的就是从2出发最终被7吸收的概率。073(7|),1,0.ihPXihh令最终被吸收则1591.2hhh利用对称性，2153Markov1111.3333hhhh利用性和全概率公式：浙江大学随机过程23有限维分布§2,,,ijikkjkpssuvpssupsusuvCK方程ksusuvtsij0,,,PssuvPssuPsusuvCK方程可以写成矩阵形：式浙江大学随机过程24CK方程的证明：||,sussuvssukPXkXiPXjXiXk全概率公式＝＝＝||sussuvsukPXkXiPXjXk马氏性＝＝＝,,ikkjkpssupsusuv,|ijsuvspsuvPXjXi证毕！浙江大学随机过程25{}MarkovnX时齐以后均假设是的链)C-K(,)(,),m,),ijmmijmmijPnnmPnPnnmPpnnmp（（）由方程：不依赖于，记称为步转移矩阵记（从到的步转移概率)mmPP（则浙江大学随机过程2612111121012()()11112...,(,...)()...kkkkknnijiknnnnnnkniiiinPXjPXipnnnPXiXiPXipp（）（）对任何，（）（）（）对任何命题：有限维分布完全由初始分布和一步转移概率所确定00))n,nnnP（（（）（）把初始分布和步分布分别写成行向量和则浙江大学随机过程270001(|)nnnijiiPXjPXiPXjXiPXip（）（）由全概率公式（）（）（）证明：1121111211121112111()()12(,...)()(|)...(|,...)()...kkkkkkknnknnnnknnknnnnniiiiPXiXiPXiPXiXiPXiXiXiPXipp（）由乘法公式浙江大学随机过程283144111424314401200120P002424502451,00,1,2Markov10,1,2310,1,1;21,1,0|031,1,0nXnPXiiPXXXPXXXXPXXX例：设是具有三个状态的时齐链，一步转移矩阵为：初始分布，试求：浙江大学随机过程29解：55181616225311621639116164PP（）(2)(2)024001115511(1)0,1,10316296PXXXPXpp（）(2)(2)245001111021,1,0|055111624128PXXXXppp