第十七章 马氏链模型

第十七章 马氏链模型

§1 随机过程的概念

一个随机试验的结果有多种可能性，在数学上用一个随机变量（或随机向量）来描述。在许多情况下，人们不仅需要对随机现象进行一次观测，而且要进行多次，甚至接连不断地观测它的变化过程。这就要研究无限多个，即一族随机变量。随机过程理论就是研究随机现象变化过程的概率规律性的。

定义1 设{?t,t?T}是一族随机变量，若对任意实数t?T,?tT是一个实数集合，是一个随机变量，则称{?t,t?T}为随机过程。

T称为参数集合，参数t可以看作时间。?t的每一个可能取值称为随机过程的一个状态。其全体可能取值所构成的集合称为状态空间，记作E。当参数集合T为非负整

数集时，随机过程又称随机序列。本章要介绍的马尔可夫链就是一类特殊的随机序列。

例1 在一条自动生产线上检验产品质量，每次取一个，“废品”记为1，“合格品”记为0。以?n表示第n次检验结果，则?n是一个随机变量。不断检验，得到一列随机变量?1,?2,?，记为{?n,n?1,2,?}。它是一个随机序列，其状态空间E?{0,1}。 例2 在m个商店联营出租照相机的业务中（顾客从其中一个商店租出，可以到m个商店中的任意一个归还），规定一天为一个时间单位，“?t?j”表示“第t天开始营业时照相机在第j个商店”，j?1,2,?,m。则{?n,n?1,2,?}是一个随机序列，其状态空间E?{1,2,?,m}。

例3 统计某种商品在t时刻的库存量，对于不同的t，得到一族随机变量，{?t,t?[0,??)}是一个随机过程，状态空间E?[0,R]，其中R为最大库存量。 我们用一族分布函数来描述随机过程的统计规律。一般地，一个随机过程{?t,t?T}，对于任意正整数n及T中任意n个元素t1,?,tn相应的随机变量?t1,?,?tn的联合分布函数记为

Ft1?tn(x1,?,xn)?P{?t1?x1,?,?tn?xn} （1）

由于n及ti(i?1,?,n)的任意性，（1）式给出了一族分布函数。记为

{Ft1?tn(x1,?,xn),ti?T,i?1,?,n;n?1,2,?}

称它为随机过程{?t,t?T}的有穷维分布函数族。它完整地描述了这一随机过程的统计规律性。

§2 马尔可夫链

2.1 马尔可夫链的定义

现实世界中有很多这样的现象：某一系统在已知现在情况的条件下，系统未来时刻的情况只与现在有关，而与过去的历史无直接关系。比如，研究一个商店的累计销售额，如果现在时刻的累计销售额已知，则未来某一时刻的累计销售额与现在时刻以前的任一时刻累计销售额无关。上节中的几个例子也均属此类。描述这类随机现象的数学模型称为马氏模型。

定义2 设{?n,n?1,2,?}是一个随机序列，状态空间E为有限或可列集，对于任意的正整数m,n，若i,j,ik?E(k?1,?,n?1)，有

-207-

P{?n?m?j|?n?i,?n?1?in?1,?,?1?i1}?P{?n?m?j|?n?i} （2）

则称{?n,n?1,2,?，（2）式称为马氏性。 }为一个马尔可夫链（简称马氏链）

事实上，可以证明若等式（2）对于m?1成立，则它对于任意的正整数m也成立。因此，只要当m?1时（2）式成立，就可以称随机序列{?n,n?1,2,?}具有马氏性，即{?n,n?1,2,?}是一个马尔可夫链。

定义3 设{?n,n?1,2,?}是一个马氏链。如果等式（2）右边的条件概率与n无关，即

P{?n?m?j|?n?i}?pij(m) （3）

则称{?n,n?1,2,?称pij(m)为系统由状态i经过m个时间间隔（或}为时齐的马氏链。（3）称为时齐性。它的含义是：系统由状态i到状态m步）转移到状态j的转移概率。

j的转移概率只依赖于时间间隔的长短，与起始的时刻无关。本章介绍的马氏链假定都是时齐的，因此省略“时齐”二字。

2.2 转移概率矩阵及柯尔莫哥洛夫定理 对于一个马尔可夫链{?n,n?1,2,?}，称以m步转移概率pij(m)为元素的矩阵当m?1时，记P(1)?P称为马尔可P(m)?(pij(m))为马尔可夫链的m步转移矩阵。

