第3章马氏过程

随机数学

第三章马氏过程教师:陈萍prob123@13.1Markov链

一、马氏链的概念及转移矩阵定义3.1.1若随机序列{Xn,nN},状态空间E={1,2,…}.对任意n1,任意i0,i1,···,inE,都有则称{Xn,nN},为是一个可数状态的Markov链，简称马氏链。注式(3.1.1)所反映这种性质称为Markov性或无后效性，它与第一章论述的Markov性是等价的.2马氏链的等价描述：1)(3.1.2）仅证:事实上:32)证:2)(3.1.1)取则反之,由定义,于是,43)4)课外练习5定义3.1.2Markov链X={Xn,nN},E={1,2,…}.1)--n步转移概率；2)若与m无关--齐次（或时齐）Markov链，此时特别,以下仅限于讨论齐次马氏链.3)--n步转移概率矩阵.6随机矩阵若马氏链的状态空间E={1，2，···，N}，则称此马氏链是有限马氏链。此时，其k步转移矩阵是一个N阶方阵显然7定理3.1.3C-K方程.或记--n时刻Xn的概率分布向量.--Markov链的绝对分布;--Markov链的初始分布.可证,一个Markov链的特性完全由它的一步转移概率矩阵P及初始分布向量决定…8定理3.1.4EX

设系统有三种可能状态E={1,2,3}.“1”表示系统运行良好，“2”表示运行不正常，“3”表示系统失效.以Xn表示系统在时刻n的状态,并设{Xn,n≥0}是一Markov链.没有维修及更换条件下，其自然转移概率矩阵为P,初始分布为π,试求系统在时刻1,2及n∞时出现各种状态的概率.9二若干实例例3.1.1独立随机变量和的序列设{ξn,n≥0}为独立同分布随机变量序列，分布律为P{ξn=k}=qk,k=0,1,…，令,则{Xn,n≥0}是一Markov链，且

10例3.1.2直线上的随机游动(1)无限制的随机游动设有一质点在数轴上随机游动，每隔一单位时间Δt(设Δt=1)移动一次，每次只能向左或向右移动Δx单位(设Δx=1)，或原地不动.设质点在0时刻的位置为a，它向右移动的概率为p≥0，向左移动的概率为q≥0，原地不动的概率为r≥0(p+q+r=1)，且各次移动相互独立，以Xn表示质点经n次移动后所处的位置，则{Xn,n≥0}是一Markov链，且pi,i+1=p,pi,i-1=q,pii=r，其余pij=0.11(2)带吸收壁的随机游动设(1)中的随机游动限制在E={0,1,2,…,b}内，当质点移动到状态0或b后就永远停留在该位置，即p00=1，pbb=1，其余pij(1≤i,j≤b-1)同(1).这时序列{Xn,n≥0}称为带两个吸收壁0和b的随机游动，是一有限状态Markov链.(3)带反射壁的随机游动如(2)中的质点到达0或b后，下次移动必返回到1或b-1，即其余同(1)，称为带反射壁0和b的随机游动，且为Markov链。12例3.1.3M/G/1排队系统假设顾客依参数为λ的Poisson过程来到只有一个服务员的服务站，若服务员空闲来客就立刻得到服务，否则排队等待直至轮到他。设每名顾客接受服务的时间独立同分布，分布函数为G(x)，且与顾客到达过程相互独立。这个系统称为M/G/1排队系统.(M--到达的时间间隔服从指数分布,G--服务时间的分布，1--单个服务员)。令Xn--第n个顾客服务完毕时等待接受服务的顾客数，Un--第n个顾客接受服务的时间内来到服务机构的顾客数，则其中可证{Xn,n=0,1,2,…}是齐次Markov链,其一步转移概率为13例3.1.4分枝过程分枝过程是Markov过程的重要特例。常用来描述细胞分裂，种群繁衍，粒子裂变等现象，在随机过程的理论和应用中占有非常重要的地位。下面介绍的模型是英国博物学家Galton,Watson在研究家族谱系关系时引入的，因此也称为Galton-Watson分枝过程（简称G-W过程）。考虑一个能产生同类后代的个体组成的群体。每个个体以概率产生m个新后代，与别的个体产生的后代个数相互独立。初始的个体个数为X0，其后代构成第一代，总数记为X1。以此类推，以Xn表示第n代的总数，记表示第n代的第i个个体的后代个数，那么就为一个齐次Markov链，称之为时间离散的分枝过程.pij=…14数学模型为设独立同分布取非负整数，其公共分布为。X0任意取正整数的随机变量则是一个离散时间的分枝过程，或分枝链。可证:为齐次Markov链.且15EX设{Xi,i=1,2,…}是相互独立的随机变量，且使得P{Xi=j}=aj，j=0,1,…,如果其中就称在时刻n产生了一个记录.若在时刻n产生了一个记录，就称Xn为记录值，以Rn表示第n个记录值.证明，是Markov链，并求其转移概率；16证明：根据题意有：满足故故是一个马尔可夫链且17§3.2Markov链的状态分类与判别例3.2.1设系统有三种可能状态E={1,2,3}.“1”表示系统运行良好，“2”表示运行不正常，“3”表示系统失效.以Xn表示系统在时刻n的状态,并设{Xn,n≥0}是一Markov链.其一步转移概率矩阵为P用有向图表示为：18定义3.2.1称状态iE为吸收态，若pii=1.定义3.2.2对i,j

E，若存在n

N，使，则称自状态i出发可达状态j，记为i

j.如果ij且ji，则称i,j相通，记为ij.定理3.2.1相通是一种等价关系,即满足自返性ii;对称性ij,则ji;传递性ij,jk则ik.19定义3.2.3若一Markov链的任意两个状态都相通，则称为不可约链。定义3.2.4令Tij=min{n:X0=i,Xn=j,n1}，称为系统在0时刻从状态i出发，首次到达状态j的时间，简称为首达时.且规定,若右边为空集，则Tij=∞.EX设{Xn}是无限制的随机游动,且p,q,r都大于0.证明{Xn}是不可约链.20

定义3.2.5令表示0时刻从状态i出发，经n步转移后首次到达状态j的概率，称为n步首达概率；由i出发，经过有限步首次到达状态j的概率为21

定义3.2.6若fii=1，则称状态i为常返态;若fii<1，则称状态i为瞬时态（非常返态）。定义3.2.7如果fij=1,记则表示从i出发到达j的平均转移时间.特别，称为从状态i出发，返回状态i的平均返回时间.若<∞，称i为正常返态；若=∞，称i为零常返状态.例3.2.1（续1）求系统由1出发，经过有限步首次到达状态2的概率.并求fii,i=1,2,322例3.2.2

设马尔可夫链的状态空间E={1,2,3,4}，转移概率矩阵为试判断各状态的常返性。23引理

对任意i,jE及n1，有

注：由式(3.2.1)可得递推公式:上式也称为M.C从状态i首次到达状态j的分解式，简称首达分解式。推论定理3.2.224i为瞬时态定理3.2.3推论有限状态马氏链的状态空间至少有一个常返态。定理3.2.4常返态全体构成一个闭集。定义3.2.8设CE，若对任意的iC，和任意的jC,及任意的nT，pij(n)=0，则称C为E的闭集。i为常返态25

定理3.2.6设马氏链的状态空间为E，(1)对任意i,jE，若ij，则它们同为常返态或瞬时态；而且当i,j是常返态时，i,j同为正常返态或同为零常返态；(2)不可约的有限齐次马氏链的状态都是正常返的。定义3.2.7如果集合{n:n≥1,>0}≠φ，称该数集的最大公约数d(i)为状态i的周期.若d(i)>1，称i为周期的，若d(i)=1，称i为非周期的.定义3.2.8若状态i为正常返态的且非周期的，则称i为遍历状态.定义3.2.9称Markov链是遍历的,如果所有状态都是遍历态.26小结相通、闭集、不可约状态常返瞬时正常返、零常返周期、非周期遍历定理3.2.7设马氏链的状态空间为E，i,jE，（1）若iE是一个周期态，且ij，则j也是周期态，且di=dj；（2）若此链不可约，且对iE有pii>0，则此链是非周期链。273.3状态空间分解定理任意Markov链的状态空间E可唯一分解为有限或可列个互不相交的子集之和其中N由全体瞬时态组成;每个或是零常返或正常返态组成的不可约闭集;(3)每个或中的状态同类.它们有相同的周期,且28EX设齐次马尔可夫链的矩阵一步转移概率矩阵为试对其状态空间进行分解.29例3.4.1

设Markov链的转移矩阵为(1)试求状态1,2的n步首达概率并求(2)求Pn并考虑当的情况.3.4极限定理及平稳分布解(1)30同理例3.4.1

设Markov链的转移矩阵为(1)试求状态1,2的n步首达概率.31例3.4.1

设Markov链的转移矩阵为(2)求Pn并考虑当的情况.取从而32表明33定理3.4.1若状态j是周期为d的常返态,则推论3.4.1若状态j是常返态,则j是0常返态极限定理定理3.4.2

若j是瞬时态或零常返态,则对任意iS,34定理3.4.3

若j是正常返态且周期为d,则对任意i及,有推论设{Xn}是不可约遍历链,则i,j∈E35定义3.4.1对于马氏链{Xn，n0},概率分布称为是平稳的,若平稳分布与极限分布定理3.4.4不可约Markov链是遍历链对任意i,jS，存在仅依赖于j的常数j，使得j称为Markov链的极限分布.且有36例3.3.2设有6个车站,车站中间的公路连接情况如图.汽车每天可以从一个站驶向与之直接相邻的车站,并在夜晚到达车站留宿,次日凌晨重复相同的活动.设每天凌晨汽车开往临近的任一车站都是等可能的,试说明很长时间后,各站每晚留宿的汽车比例趋于稳定.求出这个比例以便正确地设置各站的服务规模.125364P10037>>P100=P^100P100=0.12500.18750.12500.18750.12500.25000.12500