《数理统计与随机过程ch11》由会员分享，可在线阅读，更多相关《数理统计与随机过程ch11（39页珍藏版）》请在金锄头文库上搜索。
1、,数理统计与随机过程 第十一章,北京工业大学应用数理学院,第十一章 马尔可夫链,马尔可夫 (Markoff) 过程理论在近代物理、生物学、管理科学、经济、信息处理以及数字计算方法等方面都有重要应用。 本章首先从随机过程在不同时刻状态之间的特殊的统计联系，引入马尔可夫过程的概念。然后，对马尔可夫链(状态、时间都是离散的)的两个基本问题，即转移概率的确定及遍历性问题作介绍。,11.1 马尔可夫过程及其概率分布,在物理学中，很多确定性现象遵从如下演变原则：由时刻 t0 系统(或过程)所处的状态，可以决定系统(或过程)在时刻 t t0 所处的状态，而无需借助于 t0以前系统(或过程)所处状态的历史资料
2、。如: 微分方程问题所描绘的物理过程就属于这类问题。 这是对确定性现象而言的，将其延伸到随机性现象。,当一物理系统(或过程)遵循的是某种统计规律时，可仿照上面的原则，引入以下的马尔可夫性或无后效性：过程(或系统)在时刻 t0 所处的状态为已知的条件下，过程在时刻 tt0 所处状态的条件分布与过程在 t0 之前所处的状态无关。 通俗地说，就是在已经知道过程(或系统)“现在状态”的条件下，其“将来状态”的概率不依赖于“过去状态”。,设随机过程X(t), t T的状态空间为I。如果对时间 t 的任意n个取值 t1t2 tn, n3, ti T，在条件X(ti)=xi, xiI, i=1,2, , n
3、-1下, X(tn)的条件分布函数等于在条件X(tn-1)=xn-1下X(tn)的条件分布函数，即,则称过程X(t), t T具有马尔可夫性或无后效性，称此过程为马尔可夫过程。,例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相互独立即可。 由独立增量过程的定义知：当 0tjtn-1tn, j=1, 2, , n-2时，增量 X(tj)-X(0) 与 X(tn)-X(tn-1) 相互独立。 根据X(0)=0和X(tn-1
4、)=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是一个马尔可夫过程。 由上例知，泊松过程是时间连续状态离散的马氏过程；维纳过程是时间状态都连续的马氏过程。,时间和状态都离散的马尔可夫过程称为马尔可夫链，简称马氏链，记为Xn=X(n), n =0, 1, 2, 。它可以成时间集T1=0, 1, 2, 上对离散状态的马氏过程相继观察的结果。我们约定，马氏链的状态空间为I=a1, a2, , ai R。,其中ai I。 记(1.2)式等号
5、后的项为pij(m, m+n), 称条件概率 pij(m, m+n)=PXm+n= ajXm = ai (1.3) 为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的n步转移概率。,马氏链的马尔可夫性通常用条件概率分布或条件分布律来刻画，即对任意的正整数 n, r 和 0t1t2 trm；m, n T1，有,由于链在时刻m从任何一状态ai出发，到另一时刻 m+n，必然转移到a1, a2, 状态中的某一个，故,由转移概率所组成的矩阵 P(m, m+n)=( pij(m, m+n) ) 称为马氏链的 n步转移概率矩阵。由(1.4)式知，矩阵的每一行元素之和都等于1。,当 n 步转移概
6、率 pij(m, m+n) 只与i, j及时间间距 n 有关时，将其记成 pij(n)，即 pij(m, m+n)= pij(n) 并称此转移概率具有平稳性。同时也称马氏链是齐次的或时齐的。以下我们讨论齐次马氏链。,在马氏链为齐次情形下，记一步转移概率为 pij=pij(1)=PXm+1= ajXm = ai 一步转移概率矩阵为,在上述矩阵的左侧和上边标上状态a1, a2, 是为了显示Pij是由状态ai经一步转移到状态aj的概率。,例2 （0-1传输系统）在如下图只传传输数字0和1的串联系统中，设每一级的传真率（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）为p，误码率为q=1
7、-p，并设一个单位时间传输一级， X0是第一级的输入，Xn是第n级的输出(n1)，那么Xn, n =0,1,2, 是一随机过程，状态空间I=0,1，而且当Xn=i , iI为已知时, Xn+1所处的状态的概率分布只与Xn=i 有关，而与时刻n以前所处的状态无关，所以它是一个马氏链，而且还是齐次的。它的一步转移概率和一步转移概率矩阵分别为,例2 一维随机游动 设一醉汉Q在如下图所示直线的点集I=1,2,3,4,5上作随机游动，且仅在1秒、2秒等时刻发生游动。游动的概率规则是：如果Q现在位于点i(1i5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在位于1(或
8、5)这点上，则下一时刻就以概率1移动到2(或4)这一点上。1和5这两点称为反射壁。上面这种游动称为带有两个反射壁的随机游动。,若以Xn表示时刻n时Q的位置，不同的位置就是Xn的不同状态，那么 Xn , n=0,1,2是一随机过程，状态空间就是I，而且Xn=i, i I为已知时， Xn+1所处的状态的概率分布只与Xn= i 有关，而与Q在时刻n以前如何达到i是完全无关的，所以 Xn , n=0,1,2是一马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为,如果把1这一点改为吸收壁，即是说Q一旦到达1这一点，则就永远留在点1上，此时，相应链的转移概率矩阵只须把P中的第一横行改为(1,
9、0,0,0,0)。总之，改变游动的概率规则,就可得到不同方式的随机游动和相应的马式链。 随机游动的思想在数值计算方法方面有重要应用。,例4(排队模型): 设服务系统由一个服务员和只可以容 纳两个人的等候室组成，见图11-3。服务规则是：先 到先服务，后来者首先需在等候室。,图11-3,假定一顾客到达系统时发现系统内已有3个顾客 (一个正在接受服务，两个在等候室排队)，则该顾客 即离去。设时间间隔t内有一个顾客进入系统的概 率为q，有一原来被服务的顾客离开系统(即服务完毕) 的概率为p。 又设当t充分小时，在这时间间隔内多于一个顾 客进入或离开系统实际上是不可能的。再设有无顾 客来到与服务是否完
10、毕是相互独立。现用马氏链来 描述这个服务系统。,设Xn=X(nt)表示时刻nt 时系统内的顾客数，即系统的状态, Xn , n=0,1,2 是一随机过程,状态空间I=0,1,2,3,可知它是一个齐次马氏链。下面来计算此马氏链的一步转移概率。 p00 在系统内没有顾客的条件下，经t 后仍没有顾客的概率(此处是条件概率，以下同) p00=1-q. p01-在系统内没有顾客的条件下，经t 后有一顾客进入系统的概率，p01=q. p10-系统内恰有一个顾客正在接受服务的条件下，经t后系统内无人的概率，它等于在t 间隔内顾客因服务完毕而离去 ，且无人进入系统的概率，p10=p(1-q).,p11 系统内
11、恰有1个顾客的条件下，在t 间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率。 p11=pq+(1-p)(1-q). p12 正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率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 一人因服务完毕而离去且另一人将进入系统，或者无人离
12、开系统的概率， p33 = pq+(1-p),于是，该马氏链的一步转移概率矩阵为,在实际问题中，一步转移概率通常可通过统计试验确定，下面看一实例。,例5 ：某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下： 1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111,设Xn为第n( n =1,2,97)个时段的计算机状态,可以认为它
13、是一个马氏链,状态空间I=0，1.96次状态转移的情况是: 0 0,8次； 0 1,18次； 1 0,18次； 1 1,52次. 因此，一步转移概率可用频率近似地表示为,例6（续例5） 若计算机在前一段(15分钟)的状态为0，问在此条件下从此时段起此计算机能连续正常工作3刻钟(3个时段)的概率为多少？ 解 由题意，某一时段的状态为0就是初始状态为0，即 X 0= 0。由乘法公式、马氏性和齐次性得，所求条件概率为,接着，我们来研究齐次马氏链的有限维分布。首先，记,称它为马氏链的初始分布。再看马氏链在任意时刻n T1的一维分布：,显然，应有 由全概率公式,即,(1.6),(1.7),一维分布(1.
14、6)也可用行向量表示成 p(n)=( p1(n), p2(n), pj(n),) 这样，利用矩阵乘法(I是可列无限集时，仍用有限阶矩阵乘法的规则确定矩阵之积的元)，(1.7)式可写成 p(n) = p(0)P(n) 此式表明，马氏链在任一时刻nT1时的一维分布由初始分布 p(0)和n 步转移概率矩阵所确定。,(1.6) ,(1.7) ,又,对于任意n个时刻t1t2 tn, ti T1 以及状态 ，马氏链的n维分布：,(1.8),由此，并结合(1.7)或(1.7) 可知：齐次马氏链的有限维分布同样完全由初始分布和转移概率确定。 总之，转移概率决定了马氏链的统计规律。因此，确定马氏链的任意n步转移
15、概率就成为马氏链理论中的重要问题之一。,11.2 多步转移概率的确定,为了确定齐次马氏链的n步转移概率Pij(n) ，首先介绍Pij(n) 所满足的基本方程。 设X(n), n T1是一齐次马氏链,则对任意的u,v T1 ,有 方程(2.1)就是著名的切普曼-柯莫哥洛夫(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”这样一些事件
16、和事件(见图11-4)。,图 11-4,方程(2.1)的证明如下：先固定ak I 和sT1，由条件概率定义和乘法定理，有,(2.2),又由于事件组“X(s+u)= ak”,k=1,2,构成一划分，故有,将(2.2)式代入上式，即得所要证明的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次方。 进而可知，齐次马氏链的有限维分布可由初始与一步转移概率完全确定。,