夫链的一步转移矩阵，或简称转移矩阵。它们具有下列三个基本性质： （i）对一切i,j?E，0?pij(m)?1；

（ii）对一切i?E，

?p(m)?1；

ijj?E（iii）对一切i,j?E，pij(0)??ij???1,当i?j时。

0，当i?j时?当实际问题可以用马尔可夫链来描述时，首先要确定它的状态空间及参数集合，然

后确定它的一步转移概率。关于这一概率的确定，可以由问题的内在规律得到，也可以由过去经验给出，还可以根据观测数据来估计。

例4 某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下：

1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111

解 设Xn(n?1,?,97)为第n个时段的计算机状态，可以认为它是一个时齐马氏链，状态空间E?{0,1}，编写如下Matlab程序：

a1='1110010011111110011110111111001111111110001101101'; 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

-208-

format rat

fid=fopen('data1.txt','r'); a=[];

while (~feof(fid)) a=[a fgetl(fid)]; end

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次状态转移的情况是：

0?0，8次； 0?1，18次； 1?0，18次； 1?1，52次， 因此，一步转移概率可用频率近似地表示为

84? 8?1813189p01?P{Xn?1?1|Xn?0}??

8?1813189p10?P{Xn?1?0|Xn?1}??

18?52355226p11?P{Xn?1?1|Xn?1}??

18?5235例5 设一随机系统状态空间E?{1,2,3,4}，记录观测系统所处状态如下： p00?P{Xn?1?0|Xn?0}?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

若该系统可用马氏模型描述，估计转移概率pij。

解 首先将不同类型的转移数nij统计出来分类记入下表

i?j转移数nij

1 2 3 4 各类转移总和

1 2 3 4 4 4 1 1 3 2 4 2 4 4 2 1 0 1 4 2 ijj行和ni 10 11 11 7 ??ni等于观测数据中马氏链处于各种状态次数总和减1，而行和ni是

-209-

系统从状态i转移到其它状态的次数，nij是由状态i到状态j的转移次数，则pij的估计值pij?nijni。计算得

?2/5?3/11???P?4/11??02/52/114/111/71/104/112/114/71/10?2/11?? 1/11??2/7?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(i,:)/ni(i); end p

例6（带有反射壁的随机徘徊）如果在原点右边距离原点一个单位及距原点s(s?1)个单位处各立一个弹性壁。一个质点在数轴右半部从距原点两个单位处开始随机徘徊。每次分别以概率p(0?p?1)和q(q?1?p)向右和向左移动一个单位；若在+1处，则以概率p反射到2，以概率q停在原处；在s处，则以概率q反射到s?1，以概率p停在原处。设?n表示徘徊n步后的质点位置。{?n,n?1,2,?}是一个马尔可夫链，其状态空间E?{1,2,?,s}，写出转移矩阵P。

解 P{?0?i}???1,当i?2时

?0，当i?2时?q,当j?1时? p1j??p,当j?2时

?0,其它??p,当j?s时? psj??q,当j?s?1时

?0,其它? -210-

?p,当j?i?1时? pij??q,当j?i??1时(i?2,3,?,s?1)

?0,其它?因此，P为一个s阶方阵，即

0??00???00??。

????q0p??0qp?定理1 （柯尔莫哥洛夫—开普曼定理）设{?n,n?1,2,?}是一个马尔可夫链，其状态空间E?{1,2,?}，则对任意正整数m,n有

pij(n?m)??pik(n)pkj(m)

?k?E?qp0?q0p??0q0 P???????000??0000其中的i,j?E。

定理2 设P是一个马氏链转移矩阵（P的行向量是概率向量），P行向量，则第n步的概率分布为

(0)是初始分布

P(n)?P(0)Pn。

例7 若顾客的购买是无记忆的，即已知现在顾客购买情况，未来顾客的购买情况不受过去购买历史的影响，而只与现在购买情况有关。现在市场上供应A、B、C三个不同厂家生产的50克袋状味精，用“?n?1”、“?n?2”、“?n?3”分别表示“顾客第n次购买A、B、C厂的味精”。显然，{?n,n?1,2,?}是一个马氏链。若已知第一次顾客购买三个厂味精的概率依次为0.2，0.4，0.4。又知道一般顾客购买的倾向由表2给出。求顾客第四次购买各家味精的概率。

表2 下 次 购 买 B A C 0.8 0.1 0.1 A 上次 0.5 0.1 0.4 B 购买 0.5 0.3 0.2 C 解 第一次购买的概率分布为 ??0.2?0.80.1?转移矩阵P?0.50.1???0.50.3 P(1)0.40.4?

