96
龚光鲁,钱敏平著 应用随机过程教程及其在 算法与智能计算中的应用
清华大学出版社,2003
第 5 章 时间 离散 的 Markov 链
1 Markov 链的概念
1.1 定义与 Markov 性质
定义 ５,１ 随机过程可能取到的值 ( 状态 ) 组成的集合记为 S,称为随机过程的 状态
空间,随机序列 }0:{ ≥nnx 称为 Markov 链,如果这些随机变量都是离散的 (状态空间 S
至多是一个可数集,即 或者 S 是有限集,或者 S 可与自然数一一对应 ),而且对于 0≥?n
及任意状态 10,,,,?niiji L,都有
=====+ ),,,|( 00111 iiijP nnnn xxxx L )|( 1 ijP nn ==+ xx,(5,1)
这个性质称为 Markov 性质,
Markov 性的等价性质 1
若 A 为任意形如 })(.,,)(,)({ 111100 === nn iii wxwxwx L 的事件的并,即
U L
k
knnkk iiiA },,,{,11,11,00 ==== xxx
则有
)(),( 11 ijPiAjP nnnn ===== ++ xxxx,(5,2)
Markov 性的等价性质 2
进一步还可以证明 Markov 性等价于,对于过程在时刻 n+1 及其以后的时刻所确定的事件 B 及 等价性质 中之 A有
)(),( iBPiABP nn === xx,(5,3)
或
)()|()( iBPiAPiABP nnn ==== xxx (5,3)’
（ 5,3） 式 的含意为,如果过程在时刻 n 处于状态 i,那么不管它以前处于什么状态,过程以后处于什么状态的概率是一样的,这就说明了,Markov 链在 已知,现在,的条件下,,将来,与,过去,是条件独立的,我们把它另列为 一条性质 。
Markov 性的等价性质 3
在已知,现在,的条件下,,将来,与,过去,是条件独立的,
Markov 性的等价性质 4
对 Markov 链 }{ nx 及 0,1 ≥≥? nm 及任意状态 10,,,,?niiji L,有
=====+ ),,,|( 0011 iiijP nnnmn xxxx L )|( ijP nmn ==+ xx,(5,4)
97
证明 对 m 作归纳法,m=1 时即为 (5,1)式,设 m 时 (5,4)式正确,今证 m+1 时也正确,
),,,|( 00111 iiijP nnnmn ====++ xxxx L
),,,|,( 001111 iiikjP nnnnmn
k
======+++∑ xxxxx L
),,,,|( 001111 iiikjP nnnnmn
k
======+++∑ xxxxx L ×
),,,|( 00111 iiikP nnnn ====+ xxxx L,
利用归纳法假设及 (5,1)式,上式简化为
)|( 11 kjP nmn
k
=== +++∑ xx )|( 1 ikP nn ==+ xx
),|( 11 ikjP nnmn
k
==== +++∑ xxx )|( 1 ikP nn ==+ xx
)|,( 11 ikjP nnmn
k
==== +++∑ xxx )|,( 1 ijP nmn === ++ xx,
Markov 性的等价性质 5
对状态空间 S 上的任意有界实值函数 f 有
))((),,)(( 1001 nnnnnn ifEiifE ==== ++ xxxxx L 。 (5,5)
( (5,1) 式 是 (5,5)式的特例,即 )()( }{ xIxf j= 的情形,从 (5,1)式 推广为 (5,5)式 需要用测度论的基本知识,我们把它略去 ),
[注 ] 第 1,2,3,5 种等价性质都有与第 4 种等价性质 类似 的表达形式,请读者自检,
Markov 性的等价性质 6 （ 最一般的形式 ）
对于常见的实数集合 Λ,及由随机序列 mx 在时刻 n 及其后的信息所决定的随机变量
nh,恒有
)(),,( 00 nnnnnn iPiiP =Λ∈===Λ∈ xhxxh L
或
)()),,( 00 nnnnnn iEiiE ==== xhxxh L,
[注 ] 这个等价条件的内涵十分丰富,其等价性的证明在测度论中非常典型,本书从略,
在以实际问题 为背景的 Markov 链的研究中,人们 最 关心的是,经过时间 n,过程到达某些状态的概率有多大,以及需要多长时间才能到达这些状态,这类问题的描述首先涉及
Markov 链的转移特性 —— Markov 链的 n 步转移概率矩阵族,
１,２ 概率转移矩阵
定义 ５,２ 记
=),( mnpij,
并定义无穷矩阵
98
P )),((),( mnpmn ij=,
由于此无穷矩阵的分量都是非负的且不超过 1,易见这种无穷矩阵的乘法满足结合律,又因为
≠
===
)(0
)(1),(
ji
jinnp
ijij
D
d,(Kroneker 记号 )
所以 P =),( nn I (无穷单位矩阵 ),特别地,P )1,( +nn 称为时刻 n (到时刻 1+n )的 概率转移矩阵 而 P ),( knn + 就称为从 n 出发的 k 步概率转移矩阵,
命题 ５,３ 概率转移矩阵族满足以下 的性质
记 1 为分量全是 1 的无穷行向量 ( 矩阵 ),其维数与此 Markov 链的状态数一致,我们有
(P.1) 1),(0 ≤≤ mnpij,P ),( mn 1 T =1 T,( 上标 T 表示转置运算 )
(P.2) ( Chapman - Kolmogorov 方程 ) 对于 nml ≥≥? 有
P =),( ln P ),( mn P ),( lm,(5,6)
写成分量形式就是
∑=
k
kjikij lmpmnplnp ),(),(),(,(5,6)’
证明 验证 (P,1)
∑ ∑ ===
j j
nmij ijPmnp )|(),( xx,
U
j
nnm iPijP 1)|()|}{( ==?==== xxx 全集,
验证 (P,2)
∑∑ =====
k
mlnm
k
kjik kjPikPlmpmnp )|()|(),(),( xxxx
∑ ======
k
nmlnm ikjPikP ),|()|( xxxxx ∑ ====
k
nml ikjP )|,( xxx
U
k
nml ikjP )|},{( ==== xxx )|( ijP nl === xx,
１,３ 时齐的 Markov 链
定义 ５,４ Markov 链称为 时齐的,如果其概率转移阵 P )1,( +nn 与 n 无关 (即 1 步转移概率与出发时刻 n 无关,
我们把此矩阵简记为 P= )( ijp,由 (5,6)式得到
P =+ ),( mnn P )1,( +nn P L)2,1( ++ nn P =+?+ ),1( mnmn Pm
它也不依赖出发时刻 n,我们把它改记成 )(mP,( )( )()( mijm p=P ),其分量
)()( ijPp nmnmij === + xx 为 Markov 链 }0,{ ≥nnx 的 m 步转移概率,它也与出发时刻 n 无
99
关,于是 Chapman-Kolmogorov 方程的矩阵形式变为
)()()( nmnm PPP =+ (5,6)’’
而其分量形式为
∑=+
k
n
kj
m
ik
nm
ij ppp
)()()( (5,6)’’’
(其实 (5,6)’’式是显然的,因为它就是 P m + n = P m P n ),
以后在 本书中除非特别声明,我们所考虑的 Markov 链,均为 时 齐的 Markov 链,
对于时齐的 Markov 链 }0,{ ≥nnx,描述它的演化的最基本的量,就是它的转移概率矩阵 P= )( ijp,),,( Sjipij ∈,其中第 i 行就是给定 in =x 时,1+nx 的条件概率分布,
转移概率矩阵 P 是一个 随机矩阵,即它满足,
(1) P 中的元素均为非负,即 0≥ijp,
(2) P 中的每一行的元素之和均为 1,即 1=∑
j
ijp,
Markov 链的转移概率 },,{ Sjipij ∈ （ 或者说转移概率矩阵 P） 是刻 画 Markov 链的统计特征的基本量,事实上,一个 Markov 链可由其初始状态 0x 的统计性质 （ 即其初始分布
)( 0)0( iPi == xm ） 以及其转移概率矩阵 P 所完全确定,这就是 下面的定理 。
定理 5,５ （ M arkov 链的有限维分布 ） 若 Markov 链 }0,{ ≥nnx 的初始分布为
)( 0)0( iPi == xm,其转移概率矩阵为 P= )( ijp,则 }0,{ ≥nnx 的有限维分布为
SiiipppiiiP niiiiiiinn
nn ∈?====?,,,),,,( 10
)0(
1100 121100 LLL mxxx,
证明 由乘法公 式与 Markov 性得
),(),()()(
),,,(
00110022001100
1100
nnnn
nn
iiiPiiiPiiPiP
iiiP
==========
===
xxxxxxxxx
xxx
LL
L
nn iiiiiii ppp 121100
)0(
= Lm?
记 )()( iP nni == xm,它称为 Markov 链在 时刻 n 的绝对概率,再记由 )(nim 构成的行向量为 )(nm = ):( )( Sini ∈m,那么,我们有
定理 5,６ )( nm+m = )(mm )(nP,从而有 )(nm = )0(m nP
证明 ∑∑ ======= +++
i
n
ij
m
i
i
mmnmnm
nm
j piPijPjP
)()()( )()()( mxxxxm
= jnm )( )()( Pm,?
100
定理 ５,５ 与定理 ５,６ 说明 了 Markov 链的统计性质 （ 包括其长 时间极限行为 ）,完全可由其转移概率矩阵 P,以及它的初始分布 )0(m 所决定,因此,Markov 链的很多性质的研究就归结为随机矩阵的性质,
１,４ Markov 链的例
例 ５,７ （ 随机徘徊 ）
独立同分布的随机变量的 部分和序列,称为 随机徘徊,它是时间参数离散情形时的时齐的独立增量过程,又若其中的随机变量只取 １ 与 － １ 两个值,则称为 简单随机徘徊,
今考虑一个简单随机徘徊 }0,{ ≥nnx,其状态空间为 Z=S ={全体整数 },由 nx 的定义
∑
=
+=
n
k
kn Z
1
0xx,
其中 }0,{ ≥kZ k 为独立同分布随机变量序列,满足
pqZk
11~ )1( pq?=,
这里 nx 表示一个粒子每次分别以概率 p 与 q 向右与向左走一格,21=p 的情况称为 对称简单随机徘徊,由于随机徘徊是时齐的独立增量 过程,由第 3 章可知它也是时齐的 Markov 链,
又因为 nxxx L,,10 都是 nZZZ,,,10 L 的部分和,所以,它们和 1+nZ 独立,故
=
+=
=?===?==
==+====
++
++
其它0
1
1
)()(
)()(
11
11
ijq
ijp
ijZPiijZP
ijZPijPp
nnn
nnnnnij
x
xxxx
,
即其转移矩阵为
P = )( ijp =
LLLLLLL
MMMMMMM
MM
MM
MM
MMMMMMM
LLLLLLL
pq
pq
pq
000
000
000
,
而绝对概率为
≥?==
++
其它情形 ），
奇偶同与,且若，
(0
)()1()( 222 jnjnppCjP
jnjnjn
nnx,
事实上 )( jP n =x 就是,n 个相互独立的随机事件 }1{},...,1{},1{ 21 === nZZZ 中恰好有
101
2
jn + 个发生的概率 (
nx 要到达状态 j,所需的步数 n 不可能小于 j,故 jn ≥,设
+
nN
和?nN 分别表示在前 n 步中向右和向左的步 数,则显然有?+ += nn NNn,
+?=
nnn NNx,于是 ( )nn nN x+=
+
2
1,从而 ( )jnNj
nn +=?=
+
2
1x,又因为
( )nn nN x+=+2 是偶数,因此 n 与 nx 的奇偶性相同 ),对于初始状态为 i=0x 的简单随机徘徊,类似可得
≥?
=
===
++?+
其它情形 ）
奇偶同与,且若
(0
)()1(
)|(
222
0
)(
ijnijnppC
ijPp
ijnijnijn
n
n
n
ij xx
,
例 ５,８ (两端为反射壁的随机徘徊 ) 在例 ５,７ 中,如果在位置 a 与 b ( a<b ) 分别设置一个反射壁,即当粒子到达 a 与 b 时,下一步则以概率为 1 地分别,反射,到 1+a
与 1?b,此时粒子的运动仍然是一个 Markov 链,与例 ５,７ 不同处仅在于
).1(,0,1;)1(,0,1,1,,1,?≠==+≠==?+ bjppajpp jbbbjaaa
即其转移矩阵为
P = )( ijp =
01
000
000
000
10
LLLLL
MMMMMMM
MM
MM
MM
MMMMMMM
LLLLL
pq
pq
pq
,
读者可自行写出一端反射壁的随机徘徊的转移矩阵 P,
例 ５,９ (两端为吸收壁的随机徘徊 ) 若 Markov 链取值于 },,1,{ baa L+,且其转移矩阵为
P = )( ijp =
10
000
000
000
01
LLLLL
MMMMMMM
MM
MM
MM
MMMMMMM
LLLLL
pq
pq
pq
,
则称此 Markov 链为在 a 与 b 设有吸收壁的随机徘徊,即,1== bbaa pp,并称 a 与 b 为
102
Markov 链的 吸收态,
例 ５,１０ ( 货仓存货问题 )
设 一个运货仓库每月进货的件数是一个独立同分布的随机变量序列 },2,1:{ L=nnh,
其中 nh 表示第 n 个月进货的件数,
N
n pp
N
L
L
1
1~h,又设
0x?
NN
N
11
1
~ L
L
,仓库的货物容量为 N 件,每当仓库的货物超过 N 件时,就将 N 件打包发运,记第 n个月底的存货量为 nx,那么
1
1
1
1
≥
<
+
+=
nn
nn
nn
nn
n N
N
N xh
xh
hx
hxx 。
于是 }0::{ ≥nnx 是一个 Markov 链,事实上
≤===?+=
<<===?==
≥====?+
<<=====+=
=====
+
+
+
+
+
)(),,,|(
)(),,,|(
)(),,,|(
)(),,,,|(
),,,,(
11001
11001
11001
1111001
1111001
ijiiiijNP
NjiiiiijP
jiiiijNiP
NjiiiiijiP
iiiijP
nnnn
nnnn
nnnn
nnnn
nnnn
xxxh
xxxh
xxxh
xxxxh
xxxxx
L
L
L
L
L
,
≥?+=
<<?==
+
+
)()(
)()(
1
1
jiijNP
NjiijP
n
n
h
h
≥
<<=
+
)(
)(
jip
Njip
ijN
ij,
同样的推理 也 得到
)|( 01 ijP == xx
≥
<<=
+
)(
)(
jip
Njip
ijN
ij,
所以 }0,{ ≥nnx 是时齐的 Markov 链,且其转移矩阵的分量为
≥
<<=
+
)(
)(
jip
Njipp
ijN
ij
ij,
例 5,１１ ( 品牌选择 ) 设市场上销售 A,B,C,D 四种品牌的牙膏,根据市场调查,消费者购买哪一种品牌的牙膏,近似地仅与他前一次购买的品牌有关,而与这之前购买的品牌无关,记 0x 为某消费者最初所购买的牙膏的品牌,L,,21 xx 分别表示他在这之后 各次 所购买的牙膏的品牌,则 }0:{ ≥nnx 为一 Markov 链,其状态空间为 S={A,B,C,D},它的转移概率矩阵可以从市场调查中近似地获得,假定经过长期市场调查统计得到近似的转移矩阵为
103
P=
70.010.010.010.0
02.080.010.008.0
05.005.080.010.0
02.003.005.090.0
,
对于这个链,人们感兴趣的是这四种品牌的牙膏的市场占有率随时间进程的变化,
例 ５,１２ ( Wright-Fisher 遗传模型 ) 遗传的要素是染色体,遗传性质的携带者称为基因,它们位于染色体上,基因控制着生物的特征,它们是成对出现的,控制同一特征的不同基因称为等位基因,记这对等位基因为 A 和 a.,分别称为显性的与隐性的,在一个总体中基因 A 和 a 出现的频率称为基因频率,分别记为 p 和 p?1,设总体中的个体数为 2N,
每个个体的基因按 A 型基因的基因频率的大小,在下一代中转移成为 A 型基因,因此,繁殖出的第二代的基因型是由试验次数为 2N 的 Bernoulli试验所确定的,即如果在第 n 代母体中 A 型基 因出现了 i 次,而 a 型基因出现了 iN?2 次,则下一代出现 A 型基因的概率为
N
ip
i 2=,而出现 a 型基因的概率为 ip?1,记 nx 为第 n 代中携带 A 型基因的个体数,则易证 }0,{ ≥nnx 是一状态空间为 }2,,2,1,0{ NS L= 的时齐 Markov 链,其转移概率矩阵为
P= )( ijp,其中
jNjj
N
jN
i
j
i
j
Nnnij N
i
N
iCppCijPp
+?=?====
2
2
2
21 )21()2()1()( xx,
2,Markov 链的状态分类
2,1 首达分解,n 步转移概率的递推式,矩母函数,常返性
定义 ５,１３ （ 首次进入状态 j 的时刻 ） 把从 i 出发在 n )1(≥ 步转移中首次到达 j 的概率记为 )(nijf,用数学式表达即
)1(),1,2,1,,( 0)( ≥=?=≠== ninkjjPf knnij xxx L (5,7)
而把 Markov 链 }0,{ ≥nnx 首次 击中状态 j 的时刻 记为 jT,那么 jT 是一随机变量,但是与普通的随机变量有一点不同,就是它可以取值 ∞ （ 事实上,它 还 是一个 )( nx 停时,即它是否不大于 m,只由随机序列 nx 在时刻 m 前的信息完全确定 ）,即
∞
=≥=≥=
其它情形 ）
使得若存在
(
)1(}:1min{ jnjnT nn
j
xx,
从而 有
)1()( )(0 ≥=== nfinTP nijj x,
104
∑
∞
=
==∞=
1
)(
0 1)(
n
n
ijj fiTP x,,(5,8)
再记
∑∞
=
=
1
)(
n
n
ijij ff )|( 0 iTP j =+∞<= x 1)ii1n(P 0n ￡==?$= xx使得,(5,9)
那么 ijf 表示 }0n{ n?：x 从 i 出发,在有限时间内它能够到达 j 的概率 (或者说,从 i 出发最终转移到状态 j 的概率 ),
定义 ５,１４ （ 常返态与暂态 ） Markov 链 }0{?nn：x 的状态 i 称为 常返态,如
果 从 i 出发,能以概率为 1 地,最终又能回到 i,即 1=iif,如果状态 i 不是常返态,则称它为 暂态,
定理 5,１５ （ Markov 链的 首达分解定理 ） 对于任意状态 ji,,任意时刻 n,有
∑
=
= n
k
kn
jj
k
ij
n
ij pfp
1
)()()(,(5,10)
证明 利用 Markov 性质,我们有
=
=======
n
k
jnn
n
ij ikTjPijPp
1
0
)( ))|,()|(
０xxxx
∑∑
==
=========
n
k
k
ijkn
n
k
jjn fjjPikTPikTjP
1
)(
1
00 )|()|(),|( xxxxx,?
令
0,)0()0( == ijijij fp d,
并定义矩母函数
∑∞
=
=
0
)()(
k
nn
ijij zpzP,∑∞
=
=
0
)()(
k
nn
ijij zfzF,
易见定理 ５,１５ 可以写成如下的矩母函数形式
定理 5,１５ ’
)()()( zPzFzP jjijijij += d,(5,10) ’,?
从 （ ５,１０ ）＇ 可以解出
)(1
1)(
zFzP jjjj?=,(5,11)
)(1
)()(
zF
zFzF
jj
ij
ij?=,(5,12)
105
在 (5,11) 式中令 01?→z,便得到 ( 利用数学分析中的 Abel 定理 )
jjn
n
jj fp?=∑
∞
= 1
1
1
)(,（ ５,１１ ）＇
于是,由 常返性的定义立得如下的充要条件
定理 5,１６ （ 常返性与 暂 态的条件 ）
j 为 常返态? ∞=∑
∞
=1
)(
n
n
jjp ;
j 为暂 态? ∞<∑
∞
=1
)(
n
n
jjp,
推论 ５,１７ 状态 j 为暂 态,i ∞<∑
∞
=1
)(
n
n
ijp,从而 0lim
)( =
∞→
n
ijn p,
证明 右 ∞<= )1(ijF,
推论 ５,１８ (有限状态 Markov 链 ) 有限状态 Markov 链至少存在一个常返态,
证明 假设有限状态 Markov 链的所有状态均为暂态,那么由
∑ ∑
≤≤ ≤≤
∞→→====
Nj Nj
nn
ijn pijP
1 1
)(
0 0)|(1 xx,
这就导致了矛盾,
定义 ５,２０ 如果存在 0≥n,使 0)( >nijp,则称状态 i 可达 状态 j,记作 ji →,表示从状态 i 经过有限步的转移可以到达状态 j,它等价于,存在 11,,?nii L 使
,10,0
1
≤≤>
+
nkp
kkii
其中 jiii n ==,0,
注 （ Markov 链转移的图示 ） 把 Markov 链的状态记为顶点 。 如果 0>ijp,则从状态
i 到状态 j 画一条有向边,这样就得到表示 Markov 链的转移情况的一个有向图 （ 有些边可能是双向的 ）,那么,ji → 等价于存在顶点 i 到顶点 j 的一条由定向边组成的通路,
命题 5,２１ 设 ji → 且 ij → （ 记为 ji? ）,则状态 i 与 j 常返与否是相同的,
证明 由于 ji?,故存在 0,≥nm,使得 0,0 )()( >> njimij pp,记
0)()( >=
n
ji
m
ij ppa,
由 Chapman-Kolmogorov 方程可知,对任意非负整数 r,有
)()()()()( r
jj
n
ji
r
jj
m
ij
nrm
ii ppppp?=≥
++ a,
由对称性同样有
)()()()()( r
ii
m
ij
r
ii
n
ji
mrn
jj ppppp?=≥
++ a,
106
从而可知级数 ∑
r
r
iip
)( 与 ∑
r
r
jjp
)( 同时收敛或发散,故 ji,的常返与否是相同的
例 ５,２２ (二值链 )
P )1,0(1 1 <<
-
-= ba
bb
aa,
直观上可以想到状态 0 和 1 均是常返态,下面证明此结论,
利用归纳法我们可以得到
+?
++
+?== bb
aa
ba
ba
ab
ab
ba
n
nn
1)1(
)1(1
)(2
)1(
11
11
)(2
1)( PP,
故 nn babaababp )1()(2 1)(2 1)(00?++++=,
由于 1,0 << ba,就有 0)(2 1lim )(00 >+=
∞→ ba
bp n
n
,从而 ∞=∑
∞
=1
)(
00
n
np,故 0 为常返态,同样状态 1 也是常返态,
例 ５,２３ 在简单随机徘徊中考虑状态 0,此时
),2,1,0(0)12(00 L==+ np n,),2,1(2)2(00 L== nqpCp nnnnn,
用 Stirling 公式,!n ～ nn en?+ 212p （ 其中当 1lim =
∞→ n
n
n b
a 时,我们记
na ～ nb ）,我们可得
)2(
00
np ～
n
pq n
p
)4(,
因此 ∑
∞
=1
)(
00
n
np 收敛当且仅当 ∑
∞
=1
)4(
n
n
n
pq
p 收敛,又因为 14 ≤pq,且等号成立当且仅当
2
1== qp,于是 ∞=∑∞
=1
)(
00
n
np 当且仅当
2
1== qp,也就是说,当且只当在简单随机徘徊为对称时,状态 0 是常返的,
* 例 ５,２４ ( dZ 上的对称随机徘徊 ) 记 dZ 为 d 维整数格点组成的集合,每一个格点有 d 个方向,故各有 2d 个邻点,在 Markov 链已知处在某一 个格 点的条件下,以相同的条件概率 ( 即各以概率 d21 ),
在下一个时刻转移到它的任意一个邻点,这样的 Markov 链称为 dZ 上的对称随机徘 徊,显见各个点的常返性与暂态性是一样的,下面我们考察原点的情形,显然 0)12(00 =?np,
对于正整数 m,把 m 个不同的元素分成 l个组,使第 j 组恰有 jk 个元素 ( mkk l =++L1 ) 的不
107
同分法的数目记为 lkkmC,,1 L,那么,由归纳法可得 !! !
1
,,2
1
11
l
k
km
k
m
kk
m kk
mCCC l
LL
L ==
,于是
){(
1 1
)(
00 ∑
=++ =
=
nkk
d
i
i
n
d
kiPp
L
I 步 ）各走个坐标方向两侧独立地向第
∑
=++
=
nkk
nkkkk
n
d
dd
dCL
L
1
11 2,,,,
2 )2
1( ∑
=++
=
nkk
n
dd dkk
n
L L1
2
22
1
)21()!()!( )!2(
∑
=++
=
nkk
n
kk
n
n
nn
d
d
dCC L
L
1
1 2,,
22 ]
1[
2
1
,
这样,当 2=d 时,用 nn
nk
knk
n CC 2
2,][ =
￡
- 及 Stirling 公式,我们有
nCp nnnn?≈= p 1)(41 222)(00,
而当 3≥d 时我们利用下面的 引理,
引理 ５,２５ 在 ∞→n 时 有近似关系
d
n
d
n
n
kk
n
nk
CC dd
i
i
,,,,
1
1
max LL ≈
∑
=
=
,nC nnn?≈ p121 22,?
( 此引理可用 Stirling 公式证明 ),
利用引理 ５,２５,就得到
n
nnn
n C
dp 22
)(
00
1
2
1≤ ][max,,1
1
d
d
i
i
kk
n
nk
C L
∑
=
=
d
n
d
n
nn Cnd
,,11 L
p≈
dd
n
d
n
nn
n
d
ne
d
n
nen
nd ]2)[(
21
p
p
p?
≈
2
1
d
n
常数≈,
可见
∑∞
=?
≥∞<
≤∞=
0
)(
00 )3(
)2(
n
n
d
dp
,
即,对于 dZ 上的对称 简单 随机徘徊,当 2≤d 时,一切状态都是常返态,而当 3≥d 时,一切状态都是暂态,这个结论在直观上是很清楚的,在 d 大时,能去的地方多了,回返的可能性就小了,
因为常返态能以概率为 1 地返回,直观地看,从常 返态 i 能到达的状态 j,必须以概率为 1
返回 i,而返回 i 后又可达 j,看来似乎 j 总能返回自己,即 j 也应是常返态,另一方面,常返态既能以概率为 1 地返回一次,就能返回第二次,…,从而能返回 ∞ 次,即若状态 i 为常返态,则 Markov 链无穷次返回状态 i 的概率为 1,而若状态 j 为暂态,则 Markov 链以正概率不能返回,从而无穷次返回状态 j 的概率为 0,下段将致力于证明这两个结论,
2,2 常返性再访与 Markov 链的基本结构
设随机变量 jh 表示 Markov 链 nx 访问状态 j 的次数,即把 nx 作为下标 1≥n 的随机序
108
列时,在此序列中总共取到状态 j 的次数 (若在此序列中 j 被取到了 ∞ 次,则我们认为
∞=jh,所以 jh 是一个可以取值 ∞ 的非负整值随机变量 ),按定 义就有
)1( 0 iPf jij =≥= xh,
定理 5,２６
(1) 若 j 为常返态,则
)()( 0 SifiP ijj ∈?==∞= xh,
特别 是 在 ji = 时,有 1)( 0 ==∞= jP j xh,
(2) 若 j 为暂态,则 )(1)( 0 SiffiE
jj
ij
j ∈==xh,
证明 （ 1） 按 jT 取值的不同,把要考虑的事件划分为互不相容的事件之并,利用 Markov
性及全概 率 公式,我们得到
∑∞
=
====≥==≥
1
000 )(),()(
k
jjjj ikTPikTnPinP xxhxh
∑∞
=
===<≠=≥=
1
00 )()),(,,(
k
jlkj ikTPikljjnP xxxxh
)1()()1(
)()1()()(
0
1
00
1
00
1
0
jnPfikTPjnP
ikTPjnPikTPjnP
jij
k
jj
k
jj
k
jkj
=?≥====?≥=
===?≥====≥=
∑
∑∑
∞
=
∞
=
∞
=
xhxxh
xxhxxh
反复使用上式,就可推出
1
0
2
0 ][)1(][)(
==≥==≥ n
jjijj
n
jjijj ffjPffinP xhxh )1( ≥n,
由于 j 为常返态,即 1=jjf,令 ∞→n 就得到
SifiP ijj ∈?==∞= )( 0xh
（ 2） 由于 jh 为非负整值随机变量,与普通的期望类似地有条件期望公式
∑∞
=
=≥==
1
00 )()(
n
jj inPiE xhxh,
故由 （ 1） 中的推导及 1<jjf (因为假定暂态 j 为暂态 ) 可推出
109
SiffffiE
jj
ij
n
n
jjijj ∈=== ∑∞
=
1][)( 1
1
0xh,
推论 ５,２７ (常返与暂态的另一个等价条件 )
(1) 状态 j 为常返态,当且仅当,1)( 0 ==∞= jP j xh ；
(2) 状态 j 为暂态,当且仅当,0)( 0 ==∞= jP j xh,
证 (2) 由定理 5,２６ 得
==∞= 0)( 0 jP j xh 1)( 0 ≠?∞<= jjj fjE xh,即 j 为暂态,
[注 1] 这个推论就是说,在条件概率 )|( 0 jP =? x 下,事件 ∞=jh 的条件概率只能为
0 或 1,也称为对于 此事件 ＂ 条件 0 - 1 律 ＂ 成立,
[注 2] 推论 ５,２７ 清楚地说明了常返态与暂态的含义,对于 Markov 链,常返态是由 它出发能 ∞ 次返回的状态,而随着时间的发展,暂态将逐渐消失,所以,在对用 Markov 链描述的模型作稳态设计时,暂态是不予考虑的,这正说明了为什么区分常返态与暂态是十分重要的,
定理 5,２８ 若 i 常返,且 ji →,则 1== jjji ff,从而 j 也常返,
证明 记 0inf )(0 >= mijm pm,由于 i 为常返态,故
)|(1 0 iP i =∞== xh
)|,( 0
00
iinjP nmm ==∞== + xxx 使个有 )|,( 0
00
iinjP nmm ==∞≠+ + xxx 使个有
)|,( 0
00
iinjP nmm ==∞=≤ + xxx 使个有 )|( 0
0
ijP m =≠+ xx
)1()|( )(0)( 00 mijimij pjTPp?+=∞<≤ x
Pp mij= 1(1 )( 0 ))|( 0 jTi =∞< x 1≤,
因此
1)|( 0 ==∞<= jTPf iji x,
于是存在 n 使 0)( >njif,从而 0)()( >≥ njinji fp,即 ij →,由命题 5,２１ 得 j 的常返性,
上面得到的关于状态为常返 （ 或暂态 ） 的条件,从概念的含义看是很清楚的,但是很难用于实际判断,比较起来,用 命题 ５,１６ 来判断状态 j 是否常返 常 更为可行,
[注 ] (∑
∞
=1
)(
n
n
jjp 的概率含义 ) 记
==
其它情形 ）
若
(0
)(1)(
}{
jI n
nj
xx,
110
那么 ∑
∞
=
=
1
}{ )(
n
njj I xh,因此
∑∑
∞
=
∞
=
===
1
0
1
)( )(
n
n
n
n
jj jjPp xx )())(( 0
1
0}{ iEiIE j
n
nj ==== ∑∞
=
xhxx,
Markov 链的基本结构
定义 ５,２８ （ 状态的互通性 ） 两个互相可达的 ji,称为是 互通的,记为 ji?,
命题 5,２９ 在常返态间,互通性是等价关系,即它满足
（ １ ） 自反性,ii? ；
（ ２ ） 对称性,若 ji?,则 ji? ；
（ ３ ） 传递性,若 ji?,且 kj?,则 ki?,
证明 我们只须证明传递性,设 ji?,则存在整数 n,使得 0)( >nijp,又由于
kj?,故存在整数 m,使得 0)( >mjkp,因此 由 Chapman-Kolmogorov 方程得到
0)()()()()( >≥= ∑
∈
+ m
jk
n
ij
Sr
m
rk
n
ir
nm
ik ppppp,
故 ki →,同理可证,ik →,从而有 ki?,
注 与多数课本不同的是,在本书中我们 只对常返态考虑等价性,原因在于对于暂态果 i 不可能有 ii →,也就是说,只在常返态间,互通性才是自返的,即 ii →,只有此时它才可能是一个数学上的等价关系,
Markov 链的状态,除暂态外,可利用互通这个等价关系划分成不同的等价类,即把互通的常返状态归入同一类中,称为一个 常返类,而把所有的暂态状态,通通放到一个,另类,
中,不再加以细分,单个状态 k 是一个常返类的充要要条 件为,1=kkp,此时 k 为 吸收态,
定义 ５,３０ (状态闭集与不可约性 )
状态的集合 A 称为 闭集,如果对于任意状态 Ai∈,满足 ∑
∈
=
Aj
ijp 1,显见状态空间 (即全体状态 ) 是一个闭集,如果除此以外再也没有其它非空闭集,则称此 Markov 链为 不可约的,
显见,一个常 返类是闭集,而且它不含更小的闭集,
简单随机徘徊的所有状态都在同一等价类,故它是 一 个 不可约 Markov 链,而两端为 0
和 N 的吸收壁随机徘徊,吸收状态 0 和 N 分别都是一个单点常返类,它们是仅有的真闭集 (即除状态空间以外的闭集 ),此 Markov 链是 可约的,
命题 5,３ １ （ 状态分解定理 ） （ １ ） Markov 链的状态空间 S 可唯一分解为,
LUUU 21 HHTS =,
其中 T 为暂态的全体,而 iH 为等价常返类,
（ ２ ） 若 Markov 链的初分布集中在某个常返类 kH 上,则此 Markov 链概率为 1 地永远在此常返类中,也就是说,它也可以看成状态空间为 kH 的不可约 Markov 链,
111
所有的状态全是常返态的链称为 常返链 ； 没有常返态的链称为 暂态链,简单随机徘徊当
2
1== qp 时 （ 即对称 的简单 随机徘徊 ）,是一个常返链 ； 而当 qp ≠ 时,是暂态链,dZ 上的对称 的简单 随机徘徊当 2≤d 时,是一个常返链 ； 而当 3≥d 时,是暂态链,
１,３ 平均回访时间与正常返性
我们将用平均回访时间是否有限,来对常返态作进一步的区分,
定义 ５,３２ （ 平均回访时间 ） 对于 Markov 链 首达 i 的时刻 iT,记
)( 0 iTE ii == xm,
则 im 表示状态 i 的 平均回访时间,iT 是一个可取 ∞ 的广义整值随机变量,它的分布表为
∞
iiiiii fff 1
21
)2()1( L
L,
当 i 为暂态时,因为 1<iif,所以 ∞=im ; 而在 i 为常返时则有
∑∑
∞
=
∞
=
====
1
)(
1
0 )(
n
n
ii
i
ii nfinTnP xm,
于是利用 im 我们可以对 常返态作进一步的区分如下
定义 ５,３３ 常返态 i 称为 零常返的 ( 简称 零态 ),如果 ∞=im ； 否则称为 正常返的,
（ 从 后面的定理 ５,４７,可以知道 有限状态 Markov 链的任何常返态必定是正常返的,
可见,零常返只能出现在可数状态 Markov 链的情形 ）,
我们还要引入一种特殊的,而 且 在物理中占重要地位的 一种 正常返态,称为 遍历态 。 为此我们先介绍周期的概念,
定义 ５,３４ （ 状态 的 周期 ） 将 满足 0)( >niip 的所有 1≥n 的整数的最大公约数记成
id,(如果对所有 1≥n 都有 0
)( =n
iip,则约定 ∞=id ),1=id 或 ∞ 的状态,称为 非周期的,1>id 的状态称为 周期的,
由周期的定义立即可知,若 n 不能被 id 整除,则必有 0)( =niip 。
定义 ５,３５ 正常返的非周期状态称为 遍历态,
例 ５,２２ （ 续 ） 例 ５,２２ 中的 两个状态均为正常返的,又由于 0)1( >iip （ i=0,1）,
即 1=id （ i=0,1）,故此 Markov 链的状态 0 和 1 均为遍历态,
读者可自行验证下面的定理,
定理 5,３６ 设 ji?,则
112
（ 1） i 为常返态,当且仅当 j 为常返态,
（ 2） i 为暂态,当且仅当 j 为暂态,
（ 3） i 为零常返态,当且仅当 j 为零常返态,
（ 4） i 为正常返态,当且仅当 j 为正常返态,
（ 5） i 为遍历态,当且仅当 j 为遍历态,
[注 ] 事实上,此时我们还有,状态 i 为周期态,当且仅当 j 为周期态,且 ji dd = 。 其证明方法是用初等数论,本书略去,
以上结论说明,零常返,正常返,周期大小,遍历,都是常返等价类的,类性质,,它们对同一 个等价类中的状态都是相同的,
3,Markov 链的转移概率的极限与不变分布
3,1 不变分布与平稳 Markov 链
定义 ５,３７ 状态空间 S 上的概率分布 p = },,{ 21 Lpp 称为 P 的 不变概率分布,简称
不变分布,如果 Ppp =,
不变分布未必存在,若状态空间 S 为有限集,且不变分布存在,则 1 是矩阵 P 的左特征值,而不变分布 p 是它的左特征向量,此时 p 可由代数方程组
Ppp =,p T1 =1
的非负解得到,其中 =1 )1,,1( L （ 上标的 T 表示取转置 ）,
命题 5,３８ 若转移矩阵为 P 的 Markov 链 }0n,{ n ≥x 的初始分布取为不变分布 p,
则 }0n,{ n ≥x 为平稳列,即对于 k1 n,,n,k,n L?,},,( nnnn
k1 ++
xx L 与 },,(
k1 nn
xx L 有相同的联合分布,(关于平稳列的一般理论可参见第 11 章 ),
(请自行验证 ),
3,2 有限状态 Markov 链的的不变分布与极限分布
定理 5,３９ 若 Markov 链 }0,{ ≥nnx 的状态空间 S 为有限集 （ 不妨设
},,2,1{ NS L= ）,且其转移概率 矩阵 P = )( ijp 满足 Sjipij ∈?>,0,则存在 S 上唯一的概率分布 p = },,,{ 21 Nppp L,使得对所有 Sji ∈,及 NSjipij 1),:min( ≤∈=d,都有,
（ 1） Ppp = (即 p 为 P 的不变概率分布 ),而且 dp ≥j ;
（ 2） ∞→nlim nP =p T1,
此外,P 还满足 指数遍历性,即
n
j
n
ij Np )1(
)( dp?≤?,
[注 ] (2 ) 远比 (1) 强,
113
证明 记 )(njM 与 )(njm 分别为矩阵 nP 的第 j 列的最大与最小值,显然
dd )1(11),:min(≤?=≤∈≡ ∑
≠
NppSjip
jk
ikijij,
因此
N
1≤d,d≥)1(
jm,d)1(1
)1(≤ NM
j,
进而
ddd NNmM jj?=≤? 1)1(1)1()1(,（ E.1）
再则,我们有
)()()()1()1( maxmaxmax nj
k
n
jiki
k
n
kjiki
n
iji
n
j MMppppM =≤== ∑∑++,
类似地
)()()()1()1( minminmin nj
k
n
jiki
k
n
kjiki
n
iji
n
j mmppppm =≥== ∑∑++
这说明 )(njM 是单调下降的,而 )(njm 是单调上升的,我们将证明
)(0)1(0 )()( ∞→→?≤?≤ nNmM nnjnj d,（ E.2）
只要证明了 （ E.2）,就由它可以推出,当 ∞→n 时,nP 的第 j 列的各分量与 )(njM 及 )(njm
有相同的极限 （ 令 )(lim nj
nj
M
∞→
≡p,则由 )()()()()( njnjjnijnjnj mMpMm?≤?≤? p,直接导出 jnj
n
p p=
∞→
)(lim ）,从而有
∑∑
∈∈∞→
+
∞→
===
Sk
kjk
Sk
kj
n
ikn
n
ijnj pppp pp
)()1( limlim
可见为了证明 (1),只须证明 （ E.2）,现在我们证明 （ E.2）,注意
∑ ∑∑?=?=? ++
k k
n
kjkiik
n
kjki
k
n
kjik
n
ji
n
ij ppppppppp
)(
*
)(
*
)()1(
*
)1( )(
∑∑
∈∈
+?=
*
)(
*
)(
* )()(
Jk
n
kjkiik
Jk
n
kjkiik pppppp,
其中 }:{ * jiij ppSjJ >∈=,}:{* *jiij ppSjJ ≤∈=,由于
∑
∈
Jj
jiij pp )( * + ∑
∈
*
* )(
Jj
jiij pp = 011)( * =?=?∑
∈Sj
jiij pp,
故而
∑
∈
*
* )(
Jj
jiij pp = ∑
∈
Jj
jiij pp )( *,
并且
dNpppppp
Jj
ji
Jj
ij
Jj
ji
Jj
ij
Jj
jiij?≤=?=? ∑∑∑∑∑
∈∈∈∈∈
11)( *
*
**,
从而
114
∑∑
∈∈
++?+?≤?
*
)(
*
)(
*
)1(
*
)1( )()(
Jk
n
kjkiik
Jk
n
kjkiik
n
ji
n
ij mppMpppp
∑
∈
=
Jk
kiik
n
j
n
j ppmM )()( *
)()( ))(1( )()( n
j
n
j mMN≤ d,（ E.3）
若选取 i,i * 满足 )1()1( ++ = njnij Mp,)1()1(* ++ = njnji mp,则由 （ E.3） 得
))(1( )()()1()1( njnjnjnj mMNmM≤? ++ d,（ E.4）
这样迭代多次,再利用 （ E.4） 便得 （ E.2）,
最后我们证明不变分布是唯一的,设 m ＝ },,,{ 2,1 nmmm L 是 P 的另一个不变分布,
则有
ppmpmmmmm ==fi=== )()( TTn2 11PPP L,
例 ５,２２ （ 续 ）
P =
bb
aa
1
1 （ 0<a,b<1）。
这时定理 5,３９ 条件满足,故不变分布 p = },{ 10 pp 存在唯一,且应满足下列方程
( ) 1),,(1 1,101010 =+=
pppppp
bb
aa 。
容易解得
)(2
1,
)(2
1
10 ba
a
ba
b
+?
=
+?
= pp 。
这里我们并不需要知道 nP 的形式,
例 ５,１１ （ 续 ） 在牙膏品牌的市场占有率的例子里,Markov 链 }0,{ ≥nnx 的所有状态均为遍历态,所以它存在唯一的不变分布 p = },,,{ 4321 pppp,且满足 p P =p,即
14321 1.008.01.09.0 ppppp =+++,
24321 1.01.08.005.0 ppppp =+++,
34321 1.08.005.003.0 ppppp =+++,
44321 7.002.005.002.0 ppppp =+++,
14321 =+++ pppp,
可以求出
115
p = }086.0,179.0,253.0,482.0{
可见,随着时间的推移,厂家 A,B,C,D 的市场占有率将分别变为 48.2%,25.3%,17.9%和
8.6%,
[注 ] 定理 5,３９ 的条件对于不变分布的存在唯一性来说太强,事实上,我们有
（ 1） 有限状态的 Markov 链只要是互通的,（ 即全体状态组成一个互通常返类 ）,它一定存在唯一的不变分布,例如,两端反射壁的随机徘徊,它不是一步互通的,nP 也没有极限,
但是它仍有唯一的不变分布,
（ ２ ） 我们将在第 5 节 中得到,可数状 态的只有正常返态的 Markov 链,一定存在不变分布,又若此链还是互通的,那么不变分布还是唯一的 （ 但是此时 nP 未必有极限 ),
3,3 转移矩阵的平均极限
在 ∞→n 时,一般地 nP 未必有极限,例如对于
=
01
10P,有 PP n =+12,IP n =2,
极限不存在的原因在于 nP 有周期性,消除周期性的办法是代之以求平均极限
n
1lim
n ∞→ )(
1?+++ nPPI L,对于可数状态的 Markov 链,虽然可以证明这个极限一定存在,但是,在本书中我们只对有限状态情形给出证明,
定理 5,４０ （ 有限状态情形的平均极限定理 ） 设 P为 NN× 转移矩阵,则
n
1lim
n ∞→ )(
1?+++ nPPI L
存在,把它记为 L )l( ij=,则它满足
2LLPLLP ===,
证明 记
L ( ) ==
)n(l(n) ij n1 )( 2 nPPP ++ L,
显见 )n(lij 是取值于 [0,1]的序列,所以存在公共子列 kn,使对于任意 Nji ≤,，
ijij lnl 某个→)(,于是
L )n( k P
kn
1= ∑
=
+k
n
m
mP
1
1
kn
1= )( 1
1
PPP k
k nn
m
m?+ +
=
∑ L→,
从而有 LLP =,同样我们有 LPL =,进而得 LLP m =,LLPm = 以及
(LL =)n (L )n LL =,
最后,我们来证明 L →)(n L,为此只要验证 L )n( 的一切收敛子列都有相同的极限,假
116
定另有一个收敛子列,L →)m( k ~L,那么,由 (LL =}mk (L )mk LL = 便得
LLLLL == ~~,但是 L 与
~L
是对称的,因此也应有
~~~ LLLLL ==
,这样就有 LL =~,
从而 L →)(n L,
[注 ] 对于可数状态的 Markov 链,定理结论仍然正确,但是证明要复杂多了,需要用
Tauber 型定理,故略,
为讨论极限矩阵 L 的形状,我们先引述一个数学分析的引理,它的证明由数学分析是不
难得到的,本书略去,
引理 ５,４１ 若,Mb0,a,0a k,n
n
nn ≤≤∞<≥ ∑ 且 )n(,bb kk,n ∞→→,则
∑∑ ∞
==
∞→ →?
1k
kk
n
1k
n
k,nk baba,
命题 5,４２ (1) jjijij lfl =,
(2),对于互通的有限状态 Markov 链,极限矩阵 L 的各行是一样的,即它具有形式
pT1L =,其中 p 是 P的不变测度,
证明 由
∑ ∑∑
= =
=
==
n
m
m
k
km
jj
k
ij
n
m
m
ijij pfnpnnl
1 1
)()(
1
)( 11)( ∑ ∑
= =
=
n
k
n
km
km
ij
k
ij pnf
1
)()( 1,
用引理 ５,４１ 便得 (1),而互通的有限 Markov 链的状态都是常返态,由定理 5,28 可知
1=ijf,即 jjij ll =,从而 L 具有形式 pT1,其中 =jp jjij ll =,
注 1 对于可数个状态的互通的常返 Markov 链,命题也成立,但是 p 未必是 P的不变测度,因为它 可能为零矩阵 (参见后面的 5,2 段 ),由定理 ５,４２ 可见 L 应该是以下的形式
=L
OMMM
L
L
0
0100
0010
0
2
2
1
1
21
21
)(
)(
)()(
p
p
pp
T
T
jijjij
H
H
ffT
HHT
注 2 (有限状态 Markov 链的 ijf 的计算 ) 由全概率公式可得下述递推关系
ijij
jk
n
kjik
n
ij pfnfpf =>= ∑
≠
)1()1()( ),1(,,
对 n 求和便得
∑
≠
+=
jk
ijkjikij pfpf,
记总状态数为 N,于是 TNjjj fff ),,( 1 L
= 是方程 =x P jj px +→ )0( 的解,其中 P )0( →j
117
为把 P中第 j 列改为零后所得的矩阵,而 jp 为 P的第 j 列列向量,这个方程的近似解可以用迭代方法求得,用这个方法可以在原则上估算被指定的吸收态所吸收的概率,例如说,
从 i 出发最终被吸收态 a 吸收的概率为 iaf,因此,上面的方程实际上是博采者输光概率的方程的一般化,
4,Dobrushin 不等式与 指数收敛性
研究 nP 的收敛性,比定理 5 。 ３９ 在理论与应用方面更为一般的是 Dobrushin 方法,它建立在 Dobrushin 不等式的基础上,对于无穷维行向量 ( 可取负值 ) =w ),,( 21 Lww,可以定义模
=|||| w ∑
j
jw ||
( 显见它满足三角不等式,|||||||||||| ~~ wwww +≤+ ),
4,1 Dobrushin 不等式
定理 5,４３ 对于概率分 布向量 vu,,我们有
(1) |||| vPuP? ∑ ∑ ≤?=
i
i
i
iii PCvpup )(||)||( |||| vu?,
其中
||||sup21)(,?=?= ∑
j
kjijki ppPC p?i p ||k,
称为转移密度的 Dobrushin 收缩系数,简称 Dobrushin 数,其 中 p i 是 P的第 i 行组成的行向量 。
(2) 对于转移矩阵 QP,有
)()()( QCPCPQC ≤ 。
证明 (1) 记数 a 的正部与负部分别为 +a 与?a,再分别记
/)( ±±?= jjj vur ||||21 vu?,
注意
∑∑ =?=+
j
jjjjjj
j
vuvuvu 0)(])()[(,
∑∑ =?=?++
j
jjjjjj
j
vuvuvu ||])()[( |||| vu?,
我们有
118
∑ +
j
jr ∑?=
j
jr ||||
2
vu?= ∑ =?
+
j
jj vu 1)(,
同时还有
)(21)()(?+?+?==? jjjjjjjj vuvuvu rr |||| vu?,
于是
∑ ∑
i
i
i
iii vpup ||)|| = ∑∑?
i
iiij
j
vup |)(|
||||21 vu?= ∑∑?+?
i
iiij
j
p |)(| rr ||||21 vu?= ∑∑∑?+?
i
kikjij
kj
pp |)(| rr
|||| vu?≤ ∑∑+
i
kjijki
k
pp |)|21(rr )(PC≤ |||| vu?,
今证 (2),记 P的第 i 行的行向量为 p i,则由定义及 (1) 得到
=)(PQC ∑ ∑∑?
j
ljkl
l
ljil
l
ki qpqp ||sup2
1
,
||sup21,ki= p i pQ? k ||Q
||)(sup21,QCki≤ p?i p ||k ||sup21,ki= )()( QCPC=,?
显见,对于 N 个状态的 Markov 链的转移矩阵 P 有
ijji pNPC,min1)(?≤,
4,2 Dobrushin 收敛定理
定理 5,４４ 若 1)( <PC,则存在不变分布 p,及 常数 0,10 ><< Ca,0n,使
)(,|)(| 0nnCnp n
j
jij ≥?<?∑ ap,
证明提示 对于任意概率分布向量 vu,,用 Dobrushin 不等式得
∑ ∑
i i
n
ii
n
ii pvpu ||||
)()( ∑?=
ji
iij
n
ij vupp
,
)( ||)(||
||)(|| )1()1(∑ ∑∑=
i i
i
n
iji
n
ij
j
j vpupp ∑ ∑≤
i i
i
n
iji
n
ij vpuppC ||||)(
)1()1(
≤≤ LL )(归纳地 npC ))(( |||| vu?,
用高等分析中完备距离空间的压缩映射原理 (全体向量在距离
=),( vud |||| vu?
下,组成完备距离空间,参见第 9 章第 3 节 ) 可知,存在 概率分布向量 p,对于任意概率分布向量 u,
都有
119
n
i
i
i pCnpu ))((||)(|| ≤∑ p |||| p?u,
取 u ),,( 21 Lkk pp=,2=C,)(PC=a,便得,对于任意 k 均有
n
j
n
kj
j
Cp ap ≤?+∑ || )1(,
[注 1] 定理 5,３９ 是定理 5.４４ 的特殊情形,这时有 11)( <?= dNPC,但是定理
5.３９ 更为直观,所以我们仍把它单独列出,细心的读者会看出,定理 5.４４ 恰是定理 5,
３９ 的发展与抽象化,
[注 2] 在实用中,定理 5.４４ 大多是适用的,
5,与常返态相系的延迟更新流,互通常返 Markov 链的极限定理
5.1 与常返态相系的延迟更新流
对于常返态 i,记 Markov 链首次到达 i 的时刻为 0T,以后各次返回 i 的时间间隔相继为
L21,TT
命题 ５,４５ }1:{ ≥nTn 独立同分布,而且与 0T 独立,
证明 利用 Markov 性及齐次性
))0(,,|)0(,,()|( 01 nkiimliiPnTmTP knlnmn <≤≠=<<≠==== ++ xxxx
)|)0(,,( imliiP nlnmn =<<≠== ++ xxx )|)0(,,( 0 imliiP lm =<<≠== xxx,
而上式右方与 0T 的取值无关,因此 1T 与 0T 独立,类似地可证明 }1:{ ≥nTn 独立,而且与 0T
独立,并且 }1:{ ≥nTn 同分布,?
从常返态 i 出发的互通的 Markov 链是一个再现过程,相 系更新间隔流 }0:{ ≥nTn,
由此生成一个延迟更新过程 )(itN,1T 的分布为?d 格点分布,其中 1≥d,我们不加证明地指出,在 2≥d 时,它就是 i 的周期,
5,2 互通常返链的极限定理
定理 5,４６ 设 )(inN 为互通的 Markov 链在 时刻 n 前返回常返状态 i 的频数,则其频率有极限
1)1(
)(
= →? ∞→
i
n
i
n
n
NP
m,
120
其中 ∑===
k
k
iii kfiTE
)(
01 )|( xm,而 }0:{ ≥nTn 为 常返状态 i 相系的延迟 更新间隔流,
证明 这是延迟更新定理的推论,
[ 注 ] 定理的结论也可以写成
i
nnii
n
II
m
xx 1)()( }{1}{ →?++ ∞→L
( 以概率为 1 成立 ),
定理 5,４７ 若 Markov 链的所有状态都是互通常返的,则对于任意 i 有
∑
=
∞→ ==
n
k j
k
ijnij pnl
1
)( 1)1lim(
m,
而且此时平均极限 L 的所有分量要么全为正,要么全为零,
证明 我们只对有限状态情形给出证明,因为一般状态情形需要测度论的工具,
用定理 5,４０ 我们得到
∑
=
∞→∞→ ==
n
k
n
k
ijnij Epnl
1
)( (lim1lim )|)()(
0
}{1}{ i
n
II njj =++ xxx L
∞→= nE(lim
i
njj i
n
II
mx
xx 1)|)()(
0
}{1}{ ==++L,
这里实际上用了取期望与求极限的交换性,在有限状态情形是没有问题的,而在一般情形则需要用测度论的工具,
再则,对于任意两个状态 ji,,由于它们常返互通,就必定存在 00,nm,使
0,)()( 00 >njimij pp
于是
∑++
=
∞→ ++=
00
1
)(
00
1lim nmn
k
k
ijnii pnmnl
∑
=
++
∞→=
n
k
knm
iin pn
1
)( 001lim
∑
=
∞→≥
n
k
n
ji
k
jj
m
ijn pppn
1
)()()( 001lim )()( 00 n
jijj
m
ij plp=,
又因为 ji,是对称的,所以它们是否为正是相同的,从而平均极限 L 的所有分量要么全为正,要么全为零,
推论 ５,４８ 若 Markov 链的所有状态都是互通正常返的,则 L 的所有分量全正,此时 pT1L =,其中 p 是 P 的唯一的不变测度 ; 而 若 Markov 链的所有状态都是互通零常返的,则 L 0=,
推论 5.49 Markov 链存在不变分布的充要条件为至少存在一个正常返类,在条件成立
121
下 Markov 链的一切不变分布可以表为它在各个正常返类上的不变分布 )(ip 们 的凸线性组合,
p ∑=
i
il
)(ip,∑ =≥
i
ii 1,0 ll,
证明提示 由 L 的形式立得充要条件,用较多的数学工具还可以证明不变分布的表示
( 因其涉及过多的技术细节,本书略去 ),
由推论 2 直接推出下述非常有用的互通正常返性判据,
定理 5,５０ (Markov 链的互通正常返性判据 )
（ 1 ） 对于互通或只有一个常返类的 Markov 链,那么此链为正常返的充要条件为存在唯一的不变分布,
（ 2 ） 无暂态的 Markov 链为互通正常返的充要条件为存在唯一的 不变分布,?
这个定理在判别 Markov 链的正常返性时非常有用,
[ 注 1] 当 Markov 链的所有状态都是互通正常返且非周期时,进一步有
∞→nlim
nP p== L T1,
此结论在实际中非常有用,它说明在时间发展充分长以后,不论初始值为什么,nP 的每一行都近似为 p,它可以用来作为稳态设计的根据,
再则,这个注也是一个非常一般的结论,大多数有关 ∞→nlim nP 存在的结果,都常由此引申而得,
[注 2] 对于正常返性的判别,还有一个充分条件,我们姑称之为,在有限集外的?e 盈函数条件,,近年来,它在多路通信的数学理论中,有不少应用,其叙述如下,
Foster 定理 （ 利用 Lyapunov 函数的正常返性判据 ）
若不可约,Markov 链 的转移矩阵 P )( ijp= 满足 即,存在状态空间上的非负函数 g (可取 ∞+ ),
0>C 及一个状态的有限集 F,满足
)()( Fijgp
j
ij ∈∞<∑,（ L,１ ）
)()()()( FiCigjgjp
j
ij≤?∑,（ L,２ ）
则此链为正常返的,再加上 非周期性,则进一步有
∞→nlim
nP =p T1,
又若 （ L,２ ） 改为
)10,)()()( <<≤∑ rr FiCigjgjp
j
ij （
（ L,２ ）＇
那么,此收敛还是指数收敛,
（ 直观地,函数 g 与常微分方程的稳定性理论中的 Lyapunov 函数起类似的作用,也称为 Markov 链的 Lyapunov 函数,第二个条件说明 h 函数 g 在沿 F 的余集中的状态运动时一致地减小 （ 经过一次转移后一致地减小了 ）,而由第一个条件,沿有限集 F 中状态运动时函数 g 的增加是一致地有界的,且由不可约
122
性,Markov 链终究会离开有限集 F,这样就使得在确定极限分布时,F 的作用可以在实际上忽略不计,
从而保证极限 分布的处在 ）,
定理的证明需要较多的鞅论知识,本书从略,
更重要的意义是此定理在连续时间的对应的推广形式,称为 Tweedle 定理,
定理 5,5 １ (遍历性定理 )
若 Markov 链的所有状态都是互通正常返的,f 是状态空间 S 上有界实值函数且满足
∑ ∞<μ
i i
if 1|)(|,则
∑ = →?++ ∞→
i i
nn if
n
ffP 1)1)()()(( 1
m
xx L,
即对于任意一个互通的 Markov 链及满足 ∑ ∞<μ
i i
if 1|)(| 的 f,以概率为 1 地有
pi →?ξ++ξ ∑∞→
)(0
)()()()( 1
对零常返链对正常返链
i
inn if
n
ff L,
其中 p = },,,{ 21 Lpp 是 P的不变分布,
i
i mp
1=,此极限与初分布无关,
证明 我们只对有限状态情形给出证明,因为一般状态情形需要测度论的工具,设状态数为 N,注意到 ∑
=
=
N
i
kik Iiff
1
}{ )()()( xx,于是由定理 5,４０ 得
∑∑∑
= ==
=
n
k
N
i
ki
n
k
k Iifnfn
1 1
}{
1
)()(1)(1 xx
∑∑ ∑
=
∞→
= =
→?=
N
i i
n
k
N
i
n
k
i ifInif
11 1
}{
1)()(1)(
mx ( 以概率为 1 成立 ),
[ 注 1] 有多个正常返类时,相应的极限仍然存在,但是依赖于初值的选取,
[ 注 ２ ] 若 Markov 链 )0,{ ≥nnx 的所有状态都是互通正常返,则不难证明
),( 1+?= nnn xxh 也是时齐的互通 Markov 链,其转移概率为 jlkjlkji pp δ=),(),,( （ 它不依赖 i ），
而且以 SSjiji ×∈),(),( ),(p 为唯一的不变分布,其中 ijiji ppp
=),(,而 p ),,( 21 Lpp= 是
Markov 链 )0:{ ≥nnx 的不变分布,由定理 5.５０ 推出 }0:{ ≥nnh 也是互通正常返 Markov
链,从而对于 SS × 上定义的函数 g,只要满足 ∑ ∞<pi
ji
iji pjig
,
|),(|,就 以概率为 1 地
123
有
→?ξξ++ξξ ∞→++ nnknk n gg ),(),( 11 L ∑ pi
ji
iji pjig
,
),(,
（ ),( 1+?= nnn xxh 的互通性证明如下,
设 ),(),,( lkji 为任意两个状态 。 如果 0=klp,则 ),( lk 是一个不可达到的状态,在本质上可以去除 。
所以我们不妨设 0>klp 。 由 nξ 的互通性,存在一条从 j 到 k 的通路 ； kjjj m =→→→ L1,
于是我们得到,),(),(),(),(),( 1211 lkkjjjjjji m →→→→→?L,这就得到了从 ),( ji 到
),( lk 的一条通路 ）,
[ 注 3] 一般地,涉及 Markov 链 )0:{ ≥nnx 的概率,由它的有 限维分布族确定,也就是由它的初始分布 m 与转移矩阵 P确定,但是,在得到注 2 的结论时,假定的条件只对 P作了要求,这正说明上面的结论与 Markov 链 )0:{ ≥nnx 的初始值 m 无关,这类与初始值无关的结论,正适合统计物理中稳态模型的要求 ( 与后面第 11 章的平稳序列理论相比较,当初始值为不变分布 p,即 iiP px == )( 0 时,)0:{ ≥nnx 为平稳序列,而且可以证明在我们的条件下,它具有所谓遍历性,于是利用平稳序列的遍历性定理,也可以得到上面的极限,
但这时须假定初始值服从不变分布,也就是说,从强有力的平稳序列理论,并不能得到这类与初始值无关的结论,由此可见 Markov 链理论的优点 ),
[ 注 4] 注 3 的结论还可以推广到 m 个变量的函数的情形,
[ 注 5] 对于互通 的正常返 Markov 链,不管它的初分布 m = )( 0?=xP 是什么,可以用 }{ nx
关于时间发展的平均来估计此 Markov 链的不变分布与转移矩阵,作法如下,分别取
)},{(}{,jii IgIf ==,则以概率为 1 地有
i
nnii
n
II pxx →?++ ∞→)()( }{1}{ L
,
)(),(),( )},{(11)},{( kpn II ijinnknjikji pxxxx →?++ ∞→++ L,
由此我们可得用一条轨道来估计 ip 与 ijp 的估计式,
=^ip n II nii )()( }{1}{ xx ++L,
124
=
^
ijp )()(
)()()()(
}{1}{
1}{}{2}{1}{
nii
njniji
II
IIII
xx
xxxx
++
++ +
L
L
,
此两式是对 ip 与 ijp 进行模拟计算的依据,
关于 Markov 链的数值计算,有以下的注意事项,
１,初始分布 0m,转移矩阵 P )( ijp= 的 Markov 链的样本,可以作如下的模拟,
(1) 取一个 0m 随机数 0i ;
(2) 取一个 )),,,((
000 1
LL jiii ppp = 随机数 1i ;
(3) 取一个
1i
p 随机数 2i ; …
那么 ),,,( 210 Liii 就是 Markov 链 ),,,( 210 Lxxx 的一个样本,
２,没有可逆分布情形时不变分布的近似算法 ( 参阅 [T])
假定状态空间为非负整数,且当 0mm ≥ 时,不变分布 p ),,( 10 Lpp= 满足
m
m Cap ≈,
那么
)( 000 mmmmmm ≥≈?app,
(1) a 的近似确定
此时不变分布的矩母函数 zzzz mmkk
m
k
+≈ ∑
= a
ppp 1 1)( 0
0
0 1
0
,所以,如果知道了不变分布的矩母函数 )( zp 近似地是一个有理函数,且它的分母只有一个大于 1 的根,那么此根的倒数就是 a,
(2) mppp,,,10 L 的确定
不变分布满足的方程可以改写为
=
1
0
0m
p
p
M A
0
0 1
0
m
m
p
p
p
M
,
11 0
0 1
0
=?+∑
= a
pp m
i
m
i
,
其中
A )0,10()( 00 mjmiaij ≤≤?≤≤=,
125
=
≤≤
=?∞
=
∑ )(
)10(
0
0
0
0
mjp
mjp
a
ki
mk
mk
ji
ij a,
6,停时与强 Markov 性
6,1 停时
定义 ５,５２ 非负且可取 ∞+ 的随机时刻 t,称为时齐的 Markov 链 )0:{ ≥nnx 的 停时,如果它是 }{ nx - 可 知的,即,对于 任意 n,事件 }{ n≤t 可由 Markov 链 }{ nx 在 n 前 的信 息 }:{ nmm ≤x 所决定,直观上说明停时 的发展是与 Markov 链的发展是,同步的,,
Markov 链首次到达状态空间的某一个子集合 A 的时刻 At,就是停时的典例,这是因为事件 )}(,,{}{
1
mkAAn km
n
m
A <?∈=≤
=
xxt U 只涉及 }{ nx 在 n 前的信息,
6.2 强 Markov 性
命题 ５,５３ 时齐的 Markov 链 )0:{ ≥nnx 具有 强 Markov 性,就是对于停时也有
Markov 性,即,对于任意停时 t 及任意状态 10,,,,?niiji L,在集合 }{ ∞<t 上,都有
),|( 1 前的信息在时刻 txxx tt?+ == ijP )|( 1 ijP === + tt xx )|( 01 ijP === xx,
( 证明提示 把条件概率写成联合概率除以条件的概率,再在计算其中每一个概率时,
对 t 的取值用全概率公式,然后分别用 Markov 性,即可证明,细节从略 ),
[注 ] 强 Markov 性也有与 Markov 性类似的相应的等价性叙述,请读者仿照 Markov 性的各种等价性叙述,把它们写出来,
7,禁忌概率与首达分布
7,1 禁忌 概率
定义 ５,５４ 由状态 i 出发,经 n 步到达状态 j,中间未到过状态集 A的概率,称为 禁忌 A的转移概率,记为 )(nijA p,即
)(n
ijA p ).|)0(,,( 0 inmAjP mn =<<?== xxx
7,2 首达时与首达分 布
定义 ５,５５ (首达时及其分布 )
设 A为一个状态集,随机时刻 }:0inf( An nA ∈≥=? xt 称为 首达 A的时刻 (对于空集 Φ,恒定义
126
∞=Φinf ),简称 A的首达时,
(注意首达时与击中时不同,击中时定义为 }:1inf( AnT nA ∈≥=? x,0=n 它在何处是不计入的 ),
定义 ５,５６ (首达分布 )
)|,( 0 ijP
AA
==∞< xxt t 作为状态 j 的概率函数,称为 A的首达分布,一般地,首达分布是 有亏损的分布,因为
===∞<∑
∈
)|,( 0 ijP
AA
Sj
xxt t 1)|( 0 ≤=∞< iP A xt,
而可能小与 １,只有当 1)|( 0 ==∞< iP A xt 时,首达 分布才是一个分布,
定义 ５,５７ (越出时 )
}:0inf{ An nA?≥=? xs
称为越出状态集 A的时刻,简称 A的越出时,它是 A的余集的首达时刻 ASA \st =,
7,3 禁忌概率,首达分布与平均首达时间
定理 5,５８
(1),
==>
∈====
)()|,(
)()|,(
0
0)(
AjijnP
AjijnPp
nA
nAn
ijA xxt
xxt
,
(2),把 P限制在状态集 A上,并记为 AP Ajiijp ∈=,)(,则对于任意 Aji?,有
()( =nijA p ASP \ ijn ),
(3) 对于 Ai 有
)|( 0 inP A => xt ASP \(= iTn )1 ∑
=
Aj
n
ijA p
)(,
(4),若 1)( =∞<AP t,则有
== )|( 0 iE A xt ∑
∞
=0n
ASP \(
n
i
T )1,
以上各式中的上标 n 是指 n 次方幂,
证明 (1) 显然,今用归纳法证明 (2),1=n 时恰是定义,设 n 时等式成立,1+n 时利用 Markov
性及归纳法假设得
),,( 1
\
)1( jknPp
n
ASk
nA
n
ijA ==>= +
∈
+ ∑ xxt
∑
∈
+ ===
ASk
nn
n
ikA kjPp
\
1
)( )|( xx
∑
∈
=
ASk \
ASP \ kj
n p (=
ASP \ ij
n )1+,
(3)的证明,
127
∑
∈
==>
ASj
n
ijAA pinp
\
)()|( xt
∑
∈
=
ASj \
( ASP \ ijn ) ASP \(= iTn )1,
最后证明 (4),当 1)( =∞<AP t 时,我们有
∑ ∑∞
=
∞
=
=>=====
1 0
000 )|()|()|(
k n
AAA inPikkPiE xtxtxt,
再用 (3),便得 (4),
定理 5,５９ 若 1)|(,0 ==∞<∈? iPBi B xs,则有
(1),BPI?( =?1)n ∑
∞
=0n
BP ∞<
n,
(2) B 的平均越出时间与越出分布有 表达公式,
E =?= )|( 0xs B 1)( BPI T1,
x(P
Bs
[)| 0 ∑
∈
===
Bk
ij x 1)( BPI kjik p],
证明 令
∈
∈=
)\(
)(~
BSi
Bipp
ij
ij
ij d,
那么定理 5,５８ 对于
~P
仍然成立,而对于转移矩阵为
~P
的 Markov 链来说,BS \ 中的状态都是吸收态,
由本定理的条件知道 B 中的状态都不是常返态,即全是暂态,故而
∑∑ ∈?∞<=
n
n
ij
n
n
ijBS Bjipp,,
)(~
)(
\,
于是由定理 5,５８ 的 (2)推出本定理的 （ 1）,(2)的第一式恰为定理 5,５８ 的 (4),而由定理 5,５８ 的 (1),有
x(P
Bs
=== )| 0 ij x ∑ ∑
≥ ≥
====
1 1
)(
\0 )|,(
n n
n
ijBSnB pijnP xxs,
再用定理 5,５８ 的 (2) 便得第二式,】
在 S 为有限集时,平均越出时间与越出分布可写成更为简单的公式,提供实用计算,
定理 5,６０ 对于有限状态 Markov 链,平均越出时间与越出分布可以用行列式表示,即 对任意 Bi∈
只要满足 1)|( 0 ==∞< iP B xs,那么,对任意 Bj ∈ 有
E =0|( xs B =)i ∑
∈Bk
ik
BD
BD
)(
)(,
x((P
Bs
=== ))| 0 ij x )( )( BD pBD kjik
Bk
∑
∈
,
128
其中 det)( =BD )( BPI?,)( BD jk 为 )(BD 的 ),( kj 处元素的代数余子式,
证明 把定理 ５,５９ 的 (2)中第一式用逆矩阵写出来就是 (1),类似地得到第二式,
8,可逆 Markov 链与可逆分布
一个用 Markov 链描述的 系统,常常可以利用它的长时间后的稳定分布,作为其参数的稳定设计的依据,在前面我们已经看到,在很宽的条件下,不变分布就是这个稳定分布,而求不变分布需要解一个方程,一般来说需要很大的工作量,所幸的是,在实际中有很多简单的网络系统常满足一个对称性条件,即所谓可逆性条件,对于这种 Markov 链,有一种求不变分布的简便方法,在本节中,我们将给出这方面的理论,
8,1 可逆 Markov 链
定义 ５,６１ 以 P 为转移矩阵的 Markov 链,称为 可逆的,如果存在概率分布
m ),,( 21 Lmm= 使
jijiji ppSji mm =∈?,,,
m 称为 可逆初分布,简称 可逆分布,在物理中,此条件称为 细致平衡 条件,
由此定义可以看出,可逆分布是唯一的,又可逆分布一定是不变分布,事实上,由可逆性的定义立得
∑ ∑ ==
i i
jjijiji pp mmm,
定义 ５,６２ 随机变量序列 nx 称为时间可逆 的,如果 对于任意时刻 0≥> nm,恒有
),,,( 1 mnn xxx L+ 与 ),,,( 1 nnm xxx +L 同分布,
例 ５,６３ 若取可逆 Markov 链的 可逆分布为 初始分布,即 )(,)( 0 SiiP i ∈?== mx,
则此 Markov 链是时间可逆的,
事实上,由初始分布是可逆分布得到
),,,( 11 mmnnnn iiiP === ++ xxx L
mmnnnnn iiiiiii
ppp
1211?+++
= Lm
mmnnnnn iiiiiii
ppp
12111?++++
= Lm
mmmnnnn iiiiiii
ppp m
1121?+++
= L
),,,( 11 nnnnmm iiiP ==== ++ xxx L,
命题 5,6４ 在初始分布 m 下,Markov 链是可逆的充要条件为,以 m 为初始分布的随机变量序列是时间可逆的,
证明 必要性已经证明,充分性得自,,Sji ∈?
=iji pm ),( 0 jiP i == xx ),( 0 ijP i === xx jij pm=,
推论 ５,６５ 细致平衡条件等价于,jin,,?,有 )()( njijniji pp mm =,
129
求可逆 Markov 链的不变分布 ( 就是可逆分布 ),与求一般 Markov 链的不变分布相比,要简单得多,所以,判别一个 Markov 链是否具有可逆性,在实际中是十分重要的,
再则,若 Markov 链具有不变分布 m,设 0S 是状态空间的一个子集,把 Markov 链限制在
0S 上,即对于 0,Sji ∈?,定义
∑
∈
=
0
0
Sk
ik
ijS
ij p
pp
,
=+ ≠= ∑
0
)(
)(~
Sk
ikii
ij
ij jipp
jip
p,
∑
∈
=
k
k
iS
i m
mm 0,
一般地,m 0S 不再是 P 0S 和
~P
的不变分布,但是,当 m 为 P的可逆分布时,m 0S 仍是 P 0S
和
~P
的可逆分布,这个性质称为 可逆初始分布关于状态子集的不变性,
8,2 例
例 ５,６６ {整数格点 Z 上的生灭链 }
设正数 ),2,1,0(,1,L±±=?= ipqp iii,
P
=
+=
==
)(0
)1(
)1(
),(
其它
ijq
ijp
pp i
i
ijij,
定义
<
=
>
=
∏
∏
+=?
= +
0
1 1
1
0 1~
)0(
)0(1
)0(
ik k
k
i
k k
k
i
ipq
i
iqp
m,
那么容易检查
jijiji ppSji
~~
,,mm =∈?,
于是只要 ip 们满足条件
∑∞
∞=
∞<
i
i
~
m,
再令
∑∞
∞=
=
j
j
i
i ~
~
m
mm,则 m ),,,,(
101 LL mmm?= 就是可逆分布,
130
例 ５,６７ 设转移矩阵为
=
2
10
2
1 2
1
2
10
02121
P,
我们来证明它不存在可逆分布,解方程 mm =P 得 P的不变分布为 )31,31,31(=m,而对于
2,1=i 有 061,111,≠=? +++ iiiiii pp mm,这说明 P没有可逆分布,
8,3 可逆初分布存在性判别法
定理 5,６８ ( Kolmogorov 可逆性准则 ) 状态数为 N 的互通的 Markov 链具有可逆分布的充要条件为,对于任意的一个状态环路 121,iiiiR m →→→→ L 恒成立下面的
(K) 条件,
(K)?= RR pp,
其中 Rp 是沿环路 R 的转移概率的积,即,
1121 iiiiiiR mmm pppp?
= L,
而?R 则是环路 R 的反向环路,
在 (K) 条件满足时,可逆分布是唯一的,而且可以求得如下,固定某个状态 0i,对于任意状态 i,任取一条从 0i 到的通路 iiiii mm =→→→→ +110 L,于是它满足
0
0 1
1 >=∏
=
+
+
m
k ii
ii
i
kk
kk
p
pv
,
定义
=+
≠+
=
∑
∑
≠
≠
)(1 1
)(1
0
0
0
0
iiv
iivv
ik
k
ik
k
i
im,
那么可逆分布为 m ),,,( 21 Nmmm L=,其中 iv 不依 0i 及通路的选取,
[注 ] 对于一般的可数状态 Markov 链,只要在 (K) 条件外加一个要求 ∑ ∞<
i
iv,则充要条件及可逆分布 m 的表达式仍然正确,可见本定理提供了得到 可逆分布 的简单方法,
证明 必要性,首先证明 im 们全为正,事实上,由于 m 是 可逆初分布,所以存在 0i
131
使 0
0
>im,再由链的互通性,对于任意 i,必有 n 使 0)(
0 >
n
iip,于是由可逆性条件立得 0>im,其次,任取通路 iiii n =→→→ +110 L,则我们有
iiiiiiiiiiiiii nn pppppp LL 2110121100 mm = iiiiiii nppp mLL 0201==,
特别地,当通路为闭的环路时有 ii =0,故得条件 (K),因此必要性成立,
充分性,首先证明,iv 们的定义与从 0i 到 i 的通路的具体取法无关,事实上,设有两条通路,,1R iiii n =→→→ +110 L 及,2R iiii m =→→→ +110 '' L,把沿通路 21,RR
定义的 iv 值分别记为 )1(iv 与 )2(iv,对于 21,RR 的反向环路 21,RR,考虑复合环路
12 RR o
(
0i 出发沿 1R 至 i 再沿 2R 的反向环路
2R 回到 0i ),由 (K) 条件可得
2112 RRRR
pp oo =,即
i
i
RR
RR
RR
RR
v
v
pp
pp
p
p
)2(
)1(
12
21
21
121 ===
o
o,
于是 )1(iv = )2(iv,从而 m 作为 v 的规一化也是唯一地确定的,最后证明 m 为可逆分布,事实上,对于任意的 ji,分两种情形考虑
(1),0>ijp 的情形,取 i 到 j 的通路 R,这时对于前面的通路 1R,由 (K) 条件得
0
11 >= RRRR pp oo,可见有 0>jip,进一步取 ji =0,那么 1),(,=≠= j
ij
ji
i vjip
pv
,
于是得 jijiji pvpv =,所以 m 是可逆分布,
(2),0=ijp 的情形,此时由情形 (1)知道必有 0=jip,从而 jijiji pvpv = 仍旧成立,
9,分支 Markov 链 (Galton - Watson 简单分支过程 )
Markov 链的应用非常广泛,它涉及物理,生物,化学,神经网络,信息,经济,金融等诸多领域,在各种应用模式中,由于实际问题往往是十分复杂的,如不对其进行适当的简化,不仅可能使问题因过于复杂而无法解决,而且也会使主要矛盾被枝节所掩盖而难以理解,
因而我们必须对许多实际问题进行必要的抽象和简化,以便理解其实质,于是,也就不可避免地会使问题可能与实际有一定的差距,所以,在读者应用 Markov 链去解决实际问题时,
还需具体问题具体分析,根据实际情况去作必要的变通,以灵活地应用各种 模型,
本节所要介绍的分支 Markov 链,主要关注的是群体灭绝的概率,这类问题来源于中子,
细胞或微生物等 ( 其中个体统一地称为粒子 ) 的分裂与死亡的随机现象,这里每一代的裂变
132
是各自独立地进行的,裂变后的粒子的总数决定了下一代粒子的总数的分布,
设 }1,:{,≥knknx 是一族相互独立同分布,而且取非负整数值的随机变量,它表示第 ｎ
代的第 ｋ 个粒子分裂成的粒子数 ( 假定在它分裂后自己就立刻死亡 ),0,=knx 就意味着此粒子不分裂而死亡,于是第 ｎ＋ １ 代的粒子总数是
nnn h
xxh,1,1 ++=++ L,
设开始是一个粒子,即 10 =h,我们说明 nh 是 Markov 链,事实上,利用独立性我们有
(),,|( 111 PiijP nnnn ====+ Lhhh j
nnn
=++ hxx,1,L ),,| 11 L == nnn ii hh
jP inn =++=,1,( xx L ),,| 11 L == nnn ii hh )(,1,jP inn =++= xx L
)(,11,1 jP i =++= xx L,
上式右方与 },,{ 2211 L == nnnn ii hh 及 n 无关,可见 nh 是时齐的 Markov 链,而且其转移概率为
)(,11,1 jPp iij =++= xx L,
现在我们来具体计算 ijp,为此令 )0()( 11,1 ≥=== kpkPp kk x,记 1,1x 的矩母函数为
k
k
k
zpzF ∑
∞
=
=
0
)(,
那么,利用幂级数的乘法规则,我们由数学归纳法得到 kik
k
i zpzF ∑
∞
=
=
0
)]([,于是
0|
)]([
!
1
== z
i
ik dz
zFd
kp ( 0,0 ≥> ki ),
此外,由模型的含义显然有 0,1 00,0 == kpp ( 0>k ),这就是说 0 是此 Markov 链的吸收状态,当过程达到状态 ０ 就不再有粒子了,分裂也就中止了,在这个模型中,我们首先感兴趣的量是此 M arkov 链被 0 吸收的概率,即灭绝概率,我们把它记为 r,即 )( 0 ∞<= TPr,
其中 0T 为 Markov 链 nh 首次达到 0 的时刻,
记 nh 的矩母函数为
k
n
k
n zkPzG )()(
0
== ∑
∞
=
h,
再一次由幂级数的乘法推出
133
k
n
k
n zkPzG )()( 1
0
1 == +
∞
=
+ ∑ h knnn
ik
ziPikP )()|( 1
00
==== +
∞
=
∞
=
∑∑ hhh
k
nik
ik
ziPp )(
00
== ∑∑
∞
=
∞
=
h in
i
zFiP )]()[(
0
== ∑
∞
=
h ))(( zFGn=,
即第 n 代的个体数的矩母函数是第 1 代的矩母函数的 n 次叠置,由此可以算出 nEh 与
)( nVar h 的递推公式,
现在我们来分别分析在什么条件下有 ρ ＝ １,ρ ＝ ０ 及 ０ ＜ ρ ＜ １,也就是什么条件下粒子概率为 1 地全 死光,永远不会死光,或既可能死光也可能不死光,最简单的情况是
00 =p 或 10 =p 的情形,它们分别代表粒子在下一个时刻不死亡与必然死亡,那么显然前者永不灭绝,而后者是必定灭绝,为避免这种平凡的情况我们假定 ０ ＜ ρ ＜ １,我们来求
ρ,记平均一个粒子的后代个数为 1,1xm E=,直观地可以猜测,若 μ ＞ １ 则不会全部灭绝,
而 μ ＜ １ 则会全部灭绝,为此,注意由于各个粒子的分裂是独立地进行的,所以有
)|( 10 kTP =∞< h kTP )1|( 10 =∞<= h kr=
于是由全概率公式推得
)( 0 ∞<= TPr )()|( 10
1
0 rh FkTPpp k
k
==∞<+= ∑
∞
=
,
可见 r 是函数 )( xF 在 ]1,0[ 中的不动点,也就是说 ρ 应为曲线 xy = 与曲线 )(xFy = 在中
]1,0[ 之交点的横坐标,显见 1=x 总是一个不动点,这是一个平凡的不动点,我们对此不感兴趣,而当 10 << x 时有
0)(' 1
1
>=?
∞
=
∑ nn
n
xnpxF,0)1()('' 2
2
≥?=?
∞
=
∑ nn
n
xpnnxF,
可见 )( xF 是递增的凸函数,于是 )( xF 是否在区间 (0,1) 中有不动点,就归结为 凸函数
xxF?)( 在 1=x 处的导数是正还是负,前一种情形说明当 ε ＞ ０ 充分小时,
01)1()1()1( =?< FF ee,因而由 0)0( 0 >= pF 与连续函数的中值定理得到,方程
xxF =)( 在区间 )1,0( 中有解,进而由 )( xF 的凸性就知道这个方程在区间 )1,0( 中解是唯一的,我们把它记为 0r,而后一种情形即 01)1(' ≤?F ( 也即 μ≤ １ ),此时由 )( xF 的凸性得到 xxF?)( 在区间 )1,0( 中恒负,所以这时方程 xxF =)( 在 [ ０,１ ] 中只可能有一个解,
134
1=x,从而在 1<m 时必然有 1=r,这说明最终将以概率为 1 地全部灭绝,而在 μ ＞ １ 时,
我们来证明 0rr = ( 而不可能是 1=r ),事实上
)(
0,1
)(
00
)(
0,1
1
)(
0,1
1
limlim nnknk
n
k
n
n
n
ppff ∞→?
=
∞→
∞
=
=== ∑∑r,
为了证明 0rr =,我们只需归纳地证明 0)(10 r≤np,首先,当 1=n 时有
000
)1(
0,1 )()0( rr =<== FFpp,
今作归纳法假设,设此不等式在 n 时成立,在 1+n 时由 )( xF 的递增性我们有
00
)(
0,1
)(
0,1
1
)(
0
)1(
1
1
)1(
0,1 )()()( rr =≤=== ∑∑ ∞
=
∞
=
+ FpFppppp nkn
k
k
n
kk
k
n,
综上所述得到以下结论
定理 ５,６９ 对于 Galton - Watson 简单分枝过程,设一个粒子的裂变分布列为
kpkP == )( 1,1x （ｋ＝ ０,１,… ）,且满足 10 0 << p,令 1,1xm E=,则在开始时有 i
个粒子时,全部粒子的灭绝概率为 ir,其中
>
≤=
)1(
)1(1
0 mr
mr,
而 0r 是方程 xxF =)( 的最小非负解,
此时第 n 代粒子数的平均规模为
)(
11
)1(
1
1
011 )1|(
n
jkj
jk
n
k
k
nn ppkkpE ∑∑∑ ∞
=
∞
=
+
∞
=
+
+ ==== hha
j
j
p∑
∞
=
=
1
)|( 0 jE n =hh j
j
p∑
∞
=
=
1
)1|( 0 =hhnjE nma=,
由于 10 =a,因而 nn ma =,可见当 μ ＜ １ 时,平均粒子数逐代单调下降趋于 0,当 μ ＝ １
时,各代粒子平均相同,而当 μ ＞ １ 时,平均粒子数按指数阶逐代上升至无穷,1=m 的情形称为临界情形,前面已经知道在 这种情形粒子最终必定灭绝,此时人们感兴趣的问题是平均灭绝时间多长,对此本书不再介绍,而 1>m 的情形,则称为上临界情形,
135
习题 ５
1,举例说明,如果集合 A包含不止一个状态,那么对于 Markov 链 }0:{ ≥nX n,下列等式不一定成立
)|(),,,|( 111001 AXjXPAXiXiXjXP nnnnnn ∈==∈=== ++ L,
2,设 nx 是以 {0,1,2} 为状态空间的 Markov 链,其转移矩阵为
3
1
3
1
3
1
122
212
aaa
aaa
,问
)(}2{ nn I xh = 是否为一个 Markov 过程? 如果回答,是,,则转移矩阵是什么?
3,设有数字 1,2,…,m,
(1),在其中任取一个数记为 0X,再在 1,2,…,1?nX )1( ≥n 中任取一个数记为 nX,证明
}0:{ ≥nX n 为 Markov 链,并求其转移矩阵,
(2),把它作一个随机排列,maa,,1 L,令 10 =X,)}(,min{ 1 ikaaXiX kinn <≥>=?,
min? 定义为 1+m,证明 10,,?mXX L 是一个以 }1,,1{ +mL 为状态空间的 Mar kov 链,求它的转移矩阵
4,连续地掷一枚均匀的硬币,如果第 n 次掷得正面,则令 0=nX ； 如果第 n 次掷得反面,且从第 n 次
往前看连续出现反面的数目为 k,则令 kX n =,约定 00 =X,证明 }0:{ ≥nX n 是 Markov 链,
并求其转移矩阵,
5,汽车单向地通过某路口,假设一秒钟可通过一辆汽车,路口的红灯 持续 r 秒,绿灯持续 g 秒,以,红灯 -
绿灯,的出现作为一个单元时间,在第 n 个单元开始时在等候的汽车数记为 1?nX,而把在这单元中来到的汽车数记为 nx,设 }1:{ ≥nnx 为独立同分布
+
+gr
n ppp
gr
L
L
10
10~x
,再假定在开始时刻路口没有汽车在等候,证明 }0:{ ≥nX n 是 Markov 链,并求其转移矩阵,
6,设 m 个人中的某些人已患流行性感冒,假定传染在两人间的接触中发生,当病人遇见健康者时,后者被
传染的概率为 p,一切成对的接触都是等可能的,而且在每个单位时间内只发生一次接触,记 nX 为时
刻 n 患病的人数,证明 nX 是 Markov 链,并求其转移矩阵,
7,设某水库容量为 c 立方米,在时刻 n 水库的储水量记为 nX,在时段 [n,n+1]内流入水库的水量记为 1+nx,
136
超过水库容量的水即溢出,假定在时段 [n,n+1]末从水库放掉 m（ <c） 立方米水 （ 其中包括库满而溢出的部分,如果溢出的水量已超过 m 立方米就不再放水 ）,假设 }1:{ ≥nnx 独立同分布且与 0X 独立,
0,)( ≥== kkP kn ax,证明 }0:{ ≥nX n 是 Markov 链,并求其转移矩阵,
8,设 1,0,=+> qpqp,若 Markov 链具有循环型的转移矩阵,
P
=
qp
pq
pq
pq
OO
,
证明
P
=
)(
1
)()(
2
)(
2
)(
1
)(
1
)(
)()(
1
)(
2
)(
1
nn
m
n
n
n
m
nn
m
n
m
n
m
nn
n
aaa
a
aaa
aaaa
L
OO
OOO
O
L
,
其中 nmnmnn pqaaa )(1)()(2)(1 www +=+++?L,而 w 为 1 的 m 次主复数根 (1 的其它复根都是它的幂 ),
9,证明有限状态 Markov 链的转移矩阵的特征值的 模都不大于 1,而且 1 总是特征值,
10,对于二值 Markov 链
P )1,0(,1 1 ≤≤
= ba
bb
aa
求 )(nijf 及 ∞→nlim Pn,
11,对下列各转移矩阵的状态进行分类,
=
1
1
1 2
1
2
1
1P,
=
2
1
4
1
4
1
2
1
2
1
2
1
2
12
1
2
1
2
1
2
1
2P,
=
3
2
3
1
3
2
3
1
3
0
0
001
P,
137
=
3
2
3
1
3
2
2
1
3
2
3
1
4
0
0
0
P,
=
0
0
0
3
2
3
1
3
2
3
1
3
2
3
1
5P,
=
OM
L
L
L
L
4
3
4
1
3
2
3
1 2
1
2
1
1
6P,
对 54,PP,6P 求 ijf,再记从状态 1 出发首次返回状态 1 的时间为 1t,求它的分布与期望,
1 2,设 Markov 链的转移矩阵为
=
100
0 4143
4
1
4
1
2
1
P,求 )3,2,1(,=if ii 及 nn P∞→lim,
13,若 出口商品用三状态表示,状态为 +1 表示今年比去年增长,状态 0 表示与去年持平,状态 –1 表示 今年比去年减少,过去的统计数据得到的状态间的转移矩阵为
+
+?
04.06.0
35.03.035.0
8.02.00
1
0
1
101
求各状态的平均返回时间和增长趋势与减少趋势的期望长度,
14,证明定理 5,３９ 是定理 5,４４ 的特例,
15,对于时齐的 M arkov 链 }0:{ ≥nnx,令 ),( 1+= nnn xxh,则 nh 也是时齐的 M arkov 链,在求 nh 的转移矩阵,
16 证明对于互通的有限 M arkov 链 }0:{ ≥nnx,以概率为 1 地有极限关系
∑ →?++ ∞→++
ji
iji
nnknk kpjig
n
gg
,
11 )(),(),(),( pxxxx L
17,设 }0:{ ≥nX n 是为正常返非周期的不可约 Markov 链,转移矩阵为 )( ijpP =,而 }0:{ ≥nnx 是
与 }0:{ ≥nX n 独立的独立同分布,随机变量列,)1(,)( ≥== kkP kn ax,令
nn xxhh ++== L10,0 1≥n,0,≥= nXY nn h,
则 }0:{ ≥nYn 为正常返不可约马尔可夫链,其转移矩阵为 ∑∞== 1~ k kk PaP,且它与 }0:{ ≥nX n
有相同的平稳分布,
18.,水库供水按其水位分为下列 5 个状态,1 表示危险水平,2 表示缺水,3 表示刚够,4 表示达到较好水平,5 表示充足,由统计已有数据得到其转移矩阵为
138
=
4.04.01.01.00
3.04.02.01.00
1.02.04.02.01.0
1.02.02.02.03.0
05.03.01.01.0
P,
求到出现危险水平的平均时间,
19,设 t 为 Markov 链 nx 的有限值停时,令 nn += txh,证明 nh 也是 Markov 链,求它的转移矩阵,再证明在已知 txh =0 的条件下,}{ nh 与 ),,,( 0 txxt L 条件独立,
20,设 }{ nx,}{ nh 相互独立,它们分别是独立同分布序列 ){ nX 与 }( nY 的部分和,
nn XX ++= L1x,)1(,
10~
11
≥
k
pqX k,nn YY ++= L1h,
)1(,10~
22
≥
k
pqYk,令 },1:min{ MnnT nn ±=?≥= hx,证明
（ 1） 若 21 pp >,则 MTT MP lhx +=?=? 1 1)(,其中
12
21
qp
qp=l；
（ 2） )1)(( )1(
21
M
M
pp
MET
l
l
+?
=,
21,设 }0:{ ≥nnx 独立同分布,
2
1
2
1
11
~nx,∑ = ≥== nk kn nSS 10 1,,0 x,
0,max
0
≥=
≤≤
nSM k
nkn
,证明 }0:{ ≥nSn 及 }0:{ ≥? nSM nn 都是 Markov 链,
22,假定 }1,{ ≥nnx 独立同分布,,)1(,)( ≥== kkP kn ax,对于 0≥n 定义
≥++<≤++
<=
+ 1,,
,0
111
1
knk
n
kk
n xxxx
xh
LL,∑ = =?=
n
j jn n
h xxV
0 0 )0(,,
证明 }0:{ ≥nnV 是常返的不可约 Markov 链,而且它是正常返的充要条件为 ∑∞= ∞<1k kka,
23,设 Markov 链 nx 有 N 个状态,而 i 为常返态,求证存在常数 q,0<q<1,使得当 Nn > 时,从状态 i
出发首次返回 i 的时间 it 满足 ni qinP <=> )|( 0xt,
24,证明对于状态空间为 S 的 Markov 链有
(1) 对于任意 Sji ∈,,有 ijij pf =)1(,)1(,)()1( ≥= ∑
≠
+ nfpf n
kjik
jk
n
ij,
139
(2) 在 j 固定时,}:{ Sif ij ∈? 是无穷个线性方程组 ∑
≠
+=
jk
ijkiki pxpx 以初值为
),0{ )0( Sixi ∈?= 的迭代解 ),0{ * Sixi ∈?=,即 )(,)(* Sixx ni
n
i ∈?= ∑,而
∑
≠
+ +=
jk
ij
n
kik
n
i pxpx
)()1(,
(3) 上面的迭代解 ),0{ * Sixi ∈?= 是方程 ∑
≠
+=
jk
ijkiki pxpx 的最小非负解,
25,设取值于非负整数的 Markov 链的状态为 },2,1,0{ L,转移矩阵为
=
OO
pq
pq
pqq
P
dd )1(
1
,
求吸收概率 1,0 ≥if i,
26,袋中有黑白两色的球共 m 个,每次从中随机地取出一个球后,放进一个不同色的球,令 nx 为取了 n
次后袋中的白球数,证明它是正常返不可约 Markov 链,并求其平稳分布,
27,有 m 个白球与 m 个黑球 混放在两个袋中,每个袋中各 m 个,在每个袋中各取出一个,互相交换后放
回袋中,令 nx 为交换了 n 次后在第一个袋中的白球数,证明它是正常返不可约 Markov 链,并求其平稳
分布,
28,若 Markov 链 nx 具有双随机的转移矩阵,即转移矩阵还满足 1=∑ ij
i
p,证明
(1) 如果状态只有有限个,那么它 们都是正常返的,
(2) 如果状态只有有限个,且链是不可约的,那么它具有均匀的平稳分布,
(3) 如果状态空间为无限,且链是不可约的,那么它不是正常返的,
29,设 Markov 链正常返不可约,其平稳分布为 (=p ),,10 Lpp,定义倒逆转移矩阵为
ji
i
j
ij pp p
p=^
,证明它也是不可约正常返的,
30,若 Markov 链 nx 的转移矩阵满足,存在非负数列 nu 及一个状态 k 使
∞<=∑? jkj
j
upd,)(,1 kiuup ijij
j
≠?≤∑,
(1) 作序列 jnij
i
n
iii upuuu
)()1()1(,∑== +,证明
)1()()2( 1)1( ++ +?+≤ n
i
n
ik
n
i upu d,
140
(2) 证明 )1(1 11
)2(
)(
1 n
up
n
im
ik
n
m
+≥∑
= d
,
(3) 如果 nx 还是不可约的,那么它是正常返的,
31,设 Markov 链的转移矩阵为
O
L
1
1
210 aaa
( 0,0 ≥> iai ),证明它是常返不可约,,而且它是正常返的充要条件为 ∞<= ∑
∞
=
n
n
na
1
m,在条件成立时平稳分布为 (=p ),,10 Lpp,其中
),1,0(1 L== ∑
∞
=
ian
in
i mp,
32,设 Markov 链的转移矩阵为
M
O2
11
00
1
1
q
qq
qq
( L,1,0,0 =∞<< iqi ),证明
(1) 它是非常返的 充要条件是 ∞<∑ i
i
q ;
(2) 它是正常返的充要条件是 ∞=∑ i
i
q,且 =m ∞<+?
∞
=
∑ )1()1(1 10
1
i
I
qq L,在条件成立时平稳分布为 (=p =),,,210 Lppp )),1)(1(,1,1(1 100 Lqqqm,
33,设 Markov 链的转移矩阵满足
),1,0,1,(0,0,0 1,1,LL?=>=≥=>= +? ipprpqp iiiiiiiii
给出具有平稳分 布的条件,并求出其平稳分布,
34,设 nx 是不可约的且具有平稳分布的 Markov 链,而 }{ nX 是与此 Markov 链独立的独立同分布随机序
列,且
LL
LL
k
n pp
k
1
1~x
,记
nXXn ++
= L
1
xh,证明 nh 也是不可约正常返 Markov
链,并求它的转移矩阵,再说明它与 nx 有相同的平稳分 布,
35,设
nnnn h
xxh,1,1 ++=+ L 为分支链,满足 )0()( 1,1 ≥== kpkP kx,
(1) 假定 1210 =++ ppp,证明此分支链以概率为 1 灭绝的充要条件为 20 pp ≥,
141
(2) 假定 13210 =+++ pppp,证明此分支链以概率为 1 灭绝的充要条件为 230 2 ppp +≥,
(3) 假定 13 =p,求此分支链以灭绝的概率,
(4) 假定 )10,10,1( rarkarp kk?≤<<<≥=,求此分支链以灭绝的概率,
(5) 假定 pppp =?= 10,1,求此分支链灭绝时间的分布,
龚光鲁,钱敏平著 应用随机过程教程及其在 算法与智能计算中的应用
清华大学出版社,2003
第 5 章 时间 离散 的 Markov 链
1 Markov 链的概念
1.1 定义与 Markov 性质
定义 ５,１ 随机过程可能取到的值 ( 状态 ) 组成的集合记为 S,称为随机过程的 状态
空间,随机序列 }0:{ ≥nnx 称为 Markov 链,如果这些随机变量都是离散的 (状态空间 S
至多是一个可数集,即 或者 S 是有限集,或者 S 可与自然数一一对应 ),而且对于 0≥?n
及任意状态 10,,,,?niiji L,都有
=====+ ),,,|( 00111 iiijP nnnn xxxx L )|( 1 ijP nn ==+ xx,(5,1)
这个性质称为 Markov 性质,
Markov 性的等价性质 1
若 A 为任意形如 })(.,,)(,)({ 111100 === nn iii wxwxwx L 的事件的并,即
U L
k
knnkk iiiA },,,{,11,11,00 ==== xxx
则有
)(),( 11 ijPiAjP nnnn ===== ++ xxxx,(5,2)
Markov 性的等价性质 2
进一步还可以证明 Markov 性等价于,对于过程在时刻 n+1 及其以后的时刻所确定的事件 B 及 等价性质 中之 A有
)(),( iBPiABP nn === xx,(5,3)
或
)()|()( iBPiAPiABP nnn ==== xxx (5,3)’
（ 5,3） 式 的含意为,如果过程在时刻 n 处于状态 i,那么不管它以前处于什么状态,过程以后处于什么状态的概率是一样的,这就说明了,Markov 链在 已知,现在,的条件下,,将来,与,过去,是条件独立的,我们把它另列为 一条性质 。
Markov 性的等价性质 3
在已知,现在,的条件下,,将来,与,过去,是条件独立的,
Markov 性的等价性质 4
对 Markov 链 }{ nx 及 0,1 ≥≥? nm 及任意状态 10,,,,?niiji L,有
=====+ ),,,|( 0011 iiijP nnnmn xxxx L )|( ijP nmn ==+ xx,(5,4)
97
证明 对 m 作归纳法,m=1 时即为 (5,1)式,设 m 时 (5,4)式正确,今证 m+1 时也正确,
),,,|( 00111 iiijP nnnmn ====++ xxxx L
),,,|,( 001111 iiikjP nnnnmn
k
======+++∑ xxxxx L
),,,,|( 001111 iiikjP nnnnmn
k
======+++∑ xxxxx L ×
),,,|( 00111 iiikP nnnn ====+ xxxx L,
利用归纳法假设及 (5,1)式,上式简化为
)|( 11 kjP nmn
k
=== +++∑ xx )|( 1 ikP nn ==+ xx
),|( 11 ikjP nnmn
k
==== +++∑ xxx )|( 1 ikP nn ==+ xx
)|,( 11 ikjP nnmn
k
==== +++∑ xxx )|,( 1 ijP nmn === ++ xx,
Markov 性的等价性质 5
对状态空间 S 上的任意有界实值函数 f 有
))((),,)(( 1001 nnnnnn ifEiifE ==== ++ xxxxx L 。 (5,5)
( (5,1) 式 是 (5,5)式的特例,即 )()( }{ xIxf j= 的情形,从 (5,1)式 推广为 (5,5)式 需要用测度论的基本知识,我们把它略去 ),
[注 ] 第 1,2,3,5 种等价性质都有与第 4 种等价性质 类似 的表达形式,请读者自检,
Markov 性的等价性质 6 （ 最一般的形式 ）
对于常见的实数集合 Λ,及由随机序列 mx 在时刻 n 及其后的信息所决定的随机变量
nh,恒有
)(),,( 00 nnnnnn iPiiP =Λ∈===Λ∈ xhxxh L
或
)()),,( 00 nnnnnn iEiiE ==== xhxxh L,
[注 ] 这个等价条件的内涵十分丰富,其等价性的证明在测度论中非常典型,本书从略,
在以实际问题 为背景的 Markov 链的研究中,人们 最 关心的是,经过时间 n,过程到达某些状态的概率有多大,以及需要多长时间才能到达这些状态,这类问题的描述首先涉及
Markov 链的转移特性 —— Markov 链的 n 步转移概率矩阵族,
１,２ 概率转移矩阵
定义 ５,２ 记
=),( mnpij,
并定义无穷矩阵
98
P )),((),( mnpmn ij=,
由于此无穷矩阵的分量都是非负的且不超过 1,易见这种无穷矩阵的乘法满足结合律,又因为
≠
===
)(0
)(1),(
ji
jinnp
ijij
D
d,(Kroneker 记号 )
所以 P =),( nn I (无穷单位矩阵 ),特别地,P )1,( +nn 称为时刻 n (到时刻 1+n )的 概率转移矩阵 而 P ),( knn + 就称为从 n 出发的 k 步概率转移矩阵,
命题 ５,３ 概率转移矩阵族满足以下 的性质
记 1 为分量全是 1 的无穷行向量 ( 矩阵 ),其维数与此 Markov 链的状态数一致,我们有
(P.1) 1),(0 ≤≤ mnpij,P ),( mn 1 T =1 T,( 上标 T 表示转置运算 )
(P.2) ( Chapman - Kolmogorov 方程 ) 对于 nml ≥≥? 有
P =),( ln P ),( mn P ),( lm,(5,6)
写成分量形式就是
∑=
k
kjikij lmpmnplnp ),(),(),(,(5,6)’
证明 验证 (P,1)
∑ ∑ ===
j j
nmij ijPmnp )|(),( xx,
U
j
nnm iPijP 1)|()|}{( ==?==== xxx 全集,
验证 (P,2)
∑∑ =====
k
mlnm
k
kjik kjPikPlmpmnp )|()|(),(),( xxxx
∑ ======
k
nmlnm ikjPikP ),|()|( xxxxx ∑ ====
k
nml ikjP )|,( xxx
U
k
nml ikjP )|},{( ==== xxx )|( ijP nl === xx,
１,３ 时齐的 Markov 链
定义 ５,４ Markov 链称为 时齐的,如果其概率转移阵 P )1,( +nn 与 n 无关 (即 1 步转移概率与出发时刻 n 无关,
我们把此矩阵简记为 P= )( ijp,由 (5,6)式得到
P =+ ),( mnn P )1,( +nn P L)2,1( ++ nn P =+?+ ),1( mnmn Pm
它也不依赖出发时刻 n,我们把它改记成 )(mP,( )( )()( mijm p=P ),其分量
)()( ijPp nmnmij === + xx 为 Markov 链 }0,{ ≥nnx 的 m 步转移概率,它也与出发时刻 n 无
99
关,于是 Chapman-Kolmogorov 方程的矩阵形式变为
)()()( nmnm PPP =+ (5,6)’’
而其分量形式为
∑=+
k
n
kj
m
ik
nm
ij ppp
)()()( (5,6)’’’
(其实 (5,6)’’式是显然的,因为它就是 P m + n = P m P n ),
以后在 本书中除非特别声明,我们所考虑的 Markov 链,均为 时 齐的 Markov 链,
对于时齐的 Markov 链 }0,{ ≥nnx,描述它的演化的最基本的量,就是它的转移概率矩阵 P= )( ijp,),,( Sjipij ∈,其中第 i 行就是给定 in =x 时,1+nx 的条件概率分布,
转移概率矩阵 P 是一个 随机矩阵,即它满足,
(1) P 中的元素均为非负,即 0≥ijp,
(2) P 中的每一行的元素之和均为 1,即 1=∑
j
ijp,
Markov 链的转移概率 },,{ Sjipij ∈ （ 或者说转移概率矩阵 P） 是刻 画 Markov 链的统计特征的基本量,事实上,一个 Markov 链可由其初始状态 0x 的统计性质 （ 即其初始分布
)( 0)0( iPi == xm ） 以及其转移概率矩阵 P 所完全确定,这就是 下面的定理 。
定理 5,５ （ M arkov 链的有限维分布 ） 若 Markov 链 }0,{ ≥nnx 的初始分布为
)( 0)0( iPi == xm,其转移概率矩阵为 P= )( ijp,则 }0,{ ≥nnx 的有限维分布为
SiiipppiiiP niiiiiiinn
nn ∈?====?,,,),,,( 10
)0(
1100 121100 LLL mxxx,
证明 由乘法公 式与 Markov 性得
),(),()()(
),,,(
00110022001100
1100
nnnn
nn
iiiPiiiPiiPiP
iiiP
==========
===
xxxxxxxxx
xxx
LL
L
nn iiiiiii ppp 121100
)0(
= Lm?
记 )()( iP nni == xm,它称为 Markov 链在 时刻 n 的绝对概率,再记由 )(nim 构成的行向量为 )(nm = ):( )( Sini ∈m,那么,我们有
定理 5,６ )( nm+m = )(mm )(nP,从而有 )(nm = )0(m nP
证明 ∑∑ ======= +++
i
n
ij
m
i
i
mmnmnm
nm
j piPijPjP
)()()( )()()( mxxxxm
= jnm )( )()( Pm,?
100
定理 ５,５ 与定理 ５,６ 说明 了 Markov 链的统计性质 （ 包括其长 时间极限行为 ）,完全可由其转移概率矩阵 P,以及它的初始分布 )0(m 所决定,因此,Markov 链的很多性质的研究就归结为随机矩阵的性质,
１,４ Markov 链的例
例 ５,７ （ 随机徘徊 ）
独立同分布的随机变量的 部分和序列,称为 随机徘徊,它是时间参数离散情形时的时齐的独立增量过程,又若其中的随机变量只取 １ 与 － １ 两个值,则称为 简单随机徘徊,
今考虑一个简单随机徘徊 }0,{ ≥nnx,其状态空间为 Z=S ={全体整数 },由 nx 的定义
∑
=
+=
n
k
kn Z
1
0xx,
其中 }0,{ ≥kZ k 为独立同分布随机变量序列,满足
pqZk
11~ )1( pq?=,
这里 nx 表示一个粒子每次分别以概率 p 与 q 向右与向左走一格,21=p 的情况称为 对称简单随机徘徊,由于随机徘徊是时齐的独立增量 过程,由第 3 章可知它也是时齐的 Markov 链,
又因为 nxxx L,,10 都是 nZZZ,,,10 L 的部分和,所以,它们和 1+nZ 独立,故
=
+=
=?===?==
==+====
++
++
其它0
1
1
)()(
)()(
11
11
ijq
ijp
ijZPiijZP
ijZPijPp
nnn
nnnnnij
x
xxxx
,
即其转移矩阵为
P = )( ijp =
LLLLLLL
MMMMMMM
MM
MM
MM
MMMMMMM
LLLLLLL
pq
pq
pq
000
000
000
,
而绝对概率为
≥?==
++
其它情形 ），
奇偶同与,且若，
(0
)()1()( 222 jnjnppCjP
jnjnjn
nnx,
事实上 )( jP n =x 就是,n 个相互独立的随机事件 }1{},...,1{},1{ 21 === nZZZ 中恰好有
101
2
jn + 个发生的概率 (
nx 要到达状态 j,所需的步数 n 不可能小于 j,故 jn ≥,设
+
nN
和?nN 分别表示在前 n 步中向右和向左的步 数,则显然有?+ += nn NNn,
+?=
nnn NNx,于是 ( )nn nN x+=
+
2
1,从而 ( )jnNj
nn +=?=
+
2
1x,又因为
( )nn nN x+=+2 是偶数,因此 n 与 nx 的奇偶性相同 ),对于初始状态为 i=0x 的简单随机徘徊,类似可得
≥?
=
===
++?+
其它情形 ）
奇偶同与,且若
(0
)()1(
)|(
222
0
)(
ijnijnppC
ijPp
ijnijnijn
n
n
n
ij xx
,
例 ５,８ (两端为反射壁的随机徘徊 ) 在例 ５,７ 中,如果在位置 a 与 b ( a<b ) 分别设置一个反射壁,即当粒子到达 a 与 b 时,下一步则以概率为 1 地分别,反射,到 1+a
与 1?b,此时粒子的运动仍然是一个 Markov 链,与例 ５,７ 不同处仅在于
).1(,0,1;)1(,0,1,1,,1,?≠==+≠==?+ bjppajpp jbbbjaaa
即其转移矩阵为
P = )( ijp =
01
000
000
000
10
LLLLL
MMMMMMM
MM
MM
MM
MMMMMMM
LLLLL
pq
pq
pq
,
读者可自行写出一端反射壁的随机徘徊的转移矩阵 P,
例 ５,９ (两端为吸收壁的随机徘徊 ) 若 Markov 链取值于 },,1,{ baa L+,且其转移矩阵为
P = )( ijp =
10
000
000
000
01
LLLLL
MMMMMMM
MM
MM
MM
MMMMMMM
LLLLL
pq
pq
pq
,
则称此 Markov 链为在 a 与 b 设有吸收壁的随机徘徊,即,1== bbaa pp,并称 a 与 b 为
102
Markov 链的 吸收态,
例 ５,１０ ( 货仓存货问题 )
设 一个运货仓库每月进货的件数是一个独立同分布的随机变量序列 },2,1:{ L=nnh,
其中 nh 表示第 n 个月进货的件数,
N
n pp
N
L
L
1
1~h,又设
0x?
NN
N
11
1
~ L
L
,仓库的货物容量为 N 件,每当仓库的货物超过 N 件时,就将 N 件打包发运,记第 n个月底的存货量为 nx,那么
1
1
1
1
≥
<
+
+=
nn
nn
nn
nn
n N
N
N xh
xh
hx
hxx 。
于是 }0::{ ≥nnx 是一个 Markov 链,事实上
≤===?+=
<<===?==
≥====?+
<<=====+=
=====
+
+
+
+
+
)(),,,|(
)(),,,|(
)(),,,|(
)(),,,,|(
),,,,(
11001
11001
11001
1111001
1111001
ijiiiijNP
NjiiiiijP
jiiiijNiP
NjiiiiijiP
iiiijP
nnnn
nnnn
nnnn
nnnn
nnnn
xxxh
xxxh
xxxh
xxxxh
xxxxx
L
L
L
L
L
,
≥?+=
<<?==
+
+
)()(
)()(
1
1
jiijNP
NjiijP
n
n
h
h
≥
<<=
+
)(
)(
jip
Njip
ijN
ij,
同样的推理 也 得到
)|( 01 ijP == xx
≥
<<=
+
)(
)(
jip
Njip
ijN
ij,
所以 }0,{ ≥nnx 是时齐的 Markov 链,且其转移矩阵的分量为
≥
<<=
+
)(
)(
jip
Njipp
ijN
ij
ij,
例 5,１１ ( 品牌选择 ) 设市场上销售 A,B,C,D 四种品牌的牙膏,根据市场调查,消费者购买哪一种品牌的牙膏,近似地仅与他前一次购买的品牌有关,而与这之前购买的品牌无关,记 0x 为某消费者最初所购买的牙膏的品牌,L,,21 xx 分别表示他在这之后 各次 所购买的牙膏的品牌,则 }0:{ ≥nnx 为一 Markov 链,其状态空间为 S={A,B,C,D},它的转移概率矩阵可以从市场调查中近似地获得,假定经过长期市场调查统计得到近似的转移矩阵为
103
P=
70.010.010.010.0
02.080.010.008.0
05.005.080.010.0
02.003.005.090.0
,
对于这个链,人们感兴趣的是这四种品牌的牙膏的市场占有率随时间进程的变化,
例 ５,１２ ( Wright-Fisher 遗传模型 ) 遗传的要素是染色体,遗传性质的携带者称为基因,它们位于染色体上,基因控制着生物的特征,它们是成对出现的,控制同一特征的不同基因称为等位基因,记这对等位基因为 A 和 a.,分别称为显性的与隐性的,在一个总体中基因 A 和 a 出现的频率称为基因频率,分别记为 p 和 p?1,设总体中的个体数为 2N,
每个个体的基因按 A 型基因的基因频率的大小,在下一代中转移成为 A 型基因,因此,繁殖出的第二代的基因型是由试验次数为 2N 的 Bernoulli试验所确定的,即如果在第 n 代母体中 A 型基 因出现了 i 次,而 a 型基因出现了 iN?2 次,则下一代出现 A 型基因的概率为
N
ip
i 2=,而出现 a 型基因的概率为 ip?1,记 nx 为第 n 代中携带 A 型基因的个体数,则易证 }0,{ ≥nnx 是一状态空间为 }2,,2,1,0{ NS L= 的时齐 Markov 链,其转移概率矩阵为
P= )( ijp,其中
jNjj
N
jN
i
j
i
j
Nnnij N
i
N
iCppCijPp
+?=?====
2
2
2
21 )21()2()1()( xx,
2,Markov 链的状态分类
2,1 首达分解,n 步转移概率的递推式,矩母函数,常返性
定义 ５,１３ （ 首次进入状态 j 的时刻 ） 把从 i 出发在 n )1(≥ 步转移中首次到达 j 的概率记为 )(nijf,用数学式表达即
)1(),1,2,1,,( 0)( ≥=?=≠== ninkjjPf knnij xxx L (5,7)
而把 Markov 链 }0,{ ≥nnx 首次 击中状态 j 的时刻 记为 jT,那么 jT 是一随机变量,但是与普通的随机变量有一点不同,就是它可以取值 ∞ （ 事实上,它 还 是一个 )( nx 停时,即它是否不大于 m,只由随机序列 nx 在时刻 m 前的信息完全确定 ）,即
∞
=≥=≥=
其它情形 ）
使得若存在
(
)1(}:1min{ jnjnT nn
j
xx,
从而 有
)1()( )(0 ≥=== nfinTP nijj x,
104
∑
∞
=
==∞=
1
)(
0 1)(
n
n
ijj fiTP x,,(5,8)
再记
∑∞
=
=
1
)(
n
n
ijij ff )|( 0 iTP j =+∞<= x 1)ii1n(P 0n ￡==?$= xx使得,(5,9)
那么 ijf 表示 }0n{ n?：x 从 i 出发,在有限时间内它能够到达 j 的概率 (或者说,从 i 出发最终转移到状态 j 的概率 ),
定义 ５,１４ （ 常返态与暂态 ） Markov 链 }0{?nn：x 的状态 i 称为 常返态,如
果 从 i 出发,能以概率为 1 地,最终又能回到 i,即 1=iif,如果状态 i 不是常返态,则称它为 暂态,
定理 5,１５ （ Markov 链的 首达分解定理 ） 对于任意状态 ji,,任意时刻 n,有
∑
=
= n
k
kn
jj
k
ij
n
ij pfp
1
)()()(,(5,10)
证明 利用 Markov 性质,我们有
=
=======
n
k
jnn
n
ij ikTjPijPp
1
0
)( ))|,()|(
０xxxx
∑∑
==
=========
n
k
k
ijkn
n
k
jjn fjjPikTPikTjP
1
)(
1
00 )|()|(),|( xxxxx,?
令
0,)0()0( == ijijij fp d,
并定义矩母函数
∑∞
=
=
0
)()(
k
nn
ijij zpzP,∑∞
=
=
0
)()(
k
nn
ijij zfzF,
易见定理 ５,１５ 可以写成如下的矩母函数形式
定理 5,１５ ’
)()()( zPzFzP jjijijij += d,(5,10) ’,?
从 （ ５,１０ ）＇ 可以解出
)(1
1)(
zFzP jjjj?=,(5,11)
)(1
)()(
zF
zFzF
jj
ij
ij?=,(5,12)
105
在 (5,11) 式中令 01?→z,便得到 ( 利用数学分析中的 Abel 定理 )
jjn
n
jj fp?=∑
∞
= 1
1
1
)(,（ ５,１１ ）＇
于是,由 常返性的定义立得如下的充要条件
定理 5,１６ （ 常返性与 暂 态的条件 ）
j 为 常返态? ∞=∑
∞
=1
)(
n
n
jjp ;
j 为暂 态? ∞<∑
∞
=1
)(
n
n
jjp,
推论 ５,１７ 状态 j 为暂 态,i ∞<∑
∞
=1
)(
n
n
ijp,从而 0lim
)( =
∞→
n
ijn p,
证明 右 ∞<= )1(ijF,
推论 ５,１８ (有限状态 Markov 链 ) 有限状态 Markov 链至少存在一个常返态,
证明 假设有限状态 Markov 链的所有状态均为暂态,那么由
∑ ∑
≤≤ ≤≤
∞→→====
Nj Nj
nn
ijn pijP
1 1
)(
0 0)|(1 xx,
这就导致了矛盾,
定义 ５,２０ 如果存在 0≥n,使 0)( >nijp,则称状态 i 可达 状态 j,记作 ji →,表示从状态 i 经过有限步的转移可以到达状态 j,它等价于,存在 11,,?nii L 使
,10,0
1
≤≤>
+
nkp
kkii
其中 jiii n ==,0,
注 （ Markov 链转移的图示 ） 把 Markov 链的状态记为顶点 。 如果 0>ijp,则从状态
i 到状态 j 画一条有向边,这样就得到表示 Markov 链的转移情况的一个有向图 （ 有些边可能是双向的 ）,那么,ji → 等价于存在顶点 i 到顶点 j 的一条由定向边组成的通路,
命题 5,２１ 设 ji → 且 ij → （ 记为 ji? ）,则状态 i 与 j 常返与否是相同的,
证明 由于 ji?,故存在 0,≥nm,使得 0,0 )()( >> njimij pp,记
0)()( >=
n
ji
m
ij ppa,
由 Chapman-Kolmogorov 方程可知,对任意非负整数 r,有
)()()()()( r
jj
n
ji
r
jj
m
ij
nrm
ii ppppp?=≥
++ a,
由对称性同样有
)()()()()( r
ii
m
ij
r
ii
n
ji
mrn
jj ppppp?=≥
++ a,
106
从而可知级数 ∑
r
r
iip
)( 与 ∑
r
r
jjp
)( 同时收敛或发散,故 ji,的常返与否是相同的
例 ５,２２ (二值链 )
P )1,0(1 1 <<
-
-= ba
bb
aa,
直观上可以想到状态 0 和 1 均是常返态,下面证明此结论,
利用归纳法我们可以得到
+?
++
+?== bb
aa
ba
ba
ab
ab
ba
n
nn
1)1(
)1(1
)(2
)1(
11
11
)(2
1)( PP,
故 nn babaababp )1()(2 1)(2 1)(00?++++=,
由于 1,0 << ba,就有 0)(2 1lim )(00 >+=
∞→ ba
bp n
n
,从而 ∞=∑
∞
=1
)(
00
n
np,故 0 为常返态,同样状态 1 也是常返态,
例 ５,２３ 在简单随机徘徊中考虑状态 0,此时
),2,1,0(0)12(00 L==+ np n,),2,1(2)2(00 L== nqpCp nnnnn,
用 Stirling 公式,!n ～ nn en?+ 212p （ 其中当 1lim =
∞→ n
n
n b
a 时,我们记
na ～ nb ）,我们可得
)2(
00
np ～
n
pq n
p
)4(,
因此 ∑
∞
=1
)(
00
n
np 收敛当且仅当 ∑
∞
=1
)4(
n
n
n
pq
p 收敛,又因为 14 ≤pq,且等号成立当且仅当
2
1== qp,于是 ∞=∑∞
=1
)(
00
n
np 当且仅当
2
1== qp,也就是说,当且只当在简单随机徘徊为对称时,状态 0 是常返的,
* 例 ５,２４ ( dZ 上的对称随机徘徊 ) 记 dZ 为 d 维整数格点组成的集合,每一个格点有 d 个方向,故各有 2d 个邻点,在 Markov 链已知处在某一 个格 点的条件下,以相同的条件概率 ( 即各以概率 d21 ),
在下一个时刻转移到它的任意一个邻点,这样的 Markov 链称为 dZ 上的对称随机徘 徊,显见各个点的常返性与暂态性是一样的,下面我们考察原点的情形,显然 0)12(00 =?np,
对于正整数 m,把 m 个不同的元素分成 l个组,使第 j 组恰有 jk 个元素 ( mkk l =++L1 ) 的不
107
同分法的数目记为 lkkmC,,1 L,那么,由归纳法可得 !! !
1
,,2
1
11
l
k
km
k
m
kk
m kk
mCCC l
LL
L ==
,于是
){(
1 1
)(
00 ∑
=++ =
=
nkk
d
i
i
n
d
kiPp
L
I 步 ）各走个坐标方向两侧独立地向第
∑
=++
=
nkk
nkkkk
n
d
dd
dCL
L
1
11 2,,,,
2 )2
1( ∑
=++
=
nkk
n
dd dkk
n
L L1
2
22
1
)21()!()!( )!2(
∑
=++
=
nkk
n
kk
n
n
nn
d
d
dCC L
L
1
1 2,,
22 ]
1[
2
1
,
这样,当 2=d 时,用 nn
nk
knk
n CC 2
2,][ =
￡
- 及 Stirling 公式,我们有
nCp nnnn?≈= p 1)(41 222)(00,
而当 3≥d 时我们利用下面的 引理,
引理 ５,２５ 在 ∞→n 时 有近似关系
d
n
d
n
n
kk
n
nk
CC dd
i
i
,,,,
1
1
max LL ≈
∑
=
=
,nC nnn?≈ p121 22,?
( 此引理可用 Stirling 公式证明 ),
利用引理 ５,２５,就得到
n
nnn
n C
dp 22
)(
00
1
2
1≤ ][max,,1
1
d
d
i
i
kk
n
nk
C L
∑
=
=
d
n
d
n
nn Cnd
,,11 L
p≈
dd
n
d
n
nn
n
d
ne
d
n
nen
nd ]2)[(
21
p
p
p?
≈
2
1
d
n
常数≈,
可见
∑∞
=?
≥∞<
≤∞=
0
)(
00 )3(
)2(
n
n
d
dp
,
即,对于 dZ 上的对称 简单 随机徘徊,当 2≤d 时,一切状态都是常返态,而当 3≥d 时,一切状态都是暂态,这个结论在直观上是很清楚的,在 d 大时,能去的地方多了,回返的可能性就小了,
因为常返态能以概率为 1 地返回,直观地看,从常 返态 i 能到达的状态 j,必须以概率为 1
返回 i,而返回 i 后又可达 j,看来似乎 j 总能返回自己,即 j 也应是常返态,另一方面,常返态既能以概率为 1 地返回一次,就能返回第二次,…,从而能返回 ∞ 次,即若状态 i 为常返态,则 Markov 链无穷次返回状态 i 的概率为 1,而若状态 j 为暂态,则 Markov 链以正概率不能返回,从而无穷次返回状态 j 的概率为 0,下段将致力于证明这两个结论,
2,2 常返性再访与 Markov 链的基本结构
设随机变量 jh 表示 Markov 链 nx 访问状态 j 的次数,即把 nx 作为下标 1≥n 的随机序
108
列时,在此序列中总共取到状态 j 的次数 (若在此序列中 j 被取到了 ∞ 次,则我们认为
∞=jh,所以 jh 是一个可以取值 ∞ 的非负整值随机变量 ),按定 义就有
)1( 0 iPf jij =≥= xh,
定理 5,２６
(1) 若 j 为常返态,则
)()( 0 SifiP ijj ∈?==∞= xh,
特别 是 在 ji = 时,有 1)( 0 ==∞= jP j xh,
(2) 若 j 为暂态,则 )(1)( 0 SiffiE
jj
ij
j ∈==xh,
证明 （ 1） 按 jT 取值的不同,把要考虑的事件划分为互不相容的事件之并,利用 Markov
性及全概 率 公式,我们得到
∑∞
=
====≥==≥
1
000 )(),()(
k
jjjj ikTPikTnPinP xxhxh
∑∞
=
===<≠=≥=
1
00 )()),(,,(
k
jlkj ikTPikljjnP xxxxh
)1()()1(
)()1()()(
0
1
00
1
00
1
0
jnPfikTPjnP
ikTPjnPikTPjnP
jij
k
jj
k
jj
k
jkj
=?≥====?≥=
===?≥====≥=
∑
∑∑
∞
=
∞
=
∞
=
xhxxh
xxhxxh
反复使用上式,就可推出
1
0
2
0 ][)1(][)(
==≥==≥ n
jjijj
n
jjijj ffjPffinP xhxh )1( ≥n,
由于 j 为常返态,即 1=jjf,令 ∞→n 就得到
SifiP ijj ∈?==∞= )( 0xh
（ 2） 由于 jh 为非负整值随机变量,与普通的期望类似地有条件期望公式
∑∞
=
=≥==
1
00 )()(
n
jj inPiE xhxh,
故由 （ 1） 中的推导及 1<jjf (因为假定暂态 j 为暂态 ) 可推出
109
SiffffiE
jj
ij
n
n
jjijj ∈=== ∑∞
=
1][)( 1
1
0xh,
推论 ５,２７ (常返与暂态的另一个等价条件 )
(1) 状态 j 为常返态,当且仅当,1)( 0 ==∞= jP j xh ；
(2) 状态 j 为暂态,当且仅当,0)( 0 ==∞= jP j xh,
证 (2) 由定理 5,２６ 得
==∞= 0)( 0 jP j xh 1)( 0 ≠?∞<= jjj fjE xh,即 j 为暂态,
[注 1] 这个推论就是说,在条件概率 )|( 0 jP =? x 下,事件 ∞=jh 的条件概率只能为
0 或 1,也称为对于 此事件 ＂ 条件 0 - 1 律 ＂ 成立,
[注 2] 推论 ５,２７ 清楚地说明了常返态与暂态的含义,对于 Markov 链,常返态是由 它出发能 ∞ 次返回的状态,而随着时间的发展,暂态将逐渐消失,所以,在对用 Markov 链描述的模型作稳态设计时,暂态是不予考虑的,这正说明了为什么区分常返态与暂态是十分重要的,
定理 5,２８ 若 i 常返,且 ji →,则 1== jjji ff,从而 j 也常返,
证明 记 0inf )(0 >= mijm pm,由于 i 为常返态,故
)|(1 0 iP i =∞== xh
)|,( 0
00
iinjP nmm ==∞== + xxx 使个有 )|,( 0
00
iinjP nmm ==∞≠+ + xxx 使个有
)|,( 0
00
iinjP nmm ==∞=≤ + xxx 使个有 )|( 0
0
ijP m =≠+ xx
)1()|( )(0)( 00 mijimij pjTPp?+=∞<≤ x
Pp mij= 1(1 )( 0 ))|( 0 jTi =∞< x 1≤,
因此
1)|( 0 ==∞<= jTPf iji x,
于是存在 n 使 0)( >njif,从而 0)()( >≥ njinji fp,即 ij →,由命题 5,２１ 得 j 的常返性,
上面得到的关于状态为常返 （ 或暂态 ） 的条件,从概念的含义看是很清楚的,但是很难用于实际判断,比较起来,用 命题 ５,１６ 来判断状态 j 是否常返 常 更为可行,
[注 ] (∑
∞
=1
)(
n
n
jjp 的概率含义 ) 记
==
其它情形 ）
若
(0
)(1)(
}{
jI n
nj
xx,
110
那么 ∑
∞
=
=
1
}{ )(
n
njj I xh,因此
∑∑
∞
=
∞
=
===
1
0
1
)( )(
n
n
n
n
jj jjPp xx )())(( 0
1
0}{ iEiIE j
n
nj ==== ∑∞
=
xhxx,
Markov 链的基本结构
定义 ５,２８ （ 状态的互通性 ） 两个互相可达的 ji,称为是 互通的,记为 ji?,
命题 5,２９ 在常返态间,互通性是等价关系,即它满足
（ １ ） 自反性,ii? ；
（ ２ ） 对称性,若 ji?,则 ji? ；
（ ３ ） 传递性,若 ji?,且 kj?,则 ki?,
证明 我们只须证明传递性,设 ji?,则存在整数 n,使得 0)( >nijp,又由于
kj?,故存在整数 m,使得 0)( >mjkp,因此 由 Chapman-Kolmogorov 方程得到
0)()()()()( >≥= ∑
∈
+ m
jk
n
ij
Sr
m
rk
n
ir
nm
ik ppppp,
故 ki →,同理可证,ik →,从而有 ki?,
注 与多数课本不同的是,在本书中我们 只对常返态考虑等价性,原因在于对于暂态果 i 不可能有 ii →,也就是说,只在常返态间,互通性才是自返的,即 ii →,只有此时它才可能是一个数学上的等价关系,
Markov 链的状态,除暂态外,可利用互通这个等价关系划分成不同的等价类,即把互通的常返状态归入同一类中,称为一个 常返类,而把所有的暂态状态,通通放到一个,另类,
中,不再加以细分,单个状态 k 是一个常返类的充要要条 件为,1=kkp,此时 k 为 吸收态,
定义 ５,３０ (状态闭集与不可约性 )
状态的集合 A 称为 闭集,如果对于任意状态 Ai∈,满足 ∑
∈
=
Aj
ijp 1,显见状态空间 (即全体状态 ) 是一个闭集,如果除此以外再也没有其它非空闭集,则称此 Markov 链为 不可约的,
显见,一个常 返类是闭集,而且它不含更小的闭集,
简单随机徘徊的所有状态都在同一等价类,故它是 一 个 不可约 Markov 链,而两端为 0
和 N 的吸收壁随机徘徊,吸收状态 0 和 N 分别都是一个单点常返类,它们是仅有的真闭集 (即除状态空间以外的闭集 ),此 Markov 链是 可约的,
命题 5,３ １ （ 状态分解定理 ） （ １ ） Markov 链的状态空间 S 可唯一分解为,
LUUU 21 HHTS =,
其中 T 为暂态的全体,而 iH 为等价常返类,
（ ２ ） 若 Markov 链的初分布集中在某个常返类 kH 上,则此 Markov 链概率为 1 地永远在此常返类中,也就是说,它也可以看成状态空间为 kH 的不可约 Markov 链,
111
所有的状态全是常返态的链称为 常返链 ； 没有常返态的链称为 暂态链,简单随机徘徊当
2
1== qp 时 （ 即对称 的简单 随机徘徊 ）,是一个常返链 ； 而当 qp ≠ 时,是暂态链,dZ 上的对称 的简单 随机徘徊当 2≤d 时,是一个常返链 ； 而当 3≥d 时,是暂态链,
１,３ 平均回访时间与正常返性
我们将用平均回访时间是否有限,来对常返态作进一步的区分,
定义 ５,３２ （ 平均回访时间 ） 对于 Markov 链 首达 i 的时刻 iT,记
)( 0 iTE ii == xm,
则 im 表示状态 i 的 平均回访时间,iT 是一个可取 ∞ 的广义整值随机变量,它的分布表为
∞
iiiiii fff 1
21
)2()1( L
L,
当 i 为暂态时,因为 1<iif,所以 ∞=im ; 而在 i 为常返时则有
∑∑
∞
=
∞
=
====
1
)(
1
0 )(
n
n
ii
i
ii nfinTnP xm,
于是利用 im 我们可以对 常返态作进一步的区分如下
定义 ５,３３ 常返态 i 称为 零常返的 ( 简称 零态 ),如果 ∞=im ； 否则称为 正常返的,
（ 从 后面的定理 ５,４７,可以知道 有限状态 Markov 链的任何常返态必定是正常返的,
可见,零常返只能出现在可数状态 Markov 链的情形 ）,
我们还要引入一种特殊的,而 且 在物理中占重要地位的 一种 正常返态,称为 遍历态 。 为此我们先介绍周期的概念,
定义 ５,３４ （ 状态 的 周期 ） 将 满足 0)( >niip 的所有 1≥n 的整数的最大公约数记成
id,(如果对所有 1≥n 都有 0
)( =n
iip,则约定 ∞=id ),1=id 或 ∞ 的状态,称为 非周期的,1>id 的状态称为 周期的,
由周期的定义立即可知,若 n 不能被 id 整除,则必有 0)( =niip 。
定义 ５,３５ 正常返的非周期状态称为 遍历态,
例 ５,２２ （ 续 ） 例 ５,２２ 中的 两个状态均为正常返的,又由于 0)1( >iip （ i=0,1）,
即 1=id （ i=0,1）,故此 Markov 链的状态 0 和 1 均为遍历态,
读者可自行验证下面的定理,
定理 5,３６ 设 ji?,则
112
（ 1） i 为常返态,当且仅当 j 为常返态,
（ 2） i 为暂态,当且仅当 j 为暂态,
（ 3） i 为零常返态,当且仅当 j 为零常返态,
（ 4） i 为正常返态,当且仅当 j 为正常返态,
（ 5） i 为遍历态,当且仅当 j 为遍历态,
[注 ] 事实上,此时我们还有,状态 i 为周期态,当且仅当 j 为周期态,且 ji dd = 。 其证明方法是用初等数论,本书略去,
以上结论说明,零常返,正常返,周期大小,遍历,都是常返等价类的,类性质,,它们对同一 个等价类中的状态都是相同的,
3,Markov 链的转移概率的极限与不变分布
3,1 不变分布与平稳 Markov 链
定义 ５,３７ 状态空间 S 上的概率分布 p = },,{ 21 Lpp 称为 P 的 不变概率分布,简称
不变分布,如果 Ppp =,
不变分布未必存在,若状态空间 S 为有限集,且不变分布存在,则 1 是矩阵 P 的左特征值,而不变分布 p 是它的左特征向量,此时 p 可由代数方程组
Ppp =,p T1 =1
的非负解得到,其中 =1 )1,,1( L （ 上标的 T 表示取转置 ）,
命题 5,３８ 若转移矩阵为 P 的 Markov 链 }0n,{ n ≥x 的初始分布取为不变分布 p,
则 }0n,{ n ≥x 为平稳列,即对于 k1 n,,n,k,n L?,},,( nnnn
k1 ++
xx L 与 },,(
k1 nn
xx L 有相同的联合分布,(关于平稳列的一般理论可参见第 11 章 ),
(请自行验证 ),
3,2 有限状态 Markov 链的的不变分布与极限分布
定理 5,３９ 若 Markov 链 }0,{ ≥nnx 的状态空间 S 为有限集 （ 不妨设
},,2,1{ NS L= ）,且其转移概率 矩阵 P = )( ijp 满足 Sjipij ∈?>,0,则存在 S 上唯一的概率分布 p = },,,{ 21 Nppp L,使得对所有 Sji ∈,及 NSjipij 1),:min( ≤∈=d,都有,
（ 1） Ppp = (即 p 为 P 的不变概率分布 ),而且 dp ≥j ;
（ 2） ∞→nlim nP =p T1,
此外,P 还满足 指数遍历性,即
n
j
n
ij Np )1(
)( dp?≤?,
[注 ] (2 ) 远比 (1) 强,
113
证明 记 )(njM 与 )(njm 分别为矩阵 nP 的第 j 列的最大与最小值,显然
dd )1(11),:min(≤?=≤∈≡ ∑
≠
NppSjip
jk
ikijij,
因此
N
1≤d,d≥)1(
jm,d)1(1
)1(≤ NM
j,
进而
ddd NNmM jj?=≤? 1)1(1)1()1(,（ E.1）
再则,我们有
)()()()1()1( maxmaxmax nj
k
n
jiki
k
n
kjiki
n
iji
n
j MMppppM =≤== ∑∑++,
类似地
)()()()1()1( minminmin nj
k
n
jiki
k
n
kjiki
n
iji
n
j mmppppm =≥== ∑∑++
这说明 )(njM 是单调下降的,而 )(njm 是单调上升的,我们将证明
)(0)1(0 )()( ∞→→?≤?≤ nNmM nnjnj d,（ E.2）
只要证明了 （ E.2）,就由它可以推出,当 ∞→n 时,nP 的第 j 列的各分量与 )(njM 及 )(njm
有相同的极限 （ 令 )(lim nj
nj
M
∞→
≡p,则由 )()()()()( njnjjnijnjnj mMpMm?≤?≤? p,直接导出 jnj
n
p p=
∞→
)(lim ）,从而有
∑∑
∈∈∞→
+
∞→
===
Sk
kjk
Sk
kj
n
ikn
n
ijnj pppp pp
)()1( limlim
可见为了证明 (1),只须证明 （ E.2）,现在我们证明 （ E.2）,注意
∑ ∑∑?=?=? ++
k k
n
kjkiik
n
kjki
k
n
kjik
n
ji
n
ij ppppppppp
)(
*
)(
*
)()1(
*
)1( )(
∑∑
∈∈
+?=
*
)(
*
)(
* )()(
Jk
n
kjkiik
Jk
n
kjkiik pppppp,
其中 }:{ * jiij ppSjJ >∈=,}:{* *jiij ppSjJ ≤∈=,由于
∑
∈
Jj
jiij pp )( * + ∑
∈
*
* )(
Jj
jiij pp = 011)( * =?=?∑
∈Sj
jiij pp,
故而
∑
∈
*
* )(
Jj
jiij pp = ∑
∈
Jj
jiij pp )( *,
并且
dNpppppp
Jj
ji
Jj
ij
Jj
ji
Jj
ij
Jj
jiij?≤=?=? ∑∑∑∑∑
∈∈∈∈∈
11)( *
*
**,
从而
114
∑∑
∈∈
++?+?≤?
*
)(
*
)(
*
)1(
*
)1( )()(
Jk
n
kjkiik
Jk
n
kjkiik
n
ji
n
ij mppMpppp
∑
∈
=
Jk
kiik
n
j
n
j ppmM )()( *
)()( ))(1( )()( n
j
n
j mMN≤ d,（ E.3）
若选取 i,i * 满足 )1()1( ++ = njnij Mp,)1()1(* ++ = njnji mp,则由 （ E.3） 得
))(1( )()()1()1( njnjnjnj mMNmM≤? ++ d,（ E.4）
这样迭代多次,再利用 （ E.4） 便得 （ E.2）,
最后我们证明不变分布是唯一的,设 m ＝ },,,{ 2,1 nmmm L 是 P 的另一个不变分布,
则有
ppmpmmmmm ==fi=== )()( TTn2 11PPP L,
例 ５,２２ （ 续 ）
P =
bb
aa
1
1 （ 0<a,b<1）。
这时定理 5,３９ 条件满足,故不变分布 p = },{ 10 pp 存在唯一,且应满足下列方程
( ) 1),,(1 1,101010 =+=
pppppp
bb
aa 。
容易解得
)(2
1,
)(2
1
10 ba
a
ba
b
+?
=
+?
= pp 。
这里我们并不需要知道 nP 的形式,
例 ５,１１ （ 续 ） 在牙膏品牌的市场占有率的例子里,Markov 链 }0,{ ≥nnx 的所有状态均为遍历态,所以它存在唯一的不变分布 p = },,,{ 4321 pppp,且满足 p P =p,即
14321 1.008.01.09.0 ppppp =+++,
24321 1.01.08.005.0 ppppp =+++,
34321 1.08.005.003.0 ppppp =+++,
44321 7.002.005.002.0 ppppp =+++,
14321 =+++ pppp,
可以求出
115
p = }086.0,179.0,253.0,482.0{
可见,随着时间的推移,厂家 A,B,C,D 的市场占有率将分别变为 48.2%,25.3%,17.9%和
8.6%,
[注 ] 定理 5,３９ 的条件对于不变分布的存在唯一性来说太强,事实上,我们有
（ 1） 有限状态的 Markov 链只要是互通的,（ 即全体状态组成一个互通常返类 ）,它一定存在唯一的不变分布,例如,两端反射壁的随机徘徊,它不是一步互通的,nP 也没有极限,
但是它仍有唯一的不变分布,
（ ２ ） 我们将在第 5 节 中得到,可数状 态的只有正常返态的 Markov 链,一定存在不变分布,又若此链还是互通的,那么不变分布还是唯一的 （ 但是此时 nP 未必有极限 ),
3,3 转移矩阵的平均极限
在 ∞→n 时,一般地 nP 未必有极限,例如对于
=
01
10P,有 PP n =+12,IP n =2,
极限不存在的原因在于 nP 有周期性,消除周期性的办法是代之以求平均极限
n
1lim
n ∞→ )(
1?+++ nPPI L,对于可数状态的 Markov 链,虽然可以证明这个极限一定存在,但是,在本书中我们只对有限状态情形给出证明,
定理 5,４０ （ 有限状态情形的平均极限定理 ） 设 P为 NN× 转移矩阵,则
n
1lim
n ∞→ )(
1?+++ nPPI L
存在,把它记为 L )l( ij=,则它满足
2LLPLLP ===,
证明 记
L ( ) ==
)n(l(n) ij n1 )( 2 nPPP ++ L,
显见 )n(lij 是取值于 [0,1]的序列,所以存在公共子列 kn,使对于任意 Nji ≤,，
ijij lnl 某个→)(,于是
L )n( k P
kn
1= ∑
=
+k
n
m
mP
1
1
kn
1= )( 1
1
PPP k
k nn
m
m?+ +
=
∑ L→,
从而有 LLP =,同样我们有 LPL =,进而得 LLP m =,LLPm = 以及
(LL =)n (L )n LL =,
最后,我们来证明 L →)(n L,为此只要验证 L )n( 的一切收敛子列都有相同的极限,假
116
定另有一个收敛子列,L →)m( k ~L,那么,由 (LL =}mk (L )mk LL = 便得
LLLLL == ~~,但是 L 与
~L
是对称的,因此也应有
~~~ LLLLL ==
,这样就有 LL =~,
从而 L →)(n L,
[注 ] 对于可数状态的 Markov 链,定理结论仍然正确,但是证明要复杂多了,需要用
Tauber 型定理,故略,
为讨论极限矩阵 L 的形状,我们先引述一个数学分析的引理,它的证明由数学分析是不
难得到的,本书略去,
引理 ５,４１ 若,Mb0,a,0a k,n
n
nn ≤≤∞<≥ ∑ 且 )n(,bb kk,n ∞→→,则
∑∑ ∞
==
∞→ →?
1k
kk
n
1k
n
k,nk baba,
命题 5,４２ (1) jjijij lfl =,
(2),对于互通的有限状态 Markov 链,极限矩阵 L 的各行是一样的,即它具有形式
pT1L =,其中 p 是 P的不变测度,
证明 由
∑ ∑∑
= =
=
==
n
m
m
k
km
jj
k
ij
n
m
m
ijij pfnpnnl
1 1
)()(
1
)( 11)( ∑ ∑
= =
=
n
k
n
km
km
ij
k
ij pnf
1
)()( 1,
用引理 ５,４１ 便得 (1),而互通的有限 Markov 链的状态都是常返态,由定理 5,28 可知
1=ijf,即 jjij ll =,从而 L 具有形式 pT1,其中 =jp jjij ll =,
注 1 对于可数个状态的互通的常返 Markov 链,命题也成立,但是 p 未必是 P的不变测度,因为它 可能为零矩阵 (参见后面的 5,2 段 ),由定理 ５,４２ 可见 L 应该是以下的形式
=L
OMMM
L
L
0
0100
0010
0
2
2
1
1
21
21
)(
)(
)()(
p
p
pp
T
T
jijjij
H
H
ffT
HHT
注 2 (有限状态 Markov 链的 ijf 的计算 ) 由全概率公式可得下述递推关系
ijij
jk
n
kjik
n
ij pfnfpf =>= ∑
≠
)1()1()( ),1(,,
对 n 求和便得
∑
≠
+=
jk
ijkjikij pfpf,
记总状态数为 N,于是 TNjjj fff ),,( 1 L
= 是方程 =x P jj px +→ )0( 的解,其中 P )0( →j
117
为把 P中第 j 列改为零后所得的矩阵,而 jp 为 P的第 j 列列向量,这个方程的近似解可以用迭代方法求得,用这个方法可以在原则上估算被指定的吸收态所吸收的概率,例如说,
从 i 出发最终被吸收态 a 吸收的概率为 iaf,因此,上面的方程实际上是博采者输光概率的方程的一般化,
4,Dobrushin 不等式与 指数收敛性
研究 nP 的收敛性,比定理 5 。 ３９ 在理论与应用方面更为一般的是 Dobrushin 方法,它建立在 Dobrushin 不等式的基础上,对于无穷维行向量 ( 可取负值 ) =w ),,( 21 Lww,可以定义模
=|||| w ∑
j
jw ||
( 显见它满足三角不等式,|||||||||||| ~~ wwww +≤+ ),
4,1 Dobrushin 不等式
定理 5,４３ 对于概率分 布向量 vu,,我们有
(1) |||| vPuP? ∑ ∑ ≤?=
i
i
i
iii PCvpup )(||)||( |||| vu?,
其中
||||sup21)(,?=?= ∑
j
kjijki ppPC p?i p ||k,
称为转移密度的 Dobrushin 收缩系数,简称 Dobrushin 数,其 中 p i 是 P的第 i 行组成的行向量 。
(2) 对于转移矩阵 QP,有
)()()( QCPCPQC ≤ 。
证明 (1) 记数 a 的正部与负部分别为 +a 与?a,再分别记
/)( ±±?= jjj vur ||||21 vu?,
注意
∑∑ =?=+
j
jjjjjj
j
vuvuvu 0)(])()[(,
∑∑ =?=?++
j
jjjjjj
j
vuvuvu ||])()[( |||| vu?,
我们有
118
∑ +
j
jr ∑?=
j
jr ||||
2
vu?= ∑ =?
+
j
jj vu 1)(,
同时还有
)(21)()(?+?+?==? jjjjjjjj vuvuvu rr |||| vu?,
于是
∑ ∑
i
i
i
iii vpup ||)|| = ∑∑?
i
iiij
j
vup |)(|
||||21 vu?= ∑∑?+?
i
iiij
j
p |)(| rr ||||21 vu?= ∑∑∑?+?
i
kikjij
kj
pp |)(| rr
|||| vu?≤ ∑∑+
i
kjijki
k
pp |)|21(rr )(PC≤ |||| vu?,
今证 (2),记 P的第 i 行的行向量为 p i,则由定义及 (1) 得到
=)(PQC ∑ ∑∑?
j
ljkl
l
ljil
l
ki qpqp ||sup2
1
,
||sup21,ki= p i pQ? k ||Q
||)(sup21,QCki≤ p?i p ||k ||sup21,ki= )()( QCPC=,?
显见,对于 N 个状态的 Markov 链的转移矩阵 P 有
ijji pNPC,min1)(?≤,
4,2 Dobrushin 收敛定理
定理 5,４４ 若 1)( <PC,则存在不变分布 p,及 常数 0,10 ><< Ca,0n,使
)(,|)(| 0nnCnp n
j
jij ≥?<?∑ ap,
证明提示 对于任意概率分布向量 vu,,用 Dobrushin 不等式得
∑ ∑
i i
n
ii
n
ii pvpu ||||
)()( ∑?=
ji
iij
n
ij vupp
,
)( ||)(||
||)(|| )1()1(∑ ∑∑=
i i
i
n
iji
n
ij
j
j vpupp ∑ ∑≤
i i
i
n
iji
n
ij vpuppC ||||)(
)1()1(
≤≤ LL )(归纳地 npC ))(( |||| vu?,
用高等分析中完备距离空间的压缩映射原理 (全体向量在距离
=),( vud |||| vu?
下,组成完备距离空间,参见第 9 章第 3 节 ) 可知,存在 概率分布向量 p,对于任意概率分布向量 u,
都有
119
n
i
i
i pCnpu ))((||)(|| ≤∑ p |||| p?u,
取 u ),,( 21 Lkk pp=,2=C,)(PC=a,便得,对于任意 k 均有
n
j
n
kj
j
Cp ap ≤?+∑ || )1(,
[注 1] 定理 5,３９ 是定理 5.４４ 的特殊情形,这时有 11)( <?= dNPC,但是定理
5.３９ 更为直观,所以我们仍把它单独列出,细心的读者会看出,定理 5.４４ 恰是定理 5,
３９ 的发展与抽象化,
[注 2] 在实用中,定理 5.４４ 大多是适用的,
5,与常返态相系的延迟更新流,互通常返 Markov 链的极限定理
5.1 与常返态相系的延迟更新流
对于常返态 i,记 Markov 链首次到达 i 的时刻为 0T,以后各次返回 i 的时间间隔相继为
L21,TT
命题 ５,４５ }1:{ ≥nTn 独立同分布,而且与 0T 独立,
证明 利用 Markov 性及齐次性
))0(,,|)0(,,()|( 01 nkiimliiPnTmTP knlnmn <≤≠=<<≠==== ++ xxxx
)|)0(,,( imliiP nlnmn =<<≠== ++ xxx )|)0(,,( 0 imliiP lm =<<≠== xxx,
而上式右方与 0T 的取值无关,因此 1T 与 0T 独立,类似地可证明 }1:{ ≥nTn 独立,而且与 0T
独立,并且 }1:{ ≥nTn 同分布,?
从常返态 i 出发的互通的 Markov 链是一个再现过程,相 系更新间隔流 }0:{ ≥nTn,
由此生成一个延迟更新过程 )(itN,1T 的分布为?d 格点分布,其中 1≥d,我们不加证明地指出,在 2≥d 时,它就是 i 的周期,
5,2 互通常返链的极限定理
定理 5,４６ 设 )(inN 为互通的 Markov 链在 时刻 n 前返回常返状态 i 的频数,则其频率有极限
1)1(
)(
= →? ∞→
i
n
i
n
n
NP
m,
120
其中 ∑===
k
k
iii kfiTE
)(
01 )|( xm,而 }0:{ ≥nTn 为 常返状态 i 相系的延迟 更新间隔流,
证明 这是延迟更新定理的推论,
[ 注 ] 定理的结论也可以写成
i
nnii
n
II
m
xx 1)()( }{1}{ →?++ ∞→L
( 以概率为 1 成立 ),
定理 5,４７ 若 Markov 链的所有状态都是互通常返的,则对于任意 i 有
∑
=
∞→ ==
n
k j
k
ijnij pnl
1
)( 1)1lim(
m,
而且此时平均极限 L 的所有分量要么全为正,要么全为零,
证明 我们只对有限状态情形给出证明,因为一般状态情形需要测度论的工具,
用定理 5,４０ 我们得到
∑
=
∞→∞→ ==
n
k
n
k
ijnij Epnl
1
)( (lim1lim )|)()(
0
}{1}{ i
n
II njj =++ xxx L
∞→= nE(lim
i
njj i
n
II
mx
xx 1)|)()(
0
}{1}{ ==++L,
这里实际上用了取期望与求极限的交换性,在有限状态情形是没有问题的,而在一般情形则需要用测度论的工具,
再则,对于任意两个状态 ji,,由于它们常返互通,就必定存在 00,nm,使
0,)()( 00 >njimij pp
于是
∑++
=
∞→ ++=
00
1
)(
00
1lim nmn
k
k
ijnii pnmnl
∑
=
++
∞→=
n
k
knm
iin pn
1
)( 001lim
∑
=
∞→≥
n
k
n
ji
k
jj
m
ijn pppn
1
)()()( 001lim )()( 00 n
jijj
m
ij plp=,
又因为 ji,是对称的,所以它们是否为正是相同的,从而平均极限 L 的所有分量要么全为正,要么全为零,
推论 ５,４８ 若 Markov 链的所有状态都是互通正常返的,则 L 的所有分量全正,此时 pT1L =,其中 p 是 P 的唯一的不变测度 ; 而 若 Markov 链的所有状态都是互通零常返的,则 L 0=,
推论 5.49 Markov 链存在不变分布的充要条件为至少存在一个正常返类,在条件成立
121
下 Markov 链的一切不变分布可以表为它在各个正常返类上的不变分布 )(ip 们 的凸线性组合,
p ∑=
i
il
)(ip,∑ =≥
i
ii 1,0 ll,
证明提示 由 L 的形式立得充要条件,用较多的数学工具还可以证明不变分布的表示
( 因其涉及过多的技术细节,本书略去 ),
由推论 2 直接推出下述非常有用的互通正常返性判据,
定理 5,５０ (Markov 链的互通正常返性判据 )
（ 1 ） 对于互通或只有一个常返类的 Markov 链,那么此链为正常返的充要条件为存在唯一的不变分布,
（ 2 ） 无暂态的 Markov 链为互通正常返的充要条件为存在唯一的 不变分布,?
这个定理在判别 Markov 链的正常返性时非常有用,
[ 注 1] 当 Markov 链的所有状态都是互通正常返且非周期时,进一步有
∞→nlim
nP p== L T1,
此结论在实际中非常有用,它说明在时间发展充分长以后,不论初始值为什么,nP 的每一行都近似为 p,它可以用来作为稳态设计的根据,
再则,这个注也是一个非常一般的结论,大多数有关 ∞→nlim nP 存在的结果,都常由此引申而得,
[注 2] 对于正常返性的判别,还有一个充分条件,我们姑称之为,在有限集外的?e 盈函数条件,,近年来,它在多路通信的数学理论中,有不少应用,其叙述如下,
Foster 定理 （ 利用 Lyapunov 函数的正常返性判据 ）
若不可约,Markov 链 的转移矩阵 P )( ijp= 满足 即,存在状态空间上的非负函数 g (可取 ∞+ ),
0>C 及一个状态的有限集 F,满足
)()( Fijgp
j
ij ∈∞<∑,（ L,１ ）
)()()()( FiCigjgjp
j
ij≤?∑,（ L,２ ）
则此链为正常返的,再加上 非周期性,则进一步有
∞→nlim
nP =p T1,
又若 （ L,２ ） 改为
)10,)()()( <<≤∑ rr FiCigjgjp
j
ij （
（ L,２ ）＇
那么,此收敛还是指数收敛,
（ 直观地,函数 g 与常微分方程的稳定性理论中的 Lyapunov 函数起类似的作用,也称为 Markov 链的 Lyapunov 函数,第二个条件说明 h 函数 g 在沿 F 的余集中的状态运动时一致地减小 （ 经过一次转移后一致地减小了 ）,而由第一个条件,沿有限集 F 中状态运动时函数 g 的增加是一致地有界的,且由不可约
122
性,Markov 链终究会离开有限集 F,这样就使得在确定极限分布时,F 的作用可以在实际上忽略不计,
从而保证极限 分布的处在 ）,
定理的证明需要较多的鞅论知识,本书从略,
更重要的意义是此定理在连续时间的对应的推广形式,称为 Tweedle 定理,
定理 5,5 １ (遍历性定理 )
若 Markov 链的所有状态都是互通正常返的,f 是状态空间 S 上有界实值函数且满足
∑ ∞<μ
i i
if 1|)(|,则
∑ = →?++ ∞→
i i
nn if
n
ffP 1)1)()()(( 1
m
xx L,
即对于任意一个互通的 Markov 链及满足 ∑ ∞<μ
i i
if 1|)(| 的 f,以概率为 1 地有
pi →?ξ++ξ ∑∞→
)(0
)()()()( 1
对零常返链对正常返链
i
inn if
n
ff L,
其中 p = },,,{ 21 Lpp 是 P的不变分布,
i
i mp
1=,此极限与初分布无关,
证明 我们只对有限状态情形给出证明,因为一般状态情形需要测度论的工具,设状态数为 N,注意到 ∑
=
=
N
i
kik Iiff
1
}{ )()()( xx,于是由定理 5,４０ 得
∑∑∑
= ==
=
n
k
N
i
ki
n
k
k Iifnfn
1 1
}{
1
)()(1)(1 xx
∑∑ ∑
=
∞→
= =
→?=
N
i i
n
k
N
i
n
k
i ifInif
11 1
}{
1)()(1)(
mx ( 以概率为 1 成立 ),
[ 注 1] 有多个正常返类时,相应的极限仍然存在,但是依赖于初值的选取,
[ 注 ２ ] 若 Markov 链 )0,{ ≥nnx 的所有状态都是互通正常返,则不难证明
),( 1+?= nnn xxh 也是时齐的互通 Markov 链,其转移概率为 jlkjlkji pp δ=),(),,( （ 它不依赖 i ），
而且以 SSjiji ×∈),(),( ),(p 为唯一的不变分布,其中 ijiji ppp
=),(,而 p ),,( 21 Lpp= 是
Markov 链 )0:{ ≥nnx 的不变分布,由定理 5.５０ 推出 }0:{ ≥nnh 也是互通正常返 Markov
链,从而对于 SS × 上定义的函数 g,只要满足 ∑ ∞<pi
ji
iji pjig
,
|),(|,就 以概率为 1 地
123
有
→?ξξ++ξξ ∞→++ nnknk n gg ),(),( 11 L ∑ pi
ji
iji pjig
,
),(,
（ ),( 1+?= nnn xxh 的互通性证明如下,
设 ),(),,( lkji 为任意两个状态 。 如果 0=klp,则 ),( lk 是一个不可达到的状态,在本质上可以去除 。
所以我们不妨设 0>klp 。 由 nξ 的互通性,存在一条从 j 到 k 的通路 ； kjjj m =→→→ L1,
于是我们得到,),(),(),(),(),( 1211 lkkjjjjjji m →→→→→?L,这就得到了从 ),( ji 到
),( lk 的一条通路 ）,
[ 注 3] 一般地,涉及 Markov 链 )0:{ ≥nnx 的概率,由它的有 限维分布族确定,也就是由它的初始分布 m 与转移矩阵 P确定,但是,在得到注 2 的结论时,假定的条件只对 P作了要求,这正说明上面的结论与 Markov 链 )0:{ ≥nnx 的初始值 m 无关,这类与初始值无关的结论,正适合统计物理中稳态模型的要求 ( 与后面第 11 章的平稳序列理论相比较,当初始值为不变分布 p,即 iiP px == )( 0 时,)0:{ ≥nnx 为平稳序列,而且可以证明在我们的条件下,它具有所谓遍历性,于是利用平稳序列的遍历性定理,也可以得到上面的极限,
但这时须假定初始值服从不变分布,也就是说,从强有力的平稳序列理论,并不能得到这类与初始值无关的结论,由此可见 Markov 链理论的优点 ),
[ 注 4] 注 3 的结论还可以推广到 m 个变量的函数的情形,
[ 注 5] 对于互通 的正常返 Markov 链,不管它的初分布 m = )( 0?=xP 是什么,可以用 }{ nx
关于时间发展的平均来估计此 Markov 链的不变分布与转移矩阵,作法如下,分别取
)},{(}{,jii IgIf ==,则以概率为 1 地有
i
nnii
n
II pxx →?++ ∞→)()( }{1}{ L
,
)(),(),( )},{(11)},{( kpn II ijinnknjikji pxxxx →?++ ∞→++ L,
由此我们可得用一条轨道来估计 ip 与 ijp 的估计式,
=^ip n II nii )()( }{1}{ xx ++L,
124
=
^
ijp )()(
)()()()(
}{1}{
1}{}{2}{1}{
nii
njniji
II
IIII
xx
xxxx
++
++ +
L
L
,
此两式是对 ip 与 ijp 进行模拟计算的依据,
关于 Markov 链的数值计算,有以下的注意事项,
１,初始分布 0m,转移矩阵 P )( ijp= 的 Markov 链的样本,可以作如下的模拟,
(1) 取一个 0m 随机数 0i ;
(2) 取一个 )),,,((
000 1
LL jiii ppp = 随机数 1i ;
(3) 取一个
1i
p 随机数 2i ; …
那么 ),,,( 210 Liii 就是 Markov 链 ),,,( 210 Lxxx 的一个样本,
２,没有可逆分布情形时不变分布的近似算法 ( 参阅 [T])
假定状态空间为非负整数,且当 0mm ≥ 时,不变分布 p ),,( 10 Lpp= 满足
m
m Cap ≈,
那么
)( 000 mmmmmm ≥≈?app,
(1) a 的近似确定
此时不变分布的矩母函数 zzzz mmkk
m
k
+≈ ∑
= a
ppp 1 1)( 0
0
0 1
0
,所以,如果知道了不变分布的矩母函数 )( zp 近似地是一个有理函数,且它的分母只有一个大于 1 的根,那么此根的倒数就是 a,
(2) mppp,,,10 L 的确定
不变分布满足的方程可以改写为
=
1
0
0m
p
p
M A
0
0 1
0
m
m
p
p
p
M
,
11 0
0 1
0
=?+∑
= a
pp m
i
m
i
,
其中
A )0,10()( 00 mjmiaij ≤≤?≤≤=,
125
=
≤≤
=?∞
=
∑ )(
)10(
0
0
0
0
mjp
mjp
a
ki
mk
mk
ji
ij a,
6,停时与强 Markov 性
6,1 停时
定义 ５,５２ 非负且可取 ∞+ 的随机时刻 t,称为时齐的 Markov 链 )0:{ ≥nnx 的 停时,如果它是 }{ nx - 可 知的,即,对于 任意 n,事件 }{ n≤t 可由 Markov 链 }{ nx 在 n 前 的信 息 }:{ nmm ≤x 所决定,直观上说明停时 的发展是与 Markov 链的发展是,同步的,,
Markov 链首次到达状态空间的某一个子集合 A 的时刻 At,就是停时的典例,这是因为事件 )}(,,{}{
1
mkAAn km
n
m
A <?∈=≤
=
xxt U 只涉及 }{ nx 在 n 前的信息,
6.2 强 Markov 性
命题 ５,５３ 时齐的 Markov 链 )0:{ ≥nnx 具有 强 Markov 性,就是对于停时也有
Markov 性,即,对于任意停时 t 及任意状态 10,,,,?niiji L,在集合 }{ ∞<t 上,都有
),|( 1 前的信息在时刻 txxx tt?+ == ijP )|( 1 ijP === + tt xx )|( 01 ijP === xx,
( 证明提示 把条件概率写成联合概率除以条件的概率,再在计算其中每一个概率时,
对 t 的取值用全概率公式,然后分别用 Markov 性,即可证明,细节从略 ),
[注 ] 强 Markov 性也有与 Markov 性类似的相应的等价性叙述,请读者仿照 Markov 性的各种等价性叙述,把它们写出来,
7,禁忌概率与首达分布
7,1 禁忌 概率
定义 ５,５４ 由状态 i 出发,经 n 步到达状态 j,中间未到过状态集 A的概率,称为 禁忌 A的转移概率,记为 )(nijA p,即
)(n
ijA p ).|)0(,,( 0 inmAjP mn =<<?== xxx
7,2 首达时与首达分 布
定义 ５,５５ (首达时及其分布 )
设 A为一个状态集,随机时刻 }:0inf( An nA ∈≥=? xt 称为 首达 A的时刻 (对于空集 Φ,恒定义
126
∞=Φinf ),简称 A的首达时,
(注意首达时与击中时不同,击中时定义为 }:1inf( AnT nA ∈≥=? x,0=n 它在何处是不计入的 ),
定义 ５,５６ (首达分布 )
)|,( 0 ijP
AA
==∞< xxt t 作为状态 j 的概率函数,称为 A的首达分布,一般地,首达分布是 有亏损的分布,因为
===∞<∑
∈
)|,( 0 ijP
AA
Sj
xxt t 1)|( 0 ≤=∞< iP A xt,
而可能小与 １,只有当 1)|( 0 ==∞< iP A xt 时,首达 分布才是一个分布,
定义 ５,５７ (越出时 )
}:0inf{ An nA?≥=? xs
称为越出状态集 A的时刻,简称 A的越出时,它是 A的余集的首达时刻 ASA \st =,
7,3 禁忌概率,首达分布与平均首达时间
定理 5,５８
(1),
==>
∈====
)()|,(
)()|,(
0
0)(
AjijnP
AjijnPp
nA
nAn
ijA xxt
xxt
,
(2),把 P限制在状态集 A上,并记为 AP Ajiijp ∈=,)(,则对于任意 Aji?,有
()( =nijA p ASP \ ijn ),
(3) 对于 Ai 有
)|( 0 inP A => xt ASP \(= iTn )1 ∑
=
Aj
n
ijA p
)(,
(4),若 1)( =∞<AP t,则有
== )|( 0 iE A xt ∑
∞
=0n
ASP \(
n
i
T )1,
以上各式中的上标 n 是指 n 次方幂,
证明 (1) 显然,今用归纳法证明 (2),1=n 时恰是定义,设 n 时等式成立,1+n 时利用 Markov
性及归纳法假设得
),,( 1
\
)1( jknPp
n
ASk
nA
n
ijA ==>= +
∈
+ ∑ xxt
∑
∈
+ ===
ASk
nn
n
ikA kjPp
\
1
)( )|( xx
∑
∈
=
ASk \
ASP \ kj
n p (=
ASP \ ij
n )1+,
(3)的证明,
127
∑
∈
==>
ASj
n
ijAA pinp
\
)()|( xt
∑
∈
=
ASj \
( ASP \ ijn ) ASP \(= iTn )1,
最后证明 (4),当 1)( =∞<AP t 时,我们有
∑ ∑∞
=
∞
=
=>=====
1 0
000 )|()|()|(
k n
AAA inPikkPiE xtxtxt,
再用 (3),便得 (4),
定理 5,５９ 若 1)|(,0 ==∞<∈? iPBi B xs,则有
(1),BPI?( =?1)n ∑
∞
=0n
BP ∞<
n,
(2) B 的平均越出时间与越出分布有 表达公式,
E =?= )|( 0xs B 1)( BPI T1,
x(P
Bs
[)| 0 ∑
∈
===
Bk
ij x 1)( BPI kjik p],
证明 令
∈
∈=
)\(
)(~
BSi
Bipp
ij
ij
ij d,
那么定理 5,５８ 对于
~P
仍然成立,而对于转移矩阵为
~P
的 Markov 链来说,BS \ 中的状态都是吸收态,
由本定理的条件知道 B 中的状态都不是常返态,即全是暂态,故而
∑∑ ∈?∞<=
n
n
ij
n
n
ijBS Bjipp,,
)(~
)(
\,
于是由定理 5,５８ 的 (2)推出本定理的 （ 1）,(2)的第一式恰为定理 5,５８ 的 (4),而由定理 5,５８ 的 (1),有
x(P
Bs
=== )| 0 ij x ∑ ∑
≥ ≥
====
1 1
)(
\0 )|,(
n n
n
ijBSnB pijnP xxs,
再用定理 5,５８ 的 (2) 便得第二式,】
在 S 为有限集时,平均越出时间与越出分布可写成更为简单的公式,提供实用计算,
定理 5,６０ 对于有限状态 Markov 链,平均越出时间与越出分布可以用行列式表示,即 对任意 Bi∈
只要满足 1)|( 0 ==∞< iP B xs,那么,对任意 Bj ∈ 有
E =0|( xs B =)i ∑
∈Bk
ik
BD
BD
)(
)(,
x((P
Bs
=== ))| 0 ij x )( )( BD pBD kjik
Bk
∑
∈
,
128
其中 det)( =BD )( BPI?,)( BD jk 为 )(BD 的 ),( kj 处元素的代数余子式,
证明 把定理 ５,５９ 的 (2)中第一式用逆矩阵写出来就是 (1),类似地得到第二式,
8,可逆 Markov 链与可逆分布
一个用 Markov 链描述的 系统,常常可以利用它的长时间后的稳定分布,作为其参数的稳定设计的依据,在前面我们已经看到,在很宽的条件下,不变分布就是这个稳定分布,而求不变分布需要解一个方程,一般来说需要很大的工作量,所幸的是,在实际中有很多简单的网络系统常满足一个对称性条件,即所谓可逆性条件,对于这种 Markov 链,有一种求不变分布的简便方法,在本节中,我们将给出这方面的理论,
8,1 可逆 Markov 链
定义 ５,６１ 以 P 为转移矩阵的 Markov 链,称为 可逆的,如果存在概率分布
m ),,( 21 Lmm= 使
jijiji ppSji mm =∈?,,,
m 称为 可逆初分布,简称 可逆分布,在物理中,此条件称为 细致平衡 条件,
由此定义可以看出,可逆分布是唯一的,又可逆分布一定是不变分布,事实上,由可逆性的定义立得
∑ ∑ ==
i i
jjijiji pp mmm,
定义 ５,６２ 随机变量序列 nx 称为时间可逆 的,如果 对于任意时刻 0≥> nm,恒有
),,,( 1 mnn xxx L+ 与 ),,,( 1 nnm xxx +L 同分布,
例 ５,６３ 若取可逆 Markov 链的 可逆分布为 初始分布,即 )(,)( 0 SiiP i ∈?== mx,
则此 Markov 链是时间可逆的,
事实上,由初始分布是可逆分布得到
),,,( 11 mmnnnn iiiP === ++ xxx L
mmnnnnn iiiiiii
ppp
1211?+++
= Lm
mmnnnnn iiiiiii
ppp
12111?++++
= Lm
mmmnnnn iiiiiii
ppp m
1121?+++
= L
),,,( 11 nnnnmm iiiP ==== ++ xxx L,
命题 5,6４ 在初始分布 m 下,Markov 链是可逆的充要条件为,以 m 为初始分布的随机变量序列是时间可逆的,
证明 必要性已经证明,充分性得自,,Sji ∈?
=iji pm ),( 0 jiP i == xx ),( 0 ijP i === xx jij pm=,
推论 ５,６５ 细致平衡条件等价于,jin,,?,有 )()( njijniji pp mm =,
129
求可逆 Markov 链的不变分布 ( 就是可逆分布 ),与求一般 Markov 链的不变分布相比,要简单得多,所以,判别一个 Markov 链是否具有可逆性,在实际中是十分重要的,
再则,若 Markov 链具有不变分布 m,设 0S 是状态空间的一个子集,把 Markov 链限制在
0S 上,即对于 0,Sji ∈?,定义
∑
∈
=
0
0
Sk
ik
ijS
ij p
pp
,
=+ ≠= ∑
0
)(
)(~
Sk
ikii
ij
ij jipp
jip
p,
∑
∈
=
k
k
iS
i m
mm 0,
一般地,m 0S 不再是 P 0S 和
~P
的不变分布,但是,当 m 为 P的可逆分布时,m 0S 仍是 P 0S
和
~P
的可逆分布,这个性质称为 可逆初始分布关于状态子集的不变性,
8,2 例
例 ５,６６ {整数格点 Z 上的生灭链 }
设正数 ),2,1,0(,1,L±±=?= ipqp iii,
P
=
+=
==
)(0
)1(
)1(
),(
其它
ijq
ijp
pp i
i
ijij,
定义
<
=
>
=
∏
∏
+=?
= +
0
1 1
1
0 1~
)0(
)0(1
)0(
ik k
k
i
k k
k
i
ipq
i
iqp
m,
那么容易检查
jijiji ppSji
~~
,,mm =∈?,
于是只要 ip 们满足条件
∑∞
∞=
∞<
i
i
~
m,
再令
∑∞
∞=
=
j
j
i
i ~
~
m
mm,则 m ),,,,(
101 LL mmm?= 就是可逆分布,
130
例 ５,６７ 设转移矩阵为
=
2
10
2
1 2
1
2
10
02121
P,
我们来证明它不存在可逆分布,解方程 mm =P 得 P的不变分布为 )31,31,31(=m,而对于
2,1=i 有 061,111,≠=? +++ iiiiii pp mm,这说明 P没有可逆分布,
8,3 可逆初分布存在性判别法
定理 5,６８ ( Kolmogorov 可逆性准则 ) 状态数为 N 的互通的 Markov 链具有可逆分布的充要条件为,对于任意的一个状态环路 121,iiiiR m →→→→ L 恒成立下面的
(K) 条件,
(K)?= RR pp,
其中 Rp 是沿环路 R 的转移概率的积,即,
1121 iiiiiiR mmm pppp?
= L,
而?R 则是环路 R 的反向环路,
在 (K) 条件满足时,可逆分布是唯一的,而且可以求得如下,固定某个状态 0i,对于任意状态 i,任取一条从 0i 到的通路 iiiii mm =→→→→ +110 L,于是它满足
0
0 1
1 >=∏
=
+
+
m
k ii
ii
i
kk
kk
p
pv
,
定义
=+
≠+
=
∑
∑
≠
≠
)(1 1
)(1
0
0
0
0
iiv
iivv
ik
k
ik
k
i
im,
那么可逆分布为 m ),,,( 21 Nmmm L=,其中 iv 不依 0i 及通路的选取,
[注 ] 对于一般的可数状态 Markov 链,只要在 (K) 条件外加一个要求 ∑ ∞<
i
iv,则充要条件及可逆分布 m 的表达式仍然正确,可见本定理提供了得到 可逆分布 的简单方法,
证明 必要性,首先证明 im 们全为正,事实上,由于 m 是 可逆初分布,所以存在 0i
131
使 0
0
>im,再由链的互通性,对于任意 i,必有 n 使 0)(
0 >
n
iip,于是由可逆性条件立得 0>im,其次,任取通路 iiii n =→→→ +110 L,则我们有
iiiiiiiiiiiiii nn pppppp LL 2110121100 mm = iiiiiii nppp mLL 0201==,
特别地,当通路为闭的环路时有 ii =0,故得条件 (K),因此必要性成立,
充分性,首先证明,iv 们的定义与从 0i 到 i 的通路的具体取法无关,事实上,设有两条通路,,1R iiii n =→→→ +110 L 及,2R iiii m =→→→ +110 '' L,把沿通路 21,RR
定义的 iv 值分别记为 )1(iv 与 )2(iv,对于 21,RR 的反向环路 21,RR,考虑复合环路
12 RR o
(
0i 出发沿 1R 至 i 再沿 2R 的反向环路
2R 回到 0i ),由 (K) 条件可得
2112 RRRR
pp oo =,即
i
i
RR
RR
RR
RR
v
v
pp
pp
p
p
)2(
)1(
12
21
21
121 ===
o
o,
于是 )1(iv = )2(iv,从而 m 作为 v 的规一化也是唯一地确定的,最后证明 m 为可逆分布,事实上,对于任意的 ji,分两种情形考虑
(1),0>ijp 的情形,取 i 到 j 的通路 R,这时对于前面的通路 1R,由 (K) 条件得
0
11 >= RRRR pp oo,可见有 0>jip,进一步取 ji =0,那么 1),(,=≠= j
ij
ji
i vjip
pv
,
于是得 jijiji pvpv =,所以 m 是可逆分布,
(2),0=ijp 的情形,此时由情形 (1)知道必有 0=jip,从而 jijiji pvpv = 仍旧成立,
9,分支 Markov 链 (Galton - Watson 简单分支过程 )
Markov 链的应用非常广泛,它涉及物理,生物,化学,神经网络,信息,经济,金融等诸多领域,在各种应用模式中,由于实际问题往往是十分复杂的,如不对其进行适当的简化,不仅可能使问题因过于复杂而无法解决,而且也会使主要矛盾被枝节所掩盖而难以理解,
因而我们必须对许多实际问题进行必要的抽象和简化,以便理解其实质,于是,也就不可避免地会使问题可能与实际有一定的差距,所以,在读者应用 Markov 链去解决实际问题时,
还需具体问题具体分析,根据实际情况去作必要的变通,以灵活地应用各种 模型,
本节所要介绍的分支 Markov 链,主要关注的是群体灭绝的概率,这类问题来源于中子,
细胞或微生物等 ( 其中个体统一地称为粒子 ) 的分裂与死亡的随机现象,这里每一代的裂变
132
是各自独立地进行的,裂变后的粒子的总数决定了下一代粒子的总数的分布,
设 }1,:{,≥knknx 是一族相互独立同分布,而且取非负整数值的随机变量,它表示第 ｎ
代的第 ｋ 个粒子分裂成的粒子数 ( 假定在它分裂后自己就立刻死亡 ),0,=knx 就意味着此粒子不分裂而死亡,于是第 ｎ＋ １ 代的粒子总数是
nnn h
xxh,1,1 ++=++ L,
设开始是一个粒子,即 10 =h,我们说明 nh 是 Markov 链,事实上,利用独立性我们有
(),,|( 111 PiijP nnnn ====+ Lhhh j
nnn
=++ hxx,1,L ),,| 11 L == nnn ii hh
jP inn =++=,1,( xx L ),,| 11 L == nnn ii hh )(,1,jP inn =++= xx L
)(,11,1 jP i =++= xx L,
上式右方与 },,{ 2211 L == nnnn ii hh 及 n 无关,可见 nh 是时齐的 Markov 链,而且其转移概率为
)(,11,1 jPp iij =++= xx L,
现在我们来具体计算 ijp,为此令 )0()( 11,1 ≥=== kpkPp kk x,记 1,1x 的矩母函数为
k
k
k
zpzF ∑
∞
=
=
0
)(,
那么,利用幂级数的乘法规则,我们由数学归纳法得到 kik
k
i zpzF ∑
∞
=
=
0
)]([,于是
0|
)]([
!
1
== z
i
ik dz
zFd
kp ( 0,0 ≥> ki ),
此外,由模型的含义显然有 0,1 00,0 == kpp ( 0>k ),这就是说 0 是此 Markov 链的吸收状态,当过程达到状态 ０ 就不再有粒子了,分裂也就中止了,在这个模型中,我们首先感兴趣的量是此 M arkov 链被 0 吸收的概率,即灭绝概率,我们把它记为 r,即 )( 0 ∞<= TPr,
其中 0T 为 Markov 链 nh 首次达到 0 的时刻,
记 nh 的矩母函数为
k
n
k
n zkPzG )()(
0
== ∑
∞
=
h,
再一次由幂级数的乘法推出
133
k
n
k
n zkPzG )()( 1
0
1 == +
∞
=
+ ∑ h knnn
ik
ziPikP )()|( 1
00
==== +
∞
=
∞
=
∑∑ hhh
k
nik
ik
ziPp )(
00
== ∑∑
∞
=
∞
=
h in
i
zFiP )]()[(
0
== ∑
∞
=
h ))(( zFGn=,
即第 n 代的个体数的矩母函数是第 1 代的矩母函数的 n 次叠置,由此可以算出 nEh 与
)( nVar h 的递推公式,
现在我们来分别分析在什么条件下有 ρ ＝ １,ρ ＝ ０ 及 ０ ＜ ρ ＜ １,也就是什么条件下粒子概率为 1 地全 死光,永远不会死光,或既可能死光也可能不死光,最简单的情况是
00 =p 或 10 =p 的情形,它们分别代表粒子在下一个时刻不死亡与必然死亡,那么显然前者永不灭绝,而后者是必定灭绝,为避免这种平凡的情况我们假定 ０ ＜ ρ ＜ １,我们来求
ρ,记平均一个粒子的后代个数为 1,1xm E=,直观地可以猜测,若 μ ＞ １ 则不会全部灭绝,
而 μ ＜ １ 则会全部灭绝,为此,注意由于各个粒子的分裂是独立地进行的,所以有
)|( 10 kTP =∞< h kTP )1|( 10 =∞<= h kr=
于是由全概率公式推得
)( 0 ∞<= TPr )()|( 10
1
0 rh FkTPpp k
k
==∞<+= ∑
∞
=
,
可见 r 是函数 )( xF 在 ]1,0[ 中的不动点,也就是说 ρ 应为曲线 xy = 与曲线 )(xFy = 在中
]1,0[ 之交点的横坐标,显见 1=x 总是一个不动点,这是一个平凡的不动点,我们对此不感兴趣,而当 10 << x 时有
0)(' 1
1
>=?
∞
=
∑ nn
n
xnpxF,0)1()('' 2
2
≥?=?
∞
=
∑ nn
n
xpnnxF,
可见 )( xF 是递增的凸函数,于是 )( xF 是否在区间 (0,1) 中有不动点,就归结为 凸函数
xxF?)( 在 1=x 处的导数是正还是负,前一种情形说明当 ε ＞ ０ 充分小时,
01)1()1()1( =?< FF ee,因而由 0)0( 0 >= pF 与连续函数的中值定理得到,方程
xxF =)( 在区间 )1,0( 中有解,进而由 )( xF 的凸性就知道这个方程在区间 )1,0( 中解是唯一的,我们把它记为 0r,而后一种情形即 01)1(' ≤?F ( 也即 μ≤ １ ),此时由 )( xF 的凸性得到 xxF?)( 在区间 )1,0( 中恒负,所以这时方程 xxF =)( 在 [ ０,１ ] 中只可能有一个解,
134
1=x,从而在 1<m 时必然有 1=r,这说明最终将以概率为 1 地全部灭绝,而在 μ ＞ １ 时,
我们来证明 0rr = ( 而不可能是 1=r ),事实上
)(
0,1
)(
00
)(
0,1
1
)(
0,1
1
limlim nnknk
n
k
n
n
n
ppff ∞→?
=
∞→
∞
=
=== ∑∑r,
为了证明 0rr =,我们只需归纳地证明 0)(10 r≤np,首先,当 1=n 时有
000
)1(
0,1 )()0( rr =<== FFpp,
今作归纳法假设,设此不等式在 n 时成立,在 1+n 时由 )( xF 的递增性我们有
00
)(
0,1
)(
0,1
1
)(
0
)1(
1
1
)1(
0,1 )()()( rr =≤=== ∑∑ ∞
=
∞
=
+ FpFppppp nkn
k
k
n
kk
k
n,
综上所述得到以下结论
定理 ５,６９ 对于 Galton - Watson 简单分枝过程,设一个粒子的裂变分布列为
kpkP == )( 1,1x （ｋ＝ ０,１,… ）,且满足 10 0 << p,令 1,1xm E=,则在开始时有 i
个粒子时,全部粒子的灭绝概率为 ir,其中
>
≤=
)1(
)1(1
0 mr
mr,
而 0r 是方程 xxF =)( 的最小非负解,
此时第 n 代粒子数的平均规模为
)(
11
)1(
1
1
011 )1|(
n
jkj
jk
n
k
k
nn ppkkpE ∑∑∑ ∞
=
∞
=
+
∞
=
+
+ ==== hha
j
j
p∑
∞
=
=
1
)|( 0 jE n =hh j
j
p∑
∞
=
=
1
)1|( 0 =hhnjE nma=,
由于 10 =a,因而 nn ma =,可见当 μ ＜ １ 时,平均粒子数逐代单调下降趋于 0,当 μ ＝ １
时,各代粒子平均相同,而当 μ ＞ １ 时,平均粒子数按指数阶逐代上升至无穷,1=m 的情形称为临界情形,前面已经知道在 这种情形粒子最终必定灭绝,此时人们感兴趣的问题是平均灭绝时间多长,对此本书不再介绍,而 1>m 的情形,则称为上临界情形,
135
习题 ５
1,举例说明,如果集合 A包含不止一个状态,那么对于 Markov 链 }0:{ ≥nX n,下列等式不一定成立
)|(),,,|( 111001 AXjXPAXiXiXjXP nnnnnn ∈==∈=== ++ L,
2,设 nx 是以 {0,1,2} 为状态空间的 Markov 链,其转移矩阵为
3
1
3
1
3
1
122
212
aaa
aaa
,问
)(}2{ nn I xh = 是否为一个 Markov 过程? 如果回答,是,,则转移矩阵是什么?
3,设有数字 1,2,…,m,
(1),在其中任取一个数记为 0X,再在 1,2,…,1?nX )1( ≥n 中任取一个数记为 nX,证明
}0:{ ≥nX n 为 Markov 链,并求其转移矩阵,
(2),把它作一个随机排列,maa,,1 L,令 10 =X,)}(,min{ 1 ikaaXiX kinn <≥>=?,
min? 定义为 1+m,证明 10,,?mXX L 是一个以 }1,,1{ +mL 为状态空间的 Mar kov 链,求它的转移矩阵
4,连续地掷一枚均匀的硬币,如果第 n 次掷得正面,则令 0=nX ； 如果第 n 次掷得反面,且从第 n 次
往前看连续出现反面的数目为 k,则令 kX n =,约定 00 =X,证明 }0:{ ≥nX n 是 Markov 链,
并求其转移矩阵,
5,汽车单向地通过某路口,假设一秒钟可通过一辆汽车,路口的红灯 持续 r 秒,绿灯持续 g 秒,以,红灯 -
绿灯,的出现作为一个单元时间,在第 n 个单元开始时在等候的汽车数记为 1?nX,而把在这单元中来到的汽车数记为 nx,设 }1:{ ≥nnx 为独立同分布
+
+gr
n ppp
gr
L
L
10
10~x
,再假定在开始时刻路口没有汽车在等候,证明 }0:{ ≥nX n 是 Markov 链,并求其转移矩阵,
6,设 m 个人中的某些人已患流行性感冒,假定传染在两人间的接触中发生,当病人遇见健康者时,后者被
传染的概率为 p,一切成对的接触都是等可能的,而且在每个单位时间内只发生一次接触,记 nX 为时
刻 n 患病的人数,证明 nX 是 Markov 链,并求其转移矩阵,
7,设某水库容量为 c 立方米,在时刻 n 水库的储水量记为 nX,在时段 [n,n+1]内流入水库的水量记为 1+nx,
136
超过水库容量的水即溢出,假定在时段 [n,n+1]末从水库放掉 m（ <c） 立方米水 （ 其中包括库满而溢出的部分,如果溢出的水量已超过 m 立方米就不再放水 ）,假设 }1:{ ≥nnx 独立同分布且与 0X 独立,
0,)( ≥== kkP kn ax,证明 }0:{ ≥nX n 是 Markov 链,并求其转移矩阵,
8,设 1,0,=+> qpqp,若 Markov 链具有循环型的转移矩阵,
P
=
qp
pq
pq
pq
OO
,
证明
P
=
)(
1
)()(
2
)(
2
)(
1
)(
1
)(
)()(
1
)(
2
)(
1
nn
m
n
n
n
m
nn
m
n
m
n
m
nn
n
aaa
a
aaa
aaaa
L
OO
OOO
O
L
,
其中 nmnmnn pqaaa )(1)()(2)(1 www +=+++?L,而 w 为 1 的 m 次主复数根 (1 的其它复根都是它的幂 ),
9,证明有限状态 Markov 链的转移矩阵的特征值的 模都不大于 1,而且 1 总是特征值,
10,对于二值 Markov 链
P )1,0(,1 1 ≤≤
= ba
bb
aa
求 )(nijf 及 ∞→nlim Pn,
11,对下列各转移矩阵的状态进行分类,
=
1
1
1 2
1
2
1
1P,
=
2
1
4
1
4
1
2
1
2
1
2
1
2
12
1
2
1
2
1
2
1
2P,
=
3
2
3
1
3
2
3
1
3
0
0
001
P,
137
=
3
2
3
1
3
2
2
1
3
2
3
1
4
0
0
0
P,
=
0
0
0
3
2
3
1
3
2
3
1
3
2
3
1
5P,
=
OM
L
L
L
L
4
3
4
1
3
2
3
1 2
1
2
1
1
6P,
对 54,PP,6P 求 ijf,再记从状态 1 出发首次返回状态 1 的时间为 1t,求它的分布与期望,
1 2,设 Markov 链的转移矩阵为
=
100
0 4143
4
1
4
1
2
1
P,求 )3,2,1(,=if ii 及 nn P∞→lim,
13,若 出口商品用三状态表示,状态为 +1 表示今年比去年增长,状态 0 表示与去年持平,状态 –1 表示 今年比去年减少,过去的统计数据得到的状态间的转移矩阵为
+
+?
04.06.0
35.03.035.0
8.02.00
1
0
1
101
求各状态的平均返回时间和增长趋势与减少趋势的期望长度,
14,证明定理 5,３９ 是定理 5,４４ 的特例,
15,对于时齐的 M arkov 链 }0:{ ≥nnx,令 ),( 1+= nnn xxh,则 nh 也是时齐的 M arkov 链,在求 nh 的转移矩阵,
16 证明对于互通的有限 M arkov 链 }0:{ ≥nnx,以概率为 1 地有极限关系
∑ →?++ ∞→++
ji
iji
nnknk kpjig
n
gg
,
11 )(),(),(),( pxxxx L
17,设 }0:{ ≥nX n 是为正常返非周期的不可约 Markov 链,转移矩阵为 )( ijpP =,而 }0:{ ≥nnx 是
与 }0:{ ≥nX n 独立的独立同分布,随机变量列,)1(,)( ≥== kkP kn ax,令
nn xxhh ++== L10,0 1≥n,0,≥= nXY nn h,
则 }0:{ ≥nYn 为正常返不可约马尔可夫链,其转移矩阵为 ∑∞== 1~ k kk PaP,且它与 }0:{ ≥nX n
有相同的平稳分布,
18.,水库供水按其水位分为下列 5 个状态,1 表示危险水平,2 表示缺水,3 表示刚够,4 表示达到较好水平,5 表示充足,由统计已有数据得到其转移矩阵为
138
=
4.04.01.01.00
3.04.02.01.00
1.02.04.02.01.0
1.02.02.02.03.0
05.03.01.01.0
P,
求到出现危险水平的平均时间,
19,设 t 为 Markov 链 nx 的有限值停时,令 nn += txh,证明 nh 也是 Markov 链,求它的转移矩阵,再证明在已知 txh =0 的条件下,}{ nh 与 ),,,( 0 txxt L 条件独立,
20,设 }{ nx,}{ nh 相互独立,它们分别是独立同分布序列 ){ nX 与 }( nY 的部分和,
nn XX ++= L1x,)1(,
10~
11
≥
k
pqX k,nn YY ++= L1h,
)1(,10~
22
≥
k
pqYk,令 },1:min{ MnnT nn ±=?≥= hx,证明
（ 1） 若 21 pp >,则 MTT MP lhx +=?=? 1 1)(,其中
12
21
qp
qp=l；
（ 2） )1)(( )1(
21
M
M
pp
MET
l
l
+?
=,
21,设 }0:{ ≥nnx 独立同分布,
2
1
2
1
11
~nx,∑ = ≥== nk kn nSS 10 1,,0 x,
0,max
0
≥=
≤≤
nSM k
nkn
,证明 }0:{ ≥nSn 及 }0:{ ≥? nSM nn 都是 Markov 链,
22,假定 }1,{ ≥nnx 独立同分布,,)1(,)( ≥== kkP kn ax,对于 0≥n 定义
≥++<≤++
<=
+ 1,,
,0
111
1
knk
n
kk
n xxxx
xh
LL,∑ = =?=
n
j jn n
h xxV
0 0 )0(,,
证明 }0:{ ≥nnV 是常返的不可约 Markov 链,而且它是正常返的充要条件为 ∑∞= ∞<1k kka,
23,设 Markov 链 nx 有 N 个状态,而 i 为常返态,求证存在常数 q,0<q<1,使得当 Nn > 时,从状态 i
出发首次返回 i 的时间 it 满足 ni qinP <=> )|( 0xt,
24,证明对于状态空间为 S 的 Markov 链有
(1) 对于任意 Sji ∈,,有 ijij pf =)1(,)1(,)()1( ≥= ∑
≠
+ nfpf n
kjik
jk
n
ij,
139
(2) 在 j 固定时,}:{ Sif ij ∈? 是无穷个线性方程组 ∑
≠
+=
jk
ijkiki pxpx 以初值为
),0{ )0( Sixi ∈?= 的迭代解 ),0{ * Sixi ∈?=,即 )(,)(* Sixx ni
n
i ∈?= ∑,而
∑
≠
+ +=
jk
ij
n
kik
n
i pxpx
)()1(,
(3) 上面的迭代解 ),0{ * Sixi ∈?= 是方程 ∑
≠
+=
jk
ijkiki pxpx 的最小非负解,
25,设取值于非负整数的 Markov 链的状态为 },2,1,0{ L,转移矩阵为
=
OO
pq
pq
pqq
P
dd )1(
1
,
求吸收概率 1,0 ≥if i,
26,袋中有黑白两色的球共 m 个,每次从中随机地取出一个球后,放进一个不同色的球,令 nx 为取了 n
次后袋中的白球数,证明它是正常返不可约 Markov 链,并求其平稳分布,
27,有 m 个白球与 m 个黑球 混放在两个袋中,每个袋中各 m 个,在每个袋中各取出一个,互相交换后放
回袋中,令 nx 为交换了 n 次后在第一个袋中的白球数,证明它是正常返不可约 Markov 链,并求其平稳
分布,
28,若 Markov 链 nx 具有双随机的转移矩阵,即转移矩阵还满足 1=∑ ij
i
p,证明
(1) 如果状态只有有限个,那么它 们都是正常返的,
(2) 如果状态只有有限个,且链是不可约的,那么它具有均匀的平稳分布,
(3) 如果状态空间为无限,且链是不可约的,那么它不是正常返的,
29,设 Markov 链正常返不可约,其平稳分布为 (=p ),,10 Lpp,定义倒逆转移矩阵为
ji
i
j
ij pp p
p=^
,证明它也是不可约正常返的,
30,若 Markov 链 nx 的转移矩阵满足,存在非负数列 nu 及一个状态 k 使
∞<=∑? jkj
j
upd,)(,1 kiuup ijij
j
≠?≤∑,
(1) 作序列 jnij
i
n
iii upuuu
)()1()1(,∑== +,证明
)1()()2( 1)1( ++ +?+≤ n
i
n
ik
n
i upu d,
140
(2) 证明 )1(1 11
)2(
)(
1 n
up
n
im
ik
n
m
+≥∑
= d
,
(3) 如果 nx 还是不可约的,那么它是正常返的,
31,设 Markov 链的转移矩阵为
O
L
1
1
210 aaa
( 0,0 ≥> iai ),证明它是常返不可约,,而且它是正常返的充要条件为 ∞<= ∑
∞
=
n
n
na
1
m,在条件成立时平稳分布为 (=p ),,10 Lpp,其中
),1,0(1 L== ∑
∞
=
ian
in
i mp,
32,设 Markov 链的转移矩阵为
M
O2
11
00
1
1
q
( L,1,0,0 =∞<< iqi ),证明
(1) 它是非常返的 充要条件是 ∞<∑ i
i
q ;
(2) 它是正常返的充要条件是 ∞=∑ i
i
q,且 =m ∞<+?
∞
=
∑ )1()1(1 10
1
i
I
qq L,在条件成立时平稳分布为 (=p =),,,210 Lppp )),1)(1(,1,1(1 100 Lqqqm,
33,设 Markov 链的转移矩阵满足
),1,0,1,(0,0,0 1,1,LL?=>=≥=>= +? ipprpqp iiiiiiiii
给出具有平稳分 布的条件,并求出其平稳分布,
34,设 nx 是不可约的且具有平稳分布的 Markov 链,而 }{ nX 是与此 Markov 链独立的独立同分布随机序
列,且
LL
LL
k
n pp
k
1
1~x
,记
nXXn ++
= L
1
xh,证明 nh 也是不可约正常返 Markov
链,并求它的转移矩阵,再说明它与 nx 有相同的平稳分 布,
35,设
nnnn h
xxh,1,1 ++=+ L 为分支链,满足 )0()( 1,1 ≥== kpkP kx,
(1) 假定 1210 =++ ppp,证明此分支链以概率为 1 灭绝的充要条件为 20 pp ≥,
141
(2) 假定 13210 =+++ pppp,证明此分支链以概率为 1 灭绝的充要条件为 230 2 ppp +≥,
(3) 假定 13 =p,求此分支链以灭绝的概率,
(4) 假定 )10,10,1( rarkarp kk?≤<<<≥=,求此分支链以灭绝的概率,
(5) 假定 pppp =?= 10,1,求此分支链灭绝时间的分布,
