第
3
章
马尔可夫链
..3.1基本概念
本章首先考察取有限个值或者可数个可能值的随机过程{Xn,n=0,1,2,…} 
(n∈T)。一般将这种随机过程的可能值的集合也记为{0,1,2,…}( 即状态空间也

是非负整数集)。如果Xn 
=i,那么称随机过程在时刻
n 
处在状态i。只要过程处

在状态i,就有一个固定的概率pij 
,使它在下一时刻处在状态j。由此有如下定

i0,in-1

义:若对于一切状态{i1,…,}、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 
(3-1)
则称这样的随机过程为马尔可夫链。并称由此式刻画的马尔可夫链的特性为马
尔可夫性,也称无后效性。

上面的定义说明:要确定过程将来的状态,知道它此刻的状态就足够了,并不
需要对它以往状况的认识。也就是说对于一个马尔可夫链,在给定过去的状态
X0,X1,…Xn-1和现在的状态Xn 
时,将来的状态Xn+1 的条件分布独立于过去的
状态,而只依赖于现在的状态。pij 
表示过程处在状态
i 
时下一次转移到状态
j 
的
概率。由于概率值非负且过程必须转移到某个状态,所以有如下性质(状态空间

I={1,2,…}): 

i.即i,Σ(∞) pij 
≥0,
j 
>0( 
j 
∈I)

i=0

Σpij=i=1,2,…( 即
i 
∈I)

j∈T

称P{Xn+1=j|Xn 
==pij 
1,0,
Xn 
n=1,的一步转移概率, 
简称转移概率。
i}为马尔可夫链{,0,2,…} 

由马尔可夫链定义知

P{X0=i0,X1=i1,…,Xn 
=in 
} 
=P{Xn 
=in|X0=i0,X1=i1,…,Xn-1=in-1}P{X0=i0,X1=i1,…,Xn 
=in 
} 
=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} 


第3章 马尔可夫链 89 
可见,一旦马尔可夫链的初始分布P {X0=i0}给定,其统计特性就完全由条件概率所
决定: 
P{Xn =in|Xn-1=in-1} 
如何确定这个条件概率是马尔可夫链理论和应用中的重要问题之一。一般情况下,转
移概率pij与状态i、j 和时间n 有关。当马尔可夫链的转移概率P {Xn+1=j|Xn =j}只与
状态i、j 有关而与n 无关时,称马尔可夫链为齐次的;否则,称其为非齐次的。本章只讨论
齐次马尔可夫链,并将其简称为马尔可夫链。
马尔可夫链
基本概念
当马尔可夫链的状态为有限个时,称为有限链;否则称为无限链。但无论状态是有限的
还是无限的,都可以将pij (i,j∈{0,1,2,…})排成一个矩阵的形式。记为P =(pij ),它
等于
p00 p01 … p0j 
p10 p11 … p1j 
. . . . 
pi0 pi1 … pij 
é
.
êêêêê 
ù
.
úúúúú 
称P 为转移概率矩阵,一般简称为转移矩阵。转移概率矩阵具有前述性质。称具有此性质
的矩阵为随机矩阵(随机矩阵是非负实数矩阵且每一行元素的和为1)。
例3-1 将一个过程转变为马尔可夫链。假设今天是否下雨依赖于前两天的天气条
件。如果前两天都下雨,那么明天下雨的概率为0.7;如果今天下雨但昨天没下雨,那么明天
下雨的概率为0.5;如果昨天下雨但今天没下雨,那么明天下雨的概率为0.4;如果昨天、今天
都没下雨,那么明天下雨的概率为0.2。假设在时间n 的状态只依赖于在时间n-1的状
态,那么上面的模型就不是一个马尔可夫链。但是,当假定在任意时间的状态仅由今天与昨
天两者的天气条件决定时,上面的模型就可以转变为一个马尔可夫链。换言之,可以假定过
程处在以下4种状态: 
. 状态0,如果昨天和今天都下雨。
. 状态1,如果昨天没下雨但今天下雨。
. 状态2,如果昨天下雨但今天没下雨。
. 状态3,如果昨天和今天都没下雨。
这就将本例所给的过程转变成一个具有4个状态的马尔可夫链,其转移概率矩阵为
P= 
0.7 0 0.3 0 
0.5 0 0.5 0 
0 0.4 0 0.6 
0 0.2 0 0.8 
é
.
êêêêê 
ù
.
úúúúú 
.. 3.2 C-K 方程
3.2.1 n 步转移概率 
下面给出n 步转移概率的概念。
p(n) ij =P{Xm+n =j|Xm =i},i,j ∈I,m ≥0,n ≥1 (3-2)

