ch13马尔可夫链

第十三章马尔可夫链运筹学OperationsResearch13.1引言13.2马尔可夫链13.3首次到达时间13.4马尔可夫分析的计算机程序11.1引言IntroductionCH13马尔可夫链2020年6月17日星期三Page3根据当前的状态和发展趋向去预测未来的状态，这是管理决策中重要的环节之一，马尔可夫分析就是这方面常用的方法。我们不断观察一个系统所处的状态，这可以用一簇随机变量来表示，这就是随机过程。CH13马尔可夫链2020年6月17日星期三Page4定义1：具有标号的随机变量组{Xi}称为随机过程，其中i∈I。随机过程中，随机变量可取到的值称为状态，其全部可能取值的集合称为状态空间。标号（指标参数）全部可能取值组成的集合I称为参数空间，参数空间I常表示时刻。CH13马尔可夫链2020年6月17日星期三Page5•状态和参数，可以是离散的，也可以是连续的。据此，可将随机过程分成四类：即：1、参数空间，状态空间均离散；2、参数空间离散，状态空间连续；3、参数空间连续，状态空间离散；4、参数空间、状态空间均连续。例1：我们要了解某地区10月1日一昼夜气温的变化情况，就要观察气温这个随机变量的变化过程，参数空间是时间区间[0，24），状态空间是气体实数，它们都是非离散的随机过程。CH13马尔可夫链2020年6月17日星期三Page6例2：某电话总机在[0，t）这段时间内接到的呼叫次数是随机变量，如果要了解总机的工作情况，就要研究呼叫次数随时间变化的过程，参数空间是时间区间[0，+∞),t在一段时间内连续变化，而[0，t）内的呼叫次数是离散的非负整数，因此它是参数空间连续、状态空间离散的随机过程。例3：如果在上例中，每隔五分钟统计电话总机接到呼叫的次数，则参数空间、状态空间都是离散的随机过程。我们将要讨论的是参数空间、状态空间都是离散的情况，且一个系统可能的状态是有限的。CH13马尔可夫链2020年6月17日星期三Page7我们要研究的问题是：1、如果系统现在处于状态r,则从现在起n步以后，系统处于状态s的概率是多少？即：求状态r状态s的概率prs(n)。2、很多步以后，系统处于状态s的概率是多少？即求ps(n)。3、如果系统现在处于状态r，步数不断增加，系统处于状态s的概率，或者说步数不断增加，系统处于状态s的概率是否稳定。即：prs(n)或ps(n)是否存在，条件是什么？怎样求值？4、从状态r首次到达状态s的期望步数是多少？n步limn∞limn∞CH13马尔可夫链2020年6月17日星期三Page8这些问题的研究是很有现实意义的，例如：根据市场统计了解到，目前某公司生产的商品占有一定的销路比例，我现在要预测，n步以后，该公司将占有的销路比例是多少？另外，参加竞争的商品占有销路的比例会稳定吗？我们关心的是分析这样一类系统，即系统的下一个状态与当前状态有关，而与系统以前状态完全无关，这样的随机过程称为马尔可夫过程。或马尔可夫链，它可用来回答上述问题和其它许多与动态系统有关的问题。人们已用马尔可夫链来分析库存问题、商品销路问题、设备更新问题、人口增长问题、会计问题、工厂布局问题及有关动态系统的其它问题。CH13马尔可夫链2020年6月17日星期三Page913.2马尔可夫链CH13马尔可夫链2020年6月17日星期三Page10定义2:一阶马尔可夫性质。如果xi+1的条件概率分布与系统在0，1，2，……，i-1步时的状态无关，仅与系统在第i步的状态有关，则称随机过程｛Xi｝具有一阶马尔可夫性质。用数学语言来表达为：若p（xi+1＝s|x0＝t0,x1＝t1,……，xi-1=ti-1,xi=r）=p(xi+1＝s|xi=r),则称随机过程｛Xi｝具有一阶马尔可夫性质。CH13马尔可夫链2020年6月17日星期三Page11这就是说，对任意i,i+1步随机变量xi+1所处的某一状态的概率，仅受紧接在它前面的随机变量xi所处的状态影响，而与再前面的随机变量x0,x1,……xi-1所处的状态无关，这种性质就是所谓的“无后效性”。概率p(xi+1＝s|xi=r)称为第i步的状态r转移到第i+1步的状态s的一步转移概率（Onestepprobability）,它是已知xi时xi+1的条件概率。CH13马尔可夫链2020年6月17日星期三Page12定义３：一步平稳转移概率如果对每个r和sp(xi+1=s|xi=r)=p(x1=s|x0=r)=prs对于所有的I都成立，则称第一步转移概率是平稳的或均匀的。从上可以看出，由现在的这一步状态r转移到下一步s的概率与现在的步数无关。对于所有的状态，其一步平稳转移概率组成了一步平稳转移概率矩阵。P=(prs)。定义4：一阶、有限状态马尔可夫链，如果随机过程{Xi}具有以下特点1.具有一阶马尔可夫性质2.有限个状态CH13马尔可夫链2020年6月17日星期三Page133.一步平稳转移概率集P=(prs)(r、s=0,1,2,3……n)4初始概率集P=(p0,p1,…….pn)T。(pr=p(x0=r)r=0,1,2,…..n)则称随机过程{Xi}为一阶、有限状态马尔可夫链。例6-1商品销路分配（书p454）冻干午餐一步平稳转移概率如下表：RM0MH1“其他”2RM00.9p000.02p010.08p02MH10.04p100.87p110.09p12“其他”20.15p200.12p210.73p22CH13马尔可夫链2020年6月17日星期三Page14上述随机过程为一阶、有限状态的马尔可夫链第一步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)其中CH13马尔可夫链2020年6月17日星期三Page15P(0)=,P(1)=分别为初始的和一步分配比例向量。(0)0(0)1(0)2ppp(1)0(1)1(1)2ppp定义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……..()0nnrssp从现态必然要转到次态CH13马尔可夫链2020年6月17日星期三Page16请注意共有N+1种状态，下面来进一步推导一下n步平稳转移概率的计算公式，先看一下三个状态的二步平稳转移概率计算，见右下图。p00(2)=p00p00+p01p10+p02p20p01(2)=p00p01+p01p11+p02p21p02(2)=p00p02+p01p12+p02p22二步平稳转移概率矩阵的第一行的三个数p00(2),p01(2),p02(2)分别为一步转移矩阵的第一行乘以第一，二，三列所得，同样第二行的三个数p000012p11p22p01p10p20p02p12p21CH13马尔可夫链2020年6月17日星期三Page17P10(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步平稳转移概率()0101010101101010(|)(|)(,|)(|,)(|)(|)(|)(|)(|)nrsnnntInntInnntInnntIntItppXsXrpXsXtXrpXsXtXrpXsXtXrpXtXrpXsXtpXtXrpXsXtpXtXrp(1)(1)nnsrtrttstItIppp所以，n步平稳转移概率矩阵P(n)=P(n-1)*P=…Pn(P是一步平稳转移矩阵）CH13马尔可夫链2020年6月17日星期三Page18从计算n步转移概率的证明式中，可以引出一般的性质：prs（n）=prt(k)pts(n-k)（整数）这就是切普曼－柯尔莫哥洛夫方程，这要将上述证明中用k代替n-1即得：=tIn(,|)mnmkmtIpXsXtXr()(|)nmnmrspsrpXXCH13马尔可夫链2020年6月17日星期三Page19====(|,)(|)mnmkmmkmtIpXsXtXrpXtXr(|)(|)mnmkmkmtIpXsXtpXtXr()rtnkktstIpp()()knktsrttIppCH13马尔可夫链2020年6月17日星期三Page20例如：例６－１商品销路分配书Ｐ４５９－４６０由此，第２步商品销路分配比例(2)20.90.020.080.90.020.080.040.870.090.040.870.090.150.120.730.150.120.730.82280.04500.13220.08430.76850.1PP4720.24930.19500.5557CH13马尔可夫链2020年6月17日星期三Page21ＲＭ型：ＭＨ型：(2)(0)(2)(0)(2)(0)(2)00001102200.35*0.82280.3*0.08430.35*0.24390.400525ppppppp(2)(0)(2)(0)(2)(0)(2)10011112210.35*0.04500.3*0.76850.35*0.19500.31455pppppppCH13马尔可夫链2020年6月17日星期三Page22其他型：这样，任意步n，多可以计算出几步平稳转移概率，和商品销路分配比例，书P４６０表16.6表明了从０步到２０步商品销路分配比例的情况，表16.7表明了n＝2,3,5,10,20,30,32,33时n步平稳转移概率矩阵，从中可以看出，自33步以后，不管０步的状态如何，处于０状态的概率为0.47,处于１状态的概率为0.29，处于２状态的概率为0.24，即每种参加商品竞争的商品最后的销路分配与各自的起始分配比例(2)(0)(2)(0)(2)(0)(2)20021122210.35*0.13220.3*0.14720.35*0.55570.284925pppppppCH13马尔可夫链2020年6月17日星期三Page23无关。此时的转移概率称为平稳转移概率。下面我们要讲稳态平稳转移概率存在的条件以及它的计算。回答引言中讲的第三个研究问题。CH13马尔可夫链2020年6月17日星期三Page24书上P461给出了稳态平稳转移概率的条件,这个条件是充分条件,要求太宽了,有一个非常不恰当的地方是prr0（r=0，1，2，…，n）这个条件使许多存在稳态平稳转移概率的系统不满足,因此,使用这个定理是不好的,我们给出正确的条件,在此基础上叙述一个比较容易判别的充分条件。(一句话：书上的判别方法不实用，另外prr0条件多余，书上的p465例子与判别定理矛盾)定理1：对于不可约非周期马尔可夫链，如果状态是正常返的，则存在。定理不证明，介绍一下概念术语。()limnsrsnap()limnrsnpCH13马尔可夫链2020年6