《数理统计与随机过程马尔科夫链.pptx》由会员分享，可在线阅读，更多相关《数理统计与随机过程马尔科夫链.pptx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、11.1 马尔可夫过程及其概率分布 在物理学中，很多确定性现象遵从如下演变原则：由时刻t0 0系统或过程所处的状态，可以决定系统或过程在时刻t t0所处的状态，而无需借助于t0以前系统或过程所处状态的历史资料。如微分方程问题所描绘的物理过程就属于这类确定性现象。把上述原则延伸到随机现象，即当一物理系统或过程遵循的是某种统计规律时，可仿照上面的原则，引入以下的马尔可夫性或无后效性：过程(或系统)在时刻t0所处的状态为已知的条件下，过程在时刻tt0所处状态的条件分布与过程在t0之前所处的状态无关。通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。第1页/共33页 现用分布函
2、数来表述马尔可夫性.设随机过程X(t),t T的状态空间为I。如果对时间t的任意n个数值t1t2 tn,n3,ti T，在条件X(ti)=xi,xiI,i=1,2,n-1下,X(tn)的条件分布函数恰等于在条件X(tn-1)=xn-1下X(tn)的条件分布函数则称过程X(t),t T具有马尔可夫性或无后效性，并称此过程为马尔可夫过程。(1.1)第2页/共33页例1 1 设X(t),t 0是独立增量过程，且X(0)=0，证明X(t),t 0是一个马尔可夫过程。证 由(1.1)式知，只要证明在已知X(tn-1)=xn-1的条件下X(tn)与X(tj),j=1,2,n-2相互独立即可。现由独立增量过
3、程的定义知道，当0tjtn-1tn,j=1,2,n-2时，增量X(tj)-X(0)与X(tn)-X(tn-1)相互独立。根据条件X(0)=0和X(tn-1)=xn-1,即有X(tj)与X(tn)-X(tn-1)相互独立。再由第三章4定理知，此时X(tn)与X(tj)，j=1,2,n-2相互独立。这表明X(t)具有后无效性,即X(t),t 0是一个马尔可夫过程。由上例知，泊松过程是时间连续状态离散的马氏过程；维纳过程是时间状态都连续的马氏过程。第3页/共33页 时间和状态都是离散的马尔可夫过程称为马尔可夫链，简称马氏链，记为Xn=X(n),n=0,1,2,，它可以看作在时间集T1=0,1,2,上
4、对离散状态的马氏过程相继观察的结果.我们约定记链的状态空间I=a1,a2,ai R。在链的情形，马尔可夫性通常用条件分布律来表示，即对任意的正整数n,r和0t1t2 trm；m,n T1，有(1.2)其中ai I。记上式右端为Pij(m,m+n),我们称条件概率 Pij(m,m+n)=PXm+n=aj Xm=ai为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率。(1.3)第4页/共33页 由于链在时刻m从任何一状态ai出发，到另一时刻m+n，必然转移到a1,a2,诸状态中的某一个，所以(1.4)由转移概率组成的矩阵P(m,m+n)=(Pij(m,m+n)称为马氏链的转移
5、概率矩阵。由(1.4)式知，此矩阵的每一行元之和等于1。当转移概率Pij(m,m+n)只与i,j及时间间距n有关时，把它记为Pij(n)，即 Pij(m,m+n)=Pij(n)并称此转移概率具有平稳性。同时也称此链是齐次的或时齐的。以下我们限于讨论齐次马氏链。第5页/共33页 在马氏链为齐次的情形下，由(1.3)式定义的转移概率 Pij(n)=PXm+n=aj Xm=ai 称为马氏链的n步转移概率，P(n)=(Pij(n)为n步转移概率矩阵。在以下的讨论中特别重要的是一步转移概率 Pij=Pij(1)=PXm+1=aj Xm=ai 或由它们组成的一步转移概率矩阵在上述矩阵的左侧和上边标上状态a
6、1,a2,是为了显示Pij是由状态ai经一步转移到状态aj的概率。第6页/共33页例2（0-1传输系统）在如下图只传传输数字0和1的串联系统中，设每一级的传真率（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）为p，误码率为q=1-p，并设一个单位时间传输一级，X0是第一级的输入，Xn是第n级的输出(n1)，那么Xn,n=0,1,2,是一随机过程，状态空间I=0,1，而且当Xn=i,iI为已知时,Xn+1所处的状态的概率分布只与Xn=i 有关，而与时刻n以前所处的状态无关，所以它是一个马氏链，而且还是齐次的。它的一步转移概率和一步转移概率分别为和第7页/共33页例2 一维随机游动
7、 设一醉汉Q在如下图所示直线的点集I=1,2,3,4,5上作随机游动，且仅在1秒、2秒等时刻发生游动。游动的概率规则是：如果Q现在位于点i(1i5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在位于1(或5)这点上，则下一时刻就以概率1移动到2(或4)这一点上。1和5这两点称为反射壁。上面这种游动称为带有两个反射壁的随机游动。第8页/共33页 若以Xn表示时刻n时Q的位置，不同的位置就是Xn的不同状态，那么 Xn,n=0,1,2是一随机过程，状态空间就是I，而且Xn=i,i I为已知时，Xn+1所处的状态的概率分布只与Xn=i 有关，而与Q在时刻n以前如何
8、达到i是完全无关的，所以 Xn,n=0,1,2是一马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为010001/31/31/30001/31/31/30001/31/31/3000101 2 3 4 512345和P=第9页/共33页 如果把1这一点改为吸收壁，即是说Q一旦到达1这一点，则就永远留在点1上，此时，相应链的转移概率矩阵只须把P中的第一横行改为(1,0,0,0,0)。总之，改变游动的概率规则,就可得到不同方式的随机游动和相应的马式链。随机游动的思想在数值计算方法方面有重要应用。例4 排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成，见图11-3。服务规
9、则是：先到先服务，后来者首先需在等候室。假定一顾客到达系统时发现系统内已有3个顾客(一个正在接受服务，两个在等候室排队)，则该顾客即离去。设时间间隔t内有一个顾客进入系统的概率为q，有一原来被服务的顾客离开系统(即服务完毕)的概率为p。又设当t充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的。再设有无顾客来到与服务是否完毕是相互独立。现用马氏链来描述这个服务系统。第10页/共33页图11-3 设Xn=X(nt)表示时刻nt 时系统内的顾客数，即系统的状态,Xn,n=0,1,2 是一随机过程,状态空间I=0,1,2,3,可知它是一个齐次马氏链。下面来计算此马氏链的一步转移概率。
10、p00 在系统内没有顾客的条件下，经t 后仍没有顾客的概率(此处是条件概率，以下同)p00=1-q.p01-在系统内没有顾客的条件下，经t 后有一顾客进入系统的概率，p01=q.p10-系统内恰有一个顾客正在接受服务的条件下，经t后系统内无人的概率，它等于在t 间隔内顾客因服务完毕而离去，且无人进入系统的概率，p10=p(1-q)第11页/共33页 p11 系统内恰有1个顾客的条件下，在t 间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率。p11=pq+(1-p)(1-q).p12 正在接受服务的顾客继续要求服务，且另一个顾客进入系统的
11、概率p12=q(1-p).p13 正在接受服务的顾客继续要求服务，且在t 间隔内有两个顾客进入系统的概率，由假设，后者实际上是不可能发生的，p13=0.类似地，有p21=p32=p(1-q),p22=pq+(1-p)(1-q),p23=q(1-p),pij=0(|i-j|2).p33 一人因服务完毕而离去且另一人将进入系统，或者无人离开系统的概率，p33=pq+(1-p)第12页/共33页 于是该马氏链的一步转移概率矩阵为 在实际问题中，一步转移概率通常可通过统计试验确定，下面看一实例。例5 计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共
12、作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111第13页/共33页设Xn为第n(n=1,2,97)个时段的计算机状态,可以认为它是一个马氏链,状态空间I=0，1.96次状态转移的情况是:0 0,8次；0 1,18次；1 0,18次；1 1,52次.因此，一步转移概率可用频率近似地表示为第14页/共33页例6（续例5）若计算机在前一段(15分钟)的状态为0，问在此条件下从此时段起
13、此计算机能连续正常工作3刻钟(3个时段)的概率为多少？解 由题意，某一时段的状态为0就是初始状态为0，即X 0=0。由乘法公式、马氏性和齐次性得，所求条件概率为第15页/共33页 接着，我们来研究齐次马氏链的有限维分布。首先，记称它为马氏链的初始分布。再看马氏链在任意时刻n T1的一维分布：显然，应有 由全概率公式即(1.6)(1.7)一维分布(1.6)也可用行向量表示成 p(n)=(p1(n),p2(n),pj(n),)这样，利用矩阵乘法(I是可列无限集时，仍用有限阶矩阵乘法的规则确定矩阵之积的元)，(1.7)式可写成 p(n)=p(0)P(n)此式表明，马氏链在任一时刻nT1时的一维分布由
14、初始分布 p(0)和n 步转移概率矩阵所确定。(1.6)(1.7)第16页/共33页 又,对于任意n个时刻t1t2 tn,ti T1 以及状态 ，马氏链的n维分布：(1.8)由此，并结合(1.7)或(1.7)可知：齐次马氏链的有限维分布同样完全由初始分布和转移概率确定。总之，转移概率决定了马氏链的统计规律。因此，确定马氏链的任意n步转移概率就成为马氏链理论中的重要问题之一。第17页/共33页 11.2 多步转移概率的确定 为了确定齐次马氏链的n步转移概率Pij(n)，首先介绍Pij(n)所满足的基本方程。设X(n),n T1是一齐次马氏链,则对任意的u,v T1,有 方程(2.1)就是著名的切
15、普曼-柯莫哥洛夫(Chapman-Kolmogorov)方程，简称C-K方程。C-K方程基于下述事实，即“从时刻s所处的状态ai，即X(s)=ai出发，经时段u+v转移到状态 aj,即X(s+u+v）=aj”这一事件可分解成“从X(s)=ai 出发，先经时段u转移到中间状态ak(k,=1,2)，再从ak经时段v转移到状态 aj”这样一些事件和事件(见图11-4)。第18页/共33页图 11-4 方程(2.1)的证明如下：先固定ak I 和sT1，由条件概率定义和乘法定理，有(2.2)第19页/共33页又由于事件组“X(s+u)=ak”,k=1,2,构成一划分，故有将(2.2)式代入上式，即得所
16、要证明的C-K方程。C-K方程也可写成矩阵形式：P(u+v)=P(u)P(v)(2.1)利用C-K方程我们容易确定n步转移概率。事实上，在(2.1)式中令u=1,v=n-1，得递推关系：P(n)=P(1)P(n-1)=PP(n-1),从而可得 P(n)=Pn.(2.3)就是说，对齐次马氏链而言，n步转移概率矩阵是一步转移概率矩阵的n次方。进而可知，齐次马氏链的有限维分布可由初始与一步转移概率完全确定。第20页/共33页例1 设Xn,n0是具有三个状态0,1,2的齐次马氏链，一步转移概率矩阵为初始分布pi(0)=PX0=i=1/3,i=0,1,2.试求:(i)PX0=0,X2=1;(ii)PX2
17、=1解 先求出二步转移概率矩阵于是 (i)(ii)由(1.7)式，第21页/共33页例2 在1例2中,(i)设p=0.9,求系统二级传输后的传真率与三级传输后的误码率；(ii)设初始分布P1(0)=PX0=1=，P0(0)=P X0=0=1-，又已知系统经n级传输后输出为1，问原发字符也是1的概率是多少？解 先求出n步转移概率矩阵P(n)=Pn。由于有相异的特征值1=1,2=p-q,由线形代数知识，可将P表示成对角阵的相似矩阵。具体做法是：求出1,2对应的特征相量(q=1-p)(q=1-p)第22页/共33页令则(2.4)(i)由(2.4)式可知，当p=0.9时，系统经二级传输后的传真率与三级
18、传输的误码率分别为 (ii)根据贝叶斯公式，当已知系统经n级传输后输出为1，原发字符也是1的概率为第23页/共33页 对于只有两个状态的马氏链，一步转移概率矩阵一般可表示为：利用类似于例2的方法，可得n步转移概率矩阵为第24页/共33页11.3 遍历性 对于一般的两个状态的马氏链，由(2.5)式可知,当0a,b1 时就可得到n步转移概率的近似值：pij(n)j 第25页/共33页 一般，设齐次马氏链的状态空间为 I，若对于所有ai,ajI，转移概率Pij(n)存在极限或则称此链具有遍历性，又若 ，则同时称 为链的极限分布。齐次马氏链在什么条件下才具有遍历性？如何求出它的极限分布？这问题在理论上
19、已经完满解决,下面仅就只有有限个状态的链,即有限链的遍历性给出一个充分条件。第26页/共33页定理 设齐次马氏链Xn,n 1的状态空间为I=a1,a2,aN,P是它的一步转移概率矩阵，如果存在整数 m，使对任意的ai,ajI，都有 Pij(m)0,i,j=1,2,N,(3.1)则此链具有遍历性,且有极限分布=(1,2,N)，它是方程组 =P或即 (3.2)的满足条件 (3.3)的唯一解。依照定理，为证有限链是遍历的，只需要找一正整数m，使m步转移概率矩阵 Pm无零元。而求极限分布 的问题，化为求解方程组(3.2)的问题。注意，方程组(3.2)中仅N-1个未知数是独立的，而唯一解可用归一条件 确
20、定。第27页/共33页 在定理的条件下，马氏链的极限分布又是平稳分布。意即，若用 作为链的初始分布，即p(0)=,则链在任一时刻nT1的分布p(n)永远与 一致。事实上，有 p(n)=p(0)p(n)=pn=pn-1=p=例1 试说明1例2中，带有两个放射壁的随机游动是遍历的，并求其极限分布(平稳分布)。解 为简便计，以符号“”代表转移概率矩阵的正元素，于是，由1例2中的一步转移概率矩阵 P，得第28页/共33页即P(4)无零元。由定理，链是遍历的。再根据(3.2)和(3.3)式,写出极限分布 =(1,2,5)满足的方程组先由前四个方程，解得：3 1=2=3=4=3 5，将它们代入归一条件，即
21、最后一个方程，解之，得唯一解：1=5=1/11,2=3=4=3/11所以极限分布为 =(1/11,3/11,3/11,3/11,1/11)。这个分布表明：经过长时间游动之后，醉汉Q位于i点(1i5)的概率约为3/11，位于点1(或5)的概率约为1/11。第29页/共33页例2 试说明1例4(排队模型)中的链是遍历的，并求其极限分布。解 依照例1，由1例4中的一步转移概率矩阵P，可算得P(3)=P3 无零元。根据定理，链是遍历的。而极限分布 =(0,1,2,3)满足下列方程组:解之，得唯一解第30页/共33页 假若在此例中，设p=q=1/2，则可算得 0=1/7 0.14,1=2=3=2/7 0
22、.29,即此时极限分布为 =(1/7,2/7,2/7,2/7).这就是说，经过相当长的时间后，系统中无人的情形约占14%的时间，而系统中有一人、二人、三人的情形各占29%的时间。例3 设一马氏链的一步转移概率矩阵为试讨论它的遍历性。第31页/共33页解 先算得进一步可验证：当n为奇数时，P(n)=P(1)=P；n为偶数时，P(n)=P(2)。这表明对任一固定的 j(=1,2,3,4)，极限都不存在。按定义，此链不具遍历性。马氏过程的内容除了讨论最简情形马氏链之外，还研究状态离散、时间连续的马氏过程和状态、时间都连续的马氏过程，它们都有比较完善的理论，而且讨论的主题也都是从各自场合的C-K方程出发，研究转移概率的确定方法和性质。本书除前面介绍的泊松过程和维纳过程这两个具体的马氏过程模型外不再作一般的介绍。第32页/共33页感谢您的观看。第33页/共33页