邮电概率论与随机过程课件3-4班第13讲

1、第九章 Markov链教学内容Markov链的概念及一步转移概率的概念；n步转移概率与一步转移概率的关系； Markov链的状态分类；状态空间的分解；平稳分布；最后给出一些应用实例。教学重点Markov链的定义、转移概率及状态分类教学难点状态分类12008-12-21邮电大学电子前面的，而后面T进行分类。的随机过程是按照其数字特征来进行分类对Markov过程按其状态空间E和参数集1、E和T均离散，即为本章将要的Markov链；2、E离散、但T连续，即为纯不连续的Markov过程（间断型Markov 过程）；3、 E和T均连续，即为连续型Markov过程。不妨假设 E x0 , x1 ,以后令E

2、 i，T 0,1, 2,22008-12-21邮电大学电子第一节 Markov链的基本概念及转移概率一、 Markov链的定义定义9.1.1若随机过程nnin1 E，有：和i0 , i1,Pn1 in10 i0 ,n in Pn1n in 9.1.1 in1则称n 为Markov链，9.1.1式所表达的性质称为Markov性（无后效性）。解释：若把时刻n看成“现在”，把时刻0，1，n 1看成“过去”，把时刻n 1看成“将来”，那么Markov性（无后效性）说：在已知系统“现在”所处状态的情况下，系统将来的状态与“过去”所经历的状态无关。32008-12-21邮电大学电子二、（一步）转移概率Pn

3、1 j n i pij n 系统在时刻n处于状态i的条件下，在n 1时刻系统转移到状态j的概率。即随机游动的质点在时刻n处于状态i的条件下，经过一步转移随机游动到状态j的概率，记为pij n。称条件概率pij n Pn1 j n i为Markov链定义9.1.2n , n T的一步转移概率，其中i, j E。一般地，pij n不仅与i, j有关，而且也与n有关，若pij n不依赖于n，则Markov链具有平稳的转移概率，即转移概率具有平稳性。42008-12-21邮电大学电子与定义9.1.3若Marko的，记pij n为pij .n无关，则称马氏链是的Markov链。本章只i, j E 定义9

4、.1.4由pij的矩阵 p11p1n p2nP pp ij21称为系统的转移概率矩阵（随机矩阵），它具有如下性质：（1）pij 0 i, j E （2） pij 1i E jE从状态i出发转移到系统各个状态的概率之和为152008-12-21邮电大学电子例1.1质点在1、2、3、4四个整数点上随机游动，当质点在2、3时分别以1/ 3的概率向左、向右、或停留在原地；当质点在1时以概率1返回原地；质点在4时以概率1返回到3，求转移概率矩阵。解：设n 表示n时刻质点所处的位置，则E 1, 2, 3, 4.由题意，有：p11 1 p13 p14 0p12 p22 p23 1/ 3p240, p32 p

5、33 p34 1/ 3p21p43p310 1 p42 p44 0p41101/ 31/ 3001/ 31/ 31001/ 3则：P 1/ 300062008-12-21邮电大学电子1/31试画出状态转移图如下：由状态转移图，我们知道：1 、4是质点游动不可越过的壁，因此1为吸收壁，即质点到达该点后就被完全吸住，不再转移； 4为反射壁，即质点一旦到达该状态，必然被反射回去。1/3211/31/31431/31/372008-12-21邮电大学电子例1.（2 排队模型）设服务系统由一个服务员和只容纳两个人的等候室组成，服务规则是：先到先服务，后来者需在等候室依次排队，假定一个需要服务的顾客到达系

6、统时发现系统内已有三个顾客，则该顾客即离去。设时间间隔t内将有一个顾客进入系统的概率为q，原来被服务的顾客离开系统的概率为p；又设当t充分小时，在t的时间间隔内多于一个顾客进入或离开系统实际上是不可能的；再设有无顾客来到与服务是否完毕是相互独立的。现用马氏链来描述该系统，设n n一个t时系统内的顾客数，则n , n 0,1, 2,为的Markov链，状态空间E 0,1, 2, 3，计算其一步转移概率矩阵。82008-12-21邮电大学电子随机到达者q离去者pP0 系统内原本没有顾客，0解：根据题意，p n100n经过t的时间间隔后仍然没有顾客的概率，即无人进入该系统，001 ；q 同理：p因此

