第4章 马尔可夫链

第4章马尔可夫链

马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类：（1）时间、状态都是离散的马尔可夫过程，称为马尔可夫链。（2）时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链。（3）时间、状态都连续的马尔可夫过程。2021/5/91§4.1马尔可夫链的概念及转移概率

一、马尔可夫链的定义

2021/5/92

上式是马尔可夫链的马氏性（或无后效性）的数学表达式。由定义知

可见，马尔可夫链的统计特性完全由条件概率

所决定。2021/5/93二、转移概率

2021/5/94

下面我们只讨论齐次马尔可夫链，通常将“齐次”两字省略。

2021/5/95称为系统状态的一步转移概率矩阵。它具有性质：

(2)式中对j求和是对状态空间I的所有可能状态进行的，此性质说明一步转移概率矩阵中任一行元素之和为1。通常称满足上述(1)，(2)性质的矩阵为随机矩阵。

2021/5/962021/5/972021/5/98证

(1)利用全概率公式及马尔可夫性，有

2021/5/99

(3)在(1)中令l=1，利用矩阵乘法可证。

(4)由(3)，利用归纳法可证。

定理1中(1)式称为切普曼---柯尔莫哥洛夫方程，简称C--K方程。它在马尔可夫链的转移概率的计算中起着重要的作用。(2)式说明n步转移概率完全由一步转移概率决定。(4)式说明齐次马尔可夫链的n步转移概率矩阵是一步转移概率矩阵的n次乘方。

2021/5/9102021/5/9112021/5/912由（1）知，绝对概率由初始分布和n步转移概率完全确定（1）证2021/5/9132021/5/914三、马尔可夫链的一些简单例子例1

无限制随机游动

2021/5/915

设在第k步转移中向右移了x步，向左移了y步，且经过k步转移状态从i进入j，则

从而

2021/5/916分析例2

赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为，求甲输光的概率。这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a+b（即乙输光）这个游动就停止。这时的状态空间为{0，1，2，…，c}，c=a+b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。2021/5/917考虑质点从j出发移动一步后的情况解同理根据全概率公式有这一方程实质上是一差分方程，它的边界条件是2021/5/918于是设则可得到两个相邻差分间的递推关系于是欲求先求需讨论r2021/5/919当而两式相比2021/5/920故当而因此故2021/5/921用同样的方法可以求得乙先输光的概率由以上计算结果可知2021/5/922例3

天气预报问题

设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨，今日有雨，明日有雨的概率为0.5；昨日有雨，今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2。若星期一、星期二均下雨，求星期四下雨的概率。

解：设昨日、今日连续有雨称为状态０(RR)，昨日无雨、今日有雨称为状态１(NR)，昨日有雨、今日无雨称为状态2(RN)，昨日、今日无雨称为状态３(NN)，于是天气预报模型可以看着一个四个状态的马尔可夫链，转移概率为

2021/5/923

其中R代表有雨，N代表无雨。类似可得所有状态的一步转移概率。其一步转移概率矩阵为2021/5/924其两步转移概率矩阵为2021/5/925

由于星期四下雨意味着过程说处的状态为０或１，因此星期一、星期二连续下雨，星期四下雨的概率为2021/5/9262021/5/9272021/5/928

某计算机房的一台计算机经常出故障,研究者每隔15分钟观察一次计算机运行状态,收集了24小时的数据(共作97次观察).用1表示正常状态,用0表示不正常状态,所得的数据序列如下:1110010011111110011110111111001111111110001101101分析状态空间:I={0,1}.例71110110110101111011101111011111100110111111001112021/5/92996次状态转移的情况:因此,一步转移概率可用频率近似地表示为:2021/5/930以下研究齐次马氏链的有限维分布.特点:用行向量表示为一维分布由初始分布和转移概率矩阵决定2021/5/931马氏链的n维分布有限维分布仍由初始分布和转移概率矩阵决定2021/5/932一步转移概率为例82021/5/933解先求出二步转移概率矩阵于是:2021/5/9342021/5/935

把两只黑球和两只白球平均放在两个坛子中,每次从坛子中随机地各取出一球,然后把被取出的球交换放到坛子中.设X(0)表示开始时第一个坛子中的白球数,说明X(n)构成一个齐次马尔可夫链,并写出状态空间.(2)写出一步和二步转移概率矩阵.例92021/5/936解2021/5/937§4.2马尔可夫链的状态分类

一、状态分类

2021/5/9382021/5/9392021/5/9402021/5/9412021/5/9422021/5/9432021/5/9442021/5/945注：

从状态是否常返，如常返的话是否正常返，如正常返的话是否非周期等三层次上将状态区分为以下的类型：

2021/5/946证

2021/5/947证

令

2021/5/948从而由归纳法，我们有d=t证毕。