90 人工智能应用的数学基础(微课版) 
为马尔可夫链的n 步转移概率,并称P(n)=(p(n) ij )为马尔可夫链的n 步转移概率矩阵。其中
p(n) ij ≥0,Σj∈T
p(n) ij =1。
当n=1时,P(1) ij =Pij。
当n=0时,p(0) ij = 0,i≠j 
1,i=j { ,即P(0)为单位矩阵。
3.2.2 矩阵的四则运算
3-1 设{Xn ,n≥0}为马尔可夫链,则对任意正整数n,0≤1≤n,和状态i,j∈T ,n 
步转移概率具有下列性质: 
(1)C-K方程。p(n) ij =Σk∈I
p(l) ikp(n-l) kj 。
(2)p(n) ij =Σk1∈I… Σ kn-1∈I
pik1pk1k2 …pkn-1j。
(3)P(n)=PP(n-1)。
(4)P(n)=Pn 。
C-K方程的全称是Chapman-Kolmogorov方程(切普曼-柯尔莫哥洛夫方程) 
证:利用全概率公式和马尔可夫性,有
p(n) ij =P{Xm+n =j|Xm =i}=P{Yk∈I(Xm+l =k),Xm+n =j|Xm =i} 
=Σk∈I
P{Xm+l =k,Xm+n =j|Xm =i} 
=Σk∈I
P{Xm =i,Xm+l =k,Xm+n =j} 
P{Xm =i} 
=Σk∈I
P{Xm =i}P{Xm+l =k|Xm =i}P{Xm+n =j|Xm =i,Xm+l =k} 
P{Xm =i} 
=Σk∈I
P{Xm+l =k|Xm =i}P{Xm+n =j|Xm+l =k} 
=Σk∈I
P(l) ik (m )P(n-l) kj (m +l)=Σk∈I
P(l) ikP(n-l) kj 
(1)式得证。这是关于转移概率的一个重要结果。C-K 方程直观上可以作如下解释: 
图 3-1 
马尔可夫链{Xn ,n≥0}在时刻m 处于状态i,经过n 
步,即在时刻n+m 转移到状态j 的过程可以视为
它在时刻m 处于状态i,先经过l 步,即在时刻m +l 
遍历所有状态k(k=1,2,3,…),然后再经过n-l 
步,即在时刻n+m 转移到状态j 的过程,如图3-1 
所示。
C-K方程的矩阵形式为P(n)=P(l)P(n-l),当l= 
1时,即为P(n)=PP(n-l),(3)式得证。再利用归纳
法可证(4)。
在(1)式中令l=1,k =k1,得p(n) ij =Σk∈I
pik1p(n-1) k1j ,这是一个递推公式,逐步递推可得
(2)式。

第3章 马尔可夫链 91 
例3-2 随机游动。设质点在线段上做随机游动,如图3-2所示。每隔1s移动一步。
当质点处于“0”点时,必然以概率1向右移动一步至“1”点;当质点处于“4”点时,下一步必然
以概率1向左移动一步至“3”点;当质点处于其他点时,下一步便均分别以概率1/3向左、向
右移动一步或停留在原地不动。
图 3-2 
令Xn 表示n 次移动后质点所处的位置。显然,{Xn ,n≥0}为一个齐次马尔可夫链,其
状态空间为I={0,1,2,3,4}。试求{Xn ,n≥0}的一步和二步转移概率矩阵。
解:按题意可知
p00 =P(Xm+1 =0|Xm =0)=0 
p01 =P(Xm+1 =1|Xm =0)=1 
p02 =P(Xm+1 =2|Xm =0)=0 
同样可求得其他转移概率: 
p03=0,p04=0,p11=13
,p12=13
,p13=13
,p14=0,…。
于是便得到一步转移概率矩阵:
0 1 0 0 0 
13
13
13
0 0 
0 13
13
13
0 
0 0 131313 
0 0 0 1 0 
é
.
êêêêêêêêêêê 
ù
.
úúúúúúúúúúú 
二步转移概率矩阵为
0 1 0 0 0 
13
13
13
0 0 
0 13
13 13
0 
0 0 13
13
13 
0 0 0 1 0 
é
.
êêêêêêêêêêê 
ù
.
úúúúúúúúúúú 0 1 0 0 0 
13
13
13
0 0 
0 13
13
13
0 
0 0 13
13
13 
0 0 0 1 0 
é
.
êêêêêêêêêêê 
ù
.
úúúúúúúúúúú 
= 
13
13
13
0 0 
19
59
29
19
0 
19
29
39
29
19 
0 19
29
59
19 
0 0 13
13
13 
é
.
êêêêêêêêêêêêêê 
ù
.
úúúúúúúúúúúúúú

92 人工智能应用的数学基础(微课版) 
.. 3.3 马尔可夫链的状态分类
3.3.1 互达性和周期性 
定义3-1 设i 和j 是齐次马尔可夫链的两个状态。如果存在n≥0,使得P(n) ij >0,则
称从状态i 可达状态j,记作i→j;而如果对一切n≥0,有P(n) ij =0,则称从状态i 不可达状
态j。若i→j 且j→i,则称状态i 和j 互达(相通),记作i.j。引入互达性概念是为了对状
态进行分类。
命题3-1 互达性是等价关系,即它满足以下性质: 
(1)自反性:i.j。
(2)对称性:若i.j,则j.i。
(3)传递性:若i.k 且k.j,则i.j。
证:只证明(3)。若i.k 且k.j,则存在整数n 和m 使得
P(n) ik >0,P(m) kj >0 
由C-K方程得
P(n+m) ij =Σr 
P(n) ir P(m) rj ≥P(n) ik P(m) kj >0 
即i→j。类似可证j→i。
在数学上,等价关系可以用于对集合进行分割。因此,也可以利用互达性对状态空间进
行分类,并且这些类在互达关系下是等价类。
定义3-2 一个马尔可夫链的状态空间,如果在互达性这一等价关系下都居于同一类, 
那么就称这个马尔可夫链是不可约的;否则,这个马尔可夫链就被称为是可约的。引入可约
和不可约概念是为了以后研究状态的周期,进一步是为了研究转移概率的极限性质。
例3-3 若马尔可夫链有转移概率矩阵
P= 
0.6 0 0 0.4 0 
0 0.4 0 0 0.6 
0 0 1 0 0 
0.4 0 0 0.6 0 
0 0.6 0 1 0.4 
é
.
êêêêêêê 
ù
.
úúúúúúú 
给出这个马尔可夫链状态的等价类,并且试给出其n 步转移概率矩阵。
解:等价类为{1,4}、{2,5}和{3}。其中3为吸收态。
0.6 0.4 
0.4 0.6 
é
. êê
ù
. úú 
n 
= 
1+0.2n 
2 
1-0.2n 
2 
1-0.2n 
2 
1+0.2n 
2 
é
.
êêêêê 
ù
.
úúúúú 
0.4 0.6 
0.6 0.4 
é
. êê
ù
. úú 
n 
= 
1+ (-0.2)n 
2 
1- (-0.2)n 
2 
1- (-0.2)n 
2 
1+ (-0.2)n 
2 
é
.
êêêêê 
ù
.
úúúúú

第3章 马尔可夫链 93 
P(n)=12 
1+0.2n 0 0 1-0.2n 0 
0 1+ (-0.2)n 0 0 1- (-0.2)n 
0 0 2 0 0 
1-0.2n 0 0 1+0.2n 0 
0 1- (-0.2)n 0 1 1+ (-0.2)n 
é
.
êêêêêêê 
ù
.
úúúúúúú 
→ 
0.5 0 0 0.5 0 
0 0.5 0 0 0.5 
0 0 1 0 0 
0.5 0 0 0.5 0 
0 0.5 0 1 0.5 
é
.
êêêêêêê 
ù
.
úúúúúúú 
,n → ∞ 
定义3-3 设i 为马尔可夫链的一个状态,使p(n) ii >0的所有正整数n(n≥1)的最大公
约数称为状态i 的周期,记作d(i)或di。如果对所有n≥1都有p(n) ii =0,则约定周期为∞, 
称d(i)=1的状态i 为非周期性的。当状态i 的周期为d 时,p(d) ii >0不一定成立。
推论 如果n 不能被周期d(i)整除,则必有p(n) ii =0。
例3-4 若马尔可夫链有状态0、1、2、3和转移概率矩阵
P= 
0 1 0 0 
0 0 1 0 
0 0 0 1 
0.5 0 0.5 0 
é
.
êêêêê 
ù
.
úúúúú 
试求状态0的周期。
解:状态转移可以用图3-3和图3-4表示。
图 3-3 图 3-4 
P0(20n)= 1 
2n-1,n ≥2 
P0(20)=0,P0(20n-1)=0,n ≥1 
所以d(0)=2。
命题3-2 如果i.j,则di=dj。
证:设m ≥1,n≥1,使得P(m) ij >0,P(n) ji >0,则
P(m +n) ii ≥P(m) ij P(n) ji >0,P(m +n) jj ≥P(m) ij P(n) ji >0 
因此,m +n 同时能被di 及dj 整除。若P(s) ii >0,则对于任意的s≥1满足P(s) ii >0, 
因此

94 人工智能应用的数学基础(微课版) 
P(m +s+n) jj ≥P(m) ji P(s) ii P(n) ij >0 
即m +s+n 也能被dj 整除。因此,s 能被dj 整除。从而dj 整除{m ≥1:P(m) ii >0}的最大
公因子di。根据对称性,di 也整除dj。所以di=dj。
引入状态周期概念的目的是为了研究状态转移矩阵的极限性质,即当n 取不同值时
P(n)的极限,这个矩阵可以反映马尔可夫链在平稳状态时的特征。因此,下面将讨论周期
的基本性质,为此先给出数论中的一个结论。
引理3-1 设s≥2,正整数s1,s2,…,sm 的最大公因子为d,则存在正整数N ,使得n >N 
时必有非负整数c1,c2,…,cm 使nd =Σm 
i=1
cisi。
命题3-3 如果状态i 有周期d,则存在整数N ,使得对所有n≥N 恒有P(nd) ii >0。
证:这时存在正整数s1,s2,…,sm ,使得它们的最大公因子为d, 
P(sk ) ii >0,k=1,2,…,m 
由引理3-1,存在正整数N ,使得n>N 时,必有非负整数c1,c2,…,cm 使
nd =Σm 
i=1
cisi 
从而
P(nd) ii ≥ (P(s1) ii )c1 (P(s2) ii )c2 … (P(sm ) ii )cm >0 
推论3-1 设状态i 的周期为di。如果P(m) ji >0,则存在整数N ,使得对所有n≥N 恒
有P(m +ndi) ji >0。
命题3-4 设P 为一个不可约、非周期、有限状态马尔可夫链的转移矩阵,则必存在N , 
使得当n≥N 时,P(n)的所有元素都大于0。
证:由于马尔可夫链是不可约的,过程的任两个状态i 和j 都是互达的,于是m (与i 和
j 有关)使得P(m) ii >0。由推论3-1和马尔可夫链的非周期性知,存在N ,使得当n≥N 时, 
P(m +n-1) ij >0,因为状态空间有限,对全部的状态对(i,j),求出N (i,j)。并取N = 
m(ia,jx){m (i,j)+N (i,j)},则显然对所有状态i 和j,当n>N 时有P(n) ij >0。
例3-5 若马尔可夫链有转移概率矩阵
P= 0.6 0.4 
0.4 0.6 
é
. êêù
. úú 
显然这是一个不可约、非周期、有限状态的马尔可夫链,其n 步转移概率矩阵为
P(n)= 
1+0.2n 
2 
1-0.2n 
2 
1-0.2n 
2 
1+0.2n 
2 
é
.
êêêêê 
ù
.
úúúúú 
3.3.2 常返与瞬过
定义3-4 f(0) ij =0,f(n) ij =P{Xn =j,Xk ≠j,k=1,2,…,n-1|X0=i}(n≥2),则f(n) ij 
表示从状态i 出发在第n 次转移时首次到达状态j 的概率。
定义3-5 f(0) ii =0,f(n) ii =P{Xn =i,Xk ≠i,k=1,2,…,n-1|X0=i}(n≥2),则f(n) ii 
表示从状态i 出发在第n 次转移时首次回到状态i 的概率。

第3章 马尔可夫链 95 
定义3-6 Σ∞ 
n=1
f(n) ij =fij,则fij 表示从状态i 出发最终到达状态j 的概率。
性质:当i≠j 时,i→j.fij>0。
定义3-7 如果fii=1,称状态i 是常返的;如果fii<1,称状态i 为非常返的或瞬过的。
注意,如果状态i 是常返的,那么从状态i 出发经过有限步转移后又回到i 的概率为1。
定义3-8 τij表示在0时刻从状态i 出发首次到达状态j 所需的转移步数,即
τij=inf{n≥1:Xn =j|X0=i} 
如果{n≥1:Xn =j|X0=i}=.,则τij=+∞。此时有
P{τij=n}=f(n) ij 
因此
P{τij < ∞}=Σ∞ 
n=1
f(n) ij =fn
ij 
上式说明了为什么fii=1表示常返。
3-2 状态i 是常返的.Σ∞ 
n=1
P(n) ii =∞。状态i 是瞬过的.Σ∞ 
n=1
P(n) ii < ∞。
由过程的马尔可夫性,一旦回到I,过程以后的发展只依赖于当前的状态,因此从i 出
发至少回到i 两次的概率是f2ii,依此类推。用随机变量K 表示过程返回i 的次数,则
P{K ≥k|X0=i}=fk
ii, k=1,2,3,… 
于是K 的条件期望为
E(K |X0 =i)=Σ∞ 
K =1
P{K ≥k|X0 =i}=Σ∞ 
K =1
fK 
ii = 
fii 
1-fii,fii <1 
显然,E(K|X0=i)<∞。
下面将证明
Σ∞ 
n=1
P(n) ii =E(K |X0 =i) 
令In = 1, 若Xn =i 
0, 若Xn ≠i { 
则K =Σ∞ 
n=1
In 
于是
Σ∞ 
n=1
P(n) ii =Σ∞ 
n=1
P{Xn =i|X0 =i}=Σ∞ 
n=1
E{In |X0 =i}=E{Σ∞ 
n=1
In |X0 =i} 
=E{K |X0 =i} 
因此Σ∞ 
n=1
P(n) ii =Σ∞ 
n=1
Pn
ii 
由于状态i 是瞬过的.fii<1,故状态i 是瞬过的. Σ∞ 
n=1
P(n) ii < ∞。
推论3-2 如果i 是常返的,且i.j,则j 也是常返的。由i.j 知,存在m、n,使P(m) ji >0 
且P(n) ij >0。于是,对任何正整数s>0,有
P(m +s+n) jj ≥P(m) ji P(s) ii P(n) ij

96 人工智能应用的数学基础(微课版) 
因此Σ∞ 
n=1
P(k) jj ≥ Σ∞ 
s=1
P(m+s+n) jj ≥P(m) ji P(n) ij Σ∞ 
s=1
P(s) ii =∞ 
例3-6 考虑在整数点上的随机游动。向右移动一格的概率为p,向左移动一格的概率
为q=1-p。从原点0出发,则一步转移概率矩阵为
P = 
M M M M M 
… 0 p 0 0 0 … 
… q 0 p 0 0 … 
… 0 q 0 p 0 … 
… 0 0 q 0 p … 
… 0 0 0 q 0 … 
é
.
êêêêêêêê
ê 
ù
.
úúúúúúúú
ú 
-2 
-1012 
因此P0(20n-1)=0, P0(20n)=Cn 2nPnqn , n =1,2,3,… 
由斯特林(Stirling)公式知,当n 充分大时, 
n! ~ 2πe-nnn+12 
于是
P0(20n)~(4pq)n 
nπ = 
1 nπ, p=12 
cn 
nπ, p≠12 
ì
.
í
... 
..
. 
, c<1 
因此,当p=0.5时, 
Σ+∞ 
n=1
P0(n0)=∞ 
当p≠0.5时, 
Σ+∞ 
n=1
P0(n0) < ∞ 
即,当p=0.5时状态0是常返的,当p≠0.5时状态0是瞬过的。
定义3-9 对常返状态i 定义Ti 为首次返回状态i 的时刻,即
Ti=inf{n≥1:Xn =i,Xk ≠i,k=1,2,…,n-1|X0=i} 
称为常返时。
记μi =E(Ti),则有μi =Σ∞ 
n=i
nfn
ii,所以μi 是首次返回i的期望步数,称为状态i的平均
常返时。
定义3-10 一个常返状态i 当且仅当μi=∞时称为零常返的,当且仅当μi<∞时称为
正常返的。
.. 3.4 极限定理及平稳分布
例3-7 设马尔可夫链的转移矩阵为
P= 1-p p 
q 1-q 
é
. êê
ù
. úú 
,0<p,q<1

第3章 马尔可夫链 97 
(1)试求状态1、2的n 步首达概率并求μi,i=1,2。
(2)求P(n)并考虑当n→∞的情况。
解: 
(1)f1(11)=1-p,f1(21)=P(X2=1,X1≠1|X0=1)=pq,… 
f1(n1)=p (1-q)n-2q,n=2,3,4,… 
因此μi =Σ∞ 
n=1
nf1(n1)=1-p + Σ∞ 
n=2
np (1-q)n-2q =p +q 
q 
同理
f2(12)=1-q,f2(n2)=q (1-p)n-2p,n =2,3,4,… 
因此μ2=p+q 
p 
f1(n2)=(1-p)n-1p,n =1,2,3,… 
f2(n1)=q(1-q)n-1,n =1,2,3,… 
(2)(λI-P)=0.λ=1,λ=1-p-q,取
Q = 1 -p 
1 Q 
é
. êê
ù
. úú 
,D = 1 0 
0 1-p -q 
é
. êê
ù
. úú 
,Q-1 = 
q 
p +q 
p 
p +q 
- 1 p +q 1 p +q 
é
.
êêêêê 
ù
.
úúúúú 
从而
P = 1-p P 
q 1-q 
é
. êê
ù
. úú
=QDQ-1 
P(n)=QD(n)Q-1 = 
q +p(1-p -q)n 
p +q 
p -p(1-p -q)n 
p +q 
q -q(1-p -q)n 
p +q 
p +q(1-p -q)n 
p +q 
é
.
êêêêê 
ù
.
úúúúú 
lim n→∞
P(n) ii = 
q 
p +q 
p 
p +q 
q 
p +q 
p 
p +q 
é
.
êêêêê 
ù
.
úúúúú 
表明
lim n→∞
P(n) i1 = q 
p +q = 1 
μ1 
lim n→∞
P(n) i2 = q 
p +q = 1 
μ2 
3.4.1 极限定理
定理3-3 
3-3 若状态j 是周期为d 的常返态,则
lim n→∞
P(nd) jj =d 
μj 
推论3-3 若状态j 是常返态,则

98 人工智能应用的数学基础(微课版) 
j 是零常返态.P(n) jj →0 
3-4 若j 是瞬过态或零常返态,则对任意i∈S,有
lim n→∞
P(n) ij =0 
3-5 若j 是正常返态且周期为d,则对任意i 及0≤r≤d-1,有
lim n→∞
P(nd+r) ij =f(r) ij 
d 
μj 
推论3-4 设{Xn}是不可约遍历链,则.i,j∈E,有
lim n→∞
P(n) ij =1 
μj >0 
3.4.2 平稳分布与极限分布
定义3-11 对于马尔可夫链{Xn ,n≥0},若
πj =Σi∈S
πipij 
Σj∈S
πj =1,πj ≥0 
称概率分布{πj,j∈S}是平稳的。
3-6 不可约马尔可夫链是遍历链.对任意i,j∈S,存在仅依赖于j 的常数πj, 
使得
lim n→∞
P(n) ij =πj 
πj 称为马尔可夫链的极限分布,且有
πj =Σi∈S
πipij (3-3) 
例3-8 设有6个车站,车站之间的公路连接情况如图3-5所示。汽车每天凌晨可以从
图 3-5 
一个车站驶向与之直接相邻的车站,并在夜晚到达车站
留宿,次日凌晨重复相同的活动。设每天凌晨汽车开往
直接相邻的任一车站是等可能的。试说明很长时间后各
车站每晚留宿的汽车比例趋于稳定。求出这个比例,以
便正确地设置各车站的服务规模。
解:以{Xn ,n=0,1,2,…}记第n 天某辆汽车留宿
的车站号,这是一个马尔可夫链,转移概率矩阵通过解以
下方程组得到: 
πP =π 
Σ6 
i=1
πi =1 
ì
.
í
.. 
.. 
其中,π=(π1,π2,π3,π4,π5,π6)。
πP=π 是6个方程的方程组,记Pi 为P 的列元素,则它们是
Pi =πi,i=1,2,…,6 
π = 18
,3 
16,18
,3 
16,18
,14
.
è .
.
. ÷

第3章 马尔可夫链 99 
P = 
0 12
0 0 0 12 
13
0 13
0 0 13 
0 12
0 12
0 0 
0 0 13
0 13
13 
0 0 0 12
0 12 
14
14
0 14
14
0 
é
.
êêêêêêêêêêêêêêêêê 
ù
.
úúúúúúúúúúúúúúúúú 
可见,无论开始时汽车从哪一个车站出发,在很长时间后,它在任何一个车站留宿的概
率都是稳定的,从而可知所有的汽车都将以一个稳定的比例在各车站留宿。
.. 3.5 隐马尔可夫过程
本节要研究的隐马尔可夫过程(HMM)的本质是基于一种动态的情况进行推理,或者
说是根据历史进行推理。假设要为一个高血压病人提供治疗方案,医生每天为他量一次血
压,并根据血压的测量值调配用药剂量。显然,一个人当前的血压情况是跟他过去一段时间
的身体情况、治疗方案、饮食起居等多种因素息息相关的,而当前的血压测量值相当于对他
当时身体情况的一个估计,而医生当天开的处方应该是基于当前血压测量值及过往一段时
间病人的多种情况综合考虑后的结果。为了根据历史情况评价当前状态,并且预测治疗方
案的结果,就必须对这些动态因素建立数学模型。而隐马尔可夫模型就是解决这类问题时
最常用的一种数学模型。简单来说,隐马尔可夫模型是用单一离散随机变量描述过程状态
的时序概率模型。下面用一个简单的例子说明。
假设一个人手里有3个不同的骰子。第一个骰子是普通的立方体骰子(称这个骰子为
图 3-6 
D6),有6个面,每个面(1~6)出现的概率是1/6;第二
个骰子是四面体(称这个骰子为D4),每个面(1~4)出
现的概率是1/4;第三个骰子有8个面(称这个骰子为
D8),每个面(1~8)出现的概率是1/8。这3个骰子如
图3-6所示。
此人开始掷骰子,他先从3个骰子里挑一个,挑到
每一个骰子的概率都是1/3。然后掷骰子,得到一个数字,为1~8中的一个。不停地重复
上述过程,就会得到一串数字,每个数字都是1~8中的一个。例如,可能得到这样的一串数
字(掷骰子10次): 
1635273524 
这串数字称为可见状态链。但是在隐马尔可夫模型中,并非仅有一串可见状态链,还有一串
隐含状态链。在这个例子里,这串隐含状态链就是该人使用的骰子的序列。例如,隐含状态
链有可能是

100人工智能应用的数学基础(微课版) 
D6D8D8D6D4D8D6D6D4D8 
如图3-7所示。
图3-7
一般来说,隐马尔可夫链中的马尔可夫链其实是指隐含状态链,因为隐含状态之间存在
转换概率(transitionprobability)。在上面的例子里,D6 
的下一个状态是D4、D6和D8,转换概率都是1/3,D4和
D8的下一个状态也是D4、D6和D8,转换概率也都是1/3 
(见图3-8)。这样设定是为了最开始容易说清楚,但是
转换概率其实是可以随意设定的。例如,可以这样定
义:D6后面不能接D4,D6后面是D6的概率是0.9,是
D8的概率是0.

1。这样就是一个新的隐马尔可夫链。

同样,尽管可见状态之间没有转换概率,但是隐含
状态和可见状态之间有一个概率,称为输出概率图3-
8 
(emisionprobability)。就上面的例子来说,六面骰子
(D6)产生1的输出概率是1/6,产生2~6的输出概率也都是1/6。同样可以对输出概率作
其他定义。例如,某人有一个被赌场动过手脚的六面骰子,掷出来是1的概率是1/2,掷出
来是2~6的概率都是1/10 。其实对于隐马尔可夫链来说,如果提前知道所有隐含状态之
间的转换概率和所有隐含状态到所有可见状态之间的输出概率,进行模拟是相当容易的。
但是应用隐马尔可夫链模型时往往是缺失了一部分信息。有时候知道骰子有几种,每种骰
子是什么,但是不知道掷出来的骰子序列;有时候只是看到了很多次掷骰子的结果,此外什
么都不知道。如果应用算法估计这些缺失的信息,就成了一个很重要的问题。

例3-
9 

题目背景

从前有个村子,村里的人的身体情况只有两种可能:健康或者发烧。假设这个村的人
没有体温计(或者百度这种神奇的东西),人唯一能判断自己身体状况的途径就是到村头甲
开设的诊所询问。甲通过村民的描述判断病情。再假设村民只会说正常、头晕或冷。村里
的乙连续3天去甲的诊所询问。乙第一天告诉甲,感觉正常;第二天告诉甲,感觉冷;第三天
告诉甲,感觉头晕。那么,甲如何根据乙的描述推断出这3天中乙的身体状况呢? 甲通过如
下已知情况便可以推断乙的身体状况。

已知情况和算法

隐含的身体状况为{健康,发烧}。


第3章马尔可夫链101 

可观察的感觉状态为{正常,冷,头晕}。
6,发烧:0.甲预判的乙身体状况的概率分布为{健康:0.4}。
甲认为的乙身体状况的转换概率分布为{健康→健康:0.健康→发烧:0.发烧→健
4,6}。
7,3, 

康:0.发烧→发烧:0.
甲认为的在相应健康状况条件下乙的感觉的概率分布为{健康,正常:0.5,冷:0.4,晕: 

0.1;发烧, 1, 3, 6}。
正常:0.冷:0.头晕:0.
乙连续3天的身体感觉依次是正常、冷、头晕
。


问题

乙这3天的身体状况变化的过程是怎样的? 

过程

根据维特比理论,后一天的状态会依赖前一天的状态和当前的可观察的状态。那么只

要根据第一天的正常状态依次推算出到第三天头晕状态的最大概率,就可以知道这3天的

身体状况变化情况。

=0.=0.

(1)初始情况:P(健康)6,P(发烧)4。
(2)求第一天的身体状况,即计算在感觉正常的情况下最可能的身体状况
。
P(今天健康)=P(健康|正常)P(健康|初始情况)=5×0.0.
0.6=3 
P(今天发烧)发烧|正常)发烧|初始情况)0.4=04 

