马尔科夫链例题整理PPT课件

1、tX(t),例3 电话交换台在 时刻前来到的呼叫数 是无后效性的随机过程. X(t),例2 直线上的随机游动时的位置是 无后效性的随机过程.首页无记忆性未来处于某状态的概率特性只与现在状态有关，而与以前的状态无关，这种特性叫无记忆性（无后效性）。例4 布朗运动第1页/共61页若 表示质点在时刻n所处的位置，求一步转移概率。引例 例1 直线上带吸收壁的随机游动（醉汉游动）设一质点在线段1，5 上随机游动，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在2，3，4处，则均以概率 向左或向右 移动一单位；（2）若移动前在1，5处，则以概率1停留在原处。21质点在1，5两点被“吸收”12345(

2、 )X n一步转移概率矩阵的计算第2页/共61页首页有两个吸收壁的随机游动其一步转移矩阵为10000210210002102100021021000011P状态空间I=1，2，3，4，5，参数集T=1，2，3，第3页/共61页例2带有反射壁的随机游动设随机游动的状态空间I = 0，1，2，移动的规则是： （1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（p+q=1）； （2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设 表示在时刻n质点的位置， 则 ， 是一个齐次马氏链，写出其一步转移概率。nXnX0n首页第4页/共61页qp右反射壁

3、m-1mpq左反射壁1201000.000000.000000.000. . . . . . . . .00000.000000.0qpqpqpPqpqp首页第5页/共61页pq反射壁123010 0 0 .00 0 .000 . . . . . .q pqpPqp首页第6页/共61页例3一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率矩阵。pq 11000.000.0000.00.00.000.000pqqpqpPqppq1,2,.,IN首页第7页/共61页4一个质点在全直线的整数点上作随机

4、游动，移动的规则是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r停留在i，且 ，试求转移概率矩阵。1qpr1. . . . . . . . 000 . 000 . . . . . . . .prqPprq., 2, 1,0,1,2,.E 首页第8页/共61页5设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。解 这是一个齐次马氏链，其状态空间为 I=0，1，2，a一步转移矩阵是10100.01100.02200.0.110.000.0010

5、aaaaPaaaaa首页第9页/共61页练习题扔一颗色子，若前n次扔出的点数的最大值为j，就说 试问 是否为马氏链？求一步转移概率矩阵。 I=1，2，3，4，5，6首页,nXj,nXj第10页/共61页111111666666211110666663111006666411000666510.00660.0010P 第11页/共61页例1甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是q，和局的概率是 ，（ ）。设每局比赛后，胜者记“+1”分，负者记“1”分，和局不记分。当两人中有一人获得2分结束比赛。以 表示比赛至第n局时甲获得的分数。r1rqpnX（1）写出状态空间；（3）问在