7、pq0103 0 的t时间间隔内不可能有多于一个的顾客离开。p 02pP01 系统原有一个顾客，经过t的时间间隔p n110n后没有顾客的概率，即t的时间间隔内原有顾客因服务完毕而离p1 q10开，且没有任何人进入该系统，因此pP11 系统原有一个顾客，经过t间间隔的时p n111n后仍为一个顾客的概率，这里有两种情况：或者原有顾客因服务完毕而离开，且有一个；新的顾客进入该系统或者原有顾客没有离开，同时无新的顾客进入系统。所p 以 11pq 1p 1 q92008-12-21邮电大学电子等候室服务台P1 系统原有一个顾客，经过t的时间间隔后2p n112n系统有两个顾客的概率，即t的时间间隔内

8、原有顾客未服务完毕离q1 p12开，且有一人进入该系统的概率，显然：pP1 因t的时间间隔内不可能有多于一个顾3p n113n客离开，p13 0类似地有：p20 0t的时间间隔内不可能有多于一个的顾客进入。 p 1 q，p22 pq 1 p1 q，p23 p 1 q而p21 p10同理：p30则： p11 p12 p 1 q，p33 pq 1 p p31 0，p32 p21 1 p32qpq 1 pp 1 q00q 1 ppq 1 p1 q p 1 q00 p 1 qP p 1 q00pq 1 p102008-12-21邮电大学电子例1.3（输光问题）两赌徒甲、乙进行一系列，赌徒甲有a元，赌徒

9、乙有b元，每赌一局输者给赢者1元，直到两人中有一个输光为止。设在每一局中，甲赢的概率为p，输的概率为q 1 p，求甲输光的概率。这个问题实质上是带有两个吸收壁的随机游动，其状态空间E 0，1，2，c，c a b，故现在0状态先于到达状态c的概率。是求质点从a点出发到达qp0a-1aa+1a+b解：设ui 表示甲从状态i出发转移到状态0的概率，由于0和c是吸收状态，故u0 1，uc 0要计算的是ua。112008-12-21邮电大学电子由全概率公式，有：ui pui1 qui1，（i 1, 2,c 1）即甲从有i元直到输光的概率等于“他接下去以概率 p 赢了一局处于状态i 1后再输光”；和“他接

10、下去以概率 q 输了一局，处于状态i 1后再输光”这两个互不相容的事件的并事件的概率。由p q 1，则上式实质上是一个差分方程：qp ui r ui ui1 ，i 1, 2,c 1，其中r ui1边界条件为：u0 1，uc 0u r u ur (u u )i由：ui1i1ii10iu (u u ) rk故：ui1110k 1122008-12-21邮电大学电子（1）r 1，即p q 12，得：u1 1 1c , 从而得ui 1 i c ，i 1, 2,c 1b令i a，求得甲输光的概率为：u 1 acaa ba由于甲、乙的地位是对称的，故乙输光的概率为：u ba b（2）r 1，即p q的情况

11、，得：r rc1 rcu1, 从而得rcriui ，i 1, 2,c 11 rcrarc令i a，得甲输光的概率为：ua1 rc132008-12-21邮电大学电子第二节 n步转移概率定义9.2.1v设on ,k为r链n ，T分别p 称Pi M0 i和aj kpn nP,rvoj为ap,E 链j的初i始M概率和绝对概率，别称 pi , i E 和v jon k为j并分rE 链a的初M始分布和绝对分布。1设 n ,nT为Markov链，则对i和En1 定理9 .2.P有： i11，ipnn pi E1,ini142008-12-21邮电大学电子 证明P ： iP0i , i,iin11nn11n

