第5章 马尔可夫链.ppt

CHAPTER5马尔可夫链,第一节基本概念,1、分类,按马尔可夫过程参数空间和状态空间的不同可分为,一、马尔可夫链的定义及例子,随机过程称为马尔可夫链，若它只取有限或可列个值（称为过程的状态，记为0，1，2，），并且，对任意及状态，有,2.马尔可夫链的定义,定义称为n时刻的一步转移概率。,若，即pij与n无关，称转移概率具有平稳性.此时称Xn,n0为齐次（或时齐的）马尔可夫链。记P=(pij)，称P为Xn,n0的一步转移概率矩阵.,3、转移概率,4、马尔可夫链的例子,显然Yn,n1也是一马尔可夫链。,例1独立随机变量和的序列,设Yn,n1为独立同分布随机变量序列，且Yn取值为非负整数，其概率分布为PYn=i=ai，i=0,1,2,令X0=0,Xn=Y1+Yn，则易证Xn,n0是一马尔可夫链，且,例2M/G/1排队系统假设顾客依参数为的泊松过程来到一服务中心，只有一个服务员，来客发现服务员空着即刻得到服务；其他人排队等待服务。相继来到的顾客的服务时间Ti假定为相互独立的随机变量，具有共同的分布G；且假定他们与来到过程独立。M/G/1排队系统中字母M代表顾客来到时间间隔服从指数分布，G代表服务时间的分布，数字1代表只有一个服务员。若以X(t)记在t时刻系统中的顾客数，X(t),t0则不具马尔可夫性。因为，若我们知道在t时刻系统中的顾客数，那么为了预测将来的状态，我们不用关心从最近的一位顾客来到后已过去了多长时间（因为来到过程是无记忆的），但和服务中的顾客服务了多长时间有关（因为服务时间分布不具无记忆性）。,Xn-第n个顾客走后剩下的顾客数，Yn-第n+1个顾客接受服务期间来到的顾客数，则,容易证明Yn，n1独立同分布，且,因此，Xn，n1是马尔可夫链。其转移概率为,为了克服上述困难，我们可以只在顾客离去的时刻考察系统，记,例3G/M/1排队系统来到时间间隔分布为G，服务时间分布为指数分布，参数为，且与顾客到达过程独立。,Xn-第n个顾客来到时见到系统中的顾客数（包括该顾客），则Xn，n1是马尔可夫链。记,Yn-第n个顾客来到时刻到第n+1个顾客来到时刻之间系统服务完的顾客数，则,pi0公式略有不同，它是服务台由有i个顾客转为空闲的概率，即第n个顾客来到时刻到第n+1个顾客来到时刻之间系统服务完的顾客数i+1。,例4直线上的随机游动（1）无限制的随机游动设有一质点在数轴上随机游动，每隔一单位时间移动一次，每次只能向左或向右移动一单位，或原地不动。设质点在0时刻的位置为a,向右移动的概率为p，向左移动的概率为q，原地不动的概率为r(p+q+r=1),且各次移动相互独立，以Xn表示质点经n次移动后所处的位置，则Xn,n0是一马尔可夫链,转移概率为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(1i,jb-1)同（1），这时Xn,n0称为带两个吸收壁0和b的随机游动，它是一有限状态马尔可夫链。,例5Polya（波利亚）模型,罐中有b只黑球及r只红球，每次随机地取出一只后把原球放回，并加入与抽出球同色的球c只，再第二次随机地取球重复上面步骤进行下去，Xn=i表示第n回摸球放回操作完成后，罐中有i只黑球这一事件，所以,这是一个非齐次的马尔可夫链，在传染病研究中有用。,下面的定理提供了一个非常有用的获得马尔可夫链的方法，并可用于检验一随机过程是否为马尔可夫链。定理：设随机过程Xn,n0满足（1）Xn=f(Xn-1,Yn),(n1),其中f:SSS,且Yn取值在S上，（2）Yn,n1为独立同分布随机变量，且X0与Yn,n1也相互独立，则Xn,n0是马尔可夫链，其一步转移概率为pij=Pf(i,Y1)=j证明：设n1，则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,n0是马尔可夫链，且,所以有,二、切普曼-柯尔莫哥洛夫方程,显然马尔可夫链Xn,n0的一步转移概率矩阵P为随机矩阵。,2，n步转移概率定义：设Xn,n0是一马尔可夫链，称,1，随机矩阵定义：称矩阵A=(aij)SS为随机矩阵，若aij0，且,为马尔可夫链Xn,n0的n步转移概率。记,称,为n时刻Xn的概率分布向量。,称为马尔可夫链Xn,n0的初始分布向量。结论：一个马尔可夫链的特性完全由它的一步转移概率矩阵及初始分布向量决定。,类似地可以证明马尔可夫链任意个时刻的联合分布也完全由一步转移概率矩阵及初始分布向量决定。,事实上,3、定理：切普曼-柯尔莫哥洛夫方程（C-K方程）,或,其中,为马尔可夫链Xn,n0的n步转移概率矩阵。,证明：,例（马尔可夫预测）某种鲜奶A改变了广告方式，经调查发现购买A种鲜奶及另外三种鲜奶B、C、D的顾客每两个月的平均转换率为：（假设市场上只有这4种鲜奶）AA（95%）B（2%）C（2%）D（1%）BA（30%）B（60%）C（6%）D（4%）CA（20%）B（10%）C（7%）D（0%）DA（20%）B（20%）C（10%）D（50%）假设目前购买A、B、C、D4种鲜奶的顾客的分布为（25%，30%，35%，10%），求半年后鲜奶A、B、C、D的市场份额。,解一阶转移矩阵为,初始分布为,则,半年后A种鲜奶的市场占有率为,（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，则状态空间为,一步转移概率矩阵为,（2）二步转移概率矩阵,（3）在P2中P45(2)是在甲得1分的情况下经二步转移至2分从而结束比赛的概率；P41(2)是在甲得1分的情况下经二步转移至-2分（即乙得2分）从而结束比赛的概率。,解,例,某计算机房的一台计算机经常出故障,研究者每隔15分钟观察一次计算机运行状态,收集了24小时的数据(共作97次观察).用1表示正常状态,用0表示不正常状态,所得的数据序列如下:,1110010011111110011110111111001111111110001101101,分析,状态空间:I=0,1.,例,111011011010111101110111101111110011011111100111,96次状态转移的情况:,因此,一步转移概率可用频率近似地表示为:,第二节状态的分类及性质,定义1:若存在某个n使得，则称从状态i可达状态j，记为ij，如果ij且ji，则称i与j相通，记为。若一马尔可夫链的任意两个状态都是相通的，则称该马尔可夫链是不可约的。若pii=1。则称状态i为吸收态。,定理：相通是一种等价关系。即,定义2：若集合,则称该数集的最大公约数d(i)为状态i的周期。若d(i)1，称i为周期的，若d(i)=1，称i为非周期的。,注意：若状态i的周期为d,则对一切n0（mod(d)）都有,但并非对任意的n，都有。例如,定理：,则d(i)=d(j)。,证明：若i与j相通，则存在m,n，使得,对任意的s，若有，则,则，对应状态1而言，集合,的最大公约数为2，所以，。但是，当时，。但可以证明：对于充分大的n，有。,因为d(i)是i的周期，所以d(i)应同时整除n+m和n+m+s，则d(i)一定整除s，而d(j)是j的周期，所以d(i)整除d(j)。反过来也可证明d(j)整除d(i)，于是d(i)=d(j)。,定义3：首达时间定义为,若右边为空集，则令Tij表示从i出发首次到达j的时间，Tii表示从i出发首次回到i的时间.,定义4：首达概率定义为,表示从i经n步首次到达j的概率。显然有,定义5,fij表示过程从i出发在有限步内能够到达j的概率，（或者说从i出发迟早转移到状态j的概率）。,fii表示过程从i出发在有限步内（迟早）回到状态i的概率。,定义6:若fii=1,则称i为常返状态，若fii1,则称i为非常返状态（或瞬时状态或称滑过的）。,定义7:若i为常返状态，即fii=1,记,称为从状态i出发再回到i的平均回转时间（或平均回转步数）。若，称为正常返状态，若，称为零常返状态。,定义8:若状态i是正常返的并且是非周期的，则称状态i为遍历状态。,注：当i为非常返状态（滑过的）时，。,定理：与有如下关系,定理：状态i是常返状态，当且仅当,状态i是非常返状态，当且仅当,证明：约定，,的含义,则,表示过程到达i的次数。,所以,表示过程从i出发返回到i的平均次数。,若状态i是滑过的（非常返的）则,即滑过状态i只能有限次到达i。从而有限状态的马尔可夫链不可能全部状态都是滑过的。即有限状态的马尔可夫链至少有一个状态是常返的。定理：若，则i,j同为常返的和非常返的。即常返性具有类性质。若为常返的，则它们同为正常返状态或零常返状态。证明：由，知存在n,m，使得，由C-K方程总有,所以，相互控制，同为无穷或有限，从而同为常返或非常返。,以Nj(t)记到时刻t为止转移到j的次数。若j是常返的，且X0=j，则因为一旦转移到j，过程在概率上重新从头开始，故Nj(t),t0是一个来到时间间隔分布为的更新过程。若X0=i，且j是常返的，则Nj(t),t0是一个延迟更新过程，其初始来到时间间隔分布为。,为什么要将状态进行分类呢？,常返态表明，过程从常返状态出发能无穷次返回该状态，而滑过状态最多只能有限次地返回，因此，随着时间的发展，滑过状态将逐渐消失。所以，在对Markov链作稳态设计时，滑过状态是不予考虑的，这也说明了区分常返态与滑过状态是十分重要的。,例考虑直线上无限制的随机游动，状态空间为,转移概率为,则对于状态0，有,由斯特林(Stirling)公式可知：当n充分大时有,所以,注意到,所以，当时，,此时，状态0是常返的。,当时，,此时，状态0是滑过的。,由于过程的各个状态都是相通的，由此可判断其它状态的常返性。,例,转移矩阵,试对其状态分类。,解,按一步转移概率，画出各状态间的传递图,从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。,考虑状态1是否常返，,类似地可求得,所以,于是状态1是常返的。,又因为,所以状态1是正常返的。,由定理可知，此链所有状态都是正常返的。,例,设马氏链的状态空间I=0,1,2,，其一步转移概率为,其中,试证此马氏链是一个不可约常返态链,证,先证I不可约,设i，j是I中任意两个状态，,则有,类似地可证,所以,即I中任意两个状态都是相通的。,因此，I是一个不可约的闭集,再证I中状态0是一个常返态：,由状态的转移规则，得,所以,1,0,2,3,4,5,由定义知状态0为常返态。,因此，由定理知I中所有状态都是常返态。,故此马氏链为不可约常返链。,例股票价格的马尔科夫性考虑离散时间的股票价格过程，对时间t(t=0,1,2,),设S(t)表示某一股票在t时刻的价格，每间隔一个单位时间股票价格以概率q上升到前一期的u倍，或以概率1-q下降到前一期的d倍，且各次涨跌是相互独立的，即,以概率q,以概率1-q,设S(0)=S，则,定义独立同分布的随机变量序列,第i次上涨,第i次下跌。,则,并且,定义,第i次上涨,第i次下跌。,则是一Markov链。(随机游动),状态空间的分解,定义1设马尔可夫链的状态空间为S，若对任意的，都有，则称C为（随机）闭集。若C的状态相通，则称闭集C是不可约的。,注：状态i是吸收态等价于单点集i是闭集；马尔可夫链的整个状态空间为S构成一闭集。,闭集C的直观意义是自C的内部不能到达C的外部，这意味着系统状态一旦进入闭集C内，它就永远在C中运动。,引理1C是闭集的充要条件是对任意的都有。,证明：充分性显然，下证必要性，用归纳法证明：当n=1时，由定义知结论成立，假设n=k时结论成立，即对任意的有则,引理2若i是常返的，且，则。,证明：若假如，则以正概率，使得从j出发不能在有限步内到达i。而，这意味着系统中存在着一个正概率，使得它从i出发不能在有限步内回到i,从而，与i是常返状态矛盾，所以只能。,引理3若i是常返的，且，则j是常返的。,证明：由引理2知，于是存在n使得从而，即。所以。即j也是常返状态。,定理1所有的常返状态构成一闭集。,证明：设i是常返状态，且，则引理1，2知，且j也是常返状态，说明从常返状态出发只能到达常返状态，不可能到达非常返状态。,定理2马尔可夫链的状态空间S可分解为,其中为基本常返闭集，且T为所有非常返状态组成的集合（不一定是闭集）。,【注】当系统从某非常返状态出发，系统可能一直在非常返集T中（当T为闭集时），也可能在某时刻离开T进入到基本常返集中运动，一旦进入到基本常返集，就永远在该常返集中运动。,定理3若S为有限集，则所有非常返状态组成的集,合T一定是非闭集。即不管系统自什么状态出发，迟早,要进入常返闭集。,推论有限不可约马尔可夫链的状态都是常返态。即,定理4设是闭集，只考虑上所得的m步转移概率子矩阵，则是一随机矩阵。,证明：显然，任取,所以，矩阵为随机矩阵。,定理5（系统进入基本常返闭集后的运动情形）若基本常返闭集中的状态的周期为d，则可进一步d个不交子集之和，即,这些子集有性质：自中任一状态出发，下一步（经1步转移）必转移到中去。如果i=d-1，则i+1=d解释为0，即中的的状态下一步转移到中去。,证略。,第三节极限定理与平稳分布,一、极限定理,在实际应用中，人们常常关心两个问题：,（1）当时，的极限是否存在？,（2）当什么条件下，一个马尔可夫链是一个平稳序列？,注意到：，故对（1）的研究可转化为对的渐近性质的研究。即是否存在？若存在，其极限是否与状态i有关？Markov链理论中，有关这一问题的定理统称为遍历定理。,问题(2)的实际上是讨论马尔可夫链平稳分布是否存在的问题。这两个问题之间有密切联系。,例1设马尔可夫链的转移概率矩阵为,现在来计算,令,则,所以,定理1若j是非常返态（滑过的）则对任意的i有,证明：因为,所以，,令，得,（因为j是非常返态）,显然此时有,定理2若j是常返态，则,（1）若，则有,（2）若时（不可达）则有,证明（1）若，则使得,而,故,（2）显然。,的含义,则,表示过程到达j的次数。,所以,表示过程从i出发进入状态j的平均次数。,定理3若j是非常返态或零常返态，则对任意的i有,证明：定理1已证j是非常返态情形，当j是零常返态时，取有，,先固定m，令得,这是因为上式中，且是有限项和。从而,再令，注意到,所以,推论1有限状态的马尔可夫链没有零常返态。,推论2有限状态的马尔可夫链的状态不可能全为非常返状态。,推论3不可约的有限状态马尔可夫链的状态全为正常返的。,推论4若马尔可夫链有一个零常返态，则必有无限个零常返态。（由推论1可得）。,定理4若j是正常返态，周期为d,则对任意的i及有,当j是正常返状态时情况较复杂，此时不一定存在，即使存在也可能与i有关。这时有一下结论:(证略),其中,表示从状态i出发，在时刻n=r(mod(d)首次到达状态j的概率。且,推论1若j是遍历状态（正常返的并且是非周期的），则对任意的状态iS有,证明：在定理4中取d=1,r=0。,推论2对于不可约的遍历链（即所有状态是遍历状态且相通），若对任意状态i，jS，有,注意到：若，且j为常返态，则。由推论1即得。,定理4若j是常返状态，则对任意的iS，有,推论若不可约马尔可夫链的状态是常返状态，则对任意的i，jS，有,注意：表示过程从i出发前n个单位时间进入,状态j的总的平均次数，表示每单位时间到达状,态j的平均次数，与表达的含义相同。,状态性质判别法：,i非常返,i零常返,i正常返,i遍历的,二、平稳分布与极限分布,1，定义：设pij是马尔可夫链Xn,n1的转移概率。若概率分布pj,j0满足,则称pj,j0为Xn,n1的平稳分布。记,则平稳分布可表示为如下矩阵形式,显然有,即,注意：由知，所以1是矩阵P的左特征值，平稳分布是P的左特征向量。,证明：若马尔可夫链Xn,n0的初始分布,即Xn与X0有相同的分布，这说明过程Xn,n0是平稳过程。这也是称分布pj=PX0=j为平稳分布的原因。,定理：设Xn,n0是马尔可夫链，则Xn,n0是平稳过程的充要条件是其初始分布是平稳分布。,是平稳分布，则对任意的n，有,反之，若Xn,n0是平稳过程，则,而,所以,即是平稳分布。,平稳分布可通过求方程组,的非负解得到。其中。,2，定义：若不可约马尔可夫链是遍历的（即所有状,称为马尔可夫链的极限分布。,态相通且均为周期为1的正常返态），则极限,定理：不可约遍历的马尔可夫链有唯一的平稳分布,此时唯一的平稳分布就是极限分布。即,注：若状态都是滑过的（非常返）或都是零常返的，则平稳分布不存在。,证明：由定理4的推论2知不可约遍历的马尔可夫链的极限分布存在，且,下证是平稳分布。由于,则有,易知上式中极限与求和可交换，则有,再由C-K方程得，,两边取极限得，,即，从而是平稳分布。,再证平稳分布的唯一性：,假设还有另外一个平稳分布，则有,归纳可证,令有，,因为，所以有，即平稳分布是唯一的。,定理：一个不可约非周期的马尔可夫链属于下列两种情况之一：,1，状态或全是滑过的（非常返的）或全是零常返的。此时对一切的i,j有,因而不存在平稳分布。,2，状态全是正常返态。即,此时是平稳分布，且不存在任何其它的平稳分布。此时极限分布即是平稳分布。,注：1，对于不可约的遍历链（不可约、正常返、周期为1）因为,所以，可被解释为马尔可夫链长时间之后处于状态j的时间所占的比率。2，对于不可约的遍历链，因为极限分布存在且等于平稳分布，这意味着当n充分大时有，,即Xn,n0是一渐近平稳序列(平稳过程)，这在实际问题中是很有意义的。,例,设马氏链的状态空间I=0,1,2,，转移概率为,试讨论各状态的遍历性。,解,根据转移概率作出状态传递图,从图可知，对任一状态都有，,故由定理可知，I中的所以状态都是相通的，,因此只需考虑状态0是否正常返即可。,故,从而0是常返态。,又因为,所以状态0为正常返。,又由于,故状态0为非周期的,从而状态0是遍历的。,故所有状态i都是遍历的。,例,设有6个球（其中2个红球，4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以表示开始时甲盒中红球的个数，（）表示经n次交换后甲盒中的红球数。,(1)求马氏链，的转移概率矩阵；,(2)证明，是遍历的；,（3）求,（4）求,解,其一步转移矩阵为,甲,乙,红球0白球3,红球2白球1,红球1白球2,红球1白球2,红球2白球1,红球0白球3,并作出状态传递图,（2）由于它是一个有限马氏链，故必有一个常返态，,又链中三个状态0、1、2都相通，所以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个状态都是正常返的。,所以此链为非周期的。,故此链是不可约非周期的正常返链，即此链是遍历的。,（2）可以利用定理证明遍历性,解之得,故得,（4）,讨论对时间连续状态离散的马尔可夫过程，取时间参数，状态空间I=0,1,2,第五节时间连续马尔可夫链,一、定义及性质,时间连续的马尔可夫链,转移概率,齐次马氏链,转移概率仅由t决定而与s无关,2性质,性质1,切普曼柯尔莫哥洛夫方程,性质2,连续时间齐次马氏链的有限维概率分布由它的初始分布和转移矩阵所确定,注,性质3,注,对时间来说是可逆性,性质4,已知现在，那么过去与将来是独立,注,性质5（遍历性定理）,马尔可夫定理,设,是状态空间I=0,1，2,s的时间连续的齐次马氏链，,则,的满足条件,的唯一解。,例1,考虑一个电话总机接到的呼唤流，以表示这个总机在0，t中接到的呼唤次数，由于呼唤流在不相交的时间区间中接到的呼唤次数是相互独立的，且服从泊松分布，所以是一个时间连续状态离散的马氏过程，而且是齐次的。写出它的转移概率。,当呼唤次数时,转移概率,当时,其状态空间I=0，1，2，,转移概率为,1随机连续,则称是随机连续的。,定理1,二、可尔莫哥洛夫微分方程,时间连续的齐次马氏链,是随机连续的充要条件为：对任意的，有,随机连续直观意义,当系统经过很短时间