0.1?0.4? ?0.2??则顾客第四次购买各家味精的概率为

?。 P(4)?P(1)P3??0.70040.1360.16362.3 转移概率的渐近性质—极限概率分布

-211-

现在我们考虑，随n的增大，P是否会趋于某一固定向量？先考虑一个简单例子：

n?0.50.5?转移矩阵P???，当n???时，

0.70.3???75???Pn??1212?

75???1212?5??7TTuP?uPu又若取u??，则，为矩阵的对应于特征值??1的特征（概??1212?率）向量，u也称为P的不动点向量。哪些转移矩阵具有不动点向量？为此我们给出

正则矩阵的概念。

定义４ 一个马氏链的转移矩阵P是正则的，当且仅当存在正整数k，使P的每一元素都是正数。

定理３ 若P是一个马氏链的正则阵，那么：

（i）P有唯一的不动点向量W，W的每个分量为正。 （ii）P的n次幂P（n为正整数）随n的增加趋于矩阵W，W的每一行向量均等于不动点向量W。

例8 信息的传播 一条新闻在a1,a2,?,an,?等人中间传播，传播的方式是a1传给a2，a2传给a3，?如此继续下去，每次传播都是由ai传给ai?1。每次传播消息的失真概率是p，0?p?1，即ai将消息传给ai?1时，传错的概率是p，这样经过长时间传播，第n个人得知消息时，消息的真实程度如何？

设整个传播过程为随机转移过程，消息经过一次传播失真的概率为p，转移矩阵

nk 假 真

P?假?1?真 ?p??pp?

?1?p??P是正则矩阵。又设V是初始分布，则消息经过n次传播后，其可靠程度的概率分布

为V?P。

一般地，设时齐马氏链的状态空间为E，如果对于所有i,j?E，转移概率pij(n)存在极限

limpij(n)??j，（不依赖于i）

n??n或

??1???1n???? P(n)?P?(?n??)???1??? -212-

?2??j???2??j????????， ?2??j?????????则称此链具有遍历性。又若

??jj?1，则同时称??(?1,?2,?)为链的极限分布。

下面就有限链的遍历性给出一个充分条件。 定理4 设时齐（齐次）马氏链{?n,n?1,2,?}的状态空间为E?{a1,?,aN}，

P?(pij)是它的一步转移概率矩阵，如果存在正整数m，使对任意的ai,aj?E，都

有

pij(m)?0，i,j?1,2,?,N

则此链具有遍历性；且有极限分布??(?1,?,?N)，它是方程组

???P 或即 ?j???ipij，j?1,?,N

i?1N的满足条件

?j?0，??j?1

j?1N的唯一解。

例9 根据例7中给出的一般顾客购买三种味精倾向的转移矩阵，预测经过长期的多次购买之后，顾客的购买倾向如何？

解 这个马氏链的转移矩阵满足定理4的条件，可以求出其极限概率分布。为此，解下列方程组：

?p1?0.8p1?0.5p2?0.5p3?p?0.1p?0.1p?0.3p?2123 ?p?0.1p?0.4p?0.2p123?3??p1?p2?p3?1编写如下的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=a\\b

T或者利用求转移矩阵P的转置矩阵P的特征值1对应的特征(概率)向量，求得极限概率。编写程序如下：