12、i EP 0 i1, nni概率的可加性n1 ii, 1i E0 P 1i Pnn1乘法i P i公式ni 1i00i EP i0 P 1i Ein P1nMai rkov性i1in10nppiii E结论：Markov链的有限维分布完全由其初始分布和转移概率确定，即Markov链的统计特性完全由其初始分布和转移概率确定。152008-12-21邮电大学电子推论 在定理9.2.1的条件下，有：（1）P0 i,1 i1 ,n p piipi i piin1 n11 2(2)P1 i1 ,n 下面介绍n步转移概率 pii pi i piin1 n11 2 P j ii, j E, n 1为Mark

13、ovn定义9.2.2称条件概率pmnijm链 , n T的n步转移概率，并称Pn p 链 的n为Markovn步转nijn移概率矩阵，其中：n 0（1）pij（2） pn 1ijjE 1 i j即Pn为随机矩阵，当n 1时，p1 p ，P10 P，p0 i jijijij162008-12-21邮电大学电子定理9.2.2设 , n T为Markov链，则对n 0, i, j E，p n有如下性质：nijnl Chapmolmogorov方程，简称C K方程 pnl p（1）pijirrjrE n（3）Pn P Pn1（4）Pn Pn（2）ppp pijir1r1r2rn1 jr1Ern1E证明

14、：（1）利用全概率公式和Markov性，有：P j i, r,P i, jmlmnm rE P j i nmnmpP iP imnijmmm Pm i,ml r,mn j Pm i,ml rPm i,ml rPm irE Pmn rE Pmn j m i,ml r Pml r m i条件概率的定义 r Pml r m iMarkov性j mlrE pl p nl irrjrE172008-12-21邮电大学电子（2）利用（1），令l 1，r r1，得： p p pn1 pn11 pn2pijir1r1 jir1r1r2 r2 jr1Er1Er2E pir pr r11 2 prjn1r1Ern

15、1E pn1 pn1（3）利用（1），令l 1，得：pijir1r1 jr1E改写为矩阵的表示形式，有：Pn P Pn1（4）由（3）可利用归纳法加以证明。注意：（1）C K方程最重要；（2）n步转移概率完全由一步转移概率确定；（3）由（ ）Markov链的n步转移概率矩阵是一步转移概率矩阵的n次幂，可见一步转移概率矩阵尤为重要。182008-12-21邮电大学电子对于绝对概率pj n也有类似于 n步转移概率的性质，我们记：T p n , p ，n 0绝对概率p 向量n初始概率向量p，n12pT0p,12.3设nn , T为Markov链，则n对, E ， j p 有如n 下性质：1j定9 理

16、.2（p1） n np（2） n pn1n1pppjiijjiiji Ei E PT（P3） Tn P证明：（3 ）和（ ）4 分别是（1 ）和（ ）2 的矩阵形式，因此只须证明（1 ）（）2 jp（n1） Pj iPP , ijjn0n0ni Ei EP i P i njpp0n0iiji Ei E,j （p 2） n PP, iPijjn1n1jnnnii E EjP in1 P n2008-12-21 i i p1nijpn1i Ei E19邮电大学电子例.21（天气预报问题）设昨 日、今日都下雨，明日 有雨的概率为.07；昨日无雨，今日有雨 ，明日有雨的概率为.05； 昨日有雨，今日无

17、雨， 明日有雨的概率为.04；昨日、今日均无雨，明日有雨的概 率为.02。若一、二均下雨，求四下雨的概率。RR ，NR ，RN ，NN ，解：设昨日有雨、今日有雨为状态 0昨日无雨、今日有雨为昨日有雨、今日无雨为昨日无雨、今日无雨为状态1状态2状态3于是天气预报模型可看做一个四状态的 Markov 链。202008-12-21邮电大学电子根据已知条件其转移概 率为：R RRR 连续三P天有雨 pP00今明昨今RR0.P R7明昨今NR 0（R不可能事件）PpR01今明昨今NR PN1 0R.R7 R 0PR.302今明昨今 明昨今NR 0（R不可能事件）PpN03今明昨今其中R代表有雨， N代

