工程数学 第24讲 本文件可从网址 http://math.vip.sina.com 上下载 (单击ppt讲义后选择'工程数学'子目录)

第十一章 马尔可夫链 §1 马尔可夫过程及其概率分布

在物理学中, 很多确定性现象遵从如下演变原则: 由时刻t0系统或过程所处的状态, 可以决定系统或过程在时刻t>t0所处的状态, 而无需借助于t0以前系统或过程所处状态的历史资料. 如微分方程初值问题所描绘的物理过程. 将这样的原则延伸到随机现象, 引入马尔可夫性或无后效性: 过程(或系统)在时刻t0所处的状态为已知条件下, 过程在时刻t>t0所处状态的条件分布与过程在时刻t0之前的状态无关. 即已经知道过程"现在"的条件下, 其"将来"不依赖于"过去".

设随机过程{X(t), tT}的状态空间为I. 如果对任意n个时间值t1<t2< 设随机过程{X(t), tT}的状态空间为I. 如果对任意n个时间值t1<t2<...<tn, n3, tiT, 在条件X(ti)=xi,xiI, i=1,2,...,n-1下, P{X(tn)xn|x(t1)=x1, X(t2)=x2,...,X(tn-1)=xn-1} =P{X(tn)xn|X(tn-1)=xn-1}, xnR, (1.1) 或写成 则称过程{X(t), tT}具有马尔可夫性或无后效性, 并称此过程为马尔可夫过程.

例1 设{X(t),t0}是独立增量过程, 且X(0)=0, 证明{X(t),t0}是一个马尔可夫过程. 证 由(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相互独立即可. 而当0<tj<tn-1<tn, 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)-xn-1 相互独立. 此时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.

对链的情形, 对任意的正整数n,r和0t1<t2<...< tr<m; ti, m, n+mT1, 有 其中aiI. 记上式右端为Pij(m,m+n), 称 Pij(m,m+n)=P{Xm+n=aj|Xm=ai} (1.3) 为马氏链在时刻m处于状态ai条件下, 在时刻m+n转移到状态aj的转移概率. 易知

转移概率组成的矩阵P(m,m+n)=(Pij(m,m+n))称为马氏链的转移概率矩阵, 上式表明此矩阵的每一行元素之和等于1 转移概率组成的矩阵P(m,m+n)=(Pij(m,m+n))称为马氏链的转移概率矩阵, 上式表明此矩阵的每一行元素之和等于1. 当转移概率Pij(m,m+n)只与i,j及时间间距n有关时, 把它记为Pij(n), 即 Pij(m,m+n)=Pij(n) 并称此转移概率具有平稳性. 同时也称此链是齐次的或时齐的. 以下仅限于讨论齐次马氏链.

