马尔科夫链例题整理(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,若 表示质点在时,刻,n,所处的位置，分析它的,概率特性。,例,1,直线上带吸收壁的随机游动（醉汉游动）,设一质点在线段,1,，,5,上随机游动，每秒钟发生一次随机游动，移动的规则是：,（,1,）若移动前在,2,，,3,，,4,处，则均以概率 向左或向右 移动一单位；,（,2,）若移动前在,1,，,5,处，则以概率,1,停留在原处。,质点在,1,，,5,两点被“吸收”,1,2,3,4,5,前言：马尔可夫过程的描述分类,1,首页,无记忆性,未来处于某状态的概率特性只与现在状态有关，而与以前的状态无关，这种特性叫无记忆性（无后效性）。,例,4,布朗运动,2,若 表示质点在时,刻,n,所处的位置，求,一步转移概率。,引例,例,1,直线上带吸收壁的随机游动（醉汉游动）,设一质点在线段,1,，,5,上随机游动，每秒钟发生一次随机游动，移动的规则是：,（,1,）若移动前在,2,，,3,，,4,处，则均以概率 向左或向右 移动一单位；,（,2,）若移动前在,1,，,5,处，则以概率,1,停留在原处。,质点在,1,，,5,两点被“吸收”,1,2,3,4,5,一步转移概率矩阵的计算,3,首页,有两个吸收壁的随机游动,其一步转移矩阵为,状态空间,I=1,，,2,，,3,，,4,，,5,，,参数集,T=1,，,2,，3,，,，,4,例,2,带有反射壁的随机游动,设随机游动的状态空间,I,=0,，,1,，,2,，,，移动的规则是：,（,1,）若移动前在,0,处，则下一步以概率,p,向右移动一个单位，以概率,q,停留在原处（,p,+,q,=1,）；,（,2,）若移动前在其它点处，则均以概率,p,向右移动一个单位，以概率,q,向左移动一个单位。,设 表示在时刻,n,质点的位置，则,，,是一个齐次马氏链，写出其一步转移概率。,首页,5,q,p,右反射壁,m-1,m,p,q,左反射壁,1,2,0,首页,6,p,q,反射壁,1,2,3,0,首页,7,例,3,一个圆周上共有,N,格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率,p,顺时针游动一格，以概率,逆时针游动一格。试求转移概率矩阵。,首页,8,4,一个质点在全直线的整数点上作随机游动，移动的规则是：以概率,p,从,i,移到,i,-1,，以概率,q,从,i,移到,i,+1,，以概率,r,停留在,i,，且 ，试求转移概率矩阵。,首页,9,5,设袋中有,a,个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有,k,个白球，则称系统处于状态,k,，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。,解 这是一个齐次马氏链，其状态空间为,I=0,，,1,，,2,，,，,a,一步转移矩阵是,首页,10,练习题,扔一颗色子，若前,n,次扔出的点数的最大值为,j,，就说,试问 是否为马氏链？求一步转移概率矩阵。,I=1,，,2,，,3,，,4,，,5,，,6,首页,11,12,例,1,甲、乙两人进行比赛，设每局比赛中甲胜的概率是,p,，乙胜的概率是,q,，和局的概率是 ，（）。设每局比赛后，胜者记“,+1”,分，负者记“,1”,分，和局不记分。当两人中有一人获得,2,分结束比赛。以 表示比赛至第,n,局时甲获得的分数。,（,1,）写出状态空间；,（,3,）问在甲获得,1,分的情况下，再赛二局可以结束比赛的概率是多少？,首页,13,解,（,1,）,记甲获得“负,2,分”为状态,1,，获得“负,1,分”为状态,2,，获得“,0,分”为状态,3,，获得“正,1,分”为状态,4,，获得“正,2,分”为状态,5,，则状态空间为,一步转移概率矩阵,首页,14,（,2,）二步转移概率矩阵,首页,15,（,3,）,从而结束比赛的概率；,从而结束比赛的概率。,所以题中所求概率为,首页,16,分析,例,2,赌徒输光问题,赌徒甲有资本,a,元，赌徒乙有资本,b,元，两人进行赌博，每赌一局输者给赢者,1,元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为,p,，乙获胜的概率为 ，求甲输光的概率。,这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于,a,，每次移动一格，向右移（即赢,1,元）的概率为,p,，向左移（即输,1,元）的概率为,q,。如果一旦到达,0,（即甲输光）或,a,+,b,（即乙输光）这个游动就停止。这时的状态空间为,0,，,1,，,2,，,，,c,，,c=a,+,b,，。现在的问题是求质点从,a,出发到达,0,状态先于到达,c,状态的概率。,首页,17,考虑质点从,j,出发移动一步后的情况,解,同理,根据全概率公式有,这一方程实质上是一差分方程，它的边界条件是,首页,18,于是,设,则可得到两个相邻差分间的递推关系,于是,欲求,先求,需讨论,r,首页,19,当,而,两式相比,首页,20,故,当,而,因此,故,首页,21,用同样的方法可以求得乙先输光的概率,由以上计算结果可知,首页,22,例,3,排队问题,顾客到服务台排队等候服务，在每一个服务周期中只要服务台前有顾客在等待，就要对排在前面的一位提供服务，若服务台前无顾客时就不能实施服务。,则有,求其转移矩阵,在第,n,周期已有一个,顾客在服务，到第,n+,1,周期已服务完毕,23,解,先求出转移概率,首页,24,所以转移矩阵为,首页,25,证,26,定理,4.3,马尔科夫链的有限维分布：,27,练习,：,马氏链的状态空间,I=1,，,2,，,3,，初始概率为,28,例,4,市场占有率预测,设某地有,1600,户居民，某产品只有甲、乙、丙,3,厂家在该地销售经调查，,8,月份买甲、乙、丙三厂的户数分别为,480,，,320,，,800,。,9,月份里，原买甲的有,48,户转买乙产品，有,96,户转买丙产品；原买乙的有,32,户转买甲产品，有,64,户转买丙产品；原买丙的有,64,户转买甲产品，有,32,户转买乙产品。用状态,1,、,2,、,3,分别表示甲、乙、丙三厂，试求,（,1,）转移概率矩阵；,（,2,）,9,月份市场占有率的分布；,（,3,）,12,月份市场占有率的分布；,29,解,（,1,）,E1,，,2,，,3,状态,1,、,2,、,3,分别表示甲、乙、丙的用户,一步转移概率矩阵为,（,2,）以,1600,除,8,月份甲，乙，丙的户数得初始概率分布（即初始市场占有率）,30,所以,9,月份市场占有率分布为,（,3,）,12,月份市场占有率分布为,31,例,1,其一步转移矩阵为,试研究各状态间的关系，并画出状态传递图,。,解,先按一步转移概率，画出各状态间的传递图,首页,32,2/3,1/4,1/4,1/3,1/2,1/2,0,1,2,1/2,图,3-1,由图可知,状态,0,可到达状态,1,，经过状态,1,又可到达状态,2,；反之，从状态,2,出发经状态,1,也可到达状态,0,。,因此，状态空间,I,的各状态都是互通的。,又由于,I,的任意状态,i(i=0,，,1,，,2),不能到达,I,以外的任何状态，,所以,I,是一个闭集,而且,I,中没有其它闭集,所以此马氏链是不可约的,。,首页,33,例,2,其一步转移矩阵为,试讨论哪些状态是吸收态、闭集及不可约链,。,解,先按一步转移概率，画出各状态间的传递图,首页,34,1,1,1/2,1/2,1/2,3,1,1/2,图,4-2,4,5,2,1,闭集，,由图可知,状态,3,为吸收态,且,闭集，,闭集，,其中 是不可约的。,又因状态空间,I,有闭子集，,故此链为非不可约链。,首页,35,3,常返态与瞬时态,则称状态,i,为常返态,则称状态,i,为瞬时态,注,“,常返”一词，有时又称“返回”、“常驻”或“持久”,“,瞬时”也称“滑过”或“非常返”,定理,4,定理,5,定理,6,如果,i,为常返态，且 ，则,j,也是常返态。,定理,7,所有常返态构成一个闭集,36,5,正常返态与零常返态,平均返回时间,从状态,i,出发，首次返回状态,i,的平均时间,称为状态,i,平均返回时间,.,根据的值是有限或无限，可把常返态分为两类：,设,i,是常返态，,则称,i,为正常返态；,则称,i,为零常返态。,首页,37,例,其一步转移矩阵如下，是对,I,进行分解。,I,可分解为：,C,1,=2,，,3,4,C,2,=5,，,6,7,两个闭集及,N=1,，即,I=N+C1+C2,38,用极限判断状态类型的准则,（,2,）,i,是零常返态,（,3,）,i,是正常返态,（,1,）,i是瞬时态,且,且,首页,39,例,3,转移矩阵,试对其状态分类。,解,按一步转移概率，,画出各状态间的传递图,2,1/4,1,1,1/4,1/4,1,1/4,1,4,3,首页,40,从图可知，此链的每一状态都可到达另一状态，即,4,个状态都是相通的。,考虑状态,1,是否常返，,于是状态,1,是常返的。,又因为,所以状态,1,是正常返的。,此链所有状态都是正常返的。,2,1/4,1,1,1/4,1/4,1,1/4,1,4,3,41,三、状态的周期与遍历,1,周期状态,对于任意的 ，令,其中,GCD,表示最大公约数,则称 为周期态，,则称 为非周期态。,定理,11,2,遍历状态,若状态,i,是正常返且非周期，则称,i,为遍历状态。,1,1,1/2,1/2,1/2,3,1,1/2,图,4-2,4,5,2,1,42,例,4,设马氏链的状态空间,I,=0,1,2,，转移概率为,试讨论各状态的遍历性。,解,根据转移概率作出状态传递图,1/2,1/2,1/2,1/2,1/2,1/2,0,1,2,1/2,图,4-4,3,1/2,首页,43,从图可知，对任一状态 都有 ，,故由定理可知，,I,中的所以状态都是相通的，,因此只需考虑状态,0,是否正常返即可。,故,从而,0,是常返态。,又因为,所以状态,0,为正常返。,又由于,故状态,0,为非周期的,从而状态,0,是遍历的。,故所有状态,i,都是遍历的。,1/2,1/2,1/2,1/2,1/2,1/2,0,1,2,1/2,图,4-4,3,1/2,44,1/3,1/2,1,1/3,1/2,1,1/3,1,2,3,4,例,5,设马氏链的状态空间,I=1,，,2,，,3,，,4,，其一步转移矩阵为,解,试对其状态分类。,按一步转移概率，画出各状态间的传递图,它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。,可继续讨论是否为正常返态,45,可讨论状态,1,1/3,1/2,1,1/3,1/2,1,1/3,1,2,3,4,46,状态,1,是常返态,状态,1,是正常返态,所以，全部状态都是正常返态,首页,1/3,1/2,1,1/3,1/2,1,1/3,1,2,3,4,47,例,1,其一步转移矩阵为,试证此链具有遍历性，并求平稳分布和各状态的平均返回时间,解,由于,首页,48,所以,因此，该马氏链具有遍历性。,解得,所以马氏链的平稳分布为,X,1,2,3,各状态的平均返回时间,49,例,2,设有,6,个球（其中,2,个红球，,4,个白球）分放于甲、乙两个盒子中，每盒放,3,个，今每次从两个盒中各任取一球并进行交换，以 表示开始时甲盒中红球的个数，（）表示经,n,次交换后甲盒中的红球数。,(1),求马氏链,，,的转移概率矩阵；,(2),证明,，,是遍历的；,（,3,）求4,）求,首页,50,解,其一步转移矩阵为,甲,乙,红球,0,白球,3,红球,2,白球,1,红球,1,白球,2,红球,1,白球,2,红球,2,白球,1,红球,0,白球,3,1/3,2/9,5/9,2/3,2/9,1/3,0,1,2,2/3,51,由状态传递图,1/3,2/9,5/9,2/3,2/9,1/3,0,1,2,2/3,（,2,）由于它是一个有限马氏链，故必有一个常返态，,又链中三个状态,0,、,1,、,2,都相通，所以每个状态都是常返态。,所以是一个不可约的有限马氏链，从而每个状态都是正常返的。,所以此链为非周期的。,故此链是不可约非周期的正常返链，即此链是遍历的。,首页,52,也可以利用定理,1,证明遍历性,首页,53,解之得,故得,首页,54,（,4,）,首页,55,例,3,市场占有率预测,设某地有,1600,户居民，某产品只有甲、乙、丙,3,厂家在该地销售。经调查，,8,月份买甲、乙、丙三厂的户数分别为,480,，,320,，,800,。,9,月份里，原买甲的有,48,户转买乙产品，有,96,户转买丙产品；原买乙的有,32,户转买甲产品，有,64,户转买丙产品；原买丙的有,64,户转买甲产品，有,32,户转买乙产品。用状态,1,、,2,、,3,分别表示甲、乙、丙三厂，试求,（,1,）转移概率矩阵；,（,2,）,9,月份市场占有率的分布；,（,3,）,12,月份市场占有率的分布；,（,4,）当顾客流如此长期稳定下去市场占有率的分布。,（,5,）,各状态的平均返回时间,首页,56,解,（,1,）,由题意得频数转移矩阵为,再用频数估计概率，得转移概率矩阵为,（,2,）以,1600,除以,N,中各行元素之和，得初始概率分布（即初始市场占有率）,首页,57,所以,9,月份市场占有率分布为,（,3,）,12,月份市场占有率分布为,首页,58,（,4,）由于该链不可约、非周期、状态有限正常返的，所以是遍历的。,解方程组,即得当顾客流如此长期稳定下去是市场占有率的分布为,（,5,）,59,例,4,(,书中,69,页例,4.18,）,其一步转移矩阵为,试并每个不可约闭集的平稳分布,60,的平稳分布得,状态空间可分解为：,C=2,，,3,4 D=5,，,6,7,两个闭集，分别求对应转移概率矩阵,61,