18、表无雨。类似地得到所有状态的一步转移概率矩阵，即：p00 p0111p2131p02p073000000420000.350068p 5pppP 10 1312p20 23 033p22pp.00. 0ppp30 32212008-12-21邮电大学电子.07.004.2.00.0.3050. 070 .000.0.350.00550 .0PP 2 P0000006806. 213.500.200. 200 0 12.48 . 100. 0由于四下雨意味着二连续下雨，过程所处的状态为0四下雨的概率为：或 ，1此一、p2 0 2p .0. 12. 0p49610001222008-12-21邮电

19、大学电子因000Markov链的状态分类第三节一、状态的互通在例1.1中根据转移概率，可将某些边界分为吸收壁、反射壁等，下面从随机游动出发，利用转移概率研究Markov链的状态空间，分析状态之间的关系，进而将所有状态进行分类。设Markov链n , n 0具有可数的状态空间E 0,1, 2,，转移概率矩阵为P pij ，初始分布为 pi , i E。n 定义9.3.1若 n1，使得 p 0，则称状态i可到达j ，记为 i；j；jij 0，则称状态in 反之， n，均有： p不可到达j ，记为 iij若 i 且j，i 则称状态i ,j互通，记为i jj。通常将状态空间中互通 的状态的集合称为 类

20、，互通的状态为同类 。232008-12-21邮电大学电子1122链具有转移概率矩阵 P 例3.1设Markov，则： 01n1 1 n1n22 PnP01 1 12 n 0，则1 2；但pn 0，则2 1则pn1221知道：尽管i j，但确实有j i由此例j i 1j i 1 p随机游动）E 0, 1, 2,，p例3.（2 qij p q 1, i, j E p 0 i i 1 i 0, 1, 2,p解：由于 ii1 q 0 i 1 ipi1i则随机游动的所有状态互通。242008-12-21邮电大学电子定理9.3.（1 传递性）若i k且k j，则i j证明：由i k，则l 1，使得pl

21、0ik由k j，则n 1，使得pn 0kjrE由C K方程，pnl lnln pp0ppijirrjikrj则：i j推论：若i k1, k1 k2 , kn j，则i j（1）对称性：若i j，则j i定理9.3.2（2）传递性：若i k且k j，则i j显然，对有限制随机游动，若带有吸收壁，则吸收壁与其它状态都不互通，即除吸收壁外，其它状态互通；对随机游动，则任何状态都互通。252008-12-21邮电大学电子二、状态的分类定义9.3.2对Markov链任意两个状态i, j E，定义：（1）称Tij minn 0状态j的时间； i,n j, n 1是系统从状态i出发，首次到达（2）称f n

22、 P Ti出发，经n步首次到达ijij状态j的（条件）概率，即f n P j, s 1,n 1 i j,ijns0（3）称f PT i PTn1 n inf是系统从ijij0ij0ijn1状态i出发，经有限步终于到达状态j的概率。: f 0 0,i, j显然：ij特别地，当i j，Tii是指从状态 i 出发，首次返回状态 i 的时间；fii是指系统从状态 i 出发，经有限步终于返 回状态 i 的概率。262008-12-21邮电大学电子n引理9.3.1 i, j E及n 1，有：pn P j nl jj ilfpijn0ijl 1 j iT n P T l, j i证明：pn Pijn0iji

23、jn0l n j 0 i PTij l 0 i Pn l PTijl nn l,n j 0 i,Tijl n iPn jl 1n l 0 j 0 i,1j,l 1 j,lP Tij nl jjlfpijl 1n1n由：pnij nl jjnl jjlln0jjfpfpfpijijijl 1l 1n1则：f n nl jj pnlfpijijijl 1可以利用以上结论以及f 1 p 可递推求出f n。ijijij272008-12-21邮电大学电子 0p10q3q1设Markov链E 1, 2, 3，P qp ，求n13例3.32 0 2 p3解法1利用以上递推关系，有： 0p10q3q1 0p