=P( P( =1×0.0.
那么就可以认为第一天最可能的身体状况是健康
。


(3)求第二天的身体状况
。
由第一天的发烧或者健康转换到第二天的发烧或者健康有4种可能
:
P(前一天发烧,今天发烧)=P(发烧|前一天)P(发烧→发烧)P(冷|发烧) 
=0.6×0.0.

04×0.3=0072 
P(前一天发烧,今天健康)=P(健康|前一天)P(发烧→健康)P(冷|健康) 
=0.4×0.0.

04×0.4=0064 
P(前一天健康,今天健康)=P(发烧|前一天)P(健康→健康)P(冷|健康) 
=0.7×0.0.

3×0.4=084 
P(前一天健康,今天发烧)=P(健康|前一天)P(健康→发烧)P(冷|发烧) 
=0.3×0.3×0.0.
可以认为,第二天最可能的状况是健康。
3=027 

(4)求第三天的身体状况。
P(前一天发烧,今天发烧)=P(发烧|前一天)P(发烧→发烧)P(头晕|发烧) 
=0.6×0.0.

027×0.6=00972 
P(前一天发烧,今天健康)=P(健康|前一天)P(发烧→健康)P(头晕|健康) 
=0.4×0.0.

027×0.1=00108 
P(前一天健康,今天健康)=P(发烧|前一天)P(健康→健康)P(头晕|健康) 
=0.7×0.0.

084×0.1=00588 
P(前一天健康,今天发烧)=P(健康|前一天)P(健康→发烧)P(头晕|发烧) 
=0.3×0.0.

084×0.6=01512
可以认为,第三天最可能的状况是发烧
。



102人工智能应用的数学基础(微课版) 
结论
根据如上计算,可以推断,乙这3天身体变化的序列是健康→健康→发烧。
..3.6马尔可夫链的应用
3.6.1群体消失模型
考虑一个从单个祖先开始的群体。每个个体生命结束时以概率pj(j=0,1,2,…) 产生
j个新的后代,与其他的个体产生的后代个数相互独立。初始的个体总数以X0 表示,称为
第零代的总数;第零代的后代构成第一代,其总数记为X1;第一代的每个个体以同样的分布
产生第二代…… 一般地,以Xn记第n代的总数。此马尔可夫链{Xn,n=0,1,2,…} 称为离
散分支过程。
现在假设群体是从单个祖先开始的,即X0=1,则有
Xn=Σ Xn-1 
i=1 
Zn,i(3-4) 
其中Zn,i表示第n代的第i个成员的后代个数。
首先考虑第n代的平均个体数E[Xn], 对Xn取条件期望,有
E[Xn]=E[E[Xn|Xn-1]]=μE[Xn-1]=…=μn(3-5)
∞ 
其中,μ= 
Σipi 
为每个个体的后代个数的均值。

i=0

.若μ<1,平均个体数单调下降并趋于0。
.若μ=1,各代平均个体数相同。
.若μ>1,平均个体数按照指数阶上升至无穷。
下面就考虑群体最终会消亡的概率π0。对第一代个体数取条件概率,则
群体消亡}群体消亡|X1πj

π0=P{ 
= Σ(∞) P{ =j}pj = Σ(∞) 0pj 

j=j=

上面的公式意为:若群体最终灭则以第一代为祖先的
j 
个家全部消亡,而各家
族已经假定为独立的,每一家族灭绝的概率均为π0。绝,(0) 族将(0) 
3-
7 
设p0>0,p0+p1<1,则(不考虑p0=0和p0=1)平凡情况如下: 

(1)π0 是满足π0πj的最小正数。
= Σ(∞) 0pj 

定理3-
7 
(2)π0=1.μ≤1 。
j=0 
证:为了证明π0 是(1)中等式的最小解,设π≥0 满足该等式。用归纳法证明,对一切
n,0}, 现有

π≥P{Xn 
=

πj

π= Σ(∞) 0pj 
≥π0p0=p0=P{X1=0}

j=0 

假定π≥P{Xn 
=0} 

∞ 

jπj

则P{Xn+1=0}=Σ(∞) P{Xn+1=0|X1=j}pj = Σ(∞) (P{Xn 
=0})pj 
≤Σ 0pj 
=
π 

j=0 j=0 j=0 

因此,对一切n,Xn 
=0}。令n→∞,iP{Xn 
==群体消亡}π0。(1)得证。

π≥P{π≥lm 0}P{=

n→∞ 


第3章马尔可夫链103
下面证明(2) 。首先定义母函数: 
Φ(s)=Σ ∞ 
j=0 
sjpj
因此p0+p1<1 。所以,对一切s∈(0,1), 有
Φ″(s)=Σ ∞ 
j=0j(j-1)sj-2pj>0 
因此Φ(s)在开区间(0,1)中是严格单调递增的凸函数,分两种情况: 
第一种情况:对一切s∈(0,1),Φ(s)>s。
第二种情况:对某个s∈(0,1),Φ(s)=s,于是
Φ'(π0)≤π0,π0=1.Φ'(1)≤1,Φ'(1)=μ
故(2)得证。
在实际应用中,考虑一个群体的真实增长时,离散分支过程的假定在群体达到无限之前
就不成立了(比如独立同分布性) 。但另一方面,利用离散分支过程研究消亡现象是有意义
的,因为一般灭绝常常发生在过程的早期。
3.6.2人口结构变化的马尔可夫链模型
考虑社会的教育水平与文化程度的发展变化,可以建立如下模型:将全国所有16 岁以
上的人口分为文盲、初中、高中(含中专) 、大学(含大专) 、中级技术人才、高级技术人才、特级
专家7类,结构的变化为升级、退化(例如初中文化者会重新变为文盲)、进入(例如年龄达
到16 岁或移民进入)、迁出( n1(n2(n3(表示在
t 

年各等级的人数。
例如死亡或移民到国外)。用(t),t),…,t)) 

N 
(t)
= Σ(7) t)(

ni(36)

=1 

为全社会16 岁以上人口总数(简称为总人数),(i) 以qij 
记为每年从
i 
级转为
j 
级的人数占
i 
级
人数的百分百,则
Q 
=(j)

q7×7 

是一个准转移矩阵(每行所有元素之和不超过1)。(i) 考虑进入与迁出。记wi 
为每年从
i 
级迁出的人数占
i 
级人数的比例,
i 
为每年进入i

r

级的人数占总进入人数的比例,则

7 

Σ(7) qij 
+wi 
=1,ri 
≥0,Σri=1 

i=1i=1

记R(为总进入人数,t)为总迁出人数,则

t) 
W (
N 
(=
N 
(t)-
W 
(t)


t+1)t)+R(

(Σ(7) t)(

t)t)

njt+1)
= 
ni(qij 
+rjR(-njwj 

i=1 

M 
(=
N 
(-
N 
(=t)t)

t)t+1)t)R(-
W 
(
设总人(令) 数以常数百分比
α 
增长(可以为负增长), 即
N 
(t+1)

M 
(=t),α= 
N 
(-1

t)αN 
(t)


1 04 人工智能应用的数学基础(微课版) 
记αj(t)=nj(t) 
N (t),则αj(t+1)= 1 
1+α Σ7 
i=1
[ αj(t)(qij +rjwi)-wjαj(t)+αrj ] 
特别地,当α=0时, 
αj(t+1)=Σ7 
i=1
αj(t)(qij +rjwi)-wjαj(t) 
记α(t)=(α1(t),α2(t),…,α7(t)),P=(pij),其中
pij= qij+rjwi, i≠j 
qij+rjwi-wj,i=j { 
则上式变为α(t+1)=α(t)P。这是一个以P 为转移矩阵的马尔可夫链在t+1时刻的分布
所满足的方程。
在实际中,总是希望人口结构维持一个合理的稳定水平α* ,文盲越少越好,而专家也无
须太多,并且从现在的α(0)出发,通过控制人口进入各级的比例r=(r1,r2,…,r7)尽快地
达到这个稳定水平。为此,接下来讨论在不同的r 下全部可能的稳定结构。
由于α=αP(因为α 是稳定的),即
α=α(Q+(rjwi)-(wjδij))=αQ+(αw')r-(α1w1,α2w2,…,α7w7) 
其中,w =(w1,w2,…,w7),r=(r1,r2,…,r7)。当αw'≠0时, 
r=α[I-Q+(wjδij)](αw')-1 
即α=(αw')r [I-Q+(wjδij)]-1 
又因为要求ri≥0, 
αj ≥ Σ7 
i=1
αiqij -αjwj(.j) 
可以找出r,使得
α=αQ+αw'r-α(wjδij)=αP 
从而对于此r,α 是一个稳定的结构。
3.6.3 数据压缩与熵
信息存储和恢复的数学理论基础是由香农建立的。作为马尔可夫过程的应用,本节讨
论这一理论的一个方面。假定文字是由有限字母集S={a1,a2,…,am }中的符号构成的。
术语“文字”不是仅仅指人类语言中的文字,还可以有更广泛的意义,例如DNA 的基因序
列、计算机中的数据、音乐等。
加密编码规则是一个变换。它将一个文字序列用另一个文字序列代替并且能够唯一地
再现原来的文字序列(解码)。为了简单起见,本节只考虑加密编码。
一个符号序列代表一个单字,符号的个数是它的长度。一个长度为t 的单字通过加密
算法被加密成长度为s 的代码。为了压缩文字,就要用短的代码代表使用频率高的序列,而
用长的代码代表很少使用的序列。在这种关系中,文字的统计结构(字频)将扮演重要角色。
现在考虑符号在序列中出现的频率服从一个具有平稳性的、其转移概率矩阵为(pij:i, 
j=1,2,…,M )的马尔可夫链。
香农提出了英文的马尔可夫逼近方法。
打开一本英文书,随机地选取一个字母,比如T;跳过几行以后再读,直到再次遇到T,

第3章 马尔可夫链1 05 
选取其后的第一个字母,例如H;跳过更多行后继续读,直到再次遇到H,选取其后的第一
个字母,例如A……继续这样的步骤,得到一个文字样本,这一文字比按照英语语法组成的
文字更接近马尔可夫链。
不仅如此,我们还希望这种做法能够使得文字表现得比随机选择的字母更加接近英语语法
结构。因此,也可以考虑以更高阶的马尔可夫链逼近英语语法结构,例如选择后面的两个字母。
令过程X1,X2,X3,…具有状态空间S、平稳的转移概率矩阵(pij)和唯一的不变初始
分布π=π1,则Xn 是一个平稳过程,并且长度为t 的单字a={ai1,ai2,…,ait}出现的概率
为πi1pi1,i2pi2,i3…pit-1,it。
假定在编码变换下,单字a={ai1,ai2,…,ait}加密为一个长度为s={ai1,ai2,…,ait} 
的单字。令
μt=E[c(a={ai1,ai2,…,ait})] 
t 
μt 代表文字长度t 的压缩率。
给定一种类型的文字,它能够被一种编码压缩的最佳范围由压缩系数确定: 
μ=lim t→∞supμt 
在这里考虑的问题是用给定文字的马尔可夫结构的参数计算压缩系数和构造最佳的压
缩编码。下面将证明最佳的压缩系数(最佳的意义是,虽然有些编码的压缩系数会任意接
近,但是绝不会超过μ)为
μ = H 
log2M =Σi 
πiHi 
log2M =-Σi 
πi Σj 
( pijlog2pij ) 
log2M (3-7) 
Hi =Σj 
pijlog2pij 代表状态i 转移分布的熵,它测量的是当马尔可夫链从状态i 向前
移动一步时所得的信息。
H =Σi 
πiHi 称为马尔可夫链的熵。容易看出,对给定的马尔可夫链的转移概率,一旦
不变初始分布确定,则最佳压缩系数可根据式(3-7)计算。
对于一个长度为t 的单字a,令Pt(a)=P{(X0,X1,…,Xt-1)=a},则
-log2pt(X0,X1,…,Xt-1)=-log2π(X0)+ Σi (-log2pXi,Xi+1)=Y0 + Σi 
Yi
(3-8) 
这里Y1,Y2,Y3,…是一个平稳的有界随机变量序列。应用大数定理于这一平稳序列, 
可以得到
lim t→∞ 
-log2pt(X0,X1,…,Xt-1) 
t =EY1 =H (3-9) 
式(3-9)的一个重要而且有用的推论是:为了减小概率,将所有字长为t 的Mt 个单字
排列为a(1),a(2),…,a(Mt)。对任何正数ε<1,令
Nt(ε)=min N :ΣN 
i=1
{ pt(a(i))≥ε} (3-10) 
于是有下面的命题:对0<ε<1,有
lim t→∞
Nt(ε) 
t =H

1 06 人工智能应用的数学基础(微课版) 
.. 3.7 小 结
本章介绍了马尔可夫链的相关知识,包括基本概念、隐马尔可夫模型、C-K方程、马尔可
夫链的状态分类、极限定理及平稳分布、转移概率与柯尔莫哥洛夫微分方程以及马尔可夫链
的应用。
.. 3.8 习 题
1.设有独立重复试验序列{Xn ,n≥1}。以Xn =1记第n 次试验时事件A 发生,且
P{Xn =1}=θ;以Xn =0记第n 次试验时事件A 不发生,且P{Xn =0}=λ=1-θ。求k 步
转移概率矩阵。
2.若顾客的购买是无记忆的。现在市场上供应A、B、C3个不同厂家生产的50g袋装
味精。用Xn =1,Xn =2,Xn =3分别表示事件顾客第n 次购买A 厂、B厂、C厂的味精,则
{Xn}是一个马尔可夫链。已知顾客第一次购买A 厂、B厂、C 厂味精的概率依次为0.4, 
0.4,0.2,又已知一般顾客购买的倾向表如下: 
0.8 0.1 0.1 
0.5 0.1 0.4 
0.5 0.3 0.2 
é
.
êêêê 
ù
.
úúúú 
(1)求顾客第二次购买A 厂、B厂、C厂味精的概率。
(2)求顾客3次购买后的倾向表。
(3)长时间的购买活动后,A、B、C三厂的市场占有率如何? 
3.天气预报问题。设明天是否有雨仅与今天的天气有关,而与过去的天气无关。又设
今天下雨而明天下雨的概率为α,而今天无雨明天有雨的概率为β。规定有雨天气为状态
0,无雨天气为状态1,因此本问题是有两个状态的马尔可夫链。设α=0.4,β=0.7。求今天
有雨且第四天仍有雨的概率。
4.设马尔可夫链的状态空间为I={0,1,2},一步转移概率矩阵为
P= 
0.1 0.4 0.5 
0.3 0.4 0.3 
0.5 0.3 0.2 
é
.
êêêê ù
.
úúúú 
求其相应的极限分布。
5.设马尔可夫链的转移概率矩阵为
P= 
12
0 12
0 
0 12
0 12 
12
0 12
0 
0 12
0 12 
é
.
êêêêêêêêêêê 
ù
.
úúúúúúúúúúú

第3章 马尔可夫链1 07 
讨论此马尔可夫链的遍历性。
6.设马尔可夫链{Xn ,n≥1}的转移概率矩阵为
P= 
14
34
0 
34
0 14 
0 14
34 
é
.
êêêêêêêê 
ù
.
úúúúúúúú 
求其平稳分布。
7.在计算机系统中,每一轮循环有误差的概率取决于前一轮循环是否有误差。以0表
示有误差状态,1表示无误差状态。设转移概率矩阵为
P= 0.25 0.75 
0.5 0.5 
é
. êê
ù
. úú 
讨论相应的齐次马尔可夫链的遍历性,并求其平稳(极限)分布。