马尔科夫链考试例题.pdf

若 表示质点在时刻n所处的位置，分析它的 概率特性。 例例1 直线上带吸收壁的随机游动（醉汉游动） 设一质点在线段 直线上带吸收壁的随机游动（醉汉游动） 设一质点在线段1，5 上随机游动，每秒钟发生 一次随机游动，移动的规则是： 上随机游动，每秒钟发生 一次随机游动，移动的规则是： （1）若移动前在）若移动前在2，3，4处，则均以概率处，则均以概率 向左向左 或向右或向右 移动一单位； （ 移动一单位； （2）若移动前在）若移动前在1，5处，则以概率处，则以概率1停留在原处。停留在原处。 2 1 质点在1，5两点被“吸收” 12 345 ( )X n 前言：马尔可夫过程的描述分类前言：马尔可夫过程的描述分类 1 tX(t),例3 电话交换台在 时刻前来到的呼叫数 是无后效性的随机过程. X(t),例2 直线上的随机游动时的位置是 无后效性的随机过程. 无记忆性无记忆性 未来处于某状态的概率特性只与现在状态 有关，而与以前的状态无关，这种特性叫 无记忆性（无后效性）。 例例4 布朗运动布朗运动 2 若 表示质点在时刻n所处的位置，求 一步转移概率。 引例引例 例例1 直线上带吸收壁的随机游动（醉汉游动） 设一质点在线段 直线上带吸收壁的随机游动（醉汉游动） 设一质点在线段1，5 上随机游动，每秒钟发生 一次随机游动，移动的规则是： 上随机游动，每秒钟发生 一次随机游动，移动的规则是： （1）若移动前在）若移动前在2，3，4处，则均以概率处，则均以概率 向左向左 或向右或向右 移动一单位； （ 移动一单位； （2）若移动前在）若移动前在1，5处，则以概率处，则以概率1停留在原处。停留在原处。 2 1 质点在1，5两点被“吸收” 12 345 ( )X n 一步转移概率矩阵的计算 3 有两个吸收壁的随机游动有两个吸收壁的随机游动 其一步转 移矩阵为 10000 2 1 0 2 1 00 0 2 1 0 2 1 0 00 2 1 0 2 1 00001 1 P 状态空间状态空间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质点的位置， 则 ， 是一个齐次马氏链，写出其一步转 移概率。 n X n X0n 5 q p 右反射壁 m-1m pq 左反射壁 120 1 000 .000 000 .000 000 .000 . . . . . . . . . 00000 .0 00000 .0 qp qp qp P qp qp 6 pq 反 射 壁 1230 1 0 0 0 . 00 0 . 000 . . . . . . . q p qp P qp 7 例3一个圆周上共有N格（按顺时针排列），一 个质点在该圆周上作随机游动，移动的规则是： 质点总是以概率p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率 矩阵。 pq 1 1 000.0 00.00 00.00 . 00.00 0.000 pq qp qp P qp pq 1,2,.,IN 8 4一个质点在全直线的整数点上作随机游动，移 动的规则是：以概率p从i移到i-1，以概率q从i移到 i+1，以概率r停留在i，且 ，试 求转移概率矩阵。 1qpr 1 . . . . . . . . . 000 . . 000 . . . . . . . . . prq P prq ., 2, 1,0,1,2,.E 9 5设袋中有a个球，球为黑色的或白色的，今随 机地从袋中取一个球，然后放回一个不同颜色的 球。若在袋里有k个白球，则称系统处于状态k， 试用马尔可夫链描述这个模型（称为爱伦菲斯特 模型），并求转移概率矩阵。 解 这是一个齐次马氏链，其状态空间为 I=0，1，2，a 一步转移矩阵是 1 0100.0 11 00.0 22 00.0 11 0.00 0.0010 a aa a Paa a aa 10 练习题 扔一颗色子，若前n次扔出的点数的最大值为j， 就说 试问 是否为马氏链？求一步转移概率矩 阵。 I=1，2，3，4，5，6 , n Xj , n Xj 11 111111 666666 21111 0 66666 3111 00 6666 411 000 666 51 0.00 66 0.0010 P 12 例例1 甲、乙两人进行比赛，设每局比赛中甲胜的概率 是 甲、乙两人进行比赛，设每局比赛中甲胜的概率 是p，乙胜的概率是，乙胜的概率是q，和局的概率是，和局的概率是 ， （ ， （ ）。设每局比赛后，胜者记“）。设每局比赛后，胜者记“+1” 分，负者记“分，负者记“1”分，和局不记分。当两人中有 一人获得 分，和局不记分。当两人中有 一人获得2分结束比赛。以分结束比赛。以 表示比赛至第表示比赛至第n局局 时甲获得的分数。时甲获得的分数。 r 1rqp n X （1）写出状态空间；）写出状态空间； （3）问在甲获得）问在甲获得1分的情况下，再赛二局可以 结束比赛的概率是多少？ 分的情况下，再赛二局可以 结束比赛的概率是多少？ 13 解（解（1） 记甲获得“负2分”为状态1，获得 “负1分”为状态2，获得“0分”为状态3， 获得“正1分”为状态4，获得“正2分”为 状态5，则状态空间为 12345I ， ， ， ， 一步转移概率矩阵 10000 00 00 00 00001 qrp Pqrp qrp 14 （2）二步转移概率矩阵 (2)2 PP 10000 20 222 02 00001 22 222 22 rpppqrqrq pprpqrrqq pprpqrrpq 15 （3） 从而结束比赛的概率； 从而结束比赛的概率。 所以题中所求概率为 )1 (0)(rprpp 16 分 析 例例2 赌徒输光问题赌徒输光问题 赌徒甲有资本a元，赌徒乙有资本b元，两人进行 赌博，每赌一局输者给赢者1元，没有和局，直 赌至两人中有一人输光为止。设在每一局中，甲 获胜的概率为p，乙获胜的概率为 ， 求甲输光的概率。 pq1 这个问题实质上是带有两个吸收壁的随机游动。从 甲的角度看，他初始时刻处于a，每次移动一格，向 右移（即赢1元）的概率为p，向左移（即输1元）的 概率为q。如果一旦到达0（即甲输光）或a + b（即 乙输光）这个游动就停止。这时的状态空间为0，1， 2，c，c = a + b，。现在的问题是求质点从a出 发到达0状态先于到达c状态的概率。 17 考虑质点从j出发移动一步后的情况 解解 设cj 0 设 j u为质点从 j 出发到达 0 状态先于到达 c 状态的概率。 在以概率 p 移到1j的假设下， 到达 0 状态先于到达 c 状态的概率为 1j u 同理 以 概 率 q 移 到1j的 前 提 下 ， 到达0状态先于到达c状态的概率为 1j u 根据全概率公式有 qupuu jjj11 这一方程实质上是一差分方程，它的边界条件是 0, 1 0 c uu 18 于是 设 )( 11jjjj uu p q uu p q r 1 jjj uud 则可得到两个相邻差分间的递推关系 1 jj rdd 于是 2 120 j jjj drdr dr d 欲求 a u先求 j u 需讨论 r 19 当 而 1r c uu 0 1 )( 1 1 0 jj c j uu j c j d 1 0 0 1 0 dr j c j 0 1 1 d r r c cjj uuu)( 1 1 ii c ji uu 0 11 drd i c ji i c ji 1 0 (1) jcj rrrd 0 1 d r rr cj 两式相比 c cj j r rr u 1 20 故 c ca a r rr u 1 cca p q p q p q )(1)()( 当1r 00 1cduu c 而 0 )(djcu j 因此 c jc u j 故 c b c ac ua 21 用同样的方法可以求得乙先输光的概率 由以上计算结果可知 当1r即qp 时，甲先输光的概率为 cca p q p q p q )(1)()( 当1r即qp 时， 甲先输光的概率为c b 当qp 时，乙输光的概率为 ca p q p q )(1)(1 当qp 时，乙先输光的概率为 c a 22 例例3 排队问题排队问题 顾客到服务台排队等候服务，在每一个服务周期中只 要服务台前有顾客在等待，就要对排在前面的一位提 供服务，若服务台前无顾客时就不能实施服务。 设在第 n 个服务周期中到达的顾客数为一随机变量 n Y 且诸 n Y独立同分布： 1 k k p 记 n X为服务周期 n 开始时服务台前顾客数 则有 0, 1,1 1 nn nnn n XY XYX X 若 若 此时 n X，1n 为一马氏链，求其转移矩阵 在第n周期已有一个 顾客在服务，到第n+1 周期已服务完毕 23 解解先求出转移概率 ) 0| 0( 0100 XXPp) 0( 0 YP 0 p ) 0| 1( 0101 XXPp) 1( 0 YP 1 p ) 1| 0( 110 nn XXPp) 1| 01( nnn XYXP ) 0( n YP 0 p ) 1| 1( 111 nn XXPp) 1| 11( nnn XYXP ) 1( n YP 1 p ) 2| 0( 120 nn XXPp) 2| 01( nnn XYXP ) 1( n YP0 ) 2| 1( 121 nn XXPp ) 2| 11( nnn XYXP ) 0( n YP 0 p ) 2| 2( 122 nn XXPp) 1( n YP 1 p 24 所以转移矩阵为 01234 01234 10123 012 0 00 ppppp ppppp Ppppp ppp 25 证jXP n 0 I , n i P Xj Xi 00 I | n i P Xi P Xj Xi ( ) i I n ij i p p 0 , n i P XjXi (n)(n) 1212 (1)(1)(1)(1) 11i1111221 E I=1,2, 32 P, P,P, P 55 1, PX =1= p i i n Ppppp p 设 马 氏 链 的 状 态 空 间初 始 分 布 为 试 对 n=1,2,3,计 算 解 ： 例 2 26 定理4.3 马尔科夫链的有限维分布： 11 2m-1 m 1122mm 012 012 X,X,X 1) ,0, 0.10.20.7 0.90.10 0.10.80.1 0.30.40.3 X0,X1,X2 2 iiii iii i I Piii p p pp n P ppp p n 由全概率公式得到证明，它是公式（ 的推广。 考虑状态0，1，2上的一个马氏链X 它又转移概率矩阵 初始分布为，试求 概率（1） 3： （ 例 ） 234 X0,X2,X1p 27 练习：马氏链的状态空间I=1，2，3，初始概 率为 123 12 1222 13 0 44 111111 , 424333 13 0 44 (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)=3 pppP 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分别表示甲、乙、丙的用户分别表示甲、乙、丙的用户 一步转移概率矩阵为 48048964896 0.7, 0.1, 0.2 480480480 32320326464 0.1, 0.7, 0.2 320320320 64328006432 0.08, 0.04, 0.88 800800800 111213 212223 313233 PPP PPP PPP 88 . 0 04 . 0 08 . 0 2 . 07 . 01 . 0 2 . 01 . 07 . 0 1 P （2）以1600除8月份甲，乙，丙的户数，得初始概率 分布（即初始市场占有率） (0)(0)(0) 123 (0)(,)(0.3 0.2 0.5)Pppp 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( 4 1 )0()4(PPP ) 5 . 02 . 03 . 0 ( 4 88. 004. 008. 0 2 . 07 . 01 . 0 2 . 01 . 07 . 0 )5983. 01698. 02319. 0( 31 例例1 其一步转移矩阵为 试研究各状态间的关系，并画出状态传递图试研究各状态间的关系，并画出状态传递图。 设马氏链0,nX n 的状态空间 I=0，1，2 3 2 3 1 0 4 1 4 1 2 1 0 2 1 2 1 1 P 解 先按一步转移概率，画出各状态间的传递图先按一步转移概率，画出各状态间的传递图 32 2/3 1/41/4 1/3 1/2 1/2 012 1/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/1 1 P 34 11 1/2 1/2 1/2 3 1 1/2 图4-2 4 5 2 1 闭集， 由图可知 状态3为吸收态 且 故 1 C= 3为闭 集 2 C=1,4 3 C=1,3,4 闭集，闭集， 其中 是不可约的。 1 C， 2 C 又因状态空间I有闭子集，故此链为非不可约链。 35 3常返态与瞬时态常返态与瞬时态 则称状态i为常返态 则称状态i为瞬时态 注注 若1 ii f 若1 ii f “常返”一词，有时又称“返回”、“常驻”或“持久” “瞬时”也称“滑过” 或“非常返” 定理定理4 若1 ii f，则系统以概率 1 无穷次返回 i； 若1 ii f，则系统以概率 1 只有有穷次返回 i。 定理定理5i是 常 返 态 的 充 要 条 件 是 0 )( n n ii p 定理定理6 如果i为常返态，且 ，则j也是常返态。ji 定理定理7所有常返态构成一个闭集 36 5正常返态与零常返态 平均返回时间 从状态i出发，首次返回状态i的平均时间 称为状态i平均返回时间. 根据的值是有限或无限，可把常返态分为两类： 设i是常返态， 则称i为正常返态； )( 11 n ii n ii n iii nfnTnPTE 若 i 若 i ， 则称i为零常返态。 37 例例 其一步转移矩阵如下，是对I进行分解。 0 .10 .10 .20 .20 .40 0 0 0 0 .50 .50 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 00 .50 .50 0 0 0 00 .500 .5 0 0 0 000 .50 .5 P I可分解为：C1=2，3, 4 C2=5，6,7 两个闭集及 N=1 ，即I=N+ C1+ C2 12 0 0.5 0.50.500.5 001 P= 0.5 0.50 10000.5 0.5 P 38 用极限判断状态类型的准则用极限判断状态类型的准则 （2）i是零常返态 （ 是零常返态 （3）i是正常返态是正常返态 0lim )( n ii n p （1）i是瞬时态是瞬时态 )( 0 n ii n p （这时0lim )( n ii n p） )( 0 n ii n p 且 )( 0 n ii n p 且且 0lim )( n ii n p 首页首页 39 例例3 转移矩阵4 , 3 , 2 , 1I 0001 1000 0100 4 1 4 1 4 1 4 1 P 试对其状态分类。 解解 按一步转移概率， 画出各状态间的传 递图 2 1/4 11 1/41/4 1 1/4 1 4 3 40 从图可知，此链的每一状态都可到达另一状态，即4个 状态都是相通的。考虑状态1是否常返，需要计算 11 f： 4 1 )1( 11 f (2) 111441 1 4 fpp 4 1 413413 )3( 11 pppf 4 1 41342312 )4( 11 ppppf )( 11 1 11 n n ff 1 4 1 4 1 4 1 4 1 于是状态1是常返的。 2 5 )( 11 1 1 n n fn 又因为 所以状态1是正常返的。 此链所有状态都是正常返的。此链所有状态都是正常返的。 2 1/4 11 1/41/4 1 1/4 1 4 3 41 三、状态的周期与遍历三、状态的周期与遍历 1周期状态 对于任意的 ，令 其中GCD表示最大公约数 Ii 01 )( n iii pnGCDd： 如果1 i d，则称 为周期态， ii d为周期 如果1 i d则称 为非周期态。 i 定理定理11设马氏链的状态空间为 I，Iji, （1）若ji ，则 ji dd ； （2）若是不可约马氏链，且0 ii p，则此马氏链是非周期链。 2遍历状态若状态i是正常返且非周期，则称i为遍历状态。 若马氏链 n X的所有状态都是遍历的， 11 1/2 1/2 1/2 3 1 1/2 图4-2 4 5 2 1 42 例例4 设马氏链的状态空间I = 0,1,2,，转移概率为 试讨论各状态的遍历性。 解解根据转移概率作出状态传递图 2 1 00 p， 2 1 1, ii p， 2 1 0 i p，Ii 1/21/21/2 1/21/21/2 012 1/2 图4-4 3 1/2 43 从图可知，对任一状态 都有 ， 故由定理可知，I 中的所以状态都是相通的， Ii 0i 因此只需考虑状态0是否正常返即可。 (1) 00 1 , 2 f (2) 00 1 11 , 2 24 f (3)3 00 11 ( ), 28 f 故 1 2 1 1 00 n n f 从而0是常返态。 又因为 ( ) 000 11 1 2 2 n n nn nfn 所以状态0为正常返。又由于 0 2 1 ) 1 ( 00 p故状态0为非周期的 从而状态0是遍历的。 故所有状态i都是遍历的。 1/21/21/2 1/21/21/2 012 1/2 图4-4 3 1/2 44 1/3 1/2 1 1/3 1/2 1 1/3 123 4 例5设马氏链的状态空间I=1，2，3，4，其一步转移矩阵为 解 试对其状态分类。 0010 0 2 1 2 1 0 0001 3 1 3 1 3 1 0 1 P 按一步转移概率，画出各状态间的传递图 它是有限状态的马氏链，故必有一个常返态，又 链中四个状态都是互通的。因此，所有状态都是 常返态，这是一个有限状态不可约的马氏链。 可继续讨论是否为正常返态 45 可讨论状态1 0 )1( 11 f 3 1 )2( 11 f 2 1 2 1 3 1 3 1 )3( 11 f 12 1 1 2 1 2 1 3 1 )4( 11 f ( ) 1111 2 1 11111 32122 12212 n n ff 122 1 1 2 1 2 1 2 1 3 1 )5( 11 f 122 1 1 2 1 2 1 2 1 2 1 3 1 2 )6( 11 f 1 1/3 1/2 1 1/3 1/2 1 1/3 123 4 46 状态1是常返态 )( 11 1 1 n n fn 2 11111 23456 32122 12212 状态1是正常返态 所以，全部状态都是正常返态 1/3 1/2 1 1/3 1/2 1 1/3 123 4 47 例例1 其一步转移矩阵为 试证此链具有遍历性，并求平稳分布和各状态的平均返回时间 3 2 3 1 0 3 2 0 3 1 0 3 2 3 1 1 P 解解 由于 2 12 )(PP 3 2 9 2 9 1 9 4 9 4 9 1 9 4 9 2 3 1 48 所以 因此，该马氏链具有遍历性。 解得 112 213 323 123 11 33 21 33 22 33 1 所以马氏链的平稳分布为 X i 123 7 1 7 2 7 4 各状态的平均返回时间各状态的平均返回时间 49 例例2设有6个球（其中2个红球，4个白球）分放于甲、 乙两个盒子中，每盒放3个，今每次从两个盒中 各任取一球并进行交换，以 表示开始时甲 盒中红球的个数， （ ）表示经n次交换 后甲盒中的红球数。 ( 1 ) 求马氏链 ， 的转移概率矩阵； 0 X n X1n n X1n ( 2 ) 证明 ， 是遍历的； n X1n （3）求 )( lim n ij n p 2 , 1 , 0,ji （4）求lim ( ) j n p n 2 , 1 , 0j 50 解 其一步转移矩阵为 解 其一步转移矩阵为 3 1 3 2 0 9 2 9 5 9 2 0 3 2 3 1 1 P 甲乙 红球红球0 白球白球3 红球红球2 白球白球1 红球红球1 白球白球2 红球红球1 白球白球2 红球红球2 白球白球1 红球红球0 白球白球3 1/3 2/9 5/9 2/3 2/9 1/3 012 2/3 51 由状态传递图 1/3 2/9 5/9 2/3 2/9 1/3 012 2/3 （2）由于它是一个有限马氏链，故必有一个常返态， 又链中三个状态0、1、2都相通，所以每个状态都是常返态。 所以是一个不可约的有限马氏链，从而每个状态都是正常返的。 所以此链为非周期的。 故此链是不可约非周期的正常返链，即此链是遍历的。 52 也可以利用定理1证明遍历性 2 2 12 3 1 3 2 0 9 2 9 5 9 2 0 3 2 3 1 PP 53 解之得 001 1012 212 012 j 12 39 252 393 21 93 1 0,(0,1,2)j 故得 ( ) 0 lim n i n p 0 1 5 ( ) 1 lim n i n p 1 3 5 54 （4） 0 1 5 1 3 5 0 lim( ) n p n 1 lim( ) n p n 55 例例3市场占有率预测市场占有率预测 设某地有1600户居民，某产品只有甲、乙、丙3厂家 在该地销售。经调查，8月份买甲、乙、丙三厂的户 数分别为480，320，800。9月份里，原买甲的有48户 转买乙产品，有96户转买丙产品；原买乙的有32户转 买甲产品，有64户转买丙