24、10q3q1 q qP2 P2pp2 2 22 p30 p30 p1q2q12p3q1 p2 q3 p1 p33282008-12-21邮电大学电子n1而f n nl jjnlpfpijijijl 1则：f 1 p1，ijij即f 1 0，f 11 p p111112121 p，ijijijjj pq p则11111111113p2f 2 p2 f 1 p，f 2f 1p121212222同理可计算f 3，只要先求出P3即可.ij这种方法理论上可行，但计算烦琐。292008-12-21邮电大学电子解法 2画出状态根据题意，转移图如下：1p3p1q1q2q332p2由状态转移图，有：q m m

25、2m 1 2 m ,m 1mpn13 n qf12pmmmm pn,pm p pm 111m 11m1mqnm , 1212 n 同理，有：fp1mm2nm,302008-12-21邮电大学电子1p3p1q1q2 q3p2320n 0m 1m 1121 32或 1fpnm pqp 1 qm12p 1m 1m1313 n1,2 m ,2m0mmpm 13m 1pp1qppq23 1113或n1 , 21m1,1m1113 322 0 2m312008-12-21邮电大学电子0 i j。fij定理9.3.3证明：“ ”因i j,则n 1，使得p(n) 0。ijn fp(nk) 得：l，f0, 于是

26、f 0。由p(n)(k)(l )ijijjjijijk 1 因f0，则l 1，使得f0(l )ijijl fp(l k) ffij0，于是i j。由p(l)(k)(l )ijijjjijk 1 j0推论：i且0ji f。322008-12-21邮电大学电子理论上， Tij 是可以计算的；但实际 上一般不可能对 Tij的一切可能的取值来求 出 1的条件下从状态 i出发最后到达状态 j的平均时间：最小值，故考虑在fijn iEjT ijijnfn1n1n 当i j，称inf为状态i的平均返回时间。ii若fii 1，则称状态i常返（迟早必然会返回状态i）若fii 1，则称状态i非常返对常返状态i，若

27、i ，则为正常返；若i ，则为零常返。定义9.3.3定义9.3.4（1）对pn 0的所有正整数n 1存在最大公约数d，则称定义9.3.5ii状态i 是周期为d的, 记为d (i) d；若d (i) 1，则称状态i是非周期的；（2）非周期的正常返态，称为遍历态。332008-12-21邮电大学电子nn : pii 0记：d (i)892例 设Markov链的状态空间为E 1, 9, 状态转移图 如右所示，求1状态的周期。731645Dn : pnD4, 6,10,12,14,16, 2d (1)011下面给出关于周期d的性质定理 如果d ( j) d ,则存在正整数M，使对一切n M , 有p证

28、明略。(nd) 0。jj注：如果n : p (n) 0不空，就一定包含无穷多个元素。jj如果d ( j) d，则当n 0mod(d )时，p (n) 0，但不一定对jj(nd) 0。所有的n，有pjj342008-12-21邮电大学电子定理9.3.4设A 系统无限多次 mj， 系统至少jA，并记次 1 1mf jj 1AP m ， i P，则：Qi QA0ij0ij0jjfjj m1A证明：由A和 mA的定义知A： m 1m,A,2，, 且AmAm1因而P： A i mlimPlim QQiij0ijm0mmij m 1先计算Q P0nm 1AQim1ij0P至少,m ,n使得j,1n nl,

29、 1,j,j1mnnl0 P jn1n, nnP ln ,1j,ni至少有m个,1j l,0nl jnijj 0 fP系统至少m次到达n1 nijfQn1jmjijfjjQm352008-12-21邮电大学电子 f1Q m f fQ1 1 1fm mQ 1 mf1Q于m是jjjjjjjjjjjjf jjf jjjjjjjj1 m limfm jjjj0mm：推论 f常j返ijQ 0ijj返非常如果j是常返的，则系统从j出发无穷多次返回j的概率为1，如果j是非常返的，则系统从j出发无穷多次返回j的概率为0。练习： (ni)f证明：若 常返，p则Qiiikikk362008-12-21邮电大学电子

