第3章马氏过程

1、1随机数学 第三章第三章 马氏过程马氏过程教师教师: : 陈陈 萍萍23.1 Markov链链一、马氏链的概念及转移矩阵一、马氏链的概念及转移矩阵001111|,nnnnP XiXi XiXi11|,(3.1.1)nnnnP XiXi定义定义3.1.1 3.1.1 若随机序列若随机序列XXn n,n,n N N,状态空间状态空间E=1,2,.对任意对任意n n 1,1,任意任意i i0 0,i,i1 1, ,i,in n E,E,都有都有则称则称XXn n,n,n N N,为为是一个可数状态的是一个可数状态的Markov链，简链，简称称马氏链马氏链。注 式(3.1.1)所反映这种性质称为Mar

2、kov性或无后效性，它与第一章论述的Markov性是等价的.3马氏链马氏链的等价描述：的等价描述：1)01011,nnntttNiiiE (3.1.2）仅证仅证:22110022(,)()nnnnnnnnP XiXiXi XiP XiXi事实上事实上:122111101022110011100(,)(,)(,)nnnnnnnnniEnnnnXiP XiXiXi XiP XiXiXi XiP XiXi Xi1221111(|) (|)nnnnnnnnniEP XiXiP XiXi22()nnnnP XiXi42)111:. .,0,|nnnnnnnh RR stE h XnXXE h XE h

3、XX 令=, . . . ,FF证证: 2)(3.1.1) 取取 1001111111|,|nnnnnnnnnnnnE h XP XiXi XiXiE h XXP XiXiF001111,:,nnnXinnh XXiXiXi则则反之反之, 由定义由定义,11|nnnnXinXinEEXF于是于是,1111|,iinniEniEniniiEcEcXwhere EXF53)101101(,)nn mnntntn mttntnP XiXiXiXiXi11(,)nn mntntn mtnP XiXiXi4)6定义定义3.1.2 3.1.2 MarkovMarkov链链X=XXn n,n,n N N ,

4、 E=1,2, , E=1,2,.1) - n1) - n步转移概率；步转移概率；2)2)若若 与与m m 无关无关 -齐次（或时齐）齐次（或时齐）MarkovMarkov链，链，此时此时( , )ijpm n特别特别, (1)ijijpp以下仅限于讨论齐次马氏链以下仅限于讨论齐次马氏链. 3) - n步转移概率矩阵步转移概率矩阵. ( )()nnijPp7 111212122212.kkkNkkkNkkkkNNNNppppppPppp随机矩阵随机矩阵若马氏链的状态空间若马氏链的状态空间E=1E=1，2 2，NN，则，则称此称此马氏链马氏链是有限马氏链。此时，其是有限马氏链。此时，其k k步转

5、移矩阵是一个步转移矩阵是一个N N 阶方阶方阵阵( )( )( ) 01, ,;( )1,.nnijijj Eipi jEiipiE显然显然8定理定理3.1.3 C-K方程方程.()()( )3.1.6m nmnijikkjk Sppp或或 3.1.7m nmnm nPPPP记记 - n时刻时刻Xn的概率分布向量的概率分布向量. - Markov链的绝对分布链的绝对分布; -Markov链的初始分布链的初始分布.( ),iniE(0)(0),iiE可证, 一个Markov链的特性完全由它的一步转移概率矩阵P及初始分布向量 决定9)(1)( ) ;( )(0)(3.1.9)niinn PnP定理

6、定理3.1.4EXEX 设系统有三种可能状态设系统有三种可能状态E = 1, 2, 3. “1”表示系统运表示系统运行良好，行良好，“2”表示运行不正常，表示运行不正常，“3”表示系统失效表示系统失效. 以以Xn表示系统在时刻表示系统在时刻n的状态的状态, 并设并设Xn, n0是一是一Markov链链. 没有维修及更换条件下，其自然转移概率矩阵为没有维修及更换条件下，其自然转移概率矩阵为P, 初始分布为初始分布为, 试求系统在时刻试求系统在时刻1,2及及n时出现各种状时出现各种状态的概率态的概率.01 . 09 . 011)1,nninttNiiE 101210100 11 2101(,)0n

