第四章-马尔可夫链-随机过程

第四章马尔可夫链（MarkovChains）一、概念和转移概率矩阵1.概念随机过程{Xn,n=0,1,2,}可能取值集合为非负整数集E={0,1,2,}。若对一切状态i0,i1,i2,,in-1，i,j及一切n有(4.4.1)P{Xn+1=j|Xn=i,Xn-1=in-1,,X1=i1,X0=i0}=P{Xn+1=j|Xn=i}＝Pij则随机过程称为马尔可夫链（aMarkovchain）。若对一切状态i,j有P{Xn+1=j|Xn=i}＝Pij与n无关，则称马尔可夫链为齐次的或平稳的。本章研究的马尔可夫链为齐次的。方程(4.4.1)可解释为，对马尔可夫链，给定过去的状态X0,X1,,Xn-1及现在的状态Xn，将来的状态Xn+1的条件分布与过去的状态独立，只依赖于现在的状态，这种性质称为马尔可夫性（theMarkovianproperty）。2.一步转移概率矩阵Pij代表处于状态i的过程下一步转移到状态j的概率。由于概率是非负的，且过程必须转移到某个状态，所以有Pij0,i,j0;01,0,1,ijjPi以P记一步转移概率的矩阵(thematrixofone-steptransitionprobabilitiesPij)，从而000102101112012iiiPPPPPPPPPP例4.1(a)M/G/1排队系统。假设顾客依照参数为的泊松过程来到一服务中心，只有一个服务员，来客发现服务员空着即刻得到服务，其他人排队等待直至轮到他们。相继的顾客的服务时间假定是独立的随机变量，具有共同的分布G；且也假定他们与来到过程独立。此系统称为M/G/1排队系统。字母M代表顾客来到间隔的分布是指数分布，G代表服务时间的分布；数字1表示只有一个服务员。以Xn记第n个顾客走后留下的顾客数，n1。又以Yn记第(n+1)个顾客受服务期间来到的顾客数。当Xn0时，第n个顾客离去后余下有Xn个顾客，其中一人进入服务，而其余Xn-1人排队等侯。因此，下一个人离去时系统中将包含在排队的Xn-1个顾客以及第n+1个顾客服务期间的来客，11nnnXXY。当Xn=0时第n个顾客离去后系统中无顾客，第n+1个顾客到达后立即接受服务。因此，下一个人离去时系统中将只包含第n+1个顾客服务期间的来客。由此可见(4.1.2)11,0,0nnnnnnXYXXYX由于Yn,n1表示在不相重叠的服务时间区间中来到的人数，来到过程又是泊松过程，所以它们相互独立，且：(4.1.3)0(){}(),0,1,2,!jxnxPYjedGxjj从(4.1.2)与(4.1.3)得{Xn,n=1,2,}是马尔可夫链，转移概率为00()(),0,1,2,!jxjxPedGxjj10()(),1,1(1)!jixijxPedGxjiiji0ijP其它（2,2jii)0001020310111213212223323343000000PPPPPPPPPPPPPPP例4．1(b)G/M/1排队系统。假设顾客依照一个任意的更新过程来到一个单服务台的服务中心，来到间隔分布为G。进一步假设服务分布是指数分布，参数为。若以Xn记第n个顾客来到时见到系统中的顾客数，以Yn记第n个顾客与第(n+1)个顾客到达间隔时间内服务完的顾客数，则11nnnXXY，易知过程{Xn,n1}是马尔可夫链。为对此马尔可夫链计算转移概率Pij，我们首先注意到，只要有顾客在接受服务，则在任意长为t的时间中服务完的顾客数是均值为t的泊松随机变量。这是因为相继的服务时间服从指数分布，且如我们所知，这意味着服务完的顾客数构成一个泊松过程。所以，1,0()(),1,1(1)!ijtijtPedGtjiij这是因为若一个来客发现有i个人在系统中，那么下一个来客将发现人数为i+1减去已服务完毕的人数，易知有i+1-j个人被服务完毕的概率(对相继来到之间的时间取条件)等于上式的右端。Pi0的公式略有不同(它是在一个长度分布为G的随机时间区间内至少能服务i+1个顾客的概率)，由下式给出：001()(),0!ktikitPedGtik0ijP其它（1ji)0001101112202122233031323334404142434445000000000000000PPPPPPPPPPPPPPPPPPPPP例4.1(c)独立同分布随机变量之和。一般的随机游动。设Xi,i1独立同分布．且{},0,1,2,ijPXjaj若令00S及1nniiSX，因为11nnnSSX，所以{Sn,n0}是马尔可夫链，其转移概率ijjiPa,{Sn,n0}称为一般的随机游动。若Xi表示数轴上0时刻位于原点的随机质点从时刻i-1到时刻i的位移，则Sn表示随机质点在时刻n的位置。例4.1(d)简单随机游动。若对于某个,01pp有{1},{1}1iiPXpPXqp则称随机游动{Sn,n1}，其中010,nniiSSX为简单随机游动。于是在简单随机游动中过程总是(以概率p)朝上一步或(以概率q)朝下一步。11101.1ijpjiPpjijii3.切普曼——柯尔莫哥洛夫方程(chapman-kolmogorovequations)、n步转移概率(then-steptransitionprobability)矩阵已经定义了一步转移概率Pij。现在我们定义n步转移概率nijP为处于状态i的过程经n次转移后处于状态j的概率。即{|},0,,0nijnmmPPXjXinij当然有010ijijPij,1ijijPP。切普曼一柯尔莫哥格夫方程提供了计算n步转移概率的方法。切普曼一柯尔莫哥格夫方程：对一切,0nm，一切i，j，有(4.2.1)0nmnmijikkjkPPP证明：0{|}nmijnmPPXjXi000{|}{|,}nnmnkPXkXiPXjXkXi000{|}{|}nmnnmnikkjkkPXkXiPXjXkPP00121()mjnnnmiiijPPPPP若以()nP记n步转移概率的矩阵，则由(4.2.1)得()()()nmnmPPP，其中的点代表矩阵乘法。因此，()(1)(2)nnnnPPPPPPP于是()nP可以由矩阵P自乘n次而算出。二、状态分类(classificationofstates)1.状态可达和相通若对某个0n有0nijP，则称从状态i可到达状态j(statejissaidtobeaccessiblefromstatei)。两个相互可到达的状态i与j称为相通的（iandjaresaidtocommunicate)，记作ij。命题4.2.1相通是一种等价关系(anequivalencerelation)，即(1)反身性ii(2)对称性若ij，则ji(3)传递性若ij及jk，则ik。00121()nmijmjnnnmiiijPPPPPP证明前两点从相通的定义显然得知．为了证明(3)，假设ij及jk；则存在,mn，使得0,0mnijjkPP。因此，00mnmnmnikirrkijjkrPPPPP类似地可以证明存在一个s使0skiP。称相通的两个状态属于同一个类；由命题4.2.1，任意两个类或不相交或相同。称马尔可夫链是不可约的(theMarkovchainisirreducible)，若只存在一个类—即一切状态彼此相通。2．状态周期称状态i有周期d(stateiissaidtohaveperiodd)，若对每个不可被d整除的n有0niiP，且d是具有此性质的最大整数(d是{:0}niinP的最大公约数)。(若对一切n0，0niiP，则定义i的周期是无穷大。)具有周期1的状态称为非周期的(aperiodic)。以d(i)记i的周期。,ijjkik例设马尔可夫链的状态空间I={1,2,,9}，转移概率如下图从状态1出发再返回状态1的可能步数为T={4,6,8,10,12,14,16}，T的最大公约数为2，从而状态1的周期为2895672341313211111111命题4.2.2若ij，则d(i)＝d(j)。证明先证明d(j)整除d(i)设m与n使得0mnijjiPP，且假设0siiP。则：00mnnmnmjjjkkjjiijkPPPPP000nsmnsmnsmnsmnsmjjjkkjjiijjiikkjjiiiijkkPPPPPPPPPPP，因此d(j)同时整除n+m与n+m+s；于是只要0,()siiPnsmnms被d(j)整除。所以d(j)整除d(i)。类似论证d(i)整除d(j)。于是d(i)＝d(j)。3.状态首达概率和分类对于任何状态i与j，定义nijf是从i出发在时刻n首次转移到j的概率，0{,,1,,1|}nijnkfPXjXjknXi，n=1,2…令1nijijnff，则ijf表示过程从i出发迟早转移到状态j的概率。（注意，对ij，ijf为正的当且仅当从i可达到j)。若1jjf，称状态j是常返的(recurrent)，否则称为滑过的或非常返的(transient)。11112222(2)()(2)()1,0,221,0,22nnffnffn3344(2)()33(2)()441,0,21,0,2nnffnffn例状态空间I={1,2,3,4}，转移概率如图，指出各状态周期,是常返状态还是滑过状态？23412111121解首达概率为定理（补）对任意状态i,j及1n,有1nnknkijijjjkPfP证明：01002{|}{,|}{,11,,|}nijnnnvknkPPXjXiPXjXjXiPXjvkXjXjXi1010020{|}{|,}{,11,|}{|,,11,}nnvkknvkPXjXiPXjXjXiPXjvkXjXiPXjXiXjvkXj101021121{|}{|}{,11,|}{|}nnvknkknnnknkknkijjjijjjijjjkkPXjXiPXjXjPXjvkXjXiPXjXjfPfPfP命题4.2.3状态j为常返的当且仅当0njjnP。若j是滑过的，则到达j的次数是具有有限均值11jjf的几何分布的变量，011njjnjjPf。证明若过程以概率1从j出发最终要回到j，则状态j是常返的，然而由马尔可夫性可知：回到状态j在概率上过程就重新开始。因此，概率1它将再回到j。重复这种论证可见到达状态j的次数以概率1是无限的．因而其期望是无限的。另一方面，假设j是滑过的，则每当过程回到j，将有一个正概率1jjf，它永远不再回到j；因此到达j的次数是具有有限均值11jjf的几何分布的随机变量（包括X0=j)。由上述论证可见状态j为常返的当且仅当E[到达j的次数|X0=j]=，但若令1,0,nnnXjIXj，0nnI表示到达j的次数。因为E[0nnI|X0=j]=00[|]nnEIXj0njjnP，结论得证。注：E[在时刻n的更新次数|X0=j]=E[In|X0=j]=njjP上述命题的论证极为重要，因为它证明了一个滑过状态只能以概率1到达有限次(由此得名滑过)。这也导出下述结论：命题：有限状态的马