30、三、状态分类的判别法为了下面的需要我们引入实数列的母函数的概念。设a ,n 0为一实数列，称幂级A数 s an为s 数列的annnn0s0时 A 收s敛。母函数，当存在s0 0，使s得若s ，B s分别是 n和a n的母b函数，则数列： nA a0 n,ck nb，k1,nk 0A s B ，s称 n是 cn和 an的卷积b的C 母函s 数372008-12-21邮电大学电子1 jn0n jjn jj定理9.3.5状态j 常返 常返，则1 f；若p非pn0jjnn f l jjn， n1，两边乘以sn 1求和，得：ln证明：p由pjj，并对jjl 1 l n l n l n (f0nnn n

31、l f s0)nps1fjjp jjsjj p jjjjjjn1 n0 n0l 1l 0F和 分s 别为ss njjFnP设P和p的f母函，则：数jj 1 P s 时1 ，Fss11Ff，1 所以：P s当0s 1 F jjs另一方面当0 s 时1 ，对任意的正整数 N，有：N p n nn s psP1Pjjjjn0n0382008-12-21邮电大学电子先令s 1，再令N，：limP ns jj ps1n0n0同理可证：liFm n sjjffjjs111 F s同时令两边s 对：1，则得： s1n0n 1 fpjjjj jjn j常返fjj于是1pn0 jjnj返非常f jj1 pn0推

32、论：若j非常返，则lim pn 0jjn392008-12-21邮电大学电子402008-12-21邮电大学电子n 1，则系统从状态由常返性的定义， 有fjjpjjn0j 出发经有限步转移系统迟早会返回状态地继续下去，必有：j，而当该过程无限j 系统jj j ，j 的次数将无限增加。 jjn若状态 i 非常返，有f jj1，则从状态 j 出发经pn0j ，但系统有限步转移系统迟早会返回状态多次。状态j 至多有限np推论：若j非常返，则lim0jjn412008-12-21邮电大学电子定理9.3.5d （1若）j是周期为d的常返态，则lim p(nd ) jjnj（2）若j常返，则j零常返 li

33、m p(n) 0jjn1（3若）j遍历态，则是lim p(n) jjnj证明略。推论：若j是零常返或非常返态，则：lim p(n) 0ijnnnnn l ijn l l n l lfp证明：p由pjjij fjjf1ijijl 1l 1l n对固定的n ，当n，有： p() 0，所以上式第一项趋于 零njj0 l l ff再由fij1，则截尾项n ijijl 1l n 1p( n ) 则：lim0ijn2008-12-2142邮电大学电子综上，归纳如下：jjn n （1）状态j 常返 1 f p n0，fjj1jjn0n0n 状态j正常返 p ，lim(n)p jj0jjnn0n 状态j零常返

34、 p ，lim( n )p jj0jjn fn0n jjn jj（2）状态 j非常返 11lim( n )f jjppjjnn0重要结论：有限状态的Marokv链至少有一个常返态。反证：假设E i1 ,in 的所有状态全部非常返，则不妨假设i1 ,in至多分别为k1 ,kn次，那么系统系统充分多次k1 kn 1以后再也没有任何状态可，这与系统必须处于i1,in中某一状态2008-12-21。43邮电大学电子下面说明互通与状态分类的关系:若i常返，且i j，则j i。定理9.3.6证明：由i j知, n，使p(n) 0，ijkQ 1，(n)(n)由i常返知：1pf,且piiikkiikk则若某个k使p(n) 0,必有f 1ikki则f ji 1，P系统无限次理9.3.3，必有：j ii| X 0 QiiP i系统经n，k然后再无限次| X步0k E|X系统n经X0 ( n )i系统P再无限次P |步nk E p)Q()( n ik常i返pfkiikkik Ek E442008-12-21邮电大学电子 j ，则状态定理9. 3 .7若ii,有j 下列情况：同为常返或同为非常同为正常返或同为零有相同的周期。返；常返：1 使得 p