第四章 离散时间 Markov 链
4.1 定义和一些例子
在一些物理学、生物学、经济学等许多学科中，都有如下行为的系统：该系统是与时间有关的一个系统，如果已知系统在现在的状态,则此系统的过去所处的状态与将来所处状态是 （条件） 独立的，这个特性称为Markov 性。本节我们考虑状态空间为离散的，用表示状态，参数集S jiii,,,
10
或L T为离散的（一般表示时间），。 {}L,2,1,0=T
定义 4.1.1：一个离散时间随机过程 { }0,≥nX
n
称为 Markov 链，若对任意状态序列 {} Sjiiii
n
,,,,
110
L
)(),,,(
11111001
iXjXPiXiXiXiXjXP
nnnnnn
========
++
L。
记)(
1
1,
iXjXPP
nn
nn
ij
===
+
+
，Sji ∈,称为在时的一步转移概率（one step
transition probabilities）。固定，转移概率，可以看成某个矩阵的第i行
n
n
1,+nn
ij
P j列元素，把该矩阵记为，即)(nP ( )
Sji
nn
ij
PnP
∈
+
=
,
1,
)(，它有可能是无穷维的。称为在时刻的一步转移概率矩阵。一般来说转移概率依赖于时刻，此时称该Markov链是非齐次的 (inhomogenous)。但是，一个重要的情形是粒子在时刻s处于状态i，在时刻处于状态
)(nP
n
1,+nn
ij
P n
ts + j与在初始时刻0=s处于状态i，在时刻t
处于状态j这两个过程是一样的。
定义 4.1.2：Markov链{称为齐次 Markov链或称为有平稳转移概率的
Markov链若它一步转移概率，
}0,≥nX
n
1,+nn
ij
P Tn∈ Sji ∈,不依赖于n。
对于齐次Markov链，由于一步转移概率不依赖于，因此记
1,+nn
ij
P n
)(
1
1,
iXjXPPP
nn
nn
ijij
====
+
+
，此时一步转移概率矩阵为( )
Sji
ij
PP
∈
=
,
。以下不
1
特别指明，所讨论的均为齐次 Markov 链。以SiiXPp
i
∈== ),(
0
记Markov链的初始分布（）。 {0,≥nX
n
} 1=
∑
∈Si
i
p
定理 4.1.1：1).，1,0 =≥
∑
∈Sj
ijij
PP Sji ∈?,
2),
nn
iiiiiiinn
PPPpiXiXiXP
121100
),,(
1100
==== LL
例4.1.1：直线上的随机游动。假设从原点开始，粒子以p的概率向前迈一步，
以q的概率向后迈一步，以r的概率在原地不动，1=++ rqp。表示时刻的位置，则为齐次Markov链。状态空间
n
X n
n
X { }LL,2,1,0,1,2,=S，一步转移概率
1,0,,,
1,1,
>?====
+
jiPqPrPpP
ijiiiiii
，Sji ∈?,。这是无限制随机游动。
4.2 步转移概率矩阵 n
设状态空间为，一步转移概率为S P，初始分布为SiiXPp
i
∈== ),(
0
的齐次
Markov链{}，令0,≥nX
n
( ) ( ) 2,
0
)(
≥======
+
niXjXPiXjXPP
nmmn
n
ij
，表示经过个时刻，链从状态i转移到状态n j的概率，称为步转移概率。令
，定义如下矩阵
n
≠
=
=
ji
ji
P
ij
若若
,0
,1
)0(
Sji ∈,( )
Sji
ij
PP
∈
=
,
)0()0(
，( )
Sji
ij
PPP
∈
==
,
)1(
，
，2≥n ( )
Sji
n
ij
n
PP
∈
=
,
)()(
（n步转移概率矩阵）。
定理 4.2.1：1),( ) SjPpjXP
si
n
ijin
∈?==
∑
∈
,
)(
2),(Chapman-Kolmogorov relation)
∑
∈
+
=
Sk
n
kj
m
ik
mn
ij
PPP
)()()(
，Sji ∈,
2
考虑矩阵乘法，上式可写成
)()()( mnmn
PPP?=
+
因此有
1,
)(
≥= nPP
nn
例4.2.1：考虑两个状态的Markov链{ }0,≥nX
n
，一步转移概率为
=
qq
pp
P
1
1
1
0
10
则
+
+
+
==
qq
pp
qp
qp
pq
pq
qp
PP
n
nn
)1(1
)(
4.3 状态空间的分解
定义 4.3.1：称状态i可到达（accessible）j，记为ji →，若存在使得；
若
0≥n 0
)(
>
n
ij
P
ijji →→,，则称ji,是相通的（communicate），记为ji?。
相通关系是一个等价关系，即满足,
1) 自反性：； ii?
2) 对称性：ji?，则ij?；
3) 传递性：，则kjji,ki?。
两个状态若是相通的就称他们是处于同一类。Markov 链的所有状态按相通 关 系分割成不同的等价类，两个等价类要么不相交，要么重合。
定义 4.3.2：一个状态集合C称为是闭集，若0=
ij
P对CjCi∈?,。一旦粒子进入某个闭集，就永远停留在此闭集中。一个Markov链称为不可约（irreducible）
若除整个状态空间外无别的闭集。
3
定理 4.3.1：Mrakov 链不可约?所有状态之间是相通的。
证明：?显然。（反证法）若存在两状态ji,不是相通的，不妨设ji →
/
。令
{i → }kkC =，则首先；其次对Cj? 0,,=∈?
kl
PClCk。因此为一个闭集，
而这与Mrakov链不可约矛盾。
C
例4.3.1：若Markov链一步转移概率矩阵为
=
1
2/12/1
1
2/12/1
4/34/1
5
4
3
2
1
54321
P
{}2,1,{在相通意义下为两个等价类，此链是可约的。 }5,4,3
定义 4.3.3：记{ }0,1gcd)(
)(
>≥=
n
ii
Pnnid，这里表示最大公因子（greatest
common divisor），若，称为周期的（periodic），且周期为；否则称为非周期的（aperiodic）。
gcd
1)( >id i )(id
由定义立即可知，若n不是的倍数，则。 )(id 0
)(
=
n
ii
P
定理 4.3.2：若 ji?,则 。 )()( jdid =
证明：由于ji?，故使得。于是。若有s使得
，则。由于
nm,? 0,0
)()(
>>
n
ji
m
ij
PP 0
)(
>
+mn
jj
P
0
)(
>
s
ii
P 0
)(
>
++ smn
jj
P mnjd +)(，smnjd ++)(，因此sjd )(，进而
)()( idjd。同理有)()( jdid，故)()( jdid =。
定理 4.3.3：存在正整数 使得对所有的 恒有 。 N Nn> 0
))((
>
ind
ii
P
证明依赖于一个数论知识：若个正整数互素，则存在正整数使得对所有的都存在非负整数使得。对状态i，若
k
k
nnn L,,
21
N
Nn>
k
aaa L,,
21 ∑
=
=
k
i
ii
nan
1
4
0,
)()()(
21
>
k
n
ii
n
ii
n
ii
PPP L，则
)(
,
)(
,
)(
21
id
n
id
n
id
n
k
L互素，故存在正整数使得对所有的都存在非负整数使得，且。
N
Nn>
k
aaa L,,
21 ∑
=
=
k
i
ii
naind
1
)( 0
))((
>
ind
ii
P
定理4.3.3的一个直接推论是：若,存在正整数 使得对所有的恒有 。
0
)(
>
m
ji
P N
Nn> 0
))((
>
+ indm
ji
P
定理 4.3.4：设 P 为不可约,非周期,有限状态 Markov 链的一步转移概率矩阵，
则存在正整数 使得当 时,步转移概率矩阵N Nn> n
)(n
P 的所有元素都大于 0。
4.4 常返与瞬过
在事件{上引入一个重要的概率，表示从 出发在 步转移时首次到达
}iX =
0
)(n
ij
f i n
j 的概率。用式子表示即是
)1,1,,(,0
0
)()0(
iXnkjXjXPff
kn
n
ijij
=?=≠=== L。
令，它表示从i出发最终转入到状态
∑
∞
=
=
1
)(
n
n
ijij
ff j的概率。再引入一重要随机变量{}1,,:min
0
≥=== nXiXn
nij
jτ，因此( )iXnPf
ij
n
ij
===
0
)(
τ。
定理 4.4.1,SjiPfP
n
l
ln
jj
l
ij
n
ij
∈?=
∑
=
,,
1
)()()(
证,
5
∑
∑
∑
∑
∑
=
=
=
=
=
=
=====
=≠≠=====
======
====
===
n
l
ln
jj
l
ij
n
l
lnij
n
l
llnij
n
l
ijnij
n
l
nij
n
n
ij
Pf
jXjXPiXlP
jXjXjXiXjXPiXlP
iXljXPiXlP
iXjXlP
iXjXPP
1
)()(
1
0
1
1100
1
00
1
0
0
)(
)()(
),,,()(
),()(
),(
)(
τ
τ
ττ
τ
L
推论 4.4.1：0>?→
ij
fji。
定义 4.4.1,若，称状态i为常返的 (recurrent)；若1=
ii
f 1<
ii
f，则称状态i为瞬过的 (transient)。
如果状态 i为常返的,系统无穷次返回状态 的概率为 1； 如果状态 i为瞬过，
系统无穷次返回状态 i的概率为 0。
i
定理 4.4.2：状态 i为常返的 ；状态 为瞬过。 ∞=?
∑
∞
=1
)(
n
n
ii
P i ∞<?
∑
∞
=1
)(
n
n
ii
P
证：分别引入序列{ }0,
)(
≥nP
n
ij
和{ }1,
)(
≥nf
n
ij
的形式上的母函数
∑∑
∞
=
∞
=
+==
1
)(
0
)(
)(
n
nn
ijij
n
nn
ijij
sPsPsP δ,
∑
∞
=
=
1
)(
)(
n
nn
ijij
sfsF
于是
6
)()(
)(
10
)()(
1
)()(
1
)()(
11
)()(
sPsF
sPsf
sPsf
sPf
sPfsP
jjijij
l
n
n
n
jj
ll
ijij
l
ln
ln
ln
jj
ll
ijij
l
n
ln
ln
jj
l
ijij
n
n
n
l
ln
jj
l
ijijij
+=
+=
+=
+=
+=
∑∑
∑∑
∑∑
∑∑
∞
=
∞
=
∞
=
∞
=
∞
=
∞
=
∞
==
δ
δ
δ
δ
δ
令，则ji =
)(1
1
)(
sF
sP
ii
ii
=。故
iiii
s
ii
s
n
n
ii
fsF
sPP
=
==
→
→
∞
=
∑
1
1
)(lim1
1
)(lim
1
1
0
)(
。
推论 4.4.2：若状态 j 是非常返即瞬过的，则对任意 Si∈,,此时
。
∞<
∑
∞
=0
)(
n
n
ij
P
0lim
)(
=
∞→
n
ij
n
P
对于常返态i，进一步来研究它的平均常返时间：。
∑
∞
=
==
1
)(
n
n
iiiii
fnEτμ
定义 4.4.2：若∞<
i
μ，则称为正常返 (positive recurrent)；若i ∞=
i
μ则称i为零常返 (null recurrent)；一个正常返非周期状态称为遍历态 (ergodic state)。
定理 4.4.3：若 i为常返，则 i为零常返 。 0lim
)(
=?
∞→
n
ii
n
P
推论 4.4.3：若状态 j 是零常返的，则对任意 Si∈,。 0lim
)(
=
∞→
n
ij
n
P
证明：由于，于是，先固定，令
∑∑∑
+==
=
+≤=
n
ml
l
ij
m
l
ln
jj
l
ij
n
l
ln
jj
l
ij
n
ij
fPfPfP
1
)(
1
)()(
1
)()()(
m ∞→n
有。由于0
1
)()(
→
∑
=
m
l
ln
jj
l
ij
Pf
∑
∞
=
=
1
)(
n
n
ijij
ff 1≤，故再令∞→m时，，故
。
0
1
)(
→
∑
∞
+=ml
l
ij
f
0lim
)(
=
∞→
n
ij
n
P
7
定理 4.4.4：若 遍历态，则i
i
n
ii
n
P
μ
1
lim
)(
=
∞→；若 是周期为 的正常返态，则i d
i
nd
ii
n
d
P
μ
=
∞→
)(
lim 。
证明：由于
)(1
1
)(
sF
sP
ii
ii
=，故
)(1
1
)()1(
sF
s
sPs
ii
ii
=?，两边令，则左边
→1s
)(0
)(
0
0
)(
1
0
0
)(
1
0
0
)(
11
lim
1
limlimlim
limlimlim)()1(lim
n
ii
n
k
n
n
ii
k
k
n
n
k
n
nn
ii
sk
k
n
n
k
n
nn
ii
ks
n
n
n
nn
ii
s
ii
s
P
k
P
s
sP
s
sP
s
sP
sPs
∞→
=
∞→
=
=
→∞→
=
=
∞→→
∞
=
∞
=
→→
=
+
==
==?
∑
∑
∑
∑
∑
∑
∑
右边
iii
s
ii
s
sFsF
s
μ
1
)(
1
lim
)(1
1
lim
11
=
′
=
→→
，因此
i
n
ii
n
P
μ
1
lim
)(
=
∞→
。
定理 4.4.5：若状态 是遍历的，则对任意j Si∈,
j
ij
n
ij
n
f
P
μ
=
∞→
)(
lim 。
定理 4.4.6：若 j 常返且 ij →,则 1=
ij
f。
证明：反证，若，则从出发经过有限步，不能到达1<
ij
f i j的概率为，
由于
01 >?
ij
f
ij →，故从j出发，将以某个正概率经过有限步不能回到j，故。矛盾！
1<
jj
f
综上，可得,
i瞬过 ； ∞<?
∑
∞
=1
)(
n
n
ii
P
i零常返 且 ； ∞=?
∑
∞
=1
)(
n
n
ii
P 0lim
)(
=
∞→
n
ii
n
P
i正常返 且 ； ∞=?
∑
∞
=1
)(
n
n
ii
P 0lim
)(
_____
>
∞→
n
ii
n
P
8
i遍历 且∞=?
∑
∞
=1
)(
n
n
ii
P 0
1
lim
)(
>=
∞→
i
n
ii
n
P
μ
。
定理 4.4.7：若 ji?,则 它们或同为瞬过或同为常返； 当同为常返时或同为零常返或同为正常返。
例4.4.1：Markov链，状态空间为
n
X { }4,3,2,1=S，一步转移矩阵为
=
0001
1000
0100
4
1
4
1
4
1
4
1
P
非周期不可约Markov链，由于1状态4,0,
4
1
)(
11
)4(
11
)3(
11
)2(
11
)1(
11
>===== nfffff
n
，
故1状态常返且
2
5
1
=μ故为正常返，1状态为遍历，因而所有状态是遍历的。
下面给出不可约链是否常返的判别方法。
定理 4.4.8：设不可约 Markov 链,状态空间为
n
X { }L2,1,0=S,一步转移矩阵为 P 。则 常返
n
X?下列方程组没有非零的有界解,
L,2,1,
1
==
∑
∞
=
izPz
j
jiji
4.5 平稳分布与极限分布
定义 4.5.1：设为Markov链，状态空间为，一步转移概率矩阵为
n
X S P，若实数{}Si
i
∈,π满足,
1) Si
i
∈≥,0π且； 1=
∑
∈Si
i
π
2),即SiP
Sj
jiji
∈=
∑
∈
,ππ ππ =P，这里( )
S
ππππ L
21
,=
则称{}Si
i
∈,π为Markov链的平稳分布。
n
X
下面考察非周期不可约Markov链，由上一节推论4.4.2，推论4.4.3及定理4.4.5，
4.4.6知,
9
Si
j
j
P
j
n
ij
n
∈?
>
=
∞→
为正常返，
为零常返或瞬过
0
1
,0
lim
)(
μ
。
定义 4.5.2：若步转移概率极限n
)(n
ij
P )(0
1
lim
)(
iP
j
n
ij
n
不依赖≥=
∞→
μ
为Markov链的极限分布。
n
X
定理 4.5.1：非周期不可约 Markov 链是正常返链的充要条件是它存在平稳分布，
且此时平稳分布就是极限分布。
证明：注意：由上一节定理4.4.7，非周期不可约Markov链的状态要么全是瞬过，
要么全是零常返，要么全是正常返，极限分布
j
n
ij
n
P
μ
1
lim
)(
=
∞→
存在。
充分性。若有平稳分布)(? { }Si
i
∈,π，则
∑
∈
=
Si
n
ijij
P
)(
ππ。令，由于∞→n
Si
i
∈≥,0π且，极限与求和可交换，故1=
∑
∈Si
i
π
j
Si
j
i
Si
n
iji
n
j
P
μμ
πππ
11
lim
)(
===
∑∑
∈∈
∞→
。由于1=
∑
∈Si
i
π，故至少有一个0
1
>
k
μ
，故状态k是正常返，这样所有状态都为正常返。
必要性。设链是正常返的，于是)(? 0
1
lim
)(
>=
∞→
j
n
ij
n
P
μ
。不妨设状态为无穷。
由C—K关系，，两端令
S
∑∑
=
∞
=
≥=
N
k
kj
n
ik
k
kj
n
ik
n
ij
PPPPP
0
)1(
0
)1()(
∞→n，有
∑
=
≥
N
k
kj
kj
P
0
11
μμ
,
再令，有∞→N jP
k
kj
kj
≥
∑
∞
=
,
11
0
μμ
。必对任意成立等号，若不然，则由于j
1
1
0
≤
∑
∞
=j
j
μ
，保证以下求和可以交换次序。
∑∑∑∑∑∑
∞
=
∞
=
∞
=
∞
=
∞
=
∞
=
==>
000000
1111
k
k
kj
kj
k
jk
kj
k
j
j
PP
μμμμ
，矛盾！这样jP
k
kj
kj
=
∑
∞
=
,
11
0
μμ
，故
∑
∞
=
=
0
)(
11
k
n
kj
kj
P
μμ
，令有∞→n
∑
∞
=
=
0
111
k
jkj
μμμ
，故1
1
0
=
∑
∞
=k
k
μ
，
∈Sj
j
,
1
μ
为平
10
稳分布。
推论 4.5.1：非周期不可约正常返 Markov 链的平稳分布是唯一的。
例4.5.1：（带一个弹性壁的随机游动）设Markov链状态空间为，
一步转移矩阵为
n
X {}L,2,1,0=S
P，其中L2,1,0,
1,
==
+
ipP
ii
，L,2,1,
1,
==
iqP
ii
，，
。
qP =
00
0,1 >=+ pqqp
此链为非周期不可约Markov链。先决定何时常返。由上一节定理4.4.8，考察
L3,2,,
1121
=+==
+?
ipzqzzpzz
iii
或
L3,2),(,
11112
=?=?=?
+
izz
p
q
zzz
p
q
zz
iiii
由此L,2,1,
11
=
=?
+
iz
p
q
zz
i
ii
，故L,2,1,
1
1
1
=
= iz
p
q
p
q
z
i
i
若qp >，{为有界非零解，此时链非常返；若}
i
z qp ≤，{ }
i
z无界，即方程组无有界非零的解，此时链常返。
进一步判断是正常返还是零常返。考察何时具有平稳分布。
L2,1,,
11100
=+=+=
+?
jqpqq
jjj
ππππππ
当qp =时，不存在平稳分布，此时链为零常返；当qp <时，平稳分布为
L2,1,0,1 =
= j
q
p
q
p
j
j
π，此时链为正常返。
定理 4.5.2：有限非周期不可约 Markov 链必是正常返链。
4.6 分支过程（branching process）
考虑某个群体，其一个个体繁衍下一代的子女数是随机的，可能是等，
有一定的概率分布，若用表示一个个体繁衍下一代的子女数，则是随机变量，
L2,1,0
J J
11
设分布为。假定各代个体的繁衍能力相同且是独立的繁衍下一代，表示第0代祖先的数目，一般假定为1，以表示第代中个体数目，称为分支过程。以表示第代中第i个个体繁衍下一代数目，
独立同分布，共同分布为的分布，则
L2,1,0),( === kkJPp
k
0
X
n
X n
0,≥nX
n i
J n
i
J
J
∑
=
+
=+++=
n
n
X
i
iXn
JJJJX
1
211
L
这样若给定则的分布就确定了，与无关，故为Markov
链，状态空间
n
X
1+n
X
11
,
n
XX L 0,≥nX
n
{ }L2,1,0=S，一步转移概率
() 0,
1
1
>?
=====
∑
=
+
ijJPiXjXPP
i
k
knnij
，1
00
=P。
令1,)(
0
≤=
∑
∞
=
ssps
l
l
l
φ为的母函数，定义J ss =)(
0
φ，)()(
1
ss φφ =，
()1,)()(
1
≥=
nss
nn
φφφ，显然( ) ( ))()()( sss
nmmnmn
φφφφφ ==
+
。
定理 4.6.1：)(s
n
φ 为 的母函数。
n
X
证明：归纳法。设)(s
n
φ为的母函数，考虑的母函数记为。
n
X
1+n
X )(
1
sg
n+
[]
() 1)()(
)()()(
)()()(
)()()()(
),()()(
1
010
0010
00 100
1
00
1
0
11
1
≤==
====
=====
=======
=====
+
∞
==
∞
=
∑
∞
=
∞
==
∞
=
∞
=
∞
==
∞
=
∞
=
+
∞
=
∞
=
+
∞
=
++
∑∏∑
∑∑∑∑
∑∑ ∑∑∑
∑∑∑
=
sss
siXPEsiXP
EsiXPsjJPiXP
siXPjJPsiXPiXjXP
siXjXPsjXPsg
nn
i
i
n
i
k
J
i
n
J
i
n
j
j
i
k
k
i
n
ji
j
n
i
k
k
ji
j
nnn
ji
j
nn
j
j
nn
k
i
k
k
φφφ
φ
对于分支过程，我们主要关心的是，种群灭绝概率，以表示，则 q
12
{} {} )0(lim)0(lim0lim0
11
n
n
n
n
n
l
l
n
n
n
XPXPXPq φ
∞→∞→
=
∞→
∞
=
===
==
==
UU
（注意{}{ }00
1
=?=
+ll
XX）
1
0
=p，种群不能发端；种群永不消亡。故以下假定。这时
，故
0
0
=p 10
0
<< p
0)(
1
1
>=′
∑
∞
=
k
k
k
kspsφ )(sφ在上单调非降。故 ]1,0[
1)0()0()0(0
10
≤≤≤≤=<
n
p φφφ L
序列)0(
n
φ单调非降有上界必有极限，故)0(lim0
0 n
n
qp φ
∞→
=≤<。另一方面
()0()0(
1 nn
φφφ =
+
，令有∞→n )(qq φ=，故为方程q ss =)(φ的一个正根。近一步有
定理 4.6.2：对于分支过程,设
n
X 10
0
<< p,,则
∑
∞
=
==
1k
k
kpEJμ
1) 灭绝概率 是方程q ss =)(φ 的最小正根；
2) 11 =?≤ qμ 。
证明：1)设x为方程ss =)(φ的任意正根，由于)(sφ在上单调非降，故]1,0[
xx =≤ )()0( φφ，由归纳法立得x
n
≤)0(φ，令∞→n有xq
n
n
≤=
∞→
)0(limφ。
2) 令10,
)(
)(
1
10
≤<+==
∑
∞
=
ssp
s
p
s
s
sf
k
k
k
φ
，则1)1(,)0( =∞= ff，
1)1(,)0(?=′?∞=′ μff，，故0)( >′′ sf )(sf ′严格增。当1≤μ时，在，
恒为负，此时严格减，由
10 << s )(sf ′
)(sf 1)1( =f，在(0,1)中，从而方程1)( >sf ss =)(φ的解不能在(0,1)内，故。若1=q 1>μ，由连续函数介值定理必有使得
。在，单调降，在，单调增。由，，
于是有使得，即
10 << x
0)( =′ xf ),0( x )(sf )1,(x )(sf 1)1( =f 1)( <xf
),0(
0
xs ∈ 1)(
0
=sf
00
)( ss =φ，故10
0
<≤< sq。
13
4.1 定义和一些例子
在一些物理学、生物学、经济学等许多学科中，都有如下行为的系统：该系统是与时间有关的一个系统，如果已知系统在现在的状态,则此系统的过去所处的状态与将来所处状态是 （条件） 独立的，这个特性称为Markov 性。本节我们考虑状态空间为离散的，用表示状态，参数集S jiii,,,
10
或L T为离散的（一般表示时间），。 {}L,2,1,0=T
定义 4.1.1：一个离散时间随机过程 { }0,≥nX
n
称为 Markov 链，若对任意状态序列 {} Sjiiii
n
,,,,
110
L
)(),,,(
11111001
iXjXPiXiXiXiXjXP
nnnnnn
========
++
L。
记)(
1
1,
iXjXPP
nn
nn
ij
===
+
+
，Sji ∈,称为在时的一步转移概率（one step
transition probabilities）。固定，转移概率，可以看成某个矩阵的第i行
n
n
1,+nn
ij
P j列元素，把该矩阵记为，即)(nP ( )
Sji
nn
ij
PnP
∈
+
=
,
1,
)(，它有可能是无穷维的。称为在时刻的一步转移概率矩阵。一般来说转移概率依赖于时刻，此时称该Markov链是非齐次的 (inhomogenous)。但是，一个重要的情形是粒子在时刻s处于状态i，在时刻处于状态
)(nP
n
1,+nn
ij
P n
ts + j与在初始时刻0=s处于状态i，在时刻t
处于状态j这两个过程是一样的。
定义 4.1.2：Markov链{称为齐次 Markov链或称为有平稳转移概率的
Markov链若它一步转移概率，
}0,≥nX
n
1,+nn
ij
P Tn∈ Sji ∈,不依赖于n。
对于齐次Markov链，由于一步转移概率不依赖于，因此记
1,+nn
ij
P n
)(
1
1,
iXjXPPP
nn
nn
ijij
====
+
+
，此时一步转移概率矩阵为( )
Sji
ij
PP
∈
=
,
。以下不
1
特别指明，所讨论的均为齐次 Markov 链。以SiiXPp
i
∈== ),(
0
记Markov链的初始分布（）。 {0,≥nX
n
} 1=
∑
∈Si
i
p
定理 4.1.1：1).，1,0 =≥
∑
∈Sj
ijij
PP Sji ∈?,
2),
nn
iiiiiiinn
PPPpiXiXiXP
121100
),,(
1100
==== LL
例4.1.1：直线上的随机游动。假设从原点开始，粒子以p的概率向前迈一步，
以q的概率向后迈一步，以r的概率在原地不动，1=++ rqp。表示时刻的位置，则为齐次Markov链。状态空间
n
X n
n
X { }LL,2,1,0,1,2,=S，一步转移概率
1,0,,,
1,1,
>?====
+
jiPqPrPpP
ijiiiiii
，Sji ∈?,。这是无限制随机游动。
4.2 步转移概率矩阵 n
设状态空间为，一步转移概率为S P，初始分布为SiiXPp
i
∈== ),(
0
的齐次
Markov链{}，令0,≥nX
n
( ) ( ) 2,
0
)(
≥======
+
niXjXPiXjXPP
nmmn
n
ij
，表示经过个时刻，链从状态i转移到状态n j的概率，称为步转移概率。令
，定义如下矩阵
n
≠
=
=
ji
ji
P
ij
若若
,0
,1
)0(
Sji ∈,( )
Sji
ij
PP
∈
=
,
)0()0(
，( )
Sji
ij
PPP
∈
==
,
)1(
，
，2≥n ( )
Sji
n
ij
n
PP
∈
=
,
)()(
（n步转移概率矩阵）。
定理 4.2.1：1),( ) SjPpjXP
si
n
ijin
∈?==
∑
∈
,
)(
2),(Chapman-Kolmogorov relation)
∑
∈
+
=
Sk
n
kj
m
ik
mn
ij
PPP
)()()(
，Sji ∈,
2
考虑矩阵乘法，上式可写成
)()()( mnmn
PPP?=
+
因此有
1,
)(
≥= nPP
nn
例4.2.1：考虑两个状态的Markov链{ }0,≥nX
n
，一步转移概率为
=
pp
P
1
1
1
0
10
则
+
+
+
==
pp
qp
qp
pq
pq
qp
PP
n
nn
)1(1
)(
4.3 状态空间的分解
定义 4.3.1：称状态i可到达（accessible）j，记为ji →，若存在使得；
若
0≥n 0
)(
>
n
ij
P
ijji →→,，则称ji,是相通的（communicate），记为ji?。
相通关系是一个等价关系，即满足,
1) 自反性：； ii?
2) 对称性：ji?，则ij?；
3) 传递性：，则kjji,ki?。
两个状态若是相通的就称他们是处于同一类。Markov 链的所有状态按相通 关 系分割成不同的等价类，两个等价类要么不相交，要么重合。
定义 4.3.2：一个状态集合C称为是闭集，若0=
ij
P对CjCi∈?,。一旦粒子进入某个闭集，就永远停留在此闭集中。一个Markov链称为不可约（irreducible）
若除整个状态空间外无别的闭集。
3
定理 4.3.1：Mrakov 链不可约?所有状态之间是相通的。
证明：?显然。（反证法）若存在两状态ji,不是相通的，不妨设ji →
/
。令
{i → }kkC =，则首先；其次对Cj? 0,,=∈?
kl
PClCk。因此为一个闭集，
而这与Mrakov链不可约矛盾。
C
例4.3.1：若Markov链一步转移概率矩阵为
=
1
2/12/1
1
2/12/1
4/34/1
5
4
3
2
1
54321
P
{}2,1,{在相通意义下为两个等价类，此链是可约的。 }5,4,3
定义 4.3.3：记{ }0,1gcd)(
)(
>≥=
n
ii
Pnnid，这里表示最大公因子（greatest
common divisor），若，称为周期的（periodic），且周期为；否则称为非周期的（aperiodic）。
gcd
1)( >id i )(id
由定义立即可知，若n不是的倍数，则。 )(id 0
)(
=
n
ii
P
定理 4.3.2：若 ji?,则 。 )()( jdid =
证明：由于ji?，故使得。于是。若有s使得
，则。由于
nm,? 0,0
)()(
>>
n
ji
m
ij
PP 0
)(
>
+mn
jj
P
0
)(
>
s
ii
P 0
)(
>
++ smn
jj
P mnjd +)(，smnjd ++)(，因此sjd )(，进而
)()( idjd。同理有)()( jdid，故)()( jdid =。
定理 4.3.3：存在正整数 使得对所有的 恒有 。 N Nn> 0
))((
>
ind
ii
P
证明依赖于一个数论知识：若个正整数互素，则存在正整数使得对所有的都存在非负整数使得。对状态i，若
k
k
nnn L,,
21
N
Nn>
k
aaa L,,
21 ∑
=
=
k
i
ii
nan
1
4
0,
)()()(
21
>
k
n
ii
n
ii
n
ii
PPP L，则
)(
,
)(
,
)(
21
id
n
id
n
id
n
k
L互素，故存在正整数使得对所有的都存在非负整数使得，且。
N
Nn>
k
aaa L,,
21 ∑
=
=
k
i
ii
naind
1
)( 0
))((
>
ind
ii
P
定理4.3.3的一个直接推论是：若,存在正整数 使得对所有的恒有 。
0
)(
>
m
ji
P N
Nn> 0
))((
>
+ indm
ji
P
定理 4.3.4：设 P 为不可约,非周期,有限状态 Markov 链的一步转移概率矩阵，
则存在正整数 使得当 时,步转移概率矩阵N Nn> n
)(n
P 的所有元素都大于 0。
4.4 常返与瞬过
在事件{上引入一个重要的概率，表示从 出发在 步转移时首次到达
}iX =
0
)(n
ij
f i n
j 的概率。用式子表示即是
)1,1,,(,0
0
)()0(
iXnkjXjXPff
kn
n
ijij
=?=≠=== L。
令，它表示从i出发最终转入到状态
∑
∞
=
=
1
)(
n
n
ijij
ff j的概率。再引入一重要随机变量{}1,,:min
0
≥=== nXiXn
nij
jτ，因此( )iXnPf
ij
n
ij
===
0
)(
τ。
定理 4.4.1,SjiPfP
n
l
ln
jj
l
ij
n
ij
∈?=
∑
=
,,
1
)()()(
证,
5
∑
∑
∑
∑
∑
=
=
=
=
=
=
=====
=≠≠=====
======
====
===
n
l
ln
jj
l
ij
n
l
lnij
n
l
llnij
n
l
ijnij
n
l
nij
n
n
ij
Pf
jXjXPiXlP
jXjXjXiXjXPiXlP
iXljXPiXlP
iXjXlP
iXjXPP
1
)()(
1
0
1
1100
1
00
1
0
0
)(
)()(
),,,()(
),()(
),(
)(
τ
τ
ττ
τ
L
推论 4.4.1：0>?→
ij
fji。
定义 4.4.1,若，称状态i为常返的 (recurrent)；若1=
ii
f 1<
ii
f，则称状态i为瞬过的 (transient)。
如果状态 i为常返的,系统无穷次返回状态 的概率为 1； 如果状态 i为瞬过，
系统无穷次返回状态 i的概率为 0。
i
定理 4.4.2：状态 i为常返的 ；状态 为瞬过。 ∞=?
∑
∞
=1
)(
n
n
ii
P i ∞<?
∑
∞
=1
)(
n
n
ii
P
证：分别引入序列{ }0,
)(
≥nP
n
ij
和{ }1,
)(
≥nf
n
ij
的形式上的母函数
∑∑
∞
=
∞
=
+==
1
)(
0
)(
)(
n
nn
ijij
n
nn
ijij
sPsPsP δ,
∑
∞
=
=
1
)(
)(
n
nn
ijij
sfsF
于是
6
)()(
)(
10
)()(
1
)()(
1
)()(
11
)()(
sPsF
sPsf
sPsf
sPf
sPfsP
jjijij
l
n
n
n
jj
ll
ijij
l
ln
ln
ln
jj
ll
ijij
l
n
ln
ln
jj
l
ijij
n
n
n
l
ln
jj
l
ijijij
+=
+=
+=
+=
+=
∑∑
∑∑
∑∑
∑∑
∞
=
∞
=
∞
=
∞
=
∞
=
∞
=
∞
==
δ
δ
δ
δ
δ
令，则ji =
)(1
1
)(
sF
sP
ii
ii
=。故
iiii
s
ii
s
n
n
ii
fsF
sPP
=
==
→
→
∞
=
∑
1
1
)(lim1
1
)(lim
1
1
0
)(
。
推论 4.4.2：若状态 j 是非常返即瞬过的，则对任意 Si∈,,此时
。
∞<
∑
∞
=0
)(
n
n
ij
P
0lim
)(
=
∞→
n
ij
n
P
对于常返态i，进一步来研究它的平均常返时间：。
∑
∞
=
==
1
)(
n
n
iiiii
fnEτμ
定义 4.4.2：若∞<
i
μ，则称为正常返 (positive recurrent)；若i ∞=
i
μ则称i为零常返 (null recurrent)；一个正常返非周期状态称为遍历态 (ergodic state)。
定理 4.4.3：若 i为常返，则 i为零常返 。 0lim
)(
=?
∞→
n
ii
n
P
推论 4.4.3：若状态 j 是零常返的，则对任意 Si∈,。 0lim
)(
=
∞→
n
ij
n
P
证明：由于，于是，先固定，令
∑∑∑
+==
=
+≤=
n
ml
l
ij
m
l
ln
jj
l
ij
n
l
ln
jj
l
ij
n
ij
fPfPfP
1
)(
1
)()(
1
)()()(
m ∞→n
有。由于0
1
)()(
→
∑
=
m
l
ln
jj
l
ij
Pf
∑
∞
=
=
1
)(
n
n
ijij
ff 1≤，故再令∞→m时，，故
。
0
1
)(
→
∑
∞
+=ml
l
ij
f
0lim
)(
=
∞→
n
ij
n
P
7
定理 4.4.4：若 遍历态，则i
i
n
ii
n
P
μ
1
lim
)(
=
∞→；若 是周期为 的正常返态，则i d
i
nd
ii
n
d
P
μ
=
∞→
)(
lim 。
证明：由于
)(1
1
)(
sF
sP
ii
ii
=，故
)(1
1
)()1(
sF
s
sPs
ii
ii
=?，两边令，则左边
→1s
)(0
)(
0
0
)(
1
0
0
)(
1
0
0
)(
11
lim
1
limlimlim
limlimlim)()1(lim
n
ii
n
k
n
n
ii
k
k
n
n
k
n
nn
ii
sk
k
n
n
k
n
nn
ii
ks
n
n
n
nn
ii
s
ii
s
P
k
P
s
sP
s
sP
s
sP
sPs
∞→
=
∞→
=
=
→∞→
=
=
∞→→
∞
=
∞
=
→→
=
+
==
==?
∑
∑
∑
∑
∑
∑
∑
右边
iii
s
ii
s
sFsF
s
μ
1
)(
1
lim
)(1
1
lim
11
=
′
=
→→
，因此
i
n
ii
n
P
μ
1
lim
)(
=
∞→
。
定理 4.4.5：若状态 是遍历的，则对任意j Si∈,
j
ij
n
ij
n
f
P
μ
=
∞→
)(
lim 。
定理 4.4.6：若 j 常返且 ij →,则 1=
ij
f。
证明：反证，若，则从出发经过有限步，不能到达1<
ij
f i j的概率为，
由于
01 >?
ij
f
ij →，故从j出发，将以某个正概率经过有限步不能回到j，故。矛盾！
1<
jj
f
综上，可得,
i瞬过 ； ∞<?
∑
∞
=1
)(
n
n
ii
P
i零常返 且 ； ∞=?
∑
∞
=1
)(
n
n
ii
P 0lim
)(
=
∞→
n
ii
n
P
i正常返 且 ； ∞=?
∑
∞
=1
)(
n
n
ii
P 0lim
)(
_____
>
∞→
n
ii
n
P
8
i遍历 且∞=?
∑
∞
=1
)(
n
n
ii
P 0
1
lim
)(
>=
∞→
i
n
ii
n
P
μ
。
定理 4.4.7：若 ji?,则 它们或同为瞬过或同为常返； 当同为常返时或同为零常返或同为正常返。
例4.4.1：Markov链，状态空间为
n
X { }4,3,2,1=S，一步转移矩阵为
=
0001
1000
0100
4
1
4
1
4
1
4
1
P
非周期不可约Markov链，由于1状态4,0,
4
1
)(
11
)4(
11
)3(
11
)2(
11
)1(
11
>===== nfffff
n
，
故1状态常返且
2
5
1
=μ故为正常返，1状态为遍历，因而所有状态是遍历的。
下面给出不可约链是否常返的判别方法。
定理 4.4.8：设不可约 Markov 链,状态空间为
n
X { }L2,1,0=S,一步转移矩阵为 P 。则 常返
n
X?下列方程组没有非零的有界解,
L,2,1,
1
==
∑
∞
=
izPz
j
jiji
4.5 平稳分布与极限分布
定义 4.5.1：设为Markov链，状态空间为，一步转移概率矩阵为
n
X S P，若实数{}Si
i
∈,π满足,
1) Si
i
∈≥,0π且； 1=
∑
∈Si
i
π
2),即SiP
Sj
jiji
∈=
∑
∈
,ππ ππ =P，这里( )
S
ππππ L
21
,=
则称{}Si
i
∈,π为Markov链的平稳分布。
n
X
下面考察非周期不可约Markov链，由上一节推论4.4.2，推论4.4.3及定理4.4.5，
4.4.6知,
9
Si
j
j
P
j
n
ij
n
∈?
>
=
∞→
为正常返，
为零常返或瞬过
0
1
,0
lim
)(
μ
。
定义 4.5.2：若步转移概率极限n
)(n
ij
P )(0
1
lim
)(
iP
j
n
ij
n
不依赖≥=
∞→
μ
为Markov链的极限分布。
n
X
定理 4.5.1：非周期不可约 Markov 链是正常返链的充要条件是它存在平稳分布，
且此时平稳分布就是极限分布。
证明：注意：由上一节定理4.4.7，非周期不可约Markov链的状态要么全是瞬过，
要么全是零常返，要么全是正常返，极限分布
j
n
ij
n
P
μ
1
lim
)(
=
∞→
存在。
充分性。若有平稳分布)(? { }Si
i
∈,π，则
∑
∈
=
Si
n
ijij
P
)(
ππ。令，由于∞→n
Si
i
∈≥,0π且，极限与求和可交换，故1=
∑
∈Si
i
π
j
Si
j
i
Si
n
iji
n
j
P
μμ
πππ
11
lim
)(
===
∑∑
∈∈
∞→
。由于1=
∑
∈Si
i
π，故至少有一个0
1
>
k
μ
，故状态k是正常返，这样所有状态都为正常返。
必要性。设链是正常返的，于是)(? 0
1
lim
)(
>=
∞→
j
n
ij
n
P
μ
。不妨设状态为无穷。
由C—K关系，，两端令
S
∑∑
=
∞
=
≥=
N
k
kj
n
ik
k
kj
n
ik
n
ij
PPPPP
0
)1(
0
)1()(
∞→n，有
∑
=
≥
N
k
kj
kj
P
0
11
μμ
,
再令，有∞→N jP
k
kj
kj
≥
∑
∞
=
,
11
0
μμ
。必对任意成立等号，若不然，则由于j
1
1
0
≤
∑
∞
=j
j
μ
，保证以下求和可以交换次序。
∑∑∑∑∑∑
∞
=
∞
=
∞
=
∞
=
∞
=
∞
=
==>
000000
1111
k
k
kj
kj
k
jk
kj
k
j
j
PP
μμμμ
，矛盾！这样jP
k
kj
kj
=
∑
∞
=
,
11
0
μμ
，故
∑
∞
=
=
0
)(
11
k
n
kj
kj
P
μμ
，令有∞→n
∑
∞
=
=
0
111
k
jkj
μμμ
，故1
1
0
=
∑
∞
=k
k
μ
，
∈Sj
j
,
1
μ
为平
10
稳分布。
推论 4.5.1：非周期不可约正常返 Markov 链的平稳分布是唯一的。
例4.5.1：（带一个弹性壁的随机游动）设Markov链状态空间为，
一步转移矩阵为
n
X {}L,2,1,0=S
P，其中L2,1,0,
1,
==
+
ipP
ii
，L,2,1,
1,
==
iqP
ii
，，
。
qP =
00
0,1 >=+ pqqp
此链为非周期不可约Markov链。先决定何时常返。由上一节定理4.4.8，考察
L3,2,,
1121
=+==
+?
ipzqzzpzz
iii
或
L3,2),(,
11112
=?=?=?
+
izz
p
q
zzz
p
q
zz
iiii
由此L,2,1,
11
=
=?
+
iz
p
q
zz
i
ii
，故L,2,1,
1
1
1
=
= iz
p
q
p
q
z
i
i
若qp >，{为有界非零解，此时链非常返；若}
i
z qp ≤，{ }
i
z无界，即方程组无有界非零的解，此时链常返。
进一步判断是正常返还是零常返。考察何时具有平稳分布。
L2,1,,
11100
=+=+=
+?
jqpqq
jjj
ππππππ
当qp =时，不存在平稳分布，此时链为零常返；当qp <时，平稳分布为
L2,1,0,1 =
= j
q
p
q
p
j
j
π，此时链为正常返。
定理 4.5.2：有限非周期不可约 Markov 链必是正常返链。
4.6 分支过程（branching process）
考虑某个群体，其一个个体繁衍下一代的子女数是随机的，可能是等，
有一定的概率分布，若用表示一个个体繁衍下一代的子女数，则是随机变量，
L2,1,0
J J
11
设分布为。假定各代个体的繁衍能力相同且是独立的繁衍下一代，表示第0代祖先的数目，一般假定为1，以表示第代中个体数目，称为分支过程。以表示第代中第i个个体繁衍下一代数目，
独立同分布，共同分布为的分布，则
L2,1,0),( === kkJPp
k
0
X
n
X n
0,≥nX
n i
J n
i
J
J
∑
=
+
=+++=
n
n
X
i
iXn
JJJJX
1
211
L
这样若给定则的分布就确定了，与无关，故为Markov
链，状态空间
n
X
1+n
X
11
,
n
XX L 0,≥nX
n
{ }L2,1,0=S，一步转移概率
() 0,
1
1
>?
=====
∑
=
+
ijJPiXjXPP
i
k
knnij
，1
00
=P。
令1,)(
0
≤=
∑
∞
=
ssps
l
l
l
φ为的母函数，定义J ss =)(
0
φ，)()(
1
ss φφ =，
()1,)()(
1
≥=
nss
nn
φφφ，显然( ) ( ))()()( sss
nmmnmn
φφφφφ ==
+
。
定理 4.6.1：)(s
n
φ 为 的母函数。
n
X
证明：归纳法。设)(s
n
φ为的母函数，考虑的母函数记为。
n
X
1+n
X )(
1
sg
n+
[]
() 1)()(
)()()(
)()()(
)()()()(
),()()(
1
010
0010
00 100
1
00
1
0
11
1
≤==
====
=====
=======
=====
+
∞
==
∞
=
∑
∞
=
∞
==
∞
=
∞
=
∞
==
∞
=
∞
=
+
∞
=
∞
=
+
∞
=
++
∑∏∑
∑∑∑∑
∑∑ ∑∑∑
∑∑∑
=
sss
siXPEsiXP
EsiXPsjJPiXP
siXPjJPsiXPiXjXP
siXjXPsjXPsg
nn
i
i
n
i
k
J
i
n
J
i
n
j
j
i
k
k
i
n
ji
j
n
i
k
k
ji
j
nnn
ji
j
nn
j
j
nn
k
i
k
k
φφφ
φ
对于分支过程，我们主要关心的是，种群灭绝概率，以表示，则 q
12
{} {} )0(lim)0(lim0lim0
11
n
n
n
n
n
l
l
n
n
n
XPXPXPq φ
∞→∞→
=
∞→
∞
=
===
==
==
UU
（注意{}{ }00
1
=?=
+ll
XX）
1
0
=p，种群不能发端；种群永不消亡。故以下假定。这时
，故
0
0
=p 10
0
<< p
0)(
1
1
>=′
∑
∞
=
k
k
k
kspsφ )(sφ在上单调非降。故 ]1,0[
1)0()0()0(0
10
≤≤≤≤=<
n
p φφφ L
序列)0(
n
φ单调非降有上界必有极限，故)0(lim0
0 n
n
qp φ
∞→
=≤<。另一方面
()0()0(
1 nn
φφφ =
+
，令有∞→n )(qq φ=，故为方程q ss =)(φ的一个正根。近一步有
定理 4.6.2：对于分支过程,设
n
X 10
0
<< p,,则
∑
∞
=
==
1k
k
kpEJμ
1) 灭绝概率 是方程q ss =)(φ 的最小正根；
2) 11 =?≤ qμ 。
证明：1)设x为方程ss =)(φ的任意正根，由于)(sφ在上单调非降，故]1,0[
xx =≤ )()0( φφ，由归纳法立得x
n
≤)0(φ，令∞→n有xq
n
n
≤=
∞→
)0(limφ。
2) 令10,
)(
)(
1
10
≤<+==
∑
∞
=
ssp
s
p
s
s
sf
k
k
k
φ
，则1)1(,)0( =∞= ff，
1)1(,)0(?=′?∞=′ μff，，故0)( >′′ sf )(sf ′严格增。当1≤μ时，在，
恒为负，此时严格减，由
10 << s )(sf ′
)(sf 1)1( =f，在(0,1)中，从而方程1)( >sf ss =)(φ的解不能在(0,1)内，故。若1=q 1>μ，由连续函数介值定理必有使得
。在，单调降，在，单调增。由，，
于是有使得，即
10 << x
0)( =′ xf ),0( x )(sf )1,(x )(sf 1)1( =f 1)( <xf
),0(
0
xs ∈ 1)(
0
=sf
00
)( ss =φ，故10
0
<≤< sq。
13