6、甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？首页第12页/共61页解（1） 记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为12345I ， ， ， ，一步转移概率矩阵1000000000000001qrpPqrpqrp首页第13页/共61页（2）二步转移概率矩阵(2)2PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq首页第14页/共61页（3）从而结束比赛的概率；从而结束比赛的概率。所以题中所求概率为)1 (0)(rprpp首页第15页/共

7、61页分析例2 赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为 ，求甲输光的概率。pq1这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a + b（即乙输光）这个游动就停止。这时的状态空间为0，1，2，c，c = a + b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。首页第16页/共61页考虑质点从j出发移动一步后的情况解设cj

8、 0设ju为质点从 j 出发到达 0 状态先于到达 c 状态的概率。在以概率 p 移到1j的假设下，到达 0 状态先于到达 c 状态的概率为1ju同理以 概 率 q 移 到1j的 前 提 下 ，到达0状态先于到达c状态的概率为1ju根据全概率公式有qupuujjj11这一方程实质上是一差分方程，它的边界条件是0, 10cuu首页第17页/共61页于是设（p + q）11jjjqupuu)(11jjjjuupquupqr 1jjjuud则可得到两个相邻差分间的递推关系1jjrdd于是2120jjjjdrdr dr dL欲求au先求ju需讨论 r首页第18页/共61页当而1rcuu 01)(110

9、jjcjuujcjd10010drjcj011drrccjjuuu)(11iicjiuu011drdicjiicji10(1)jcjrrrd L01drrrcj两式相比ccjjrrru1首页第19页/共61页故ccaarrru1ccapqpqpq)(1)()(当1r001cduuc而0)(djcuj因此cjcuj故cbcacua首页第20页/共61页用同样的方法可以求得乙先输光的概率由以上计算结果可知当1r即qp 时，甲先输光的概率为ccapqpqpq)(1)()(当1r即qp 时，甲先输光的概率为cb当qp 时，乙输光的概率为capqpq)(1)(1当qp 时，乙先输光的概率为ca首页第21

10、页/共61页例3 排队问题顾客到服务台排队等候服务，在每一个服务周期中只要服务台前有顾客在等待，就要对排在前面的一位提供服务，若服务台前无顾客时就不能实施服务。设在第 n 个服务周期中到达的顾客数为一随机变量nY且诸nY独立同分布：1kkp记nX为服务周期 n 开始时服务台前顾客数则有0,1,11nnnnnnXYXYXX若若此时nX，1n 为一马氏链，求其转移矩阵在第n周期已有一个顾客在服务，到第n+1周期已服务完毕第22页/共61页解先求出转移概率) 0| 0(0100XXPp) 0(0YP0p) 0| 1(0101XXPp) 1(0YP1p) 1| 0(110nnXXPp) 1| 01(n

11、nnXYXP) 0(nYP0p) 1| 1(111nnXXPp) 1| 11(nnnXYXP) 1(nYP1p) 2| 0(120nnXXPp) 2| 01(nnnXYXP) 1(nYP0) 2| 1(121nnXXPp) 2| 11(nnnXYXP) 0(nYP0p) 2| 2(122nnXXPp) 1(nYP1p首页第23页/共61页所以转移矩阵为012340123410123012000ppppppppppPpppppppLLLLLLLLLL首页第24页/共61页证jXPn0I,niP Xj Xi00I |niP Xi P Xj Xi( )iInijip p0,niP XjXiU(n)(

12、n)1212(1)(1)(1)(1)11i1111221E I=1,2,32 P, P,P, P551,PX =1= piinPpppp p设 马 氏 链 的 状 态 空 间初 始 分 布 为试 对 n=1,2,3,计 算 解 ：例 2第25页/共61页定理4.3 马尔科夫链的有限维分布： 11 2m-1 m1122mm012012X,X,X1),0,0.10.20.70.90.100.10.80.10.30.40.3X0,X1,X2 2iiii iiii IPiiip p ppnPppppLLn由全概率公式得到证明，它是公式（ 的推广。考虑状态0，1，2上的一个马氏链X它又转移概率矩阵初始分

13、布为，试求概率（1）3：（例）234X0,X2,X1p第26页/共61页 练习：马氏链的状态空间I=1，2，3，初始概率为12312122213044111111,42433313044(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)=3pppPp计算证明：求第27页/共61页例4市场占有率预测设某地有1600户居民，某产品只有甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有3

14、2户转买甲产品，有64户转买丙产品；原买丙的有64户转买甲产品，有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂，试求（1）转移概率矩阵；（2）9月份市场占有率的分布；（3）12月份市场占有率的分布；第28页/共61页解（1）E1，2，3,状态1、2、3分别表示甲、乙、丙的用户一步转移概率矩阵为480489648960.7, 0.1, 0.2480480480323203264640.1, 0.7, 0.2320320320643280064320.08, 0.04, 0.88800800800111213212223313233PPPPPPPPP88. 004. 008. 02 .

