《2022年马尔科夫链例题整理[考试易考题 .pdf》由会员分享，可在线阅读，更多相关《2022年马尔科夫链例题整理[考试易考题 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2012-8-24 1 若表示质点在时刻 n所处的位置，分析它的概率特性。例1 直线上带吸收壁的随机游动（醉汉游动）设一质点在线段 1，5 上随机游动，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在 2，3，4处，则均以概率向左或向右 移动一单位；（2）若移动前在 1，5处，则以概率 1停留在原处。21质点在 1，5两点被“吸收”1 2 3 4 5 ( )X n前言：马尔可夫过程的描述分类tX(t),例3 电话交换台在 时刻前来到的呼叫数 是无后效性的随机过程. X(t),例 2 直 线上 的 随机 游动 时 的 位 置是 无 后 效 性的 随 机 过 程.首页无记忆性未来处于某状态的
2、概率特性只与现在状态有关，而与以前的状态无关，这种特性叫无记忆性（无后效性）。例4 布朗运动若表示质点在时刻 n所处的位置，求一步转移概率。引例例1 直线上带吸收壁的随机游动（醉汉游动）设一质点在线段 1，5 上随机游动，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在 2，3，4处，则均以概率向左或向右 移动一单位；（2）若移动前在 1，5处，则以概率 1停留在原处。21质点在 1，5两点被“吸收”1 2 3 4 5 ( )X n一步转移概率矩阵的计算首页有两个吸收壁的随机游动其一步转移矩阵为?=10000210210002102100021021000011P状态空间 I=1 ，2，
3、3，4，5，参数集 T=1 ，2，3， ，例2带有反射壁的随机游动设随机游动的状态空间I = 0 ，1，2， ，移动的规则是：（1）若移动前在0处，则下一步以概率p向右移动一个单位，以概率q停留在原处（ p+q=1）；（2）若移动前在其它点处，则均以概率p向右移动一个单位，以概率q向左移动一个单位。设表示在时刻 n质点的位置，则 ， 是一个齐次马氏链，写出其一步转移概率。nXnX0n首页q p 右反射壁m-1 m p q 左反射壁1 2 0 1000.000000.000000.000. . . . . . . . .00000.000000.0qpqpqpPqpqp?=?首页名师资料总结 -
4、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2012-8-24 2 p q 反射壁1 2 3 0 10 0 0 .00 0 .000 . . . . . .q pqpPqp?=?首页例3一个圆周上共有N格（按顺时针排列），一个质点在该圆周上作随机游动，移动的规则是：质点总是以概率 p顺时针游动一格，以概率逆时针游动一格。试求转移概率矩阵。pq-= 11000.000.0000.00.00.000.000pqqpqpPqppq?=?1, 2
5、,.,IN=首页4一个质点在全直线的整数点上作随机游动，移动的规则是：以概率p从i移到 i-1，以概率 q从i移到i+1，以概率 r停留在 i，且，试求转移概率矩阵。1=+qpr1. . . . . . . .000.000. . . . . . . .prqPprq?=?.,2, 1,0,1,2,.E =-首页5设袋中有 a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。若在袋里有k个白球，则称系统处于状态k，试用马尔可夫链描述这个模型（称为爱伦菲斯特模型），并求转移概率矩阵。解这是一个齐次马氏链，其状态空间为 I=0 ，1，2，a 一步转移矩阵是10100.01
6、100.02200.0.110.000.0010aaaaPaaaaa?-?-?=?-?首页练习题扔一颗色子，若前n次扔出的点数的最大值为j，就说试问是否为马氏链？求一步转移概率矩阵。 I=1 ，2，3，4，5，6 首页,nXj=,nXj=111111666666211110666663111006666411000666510.00660.0010P?= ?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 2012-8-24 3
7、 例1 甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是 q，和局的概率是，（）。设每局比赛后，胜者记“+1”分，负者记“ 1” 分，和局不记分。当两人中有一人获得 2分结束比赛。以表示比赛至第 n局时甲获得的分数。r1=+rqpnX（1）写出状态空间；（2）求(2)P；（3）问在甲获得 1分的情况下，再赛二局可以结束比赛的概率是多少？首页解（1）记甲获得“负 2分”为状态 1，获得“负 1分”为状态 2，获得“ 0分”为状态 3，获得“正 1分”为状态 4，获得“正 2分”为状态 5，则状态空间为12345I =， ， ， ，一步转移概率矩阵1000000000000001qrp
8、Pqrpqrp?=?首页（2）二步转移概率矩阵(2)2PP=?+=100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq首页（3）在(2)P中(2)45p是在甲得 1分的情况下经二步转移至得2 分从而结束比赛的概率；( 2)41p是在甲得1 分的情况下经二步转移至2 分（即乙得2 分）从而结束比赛的概率。所以题中所求概率为(2)45p+(2)41p)1 (0)(rprpp+=+=首页分析例2 赌徒输光问题赌徒甲有资本 a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为
9、p，乙获胜的概率为，求甲输光的概率。pq-= 1这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢 1元）的概率为 p，向左移（即输1元）的概率为 q。如果一旦到达0（即甲输光）或a + b（即乙输光）这个游动就停止。这时的状态空间为0 ，1，2，c，c = a + b，。现在的问题是求质点从a出发到达 0状态先于到达 c状态的概率。首页考虑质点从 j出发移动一步后的情况解设cj 0设ju为质点从j 出发到达0 状态先于到达c 状态的概率。在以概率p 移到1+j的假设下，到达 0 状态先于到达 c 状态的概率为1+ju同理以 概 率q 移 到1
10、-j的 前 提 下 ，到达 0状态先于到达c 状态的概率为1-ju根据全概率公式有qupuujjj11-+=这一方程实质上是一差分方程，它的边界条件是0, 10=cuu首页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 2012-8-24 4 于是设（p + q）11-+=jjjqupuu)(11jjjjuupquu-=-+pqr =1+-=jjjuud则可得到两个相邻差分间的递推关系1-=jjrdd于是2120jjjjdrd
11、r dr d-=L欲求au先求ju需讨论r首页当而1rcuu -=01)(110+-=-=jjcjuujcjd-=10010drjcj-=011drrc-=cjjuuu-=)(11+-=-=iicjiuu011drdicjiicji-=-=10(1)jcjrrrd-=+L01drrrcj-=两式相比ccjjrrru-=1首页故ccaarrru-=1?-?-=ccapqpqpq)(1)()(当1=r001cduuc=-而0)(djcuj-=因此cjcuj-=故cbcacua=-=首页用同样的方法可以求得乙先输光的概率由以上计算结果可知当1r即qp 时，甲先输光的概率为?-?-ccapqpqpq)
12、(1)()(当1=r即qp =时，甲先输光的概率为cb当qp 时，乙输光的概率为?-?-capqpq)(1)(1当qp =时，乙先输光的概率为ca首页例3 排队问题顾客到服务台排队等候服务，在每一个服务周期中只要服务台前有顾客在等待，就要对排在前面的一位提供服务，若服务台前无顾客时就不能实施服务。设在第n 个服务周期中到达的顾客数为一随机变量nY且 诸nY独 立 同 分 布 ：)nkP Ykp=（，0,1,2,k =L，1=kkp记nX为服务周期 n 开始时服务台前顾客数则有?=+-=+0,1,11nnnnnnXYXYXX若若此时 nX，1n 为一马氏链，求其转移矩阵在第n周期已有一个顾客在服
13、务，到第n+1周期已服务完毕解先求出转移概率) 0|0(0100=XXPp)0(0=YP0p=)0|1(0101=XXPp) 1(0=YP1p=) 1| 0(110=+nnXXPp) 1|01(=+-=nnnXYXP) 0(=nYP0p=) 1|1(111=+nnXXPp) 1|11(=+-=nnnXYXP) 1(=nYP1p=) 2|0(120=+nnXXPp) 2|01(=+-=nnnXYXP) 1(-=nYP0=) 2| 1(121=+nnXXPp)2|11(=+-=nnnXYXP) 0(=nYP0p=) 2|2(122=+nnXXPp) 1(=nYP1p=首页名师资料总结 - - -精
14、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 2012-8-24 5 所以转移矩阵为012340123410123012000ppppppppppPppppppp?=?LLLLLLLLLL首页证jXPn=0I,niP Xj Xi=00I |niP Xi P XjXi=( )iInijip p=0,niP XjXi=U(n)(n)1212(1)(1)(1)(1)11i1111221EI=1,2,32P,P,P, P551,PX=1=piinPppppp
15、=+设 马 氏 链 的 状 态 空 间初 始 分 布 为试 对 n=1,2,3, 计算解 ：例 2定理4.3 马尔科夫链的有限维分布：11 2m-1 m1122mm012012X,X,X1),0,0.10.20.70.90.100.10.80.10.30.40.3X0,X1,X22iiii iiiiIPiiip pppnPpppp=?=?=LLn由全概率公式得到证明，它是公式（的推广。考虑状态 0，1，2上的一个马氏链X它又转移概率矩阵初始分布为，试求概率（1）3：（例）234X0,X2,X1p=? 练习：马氏链的状态空间I=1，2，3，初始概率为12312122213044111111,42
16、433313044(1)PX (0)=1,X(1)=2,X(2)=2,p(2)(2)PX (1)=2,X(2)=2X (0)=1=p(3)PX (1)=1,X (2)=2,X(3)=3pppPp?=?计 算证 明 ：求例4 市场占有率预测设某地有 1600户居民，某产品只有甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为 480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有32户转买甲产品，有64户转买丙产品；原买丙的有64户转买甲产品，有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂，试求（1）转移概率矩阵；（2）9月份
17、市场占有率的分布；（3）12月份市场占有率的分布；解（1）E1 ，2，3,状态1、2、3分别表示甲、乙、丙的用户一步转移概率矩阵为480489648960.7, 0.1, 0.2480480480323203264640.1, 0.7,0.2320320320643280064320.08, 0.04,0.88800800800-=-=111213212223313233PPPPPPPPP?=88.004. 008. 02.07.01 .02.01. 07. 01P（2）以 1600除8月份甲，乙，丙的户数，得初始概率分布（即初始市场占有率）(0)(0)(0)123(0)(,)(0.3 0.2
18、0.5)Pppp=名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 2012-8-24 6 所以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 . 0
19、2 . 01. 07 . 0?)5983.01698.02319.0(=例1 其一步转移矩阵为试研究各状态间的关系，并画出状态传递图。设马氏链0,nXn的状态空间I=0 ，1，2?=32310414121021211P解先按一步转移概率，画出各状态间的传递图首页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 中没有其它闭
20、集所以此马氏链是不可约的。首页例2 其一步转移矩阵为试讨论哪些状态是吸收态、闭集及不可约链。解先按一步转移概率，画出各状态间的传递图设 马 氏 链 的 状 态 空 间 为I = 1， 2 ， 3， 4， 5 ?=000100000100100002/102/102/1002/11P首页1 1 1/2 1/2 1/2 3 1 1/2 图4-2 4 5 2 1 闭集，由图可知状态3为吸收态且故1C= 3为闭集2C=1,43C=1,3,4闭集，闭集，4C=1,2,3,4 其中是不可约的。1C，2C又因状态空间 I有闭子集，故此链为非不可约链。首页3常返态与瞬时态则称状态 i为常返态则称状态 i为瞬时
21、态注若1=iif若1iif“ 常返”一词，有时又称“返回”、“常驻”或“持久”“ 瞬时”也称“滑过”或“非常返”定理 4 若1=iif，则系统以概率1 无穷次返回i；若1iif，则系统以概率1 只有有穷次返回i 。定理5 i是常返 态的充要条 件是=0)(nniip定理 6如果 i为常返态，且，则j也是常返态。ji ?定理 7 所有常返态构成一个闭集名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 2012-8-24 7 5正常
22、返态与零常返态平均返回时间从状态 i出发，首次返回状态i的平均时间称为状态 i平均返回时间 . 根据的值是有限或无限，可把常返态分为两类：设i是常返态，则称 i为正常返态；)(11niiniiniiinfnTnPTE=若i若=i，则称i为零常返态。首页例其一步转移矩阵如下，是对I进行分解。设马氏链0,nXn的状态空间 I=1，2，3, ,7 0 .10 .10 .20 .20 . 400000 .50 . 50000001000010000000000 .50 . 5000000 .500 .5000000 .50 .5P?=?I可分解为： C1=2，3, 4 C2=5，6,7 两个闭集及N=
23、1 ，即 I=N+ C1+ C2 120 0.5 0.50.500.5001 P = 0.5 0.5010000.5 0.5P?=?用极限判断状态类型的准则（2）i是零常返态（3）i是正常返态0lim)(=niinp（1）i是瞬时态?=)(0niinp（这时0lim)(=niinp）?=)(0niinp且?=)(0niinp且0lim)(niinp首页例3 转移矩阵已知马氏链 ,0,1,2,nXn =L的状态空间 4,3 , 2, 1=I?=00011000010041414141P试对其状态分类。解按一步转移概率，画出各状态间的传递图2 1/4 1 1 1/4 1/4 1 1/4 1 4 3
24、 首页从图可知，此链的每一状态都可到达另一状态，即4个状态都是相通的。考虑状态 1是否常返，需要计算11f：41)1(11=f(2)11144114fpp=?=41413413)3(11=?=pppf4141342312)4(11=ppppf0)(11=nf（5,6,n=L）)(11111nnff=141414141=+=于是状态 1是常返的。=niiipnGCDd：如果1id，则称为周期态，iid为周期如果1=id则称为非周期态。i定理 11 设马氏链的状态空间为I ，Iji,（1）若ji ?，则jidd =；（2）若是不可约马氏链，且0iip，则此马氏链是非周期链。2遍历状态若状态 i是正
25、常返且非周期，则称i为遍历状态。若马氏链 nX 的所有状态都是遍历的，则称nX为遍历链1 1 1/2 1/2 1/2 3 1 1/2 图4-2 4 5 2 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 2012-8-24 8 例4 设马氏链的状态空间I = 0,1,2,，转移概率为试讨论各状态的遍历性。解根据转移概率作出状态传递图2100=p，211,=+iip，210=ip，Ii 1/2 1/2 1/2 1/2 1/2
26、 1/2 0 1 2 1/2 图4-4 3 1/2 首页从图可知，对任一状态都有，故由定理可知，I 中的所以状态都是相通的，Ii 0?i因此只需考虑状态0是否正常返即可。(1)001,2f=(2)001 11,2 24f=? =(3)30011( ),28f= 故121100=nnf从而 0是常返态。又因为( )00011122nnnnnfn=?=p故状态 0为非周期的从而状态 0是遍历的。故所有状态 i都是遍历的。 1/2 1/2 1/2 1/2 1/21/2 0 1 2 1/2 图4-4 3 1/2 1/3 1/2 1 1/3 1/2 1 1/3 1 2 3 4 例5设马氏链的状态空间I=
27、1 ，2，3，4 ，其一步转移矩阵为解试对其状态分类。?=0010021210000131313101P按一步转移概率，画出各状态间的传递图它是有限状态的马氏链，故必有一个常返态，又链中四个状态都是互通的。因此，所有状态都是常返态，这是一个有限状态不可约的马氏链。可继续讨论是否为正常返态可讨论状态 1 0)1(11=f31)2(11=f21213131)3(11=?+=f1211212131)4(11=?=f( )1111211111132122 12212nnff=+?L1221121212131)5(11?=?=f1221121212121312)6(11?=?=f1=1/3 1/2 1
28、1/3 1/2 1 1/3 1 2 3 4 状态 1是常返态)(1111nnfn=ijp。1122133231231133213322331?=+?=+?=+?+=?1122331/7,1/3.5,1/7 / 4=所以马氏链的平稳分布为X i1 2 3 717274各状态的平均返回时间例2 设有6个球（其中 2个红球， 4个白球）分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进行交换，以表示开始时甲盒中红球的个数，（）表示经 n次交换后甲盒中的红球数。( 1 ) 求马氏链 ， 的转移概率矩阵；0XnX1nnX1n( 2 ) 证明 ， 是遍历的；nX1n（3）求)(limnij
29、np2, 1 ,0,=ji（4）求lim( )jnpn2, 1 ,0=j首页解其一步转移矩阵为（1）因nX表红球数，所以状态空间E = 0,1,2 ?=31320929592032311P甲乙红球 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 由状态传递图1/3 2/9 5/9 2/3 2/9 1/3 0 1 2 2/3 （2）由于它是一个有限马氏链，故必有一个常返态，又链中三个状态 0、1、2都相通，所以每个状态都是常返态。所以是一个不可约的有限马氏链，从而每个
30、状态都是正常返的。所以此链为非周期的。故此链是不可约非周期的正常返链，即此链是遍历的。又由03100=p首页也可以利用定理1证明遍历性（3）由于()jlimnijnp=（2, 1 ,0=j） ，所以先求平稳分布j22123132092959203231?=PP首页解之得0011012212012j1239252393219310, (0,1, 2)j?=+?=+?=+?+=?=?015=，135=，215=故得()0limninp=015=()1limninp=135=首页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心
31、整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 2012-8-24 10 （4）015=135=()2limninp=215=0lim( )npn=1lim( )np n=2lim( )npn=215=首页例3 市场占有率预测设某地有 1600户居民，某产品只有甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为 480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有32户转买甲产品，有 64户转买丙产品；原买丙的有64户转买甲产品，有 32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三
32、厂，试求（1）转移概率矩阵；（2）9月份市场占有率的分布；（3）12月份市场占有率的分布；（4）当顾客流如此长期稳定下去市场占有率的分布。（5）各状态的平均返回时间首页解（1） 由题意得频数转移矩阵为再用频数估计概率，得转移概率矩阵为?=704326464224329648336N?=88.004.008.02 .07 .01 .02 .01.07.01P（2）以 1600除以N中各行元素之和，得初始概率分布（即初始市场占有率）)5.02.03.0(),()0(321=pppP首页所以 9月份市场占有率分布为（3）12月份市场占有率分布为1)0()1(PPP=) 5. 02.03 .0(=?8
33、8. 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 . 07. 0?)5983.01698.02319.0(=首页（4）由于该链不可约、非周期、状态有限正常返的，所以是遍历的。解方程组?=+=+=+=188.02.02.004.07 .01 .008.01.07.0321321332123211即得当顾客流如此长期稳定下去是市场占有率的分布为)625.0156.0219. 0(),(321=123(,)(1
34、/ 0.219 1/ 0.156 1/ 0.625) =（5）例4 (书中69页例4.18）其一步转移矩阵为试并每个不可约闭集的平稳分布设马氏链0,nXn的状态空间 I=1，2，3, ,7 0 .10 .10 .20 .20 . 400000 .50 . 50000001000010000000000 .50 . 5000000 .500 .5000000 .50 .5P?=?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 2012-8-24 11 的平稳分布得状态空间可分解为：C=2 ，3, 4 D=5 ，6,7 两个闭集，分别求对应转移概率矩阵12345671234567212(,)(0,0,0,0)555111(,)(0,0,0,0,)333 =120 0.5 0.50.500.5001 P = 0.5 0.5 010000.5 0.5P?=?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -