马尔科夫链——概率与数理统计

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十一章,马尔科夫链,11.1,马尔科夫过程及其概率分布,马尔科夫过程,若随机过程,X(,t,),t,T,对于任意的正整数,n,及,t,1,t,2,t,n,T,其条件分布满足,PX(,t,n,),x,n,|X(,t,1,)=,x,1,X(,t,n,-1,)=,x,n,-1,=PX(,t,n,),x,n,|X(,t,n,-1,)=,x,n,-1,x,n,R,或写成,则称随机过程,X(,t,),t,T,为,马尔科夫过程,.,马尔科夫链,时间和状态都是离散的马尔科夫过称,为,马尔科夫链,，简称马氏链,.,记为,X,n,=X(,n,),，,n,=0,1,2,.,它可以看作在时间集,T,1,=,0,1,2,上,的离散状态的马氏过程相继观察的结果,.,链的状态空间：,I=,a,1,a,2,a,i,R.,3.,转移概率,对任意得正整数,n,r,和,0,t,1,t,2,t,r,m,;,t,i,m,n+m,T,1,有,其中,a,i,I.,则称条件概率,P,ij,(,m,m+n,),=,P,X,m+n,=,a,j,|,X,m,=,a,i,为马氏链在时刻,m,处于状态,a,i,条件下，在时刻,m+n,转移到状态,a,j,的,转移概率,.,转移概率矩阵,由转移概率组成的矩阵,称为马氏链的,转移概率矩阵,.,此矩阵的每一行元素之和等于,1.,当转移概率,P,ij,(,m,m+n,),只与,i,j,及时间距,n,有关时，把它记为,P,ij,(,n,),即,并称转移概率具有,平稳性,，同时也称此链,是,齐次的或时齐的,.,5.,n,步转移概率和,n,步转移矩阵,n,步转移概率,:,n,步转移概率矩阵,:,一步转移概率,:,一步转移概率矩阵,:,p,11,p,12,p,1j,p,21,p,22,p,2j,p,i1,p,i2,p,ij,a,1,a,2 ,a,j,a,1,a,2,.,a,i,.,例,1,.,（,0-1,传输系统）,在如下图只传输数字,0,和,1,的串联系统中，,设每一级的传真率为,p,，,误码率为,q,=1-,p,（,输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）,;,设一个单位时间传输一级,X,0,是,第一级的输入，,X,n,是第,n,级的输出,(,n,1,),那么 是一随机过程,.,状态空间,I=0,1,，,而且当,X,n,=i,i,I,为已知时，,X,n+1,所处的状态的概率分布只,与,X,n,=,i,有关，而与时刻,n,以前所处的状态无关，所以它是一个马氏链，而且还是齐次的,.,它的一步转移概率和一步转移概率矩阵分别为,1,2,n,X,0,X,1,X,n,X,2,X,n-1,和,例,2,一维随机游动,设一醉汉,Q,在如下图点集,I=1,2,3,4,5,上作随机游动，并且仅仅在,1,秒、,2,秒,等时刻发生游动,.,规律是：,(1),如果,Q,现在位于点,i,(1,i,5),则下一时刻各以,1/3,的概率向左或向右移动一格，或以,1/3,的概率留在原处；,(2),如果,Q,现在位于,1,（或,5,）这点上，则下一时刻就以概率,1,移动,2,（或,4,）这一点上,.1,和,5,这两点称为,反射壁,.,上面这种游动称为,带有两个反射壁的随机游动,.,0 1,若以,X,n,表示时刻,n,时,Q,的位置，不同的位置就是,X,n,的不同状态，那么,X,n,n,=0,1,2,是一随机过程，状态空间就是,I,，,而且,X,n,=,i,i,I,为,已知时，,X,n,+1,所处的状态的概率分布只与,X,n,=,i,有关，而与,Q,在时刻,n,以前如何达到是完全无关的，所以,X,n,n,=0,1,2,是一马氏,链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为,如果把一这一点改为吸收壁，即是说,Q,一旦到达,1,这一点，则就永远留在点一上，相应链的转移概率矩阵只须把,p,中的第一横行改为（,1,，,0,，,0,，,0,，,0,）,.,总之改变游动的概率规则，就可得到不同方式的随机游动和相应的马氏链,.,随机游动的思想在数值计算方法方面有重要应用,.,0,1,0,0,0,1/3,1/3,1/3,0,0,0,1/3,1/3,1/3,0,0,0,1/3,1/3,1/3,0,0,0,1,0,1,2 3 4 5,1,2,3,4,5,例,3,排队模型,服务系统组成,：服务员（,1,个）,等候室（,2,人）,.,服务规则,：先到先服务,.,假定一顾客到达系统时发现系统内已有,3,个顾客，则该顾客即离去,.,设时间间隔,t,内，有一个顾客进入系统的概率为,q,，有,一原来被服务的顾客离开系统的概率为,p,.,设当,t,充分小时，在这个时间间隔内多于一个顾客进入或离开系统实际上是不可能的,.,设有无顾客来到与服务是否完毕是相互独立的,.,等候室,服务台,随机到达者,离去者,系 统,设,X,n,=,X(,n,t,),表示时刻,n,t,时,系统内的顾客数，即系统的状态,.,是一随机过程，状态空间,I=0,1,2,3,，,由前例的分析,可知它是一个齐次马氏链,.,下面来计算此马氏链的一步转移概率,.,p,00,表示在系统内没有顾客的条件下，经,t,后仍,没有顾客的概率（此处是条件概率，以下同）,p,00,=1,-,q,.,p,01,表示在系统内没有顾客的条件下，经,t,后有一,顾客进入系统的概率，,p,01,=q.,p,10,系统内恰有一个顾客正在接受服务的条件下，经,t,后,系统内无人的概率，它等于在,t,间隔内顾客因服务完毕而离去，且无人进入系统的概率，,p,10,=,p,(1,q,),p,11,系统内恰有一顾客的条件下，在,t,间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率，,p,11,=,pq,+(1-,p,)(1-,q,).,p,12,正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率,p,12,=(1-,p,),q,.,p,13,正在接受服务的顾客继续要求服务，且在,t,间隔内有两个顾客进入系统的概率，由假设，后者实际上是不可能发生的，,p,13,=0.,类似地，有,p,21,=,p,32,=,p,(1-,q,),p,22,=,pq,+,(1-,p,)(1-,q,),p,23,=,q,(1-,p,),p,ij,=0,(,|,i-j,|,2,).,p,33,:,或者一人将离去且另一人将进入系统，或者无人离开的概率，,p,33,=,pq,+,(1-,p,).,于是该马氏链的一步转移概率矩阵为,1-,q,q,0,0,p,(1-,q,),pq,+(1-,p,)(1-,q,),q,(1-,p,),0,0,p,(1-,q,),pq,+(1-,p,)(1-,q,),q,(1-,p,),0,0,p,(1-,q,),pq,+,(1-,p,),在实际问题中，一步转移概率通常可通过统计实验确定,.,例,4,某计算机机房的一台计算机经常出故障，研究者每隔,15,分钟观察一次计算机的运行状态，收集了,24,小时的数据,(,共作,97,次观察,).,用,1,表示正常状态，用,0,表示不正常状态，所得的数据序列如下：,1110010011111110011110111111001111111110001101101,111011011010111101110111101111110011011111100111,设,X,n,为第,n,(,n,=1,2,97),个时段的计算机状态，可以认为它是一个马氏链，状态空间,I=0,1.96,次状态转移的情况是：,0 0,8,次；,0 1,18,次；,1 0,18,次,;1 1,52,次,.,因此，一步转移概率可用频率近似地表示为,齐次马氏链的有限维分布,.,马氏链的初始分布为,:,1),马氏链在任一时刻,n,T,1,的一维分布：,显然，应有 由全概率公式得,即,一维分布也可用行向量表示成,p,(,n,),=(,p,1,(,n,),p,2,(,n,),p,j,(,n,),),这样，利用矩阵乘法（,I,是可列无限集时，仍用有限阶）矩阵乘法的规则确定矩阵之积的元素，可写成,p,(,n,),=,p,(0),P,(,n,),(,矩阵,),结论,：马氏链在任一时刻,n,T,1,时的一维分布由初始分布,p,(0),和,n,步转移概率矩阵所确定,.,对于任意,n,个时刻,t,1,t,2,t,t,n,t,i,T,1,以及状态 有：,马氏链的,n,维,分布,：,由乘法公式,结论,：由此可知，马氏链的有限维分布同样完全由初始分布和转移概率确定,.,总之,转移概率决定了马氏链的统计规律,.,因此,确定马氏链的任意,n,步转移概率就成为马氏链理论中的重要问题之一,.,例,5,（续例,4,）若计算机在前一段（,15,分钟）的状态为,0,，问从时段起此计算机能连续正常工作一小时（,4,个时段）的概率为多少？,解 由题意，前一时段的状态为,0,就是初始分布,p,0,(0),=P,X,0,=0=1.,计算机能连续正常工作,4,个时段的概率为,P,X,0,=,0,X,1,=,1,X,2,=,1,X,3,=1,X,4,=1,=,P,X,0,=,0,P,X,1,=,1|,X,0,=,0P,X,2,=,1,|X,1,=,1,P,X,3,=1|,X,2,=,1P,X,4,=1|,X,3,=1,=,p,0,(0),P,01,(1),P,11,(1),P,11,(1),P,11,(1),11.2,多步转移概率的确定,为了确定齐次马氏链的,n,步转移概率 首先介绍,所满足的基本方程,.,设,X(,n,),n,T,1,是一齐次马氏链，则对任意的,u,v,T,1,有,这就是著名的切普曼,-,柯莫哥洛夫,(Chapman-,Kolmogorov,),方程，简称,C-K,方程,.,C-K,方程的实际背景,C-K,方程基于下述事实，即“从时刻,s,所处的状态,a,i,，,即,X(,s,)=,a,i,出发，经时段,u+v,转移 到状态,a,j,即,X(,s+u+v,)=,a,j,”,这一事件可分解成“从,X(,s,)=,a,i,”,出发，先经时段,u,转移到中间状态,a,k,(,k,=1,2),，,再从,a,k,经时段,v,转移 到状态,a,j,”,这样一些事件的和事件,.(,如下图,),a,i,a,j,O,s,s+u,s+u+v,方程（,2.1,）的证明如下：先固定 和,由于事件组“,X(,s+u,)=,a,k,”,k,=1,2,构成一划分,故有,P,ij,(,u+v,),=P,X(,s+u+v,)=,a,j,|X(,s,)=,a,i,又由条件概率定义和乘法定理，有,(,马氏链的齐次性,),将上式代入,(2.2),，即得所要证明的,C-K,方程,.,C-K,方程的证明,C-K,方程也可写成矩阵形式：,P(,u+v,)=P(,u,)P(,v,),利用,C-K,方程我们容易确定,n,步转移概率,事实上,在,(2.1),式中令,u,=1,v,=,n,-,1,，,得递推关系：,P,(,n,),=P,(,1,),P,(,n,-,1),=P P,(,n,-,1),从而可得,P(,n,)=,P,n,就是说，对齐次马氏链而言，,n,步,转移概率矩阵是,一,步转移概率矩阵的,n,次方,.,进而可知，齐次马氏链的有限维分布可由初始分布与,一,步转移概率完全确定,.,例,1,设,X,n,n,0,是具有三个状态,0,1,2,的齐次马氏链，,一,步转移概率矩阵为,初始分布,p,i,(0)=,P,X,0,=,i,=1/3,i=,0,1,2.,试求,(i),P,X,0,=0,X,2,=1;(ii)PX,2,=1,解 先求出二步转移概率矩阵,于是,(i),P,X,0,=0,X,2,=1=,P,X,0,=0 PX,2,=1|X,0,=0=p,0,(0)P,01,(2),0,1,2,0,1,2,3/4,1/4,0,1/4,1/2,1/4,0,3/4,1/4,P