2021/5/949求从状态1出发经n步转移首次到达各状态的概率。

解如用（4.16）式计算将会很复杂，我们直接通过状态转移图（4.5）来计算。利用归纳法可得

2021/5/950同理可得

2021/5/951二、常返态的判别及其性质

2021/5/9522021/5/9532021/5/954

对于常返态i，为判别它是遍历或零常返，我们不加证明地给出下面定理。

2021/5/9552021/5/9562021/5/9572021/5/9582021/5/959由C-K方程，总有------(4.27)2021/5/960----------(4.28)2021/5/961(2)仍令2021/5/9622021/5/9632021/5/964下面先看上节的一个例题2021/5/965(4.29)2021/5/966对固定的状态k，记则由全概率公式2021/5/967(4.30)上式两边求和注意

U(k)=0，得由（4.30）式得2021/5/968由此知状态0是常返的。2021/5/969§4.3状态空间的分解

2021/5/970引理得证。

闭集的意思是自C的内部不能到达C的外部。这意味着一旦质点进入闭集C中，它将永远留在C中运动。

2021/5/971

称状态I为吸收的，如=1。显然状态i吸收等价于单点集{i}为闭集。

2021/5/972例4.12

无限制随机游动为不可约马氏链，各状态的周期为2且是正常返的。

我们知道自常返状态只能到达常返状态，因此I中全体常返状态组成一闭集C。在C中互通关系具有自返性，对称性和传递性，因而它决定一分类关系。按互通关系我们可得到状态空间的分解定理。2021/5/973证

记C为全体常返状态所成的集合,D=I-C为非常返状态全体。将C按互通关系进行分解，则

2021/5/9742021/5/975试分解此链并指出各状态的常返性及周期性。2021/5/976可见1为正常返状态且周期等于3。含1的基本常返闭集为

从而状态3及5也为正常返且周期为3。同理可知6为正常返状态。

2021/5/977可见2是遍历状态。

I＝D∪C1∪C2＝{4}∪{1,3,5}∪{2,6}。

2021/5/9782021/5/9792021/5/980定理4.11周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交地子集之和，即

2021/5/9812021/5/982实际上

2021/5/9832021/5/984例4.14

设不可约马氏链的状态空间为C={1,2,3,4,5,6}，转移阵为2021/5/985由右状态转移图易见各状态的周期d=3。今固定状态i=1，令

故

此链在C中的运动如图

2021/5/9862021/5/9872021/5/9882021/5/9892021/5/990例

设X为一齐次马氏链，状态空间为S＝{a,b,c,d,e}，转移概率矩阵为

试分析其状态类型。

2021/5/991解

画出其状态转移概率图，如下页图所示。从图中不难发现C＝{a,c,e}是一个状态闭集，D＝{b,d}是非常返态集，自然C是正常返的而且是非周期的。

如果我们能够发现转移矩阵能够重排为

这相当于将状态的次序重排为S＝{a,c,e,b,d}。由上及P的标准形式即知非常返态集D＝{b,d}和遍历态集C＝{a,c,e}。D和C也是S的两个等价类，显然C是闭集，D不是闭集。

2021/5/992例设一齐次马氏链的状态空间为S＝{1,2,3,4,5,6,7,8}，转移概率矩阵为

2021/5/993例设一齐次马氏链的状态空间为S＝{1,2,3,4,5,6,7,8,9}，其转移概率矩阵有如下形式：其中*表示正的一个数，其余均为零。试确定此齐次马氏链的状态类型。

2021/5/994例设一齐次马氏链的状态空间为S＝{0,1,2,…,}，其转移矩阵如下（状态转移图如下）：

试讨论此链是常返链的充分必要条件。

2021/5/995§4.4

的渐近性质与平稳分布

2021/5/996证

由定理4.4，对N<n我们有

2021/5/997推论1有限状态的马氏链，不可能全是非常返状态，也不可能含有零常返状态，从而不可约的有限马氏链必为正常返的。这就产生了矛盾。

矛盾,证毕。

2021/5/998推论2如马氏链有一个零常返状态，则必有无限多个零常返状态。2021/5/999则我们有下面一般性定理。

2021/5/91002021/5/9101因此（4.37）式得证。

2021/5/91022021/5/91032021/5/91042021/5/9105定理

4.15对任意状态i,j有

2021/5/91062021/5/91072021/5/9108二、平稳分布

2021/5/9109根据归纳法可得

故有2021/5/9110事实上，因为

如此类推即可得。2021/5/91112021/5/9112

再证必要性，设马氏链是正常返的，于是

由C-K方程，对任意正数N，有

2021/5/9113下面要进一步证明等号成立，由

(I)

将(I)式对j求和，并假定对某个j，(I)式为严格大于，则

2021/5/9114于是有自相矛盾得结果：

故有

2021/5/9115推论1有