第5章-马尔可夫链

应用随机过程主讲教师段禅伦2011年秋季学期计算机学院研究生专业基础课程《应用数学基础》(AppliedStochasticprocesses)第5章马尔可夫链5.1引言本章,首先考察取有限个值或者可数个可能值的随机过程{Xn,n=0,1,2,…}.一般将这种随机过程的可能值的集合也记为{0,1,2,…}(即状态空间也是非负整数集).如果Xn=i,那么称随机过程在时刻n在状态i.设只要过程在状态i,就有一个固定的概率pij,使它在下一个时刻在状态j.我们有定义5.1.1若对于一切状态i0,i1,…,in-1,i,j与一切n≥0,有P{Xn+1=j|Xn=i,Xn-1=in-1,…,X1=i1,X0=i0}=P{Xn+1=j|Xn=i}=pij则称这样的随机过程称为马尔可夫链.并称由此式刻画的马尔马尔可夫链可夫链的特性为Markov性,亦称“无后效性”.此性质说明:要确定过程将来的状态,知道它此刻的状态就足够了,并不需要对它以往状况的认识.也就是说对于一个马尔可夫链,在给定过去的状态X0,X1,…,Xn-1和现在的状态Xn时,将来的状态Xn+1的条件分布独立于过去的状态而只依赖于现在的状态.pij表示过程处在状态i时,下一次转移到状态j的概率.由于概率值非负且过程必须转移到某个状态,所以有pij≥0,i,j≥0(即i,j∈I);pij=1,i=0,1,2,…(即i∈I)我们称P{Xn+1=j|Xn=i}=pij为Markov链{Xn,n=0,1,2,…}的一步转移概率,简称转移概率.0j(★)马尔可夫链由Markov链定义知P{X0=i0,X1=i1,…,Xn=in}=P{Xn=in|X0=i0,X1=i1,…,Xn-1=in-1}P{X0=i0,X1=i1,…,Xn-1=in-1}=P{Xn=in|Xn-1=in-1}P{X0=i0,X1=i1,…,Xn-1=in-1}=…=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1|Xn-2=in-2}…P{X1=i1|X0=i0}P{X0=i0}可见一旦Markov链的初始分布P{X0=i0}给定,其统计特性就完全由条件概率P{Xn=in|Xn-1=in-1}所决定.马尔可夫链如何确定这个条件概率,是Markov链理论和应用中的重要问题之一.•一般情况下,转移概率pij与状态i,j和时间n有关.当Markov链的转移概率P{Xn+1=j|Xn=i},只与状态i,j有关,而与n无关时,称Markov链为时齐的;否则,称为非时齐的.我们只讨论时齐Markov链,并简称为Markov链.当Markov链的状态为有限时,称为有限链;否则称为无限链.但无论状态是有限还是无限,我们都可以将pij(i,j∈{0,1,2,…})排成一个矩阵的形式.记为:P=(pij),它等于p00p01p02p03…p10p11p12p13…………………pi0pi1pi2pi3………………马尔可夫链称P为转移概率矩阵,一般简称为转移矩阵.转移概率矩阵具有性质(★).称具有此性质的矩阵为随机矩阵(随机矩阵是非负实数矩阵且每一行元素的和为1).例5.1(天气预报)假设明天下雨的机会只依赖于前一天的天气条件,即今天是否下雨,而不依赖过去的天气条件.且如果今天下雨,那么明天下雨的概率为α;若今天没下雨,明天下雨的概率为β.如果下雨,记过程在状态0;如果不下雨,记过程在状态1.如此,本例是一个两状态{0,1}的马尔可夫链,其转移概率矩阵是:P=(pij)==p00p01p10p11α1-αβ1-β马尔可夫链例5.2(一个通讯系统)考察一个传送数字0和1的通信系统.每个数字的传送必须经过几个阶段.在每个阶段有一个概率p使进入的数字在离开时不改变.以Xn记第n个阶段进入的数字,则{Xn,n=0,1,2,…}是一个两个状态{0,1}的马尔可夫链,具有转移概率矩阵:P=例5.3(随机游动)有一个醉汉在直线上做无限制的随机游动其状态i=0,±1,±2,….且pi,i+1=p=1-pi,i-1.这也是一个Markov链,其转移矩阵为:p1-p1-pp……………………q0p0…0000……0q0p…0000………………………0000…0q0p……………………P=马尔可夫链考虑一个包含两个生命状态S1和S2以及两个死亡状态S3和S4(即相异原因的非生命状态)的模型.若个体病愈,则认为它处于状态S1,若患病,则认为它处于S2,个体可以从S1,S2进入S3和S4,这是一个马尔可夫链的模型,转移概率矩阵为P=例5.5(赌徒的破产或称带吸收壁的随机游动)系统的状态是0到n,反映赌博者A在赌博期间拥有的钱数,当他输光或拥有钱数为n时,赌博停止;否则他将持续赌博,每次以概率p赢得1,以概率q=1-p输掉1.该系统的转移概率矩阵为p11p12p13p14p21p22p23p2400100001例5.4(一个简单的疾病死亡模型,Fix-Neyman(1951))马尔可夫链P=例5.6(带反射壁的随机游动)在例5.5中当A输光时将获得赞助1让他继续赌下去,就如同一个在直线上做随机游动的球在到达左侧0点处就立即反弹回1一样,这就是一个一侧带有反射壁的随机游动.此时P=1000…000q0p0…0000q0p…000………………0000…q0p0000…001(n+1)×(n+1)0100…000q0p0…0000q0p…000………………0000…q0p0000…001(n+1)×(n+1)马尔可夫链例5.7在任意给定的一天,一个人的心情或者是快乐的,或者是一般的,或者是郁闷的.如果今天她是快乐的,那么明天她分别以概率0.5,0.4和0.1是快乐的,一般的和郁闷的;如果今天她的心情一般,那么她明天分别以概率0.3,0.4和0.3是快乐的,一般的和郁闷的;如果今天她是郁闷的,那么她明天分别以概率0.2,0.3和0.5是快乐的,一般的和郁闷的.以Xn记她第n天的心情,则{Xn,n≥0}是一个三个状态{快乐,一般,郁闷}={0,1,2}的马尔可夫链,其转移概率矩阵0.50.40.10.30.40.30.20.30.5P=马尔可夫链例5.8(图上的简单随机游动)设有一蚂蚁在左图的图上爬行,当两个结点相邻时,蚂蚁将爬向它临近一点,并且,爬向任何一个邻近点的概率是相同的,则此Markov链的转移矩阵是下面给出一个如何将一个过程转变为马尔可夫链的例子.1362450½½000½0½000¼¼0¼¼000100000½00½000010P=马尔可夫链例5.9(将一个过程转变为马尔可夫链)假设今天是否下雨依赖于前两天的天气条件.如果过去的两天都下雨,那么明天下雨的概率为0.7;如果今天下雨但昨天没下雨,那么明天下雨的概率为0.5;如果昨天下雨但今天没下雨,那么明天下雨的概率为0.4;如果昨、今两天都没下雨,那么明天下雨的概率为0.2.假设在时间n的状态只依赖于在时间n-1是否下雨,那么上述模型就不是一个马尔可夫链.但是,当假定在任意时间的状态是由这天与前一天两者的天气条件所决定时,上面的模型就可以转变为一个马尔可夫链.换言之,可以假定过程处在:马尔可夫链状态0,如果昨天和今天都下雨;状态1,如果昨天没有下雨但今天下雨;状态2,如果昨天下雨但今天没有下雨;状态3,如果昨天和今天都没有下雨.这就将题目所给的过程转变成了一个具有4个状态的马尔可夫链,其转移概率矩阵为0.700.300.500.5000.400.600.200.8例5.10考虑订货问题.设某商店使用(s,S)订货策略,每天早上检查某商品的剩余量,设为x,则定购额为0,若x≥s;S-x,若x＜s.P=马尔可夫链设订货和进货不需要时间,每天的需求量Yn独立同分布且P{Yn=j}=aj,j=0,1,2,….现在我们要从上述问题中寻找一个Markov链.令Xn为第n天结束时的存货量,则Xn-Yn+1,若Xn≥s,S-Yn+1,若Xn＜s.构成的{Xn,n≥1}是Markov链.例5.11以Sn表示保险公司在时刻n的盈余,这里的时间以适当的单位来计算(如天,月等),初始盈余S0=x显然为已知,但未来的盈余S1,S2,…却必须视为随机变量,增量Sn-Sn-1解释为n-1和n之间获得的盈利(可以为负).假定X1,X2,…是不包含利息的盈利且独立同分布于F(x),则Xn+1=马尔可夫链Sn=Sn-1(1+i)+Xn,i为固定的利率,{Sn,n≥0}是一个Markov链,转移概率为pxy=F[y-(1+i)x].例5.12考察掷硬币的例子.硬币的正反面分别记为U和D,于是状态空间为{U,D}={1,2},式中1,2分别代表U,D.假定硬币初始时为正面,我们一共投掷了50次.在每一次投掷时,硬币以概率20%翻转.于是转移概率为:p11=0.8,p12=0.2,p21=0.2,p22=0.8.状态转移矩阵P=.进而算得P2=,P4=.于是P{X4=U}=P{X0=U→X4=U}==0.5648.0.80.20.20.80.680.320.320.680.56480.43520.43520.56484UUP马尔可夫链例5.13(隐Markov链模型)这里用简单例子引出隐Markov链模型.假定有分别记为M和W的两枚硬币.在任何给定的时刻两枚硬币或者为正面或者为反面.在任何给定时刻只有一枚硬币呈现,但是有时硬币可能被替换(M换成W或W换成M)但不改变其正反面.硬币M具有与例5.12相同的转移概率,硬币W具有转移概率.在任何给定时刻硬币被替换的概率为30%,替换完成时,硬币的状态不变.这一Markov链有4个状态,分别记为1:UM;2:DM;3:UW;4:DW.状态1,3表示正面U,状态2,4表示反面D.转移矩阵为4×4的矩阵.0.90.10.050.95马尔可夫链我们可以计算转移概率,比如UM→UM,首先有U→U(无转移),而后M→M(无转移).于是转移概率为P{U→U|M}·P{M→M}=0.8×0.7=0.56.其它转移概率类似可得.转移方式是UM→UMUM→DMUM→UWUM→DWDM→UMDM→DMDM→UWDM→DWUW→UMUW→DMUW→UWUW→DWDW→UMDW→DMDW→UWDW→DW转移概率矩阵为0.8×0.70.2×0.70.8×0.30.2×0.30.2×0.70.8×0.70.2×0.30.8×0.30.9×0.30.1×0.30.9×0.70.1×0.70.05×0.30.95×0.30.05×0.70.95×0.7若从状态UM出发,要求在第4个时间周期后,硬币处于状态D的概率,则由于2=DM和4=DW都是状态D,所求概率为+.P=.412P414P马尔可夫链例5.14确定汽车年保险金的系统称好-坏系统.在该系统中,每个参保人被赋予一个正整数值的状态.年保险金是这个状态(保险车类型以及保险水平)的函数.参保人的状态随着参保人要求理赔的次数而一年一年地变化.低的状态对应于低的年保险金.如果参保人在上一年没有理赔要求,他的状态就将降低;如果参保人在上一年至少有一次理赔要求,他的状态一般会增加(可见,无理赔是好的,并且会导致低保险金;而要求理赔是坏的,一般会导致更高的保险金).对于给定的一个好-坏系统,以si(k)记一个在上一年处在状态i,且在该年有k次理赔要求的参保人在下一年的状态.马尔可夫链一般,一个特定的参保人年理赔要求的次数是参数为λ的泊松随机变量,那么此参保人相继的状态将构成一个马尔可夫链,并具有转移概率pij=,j≥0通常有多个状态.以下表格给出了一个假定有4个状态的好-坏系统:下一个状态状态年保险金0个理赔1个理赔2个理赔3个理赔以上12001234225013443400234446003444jkskkike)(:!马尔可夫链此表说明了:s2(0)=1;s2(1)=3;s2(k)=4,k≥2.考察,年理赔次数是参数为λ的泊松随机变量的某个参保人.如果这个参保人一年中有k次理赔要求的概率是αk,那么αk=,k≥0对于表中表示的好-坏系统,参保人相继的状态的转移