马尔科夫链例题整理.ppt

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