第5章-马尔可夫链

CHAPTER5马尔可夫链第一节基本概念1、分类Xtt离散连续离散连续马尔可夫链马尔可夫序列可数状态马尔可夫过程连续状态马尔可夫过程按马尔可夫过程参数空间和状态空间的不同可分为一、马尔可夫链的定义及例子随机过程称为马尔可夫链，若它只取有限或可列个值（称为过程的状态，记为0，1，2，…），并且，对任意及状态，有,0,1,2,nXn0n011,,,,,nijiii10011111(,,,,)()nnnnnnPXjXiXiXiXiPXjXi2.马尔可夫链的定义定义称为n时刻的一步转移概率。,,ijS1nnijPXjXipn若，即pij与n无关，称转移概率具有平稳性.此时称{Xn,n≥0}为齐次（或时齐的）马尔可夫链。记P=(pij)，称P为{Xn,n≥0}的一步转移概率矩阵.,,ijijijSpnp000102101112012iiippppppPppp11,0,02,10,1,2,ijijjpijpi3、转移概率4、马尔可夫链的例子,0,jiijajipji显然{Yn,n≥1}也是一马尔可夫链。例1独立随机变量和的序列设{Yn,n≥1}为独立同分布随机变量序列，且Yn取值为非负整数，其概率分布为P{Yn=i}=ai，i=0,1,2,…令X0=0,Xn=Y1+…+Yn，则易证{Xn,n≥0}是一马尔可夫链，且例2M/G/1排队系统假设顾客依参数为的泊松过程来到一服务中心，只有一个服务员，来客发现服务员空着即刻得到服务；其他人排队等待服务。相继来到的顾客的服务时间Ti假定为相互独立的随机变量，具有共同的分布G；且假定他们与来到过程独立。M/G/1排队系统中字母M代表顾客来到时间间隔服从指数分布，G代表服务时间的分布，数字1代表只有一个服务员。若以X(t)记在t时刻系统中的顾客数，{X(t),t≥0}则不具马尔可夫性。因为，若我们知道在t时刻系统中的顾客数，那么为了预测将来的状态，我们不用关心从最近的一位顾客来到后已过去了多长时间（因为来到过程是无记忆的），但和服务中的顾客服务了多长时间有关（因为服务时间分布不具无记忆性）。Xn-----第n个顾客走后剩下的顾客数，Yn-----第n+1个顾客接受服务期间来到的顾客数，则11,0,0nnnnnnXYXXYX容易证明{Yn，n≥1}独立同分布，且100(){}{},0,1,2,!jxnnnxPYjPYjTxdGxedGxjj因此，{Xn，n≥1}是马尔可夫链。其转移概率为010(0)(0)(),0!jnnnnjxnPPXjXPYjXxPYjedGxjj为了克服上述困难，我们可以只在顾客离去的时刻考察系统，记110()(1)(1)(1),1,1(1)!0,ijnnnnnnnnjixijPPXjXiPXYjXiPYjiXiPYjixedGxjiijiP其它例3G/M/1排队系统来到时间间隔分布为G，服务时间分布为指数分布，参数为，且与顾客到达过程独立。Xn-----第n个顾客来到时见到系统中的顾客数（包括该顾客），则{Xn，n≥1}是马尔可夫链。记Yn-----第n个顾客来到时刻到第n+1个顾客来到时刻之间系统服务完的顾客数，则11nnnXXY,110111(),0,1,!iijnnnnnnnjtnpPXijXiPijXYXiPYjXitPYjedGtjijpi0公式略有不同，它是服务台由有i个顾客转为空闲的概率，即第n个顾客来到时刻到第n+1个顾客来到时刻之间系统服务完的顾客数≥i+1。011010(1)()(),0!innnnkiktkipPXXiPYiPYktedGtik例4直线上的随机游动（1）无限制的随机游动设有一质点在数轴上随机游动，每隔一单位时间移动一次，每次只能向左或向右移动一单位，或原地不动。设质点在0时刻的位置为a,向右移动的概率为p，向左移动的概率为q，原地不动的概率为r(p+q+r=1),且各次移动相互独立，以Xn表示质点经n次移动后所处的位置，则{Xn,n≥0}是一马尔可夫链,转移概率为Pi,i+1=p,Pi,i-1=q,Pi,i=r,其余Pi,j=0（2）带吸收壁的随机游动设（1）中的随机游动限制在S={0,1,2,…b}，当质点移动到状态0或b后就永远停留在该位置，即p00=1,pbb=1，其余pij(1≤i,j≤b-1)同（1），这时{Xn,n≥0}称为带两个吸收壁0和b的随机游动，它是一有限状态马尔可夫链。例5Polya（波利亚）模型罐中有b只黑球及r只红球，每次随机地取出一只后把原球放回，并加入与抽出球同色的球c只，再第二次随机地取球重复上面步骤进行下去，{Xn=i}表示第n回摸球放回操作完成后，罐中有i只黑球这一事件，所以1,1,0,nnijicbrnciPXjXijibrncelse这是一个非齐次的马尔可夫链，在传染病研究中有用。下面的定理提供了一个非常有用的获得马尔可夫链的方法，并可用于检验一随机过程是否为马尔可夫链。定理：设随机过程{Xn,n≥0}满足（1）Xn=f(Xn-1,Yn),(n≥1),其中f:S×S→S,且Yn取值在S上，（2）{Yn,n≥1}为独立同分布随机变量，且X0与{Yn,n≥1}也相互独立，则{Xn,n≥0}是马尔可夫链，其一步转移概率为pij=P[f(i,Y1)=j]证明：设n≥1，则Yn+1与X0,X1,…,Xn相互独立，事实上，因为X1=f(X0,Y1)，Y2与X0,Y1独立，所以，Y2与X1，X0独立。同理，X2=f(X1,Y2)=f(f(X0,Y1),Y2)，所以，Y3与X2，X1，X0独立。归纳可得Yn+1与X0,X1,…,Xn相互独立。所以{Xn,n≥0}是马尔可夫链，且111()(,)(,)ijnnnpPXjXiPfiYjPfiYj1100110011001111(,)(,,)(,,)(,)()nnnnnnnnnnnnnnnnnnnnnPXiXiXiPfXYiXiXiPfiYiXiXiPfiYiPXiXi所以有二、切普曼-柯尔莫哥洛夫方程,1ijjSiSa有显然马尔可夫链{Xn,n≥0}的一步转移概率矩阵P为随机矩阵。2，n步转移概率定义：设{Xn,n≥0}是一马尔可夫链，称1，随机矩阵定义：称矩阵A=(aij)S×S为随机矩阵，若aij≥0，且,0,,0nijnmmpPXjXinij为马尔可夫链{Xn,n≥0}的n步转移概率。记(),innPXi称12(),(),,(),innn为n时刻Xn的概率分布向量。12(0),(0),,(0),i称为马尔可夫链{Xn,n≥0}的初始分布向量。结论：一个马尔可夫链的特性完全由它的一步转移概率矩阵及初始分布向量决定。001121,00110011002200110011001100221111,,,,,,0nnnnnnnnnnnniiiiiiiPXiXiXiPXiPXiXiPXiXiXiPXiXiXiPXiPXiXiPXiXiPXiXippp类似地可以证明马尔可夫链任意个时刻的联合分布也完全由一步转移概率矩阵及初始分布向量决定。事实上3、定理：切普曼-柯尔莫哥洛夫方程（C-K方程）0mnnmijikkjkppp或()()()mnnmmnPPPP其中()nnijPp为马尔可夫链{Xn,n≥0}的n步转移概率矩阵。证明：00000000012,,nmnmnknmnnknnmnknmikkjknnnnPXjXiPXjXkXiPXjXkXiPXkXiPXkXiPXjXkppPPPPPPP例（马尔可夫预测）某种鲜奶A改变了广告方式，经调查发现购买A种鲜奶及另外三种鲜奶B、C、D的顾客每两个月的平均转换率为：（假设市场上只有这4种鲜奶）A→A（95%）B（2%）C（2%）D（1%）B→A（30%）B（60%）C（6%）D（4%）C→A（20%）B（10%）C（7%）D（0%）D→A（20%）B（20%）C（10%）D（50%）假设目前购买A、B、C、D4种鲜奶的顾客的分布为（25%，30%，35%，10%），求半年后鲜奶A、B、C、D的市场份额。解一阶转移矩阵为0.950.020.020.010.300.600.060.040.200.100.700.000.200.200.100.50P初始分布为1234(,,,)(0.25,0.30,0.35,0.10)则30.88940.04580.04660.018200.601750.25590.09880.043550.48340.13880.365840.011960.50090.21340.142640.14306P半年后A种鲜奶的市场占有率为0.88940.60175(0.25,0.30,0.35,0.10)0.6240.48340.5009（1）写出状态空间；（2）求P(2)；（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？例甲、乙两人进行比赛，设每局比赛中甲胜的概率p，乙胜的概率是q，和局的概率是r,(p+q+r=1)。设每局比赛后，胜者记“+1”分，负者记“-1”分，和局不记分。当两人中有一人获得2分结束比赛。以Xn表示比赛至第n局时甲获得的分数。解（1）记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为}54321{，，，，I一步转移概率矩阵为1000000000000001prqprqprqP（2）二步转移概率矩阵2)2(PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq4541(2)(2)()0(1)PPprppr（3）在P2中P45(2)是在甲得1分的情况下经二步转移至2分从而结束比赛的概率；P41(2)是在甲得1分的情况下经二步转移至-2分（即乙得2分）从而结束比赛的概率。?55,35,15.}1,{.)10(,1,0.,21,31,于多少日为雨天的概率各等月日为晴天月问天日为晴月又已知的一步转移概率矩阵试写出马氏链或天状态表示第表示雨天状态以表示晴天状态以为逆事件任一天晴或雨是互晴天转雨天的概率为雨天转晴天的概率为设任意相继的两天中nXnXnn解为逆事件且雨天转由于任一天晴或雨是互转移概率矩阵分别为故一步转移概率和一步,21,31晴天转雨天的概率为晴天的概率为例1,0,210,0,211,1,320,1,311jijijijiiXjXPnn323121211010P又由于181118712712510102P,6003.03997.05995.04005.010104P又由于日为雨天的概率为月日为晴天月故55,15.5995.0)4(01P日为晴天的概率为月日为晴天月故35,15,4167.0125)2(0