p=[0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2]; p=sym(p'); [x,y]=eig(p) for i=1:3

x(:,i)=x(:,i)/sum(x(:,i)); end x

求得p1?51113，p2?，p3?。 78484这说明，无论第一次顾客购买的情况如何，经过长期多次购买以后，A厂产的味

-213-

精占有市场的

11135，B,C两厂产品分别占有市场的，。 784842.4 吸收链

马氏链还有一种重要类型—吸收链。 若马氏链的转移矩阵为

1 2 3 41?0.30.300.4?2?0.20.30.20.3?，

?P??3?00.30.30.4???4?0001? P的最后一行表示的是，当转移到状态4时，将停留在状态4，状态4称为吸收状态。如果马氏链至少含有一个吸收状态，并且从每一个非吸收状态出发，都可以到达某

个吸收状态，那么这个马氏链被称为吸收链。

具有r个吸收状态，s(s?n?r)个非吸收状态的吸收链，它的n?n转移矩阵的标准形式为

?IO? P??r? （4）RS??其中Ir为r阶单位阵，O为r?s零阵，R为s?r矩阵，S为s?s矩阵。从（4）得

?IrO?n （5） P??n?QS??n（5）式中的子阵S表示以任何非吸收状态作为初始状态，经过n步转移后，处于s个

非吸收状态的概率。

在吸收链中，令F?(I?S)?1，则F称为基矩阵。

对于具有标准形式（即(4)式）转移矩阵的吸收链，可以证明以下定理： 定理5 吸收链的基矩阵F中的每个元素，表示从一个非吸收状态出发，过程到达每个非吸收状态的平均转移次数。

定理6 设N?FC，F为吸收链的基矩阵，C??11?1?，则N的每个元素表示从非吸收状态出发，到达某个吸收状态被吸收之前的平均转移次数。

定理7 设B?FR?(bij)，其中F为吸收链的基矩阵，R为（4）式中的子阵，

T则bij表示从非吸收状态i出发，被吸收状态j吸收的概率。

例10 智力竞赛问题 甲、乙两队进行智力竞赛。竞赛规则规定：竞赛开始时，甲、乙两队各记2分，在抢答问题时，如果甲队赢得1分，那么甲队的总分将增加1分，同时乙队总分将减少1分。当甲（或乙）队总分达到4分时，竞赛结束，甲（或乙）获胜。根据队员的智力水平，知道甲队赢得1分的概率为p，失去1分的概率为1?p，求：（i）甲队获胜的概率是多少？（ii）竞赛从开始到结束，分数转移的平均次数是多少？（iii）甲队获得1、2、3分的平均次数是多少？

分析 甲队得分有5种可能，即0、1、2、3、4，分别记为状态a0,a1,a2,a3,a4，其中a0和a4是吸收状态，a1,a2和a3是非吸收状态。过程是以a2作为初始状态。根据

-214-

甲队赢得1分的概率为p，建立转移矩阵：

a0 a1 a2 a300p00a40?0?? （6） 0??p?1??a0?100a1?1?p0p?P?a2?01?p0?a3?001?pa4?00?0将（6）式改记为标准形式：

?IO?P??2? RS??其中

?1?pR??0???0计算

0?p?00?，S??1?p0??p?1?p???00?p?， ?0???1?pqpp2?1???1q1p F?(I3?S)?? 1?2pq?2?qq1?pq???其中q?1?p。

因为a2是初始状态，根据定理5，甲队获得1，2，3分的平均次数为

q，

1?2pq1p，。又

1?2pq1?2pq?1?pqpp2?1??N?FC?q1p ??1?2pq?q2q1?pq???11?2p221?2p2 ?1?2pq??根据定理6，以a2为初始状态，甲队最终获胜的分数转移的平均次数为

又因为

2。

1?2pq?(1?pq)pp3?1??22B?FR?qp? 1?2pq??q3(1?pq)p???

-215-

p2根据定理7，甲队最后获胜的概率b22?。

1?2pqMatlab程序如下： 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) n=f*ones(3,1);n=simple(n) b=f*r;b=simple(b) §3 马尔可夫链的应用

应用马尔可夫链的计算方法进行马尔可夫分析，主要目的是根据某些变量现在的情况及其变动趋向，来预测它在未来某特定区间可能产生的变动，作为提供某种决策的依据。

例11（服务网点的设置问题）为适应日益扩大的旅游事业的需要，某城市的甲、乙、丙三个照相馆组成一个联营部，联合经营出租相机的业务。游客可由甲、乙、丙三处任何一处租出相机，用完后，还在三处中任意一处即可。估计其转移概率如下表所示：

还 相 机 处 甲 乙 丙 0.2 0.8 0 甲 0.8 0 0.2 租相机处 乙 0.1 0.3 0.6 丙 今欲选择其中之一附设相机维修点，问该点设在哪一个照相馆为最好？ 解 由于旅客还相机的情况只与该次租机地点有关，而与相机以前所在的店址无关，所以可用Xn表示相机第n次被租时所在的店址；“Xn?1”、“Xn?2”、“Xn?3”分别表示相机第n次被租用时在甲、乙、丙馆。则{Xn,n?1,2,?}是一个马尔可夫链，其转移矩阵P由上表给出。考虑维修点的设置地点问题，实际上要计算这一马尔可夫链的极限概率分布。

转移矩阵满足定理4的条件，极限概率存在，解方程组

?p1?0.2p1?0.8p2?0.1p3?p?0.8p?0.3p?213 ?

?p3?0.2p2?0.6p3??p1?p2?p3?117168得极限概率p1?，p2?，p3?。

414141由计算看出，经过长期经营后，该联营部的每架照相机还到甲、乙、丙照相馆的概率分别为