15、 07 . 01 . 02 . 01 . 07 . 01P（2）以1600除8月份甲，乙，丙的户数，得初始概率分布（即初始市场占有率）(0)(0)(0)123(0)(,)(0.3 0.2 0.5)Pppp第29页/共61页所以9月份市场占有率分布为（3）12月份市场占有率分布为1)0() 1 (PPP)5 . 02 . 03 . 0(88. 004. 008. 02 . 07 . 01 . 02 . 01 . 07 . 0)54. 019. 027. 0(41)0()4(PPP) 5 . 02 . 03 . 0 (488. 004. 008. 02 . 07 . 01 . 02 . 01 .

16、07 . 0)5983. 01698. 02319. 0(第30页/共61页例1其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。设马氏链0,nXn的状态空间 I=0，1，232310414121021211P解先按一步转移概率，画出各状态间的传递图首页第31页/共61页2/31/41/41/31/21/20121/2图3-1由图可知状态0可到达状态1，经过状态1又可到达状态2；反之，从状态2出发经状态1也可到达状态0。因此，状态空间I的各状态都是互通的。又由于I 的任意状态i (i = 0，1，2)不能到达I 以外的任何状态， 所以I是一个闭集而且I 中没有其它闭集所以此马氏链是不可约

17、的。首页第32页/共61页例2其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。解先按一步转移概率，画出各状态间的传递图设 马 氏 链 的 状 态 空 间 为 I = 1， 2， 3， 4， 5000100000100100002/102/102/1002/11P首页第33页/共61页111/21/21/2311/2图4-24521 闭集，由图可知状态3为吸收态且故 1C= 3为闭 集2C=1,43C=1,3,4闭集，闭集，其中 是不可约的。1C，2C又因状态空间I有闭子集，故此链为非不可约链。首页第34页/共61页3常返态与瞬时态则称状态i为常返态则称状态i为瞬时态注若1iif若1ii

18、f“常返”一词，有时又称“返回”、“常驻”或“持久”“瞬时”也称“滑过” 或“非常返”定理4若1iif，则系统以概率 1 无穷次返回 i；若1iif，则系统以概率 1 只有有穷次返回 i。 定理5i是 常 返 态 的 充 要 条 件 是0)(nniip定理6如果i为常返态，且 ，则j也是常返态。ji 定理7所有常返态构成一个闭集第35页/共61页5正常返态与零常返态平均返回时间 从状态i出发，首次返回状态i的平均时间称为状态i平均返回时间.根据的值是有限或无限，可把常返态分为两类：设i是常返态，则称i为正常返态；)(11niiniiniiinfnTnPTE若i若i，则称i为零常返态。首页第36

19、页/共61页例其一步转移矩阵如下，是对I进行分解。0 .10 .10 .20 .20 .40 00 0 0 .50 .50 0 00 0 0 1 0 0 00 1 0 0 0 0 00 0 0 00 .50 .500 0 0 00 .500 .50 0 0 000 .50 .5PI可分解为：C1=2，3, 4 C2=5，6,7 两个闭集及N=1 ，即I=N+ C1+ C2120 0.5 0.50.500.5001 P= 0.5 0.5010000.5 0.5P第37页/共61页用极限判断状态类型的准则（2）i是零常返态（3）i是正常返态0lim)(niinp（1）i是瞬时态)(0niinp（这

20、时0lim)(niinp）)(0niinp且)(0niinp且0lim)(niinp首页第38页/共61页例3转移矩阵4 , 3 , 2 , 1I00011000010041414141P试对其状态分类。解按一步转移概率，画出各状态间的传递图21/4111/41/411/4143首页第39页/共61页从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。考虑状态1是否常返，需要计算11f：41)1(11f(2)11144114fpp41413413)3(11pppf4141342312)4(11ppppf)(11111nnff141414141于是状态1是常返的。25)(1111nn

21、fn又因为所以状态1是正常返的。此链所有状态都是正常返的。21/4111/41/411/4143第40页/共61页三、状态的周期与遍历1周期状态对于任意的 ，令其中GCD表示最大公约数Ii01)(niiipnGCDd：如果1id，则称 为周期态，iid为周期如果1id则称 为非周期态。i定理11设马氏链的状态空间为 I，Iji,（1）若ji ，则jidd ；（2）若是不可约马氏链，且0iip，则此马氏链是非周期链。2遍历状态若状态i是正常返且非周期，则称i为遍历状态。若马氏链nX的所有状态都是遍历的，111/21/21/2311/2图4-24521第41页/共61页例4设马氏链的状态空间I =

22、 0,1,2,，转移概率为试讨论各状态的遍历性。解根据转移概率作出状态传递图2100p，211,iip，210ip，Ii1/21/21/21/21/21/20121/2图4-431/2首页第42页/共61页从图可知，对任一状态 都有 ，故由定理可知，I 中的所以状态都是相通的，Ii0i因此只需考虑状态0是否正常返即可。(1)001,2f(2)001 11,2 24f (3)30011( ),28f故121100nnf从而0是常返态。又因为( )00011122nnnnnfn 所以状态0为正常返。又由于021) 1 (00p故状态0为非周期的从而状态0是遍历的。故所有状态i都是遍历的。1/21/

23、21/21/21/21/20121/2 图4-431/2第43页/共61页1/31/211/31/211/31234例5设马氏链的状态空间I=1，2，3，4，其一步转移矩阵为解 试对其状态分类。0010021210000131313101P按一步转移概率，画出各状态间的传递图它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。可继续讨论是否为正常返态第44页/共61页可讨论状态10)1(11f31)2(11f21213131)3(11f1211212131)4(11f( )1111211111132122 12212nnf

24、fL1221121212131)5(11f1221121212121312)6(11f11/31/211/31/211/31234第45页/共61页状态1是常返态)(1111nnfn2111112345632122 122 12 L状态1是正常返态所以，全部状态都是正常返态首页1/31/211/31/211/31234第46页/共61页例1其一步转移矩阵为试证此链具有遍历性，并求平稳分布和各状态的平均返回时间3231032031032311P解由于212)(PP329291949491949231首页第47页/共61页所以因此，该马氏链具有遍历性。解得112213323123113321332

25、2331所以马氏链的平稳分布为Xi123717274各状态的平均返回时间第48页/共61页例2设有6个球（其中2个红球，4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以 表示开始时甲盒中红球的个数， （ ）表示经n次交换后甲盒中的红球数。( 1 ) 求马氏链 ， 的转移概率矩阵；0XnX1nnX1n( 2 ) 证明 ， 是遍历的；nX1n（3）求)(limnijnp2 , 1 , 0,ji（4）求lim( )jnp n2 , 1 , 0j首页第49页/共61页解其一步转移矩阵为31320929592032311P甲乙红球0白球3红球2白球1红球1白球2红球

26、1白球2红球2白球1红球0白球31/32/95/92/32/91/30122/3第50页/共61页由状态传递图1/32/95/92/32/91/30122/3（2）由于它是一个有限马氏链，故必有一个常返态，又链中三个状态0、1、2都相通，所以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个状态都是正常返的。所以此链为非周期的。故此链是不可约非周期的正常返链，即此链是遍历的。首页第51页/共61页也可以利用定理1证明遍历性22123132092959203231 PP首页第52页/共61页解之得0011012212012j1239252393219310,(0,1,2)j故得( )0l

27、imninp015( )1limninp135首页第53页/共61页（4）0151350lim( )np n1lim( )np n首页第54页/共61页例3市场占有率预测设某地有1600户居民，某产品只有甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有32户转买甲产品，有64户转买丙产品；原买丙的有64户转买甲产品，有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂，试求（1）转移概率矩阵；（2）9月份市场占有率的分布；（3）12月份市场占有率的分布；（4）当顾客流如此长期稳定下去市场占有率的分布。（5）各状态的平均返回时间首页第55页/共61页解（1） 由题意得频数转移矩阵为再用频数估计