在马氏链为齐次的情形下, 转移概率. Pij(n)=P{Xm+n=aj|Xm=ai}. (1 在马氏链为齐次的情形下, 转移概率 Pij(n)=P{Xm+n=aj|Xm=ai} (1.5) 称为马氏链的n步转移概率, P(n)=(Pij(n))为n步转移概率矩阵. 在以下的讨论中特别重要的是一步转移概率 pij=Pij(1)=P{Xm+1=aj|Xm=ai} 或由它们组成的一步转移概率矩阵

在上述矩阵的左侧和上边标上状态a1,a2,...,是为了显示pij是由状态ai一步转移到状态aj的概率.

例2 如图所示只传输数字0和1的系统串联系统中, 设每一级传真率为p, 误码率为q=1-p, 设一个单位时间传输一级, X0是第一级的输入, Xn是第n级的输出(n1). 则{Xn, n=0,1,2,...}是一随机过程, 状态空间I={0,1}, 当Xn=i, iI为已知时, Xn+1所处的状态的概率分布只与Xn=i有关, 而与时刻n以前的状态无关, 所以它是一个齐次的马氏链. 1 2 n X0 X1 X2 Xn-1 Xn

它的一步转移概率和一步转移概率矩阵分别为

例3 一维随机游动 设一醉汉Q在如图所示直线的点集I={1,2,3,4,5}上作随机游动, 且仅在1秒2秒等时刻发生游动 例3 一维随机游动 设一醉汉Q在如图所示直线的点集I={1,2,3,4,5}上作随机游动, 且仅在1秒2秒等时刻发生游动. 游动的概率规则是:如果Q现在位于点i(1<i<5), 则下一时刻以1/3概率向左或向右移动一格, 或以1/3的概率留在原处; 如果Q现在位于1(或5)这点上, 则下一时刻就以概率1移动到2(或4)上. 1和5这两点称为反射壁. 这叫带有两个反射壁的随机游动. 1 2 3 4 5

若以Xn表示时刻n时Q的位置, 不同的位置就是Xn不同的状态, 那么{Xn, n=0,1,2, 若以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横行改为(1,0,0,0,0).总之, 改变游动的概率规则, 就可得到不同方式的随机游动和相应的马氏链.

例4 排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成, 如图所示 例4 排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成, 如图所示. 服务规则是:先到先服务,后来者在等候室依次排队, 假定一个需要服务的顾客到达系统时发现系统内已有3个顾客(一个正在接受服务,两个在等候室排队), 则该顾客就离去. 等候室 服务台 系统 随机到达者 离去者

设时间间隔Dt内有一个顾客进入系统的概率为q, 有一原来被服务的顾客离开系统(即服务完毕)的概率为p 设时间间隔Dt内有一个顾客进入系统的概率为q, 有一原来被服务的顾客离开系统(即服务完毕)的概率为p. 又设当Dt充分小时, 在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的. 再设有无顾客来到与服务是否完毕是相互独立的. 现用马氏链来描述这个系统. 设Xn=X(nDt)表示时刻nDt时系统内的顾客数, 即系统的状态. {Xn, n=0,1,2,...}是一随机过程, 状态空间I={0,1,2,3}, 易知它是一马氏链, 下面计算一步转移概率.

p00: 在系统内没有顾客的条件下, 经Dt后仍然没有顾客的概率(此处是条件概率,以下同)p00=1-q p00: 在系统内没有顾客的条件下, 经Dt后仍然没有顾客的概率(此处是条件概率,以下同)p00=1-q. p01:系统内没有顾客的条件下, 经Dt后有一顾客进入系统的概率, p01=q. p10:系统内恰 有一顾客正在接受服务的条件下, 经Dt后系统内无人的概率. 它等于在Dt间隔内顾客因服务完毕而离去, 且无人进入系统的概率, p10=p(1-q).

类似地有 p11=pq+(1-p)(1-q) p12=(1-p)q p13=0 p21=p32=p(1-q), p22=pq+(1-p)(1-q) p23=q(1-p) pij=0(|i-j|2) p33=pq+(1-p).

于是一步转移概率矩阵为

在实际问题中, 一步转移概率通常可通过统计试验确定, 下面看一实例 在实际问题中, 一步转移概率通常可通过统计试验确定, 下面看一实例. 例5 某计算机房的一台计算机经常出故障, 研究者每隔15分钟观察一次计算机的运行状态, 收集了24小时的数据(共作97次观察). 用1表示正常状态, 用0表示不正常状态, 所得的数据序列如下: 111001001111111001111011111100111111111000110110111101101101011101110111101111110011011111100111 设Xn为第n(n=1,2,...,97)个时段的计算机状态,

可以认为它是一个齐次马氏链, 状态空间I={0,1}

例6 前例中计算机从某状态0的条件下能连续正常工作3个时段的条件概率为多少 例6 前例中计算机从某状态0的条件下能连续正常工作3个时段的条件概率为多少? 解 由题意可得 P{X1=1,X2=1,X3=1|X0=0} =P{X0=0,X1=2,X2=1,X3=1}/P{X0=0} =P{X0=0}P{X1=1|X0=0}P{X2=1|X1=1,X0=0} P{X3=1|X2=1,X1=1,X0=0}/P{X0=0} =P{X1=1|X0=0}P{X2=1|X1=1}P{X3=1|X2=1}

现在研究齐次马氏链的有限维分布. 首先, 记. pj(0)=P{X0=aj}, ajI, j=1,2,. 称它为马氏链的初始分布 现在研究齐次马氏链的有限维分布. 首先, 记 pj(0)=P{X0=aj}, ajI, j=1,2,.... 称它为马氏链的初始分布. 再看马氏链在任一时刻nT1的一维分布: pj(n)=P{Xn=aj}, ajI, j=1,2,.... (1.6) 又有

一维分布(1. 6)也可用行向量表示成. p(n)=(p1(n),p2(n),. ,pj(n),. ). (1 一维分布(1.6)也可用行向量表示成 p(n)=(p1(n),p2(n),...,pj(n),...). (1.6)' 这样, 利用矩阵乘法(I是可列无限集时, 仍用有限阶矩阵乘法的规则确定矩阵之积的元), p(n)=p(0)P(n). (1.7)' 此式表明, 马氏链在任一时刻nT1时的一维分布由初始分布p(0)和n步转移矩阵所确定.

又, 对于任意n个时刻t1<t2<...<tn, tiT1,以及状

由此, 并结合(1. 7)或(1. 7)'可知: 马氏链的有限维分布同样完全由初始分布和转移概率所确定 由此, 并结合(1.7)或(1.7)'可知: 马氏链的有限维分布同样完全由初始分布和转移概率所确定. 总之, 转移概率决定了马氏链运动的统计规律.因此, 确定马氏链的任意n步转移概率就成为马氏链理论中的重要问题之一.

§2 多步转移概率的确定

设{X(n),n=0,1,2,...}是一齐次马氏链, 则对于任意的u,vT1, 有 这是切普曼-科尔莫戈罗夫方程,简称C-K方程. ak aj ai s s+u s+u+v t O

C-K方程基于下述事实, 即"从时刻t所处的状态ai, 即X(s)=ai出发, 经时段u+v转移到状态aj, 即X(s+u+v)=aj" 这一事件可分解成"从X(s)=ai出发, 先经时段u转移到中间状态ak(k=1,2,...), 再从ak经时段v转移到状态aj"这样一些事件的和事件. 先固定akI和sT1, 由条件概率和乘法定理, P{X(s+u+v)=aj, X(s+u)=ak|X(s)=ai} =P{X(s+u)=ak|X(s)=ai} P{X(s+u+v)=aj|X(s+u)=ak, X(s)=ai} =Pik(u)Pkj(v). (2.2)

又由于事件组"X(s+u)=ak",k=1,2,...构成一划分, 故有 Pij(u+v)=P{X(s+u+v)=aj|X(s)=ai} 将(2.2)式代入上式, 即得所要证明的C-K方程. C-K方程也可写成矩阵形式: P(u+v)=P(u)P(v). (2.1)'

P(u+v)=P(u)P(v). (2. 1)' 利用C-K方程容易确定n步转移概率. 在(2 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次方. 进而可知, 链的有限维分布可由初始分布与一步转移概率完全确定.

例1 设{Xn,n0}是具有三个状态0,1,2的齐次马氏链, 一步转移概率矩阵为 初始分布pi(0)=P{X0=i}=1/3, i=0,1,2. 试求(i) P{X0=0,X2=1}; (ii)P{X2=1}.

解 先求出二步转移概率矩阵 于是(i)P{X0=0,X2=1}=P{X0=0}P{X2=1|X0=0}

例2 在§1例2中, (i)设p=0.9, 求系统二级传输后的传真率与三级传输后的误码率; (ii)设初始分布p1(0)=P{X0=1}=a, p0(0)=P{X0=0}=1-a. 又已知系统经n级传输后输出为1, 问原发字符是1的概率是多少? 解 先求出n步转移概率矩阵P(n)=Pn. 由于 有相异的特征值l1=1, l2=p-q,

由线性代数知识, 可将P表示成对角阵 的相似矩阵. 具体做法是:求出l1,l2对应的特征向量

则P=HLH-1. 于是, 容易算得 Pn=(HLH-1)n=HLnH-1

(i) 因此, 当p=0.9时, 系统二级传输后的传真率与三级传输后的误码率分别为 (ii)根据贝叶斯公式有

对于只有两个状态的马氏链, 一步转移概率矩阵一般可表示为 利用类似于例2的方法, 可得n步转移概率矩阵为

§3 遍历性

对于一般的两个状态的马氏链, 由(2.5)式可知, 当0<a,b<1时, Pij(n)有极限 即对于固定的状态j, 不管链在某一时刻从什么状态(i=0或1)出发, 通过长时间的转移, 到达状态j的概率都趋近于pj. 这就是所谓的遍历性. 又由于p0+p1=1, 所以(p0,p1)=p构成一分布律, 称它为链的极限分布.

设齐次马氏链的状态空间为I, 若对于所有ai,ajI, 转移概率Pij(n)存在极限 则称此链具有遍历性, 又若 , 则同时称p=(p1,p2,...)为链的极限分布.

齐次马氏链在什么条件下才具有普遍性. 如何求出它的极限分布. 这问题在理论上已经圆满解决, 但叙述它需要较多篇幅 齐次马氏链在什么条件下才具有普遍性?如何求出它的极限分布?这问题在理论上已经圆满解决, 但叙述它需要较多篇幅. 下面仅就只有有限个状态的链, 即有限链的遍历性给出一个充分条件.

定理 设齐次马氏链{Xn, n1}的状态空间为I={a1,a2,. ,aN} 定理 设齐次马氏链{Xn, n1}的状态空间为I={a1,a2,...,aN}. P是它的一步转移概率矩阵, 如果存在正整数m, 使对任意的ai,ajI, 都有 Pij(m)>0, i,j=1,2,...,N, (3.1) 则此链具有遍历性, 且有极限分布p=(p1,p2,...,pN), 它是方程组 p=pP或即 的满足条件 的唯一解.

依照定理, 为证有限链是遍历的, 只需找一正整数m, 使m步转移概率矩阵Pm无零元. 而求极限分布p的问题, 化为求解方程组(3.2)的问题. 注意, 方程组(3.2)中仅N-1个未知数是独 在定理的条件下, 马氏链的极限分布又是平稳分布. 意即, 若用p作为链的初始分布, 即p(0)=p, 则链在任一时刻nT1的分布p(n)永远与p一致. 事实上, 由(1.7)',(2.3)和(3.2)式有 p(n)=p(0)P(n)=pPn=pPn-1=...=pP=p.

例1 试说明§1例3中, 带有两个反射壁的随机游动是遍历的, 并求其极限分布(平稳分布) 例1 试说明§1例3中, 带有两个反射壁的随机游动是遍历的, 并求其极限分布(平稳分布). 解 为简便计, 以符号""代表转移概率矩阵的正的元. 于是, 由例3中的一步转移概率矩阵 P(2)=P2=

P(4)=P4= 即P(4)无零元, 由定理, 链是遍历的. 再根据(3.2)和(3.3)式, 写出极限分布p=(p1,p2,...,p5)满足的方程组.

先由前四个方程, 解得3p1=p2=p3=p4=3p5. 将它们代入最后一个方程, 解得极限分布为 p=(1/11,3/11,3/11,3/11,1/11).

例2 试说明§1例4(排队模型)中的链是遍历的, 并求其极限分布. 解 依照例1, 由中的一步转移概率矩阵P, 可算得P(3)=P3无零元 例2 试说明§1例4(排队模型)中的链是遍历的, 并求其极限分布. 解 依照例1, 由中的一步转移概率矩阵P, 可算得P(3)=P3无零元. 根据定理, 链是遍历的, 而极限分布p=(p0,p1,p2,p3)满足下列方程组:

解出的唯一解为 p0=p3(1-q)3/C, p1=p2q(1-q)2/C, p2=pq2(1-q)(1-p)/C, p3=q3(1-p)2/C, 其中C=p3(1-q)3+p2q(1-q)2+pq2(1-q)(1-p)+q3(1-p)2. 假若在此例中, p=q=1/2, 则可算得此时的极限分布为 p=(1/7,2/7,2/7,2/7). 这就是说, 经过相当长时间后, 系统中无人的情形约占14%的时间, 而系统中有一人,二人,三人的情形约各占29%的时间.

例3 设一马氏链的一步转移概率矩阵为 解 先算得

进一步可验证: 当n为奇数时, P(n)=P(1)=P; n为偶数时, P(n)=P(2). 这表明对任一固定的j( 此链不具遍历性.

作业 第十一章习题 第374页 第7题

请提问