17168、、。由于还到甲馆的照相机较多，因此维修点设在甲馆较好。但414141由于还到乙馆的相机与还到甲馆的相差不多，若是乙的其它因素更为有利的话，比如，交通较甲方便，便于零配件的运输，电力供应稳定等等，亦可考虑设在乙馆。

习 题 十 七

-216-

1. 在英国，工党成员的第二代加入工党的概率为0.5，加入保守党的概率为0.4，加入自由党的概率为0.1。而保守党成员的第二代加入保守党的概率为0.7，加入工党的概率为0.2，加入自由党的概率为0.1。而自由党成员的第二代加入保守党的概率为0.2，加入工党的概率为0.4，加入自由党的概率为0.4。求自由党成员的第三代加入工党的概率是多少？在经过较长的时间后，各党成员的后代加入各党派的概率分布是否具有稳定性？

2. 社会学的某些调查结果指出：儿童受教育的水平依赖于他们父母受教育的水平。调查过程是将人们划分为三类：E类，这类人具有初中或初中以下的文化程度；S类，这类人具有高中文化程度；C类，这类人受过高等教育。当父或母（指文化程度较高者）是这三类人中某一类型时，其子女将属于这三种类型中的任一种的概率由下面给出

子女 E SC

父E?0.7?或S0.4?母C?0.1?0.20.1?0.40.2??0.20.7??问：（i）属于S类的人们中，其第三代将接受高等教育的概率是多少？

（ii）假设不同的调查结果表明，如果父母之一受过高等教育，那么他们的子女总可以进入大学，修改上面的转移矩阵。

（iii）根据（ii）的解，每一类型人的后代平均要经过多少代，最终都可以接受高等教育？

3. 色盲是X?链遗传，由两种基因A和a决定。男性只有一个基因A或a，女性有两个基因AA、Aa或aa，当基因为a或aa时呈现色盲。基因遗传规律为：男性等概率地取母亲的两个基因之一，女性取父亲的基因外又等概率地取母亲的两个基因之一。由此可知，母亲色盲则儿子必色盲但女儿不一定。试用马氏链研究：

（i）若近亲结婚，其后代的发展趋势如何？若父亲非色盲而母亲色盲，问平均经多少代，其后代就会变为全色盲或全不色盲，两者的概率各为多少？

（ii）若不允许双方均色盲的人结婚，情况会怎样？

-217-

1. 在英国，工党成员的第二代加入工党的概率为0.5，加入保守党的概率为0.4，加入自由党的概率为0.1。而保守党成员的第二代加入保守党的概率为0.7，加入工党的概率为0.2，加入自由党的概率为0.1。而自由党成员的第二代加入保守党的概率为0.2，加入工党的概率为0.4，加入自由党的概率为0.4。求自由党成员的第三代加入工党的概率是多少？在经过较长的时间后，各党成员的后代加入各党派的概率分布是否具有稳定性？

2. 社会学的某些调查结果指出：儿童受教育的水平依赖于他们父母受教育的水平。调查过程是将人们划分为三类：E类，这类人具有初中或初中以下的文化程度；S类，这类人具有高中文化程度；C类，这类人受过高等教育。当父或母（指文化程度较高者）是这三类人中某一类型时，其子女将属于这三种类型中的任一种的概率由下面给出

子女 E SC

父E?0.7?或S0.4?母C?0.1?0.20.1?0.40.2??0.20.7??问：（i）属于S类的人们中，其第三代将接受高等教育的概率是多少？

（ii）假设不同的调查结果表明，如果父母之一受过高等教育，那么他们的子女总可以进入大学，修改上面的转移矩阵。

（iii）根据（ii）的解，每一类型人的后代平均要经过多少代，最终都可以接受高等教育？

3. 色盲是X?链遗传，由两种基因A和a决定。男性只有一个基因A或a，女性有两个基因AA、Aa或aa，当基因为a或aa时呈现色盲。基因遗传规律为：男性等概率地取母亲的两个基因之一，女性取父亲的基因外又等概率地取母亲的两个基因之一。由此可知，母亲色盲则儿子必色盲但女儿不一定。试用马氏链研究：

（i）若近亲结婚，其后代的发展趋势如何？若父亲非色盲而母亲色盲，问平均经多少代，其后代就会变为全色盲或全不色盲，两者的概率各为多少？

（ii）若不允许双方均色盲的人结婚，情况会怎样？

-217-

本文来源：https://www.bwwdw.com/article/oziv.html