《马尔科夫链培训课件.ppt》由会员分享，可在线阅读，更多相关《马尔科夫链培训课件.ppt（45页珍藏版）》请在金锄头文库上搜索。
1、第十一章 马尔科夫链,11.1马尔科夫过程及其概率分布 马尔科夫过程 若随机过程X(t)，tT对于任意的正整数n及 t1 t2tnT,其条件分布满足 PX (tn)xn| X(t1)=x1, X(tn-1)=xn-1 = PX (tn)xn| X(tn-1)=xn-1 或写成,马尔科夫链 时间和状态都是离散的马尔科夫过称 为马尔科夫链，简称马氏链。记为 Xn(t)=X(n)，n=0,1,2,. 链的状态空间：I=a1 ,a2, ,ai R,则称随机过程X(t)，tT 为马尔科夫过程。,条件转移概率,对任意得正整数n,m和0t1 t2tn m, m, ti ,n+m T1有 P(Xn+m=aj|
2、 Xt1=ai1, Xt2=ai2 , Xtr=atr ,X m=ai = P(Xn+m=aj| X m =ai ,其中ai I。则称条件概率 Pij(m,m+n)=pXm+n =aj |Xm =ai 为马氏链在时刻m,处于状态ai条件下，在时刻 m+n转移到状态aj的转移概率。,转移概率矩阵 由转移概率组成的矩阵 称为马氏链的转移概率矩阵 。此矩阵的每一行元素之和等于1。 当转移概率Pij(m,m+n)只与i,j及时间距n有关时，即当 时，称转移概率具有平稳性，同时也称此链 是齐次的或时齐的。,N步转移概率和n步转移矩阵,在马氏链为齐次的情形下，由上式定义的转移概率 称为马氏链的n步转移概率
3、 ， 则矩阵 为n步转移概率矩阵。 一步转移概率 由它们组成的一步转移概率矩阵,a1 a2 aj ,a1 a2 . ai .,其中pij是a1 ,a2,从ai状态转移到aj状态的概率,例1 （0-1传输系统）,在如下图只传输数字0和1的串联系统中， 定义传真率和误码率（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）为p，误码率为q=1-p； 设一个单位时间传输一级， X0是第一级的输入，Xn是第n级的输出（n1），那么 是一随机过程， 状态空间I=0,1，而且当Xn=i , iI为已知时， Xn+1所处的状态的概率分布只与Xn= 有关，而与时刻n以前所处的状态无关，所以它是一个
4、马氏链，而且还是齐次的它的一步转移概率和一步转移概率,1,2,n,X0,X1,Xn,X2,Xn-1,矩阵分别为 和 例2 一唯随机游戏 设一醉汉Q在如下图点集I=1，2，3，4，5上作随机游动，并且仅仅在1秒、2秒等时刻发生游动。 规律是：(1)如果Q现在位于点I(1I5),则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；(2)如果Q现在位于1（或5）这点上，则下一时刻就以概率1移动2（或4）这一点上。1和5这两点称为放射壁。上面这种游动称为带有两个放射壁的随机游戏动,0 1,1 2 3 4 5,若以Xn表示时刻n时Q的位置，不同的位置就是Xn的不同状态，那么 Xn ,
5、 n=0,1,2是一随机过程，状态空间就是I，而且Xn=I, i I为已知时， Xn+1所处的状态的概率分布只与Xn= i 有关，而与Q在时刻n以前如何达到是完全无关的，所以 Xn , n=0,1,2是一马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为,如果把一这一点改为吸收壁，即是说Q一旦到达1这一点，则就永远留在点一上，相应链的转移概率矩阵只须把p中的第一横行改为（1，0，0，0，0）。总之改变游动的概率规则，就可得到不同方式的随机游动和相应的马式链。 随机游动的思想在数值计算方法方面有重要应用。,1 2 3 4 5,1 2 3 4 5,例3 ：排队模型 服务系统组成：服务
6、员（1个）和等候室（2人）组成， 服务规则：先到先服务。假定一顾客到达系统时发现系统内已有3个顾客，则该顾客即离去， 设时间间隔t内，有一个顾客进入系统的概率为q，有被服务的顾客离开系统的概率为p， 设当t充分小时，多于一个顾客进入或离开系统实际上是不可能的， 设有无顾客来到与服务是否完毕是相互独立。,等候室,服务台,随机到达者,离去者,系 统,设Xn X（n t ）表示时刻n t 时系统内的顾客数，即系统的状态， 是一随机过程，状态空间I=0,1,2,3 ，可知它是一个齐次马氏链。下面来计算此马氏链的一步转移概率。 P00表示在系统内没有顾客的条件下，经t 后仍没有顾客的概率（此处是条件概率
7、，以下同） P00=1-q. P01-表示在系统内没有顾客的条件下，经t 后有一顾客进入系统的概率，P01=q. P10-系统内恰有一个顾客正在接受服务的条件下，经t 后,系统内无人的概率，它等于在t 间隔内顾客因服务完毕而离去 ，且无人进入系统的概率，P10=P（ 1 -q） P11系统内恰有顾客的条件下，在t 间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率。 P11 =pq+(1-p)(1-q). P12-正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率P12=q(1-q). P13-正在接受服务的顾客继续要求服务，且在
8、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) 于是该马氏链的一步转移概率矩阵为,在实际问题中，一步转移概率通常可通过统计实验确定。 例4 某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下
9、： 1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111 设Xn为第n（ n =1，2,97）个时段的计算机状态，可以认为它是一个马氏链，状态空间I=0，1.96次状态转移的情况是：,0 0,8次； 0 1,18次； 1 0,18次 ; 1 1,52次. 因此，一步转移概率可用频率近似地表示为,马氏链的有限维分布，先看马氏链在任一时刻n T1的 1)一维分布： 显然，应有 由全概率公式 即,一维分布也可用行向量表示成 P(n)=( P1(n) , P2
10、(n), Pj(n),) 这样，利用矩阵乘法（I是可列无限集时，仍用有限阶）矩阵乘法的规则确定矩阵之积的元素，可写成 P(n) = P(0)P(n)(矩阵)。 结论：马氏链在任一时刻n T1时的一维分布由初始分布 P(0)和n 步转移概率矩阵所确定。对于任意n个时刻 t1t2 t tn, ti T1以及状态 有： 马氏链的 n维分布：,由乘法公式,结论：由此可知，马氏链的有限维分布同样完全由初始分布和转移概率确定。 总之，转移概率决定了马氏链的统计规律。因此，确定马氏链的任意n步转移概率就成为马氏链理论中的重要问题之一。,例5（续例4）若计算机在前一段（15分钟）的状态为0，问从时段起此计算机
11、能连续正常工作一小时（4个时段）的概率为多少？ 解 由题意，前一时段的状态为0就是初始分布P0 （0） =PX 0= 0=1。计算机能连续正常工作4个时段的概率为 P=X0=0， X1 = 1， X2=2， X3= 1， X4=1 = p0 (0) p01 (1) p11 (1) p11 (1) p11 (1) =,11.2多步转移概率的确定,为了确定齐次马氏链的n步转移概率 ，首先介绍 所满足的基本方程。 设X（ n ）， n T1是一齐次马氏链，则对任意的u,v T1 ，有 这就是著名的切普曼-柯莫哥洛夫（Chapman-K0lmogorov）方程，简称C-K方程。,C-K方程的实际背景,
12、C-K方程基于下述事实，即“从时刻s所处的状态ai，即X (s)=a i出发，经时段u+u转移 到状态 aj ,即X(s+u+v）=aj”这一事件可分解成“从X（ s）=ai ”出发，先经时段u转移到中间状态ak(k,=1,2)，再从ak经时段v转移 到状态 aj”这样一些事件和事件。,ai,aj,O,s,s+u,s+u+v,方程（2.1）的证明如下：先固定 和 由条件概率定义和乘法定理， 马氏链的齐次性 又由于事件组“ X(s+u)= ak”,k=1,2,构成一划分，故有 Pij(u+v)=PX(s+u+v)= aj|X(s)=ai = 代入上式，即得所要证明的C-K方程。,C-K方程的证明
13、,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)= Pn, 就是说，对齐次马氏链而言， n步转移概率矩阵是一步转移概率矩阵的n次方。进而可知，链的有限维分布可由初始与一步转移概率完全确定。 例1 设Xn,n0是具有三个状态0，1，2的齐次马氏链，一步转移概率矩阵为,初始分布Pi（0）=PX0=i=1/3,i=0,1,2.试求(i)PX0=0, X2=1;(ii)PX2=1 解 先求出二步转移概率矩阵 于是
14、 (i)PX0= 0 ,X2=1=PX0=0 pX2=1| X0=0;=p0(0) p01(2)= (ii)由(1.7)式，p1（2)=PX2=1= p0(0),0 1 2,0 1 2,P=,0 1 2,P(2)= P2 =,0 1 2,=,P01 (2)+ P1 (0)P11 (2)+ P2(0) P21 (2) = 例2 在1例2中,（i）设p=0.9 , 求系统传输后的传真率与三级传输后的误码率；（ i i ）设初始分布P1 (0)= PX0 =1=a, P0 =P X0 = 0= 1 -a ，又已知系统经n级传输后输出为1，问原发字符也是1的概率是多少？ 解 先求出n步转移概率矩阵P(n)= Pn。由于 则令 得1=1， 2=p-q 则可将p表示成对角矩阵 的相似矩阵。,0 1,P=,0 1,1、求出1， 2的特征向量是 方法是令(1E-P)X=0及(2E-P)X=0,就可以求得e1,e2 令H=e1,e2 则有,(i)由此可知，当p=o.9时，系统经二级传输后的传真率与三级传输的误码率发表分别为 p11(2) =p00 (2)= p10(3) =p01(3)= (ii)根据贝叶斯公式，当已知系统经n级传输后输出为1，原发字符也是1的概率为,对于只有两个状态的马氏链，一步转移概率矩阵