7、nnnntttttttttnii ii iiiP XiXiXiPPP10二二 若干实例若干实例例例3.1.1 独立随机变量和的序列独立随机变量和的序列设设 n n, n0, n0为独立同分布随机变量序列，分布为独立同分布随机变量序列，分布律为律为PPn n = k= q = k= qk k, k=0,1, k=0,1,， 令令 , ,则则 XXn n, n0, n0是一是一MarkovMarkov链，且链，且 0nnkkX,0.j iijqjipji11例例3.1.2 直线上的随机游动直线上的随机游动(1)无限制的随机游动无限制的随机游动 设有一质点在数轴上随机游设有一质点在数轴上随机游动，每

8、隔一单位时间动，每隔一单位时间t (设设 t =1)移动一次，每次只移动一次，每次只能向左或向右移动能向左或向右移动x 单位单位(设设 x =1)，或原地不动，或原地不动. 设质点在设质点在0时刻的位置为时刻的位置为a，它向右移动的概率为，它向右移动的概率为p0，向左移动的概率为向左移动的概率为q0，原地不动的概率为，原地不动的概率为r0(p+q+r=1)，且各次移动相互独立，以，且各次移动相互独立，以Xn表示质表示质点经点经n次移动后所处的位置，则次移动后所处的位置，则Xn, n0是一是一Markov链，且链，且p i, i+1 = p, p i, i-1 = q, pii = r，其余其余

9、pij = 0.12(2)带吸收壁的随机游动带吸收壁的随机游动 设设(1)(1)中的随机游动限制在中的随机游动限制在E E=0, 1, 2,=0, 1, 2, , b b 内，当质点移动到状态内，当质点移动到状态0 0或或b b后就后就永远停留在该位置，即永远停留在该位置，即p p00 00 = 1= 1，p pbbbb = 1 = 1，其余，其余p pijij (1(1i i, , j jb b-1)-1)同同(1).(1).这时序列这时序列 X Xn n, , n n00称为带称为带两个吸收壁两个吸收壁0 0和和b b的随机游动，是一有限状态的随机游动，是一有限状态MarkovMarkov

10、链链. .(3)带反射壁的随机游动带反射壁的随机游动 如如(2)中的质点到达中的质点到达0或或b后，下次移动必返回到后，下次移动必返回到1或或b-1，即，即其余同其余同(1)，称为带反射壁，称为带反射壁0和和b的随机游动，且为的随机游动，且为Markov链。链。13例例3.1.3 M/G/1 排队排队系统系统假设顾客依参数为假设顾客依参数为的的PoissonPoisson过程来到只有一个服务员的服过程来到只有一个服务员的服务站，若服务员空闲来客就立刻得到服务，否则排队等待直务站，若服务员空闲来客就立刻得到服务，否则排队等待直至轮到他。设每名至轮到他。设每名顾客接受服务的时间独立同分布，分布函顾

11、客接受服务的时间独立同分布，分布函数为数为G(xG(x) )，且与顾客到达过程相互独立。这个系统称为，且与顾客到达过程相互独立。这个系统称为M/G/1M/G/1排队系统排队系统. . (M-(M-到达的时间间隔服从指数分布到达的时间间隔服从指数分布, G-, G-服务时间服务时间的分布，的分布，1-1-单个服务员单个服务员) )。令令X Xn n-第第n n个顾客服务完毕时等待接受服务的顾客数，个顾客服务完毕时等待接受服务的顾客数，U Un n-第第n n个顾客接受服务的时间内来到服务机构的顾客数，则个顾客接受服务的时间内来到服务机构的顾客数，则其中其中 可证可证Xn, n=0,1,2,是齐次

12、是齐次Markov链链,其一步转移概率为其一步转移概率为( ),1ijnpP Ujiin 14例例3.1.4 分枝过程分枝过程分枝过程是分枝过程是Markov过程的重要特例。常用来描述细过程的重要特例。常用来描述细胞分裂，种群繁衍，粒子裂变等现象，在随机过程的胞分裂，种群繁衍，粒子裂变等现象，在随机过程的理论和应用中占有非常重要的地位。下面介绍的模型理论和应用中占有非常重要的地位。下面介绍的模型是英国博物学家是英国博物学家Galton,Watson在研究家族谱系关系在研究家族谱系关系时引入的，因此也称为时引入的，因此也称为Galton-Watson分枝过程（简分枝过程（简称称G-W过程）。过程

