第1章 离散时间的马尔可夫链§1 随机过程的基本概念定义1 设(,,)P ΩF 是概率空间，(, )E E 是可测空间，T 是指标集. 若对任何t T ∈，有:t X E Ω→，且t X ∈F E ，则称{}(), t X t T ω∈是(, , )P ΩF 上的取值于(,)E E 中的随机过程，在无混淆的情况下简称{(), }t X t T ω∈为随机过程，称(,)E E 为状态空间或相空间，称E 中的元素为状态，称T 为时间域. 对每个固定的ω∈Ω，称()t X ω为{}(), t X t T ω∈对应于ω的轨道或现实，对每个固定的t T ∈，称()t X ω为E 值随机元. 有时()t X ω也记为 设T ⊂R ，{}, t t T ∈F 是F 中的一族单调增的子σ代数（σ代数流），即① t t T ∀∈⇒⊂F F ，且t F 是σ代数； ② , , s t s t T s t ∀∈<⇒⊂F F . 若 ()t t X t T ∈∀∈F E ，则称{}, t X t T ∈是{}t F 适应的随机过程，或适应于{}t F 的随机过程.特别地，若令 是由{}, , s X s t s T ≤∈所生成的σ代数，则{}, t X t T ∈是{}t F 适应的随机过程. 当1(, )(, )E =R E B 时，称{}, t X t T ∈为实值随机过程； 当(, )(, )E =C C E B 时，称{}, t X t T ∈为复值随机过程；当(, )(, )nn E =R E B 时，称{}, t X t T ∈为n 维随机过程；当E 是可列集（有限集）时，称{}, t X t T ∈为可列（有限）随机过程；当, T =+R R 或[], a b 时，称{}, t X t T ∈为连续参数的随机过程；当T =Z 或+Z 时，称{}, t X t T ∈为离散参数的随机过程（随机序列）；当, (), n n n T =+R R Z 或() (2)nn ≥+Z 时，称{}, t X t T ∈为随机场.随机过程的四种类型：（1）指标集T 离散，状态空间E 离散的随机过程； （2）指标集T 离散，状态空间E 连续的随机过程； （3）指标集T 连续，状态空间E 离散的随机过程； （4）指标集T 连续，状态空间E 连续的随机过程.然而，以上分类是表面的，更深刻的是按随机过程的概率结构而分类.例如：马尔可夫（Markov ）过程、平稳过程、独立增量过程、二阶矩过程、正态过程、泊松（Poisson ）过程、生灭过程、分枝过程、更新过程、鞅等. 对于随机过程{}, t X t T ∈而言，可以这样设想，有一个作随机游动的质点M ，以t X 表示在时刻t 质点M 的位置，于是{}, t X t T ∈描绘了质点M 所作的随机运动的变化过程，一般把“t X x =”形象地说成“在时刻t 质点M 处于状态x ”. 定义2 设{}, t X t T ∈是概率空间(,,)P ΩF上的、以(,)E E 为状态空间的随机过程，T =+R （或R 或直线上的任一区间）.如果A ∀∈E ，有则称{}, t X t T ∈是可测的. 设{}, t t T ∈F 是F 中的一族单调增的子σ代数. 如果, ,t T A ∀∈∈E有则称{}, t X t T ∈关于{}, t t T ∈F 循序可测.命题1 设:t X E Ω→， ()t t X t T ∈∀∈F E ，{}, t t T ∈F 是F中的一族单调增的子σ代数.如果{}, t X t T ∈关于{}, t t T ∈F 循序可测，则{}, t X t T ∈是可测的. 定义3 设{}, t X t T ∈是随机过程，称 为随机过程{}, t X t T ∈的一维分布函数；称为随机过程{}, t X t T ∈的二维分布函数；一般地，称 为随机过程{}, t X t T ∈的n 维分布函数；而称 为随机过程{}, t X t T ∈的有限维分布函数族.随机过程{}, t X t T ∈的有限维分布函数族F 具有下列性质：1. 对1n ∀≥，12,,,n t t t T ∀∈L ，及12,,,n t t t L 的任意排列12,,,n i i i t t t L ，有121212,,,,,,12(,,,)(,,,)i i i n n n t t t i i i t t t n F x x x F x x x =L L L L （对称性）2. 对1m n ∀≤≤，有12121,,,12,,,,,,12(,,,)(,,,,,,)m m m n t t t m t t t t t m F x x x F x x x +=+∞+∞L L L L L L （相容性）注 若知道了随机过程{}, t X t T ∈的有限维分布函数族F ，便知道了这一随机过程中任意有限个随机变量的联合分布，也就可以完全确定它们之间的相互关系. 可见，随机过程的有限维分布函数族能够完整地描述随机过程的统计特征. 但是在实际问题中，要知道随机过程的有限维分布函数族是不可能的，因此，人们想到了用随机过程的某些数字特征来刻画随机过程. 定义4 设{}, t X t T ∈是随机过程，称为{}, t X t T ∈的均值函数；称 为{}, t X t T ∈的方差函数；称 为{}, t X t T ∈的协方差函数；称 为{}, t X t T ∈的相关函数.注 若{}, t X t T ∈是复值随机过程，则方差函数的定义为协方差函数的定义为 相关函数的定义为 性质（1）(,)(), C t t D t t T =∈；（2）(,)(,)()(), ,C s t R s t m s m t s t T =-∈； （3）若()0m t ≡，则 (,)(,), ,C s t R s t s t T =∈.§2 马尔可夫链的定义在实际中有一类很广泛的随机过程，其特点是：过去只影响现在，而不影响将来. 这种随机过程称为马尔可夫过程. 状态离散的马尔可夫过程称为马尔可夫链，本章介绍时间离散的马尔可夫链（简称马尔可夫链）.马尔可夫（Markov ）过程的研究始于1906年，是随机过程的一个重要分支，它在近代物理、生物学、管理科学、信息处理、自动控制、金融保险等方面有着许多重要应用. 在本章中，无特别声明我们总是假设：1. 参数集合{}0,1,2,T=L ；2. 状态空间{}0,1,2,S =L 或{},2,1,0,1,2,S =--L L 或其子集.定义5 设{}, 0n X n ≥是定义在概率空间(, , )P ΩF上的随机过程，状态空间为S . 若对于任意的1n ≥及任意的整数120,n t t t t ≤<<<<L 12,,,,n i i i j S ∈L ，有 则称{}, 0n X n ≥为马尔可夫链，简称马氏链. 等式()*称为马氏性或无后效性，且假定()*式两端的条件概率都有意义（以下涉及到条件概率的式子都作类似的假定）. 定理1 随机过程{}, 0n X n ≥是马尔可夫链的充要条件是对任意的1n ≥及任意的12,,,,n i i i j S ∈L ，有§3 转移概率对于马尔可夫链{}, 0n X n ≥，描述它概率性质最重要的是它在时刻m 的一步转移概率{}1(), ,ij m m p m P X j X i i j S +===∈.马尔可夫链是描述某些特定的随机现象的数学模型，而产生这种特定的随机现象的具体模型一般称为系统，因此我们经常把事件{}m X i =说成是在时刻m 时系统处于状态i ，把{}1m m P X jX i +==说成已知在时刻m 时系统处于状态i ，而在时刻1m +时系统转移到状态j 的概率等等.定义6 设{}, 0n X n ≥是状态空间为S 的马尔可夫链，称为系统在时刻m 时处于状态i 的条件下， 经n 步转移到状态j 的n 步转移概率，简称时刻m 的n 步转移概率.显然，()()n ij p m 具有下列性质： （1）()()0, ,n ij p m i j S ≥∈；（2）{}()()1, n ij m n m j Sj Sp m P X j X i i S +∈∈====∈∑∑. 上述性质说明了，对于任意给定的i S ∈及0, 1m n ≥≥，{}()(), n ijpm j S ∈是一个概率分布. 规定： （1）(1)()()ij ij p m p m =；（2）(0)1, ,()0, .ijij i j p m i j δ=⎧==⎨≠⎩ 若()()n ij p m 与m 无关，则称{}, 0n X n ≥是时齐的或齐次的马尔可夫链. 此时，记()()(), ,, 1n n ij ij p p m i j S n =∈≥；一步转移概率记为(1), ,ij ij p p i j S =∈.对时齐的马尔可夫链{}, 0n X n ≥，有以下恒设马尔可夫链{}, 0n X n ≥是时齐的，并简称为马尔可夫链.性质 马尔可夫链{}, 0n X n ≥的n 步转移概率()n ij p 具有下列性质（1）(),,0n ij i j S p ∀∈≥； （2）(),1n ij j Si S p ∈∀∈=∑. 定理2（Chapman-Kolmogorov ） 设()n ijp 是马尔可夫链{}, 0n X n ≥的n 步转移概率，则 ,,,0i j S m n ∀∈≥，有()()()m n m n ij ik kj k Sp p p +∈=∑ （C-K 方程）证明{}{}{}()00, m n ij m n m m n k Sp P X j X i PX k X j X i +++∈=======U定理3 马尔可夫链{}, 0n X n ≥的一步转移概率ij p 可以确定所有的n 步转移概率()n ij p .证明 由C-K 方程，显然. 记()()(1),,(), ()n n ij i j S ij i j S p p ∈∈===PP P . 称()n P 为马尔可夫链{}, 0n X n ≥的n 步转移矩阵，称P 为马尔可夫链{}, 0n X n ≥的（一步）转移矩阵. 此时，C-K 方程可表示为()()()m n m n +=P P P 且()n n =P P .定义7 设{}, 0n X n ≥是马尔可夫链，对任意的0n ≥，称{}π()i n n P X i ==，i S ∈为绝对概率，特别地，称{}0π(0), i P X i i S ==∈为初始概率.显然，绝对概率和初始概率具有下列性质：故对任意0n ≥，{}π(), i n i S ∈是概率分布，通常称为绝对（概率）分布；特别，{}π(0), i i S ∈称为初始（概率）分布. 记{}{}(0)π(0), ()π()i i i S i S n n ∈∈∏=∏=.定理4 设{}, 0n X n ≥是马尔可夫链， 则它的任意有限维概率分布完全由初始分布和一步转移概率决定.证明 对任意的1n ≥，任意的整数120n t t t ≤<<<L 及任意的12,,,n i i i S ∈L ，有§4 若干例子定义8 设012, , ,ξξξL 是取整数值的独立同分布的随机变量序列，令0nn kk X ξ==∑，则称{}, 0n X n ≥为随机游动.定理5 随机游动{}, 0n X n ≥是时齐的马尔可夫链. （证明略）例1（无限制的随机游动）若随机游动{}, 0n X n ≥的状态空间为{,2,1,S =--L }0,1,2,L ，且转移概率为其中01,1p q p <<=-. 求：n 步转移概率()n ijp . 解 设在n 步转移中，向右移动x 步，向左移动y 步，则经n 步从i 到达j ，x 和y 应满足,x y n x y j i +=-=-. 所以由于, x y 只能取正整数，故()n j i +-与()n j i --必须是偶数. 又因在n 步转移中有x 步向右移动，故经n 步转移由i 到j 共有C xn种方式，于是 特别例2（带有一个吸收壁的随机游动） 设{}, 0n X n ≥是随机游动，其状态空间为{}0,1,2,S =L ，若转移概率为则称{}, 0n X n ≥为带有吸收壁0的随机游动. 其转移矩阵为例3（带有两个吸收壁的随机游动） 设{}, 0n X n ≥是随机游动，其状态空间为{}0,1,2,,S b =L ，其转移概率为其转移矩阵为例4（带有一个反射壁的随机游动） 设{}, 0n X n ≥是随机游动，其状态空间为{}0,1,2,S =L ，其转移概率为 其转移矩阵为例5（带有两个反射壁的随机游动） 设{}, 0n X n ≥是随机游动，其状态空间为{}, 0n X n ≥，其转移概率为 其转移矩阵为例6（带有弹性壁的随机游动） 设{}, 0n X n ≥是随机游动，其状态空间为{},2,1,0,1,2,S =--L L ，其转移概率为其转移矩阵为 例7 设{}, 0n X n ≥是只有两个状态（{}0, 1S =）的随机游动，其转移矩阵为这里p q +未必等于1. 求()n P ，0lim π()n n →∞，1lim π()n n →∞.解 ()()()0001()()1011n n n n n p p p p ⎛⎫= ⎪⎝⎭P由C-K 方程，得同理可求()()()011011, , n n n p p p ，故 设初始分布为{}01(0)π(0), π(0)∏=，则故0lim π()n q n p q →∞=+，同理 1lim π()n pn p q→∞=+.例8 设{}, 0n X n ≥是马尔可夫链，状态空间{}1,2,3S =，转移矩阵为初始分布为{}{}123π(0), π(0), π(0)16, 12, 1=，求（1）二步转移矩阵(2)P ；（2）{}132,1P X X ==；（3）{}32102,2, 22PXX X X =≠≠=.解 （1）(2)2143401434014338141412141412151403414034143163716⎛⎫⎛⎫⎛⎫ ⎪⎪ ⎪=== ⎪⎪ ⎪ ⎪⎪ ⎪⎝⎭⎝⎭⎝⎭PP .（2）由全概率公式、乘法公式、马氏性，得3(2)2211π(0)i i i p p ==∑ （注：也可直接由定理4得到） （3）由加法公式、乘法公式、马氏性，得 例9 设随机游动{}, 0n X n ≥的状态空间{}0,1,2,,S b =L ，其中0和b 是吸收壁，初始状态为a ，转移概率为 求质点被0点吸收的概率.解 设i u 表示质点初始位置为i 而被0点吸收的概率，则 由于1 p q +=，故11()()i i i i p u u q u u +--=-.（1）若12 p q ==，则11i i i i u u u u C +--=-=（常数），故10, .i i i u C u u iC u -=+=+ 因01, 0b u u ==，故1C b =-，从而1i i u b =-+，故1a au b=-.（2）若 p q ≠，则从而相加，得 011()(1)1()bb q p u u u q p -=+--，所以 故§5 状态的分类设{}, 0n X n ≥是马氏链，S 为状态空间，ij p 为转移概率.定义9 设A S ⊂，令称A T 为{}, 0n X n ≥首达A 的时刻（或A 的首达时），A T 是随机变量，其可能值为1,2,,.+∞L 当A为单点集{}j 时，记{}j T 为j T . 令则()n ij f 表示系统从状态i 出发， 经n 步首次到达状态j 的概率.利用乘法公式、马氏性易知：()n ii f 表示系统从i 出发， 经n 步首次返回i 的概率. 下面的定理是联系转移概率()n ij p 和首达概率()n ijf 之间关系的常用定理.定理6 对任意状态 , , 1i j S n ∈≥，有 ()()()1.nn m n m ijij jj m p f p -==∑证明 {}{}()00,n ij n j n p P X j X i P T n X j X i ====≤==令则ij f 表示系统从状态i 出发，经有限次到达状态j 的概率（也可以说成系统从状态i 出发，迟早要到达状态j 的概率）. 显然有特别，ii f 表示从状态i 出发，迟早要返回状态i 的概率.定义10 若1ii f =，则称i 是常返状态；若1ii f <，则称i 是非常返状态或滑过状态. （显然，吸收状态是常返状态）对于常返状态i ，因{}01ii i f P T X i =<∞==，这表明，从状态i 出发必定要返回它自身.记{}{}:, 1, :, 1Rii N ii S i i S f S i i S f =∈==∈<，则,. R N R N S S S S S φ==U I例10 设马氏链{}, 0n X n ≥的状态空间为{}1,2,3,4S =，转移矩阵为试判别状态的常返性.解 (1)()111114,0(2)n f f n ==≥ 1114.f = 故{}{}2,3,4,1.R N S S ==记00(),()ij j i i E T X i E T X i μμ====，则ij μ表示系统从状态i 出发，首达状态j 的平均时间；i μ表示系统从状态i 出发，首次返回i 的平均时间. 记j N 表示系统经过j N 的次数，j N 是随机变量，()j n I X 表示系统在时刻n 经过状态j 的次数，即则1().j jn n N IX ∞==∑记00(), ()ij j i i m E N X i m E N X i ====，则ij m 表示系统从状态i 出发，经过状态j 的平均次数；i m 表示系统从状态i 出发，返回状态i 的平均次数.定理7 设, i j S ∈，则 ()()11, .n n ij ij i ii n n m pm p ∞∞====∑∑证明 001()(())ij j jn n m E N X i E IX X i ∞=====∑定理8 设 , i j S ∈，则{}0, ,0,.ijR j N f j S P N X i j S ∈⎧=∞==⎨∈⎩证明 {}{}{}0001lim j j j n n P N X i P N n X i P N n X i ∞→∞=⎧⎫=∞==≥==≥=⎨⎬⎩⎭I而 故推论 设i S ∈，则 {}01,,0, .R i N i S P N X i i S ∈⎧=∞==⎨∈⎩该推论说明了定义6的合理性，即：如果状态i 是常返的，则以概率1，系统无穷次返回状态i ；如果状态i 是非常返的，则以概率1，系统只有有限次返回状态i ，亦即系统无穷次返回状态i 的概率为0. 定理9 设 , i j S ∈，则证明 （1）若 , 0R ij j S f ∈=，则 1n ∀≥，有()0n ij f =，由定理6知， 1n ∀≥，有()0n ij p =，所以0()0ij j m E N X i ===.（2）若 , 0R ij j S f ∈>，则由定理8知，{}00jPNX i =∞=>，所以ij m =0()j E N X i β==∞.（3）若 N j S ∈，则由定理8知，{}00jPNX i =∞==，所以推论 设 i S ∈，则 0,,()(1), .R i i iiii N i S m E N X i f f i S ∞∈⎧===⎨-∈⎩定义11 设 , i j S ∈，若 1n ∃≥，使()0n ij p >，则称状态i 可达状态j ，记为i j →；若 1n ∀≥，有()0n ij p =，则称状态i 不可达状态j ，记为i j →/；若i j →且j i →，则称状态i 和状态j 相通（或互通），记为i j ↔.定理10 （1）若i k →且kj →，则i j →；（2）若i k ↔且k j ↔，则i j ↔.证明 因i k →且k j →，所以 1, 1m n ∃≥≥，使得()()0, 0m n ik kj p p >>，由C-K 方程，有()()()()()0m n m n m n ij il lj ik kj l Sp p p p p +∈=≥>∑，故i j →.（2）由（1）易知（2）成立.定理11 设 , i j S ∈，则（1）0ij i j f →⇔>；（2）0ij ji i j f f ↔⇔>. 证明 只证明（1）. ""⇒ 设i j →，则 1n ∃≥，使()0n ij p >，而因此，(1)(2)(), ,,n ij ij ij f f f L 中至少有一个大于0，从而()10m ij ij m f f ∞==>∑.""⇐ 设0ij f >，因()1m ij ij m f f ∞==∑，所以 1n ∃≥，使()0n ij f >，故即i j →. 定理12 （1）()1n Rii n i S p ∞=∈⇐⇒=∞∑；（2）()1n Nii n i S p ∞=∈⇐⇒<∞∑，这时必有()lim 0n iin p →∞=； （3）若, , , R i j S i S i j ∈∈→，则R j S ∈，且1ii ij ji jj f f f f ====. 证明 由定理7及定理9的推论即知（1）和（2）；（3）略. 对于常返状态，即R i S ∈，由于()11n ii ii n f f ∞===∑，因此{}(), 1n ii f n ≥是一个概率分布，故易知 1.i μ≥定义12 设状态i 是常返的，即R i S ∈. 若i μ<∞，则称i 是正常返的；若i μ=∞，则称i 是零常返的. 记{}{}0:, , :, R R i R R i S i i S S i i S μμ+=∈<∞=∈=∞.定义13 （1）设C S ⊂，若 , i C j S C ∀∈∈-，有i j →/，则称C 是闭集；（2）设C S ⊂，若 , i j C ∀∈，都有i j →，则称C 是不可约的；（3）若S 是不可约的，则称马氏链{}, 0n X n ≥是不可约的（即 , i j S i j ∀∈⇒→）. 定理13 设C S ⊂，则下列各条等价 （1）C 是闭集； （2）(), ,10n ij i C j C n p ∀∈∉≥⇒=；（3） , 0ij i C j C f ∀∈∉⇒=.注 （1）若C 是闭集，则 , 1i C n ∀∈≥，有()1n ij j Cp ∈=∑. （2）整个状态空间S 是闭集，是最大的闭集；吸收状态i （即1ii p =）是闭集，是最小的闭集. 定理14 0,, R R R S S S +都是闭集.证明 设, .R R i S j S ∈∉ 若0ij f >，则i j →，故 R j S ∈. 矛盾，从而0ij f =，由上面的定理13，知R S 是闭集. 同理可证0, R R S S +也是闭集.例11 设{}, 0n X n ≥是马尔可夫链，状态空间为{}1,2,3,4,5S =，转移矩阵为问状态空间{}1,2,3,4,5S =中是否含有真的不可约的闭子集？{}, 0n X n ≥是否是不可约马尔可夫链. 解 易知，状态3是吸收状态，故{}3是闭集；{}{}{}1,4, 1,3,4, 1,2,3,4均是闭集；其中{}{}3, 1,4均是不可约的；因为S 含有真的闭子集，所以{}, 0n X n ≥为非不可约马尔可夫链.例12 设马尔可夫链{}, 0n X n ≥的状态空间为{}1,2,,9S =L ，状态之间的转移概率如图所示.由图可见：自状态1出发，再返回状态1的可能步数为显然T 的最大公约数为2. 但2T ∉，即自状态1出发经过2步不能返回状态1. 但我们仍把2定义为状态2的周期.定义i S ∈为状态i . 若{:n n ≥ 由定义知，如果状态i 有周期d ，则对一切[]0mod()n d ≠，都有()0n ii p =. 但这并不是说对任意的nd ，都有()0nd iip >. 如在例12中，状态1的周期2d =，但(2)110p =. 然而有如下结论.定理15 设状态i 的周期为d ，则存在正整数M ，对一切n M ≥，有()0nd iip >.证明 略（证明用到了初等数论的知识）.定理16 设状态i S ∈，如果集合{}()1, 0n iin n f ≥>非空，则证明 记 {}()G.C.D 1, 0n iid n n p =≥>，{}()G.C.D 1, 0n iic n n f =≥>，由定理6有 从而{}{}()()1, 01, 0n n iiiin n p n n f ≥>⊃≥>，于是有 1d c ≤≤. 如果1c =，则1d c ==. 如果1c >，只需证明d c ≥，为此只需证明c 是{}()1, 0n iin n p ≥>的公约数即可. 换言之，只需证明对于一切[]0mod()n c ≠，都有()0n ii p =.实际上，由c 的定义知，当1r c ≤<时，有()0r iif =. 于是，对1n c ≤<，有现假设当, 0,1,2,,1n kc r k N =+=-L 时，有()0n ii p =. 注意到[]0mod()n c ≠时，有()0n ii f =.则由定理6得于是，由归纳法知，当[]0mod()n c ≠时，有()0n ii p =.定理17 设状态i 常返且有周期d ，则()lim nd ii i n p d μ→∞=.（其中i μ为状态i 的平均返回时间，当i μ=∞时，约定0i d μ=）证明 见可数状态的马尔可夫过程，胡迪鹤，武汉大学出版社，1983，2526P -. 定义15 非周期的正常返状态称为遍历状态. 定理18 设i 是常返状态，则① i 是零常返状态⇐⇒()lim0n ii n p →∞=； ② i 是遍历状态⇐⇒()lim10n ii i n p μ→∞=>.证明 ① 设i 是零常返状态，则i μ=∞，由定理17，得 ()lim 0nd ii n p →∞=，而当[]0mod()n d ≠时，有()0n iip =，于是得()lim 0n ii n p →∞=. 反之，设()lim 0n ii n p →∞=，假设i 是正常返状态，则i μ<∞，于是由定理17，得()lim0nd ii n p →∞>，矛盾.② 设()lim10n ii i n p μ→∞=>，由①知，i 不能是零常返状态，从而只能是正常返状态，由定理17，得()limnd ii i n p d μ→∞=，注意到()()lim lim nd n ii ii n n p p →∞→∞=，得1d =，所以，i 是遍历状态. 反之，由定理17是显然的.定理19 设状态, i j S ∈，且i j ↔，则（1）i 与j 同为常返状态或同为非常返状态；如果同为常返状态，则它们同为正常返状态或同为零常返状态. （2）i 与j 有相同的周期.证明 （1）由于i j ↔，由可达的定义知存在1l ≥和1n ≥，使得由C-K 方程，对任意的1m ≥，总有()()()()()l m n l m n m ii ij jj ji jj p p p p p αβ++≥=，()()()()()l m n n m l m jj ji ii ij iip p p p p αβ++≥= 将上式两边从1到∞求和，得()()11l m n m iijj m m pp αβ∞∞++==≥∑∑，()()11l m n m jj iim m p p αβ∞∞++==≥∑∑ 可见，()1k ii k p ∞=∑与()1k jjk p∞=∑相互控制，所以它们同为无穷或同为有限. 由定理12知，i 与j 同为常返状态或同为非常返状态.若i 与j 同为常返状态，在以上的不等式中取极限，令m →∞，得()()lim lim l m n m ii jj m m p p αβ++→∞→∞≥， ()()lim lim l m n m jj ii m m p p αβ++→∞→∞≥因此，()limk iik p →∞与()lim k jj k p →∞同为正或同为零，由定理18知，i 与j 同为正常返状态或同为零常返状态. （2）设状态i 的周期为d ，状态j 的周期为c . 因为 ()()0, 0l n ij ji p p αβ=>=>，所以对任一使()0m jj p >的m ，必有()()()()()0l m n l m n m ii ij jj ji jj p p p p p αβ++≥=>，从而d 可除尽l m n ++. 又因为()()()0l n l n ii ij ji p p p αβ+≥=>，所以d 也可除尽l n +. 因此，d 可除尽m . 这说明d c ≤. 同理可证d c ≥. 故d c =，即状态i 与j 有相同的周期.注 状态的常返性与马尔可夫链的初始分布是无关的定理20 状态空间S 可唯一地分解成有限个或可列无穷个互不相交的子集之和，即(1)(2)N R R S S S S =U U UL ，且使得（1）每个()k R S 是常返状态组成的不可约闭集；（2）()k R S 中的状态或全是正常返状态，或全是零常返状态，且有相同的周期； （3）N S 是由全体非常返状态组成，自()k R S 中的状态不能到达N S 中的状态.定理21 周期为d 的不可约马尔可夫链，其状态空间S 可唯一地分解为d 个互不相交的子集之和，即0121d S S S S S -=U U UL U ，且使得自r S 中任一状态出发，经一步转移必进入1r S +中，0,1,2,,1r d =-L . （约定：0d S S =）证明 （1）任意取定一状态i S ∈，令{}()0, 0nd r r ij S j n p +=∃≥>使，0,1,2,,1r d =-L因S 是不可约的，即S 中的状态是互通的，故10d r r S S -==U.（2）若r t j S S ∃∈I （r t ≠），由定义知，必存在非负整数n 和m 使得()0nd r ij p +>，()0md t ij p +>.又由于j i ↔，必存在正整数h ，使()0h ji p >，于是由C-K 方程，有()()()0nd r h nd r h ii ij ji p p p +++≥>， ()()()0md t h md t h ii ij ji p p p +++≥>所以，d 能除尽nd r h ++，又能除尽md t h ++，从而d 能除尽 故d 能除尽r t -，注意到 01, 01r d t d ≤≤-≤≤-，故只能0r t-=，这说明，当r t ≠时，r t S S =∅I .（3）下面证明对任一r j S ∈，有11r jk k S p +∈=∑. 事实上最后一个等式是因：r j S ∈，由定义有()0nd r ij p +>，而当1r k S +∉时，由定义有(1)0nd r ikp ++=，由C-K 方程，有(1)()0nd r nd r ik ij jk p p p +++=≥，故0jk p =.（4）最后证明分解的唯一性，这只需证明{}0121,,,,d S S S S -L 不依赖于最初取定的状态i . 亦即只需证明：对取定的状态i ，如果, r j k S ∈，则对另取的状态i '，仍有, r j k S '∈（r '可以与r 不同）. 设对i 的分解为{}0121,,,,d S S S S -L ，对i '的分解为{}0121,,,,d S S S S -''''L ，又设, r j k S ∈，t i S '∈. 于是，当r t ≥时，自i '出发，以概率1只能在, ,r t r t d --+ 2,r t d -+L 等这些步上转移到j 或k ，从而, rt j k S -'∈；当r t <时，自i '出发，以概率1只能在(), 2, 3,d t r r t d r t d r t d --=-+-+-+L 等这些步上转移到j 或k ，从而, r t d j k S -+'∈.定理22 设{}, 0n X n ≥是周期为d 的不可约的马尔可夫链，则得一新的马尔可夫链{}, 0nd X n ≥，其一步转移矩阵为()()()d d ijp =P ，原马尔可夫链{}, 0n X n ≥按照定理21分解出的每个r S ，是新马尔可夫链{}, 0nd X n ≥的不可约的闭集，且r S 中的状态对新马尔可夫链是非周期的.（证明略）例13 设不可约马尔可夫链{}, 0n X n ≥的状态空间为{}1,2,3,4,5,6S =，周期为3d =，转移矩阵为对取定的状态1，易知 故{}{}{}0121,4,63,52SS S S ==U U U U . 马尔可夫链{}3, 0n X n ≥的转移矩阵为§6 n 步转移概率()n ij p 的渐近性质与平稳分布对()n ijp 极限性质，我们讨论两个问题. 一是()lim n ij n p →∞是否存在；二是其极限是否与i 有关. 这就与马尔可夫链的所谓平稳分布有密切联系.定理23 若j S ∈是非常返状态或零常返状态，则对任意i S ∈，有()lim0n ij n p →∞=.证明 因j S ∈是非常返状态或零常返状态，所以()lim 0n jj n p →∞=（由定理12和定理18）. 由定理6，对正整数Nn <，有固定N ，令n →∞，得再令N→∞，因()11k ij k f ∞=≤∑，所以()lim 0n ijn p →∞=. 推论1 如果马尔可夫链的状态空间S 是有限集，则S 中的状态不可能全是非常返状态，也不可能含有零常返状态，从而不可约的有限马尔可夫链的状态都是正常返状态. 证明 设{}0,1,2,,SN =L . 如果所有状态都是非常返状态，则对任意, i j S ∈，由定理23知()lim 0n ijn p→∞=，从而 ()10N n ijj p ==→∑（n →∞）. 矛盾. 如果S 中有零常返状态i ，设{}, Cj j S i j =∈→，若i j →，由定理12，有j i →，即C 中的状态是互通的，从而C 是不可约. 又由定理19知，C 中全是零常返状态，从而由定理14知，C 是闭集，即C 是不可约的闭集. 故()1n ij j Cp ∈=∑. 令n →∞，注意到C 是有限集，由定理23得()10n ij j C p ∈=→∑（n →∞）. 矛盾.于是，有限马尔可夫链的状态空间必含有正常返状态. 对于不可约的有限马尔可夫链，由于所有状态是互通的，故所有状态都是正常返状态.推论2 若马尔可夫链的非常返状态构成的集合N S 是有限集，则N S 不是闭集. 证明 若N S 是闭集，将产生矛盾.推论3 若马尔可夫链的状态空间S 有一个零常返状态，则必有无限多个零常返状态. 证明 设有零常返状态i S ∈，令{}, Cj j S i j =∈→，若C 是有限集，将产生矛盾.定理23考虑的是非常返状态或零常返状态的渐近分布，但当j S ∈是正常返状态时，()lim n ij n p →∞不一定存在，即使存在也可能与i 有关. 因此，我们退而研究()nd ijp 及()11n k ij k p n =∑的极限. 记()0(), 01md r ij ij m f r f r d ∞+==≤≤-∑. 则()ij f r 表示系统从状态i 出发，经[]mod()n r d =步首次到达状态j 的概率，显然定理24 设j S ∈是正常返状态，周期为d ，则 i S ∀∈及01r d ≤≤-，有证明 因为当[]0mod()n d ≠时，()0n jj p =. 所以于是，对1N n ≤<，有固定N ，令n →∞，由定理17，得再令N→∞，得于是，得推论 设周期为d 的、不可约的、正常返的马尔可夫链的状态空间为S ，则对一切, i j S ∈，有 其中10d k k SS -==U 为定理21中所给出. 特别，当1d =时，对一切, i j S ∈，有证明 在定理24中，令0r =，得 其中()0(0)md ij ij m f f ∞==∑. 如果i 与j 不在同一个k S 中，则由定理21知()0nd ij p =，注意到()()nd nd ij ij f p ≤，得()0nd ij f =，故(0)0ij f =.如果i 与j 同属于某个k S ，则当[]0mod()n d ≠时，()0n ij p =，从而()0n ij f =，故由定理12（3）知，1ij f =.定理25 对任意状态, i j S ∈，有证明 当j 为非常返状态或零常返状态时，由定理23知，()lim0n ij n p →∞=，故现设j 为正常返状态，周期为d . 注意到：如果有d 数列满足lim , 0,1,2,,1nd r r n a b r d +→∞==-L . 则必有令(), 0,1,2,,1nd r nd r ij a p r d ++==-L . 由定理24，有从而得推论 设不可约的、常返的马尔可夫链的状态空间为S ，则对 , i j S ∀∈，有 当j μ=∞时，约定10jμ=.证明 由定理19知，S 中的状态或全为正常返状态或全为零常返状态. 如果全为正常返状态，则, 1j ij f μ<∞=（定理12），由定理25得如果全为零常返状态，则j μ=∞，由定理25得 注 由定理25知，当j 为正常返状态时，尽管()lim n ijn p →∞不一定存在，但其平均值极限()11lim n k ij n k p n →∞=∑总存在. 特别，当马尔可夫链还是不可约时，()11lim n k ij n k p n →∞=∑与i 无关. 定义16 设{}, 0n X n ≥是状态空间为S 的马尔可夫链，如果存在实数集合{}π, j j S ∈，满足（1）π0, j j S ≥∈； （2）π1j j S∈=∑；（3）ππ, j i ij i S p j S ∈=∈∑.则称{}, 0n X n ≥是平稳的马尔可夫链，称{}π, j j S ∈为马尔可夫链{}, 0n X n ≥的平稳分布.对于平稳分布{}π, jj S ∈，有一般，有 ()ππ, 1n jiiji S p n ∈=≥∑.若初始分布{}π(0), jj S ∈是马尔可夫链{}, 0nXn ≥的平稳分布，则即对任何1n ≥，绝对概率等于初始概率.由此可见，当我们能判定马尔可夫链的初始分布{}π(0), jj S ∈是一平稳分布时，则该马尔可夫链在任何时刻的绝对分布{}π(), jn j S ∈都与初始分布相同. 事实上，平稳分布就是不因转移步数变化而改变的分布. 马尔可夫链处于状态j 的概率与时间推移无关，即具有平稳性.与平稳分布相关的是所谓极限分布的概念. 对于不可约的马尔可夫链，若状态j 是非周期的，则以后称{}1, jj S μ∈为极限分布.定理26 非周期不可约的马尔可夫链是正常返的充分必要条件是它存在平稳分布，且此平稳分布就是极限分布{}1, jj S μ∈.证明 “⇐”设存在平稳分布{}π, jj S ∈，于是有由于π0, j j S ≥∈和π1j j S∈=∑，故可以交换极限与求和顺序，两边令n →∞得因为π1j j S∈=∑，故至少存在一个π0k >，即10k μ>，从而 ()lim 10n ik k n p μ→∞=>，故k 是正常返的，从而马尔可夫链是正常返的，且所有的 1π0j j μ=>.“⇒”设马尔可夫链是正常返的，于是由C-K 方程，对任意正整数N （若S 是有限集，则不必如此），有 两边令m →∞，得 再令N→∞，得()()0111n n kj kj k k S j k k p p μμμ∞=∈⎛⎫⎛⎫≥= ⎪⎪⎝⎭⎝⎭∑∑ （*） 下面进一步证明，只能等式成立. 由 先令n →∞，再令N →∞，得将（*）式对j 求和，并假定对某个j ，（*）式为严格大于，则于是导致自相矛盾的结果 故（*）式对一切j 都只能成立等式再令n →∞，得 由此可知 故{}1, jj S μ∈是平稳分布.推论1 非周期的、不可约的、正常返的马尔可夫链的平稳分布是唯一的，就是极限分布. 推论2 若不可约的马尔可夫链的所有状态是非常返或零常返的，则不存在平稳分布. 证明 用反正法.设{}π, jj S ∈是马尔可夫链的平稳分布，则由定理23，有故 π0, j j S =∈，从而π0j j S∈=∑，与平稳分布π1j j S ∈=∑矛盾.例14 设马尔可夫链{}, 0n X n ≥的转移矩阵为求马尔可夫链的平稳分布及各状态的平均返回时间.解 因马尔可夫链是不可约的、非周期的，且状态有限，所以该马尔可夫链存在平稳分布{}{}123π, 1,2,3π, π, πjj ==，满足31ππ, 1,2,3ji ij i p j ===∑，即解上述方程组，得平稳分布为由定理26，得各状态的平均返回时间分别为§7 可逆性设马尔可夫链{}, 0n X n ≥的初始分布为{}π(0), i i S ∈，状态空间S 为可列集，n 步转移概率为()n ijp . 定义17 称马尔可夫链{}, 0n X n ≥可逆，如果：对任意的0n ≥，1m ≥，及任意的012,,,,m i i i i S ∈L ，均有定理27 马尔可夫链{}, 0n X n ≥可逆的充分必要条件是：对任意的, i j S ∈，有证明 “⇒”设马尔可夫链{}, 0n X n ≥可逆，由定义，对任意的0n ≥及任意的, i j S ∈，有{}{}00,,n n P X i X j P X j X i =====，从而即()()π(0)π(0)n n i ij j ji p p =，当1n =时，有π(0)π(0)i ij j ji p p =.“⇐”设对任意的, i j S ∈，有π(0)π(0)i ij j ji p p =. 则对任意的0n ≥，1m ≥，及任意的012,,,,m i i i i S ∈L ，由定理4，有由定义知，马尔可夫链{}, 0n X n ≥是可逆的.。