[工学]马尔科夫链例题整理ppt课件

1、假设 表示质点在时辰n所处的位置，分析它的概率特性。例例1 直线上带吸收壁的随机游动醉汉游动直线上带吸收壁的随机游动醉汉游动设一质点在线段设一质点在线段1，5 上随机游动，每秒钟发生上随机游动，每秒钟发生一次随机游动，挪动的规那么是：一次随机游动，挪动的规那么是：1假设挪动前在2，3，4处，那么均以概率 向左或向右 挪动一单位；2假设挪动前在1，5处，那么以概率1停留在原处。21质点在1，5两点被“吸收12345( )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两点被“吸收12345( )X n一步转移

3、概率矩阵的计算有两个吸收壁的随机游动有两个吸收壁的随机游动其一步转移矩阵为10000210210002102100021021000011P外形空间外形空间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质点的位置， 那么 ， 是一个齐次马氏链，写出其一步转移概率。nXnX0nqp右反射壁m-1mpq左反

4、射壁1201000.000000.000000.000. . . . . . . . .00000.000000.0qpqpqpPqpqppq反射壁123010 0 0 .00 0 .000 . . . . . .q pqpPqp例3一个圆周上共有N格按顺时针陈列，一个质点在该圆周上作随机游动，挪动的规那么是：质点总是以概率p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率矩阵。pq 11000.000.0000.00.00.000.000pqqpqpPqppq1,2,.,IN4一个质点在全直线的整数点上作随机游动，挪动的规那么是：以概率p从i移到i-1，以概率q从i移到i+1，以概率r

5、停留在i，且 ，试求转移概率矩阵。1qpr1. . . . . . . . 000 . 000 . . . . . . . .prqPprq., 2, 1,0,1,2,.E 5设袋中有a个球，球为黑色的或白色的，今随机地从袋中取一个球，然后放回一个不同颜色的球。假设在袋里有k个白球，那么称系统处于外形k，试用马尔可夫链描画这个模型称为爱伦菲斯特模型，并求转移概率矩阵。解 这是一个齐次马氏链，其外形空间为 I=0，1，2，a一步转移矩阵是10100.01100.02200.0.110.000.0010aaaaPaaaaa练习题扔一颗色子，假设前n次扔出的点数的最大值为j，就说 试问 能否为马氏链

6、？求一步转移概率矩阵。 I=1，2，3，4，5，6,nXj,nXj111111666666211110666663111006666411000666510.00660.0010P 例例1甲、乙两人进展竞赛，设每局竞赛中甲胜的概甲、乙两人进展竞赛，设每局竞赛中甲胜的概率是率是p，乙胜的概率是，乙胜的概率是q，和局的概率是，和局的概率是 ， 。设每局竞赛后，胜者记。设每局竞赛后，胜者记“+1分，负者记分，负者记“1分，和局不记分。当两人中分，和局不记分。当两人中有一人获得有一人获得2分终了竞赛。以分终了竞赛。以 表示竞赛至第表示竞赛至第n局时甲获得的分数。局时甲获得的分数。r1rqpnX1写出外

