《算法大全第17章 马氏链模型.pdf》由会员分享，可在线阅读，更多相关《算法大全第17章 马氏链模型.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-207-第十七章第十七章 马氏链模型马氏链模型 1 随机过程的概念 一个随机试验的结果有多种可能性，在数学上用一个随机变量（或随机向量）来描述。在许多情况下，人们不仅需要对随机现象进行一次观测，而且要进行多次，甚至接连不断地观测它的变化过程。这就要研究无限多个，即一族随机变量。随机过程理论就是研究随机现象变化过程的概率规律性的。定义 1 设,Ttt是一族随机变量，T是一个实数集合，若对任意实数tTt,是一个随机变量，则称,Ttt为随机过程。T称为参数集合，参数t可以看作时间。t的每一个可能取值称为随机过程的一个状态。其全体可能取值所构成的集合称为状态空间，记作E。当参数集合T为非负整数集时，
2、随机过程又称随机序列。本章要介绍的马尔可夫链就是一类特殊的随机序列。例 1 在一条自动生产线上检验产品质量，每次取一个，“废品”记为 1，“合格品”记为 0。以n表示第n次检验结果，则n是一个随机变量。不断检验，得到一列随机变量L,21，记为,2,1,L=nn。它是一个随机序列，其状态空间1,0=E。例 2 在m个商店联营出租照相机的业务中（顾客从其中一个商店租出，可以到m个商店中的任意一个归还），规定一天为一个时间单位，“jt=”表示“第t天开始营业时照相机在第j个商店”，mj,2,1L=。则,2,1,L=nn是一个随机序列，其状态空间,2,1mEL=。例 3 统计某种商品在t时刻的库存量，
3、对于不同的t，得到一族随机变量，),0,+tt是一个随机过程，状态空间,0RE=，其中R为最大库存量。我们用一族分布函数来描述随机过程的统计规律。一般地，一个随机过程,Ttt，对于任意正整数n及T中任意n个元素ntt,1L相应的随机变量ntt,1L的联合分布函数记为,),(1111nttnttxxPxxFnn=LLL （1）由于n及),1(nitiL=的任意性，（1）式给出了一族分布函数。记为,2,1;,1,),(11LLLL=nniTtxxFinttn 称它为随机过程,Ttt的有穷维分布函数族。它完整地描述了这一随机过程的统计规律性。2 马尔可夫链 2.1 马尔可夫链的定义 现实世界中有很多
4、这样的现象：某一系统在已知现在情况的条件下，系统未来时刻的情况只与现在有关，而与过去的历史无直接关系。比如，研究一个商店的累计销售额，如果现在时刻的累计销售额已知，则未来某一时刻的累计销售额与现在时刻以前的任一时刻累计销售额无关。上节中的几个例子也均属此类。描述这类随机现象的数学模型称为马氏模型。定义 2 设,2,1,L=nn是一个随机序列，状态空间E为有限或可列集，对于任意的正整数nm,，若)1,1(,=nkEijikL，有 -208-|,|1111ijPiiijPnmnnnnmn=+L （2）则称,2,1,L=nn为一个马尔可夫链（简称马氏链），（2）式称为马氏性。事实上，可以证明若等式（
5、2）对于1=m成立，则它对于任意的正整数m也成立。因此，只要当1=m时（2）式成立，就可以称随机序列,2,1,L=nn具有马氏性，即,2,1,L=nn是一个马尔可夫链。定义 3 设,2,1,L=nn是一个马氏链。如果等式（2）右边的条件概率与n无关，即)(|mpijPijnmn=+（3）则称,2,1,L=nn为时齐的马氏链。称)(mpij为系统由状态i经过m个时间间隔（或m步）转移到状态j的转移概率。（3）称为时齐性。它的含义是：系统由状态i到状态j的转移概率只依赖于时间间隔的长短，与起始的时刻无关。本章介绍的马氏链假定都是时齐的，因此省略“时齐”二字。2.2 转移概率矩阵及柯尔莫哥洛夫定理
6、对于一个马尔可夫链,2,1,L=nn，称以m步转移概率)(mpij为元素的矩阵)()(mpmPij=为马尔可夫链的m步转移矩阵。当1=m时，记PP=)1(称为马尔可夫链的一步转移矩阵，或简称转移矩阵。它们具有下列三个基本性质：（i）对一切Eji,，1)(0mpij；（ii）对一切Ei，=Ejijmp1)(；（iii）对一切Eji,，=时当时当，jijipijij0,1)0(。当实际问题可以用马尔可夫链来描述时，首先要确定它的状态空间及参数集合，然后确定它的一步转移概率。关于这一概率的确定，可以由问题的内在规律得到，也可以由过去经验给出，还可以根据观测数据来估计。例 4 某计算机机房的一台计算机
7、经常出故障，研究者每隔 15 分钟观察一次计算机的运行状态，收集了 24 小时的数据（共作 97 次观察）。用 1 表示正常状态，用 0 表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111 解 设)97,1(L=nXn为第n个时段的计算机状态，可以认为它是一个时齐马氏链，状态空间1,0=E，编写如下 Matlab 程序：a1=111001001111111001111011111100111111111000110
8、1101;a2=111011011010111101110111101111110011011111100111;a=a1 a2;f00=length(findstr(00,a)f01=length(findstr(01,a)f10=length(findstr(10,a)f11=length(findstr(11,a)或者把上述数据序列保存到纯文本文件data1.txt中，存放在Matlab下的work子目录中，编写程序如下：clc,clear -209-format rat fid=fopen(data1.txt,r);a=;while(feof(fid)a=a fgetl(fid);en
9、d for i=0:1 for j=0:1 s=int2str(i),int2str(j);f(i+1,j+1)=length(findstr(s,a);end end fs=sum(f);for i=1:2 f(i,:)=f(i,:)/fs(i);end f 求得 96 次状态转移的情况是：00，8 次；10，18 次；01，18 次；11，52 次，因此，一步转移概率可用频率近似地表示为 13418880|0100=+=+nnXXPp 139188180|1101=+=+nnXXPp 3595218181|0110=+=+nnXXPp 35265218521|1111=+=+nnXXPp
10、例 5 设一随机系统状态空间4,3,2,1=E，记录观测系统所处状态如下：4 3 2 1 4 3 1 1 2 3 2 1 2 3 4 4 3 3 1 1 1 3 3 2 1 2 2 2 4 4 2 3 2 3 1 1 2 4 3 1 若该系统可用马氏模型描述，估计转移概率ijp。解 首先将不同类型的转移数ijn统计出来分类记入下表 ji 转移数ijn 1 2 3 4 行和in 1 2 3 4 4 4 1 1 3 2 4 2 4 4 2 1 0 1 4 2 10 11 11 7 各类转移总和ijijn等于观测数据中马氏链处于各种状态次数总和减 1，而行和in是-210-系统从状态i转移到其它状态
11、的次数，ijn是由状态i到状态j的转移次数，则ijp的估计值iijijnnp=。计算得=7/27/47/1011/111/211/411/411/211/411/211/310/110/15/25/2P Matlab 计算程序如下：format rat clc a=4 3 2 1 4 3 1 1 2 3.2 1 2 3 4 4 3 3 1 1.1 3 3 2 1 2 2 2 4 4.2 3 2 3 1 1 2 4 3 1;for i=1:4 for j=1:4 f(i,j)=length(findstr(i j,a);end end f ni=(sum(f)for i=1:4 p(i,:)=f
12、(i,:)/ni(i);end p 例 6（带有反射壁的随机徘徊）如果在原点右边距离原点一个单位及距原点)1(ss个单位处各立一个弹性壁。一个质点在数轴右半部从距原点两个单位处开始随机徘徊。每次分别以概率)10(pp和)1(pqq=向右和向左移动一个单位；若在+1 处，则以概率p反射到 2，以概率q停在原处；在s处，则以概率q反射到1s，以概率p停在原处。设n表示徘徊n步后的质点位置。,2,1,L=nn是一个马尔可夫链，其状态空间,2,1sEL=，写出转移矩阵P。解 =时当时当，202,10iiiP =其它时当时当,02,1,1jpjqpj =其它时当时当,01,sjqsjppsj -211-
13、=其它时当时当,0)1,3,2(1,1,siijqijppijL 因此，P为一个s阶方阵，即 =pqpqqpqpqP000000000000000000LLLLLLLLL。定理 1（柯尔莫哥洛夫开普曼定理）设,2,1,L=nn是一个马尔可夫链，其状态空间,2,1L=E，则对任意正整数nm,有 =+Ekkjikijmpnpmnp)()()(其中的Eji,。定理 2 设P是一个马氏链转移矩阵（P的行向量是概率向量），)0(P是初始分布行向量，则第n步的概率分布为 nnPPP)0()(=。例 7 若顾客的购买是无记忆的，即已知现在顾客购买情况，未来顾客的购买情况不受过去购买历史的影响，而只与现在购买
14、情况有关。现在市场上供应CBA、三个不同厂家生产的 50 克袋状味精，用“1=n”、“2=n”、“3=n”分别表示“顾客第n次购买CBA、厂的味精”。显然，,2,1,L=nn是一个马氏链。若已知第一次顾客购买三个厂味精的概率依次为 0.2，0.4，0.4。又知道一般顾客购买的倾向由表 2给出。求顾客第四次购买各家味精的概率。表 2 下 次 购 买 A B C 上次 购买 A B C 0.8 0.5 0.5 0.1 0.1 0.3 0.1 0.4 0.2 解 第一次购买的概率分布为 4.04.02.0)1(=P 转移矩阵=2.03.05.04.01.05.01.01.08.0P 则顾客第四次购买
15、各家味精的概率为 1636.0136.07004.03)1()4(=PPP。2.3 转移概率的渐近性质极限概率分布 -212-现在我们考虑，随n的增大，nP是否会趋于某一固定向量？先考虑一个简单例子：转移矩阵=3.07.05.05.0P，当+n时，125127125127nP 又若取=125127u，则uuP=，Tu为矩阵TP的对应于特征值1=的特征（概率）向量，u也称为P的不动点向量。哪些转移矩阵具有不动点向量？为此我们给出正则矩阵的概念。定义 一个马氏链的转移矩阵P是正则的，当且仅当存在正整数k，使kP的每一元素都是正数。定理 若P是一个马氏链的正则阵，那么：（i）P有唯一的不动点向量W，
16、W的每个分量为正。（ii）P的n次幂nP（n为正整数）随n的增加趋于矩阵W，W的每一行向量均等于不动点向量W。例8 信息的传播 一条新闻在LL,21naaa等人中间传播，传播的方式是1a传给2a，2a传给3a，如此继续下去，每次传播都是由ia传给1+ia。每次传播消息的失真概率是p，10mpij，Nji,2,1,L=则此链具有遍历性；且有极限分布),(1NL=，它是方程组 P=或即=Niijijp1，Nj,1L=的满足条件 0j，11=Njj 的唯一解。例 9 根据例 7 中给出的一般顾客购买三种味精倾向的转移矩阵，预测经过长期的多次购买之后，顾客的购买倾向如何？解 这个马氏链的转移矩阵满足定
17、理 4 的条件，可以求出其极限概率分布。为此，解下列方程组：=+=+=+=12.04.01.03.01.01.05.05.08.0321321332123211ppppppppppppppp 编写如下的 Matlab 程序：format rat p=0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2;a=p-eye(3);ones(1,3);b=zeros(3,1);1;p_limit=ab 或者利用求转移矩阵P的转置矩阵TP的特征值 1 对应的特征(概率)向量，求得极限概率。编写程序如下：p=0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2;p=sy
18、m(p);x,y=eig(p)for i=1:3 x(:,i)=x(:,i)/sum(x(:,i);end x 求得751=p，84112=p，84133=p。这说明，无论第一次顾客购买的情况如何，经过长期多次购买以后，A厂产的味-214-精占有市场的75，CB,两厂产品分别占有市场的8411，8413。2.4 吸收链 马氏链还有一种重要类型吸收链。若马氏链的转移矩阵为=10004.03.03.000.30.20.30.20.400.30.343214 3 2 1 P，P的最后一行表示的是，当转移到状态 4 时，将停留在状态 4，状态 4 称为吸收状态。如果马氏链至少含有一个吸收状态，并且从每
19、一个非吸收状态出发，都可以到达某个吸收状态，那么这个马氏链被称为吸收链。具有r个吸收状态，)(rnss=个非吸收状态的吸收链，它的nn转移矩阵的标准形式为=SROIPr （4）其中rI为r阶单位阵，O为sr零阵，R为rs矩阵，S为ss矩阵。从（4）得=nrnSQOIP （5）（5）式中的子阵nS表示以任何非吸收状态作为初始状态，经过n步转移后，处于s个非吸收状态的概率。在吸收链中，令1)(=SIF，则F称为基矩阵。对于具有标准形式（即(4)式）转移矩阵的吸收链，可以证明以下定理：定理 5 吸收链的基矩阵F中的每个元素，表示从一个非吸收状态出发，过程到达每个非吸收状态的平均转移次数。定理 6 设
20、FCN=，F为吸收链的基矩阵，TC111L=，则N的每个元素表示从非吸收状态出发，到达某个吸收状态被吸收之前的平均转移次数。定理 7 设)(ijbFRB=，其中F为吸收链的基矩阵，R为（4）式中的子阵，则ijb表示从非吸收状态i出发，被吸收状态j吸收的概率。例 10 智力竞赛问题 甲、乙两队进行智力竞赛。竞赛规则规定：竞赛开始时，甲、乙两队各记 2 分，在抢答问题时，如果甲队赢得 1 分，那么甲队的总分将增加 1分，同时乙队总分将减少 1 分。当甲（或乙）队总分达到 4 分时，竞赛结束，甲（或乙）获胜。根据队员的智力水平，知道甲队赢得 1 分的概率为p，失去 1 分的概率为p1，求：（i）甲队
21、获胜的概率是多少？（ii）竞赛从开始到结束，分数转移的平均次数是多少？（iii）甲队获得 1、2、3 分的平均次数是多少？分析分析 甲队得分有 5 种可能，即 0、1、2、3、4，分别记为状态43210,aaaaa，其中0a和4a是吸收状态，21,aa和3a是非吸收状态。过程是以2a作为初始状态。根据-215-甲队赢得 1 分的概率为p，建立转移矩阵：=1000001000010000100001 4321043210ppppppaaaaaPaaaaa （6）将（6）式改记为标准形式：=SROIP2 其中 =ppR00001，=0100100ppppS，计算 =pqqqpqpppqpqSIF1
22、11211)(2213 其中pq=1。因为2a是初始状态，根据定理 5，甲队获得 1，2，3 分的平均次数为pqq21，pq211，pqp21。又=pqqqpqpppqpqFCN11121122 2221221211pppq+=根据定理 6，以2a为初始状态，甲队最终获胜的分数转移的平均次数为pq212。又因为=ppqqpqpppqpqFRB)1()1(2113223 -216-根据定理 7，甲队最后获胜的概率pqpb21222=。Matlab 程序如下：syms p q r=q,0;0,0;0,p;s=0,p,0;q,0,p;0,q,0;f=(eye(3)-s)(-1);f=simple(f
23、)n=f*ones(3,1);n=simple(n)b=f*r;b=simple(b)3 马尔可夫链的应用 应用马尔可夫链的计算方法进行马尔可夫分析，主要目的是根据某些变量现在的情况及其变动趋向，来预测它在未来某特定区间可能产生的变动，作为提供某种决策的依据。例 11（服务网点的设置问题）为适应日益扩大的旅游事业的需要，某城市的甲、乙、丙三个照相馆组成一个联营部，联合经营出租相机的业务。游客可由甲、乙、丙三处任何一处租出相机，用完后，还在三处中任意一处即可。估计其转移概率如下表所示：还 相 机 处 甲 乙 丙 租相机处 甲 乙 丙 0.2 0.8 0.1 0.8 0 0.3 0 0.2 0.6
24、 今欲选择其中之一附设相机维修点，问该点设在哪一个照相馆为最好？解 由于旅客还相机的情况只与该次租机地点有关，而与相机以前所在的店址无关，所以可用nX表示相机第n次被租时所在的店址；“1=nX”、“2=nX”、“3=nX”分别表示相机第n次被租用时在甲、乙、丙馆。则,2,1,L=nXn是一个马尔可夫链，其转移矩阵P由上表给出。考虑维修点的设置地点问题，实际上要计算这一马尔可夫链的极限概率分布。转移矩阵满足定理 4 的条件，极限概率存在，解方程组 =+=+=+=16.02.03.08.01.08.02.03213233123211ppppppppppppp 得极限概率41171=p，41162=
25、p，4183=p。由计算看出，经过长期经营后，该联营部的每架照相机还到甲、乙、丙照相馆的概率分别为4117、4116、418。由于还到甲馆的照相机较多，因此维修点设在甲馆较好。但由于还到乙馆的相机与还到甲馆的相差不多，若是乙的其它因素更为有利的话，比如，交通较甲方便，便于零配件的运输，电力供应稳定等等，亦可考虑设在乙馆。习 题 十 七 -217-1.在英国，工党成员的第二代加入工党的概率为 0.5，加入保守党的概率为 0.4，加入自由党的概率为 0.1。而保守党成员的第二代加入保守党的概率为 0.7，加入工党的概率为 0.2，加入自由党的概率为 0.1。而自由党成员的第二代加入保守党的概率为
26、0.2，加入工党的概率为 0.4，加入自由党的概率为 0.4。求自由党成员的第三代加入工党的概率是多少？在经过较长的时间后，各党成员的后代加入各党派的概率分布是否具有稳定性？2.社会学的某些调查结果指出：儿童受教育的水平依赖于他们父母受教育的水平。调查过程是将人们划分为三类：E类，这类人具有初中或初中以下的文化程度；S类，这类人具有高中文化程度；C类，这类人受过高等教育。当父或母（指文化程度较高者）是这三类人中某一类型时，其子女将属于这三种类型中的任一种的概率由下面给出 7.02.01.02.04.04.01.02.07.0 CSECSE母或父子女 问：（i）属于S类的人们中，其第三代将接受高
27、等教育的概率是多少？（ii）假设不同的调查结果表明，如果父母之一受过高等教育，那么他们的子女总可以进入大学，修改上面的转移矩阵。（iii）根据（ii）的解，每一类型人的后代平均要经过多少代，最终都可以接受高等教育？3.色盲是X链遗传，由两种基因A和a决定。男性只有一个基因A或a，女性有两个基因AaAA、或aa，当基因为a或aa时呈现色盲。基因遗传规律为：男性等概率地取母亲的两个基因之一，女性取父亲的基因外又等概率地取母亲的两个基因之一。由此可知，母亲色盲则儿子必色盲但女儿不一定。试用马氏链研究：（i）若近亲结婚，其后代的发展趋势如何？若父亲非色盲而母亲色盲，问平均经多少代，其后代就会变为全色盲或全不色盲，两者的概率各为多少？（ii）若不允许双方均色盲的人结婚，情况会怎样？