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