资源描述
2012-8-24 1 若 表示质点在时刻 n所处的位置，分析它的 概率特性。 例 1 直线上带吸收壁的随机游动（醉汉游动） 设一质点在线段 1， 5 上随机游动，每秒钟发生 一次随机游动，移动的规则是： （ 1）若移动前在 2， 3， 4处，则均以概率 向左 或向右 移动一单位； （ 2）若移动前在 1， 5处，则以概率 1停留在原处。 2 1 质点在 1， 5两点被“吸收 ” 1 2 3 4 5 ()X n 前言：马尔可夫过程的描述分类 tX(t),例3 电话交换台在 时刻前来到的呼叫数 是无后效性的随机过程. X(t),例2 直线上的随机游动时的位置 是 无后效性的随机过程. 首页 无 记 忆 性 未来处于某状态的概率特性只与现在状态 有关，而与以前的状态无关，这种特性叫 无记忆性（无后效性）。 例 4 布朗运动 若 表示质点在时刻 n所处的位置，求 一步转移概率。 引 例 例 1 直线上带吸收壁的随机游 动（醉汉游动） 设一质点在线段 1， 5 上随机游动，每秒钟发生 一次随机游动，移动的规则是： （ 1）若移动前在 2， 3， 4处，则均以概率 向左 或向右 移动一单位； （ 2）若移动前在 1， 5处，则以概率 1停留在原处。 2 1 质点在 1， 5两点被“吸收 ” 1 2 3 4 5 ()X n 一步转移概率矩阵的计算 首页 有两个吸收壁的随机游动 其一步转 移矩阵为 = 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， ， 例 2带有反射壁的随机游动 设随机游动的状态空间 I = 0， 1， 2， ，移动的 规则是： （ 1）若移动前在 0处，则下一步以概率 p向右移 动一个单位，以概率 q停留在原处（ p+q=1）； （ 2）若移动前在其它点处，则均以概率 p向右移 动一个单位，以概率 q向左移动一个单位。 设 表示在时刻 n质点的位置， 则 ， 是一个齐次马氏链，写出其一步转 移概率。 n X n X 0n 首页 q p 右反射壁 m-1 m p q 左反射壁 1 2 0 1 000.000 000.000 000.000 . . . . . . . . . 00000. 0 00000.0 qp qp qp P qp qp = 首页 2012-8-24 2 p q 反 射 壁 1 2 3 0 1 000. 0 0 0 . 000. . . . . . . qp qp P qp = 首页 例 3一个圆周上共有 N格（按顺时针排列），一 个质点在该圆周上作随机游动，移动的规则是： 质点总是以概率 p顺时针游动一格， 以概率 逆时针游动一格。试求转移概率 矩阵。 pq = 1 1 000.0 00.00 00.00 . . . . . . . 00.0 0 0. 00 0 p q qp qp P qp pq = 1, 2 , ., I N= 首页 4一个质点在全直线的整数点上作随机游动，移 动的规则是：以概率 p从 i移到 i-1，以概率 q从 i移到 i+1，以概率 r停留在 i，且 ，试 求转移概率矩阵。 1=+ qpr 1 . . . . . . . . . 0 0 0 . . 0 0 0 . . . . . . . . . prq P prq = ., 2, 1,0,1,2,.E = 首页 5设袋中有 a个球，球为黑色的或白色的，今随 机地从袋中取一个球，然后放回一个不同颜色的 球。若在袋里有 k个白球，则称系统处于状态 k， 试用马尔可夫链描述这个模型（称为爱伦菲斯特 模型），并求转移概率矩阵。 解 这是一个齐次马氏链，其状态空间为 I=0， 1， 2， ， a 一步转移矩阵是 1 0 1 0 0 . 0 11 0 0 . 0 22 0 0 . 0 . . . . . . 11 0 . 0 0 0 . 0 0 1 0 a aa a P aa a aa = 首页 练习题 扔一颗色子，若前 n次扔出的点数的最大值为 j， 就说 试问 是否为马氏链？求一步转移概率矩 阵。 I=1， 2， 3， 4， 5， 6 首页 , n Xj= , n Xj= 111111 666666 21111 0 66666 3111 00 6666 411 000 666 51 0 . 0 0 66 0 . 0 0 1 0 P = 2012-8-24 3 例 1 甲、乙两人进行比赛，设每局比赛中甲胜的概率 是 p，乙胜的概率是 q，和局的概率是 ， （ ）。设每局比赛后，胜者记“ +1” 分，负者记“ 1”分，和局不记分。当两人中有 一人获得 2分结束比赛。以 表示比赛至第 n 局时甲获得的分数。 r 1=+ rqp n X （ 1）写出状态空间； （ 2）求 (2) P ； （ 3）问在甲获得 1分的情况下，再赛二局可 以结束比赛的概率是多少？ 首页 解 （ 1） 记甲获得“负 2分”为状态 1，获得 “负 1分”为状态 2，获得“ 0分”为状态 3， 获得“正 1分”为状态 4，获得“正 2分”为 状态 5，则状态空间为 12345I = ， 一步转移概率矩阵 100 0 0 00 00 00 000 0 1 qr p P qr p qrp = 首页 （ 2）二步转移概率矩阵 (2) 2 P P= + + + = 10000 20 222 02 00001 22 222 22 rpppqrqrq pprpqrrqq pprpqrrpq 首页 （ 3） 在 (2) P 中 (2) 45 p 是在甲得 1 分的情况下经二步转移至得 2 分 从而结束比赛的概率； (2) 41 p 是在甲得 1 分的情况下经二步转移至 2 分（即乙得 2 分） 从而结束比赛的概率。 所以题中所求概率为 (2) 45 p + (2) 41 p )1(0)( rprpp +=+= 首页 分 析 例 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状态的概率。 首页 考虑质点从 j出发移动一步后的情况 解 设 cj 0 设 j u 为质点从 j 出发到达 0 状态先于到达 c 状态的概率。 在以概率 p 移到 1+j 的假设下， 到达 0 状态先于到达 c 状态的概率为 1+j u 同理 以概率 q 移到 1j 的前提下， 到达 0状态先于到达 c状态的概率为 1j u 根据全概率公式有 qupuu jjj 11 + += 这一方程实质上是一差分方程，它的边界条件是 0,1 0 = c uu 首页 2012-8-24 4 于是 设 （ p + q） 11 + += jjj qupuu )( 11 jjjj uu p q uu = + p q r = 1+ = jjj uud 则可得到两个相邻差分间的递推关系 1 = jj rdd 于是 2 12 0 j jj j drd rd rd = =L 欲求 a u 先求 j u 需讨论 r 首页 当 而 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 rr rd =+L 0 1 d r rr cj = 两式相比 c cj j r rr u = 1 首页 故 c ca a r rr u = 1 = cca p q p q p q )(1)()( 当 1=r 00 1 cduu c = 而 0 )( djcu j = 因此 c jc u j = 故 c b c ac u a = = 首页 用同样的方法可以求得乙先输光的概率 由以上计算结果可知 当 1r 即 qp 时，甲先输光的概率为 cca p q p q p q )(1)()( 当 1=r 即 qp = 时， 甲先输光的概率为 c b 当 qp 时，乙输光的概率为 ca p q p q )(1)(1 当 qp = 时，乙先输光的概率为 c a 首页 例 3 排队问题 顾客到服务台排队等候服务，在每一个服务周期中只 要服务台前有顾客在等待，就要对排在前面的一位提 供服务，若服务台前无顾客时就不能实施服务。 设在第 n个服务周期中到达的顾客数为一随机变量 n Y 且诸 n Y 独立同分布： ) nk P Yk p=（ ， 0,1, 2,k = L ， 1= k k p 记 n X 为服务周期 n 开始时服务台前顾客数 则有 = + = + 0, 1,1 1 nn nnn n XY XYX X 若 若 此时 n X ， 1n 为一马氏链， 求其转移矩阵 在第 n周期已有一个 顾客在服务，到第 n+1 周期已服务完毕 解 先求出转移概率 )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 YP 0= )2|1( 121 = + nn XXPp )2|11( =+= nnn XYXP )0( = n YP 0 p= )2|2( 122 = + nn XXPp )1( = n YP 1 p= 首页 2012-8-24 5 所以转移矩阵为 01234 01234 1 0123 012 0 00 ppppp ppppp P pppp ppp = L L L L LLLLLL 首页 证 jXP n = 0 I , n i P XjXi = = 00 I | n i P XiPX jXi = = () i I n ij i pp = 0 , n i P XjXi= =U (n) (n) 12 12 (1) (1) (1) (1) 11 i1 21 E I=1,2, 32 P,P, P,P 55 1, PX=1= p i i n Ppppp = = =+ 设马氏链的状态空间 初始分布为 试对n=1,2,3,计算 解： 例2 定理 4.3 马尔科夫链的有限维分布： 112 m-1m 112 2 m m 01 2 012 X , X , , X 1) ,0, 0.1 0.2 0.7 0.9 0.1 0 0.1 0.8 0.1 0.3 0.4 0.3 X 0, X 1, X 2 2 iii ii ii iI Pi i i pp p p n P ppp p = = = = = = L L n 由全概率公式得到证明，它是公式（ 的推广。 考虑状态0，1，2上的一个马氏链X 它又转移概率矩阵 初始分布为 ， ， ，试求 概率（1） 3： （ 例 ） 234 X 0, X 2, X 1p = 练习：马氏链的状态空间 I=1， 2， 3，初始概 率为 123 12 12 22 13 0 44 111 111 , 424 333 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 = 计算 证明： 求 例 4 市场占有率预测 设某地有 1600户居民，某产品只有甲、乙、丙 3厂 家在该地销售。经调查， 8月份买甲、乙、丙三厂 的户数分别为 480， 320， 800。 9月份里，原买甲的 有 48户转买乙产品，有 96户转买丙产品；原买乙的 有 32户转买甲产品，有 64户转买丙产品；原买丙的 有 64户转买甲产品，有 32户转买乙产品。用状态 1、 2、 3分别表示甲、乙、丙三厂，试求 （ 1）转移概率矩阵； （ 2） 9月份市场占有率的分布； （ 3） 12月份市场占有率的分布； 解 （ 1） E1， 2， 3,状态 1、 2、 3分别表示甲、乙、丙的用户 一步转移概率矩阵为 480 48 96 48 96 0.7, 0.1, 0.2 480 480 480 32 320 32 64 64 0.1, 0.7, 0.2 320 320 320 64 32 800 64 32 0.08, 0.04, 0.88 800 800 800 = = = = = = = = = = = 11 12 13 21 22 23 31 32 33 PPP PP P PPP = 88.004.008.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= 2012-8-24 6 所以 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(= 例 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 解 先按一步转移概率，画出各状态间的传递 图 首页 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 中没有其它闭集 所以此马氏链是不可约的 。 首页 例 2 其一步转移矩阵为 试讨论哪些状态是吸收态、闭集及不可约链 。 解 先按一步转移概率，画出各状态间的传递 图 设马氏链的状态空间为 I = 1， 2， 3， 4， 5 = 00010 00001 00100 002/102/1 02/1002/1 1 P 首页 1 1 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 闭集， 闭集， 4 C =1,2,3,4 其中 是不可约的。 1 C ， 2 C 又因状态空间 I有闭子集， 故此链为非不可约链。 首页 3常返态与瞬时态 则称状态 i为常返态 则称状态 i为瞬时态 注 若 1= ii f 若 1 ii f “常返”一词，有时又称“返回”、“常驻”或“持久” “瞬时”也称“滑过” 或“非常返” 定理 4 若 1= ii f ，则系统以概率 1 无穷次返回 i； 若 1 ii f ，则系统以概率 1 只有有穷次返回 i。 定理 5 i是常返态的充要条件是 = =0 )( n n ii p 定理 6 如果 i为常返态，且 ，则 j也是常返态。 ji 定理 7 所有常返态构成一个闭集 2012-8-24 7 5正常返态与零常返态 平均返回时间 从状态 i出发，首次返回状态 i的平均时间 称为状态 i平均返回时间 . 根据的值是有限或无限，可把常返态分为两类： 设 i是常返态， 则称 i为正常返态； )( 11 n ii n ii n iii nfnTnPTE = 若 i 若 = i ， 则称 i为零常返态。 首页 例 其一步转移矩阵如下，是对 I进行分解。 设马氏链 0, nX n 的状态空间 I=1， 2， 3, ,7 0.1 0.1 0.2 0.2 0.4 0 0 0 0 0 .5 0 .5 0 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 0 0 .5 0 0 .5 0 0 0 000.50.5 P = I可分解为： C 1 =2， 3, 4 C 2 =5， 6,7 两个闭集及 N=1 ，即 I=N+ C1+ C2 12 0 0.5 0.5 0.5 0 0.5 0 0 1 P = 0.5 0.5 0 10 0 00.50.5 P = 用极限判断状态类型的准则 （ 2） i是零常返态 （ 3） i是正常返态 0lim )( = n ii n p （ 1） i是瞬时态 i d ， 则称 为周期态， i i d 为周期 如果 1= i d 则称 为非周期态。 i 定理 11 设马氏链的状态空间为 I， Iji , （ 1）若 ji ，则 ji dd = ； （ 2）若是不可约马氏链，且 0 ii p ，则此马氏链是非周期链。 2遍历状态 若状态 i是正常返且非周期，则称 i为遍历状态。 若马氏链 n X 的所有状态都是遍历的， 则称 n X 为遍历链 1 1 1/2 1/2 1/2 3 1 1/2 图 4-2 4 5 2 1 2012-8-24 8 例 4 设马氏链的状态空间 I = 0,1,2,，转移概率为 试讨论各状态的遍历性。 解 根据转移概率作出状态传递图 2 1 00 =p ， 2 1 1, = +ii p ， 2 1 0 = i p ， Ii 1/2 1/2 1/2 1/2 1/2 1/2 0 1 2 1/2 图 4-4 3 1/2 首页 从图可知，对任一状态 都有 ， 故由定理可知， I 中的所以状态都是相通的， Ii 0i 因此只需考虑状态 0是否正常返即可。 (1) 00 1 , 2 f = (2) 00 11 1 , 22 4 f = = (3) 3 00 11 () , 28 f = = 故 1 2 1 1 00 = = n n f 从而 0是常返态。 又因为 () 000 11 1 2 2 n n nn nf n = = =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=1， 2， 3， 4，其一步转移矩阵为 解 试对其状态分类。 = 0010 0 2 1 2 1 0 0001 3 1 3 1 3 1 0 1 P 按一步转移概率，画出各状态间的传递图 它是有限状态的马氏链，故必有一个常返态，又 链中四个状态都是互通的。因此，所有状态都是 常返态，这是一个有限状态不可约的马氏链。 可继续讨论是否为正常返态 可讨论状态 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 () 11 11 2 1 11 1 1 1 3212212212 n n ff = = =+ + + + L 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 1 2 3 4 状态 1是常返态 )( 11 1 1 n n fn = = ij p 。 112 213 323 123 11 33 21 33 22 33 1 =+ =+ =+ += 112 2 3 3 1/ 7, 1/ 3.5, 1/ 7/4 = = 所以马氏链的平稳分布为 X i 1 2 3 7 1 7 2 7 4 各状态的平均返回时间 例 2 设有 6个球（其中 2个红球， 4个白球）分放于甲、 乙两个盒子中，每盒放 3个，今每次从两个盒中 各任取一球并进行交换，以 表示开始时甲 盒中红球的个数， （ ）表示经 n次交换 后甲盒中的红球数。 ( 1 ) 求马氏链 ， 的转移概率矩阵； 0 X n X 1n n X 1n ( 2 ) 证明 ， 是遍历的； n X 1n （ 3）求 )( lim n ij n p 2,1,0, =ji （ 4）求 lim ( ) j n pn 2,1,0=j 首页 解 其一步转移矩阵为 （ 1）因 n X 表红球数，所以状态空间 E = 0,1,2 = 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 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都相通，所以每个状态都是常返态。 所以是一个不可约的有限马氏链，从而每个状态都是正常返的。 所以此链为非周期的。 故此链是不可约非周期的正常返链，即此链是遍历的。 又由 0 3 1 00 =p 首页 也可以利用定理 1证明遍历性 （ 3）由于 () j lim n ij n p = （ 2,1,0=j ） ， 所以先求平稳分布 j 2 2 12 3 1 3 2 0 9 2 9 5 9 2 0 3 2 3 1 = PP 首页 解之得 001 1012 212 012 j 12 39 252 393 21 93 1 0,( 0,1,2)j =+ =+ =+ += = 0 1 5 = ， 1 3 5 = ， 2 1 5 = 故得 () 0 lim n i n p = 0 1 5 = () 1 lim n i n p = 1 3 5 = 首页 2012-8-24 10 （ 4） 0 1 5 = 1 3 5 = () 2 lim n i n p = 2 1 5 = 0 lim ( ) n p n = 1 lim ( ) n pn = 2 lim ( ) n pn = 2 1 5 = 首页 例 3 市场占有率预测 设某地有 1600户居民，某产品只有甲、乙、丙 3厂家 在该地销售。经调查， 8月份买甲、乙、丙三厂的户 数分别为 480， 320， 800。 9月份里，原买甲的有 48户 转买乙产品，有 96户转买丙产品；原买乙的有 32户转 买甲产品，有 64户转买丙产品；原买丙的有 64户转买 甲产品，有 32户转买乙产品。用状态 1、 2、 3分别表 示甲、乙、丙三厂，试求 （ 1）转移概率矩阵； （ 2） 9月份市场占有率的分布； （ 3） 12月份市场占有率的分布； （ 4）当顾客流如此长期稳定下去市场占有率的分布。 （ 5） 各状态的平均返回时间 首页 解 （ 1） 由题意得频数转移矩阵为 再用频数估计概率，得转移概率矩阵为 = 7043264 6422432 9648336 N = 88.004.008.0 2.07.01.0 2.01.07.0 1 P （ 2）以 1600除以 N中各行元素之和，得初始概率分布 （即初始市场占有率） )5.02.03.0(),()0( 321 = pppP 首页 所以 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(= 首页 （ 4）由于该链不可约、非周期、状态有限正常返 的，所以是遍历的。 解方程组 =+ += += += 1 88.02.02.0 04.07.01.0 08.01.07.0 321 3213 3212 3211 即得当顾客流如此长期稳定下去是市场占有率的分布为 )625.0156.0219.0(),( 321 = 123 ( , , ) (1/ 0.219 1/ 0.156 1/ 0.625)= （ 5） 例 4 (书中 69页 例 4.18） 其一步转移矩阵为 试并每个不可约闭集的平稳分布 设马氏链 0, nX n 的状态空间 I=1， 2， 3, ,7 0.1 0.1 0.2 0.2 0.4 0 0 0 0 0 .5 0 .5 0 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 0 0 .5 0 0 .5 0 0 0 000.50.5 P = 2012-8-24 11 的平稳分布得 状态空间可分解为： C=2， 3, 4 D=5， 6,7 两个闭集，分别 求对应转移概率矩阵 1234567 1234567 212 (,)(0, , ,0,0,0) 555 111 (,)(0,0,0,0, , ,) 333 = = 12 0 0.5 0.5 0.5 0 0.5 0 0 1 P = 0.5 0.5 0 10 0 00.50.5 P =
展开阅读全文