7、形空间；写出外形空间；3问在甲获得问在甲获得1分的情况下，再赛二局可分的情况下，再赛二局可以终了竞赛的概率是多少？以终了竞赛的概率是多少？解解1 记甲获得“负2分为外形1，获得“负1分为外形2，获得“0分为外形3，获得“正1分为外形4，获得“正2分为外形5，那么外形空间为12345I ， ， ， ，一步转移概率矩阵1000000000000001qrpPqrpqrp2二步转移概率矩阵(2)2PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq3从而终了竞赛的概率；从而终了竞赛的概率。所以题中所求概率为)1 (0)(rprpp分析例例2 赌徒

8、输光问题赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进展赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为 ，求甲输光的概率。pq1这个问题本质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时辰处于a，每次挪动一格，向右移即赢1元的概率为p，向左移即输1元的概率为q。假设一旦到达0即甲输光或a + b即乙输光这个游动就停顿。这时的外形空间为0，1，2，c，c = a + b，。如今的问题是求质点从a出发到达0外形先于到达c外形的概率。思索质点从j出发挪动一步后的情况解解设cj 0设ju为质点从 j 出发到达 0 状态先

9、于到达 c 状态的概率。在以概率 p 移到1j的假设下，到达 0 状态先于到达 c 状态的概率为1ju同理以 概 率q 移 到1j的 前 提 下 ，到达0状态先于到达c状态的概率为1ju根据全概率公式有qupuujjj11这一方程本质上是一差分方程，它的边境条件是0, 10cuu于是设（p + q）11jjjqupuu)(11jjjjuupquupqr 1jjjuud那么可得到两个相邻差分间的递推关系1jjrdd于是2120jjjjdrdr dr dL欲求au先求ju需讨论 r当而1rcuu 01)(110jjcjuujcjd10010drjcj011drrccjjuuu)(11iicjiuu

10、011drdicjiicji10(1)jcjrrrd L01drrrcj两式相比ccjjrrru1故ccaarrru1ccapqpqpq)(1)()(当1r001cduuc而0)(djcuj因此cjcuj故cbcacua用同样的方法可以求得乙先输光的概率由以上计算结果可知当1r即qp 时，甲先输光的概率为ccapqpqpq)(1)()(当1r即qp 时，甲 先 输 光 的 概 率 为cb当qp 时，乙输光的概率为capqpq)(1)(1当qp 时，乙先输光的概率为ca例例3 排队问题排队问题顾客到效能台排队等候效能，在每一个效能周期中只需效能台前有顾客在等待，就要对排在前面的一位提供效能，假设

11、效能台前无顾客时就不能实施效能。设在第 n 个服务周期中到达的顾客数为一随机变量nY且 诸nY独 立 同 分 布 ：1kkp记nX为服务周期 n 开始时服务台前顾客数那么有0,1,11nnnnnnXYXYXX若若此时nX，1n 为一马氏链，求其转移矩阵在第n周期已有一个顾客在效能，到第n+1周期已效能终了解解先求出转移概率) 0| 0(0100XXPp) 0(0YP0p) 0| 1(0101XXPp) 1(0YP1p) 1| 0(110nnXXPp) 1| 01(nnnXYXP) 0(nYP0p) 1| 1(111nnXXPp) 1| 11(nnnXYXP) 1(nYP1p) 2| 0(120

12、nnXXPp) 2| 01(nnnXYXP) 1(nYP0) 2| 1(121nnXXPp) 2| 11(nnnXYXP) 0(nYP0p) 2| 2(122nnXXPp) 1(nYP1p所以转移矩阵为012340123410123012000ppppppppppPpppppppLLLLLLLLLL证jXPn0I,niP Xj Xi00I |niP Xi P Xj Xi( )iInijip p0,niP XjXiU(n)(n)1212(1)(1)(1)(1)11i1111221E I=1,2,32 P, P,P, P551,PX =1= piinPpppp p设 马 氏 链 的 状 态 空 间

13、初 始 分 布 为试 对 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,X2 2iiii iiii IPiiip p ppnPppppLLn由全概率公式得到证明，它是公式（ 的推广。考虑状态0，1，2上的一个马氏链X它又转移概率矩阵初始分布为，试求概率（1）3：（例）234X0,X2,X1p 练习：马氏链的外形空间I=1，2，3，初始概率为12312122213044111111,42433313044(1)PX(0)=1,X

14、(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计算证明：求例例4市场占有率预测市场占有率预测设某地有设某地有1600户居民，某产品只需甲、乙、丙户居民，某产品只需甲、乙、丙3厂厂家在该地销售。经调查，家在该地销售。经调查，8月份买甲、乙、丙三厂月份买甲、乙、丙三厂的户数分别为的户数分别为480，320，800。9月份里，原买甲的月份里，原买甲的有有48户转买乙产品，有户转买乙产品，有96户转买丙产品；原买乙的户转买丙产品；原买乙的有有32户转买甲产品，有户转买甲产品，有64户转买丙产品；原买丙的户

15、转买丙产品；原买丙的有有64户转买甲产品，有户转买甲产品，有32户转买乙产品。用外形户转买乙产品。用外形1、2、3分别表示甲、乙、丙三厂，试求分别表示甲、乙、丙三厂，试求1转移概率矩阵；转移概率矩阵；29月份市场占有率的分布；月份市场占有率的分布；312月份市场占有率的分布；月份市场占有率的分布；解1E1，2，3,外形1、2、3分别表示甲、乙、丙的用户一步转移概率矩阵为480489648960.7, 0.1, 0.2480480480323203264640.1, 0.7, 0.2320320320643280064320.08, 0.04, 0.88800800800111213212223

16、313233PPPPPPPPP88. 004. 008. 02 . 07 . 01 . 02 . 01 . 07 . 01P2以1600除8月份甲，乙，丙的户数，得初始概率分布即初始市场占有率(0)(0)(0)123(0)(,)(0.3 0.2 0.5)Pppp所以9月份市场占有率分布为312月份市场占有率分布为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

17、 . 01 . 02 . 01 . 07 . 0)5983. 01698. 02319. 0(例例1其一步转移矩阵为试研讨各外形间的关系，并画出外形传送图。试研讨各外形间的关系，并画出外形传送图。设马氏链0,nXn的状态空间 I=0，1，232310414121021211P解先按一步转移概率，画出各外形间的传送先按一步转移概率，画出各外形间的传送图图2/31/41/41/31/21/20121/2图3-1由图可知由图可知外形外形0可到达外形可到达外形1，经过外形，经过外形1又可到达外形又可到达外形2；反之，从外形反之，从外形2出发经外形出发经外形1也可到达外形也可到达外形0。因此，外形空间因

18、此，外形空间I的各外形都是互通的。的各外形都是互通的。又由于又由于I 的恣不测形的恣不测形i (i = 0，1，2)不能到达不能到达I 以外的任以外的任何外形，何外形， 所以所以I是一个闭集是一个闭集而且而且I 中没有其它闭集中没有其它闭集所以此马氏链是不可约的。所以此马氏链是不可约的。例例2其一步转移矩阵为试讨论哪些外形是吸收态、闭集及不可约链。试讨论哪些外形是吸收态、闭集及不可约链。解解先按一步转移概率，画出各外形间的传送先按一步转移概率，画出各外形间的传送图图设 马 氏 链 的 状 态 空 间 为 I = 1， 2， 3， 4， 5000100000100100002/102/102/1

19、002/11P111/21/21/2311/2图4-24521 闭集，由图可知外形3为吸收态且故 1C= 3为闭集2C=1,43C=1,3,4闭集，闭集，其中 是不可约的。1C，2C又因外形空间I有闭子集，故此链为非不可约链。3常返态与瞬时态常返态与瞬时态那么称外形i为常返态那么称外形i为瞬时态注注若1iif若1iif“常返一词，有时又称“前往、“常驻或“耐久“瞬时也称“滑过 或“非常返定理定理4若1iif，则系统以概率1无穷次返回i；若1iif，则系统以概率 1 只有有穷次返回 i。 定理定理5i是常返态的充要条件是0)(nniip定理定理6假设i为常返态，且 ，那么j也是常返态。ji 定理

20、定理7一切常返态构成一个闭集5正常返态与零常返态平均前往时间 从外形i出发，初次前往外形i的平均时间称为外形i平均前往时间.根据的值是有限或无限，可把常返态分为两类：设i是常返态，那么称i为正常返态；)(11niiniiniiinfnTnPTE若i若i，那么称i为零常返态。例例其一步转移矩阵如下，是对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 两个闭

21、集及N=1 ，即I=N+ C1+ C2120 0.5 0.50.500.5001 P= 0.5 0.5010000.5 0.5P用极限判别外形类型的准那么用极限判别外形类型的准那么2i是零常返态是零常返态3i是正常返态是正常返态0lim)(niinp1i是瞬时态)(0niinp（这时0lim)(niinp）)(0niinp且)(0niinp且且0lim)(niinp例例3转移矩阵4 , 3 , 2 , 1I00011000010041414141P试对其外形分类。解解按一步转移概率，画出各外形间的传送图21/4111/41/411/4143从图可知，此链的每一外形都可到达另一外形，即4个外形都

22、是相通的。思索外形1能否常返，需要计算11f：41)1(11f(2)11144114fpp41413413)3(11pppf4141342312)4(11ppppf)(11111nnff141414141于是外形1是常返的。25)(1111nnfn又由于所以外形1是正常返的。此链一切外形都是正常返的。此链一切外形都是正常返的。21/4111/41/411/4143三、外形的周期与遍历三、外形的周期与遍历1周期外形对于恣意的 ，令其中GCD表示最大公约数Ii01)(niiipnGCDd：如果1id，那么称 为周期态，iid为周期如 果1id那么称 为非周期态。i定理定理11设马氏链的状态空间为

23、I，Iji,（1）若ji ，则jidd ；（2）若是不可约马氏链，且0iip，则此马氏链是非周期链。2遍历外形假设外形i是正常返且非周期，那么称i为遍历外形。若马氏链nX的所有状态都是遍历的，111/21/21/2311/2图4-24521例例4设马氏链的外形空间I = 0,1,2,，转移概率为试讨论各外形的遍历性。解解根据转移概率作出外形传送图2100p，211,iip，210ip，Ii1/21/21/21/21/21/20121/2图4-431/2从图可知，对任一外形 都有 ，故由定理可知，I 中的所以外形都是相通的，Ii0i因此只需思索外形0能否正常返即可。(1)001,2f(2)001

24、 11,2 24f (3)30011( ),28f故121100nnf从而0是常返态。又由于( )00011122nnnnnfn 所以外形0为正常返。又由于021) 1 (00p故外形0为非周期的从而外形0是遍历的。故一切外形i都是遍历的。1/21/21/21/21/21/20121/2 图4-431/21/31/211/31/211/31234例5设马氏链的外形空间I=1，2，3，4，其一步转移矩阵为解 试对其外形分类。0010021210000131313101P按一步转移概率，画出各外形间的传送图它是有限外形的马氏链，故必有一个常返态，又链中四个外形都是互通的。因此，一切外形都是常返态，

25、这是一个有限外形不可约的马氏链。可继续讨论能否为正常返态可讨论外形10)1(11f31)2(11f21213131)3(11f1211212131)4(11f( )1111211111132122 12212nnffL1221121212131)5(11f1221121212121312)6(11f11/31/211/31/211/31234外形1是常返态)(1111nnfn2111112345632122 122 12 L外形1是正常返态所以，全部外形都是正常返态1/31/211/31/211/31234例例1其一步转移矩阵为试证此链具有遍历性，并求平稳分布和各外形的平均前往时间323103

26、2031032311P解解由于212)(PP329291949491949231所以因此，该马氏链具有遍历性。解得1122133231231133213322331所以马氏链的平稳分布为Xi123717274各外形的平均前往时间各外形的平均前往时间例例2设有6个球其中2个红球，4个白球分放于甲、乙两个盒子中，每盒放3个，今每次从两个盒中各任取一球并进展交换，以 表示开场时甲盒中红球的个数， 表示经n次交换后甲盒中的红球数。( 1 ) 求马氏链 ， 的转移概率矩阵；0XnX1nnX1n( 2 ) 证明 ， 是遍历的；nX1n3求)(limnijnp2 , 1 , 0,ji4求lim( )jnp

27、n2 , 1 , 0j解解其一步转移矩阵为其一步转移矩阵为31320929592032311P甲乙红球红球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/32由于它是一个有限马氏链，故必有一个常返态，又链中三个外形0、1、2都相通，所以每个外形都是常返态。所以是一个不可约的有限马氏链，从而每个外形都是正常返的。所以此链为非周期的。故此链是不可约非周期的正常返链，即此链是遍历的。也可以利用定理1证明遍历性22123132092959203231 PP解之得0011012212012j1239252393219310,(0,1,2)j故得( )0limninp015( )1limninim( )np n1lim( )np n例例3市场占有率预测市场占有率预测设某地有1600户居民，某产品只需甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有32户转买甲产品，有64户转买丙产品；原买丙的有64户转买甲产品，有32户转买乙产品。用外形1、2、3分别表示甲、