马尔可夫链建模法
马尔可夫链基本理论和结论
服务网点的设置问题
常染色体遗传模型
常染体隐性疾病模型
马尔可夫链的应用
预备知识：马尔可夫链
随机过程：设 是一族随机变量，T是一个实数集合，
若对任意的 实数 ， 是一个随机变量，则称
为随机过程。
例一 在一条生产线上检验产品质量，每次取一个，废品记为1
合格品记为0。以 表示第n次检验结果，则 是一个随机
变量. 不断检验，得到一系列随机变量，
记为
它是一个 随机序列，其状态空间为E={0，1}
例二：在m个商店联营出租相机业务中（顾客从其中一个商店租出
可以到m个商店中的任意一个归还）规定一天为一个时间单位
表示第t天开始时照相机在第j个商店,j=1,2,…..m.
则 是一个随机序列，其状态空间为
例3：
某商店每月考察一次经营情况，其结果用销路好或坏这
两种状况中的一种表示。已知若果本月销路好，下月任
保只这种状况的概率为；如果本月销路坏，下月转变
为销路好的概率为，试分析假若开始时商店处于销路
好的状态，过若干月后能保持销路好的概率有多大？如果
开始是处于销路坏呢？
E={1,2,…….m}
,n=0,1,2,………..
称为这个经营系统的状态
称为无后效性，由此，更椐全概率公式容易得到
如表所示，由数字变化规律可以看出
开始销路好时状态概率的变化
n
0 1 2 3 ………
1
4/9
0
5/9
表2 开始销路坏时的状态概率的变化
0 1 2 3 ………
n
0 4/9
1 5/9
马尔可夫链的定义：
设
是一个随机序列，状态空间E为有限或可列
对于任意的正整数m,n，若i,j, 有
则称
为一个
马尔可夫链
马氏链及其基本方程
由状态转移的无后效性和全概率公式可以写出马氏链的基本方程
马氏链至少包括一个吸收状态，并且从每一个非吸收状
态出发，能以正的概率经有限次转移达到某个吸收状态
则称此马氏链为吸收链。
定理2：正则链存在唯一的极限状态概率
引入状态概率向量和转移概率矩阵
（7）
则基本方程（3）可表为
（8）
（9）
因此对于马氏链模型最基本的问题是：构造状态xn及写出转移矩阵p，一旦有了P，则给定初始状态a(0)就可以用（9）或（8）计算任意时间n的状态概率a(n)
定义1：一个有k个状态的马氏链，如果存在正整数N，使从任意
状态i经N次转移，都以大于0的概率达到状态j(I,j=1,2,…k)
称此马氏链为正则链。
正则链。
马尔可夫链的应用
模型六：服务网点的设置问题
为适应日益扩大的旅游事业的需要，某城市的甲乙丙三个
照相馆组成一个联营部，联合经营出租相机的业务。游客
可由甲乙丙三处任一处租出相机，用完后，还到三处中的
任一处即可。估计其转移概率为：
租
相
机
处
甲
乙
丙
还 相 机 处
甲
乙
丙
0
0
今欲选择其中之一附设相机维修点，请你设计一种方案。
模型分析
由于旅客还相机的情况只与该次租机地点有关，而与相机
以前所处的点址无关。
由（10）有，设极限概率为W
即：
解上列方程组可得：
由计算看出，经过长期经营后，该联营部的每架照相机
还到甲乙丙照相馆的概率为17/41，16/41，8/41。由于还到甲的照相机的概率最大，因此维修点设在甲馆较好。
模型推广：生物基因遗传等方面的应用。
§ 马氏链模型
随着人类的进化，为了揭示生命的奥秘，人们越来越注重遗传学的研究，特别是遗传特征的逐代传播，已引起人们广泛的注意。无论是人，还是动、植物都会将本身的特征遗传给下一代，这主要是因为后代继承了双亲的基因，形成自己的基因对，由基因又确定了后代所表现的特征。本节将利用数学的 马氏链方法来建立相应的遗传模型等，并讨论几个简单而又有趣的实例。
马氏链（马尔柯夫链）研究的是一类重要的随机过程，研究对象的状 态s(t)是不确定的，它可能 取K种 状态si(i=1,…,k)之一，有时甚至可取无穷多种状态。在建模时，时间变量也被离散化，我们希望通过建立两个相邻时刻研究对象取各种状态的概率之间的联系来研究其变化规律，故马氏链研究的也是一类状态转移问题。
例 设某商店经营情况可能有三种状态：好（S1：利润丰厚）、一般（S2）和不好（S3：亏损）。根据统计资料，上月状态为Si，下月状态为Sj的概率为pij（i=1,2,3; j=1,2,3），0≤pij≤1
例中的关系既可用一转移矩阵表示
例 研究某一草原生态系统中物质磷的循环，考虑土壤中含磷、牧草含磷、牛羊体内含磷和流失于系统之外四种状态，分别 以S1，S2，S3和S4表示这四种状态。以年为时间参数，一年内如果土壤中的磷以的概率被牧草生长吸收，水土流失于系统外的概率为 ；牧草中的含磷以 的概率被牛羊吃掉而转换到牛羊体内，的概率随牧草枯死腐败归还土壤；牛羊体中的磷 以的概率因粪便排泄而还归土壤，又以自 身的比率因屠宰后投放市场而转移到系统外。我们可以建立一个马尔柯夫链来研究此生态系统问题，其转移概率列表于下：
1
0
0
0
S4流失系统外
0
S3羊体含磷
0
S2牧草含磷
0
S1土壤含磷
i时段状态
S4
S3
S2
S1
i+1时段状态
状态转移概率
相应的转移矩阵 为：
且Sj+1=SjM
马氏链模型的性质完全由其转移矩
阵决定，故研究马氏链的数学工
具是线性代数中有关矩阵的理论。
首先，任一转移矩阵的行向量均为概率向量，即有 （1） （I , j=1,…,n）
（2） （i=1,…,n）
这样的矩阵被称为 随机矩阵。
常染色体遗传模型
下面给出双亲体基因型的所有可能的结合，以及其后代形成每种基因型的概率，如 表所示。
在常染色体遗传中，后代从每个亲体的基因对中各继承一个基因，形成自己的基因时，基因对也称为基因型。如果我们所考虑的遗传特征是由两个基 因A和a控制的，（A、a为表示两类基因的符号）那么就有三种基因对，记为AA，Aa，aa。
1
0
0
0
aa
0
1
0
Aa
0
0
0
1
AA
后代基因型
aa－aa
Aa－aa
Aa－Aa
AA－aa
AA－Aa
AA－AA
父体——母体的基因型
双亲随机结合的较一般模型相对比较复杂，这些我们仅研究一个较简单的特例 。
例 农场的植物园中某种植物的基因型 为AA,Aa和aa。农场计划采用 AA型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后，这种植物的任一代的三种基因型分布情况如何？
（a）假设：令n=0,1,2,…。
（i）设an,bn和cn分别表示第n代植物中，基因型 为AA,Aa和aa的植物占植物总数的百分比 。令x (n)为第n代植物的基因型分布：
当n=0时
表示植物基因型的初始分布（即培育开始时的分布）
例 农场的植物园中某种植物的基因型 为AA,Aa和aa。农场计划采用 AA型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后， 这种植物的任一代的三种基因型分布情况如何？
（b）建模
根据假设(ii)，先考虑第n代中的AA型。由于第n－1代的AA型与AA型结合。后代全部是AA型；第n－1代的Aa型与AA型结合，后代是AA型的可能性为 1/2，而 第n－1代的aa型与AA型结合，后代不可能 是AA型。因此当n=1,2…时
即
类似可推出
cn=0
显然有
（ii）第n代的分布与 第n－1代的分布之间的关系是通过表确定的。
()
()
()
将（）、（）、（）式相加，得
根据假设(I)，可递推得出：
对于()式.()式和()式，我们采用矩阵形式简记为
其中
（注：这里M为转移矩阵的位置）
()
由（）式递推，得
()
（）式给出第n代基因型的分布与初始分布的关系。
为了计算出Mn，我们将M对角化，即求出可逆矩 阵P和对角库D，使
M=PDP-1
因而有
Mn=PDnP-1, n=1,2,…
其中
这里 ， ， 是矩 阵M的三个特征值。对于 ()式中的M，易求得它的特征值和特征向量：
=1， =1/2， =0
因此
所以
通过计算，P-1=P，因此有
即
所以有
当
时，
，所以从（）式得到
即在极限的情况下，培育的植物都 是AA型。
若在上述问题中，不选用基 因AA型的植物与每一植物结合，而是将具有相同基因型植物相结合，那么后代具有三种基因型的概率如 表所示。
1
1/4
0
aa
0
1/2
0
Aa
0
1/4
1
AA
后
代
基
因
型
aa－aa
Aa－Aa
AA－AA
父体——母体的基因型
并且
，其中
M的特征值为
通过计算，可以解出与 、 相对应的两个线性无关的特征向量e1和e2，及与相对应的特征内 量e3：
因此
解得：
当
时，
，所以
因此，如果用基因
型相同的植物培育
后代，在极限情况
下，后代仅具有基
因AA和aa。
例 常染体隐性疾病模型
现在世界上已经发现的遗传病有将 近4000种。在一般情况下，遗传疾病和特殊的种族、部落及群体 有关。例如，遗传病库利氏贫血症的患者以居住在 地中海沿岸为多，镰状网性贫血症一般流行在黑人中，家族黑蒙性白痴症则流行在东欧犹太人中间。 患者经常未到成年就痛苦地死去，而他们的父母则 是疾病的病源。假若我们能识别这些疾病的隐性患 者，并且规定两个隐性患者不能结合（因为两个隐 性病患者结合，他们的后代就可能成为显性患者），那么未来的儿童，虽然有可能是隐性患者，但绝不 会出现显性特征，不会受到疾病的折磨。
现在，我们考虑在控制结合的情况下，如何确定后代中隐性患者的概率。
（a）假设
（i）常染色体遗传的正常基因记 为A，不
正常基因记 为a，并以 AA，Aa，aa
分别表示正常人，隐性患者，显性患
者的基因型
（ii）设an,bn分别表示第n代中基因型为
AA，Aa的人占总人数的百分比，
记 ，n=1,2,…（这里
不考 虑aa型是因
为这些人不可能成年并结婚）
（iii）为使每个儿童至少有一个正常的父
亲或母亲，因此隐性患者必须与正常
人结合，其后代的基因型概率由 下表
给出：
1/2
0
Aa
1/2
1
AA
后
代
基
因
型
AA－Aa
AA－AA
父母的基因型
（b）建模
由假设（iii），从第n－1代到第n代基因型分布的变化取
决于方程
所以
，其中
如果初始分 布x(0)已知，那么 第n代基因型分布为
解 将M对角化，即求出特征值及其所对应的特征向量，得
计算
=
()
因为
，所以当
时，
，
隐性患者逐渐消失。 从()式中可知
每代隐性患者的概率是前一代隐性患者概率的1/2。
()
（c）模型讨论
研究在随机结合的情况下，隐性患者的变化是很有意思的，但随机结合导致了非线性化问题，超出了本章范围，然而用其它技巧，在随机结合的情况下可以 把（）式改写为
()
下面给会出数值例子：
某地区有10%的黑人是镰状网性盆血症隐性患者，如果控制结合，根据（）式可知下一代 （大约27年）的隐性患者将减少到5%；如果随机结合，根据 （）式，可以预言下一代人中 有%是隐性患者，并且可计算出大约每出生400个黑人孩子，其中有一个是显性患者。
（近亲繁殖）
近亲繁殖是指父母双方有一个或两个共同的祖先，一般追踪到四代，即至少有相同的曾祖父（母）或外曾祖父（母）。为简单起见，我们来考察一对表兄妹（或堂兄妹）结婚的情况，其中□代表男性，○代表女性。
设曾祖父有某基因 对A1A2，曾祖母有某基因 对A3A4，容易求得：祖父母取 得A1的概率为 1/2，故祖父母同 有A1基因的概率为1/4；父母同有A1基因的概率为 1/16，而子女从父母那里获得基因对A1A1的概率为 1/64，而获得相同基因对（称为基因纯合子）A1A1，A2A2，A3A3或A4A4之一的概率为 1/16,此概率被称为表兄 妹(或堂兄妹)结婚(表亲)的近交系数。
类似可求得半堂亲（只有一个共同祖先）的近交系数 为1/32，从表亲（父母为表亲）的近交系数 为1/64；非近亲结婚不可能发生重复取某祖先的一对基因对中的某一基因作为自己的基因对的情况，故近交系数 为0。
（群体的近交系数） 设某群体中存在近亲婚配现象，称各种近交系数的数学期望为该群体的近交系数。例如，某村镇共有2000对婚配关系，其中有59对表亲，22对半堂亲 和28对从表亲，则该村镇的近亲系数为
现在，我们来研究近亲结
婚会产生什么结果。
设某基因对由 A、a两种基因组成，出 现A的概率为p，出现a的概率为q=1-p。在随机交配群体中，其子女 为AA、Aa及aa型的概率分别 为p2、2pq及q2。
对近交系数 为F的群体，根据条件概率公式，后代出 现aa型基因对的概率为
比较存在近亲交配的群体与不允许近亲交配 (F=0)的群体，
令
若a为某种隐性疾病的基因，易见，在近交群体中，后代产
生遗传病（aa型）的概率增大了， 且F越大，后代患遗传病
的概率也越大。
同样，后代出现AA型基因对的概率 为p2+Fpq。Aa型不可能 是共同祖先同一基因的重复，故其出现的概率为2pq(1-F)。
例如，苯丙酮尿症是一种隐性基因纯合子 aa型疾病（a为隐性疾病基因），隐性基因出现的频率 ，求表
兄妹结婚及非近亲结婚的子女中患有苯丙酮尿症的概率。
由前，表兄妹结婚的近交系数为 1/16,故其子女发生该疾病的概率为
而对禁止近亲结婚的群体，子女发生该疾病的概率为q2=10-4。表兄妹（或堂兄妹）结婚使子女发生该疾病的概率增大了大 约倍，由此可见，为了提高全民族的身体素质，近亲结婚是应当 禁止的。
例 X—链遗传模型的一个实例
X—链遗传是指另一种遗传方式：雄性具有一个基 因A或a，雌性具有两个基 因AA，或Aa，或aa。其遗传规律是雄性后代以相等概率得到母体两个基因中的一个，雌性后代从父体中得到一个基因，并从母体的两个基因中等可能地得到一个。下面，研究 与X—链遗传有关的近亲繁殖过程。
（a）假设
（i）从一对雌雄结合开始 ,在它们的后代 中,任选雌雄各一
个成配偶,然后在它们产生的后代中任选两个结成配
偶,如此继续下去 , (在家畜、家禽饲养中常见这种现 象)
（ii）父体与母体的基因型组成同胞对，同胞对的形式有
(A,AA),(A,Aa),(A,aa),(a,AA),(a,Aa),(a,aa) 6种。初始一
对雌雄的同胞对，是这六种类型中的任一种，其后代的
基因型如下表所示。
（iii）在每一代中，配偶的同胞对也是六种类型之一，并
有确定的概率。为计算这些概率 ,设an,bn,cn,dn,en,fn
分别是第n代中配偶的同胞对 为(A,AA)，(A,Aa)，
(A,aa),(a,AA),(a,Aa),(a,aa)型的概率，n=0,1,…。令
（iv）如果第n－1代配偶的同胞对是 （A,Aa）型，那么它
们的雄性后代将等可能地得到基 因A和a，它们的雌
性后代的基因型将等可能地 是AA或Aa。又由于 第n
代雌雄结合是随机的，那么 第n代配偶的同胞对将等
可能地为四种类型 (A,AA),(A,Aa),(a,AA),(a,Aa)之一，
对于其它类型的同胞对，我们可以进行同样分析，
因此有
1
1/2
0
0
0
0
aa
0
1/2
1
1
1/2
0
Aa
0
0
0
0
1/2
1
AA
1
1/2
0
1
1/2
0
a
0
1/2
1
0
1/2
1
AA
后
代
基
因
型
(a,aa)
(a,Aa)
(a,AA)
(A,aa)
(A,Aa)
(A,AA)
父体——母体的基因型
()
其中
从（）式中易得
经过计算，矩阵 M的特征值和特征向量为
，
，
，
，
，
,
M对角化，则有
()
其中：
当
时
因此，当
时，（）式中
即
因此，在极限情况下所有同胞对或者是 （A,AA）型，或者是（a,aa）型。如果初始的父母体同胞对 是（A,Aa）型，即b0=1，而a0= c0= d0= e0= f0=0，于是，当
时
即同胞对是(A,AA)型的概率是2/3，是(a,aa)型的概率为1/3。
（正则链与吸收链）
根据转移矩阵的不同结构，马氏链可以分为多个不同的类型，这里，我们只简单介绍其中常见而又较为重要的两类：正则链与吸收链。
定义2 对于马氏链，若存在一正整 数K，使其转移矩阵 的K次幂MK>0（每一分量均大 于0），则称此马尔链为一正则（regular）链。
定理2 若A为正则链的转移矩阵，则必有：
（1）当 时， ，其中W为一分量均大于零
的随机矩阵。
（2）W的所有行向量均相同。
定理3 记定理 2中的随机矩阵W的行向量为V=(v1,…,vn),则：
（1）对任意随机向 量x，有
（2）V是A的不动点向量,即VA=V, A的不动点向量是唯一的。
定义3 状态Si 称为马氏链的吸收状态，若转移矩阵的 第i 行满足：Pii=1，Pij=0（j≠i）
定义4 马氏链被称为 吸收链，若其满足以下两个条件：
（1）至少存在一个吸收状态 。
（2）从任一状态出发 ,经有限步转移总可到达某一吸收 状态
根据定义3，例中状态S4即
为一吸收链
具有r个吸收状态，n－r个非吸收状态的吸收链，它的n×n转移矩阵的标准形式为
（注：非标准形式可经对状态重新编号 ）
其中Ir为r 阶单位阵，O为r×s零阵，R为s×r 矩阵，S为s×s矩阵。令
上式中的子阵Sn表达了以任何非吸收状态作为初始状态，经过n步转移后，处于s个非吸收状态的概率。
在吸收链中，令F=(I－S) -1，称F为基矩阵。
定理4 吸收链的基矩 阵F中的每个元素，表示从一个非吸收
状态出发，过程到达每个非吸收状态的平均转移次
数。
定理5 设N=FC，F为吸收链的基矩阵，C=(1,1,…,1)T，则N
的每个元素表示从非吸收状态出发，到达某个吸收
状态被吸收之前的平均转移次数。
定理6 设B=FR=（bij），其中F为吸收链的基矩阵，R为T中
的子阵，则bij表示从非吸收状 态i出发，被吸收状态 j
吸收的概率。
例（竞赛问题）
甲乙两队进行一场抢答竞赛，竞赛规则规定：开始时每队各记2分，抢答题开始后，如甲取胜则甲 加1分而乙减1分，反之则乙加1分甲减1分,(每题必需决出胜负 )。规则还规定，当其中一方的得分达 到4分时，竞赛结束。现希望知道： （1）甲队获胜的概率有多大？
（2）竞赛从开始到结束，平均转移的次数为多少？
（3）甲获得1、2、3分的平均次数是多少？
设甲胜一题的概率 为p，（0<p<1），p与两队的实力有关。
甲队得分有5种可能，即0，1，2，3，4。我们分别记为状态S0，S1，S2，S3，S4，其中S0和S4是吸收状态，a1，a2和a3是非吸收状态。过程 以S2作为初始状态。根据甲队赢 得1分的概率为 p，建立转移矩阵：
S 0 S 1 S 2 S 3 S 4
将上式改记为标准形 式T：
其中
计算 F：
令q=1-p，则
因为a2是初始状态，根 据定理4，甲队获分为1，2，3分的平均次数为
，
，
。又
=
=
根据定理5，以a2为初始状态，甲队最终获胜的平均转 移欠
数为
。又因为，
根据定理6，甲队最后获胜的概率
。