13、）。考虑一个能产生同类后代的个体组成的群体。每个个考虑一个能产生同类后代的个体组成的群体。每个个体以概率体以概率 产生产生m个新后代，与别的个体产个新后代，与别的个体产生的后代个数相互独立。初始的个体个数为生的后代个数相互独立。初始的个体个数为X0 ，其，其后代构成第一代，总数记为后代构成第一代，总数记为 X1 。以此类推，以。以此类推，以 Xn表表示第示第 n代的总数，记代的总数，记 表示第表示第n 代的第代的第 i个个体的后个个体的后代个数，那么代个数，那么 就为一个齐次就为一个齐次Markov链，称之为时间离散的分枝过程链，称之为时间离散的分枝过程. pij=15数学模型为数学模型为 设

14、设 独立同分布取非负整数，独立同分布取非负整数，其公共分布为其公共分布为 。X0 任意取正整数的随机变任意取正整数的随机变量量0,kak.2 , 1,11)(nXnXinin则则 是一个离散时间的分枝过程，是一个离散时间的分枝过程，或分枝链。或分枝链。00!ijkkkijsja spjs 可证可证: 为齐次为齐次Markov链链. 且且1600X 171212,.,.knnknRXRXRX12.,knnnXXX11111|,.kkkkkP Rj Ri RiRi111|.kkkP Rj jiii1|kkP Rj ji1|kkkP Rj Ri11,|0,kkjkknnajiP Rj RiP Xj

15、Xiji183.2 Markov链的状态分类与判别链的状态分类与判别例例3.2.1 设系统有三种可能状态设系统有三种可能状态E= 1, 2, 3. “1”表示表示系统运行良好，系统运行良好，“2”表示运行不正常，表示运行不正常，“3”表示系表示系统失效统失效.以以Xn表示系统在时刻表示系统在时刻n的状态的状态, 并设并设Xn, n0是一是一Markov链链. 其一步转移概率矩阵为其一步转移概率矩阵为P用有向图表示为：用有向图表示为：0.10.10.30.610.919定义定义3.2.13.2.1 称状态称状态i i E E为吸收态，若为吸收态，若p piiii = 1. = 1.定义定义3.2

16、.23.2.2 对对i i, ,j j E E，若存在，若存在n n N N，使，使 ，则称自状态则称自状态i i出发可达状态出发可达状态j j，记为，记为i i j j. .如果如果i ij j且且j ji i，则称，则称i,ji,j 相通，记为相通，记为i ij j. . 定理定理3.2.1 相通是一种等价关系相通是一种等价关系,即满足即满足(1)自返性自返性 i i;(2)对称性对称性 ij,则则 ji;(3)传递性传递性 ij, jk则则 ik.20定义定义3.2.3 若一若一Markov链的任意两个状态都相通，则链的任意两个状态都相通，则称为称为不可约链不可约链。定义定义3.2.4

17、令令 T Tijij=minn:X=minn:X0 0=i,X=i,X n n=j,n=j,n 1 1 ，称为系统称为系统在在0时刻从状态时刻从状态i出发，首次到达状态出发，首次到达状态j的时间，简称的时间，简称为首达时为首达时.且规定且规定, 若右边为空集，则若右边为空集，则T Tijij =. =.设设Xn是无限制的随机游动是无限制的随机游动, 且且p, q, r 都大于都大于0. 证明证明Xn是不可约链是不可约链 .21 定义定义3.2.5 令令 | 11 ,|00iXnkjXjXPiXnTPfknijnij 1nnijijff表示表示0时刻从状态时刻从状态 i出发，经出发，经 n步转移

18、后首次到达状步转移后首次到达状态态j 的概率，称为的概率，称为n步首达概率；由步首达概率；由i 出发，经过有出发，经过有限步首次到达状态限步首次到达状态 j 的概率为的概率为22 定义定义3.2.6 若若fii=1，则称状态，则称状态 i 为为常返态常返态; 若若fii 1，则称状态则称状态 i 为为瞬时态瞬时态（非常返态）。（非常返态）。定义定义3.2.7 如果如果fij = 1, , 记记则则 表示从表示从i i出发到达出发到达j j的平均转移时间的平均转移时间. .特别，称特别，称为从状态为从状态i出发，返回状态出发，返回状态i的平均返回时间的平均返回时间.若若 0，称该数集，称该数集的

19、最大公约数的最大公约数d(i)为状态为状态i的周期的周期.若若d(i)1，称，称i为为周周期期的，若的，若d(i)=1，称，称i为非周期的为非周期的. niip定义定义3.2.8 若状态若状态 i为正常返态的且非周期的，则称为正常返态的且非周期的，则称i为为遍历状态遍历状态.定义定义3.2.9 称称Markov链是遍历的链是遍历的,如果所有状态都是如果所有状态都是遍历态遍历态. 27小结小结相通、相通、闭集闭集、不可约不可约状态状态常返常返瞬时瞬时正常返、正常返、零常返零常返周期周期、非周期非周期遍历遍历定理定理3.2.7 设马氏链的状态空间为设马氏链的状态空间为E， i, j E，（1）若）

20、若 i E是一个周期态，且是一个周期态，且 ij，则，则 j 也是也是周期周期态，且态，且di= dj ；（2）若此链不可约，且对）若此链不可约，且对i E有有pii 0，则此链是非，则此链是非周期链。周期链。283.3 状态空间分解定理状态空间分解定理01, ,ijkkfi jRR或任意任意Markov链的状态空间链的状态空间E可唯一分解为有限或可可唯一分解为有限或可列个互不相交的子集之和列个互不相交的子集之和其中其中 (1)N由全体瞬时态组成由全体瞬时态组成;(2)每个每个 或或 是零常返或正常返态组成的不可约是零常返或正常返态组成的不可约闭集闭集;(3)每个每个 或或 中的状态同类中的状

21、态同类.它们有相同的周期它们有相同的周期,且且kR0kR0kRkR29设齐次马尔可夫链的矩阵一步转移概率矩阵为设齐次马尔可夫链的矩阵一步转移概率矩阵为试对其状态空间进行分解试对其状态空间进行分解.30例例3.4.1 设设Markov链的转移矩阵为链的转移矩阵为1,011qpqqppP(1) 试求状态试求状态1,2的的n步首达概率并求步首达概率并求(2) 求求Pn并考虑当并考虑当 的情况的情况.n2 , 1,ii3.4 极限定理及平稳分布极限定理及平稳分布 1211112101,1,1|1,.fp fP XXXpq 2111,2,3,.nnfpqq n 21111211nnnnpqnfpnpqq

22、q 31 21222221,1,2,3,.,nnpqfq fqpp np 1112211,1,2,.;1,1,2,.nnnnfpp nfqq n例例3.4.1 设设Markov链的转移矩阵为链的转移矩阵为10,11ppPp qqq(1) 试求状态试求状态1,2的的n步首达概率步首达概率.32例例3.4.1 设设Markov链的转移矩阵为链的转移矩阵为10,11ppPp qqq(2) 求求Pn并考虑当并考虑当 的情况的情况.n 01,1IPpq 1110,10111qpppqpqQDQqpqpqpq111ppPQDQqq3311111nnnnnnqppqpppqpqpqqqpqpqpqpqpqP

23、QD QlimnnqppqpqqppqpqP 112211;limlimnniinnqppqpqPP34定理定理3.4.1 若状态若状态j是周期为是周期为d的常返态的常返态,则则jndjjndplim推论推论3.4.1若状态若状态j是常返态是常返态,则则j是是0常返态常返态 0njjp极限定理极限定理定理定理3.4.2 若若j是瞬时态或零常返态是瞬时态或零常返态, 则对任意则对任意i S, 0limnijnp35定理定理3.4.3 若若j是正常返态且周期为是正常返态且周期为d, 则对任意则对任意i及及 ,有有10dr limnd rrijijnjdpf推论推论 设设Xn是不可约遍历链是不可约遍

24、历链 ,则则 i,jEE 1lim0nijnjp36定义定义3.4.1 对于马氏链对于马氏链X n，n 0,概率分布概率分布称为是平稳的称为是平稳的,若若Sii,ijSiijp平稳分布与极限分布平稳分布与极限分布定理定理 3.4.4 不可约不可约Markov链是遍历链链是遍历链 对任意对任意i, j S，存在仅依赖于，存在仅依赖于j 的常数的常数 j，使得，使得( )limnijjnp j称为称为Markov链的极限分布链的极限分布. 且有且有ijSiijp37例例3.3.2 设有设有6个车站个车站,车站中车站中间的公路连接情况如图间的公路连接情况如图.汽车汽车每天可以从一个站驶向与之每天可以从一个站驶向与之直接相邻的车站直接相邻的车站,并在夜晚到并在夜晚到达车站留宿达车站留宿,次日凌晨重复相次日凌晨重复相同的活动同的活动.设每天凌晨汽车开设每天凌晨汽车开往临近的任一车站都是等可往临近的任一车站都是等可能的能的,试说明很长