ch13马尔可夫链

第十三章马尔可夫链,运筹学OperationsResearch,13.1引言13.2马尔可夫链13.3首次到达时间13.4马尔可夫分析的计算机程序,11.1引言Introduction,根据当前的状态和发展趋向去预测未来的状态，这是管理决策中重要的环节之一，马尔可夫分析就是这方面常用的方法。我们不断观察一个系统所处的状态，这可以用一簇随机变量来表示，这就是随机过程。,定义1：具有标号的随机变量组Xi称为随机过程，其中iI。随机过程中，随机变量可取到的值称为状态，其全部可能取值的集合称为状态空间。标号（指标参数）全部可能取值组成的集合I称为参数空间，参数空间I常表示时刻。,状态和参数，可以是离散的，也可以是连续的。据此，可将随机过程分成四类：即：1、参数空间，状态空间均离散；2、参数空间离散，状态空间连续；3、参数空间连续，状态空间离散；4、参数空间、状态空间均连续。例1：我们要了解某地区10月1日一昼夜气温的变化情况，就要观察气温这个随机变量的变化过程，参数空间是时间区间0，24），状态空间是气体实数，它们都是非离散的随机过程。,例2：某电话总机在0，t）这段时间内接到的呼叫次数是随机变量，如果要了解总机的工作情况，就要研究呼叫次数随时间变化的过程，参数空间是时间区间0，+),t在一段时间内连续变化，而0，t）内的呼叫次数是离散的非负整数，因此它是参数空间连续、状态空间离散的随机过程。例3：如果在上例中，每隔五分钟统计电话总机接到呼叫的次数，则参数空间、状态空间都是离散的随机过程。我们将要讨论的是参数空间、状态空间都是离散的情况，且一个系统可能的状态是有限的。,我们要研究的问题是：1、如果系统现在处于状态r,则从现在起n步以后，系统处于状态s的概率是多少？即：求状态r状态s的概率prs(n)。2、很多步以后，系统处于状态s的概率是多少？即求ps(n)。3、如果系统现在处于状态r，步数不断增加，系统处于状态s的概率，或者说步数不断增加，系统处于状态s的概率是否稳定。即：prs(n)或ps(n)是否存在，条件是什么？怎样求值？4、从状态r首次到达状态s的期望步数是多少？,n步,这些问题的研究是很有现实意义的，例如：根据市场统计了解到，目前某公司生产的商品占有一定的销路比例，我现在要预测，n步以后，该公司将占有的销路比例是多少？另外，参加竞争的商品占有销路的比例会稳定吗？我们关心的是分析这样一类系统，即系统的下一个状态与当前状态有关，而与系统以前状态完全无关，这样的随机过程称为马尔可夫过程。或马尔可夫链，它可用来回答上述问题和其它许多与动态系统有关的问题。人们已用马尔可夫链来分析库存问题、商品销路问题、设备更新问题、人口增长问题、会计问题、工厂布局问题及有关动态系统的其它问题。,13.2马尔可夫链,定义2:一阶马尔可夫性质。如果xi+1的条件概率分布与系统在0，1，2，i-1步时的状态无关，仅与系统在第i步的状态有关，则称随机过程Xi具有一阶马尔可夫性质。用数学语言来表达为：若p（xi+1s|x0t0,x1t1,，xi-1=ti-1,xi=r）=p(xi+1s|xi=r),则称随机过程Xi具有一阶马尔可夫性质。,这就是说，对任意i,i+1步随机变量xi+1所处的某一状态的概率，仅受紧接在它前面的随机变量xi所处的状态影响，而与再前面的随机变量x0,x1,xi-1所处的状态无关，这种性质就是所谓的“无后效性”。概率p(xi+1s|xi=r)称为第i步的状态r转移到第i+1步的状态s的一步转移概率（Onestepprobability）,它是已知xi时xi+1的条件概率。,定义：一步平稳转移概率如果对每个r和sp(xi+1=s|xi=r)=p(x1=s|x0=r)=prs,对于所有的I都成立，则称第一步转移概率是平稳的或均匀的。从上可以看出，由现在的这一步状态r转移到下一步s的概率与现在的步数无关。对于所有的状态，其一步平稳转移概率组成了一步平稳转移概率矩阵。P=(prs)。定义4：一阶、有限状态马尔可夫链，如果随机过程Xi具有以下特点1.具有一阶马尔可夫性质2.有限个状态,3.一步平稳转移概率集P=(prs)(r、s=0,1,2,3n)4初始概率集P=(p0,p1,.pn)T。(pr=p(x0=r)r=0,1,2,.n)则称随机过程Xi为一阶、有限状态马尔可夫链。例6-1商品销路分配（书p454）冻干午餐一步平稳转移概率如下表：,上述随机过程为一阶、有限状态的马尔可夫链第一步RM的销路分配比例p0(1)(第1步后处于状态0的概率)P0(1)=P0(0)P00(1)+P1(0)P10(1)+P2(0)P20(1)=0.35*0.9+0.3*0.04+0.35*0.15=0.3795第一步MH的销路分配比例p1(1)p1(1)=p0(0)p01(1)+p1(0)p11(1)+p2(0)p21(1)=0.35*0.02+0.3*0.87+0.35*0.12=0.31第一步其他的销路分配比例p2(1)p2(1)=p0(0)p02(1)+p1(0)p12(1)+p2(0)p22(1)=0.35*0.08+0.3*0.09+0.35*0.73=0.3105写成矩阵形式：P(1)=PTP(0)其中,P(0)=,P(1)=分别为初始的和一步分配比例向量。,定义5：n步平稳转移概率prs(n)=p(xi+n=s|xi=r)=p(xn=s|x0=r)式中prs(n)=0对所有的状态r和s均成立n=1,2.=1对所有的状态r均成立n=1,2.,从现态必然要转到次态,请注意共有N+1种状态，下面来进一步推导一下n步平稳转移概率的计算公式，先看一下三个状态的二步平稳转移概率计算，见右下图。p00(2)=p00p00+p01p10+p02p20p01(2)=p00p01+p01p11+p02p21p02(2)=p00p02+p01p12+p02p22二步平稳转移概率矩阵的第一行的三个数p00(2),p01(2),p02(2)分别为一步转移矩阵的第一行乘以第一，二，三列所得，同样第二行的三个数,p00,P10(2),p11(2),p12(2)分别为二步转移矩阵的第二行乘以第一，二，三列所得，p20(2),p21(2),p22(2)分别为第三行乘以第一，二，三列所得，,一般地：prs(2)=prTps,如果定义两步平稳转移概率矩阵P(2)=(prs(2),则我们有：P(2)=P(1)*P(1)=P2n步平稳转移概率,所以，n步平稳转移概率矩阵P(n)=P(n-1)*P=Pn(P是一步平稳转移矩阵）,从计算n步转移概率的证明式中，可以引出一般的性质：prs（n）=prt(k)pts(n-k)（整数）这就是切普曼柯尔莫哥洛夫方程，这要将上述证明中用k代替n-1即得：=,=,例如：例商品销路分配书由此，第步商品销路分配比例,型：型：,其他型：这样，任意步n，多可以计算出几步平稳转移概率，和商品销路分配比例，书P表16.6表明了从步到步商品销路分配比例的情况，表16.7表明了n2,3,5,10,20,30,32,33时n步平稳转移概率矩阵，从中可以看出，自33步以后，不管步的状态如何，处于状态的概率为0.47,处于状态的概率为0.29，处于状态的概率为0.24，即每种参加商品竞争的商品最后的销路分配与各自的起始分配比例,无关。此时的转移概率称为平稳转移概率。下面我们要讲稳态平稳转移概率存在的条件以及它的计算。回答引言中讲的第三个研究问题。,书上P461给出了稳态平稳转移概率的条件,这个条件是充分条件,要求太宽了,有一个非常不恰当的地方是prr0（r=0，1，2，n）这个条件使许多存在稳态平稳转移概率的系统不满足,因此,使用这个定理是不好的,我们给出正确的条件,在此基础上叙述一个比较容易判别的充分条件。(一句话：书上的判别方法不实用，另外prr0条件多余，书上的p465例子与判别定理矛盾),定理1：对于不可约非周期马尔可夫链，如果状态是正常返的，则存在。,定理不证明，介绍一下概念术语。,“非周期”：若以d(r)表示使得的那些n的最大公约数，当d(r)1时，称d(r)为状态r的周期，当d(r)=1时称状态r为非周期。（状态r经过n步后回到状态r的概率存在，这些n互约）,“不可约”：状态空间里任意两个状态是相通的，即对任意两个状态r，s，存在正整数n，使，也存在正整数m，使。,这就是书P461讲的第一个条件（16.7），它们是一致的。,“正常返”：先介绍常返状态和非常返状态。设Trr表示从状态r首次返回状态r的步数，则它可以是一步，两步它们的概率分别为，,对所有的状态非周期称为非周期马尔可夫链。显然，书P461讲的第二个条件（16.8）是非周期的特例。,则从状态r出发，返回状态r的概率为,若frr=1，则称状态r为常返的，若frr0。于是可以用线形方程组来计算出他的稳态概率,即,例6-2书P463商品销路分配问题中有两个可能的计划，MH型冻干午餐的制造商不满足于最终占有销路29%，因此考虑,解之得,计划A：制造商进行活动，设法使每一步保持原顾客的概率增加0.06(由0.89上升到0.93),而转向RM型和其它型的概率分别降到0.02和0.05。计划B:制造商进行活动,设法使买其它型的顾客吸引来买MH型的概率为18%.试向哪个计划最终可以使MH型获得更大的销路分配比例?解:对计划A和计划B,它们新的转移矩阵分别为,分别解方程组,解得,显然计划A比计划B好，因为前者最终销路分配的比例为43.48%,而后者只有38.9%.,3.首次到达时间在第2小节中，我们基本上解决了引言中提出的问题,现在我们将要解决最后一个问题,即从状态R首次到达状态S的期望步数,这就是首次到达时间定义7:首次到达时间从状态r首次到达状态s所需的转移步数定义为从状态r到s的首次到达时间我们用Trs表示,显然Trs不是一个确定的值,它可能是1步,2步，n步，类似于讲正常状态返状态那样，如果系统从状态r最终（可能经过很多步）到达状态s的概率为，则相应的首次到达时间rs为随机变量。,例如一步平稳转移概率如下,计算两步转移概率：,它是一个正矩阵，因此，具有稳态概率，由上节定理又可知所有的状态都是正常返的，由此可知，任何两个状态之间的首次到达时间是随机变量。,又如：一步平稳转移概率如下：,由此计算可得：,有正矩阵有稳态（所以这是一个充分条件）有稳态?有正矩阵可能存在吸收态,这可以看出，系统最终将处于状态，事实上，当进入状态时就,状态2称为吸收态,以上例子仍属于稳态平稳转移的例子!,非常返态,只能有限次的返回,常返态,能无穷多次的返回,不可能回到状态0和1，因此，返回状态0和1的概率显然不为1，即状态0和1是非常返状态，从而都不是随机变量，另外由于恒等于1，它也不是随机变量，但随机变量。如果Trs是随机变量，t表示Trs能取的值，即t=1，2，3，而grs(t)为相应的分布密度系数，则的概率grs(1)=prs的概率grs(2)=progos(1)+prs-1gs-1s(1)+prs+1gs+1s(1)+prNgNs=prigis(1)=-pssgrs(1)的概率grs(3)=progos(2)+prs-1gs-1s(2)+prs+1gs+1s(2)+prNgNs(2)=prigis(2)=pri(-pssgis(1),=pri-pssprigis(1)=-prs-pssgrs(2)=-pssgrs(2)-grs(1)=-grs(t)grs(n)=progos(n-1)+prs-1gs-1s(n-1)+prs+1gs+1s(n-1)+prNgNs(n-1)=prigis(n-1)=-grs(t),因为是随机变量又Trs的期望值（从状态r到状态s的期望首次到达时间）为如果r=s，则期望首次到达时间就称为状态r的期望再现时间（Expectedrecurrencetime），它是处于状态r的稳态概率的倒数，即如果，是随机变量,两边相加,即,解上述N阶线性方程组可求出,例如书商品销路分配,所有，,从状态r(0,1,2)到s(0,1,2)的首次到达时间都是随机变量,计算概率密度函数不妨计算,或,同样,或,g01(3)=p00g01(2)+p02g21(2)=0.90.0276+0.080.0906=