马尔科夫链考试例题整理.pdf

若 表示质点在时刻n所处的位置，分析它的概率特性。例1 直线上带吸收壁的随机游动（醉汉游动）设一质点在线段1，5 上随机游动，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在2，3，4处，则均以概率 向左或向右 移动一单位；（2）若移动前在1，5处，则以概率1停留在原处。21质点在1，5两点被“吸收”1 2 3 4 5( )X n 前言：马尔可夫过程的描述分类 1 t X(t),例3 电话交换台在时刻前来到的呼叫数 是无后效性的随机过程. X(t),例2 直线上的随机游动时的位置 是 无后效性的随机过程.无记忆性未来处于某状态的概率特性只与现在状态有关，而与以前的状态无关，这种特性叫无记忆性（无后效性）。例4 布朗运动 2 若 表示质点在时刻n所处的位置，求一步转移概率。引例 例1 直线上带吸收壁的随机游动（醉汉游动）设一质点在线段1，5 上随机游动，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在2，3，4处，则均以概率 向左或向右 移动一单位；（2）若移动前在1，5处，则以概率1停留在原处。21质点在1，5两点被“吸收”1 2 3 4 5( )X n一步转移概率矩阵的计算 3 有两个吸收壁的随机游动其一步转移矩阵为 10000 2102100 0210210 0021021 000011P状态空间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质点的位置， 则 ， 是一个齐次马氏链，写出其一步转移概率。 nXnX 0n 5 q p右反射壁m-1 mpq左反射壁 1 20 1 0 0 0 . 0 0 00 0 0 . 0 0 00 0 0 . 0 0 0. . . . . . . . .0 0 0 0 0 . 00 0 0 0 0 . 0q pq pq pP q pq p 6 pq反射壁 1 2 301 0 0 0 .0 0 0 .0 0 0 . . . . . .q pq pP q p 7 例3一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率矩阵。 pq 1 1 0 0 0 . 00 0 . 0 00 0 . 0 0. . . . . . .0 0 . 0 00 . 0 0 0p qq pq pP q pp q 1,2,., I N 8 4一个质点在全直线的整数点上作随机游动，移动的规则是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r停留在i，且 ，试求转移概率矩阵。 1 qpr 1 . . . . . . . . 0 0 0 . 0 0 0 . . . . . . . .p r qP p r q ., 2, 1,0,1,2,.E 9 5设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。解 这是一个齐次马氏链，其状态空间为 I=0，1，2，a一步转移矩阵是 1 0 1 0 0 . 01 10 0 . 02 20 0 . 0. . . . . .1 10 . 0 00 . 0 0 1 0aa a aP a aaa a 10 练习题扔一颗色子，若前n次扔出的点数的最大值为j，就说 试问 是否为马氏链？求一步转移概率矩阵。 I=1，2，3，4，5，6,nX j,nX j 11 1 1 1 1 1 16 6 6 6 6 62 1 1 1 10 6 6 6 6 63 1 1 10 0 6 6 6 64 1 10 0 0 6 6 6 5 10 . 0 0 6 60 . 0 0 1 0P 12 例1甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是q，和局的概率是 ，（ ）。设每局比赛后，胜者记“+1”分，负者记“1”分，和局不记分。当两人中有一人获得2分结束比赛。以 表示比赛至第n局时甲获得的分数。 r1 rqp nX（1）写出状态空间；（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？ 13 解 （1） 记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为1 2 3 4 5I ， ， ， ，一步转移概率矩阵 1 0 0 0 00 0 0 00 00 0 0 0 1q r pP q r pq r p 14 （2）二步转移概率矩阵(2) 2P P 10000 20 222 02 00001 22 222 22 rpppqrqrq pprpqrrqq pprpqrrpq 15 （3）从而结束比赛的概率；从而结束比赛的概率。所以题中所求概率为 )1(0)( rprpp 16 分析例2 赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为 ，求甲输光的概率。 pq 1这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a + b（即乙输光）这个游动就停止。这时的状态空间为0，1，2，c，c = a + b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。 17 考虑质点从j出发移动一步后的情况解 设 cj0设 ju 为质点从 j出发到达0状态先于到达 c 状态的概率。 在以概率 p移到 1j 的假设下，到达0 状态先于到达 c 状态的概率为 1ju同理 以 概 率 q 移 到 1j 的 前 提 下 ， 到达0状态先于到达c状态的概率为 1ju根据全概率公式有 qupuu jjj 11 这一方程实质上是一差分方程，它的边界条件是0,10 cuu 18 于是设 )( 11 jjjj uupquu pqr 1 jjj uud则可得到两个相邻差分间的递推关系 1 jj rdd于是 21 2 0jj j jd rd r d r d 欲求 au 先求 ju 需讨论 r 19 当而 1r cuu 01 )( 110 jjcj uujcj d 10 010 dr jcj 011 drrc cjj uuu )( 11 iic ji uu 011 drd ic jiic ji 1 0(1 )j c jr r r d 01 drrr cj两式相比 ccjj rrru 1 20 故 ccaa rrru 1 cca pqpqpq )(1)()(当 1r 00 1 cduu c 而 0)( djcuj 因此 c jcuj 故 cbcacua 21 用同样的方法可以求得乙先输光的概率由以上计算结果可知当 1r 即 qp 时，甲先输光的概率为 cca pqpqpq )(1)()(当 1r 即 qp 时，甲先输光的概率为cb 当 qp 时，乙输光的概率为 ca pqpq )(1)(1 当 qp 时，乙先输光的概率为 ca 22 例3 排队问题顾客到服务台排队等候服务，在每一个服务周期中只要服务台前有顾客在等待，就要对排在前面的一位提供服务，若服务台前无顾客时就不能实施服务。 设在第 n 个服务周期中到达的顾客数为一随机变量 nY 且诸 nY 独立同分布： 1k kp 记 nX 为服务周期 n 开始时服务台前顾客数则有 0, 1,11 nn nnnn XY XYXX 若若 此时 nX ， 1n 为一马氏链， 求其转移矩阵 在第n周期已有一个顾客在服务，到第n+1周期已服务完毕23 解 先求出转移概率 )0|0( 0100 XXPp )0( 0 YP 0p)0|1( 0101 XXPp )1( 0 YP 1p)1|0( 110 nn XXPp )1|01( nnn XYXP )0( nYP 0p)1|1( 111 nn XXPp )1|11( nnn XYXP )1( nYP 1p)2|0( 120 nn XXPp )2|01( nnn XYXP )1( nYP 0)2|1( 121 nn XXPp )2|11( nnn XYXP )0( nYP 0p)2|2( 122 nn XXPp )1( nYP 1p 24 所以转移矩阵为 0 1 2 3 40 1 2 3 41 0 1 2 30 1 200 0p p p p pp p p p pP p p p pp p p 25 证 jXP n 0I , ni P X j X i 0 0I | ni P X i P X j X i ( )i I niji p p 0 , n iP X j X i (n) (n)1 2 1 2(1) (1) (1) (1)1 1 i 1 1 11 2 21E I=1,2,3 2 P ,P , P ,P5 51,P X =1= piinP p p p p p 设马氏链的状态空间 初始分布为试对n=1,2,3,计算 解：例2 26 定理4.3 马尔科夫链的有限维分布： 1 1 2 m-1 m1 1 2 2 m m 0 1 20 1 2 X ,X , ,X 1) , 0,0.1 0.2 0.70.9 0.1 00.1 0.8 0.10.3 0.4 0.3 X 0,X 1,X 2 2i ii i i i ii I P i i ip p p p nPp p p p n由全概率公式得到证明，它是公式（ 的推广。考虑状态0，1，2上的一个马氏链X它又转移概率矩阵初始分布为 ， ， ，试求 概率（1）3：（例 ） 2 3 4X 0,X 2,X 1p 27 练习：马氏链的状态空间I=1，2，3，初始概率为1 2 3 12 12 22 1 3 04 41 1 1 1 1 1, , ,4 2 4 3 3 31 30 4 4(1) PX(0)=1,X(1)=2,X(2)=2,p (2)(2) PX(1)=2,X(2)=2 X(0)=1=p(3) PX(1)=1,X(2)=2,X(3)=3p p p P p 计算证明：求 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分别表示甲、乙、丙的用户一步转移概率矩阵为480 48 96 48 960.7, 0.1, 0.2480 480 48032 320 32 64 640.1, 0.7, 0.2320 320 32064 32 800 64 320.08, 0.04, 0.88800 800 800 11 12 1321 22 2331 32 33P P P P P P P P P 88.004.008.0 2.07.01.0 2.01.07.0 1P（2）以1600除8月份甲，乙，丙的户数，得初始概率分布（即初始市场占有率）(0) (0) (0)1 2 3(0) ( , , ) (0.3 0.2 0.5)P p p p 30 所以9月份市场占有率分布为（3）12月份市场占有率分布为1)0()1( PPP )5.02.03.0( 88.004.008.0 2.07.01.0 2.01.07.0)54.019.027.0( 41)0()4( PPP )5.02.03.0( 488.004.008.0 2.07.01.0 2.01.07.0 )5983.01698.02319.0( 31 例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。 设马氏链 0, nXn 的状态空间 I=0，1，2 32310 414121 021211P解 先按一步转移概率，画出各状态间的传递图 32 2/31/41/4 1/31/21/20 1 21/2 图3-1由图可知 状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，状态空间I的各状态都是互通的。又由于I 的任意状态i (i = 0，1，2)不能到达I 以外的任何状态， 所以I是一个闭集而且I 中没有其它闭集 所以此马氏链是不可约的。 33 例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。解 先按一步转移概率，画出各状态间的传递图 设 马 氏 链 的 状 态 空 间 为 I = 1， 2， 3， 4， 5 00010 00001 00100 002/102/1 02/1002/11P 34 111/2 1/21/2 31 1/2图4-24 52 1 闭集，由图可知 状态3为吸收态且 故 1C= 3为闭集2C =1,4 3C =1,3,4闭集， 闭集，其中 是不可约的。1C ， 2C又因状态空间I有闭子集，故此链为非不可约链。 35 3常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注 若 1iif 若 1iif“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过” 或“非常返”定理4 若 1iif ，则系统以概率 1无穷次返回 i； 若 1iif ，则系统以概率 1 只有有穷次返回 i。 定理5 i是常返态的充要条件是 0 )(n niip定理6 如果i为常返态，且 ，则j也是常返态。ji定理7 所有常返态构成一个闭集 36 5正常返态与零常返态平均返回时间 从状态i出发，首次返回状态i的平均时间称为状态i平均返回时间.根据的值是有限或无限，可把常返态分为两类：设i是常返态，则称i为正常返态； )(11 niiniiniii nfnTnPTE 若 i 若 i ， 则称i为零常返态。 37 例 其一步转移矩阵如下，是对I进行分解。0 .1 0 .1 0 .2 0 .2 0 .4 0 00 0 0 .5 0 .5 0 0 00 0 0 1 0 0 00 1 0 0 0 0 00 0 0 0 0 .5 0 .5 00 0 0 0 0 .5 0 0 .50 0 0 0 0 0 .5 0 .5P I可分解为：C 1=2，3, 4 C2=5，6,7 两个闭集及N=1 ，即I=N+ C1+ C2 1 20 0.5 0.5 0.5 0 0.50 0 1 P= 0.5 0.5 01 0 0 0 0.5 0.5P 38 用极限判断状态类型的准则（2）i是零常返态（3）i是正常返态 0lim )( niin p（1）i是瞬时态 )(0 niin p（这时 0lim )( niin p ） )(0 niin p且 )(0 niin p且 0lim )( niin p首页 39 例3 转移矩阵4,3,2,1I 0001 1000 0100 41414141P试对其状态分类。解 按一步转移概率，画出各状态间的传递图 2 1/41 11/4 1/4 11/41 43 40 从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。考虑状态1是否常返，需要计算 11f ：41)1(11 f (2)11 14 41 14f p p 41413413)3(11 pppf 4141342312)4(11 ppppf )(11111 nn ff 141414141 于是状态1是常返的。 25)(1111 nn fn又因为所以状态1是正常返的。此链所有状态都是正常返的。 2 1/41 11/4 1/4 11/41 43 41 三、状态的周期与遍历1周期状态对于任意的 ，令其中GCD表示最大公约数Ii 01 )( niii pnGCDd ： 如果 1id ， 则称 为周期态，i id 为周期 如果 1id 则称 为非周期态。i定理11 设马氏链的状态空间为 I， Iji , （1）若 ji ，则 ji dd ； （2）若是不可约马氏链，且 0iip ，则此马氏链是非周期链。2遍历状态 若状态i是正常返且非周期，则称i为遍历状态。 若马氏链 nX 的所有状态都是遍历的， 111/2 1/21/2 31 1/2图4-24 52 1 42 例4 设马氏链的状态空间I = 0,1,2,，转移概率为试讨论各状态的遍历性。解 根据转移概率作出状态传递图2100 p ， 211, iip ， 210 ip ， Ii1/2 1/2 1/21/2 1/21/20 1 21/2 图4-4 31/2 43 从图可知，对任一状态 都有 ，故由定理可知，I 中的所以状态都是相通的，Ii 0i因此只需考虑状态0是否正常返即可。(1)00 1,2f (2)00 1 1 1,2 2 4f (3) 300 1 1( ) ,2 8f 故 121100 nnf从而0是常返态。又因为 ( )0 001 1 1 22n nn nnf n 所以状态0为正常返。 又由于021)1(00 p 故状态0为非周期的从而状态0是遍历的。 故所有状态i都是遍历的。 1/2 1/2 1/21/2 1/21/20 1 21/2 图4-4 31/2 44 1/3 1/211/3 1/211/31 2 34例5设马氏链的状态空间I=1，2，3，4，其一步转移矩阵为解 试对其状态分类。 0010 021210 0001 31313101P 按一步转移概率，画出各状态间的传递图它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。可继续讨论是否为正常返态 45 可讨论状态10)1(11 f 31)2(11 f 21213131)3(11 f 1211212131)4( 11 f ( )11 11 21 1 1 1 1 13 2 12 2 12 2 12nnf f 122 1121212131)5(11 f 122 112121212131 2)6(11 f 1 1/3 1/211/3 1/211/31 2 34 46 状态1是常返态)(1111 nn fn 21 1 1 1 12 3 4 5 63 2 12 2 12 2 12 状态1是正常返态所以，全部状态都是正常返态 1/3 1/211/3 1/211/31 2 34 47 例1 其一步转移矩阵为试证此链具有遍历性，并求平稳分布和各状态的平均返回时间 32310 32031 032311P解 由于 212 )(PP 329291 949491 949231 48 所以因此，该马氏链具有遍历性。解得1 1 22 1 3 3 2 31 2 31 13 32 13 32 23 3 1 所以马氏链的平稳分布为 Xi 1 2 371 72 74各状态的平均返回时间 49 例2 设有6个球（其中2个红球，4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以 表示开始时甲盒中红球的个数， （ ）表示经n次交换后甲盒中的红球数。( 1 ) 求马氏链 ， 的转移概率矩阵；0XnX 1nnX 1n( 2 ) 证明 ， 是遍历的； nX 1n（3）求 )(lim nijn p 2,1,0, ji（4）求lim ( )jn p n 2,1,0j 50 解 其一步转移矩阵为 31320 929592 032311P甲 乙红球0白球3 红球2白球1红球1白球2 红球1白球2红球2 白球1 红球0白球3 1/32/95/9 2/32/91/30 1 22/3 51 由状态传递图 1/32/95/9 2/32/91/30 1 22/3（2）由于它是一个有限马氏链，故必有一个常返态，又链中三个状态0、1、2都相通，所以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个状态都是正常返的。所以此链为非周期的。 故此链是不可约非周期的正常返链，即此链是遍历的。 52 也可以利用定理1证明遍历性 2212 31320 929592 03231 PP 53 解之得 0 0 11 0 1 22 1 20 1 2j 1 23 92 5 23 9 32 19 3 10,( 0,1,2)j 故得 ( )0lim nin p 0 15 ( )1lim nin p 1 35 54 （4） 0 15 1 35 0lim ( )n p n 1lim ( )n p n 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） 由题意得频数转移矩阵为再用频数估计概率，得转移概率矩阵为 7043264 6422432 9648336N 88.004.008.0 2.07.01.0 2.01.07.0 1P（2）以1600除以N中各行元素之和，得初始概率分布（即初始市场占有率） )5.02.03.0(),()0( 321 pppP 57 所以9月份市场占有率分布为（3）12月份市场占有率分布为1)0()1( PPP )5.02.03.0( 88.004.008.0 2.07.01.0 2.01.07.0)54.019.027.0( 41)0()4( PPP )5.02.03.0( 488.004.008.0 2.07.01.0 2.01.07.0 )5983.01698.02319.0( 58 （4）由于该链不可约、非周期、状态有限正常返的，所以是遍历的。解方程组 1 88.02.02.0 04.07.01.0 08.01.07.0 321 3213 3212 3211 即得当顾客流如此长期稳定下去是市场占有率的分布为)625.0156.0219.0(),( 321 1 2 3( , , ) (1/0.219 1/0.156 1/0.625) （5） 59 例4(书中69页例4.18） 其一步转移矩阵为试并每个不可约闭集的平稳分布0 .1 0 .1 0 .2 0 .2 0 .4 0 00 0 0 .5 0 .5 0 0 00 0 0 1 0 0 00 1 0 0 0 0 00 0 0 0 0 .5 0 .5 00 0 0 0 0 .5 0 0 .50 0 0 0 0 0 .5 0 .5P 60 的平稳分布得状态空间可分解为：C=2，3, 4 D=5，6,7 两个闭集，分别求 转移概率矩阵1 2 3 4 5 6 71 2 3 4 5 6 7 2 1 2( , , , , , , ) (0, , , ,0,0,0)5 5 51 1 1( , , , , , , ) (0,0,0,0, , , ,)3 3 3 1 20 0.5 0.5 0.5 0 0.50 0 1 P= 0.5 0.5 01 0 0 0 0.5 0.5P 61