《{企业通用培训}马尔科夫链培训讲义》由会员分享,可在线阅读,更多相关《{企业通用培训}马尔科夫链培训讲义(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(
15、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的概率为,对于只有两个状态的马氏链,一步转移概率矩阵一般可表示为: 利用类似于例2的方法,可得n步转移概率矩阵为 11.3遍历性 对于一般的两个状态的马氏链,当0a, b1时,pij(n)有极限,上述极限的意义是:对固定的状态 j,不管链在某一时刻从什么状态(I=0或1)出发,通过长时间的转移,到达状态 j的概率都趋近 于 。这就是所谓的遍历性。又由于 , 所以 构成一分布律,称它为链的极限分布。 另外,如若我们能用其他简便的方法直接由一步转移