第4章马尔可夫链

1、第4章 马尔可夫链,马尔可夫过程按其状态和时间参数是连续的或离散的，可分为三类： （1）时间、状态都是离散的马尔可夫过程，称为马尔可夫链。 （2）时间连续、状态离散的马尔可夫过程，称为连续时间的马尔可夫链。 （3）时间、状态都连续的马尔可夫过程。,4.1 马尔可夫链的概念及转移概率,一、马尔可夫链的定义,上式是马尔可夫链的马氏性（或无后效性）的数学表达式。由定义知,可见，马尔可夫链的统计特性完全由条件概率,所决定。,二、转移概率,下面我们只讨论齐次马尔可夫链，通常将“齐次”两字省略。,称为系统状态的一步转移概率矩阵。它具有性质：,(2)式中对j求和是对状态空间I的所有可能状态进行的，此性质说明

2、一步转移概率矩阵中任一行元素之和为1。通常称满足上述(1)，(2)性质的矩阵为随机矩阵。,证 (1)利用全概率公式及马尔可夫性，有,(3)在(1)中令l=1，利用矩阵乘法可证。 (4)由(3)，利用归纳法可证。,定理1中(1)式称为切普曼-柯尔莫哥洛夫方程，简称C-K方程。它在马尔可夫链的转移概率的计算中起着重要的作用。(2)式说明n步转移概率完全由一步转移概率决定。(4)式说明齐次马尔可夫链的n步转移概率矩阵是一步转移概率矩阵的n次乘方。,由（1）知，绝对概率由初始分布和n步转移概率完全确定,（1）,证,三、马尔可夫链的一些简单例子,例1 无限制随机游动,设在第k步转移中向右移了x步，向左移

3、了y步，且经过k步转移状态从i进入j，则,从而,分析,例2 赌徒输光问题,赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为 ，求甲输光的概率。,这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a + b（即乙输光）这个游动就停止。这时的状态空间为0，1，2，c，c = a + b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。,考虑质点从j出发移

4、动一步后的情况,解,同理,根据全概率公式有,这一方程实质上是一差分方程，它的边界条件是,于是,设,则可得到两个相邻差分间的递推关系,于是,欲求,先求,需讨论 r,当,而,两式相比,故,当,而,因此,故,用同样的方法可以求得乙先输光的概率,由以上计算结果可知,例3 天气预报问题 设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨，今日有雨，明日有雨的概率为0.5；昨日有雨，今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为0.2。若星期一、星期二均下雨，求星期四下雨的概率。,解：设昨日、今日连续有雨称为状态(RR) ，昨日无雨、今日有雨称为状态(NR)，昨日有雨、今日无雨称为

5、状态2(RN)，昨日、今日无雨称为状态(NN)，于是天气预报模型可以看着一个四个状态的马尔可夫链，转移概率为,其中R代表有雨，N代表无雨。类似可得所有状态的一步转移概率。其一步转移概率矩阵为,其两步转移概率矩阵为,由于星期四下雨意味着过程说处的状态为或，因此星期一、星期二连续下雨，星期四下雨的概率为,某计算机房的一台计算机经常出故障,研究者 每隔15分钟观察一次计算机运行状态,收集了24小 时的数据 (共作97次观察) . 用1表示正常状态, 用0 表示不正常状态, 所得的数据序列如下:,111001000011110111111001111111110001101101,分析,状态空间: I

6、=0, 1.,例7,111011011010111101110111101111110011011111100111,96 次状态转移的情况:,因此, 一步转移概率可用频率近似地表示为:,以下研究齐次马氏链的有限维分布.,特点:,用行向量表示为,一维分布由初始分布和 转移概率矩阵决定,马氏链的 n 维分布,有限维分布仍由初始分布 和转移概率矩阵决定,一步转移概率为,例8,解,先求出二步转移概率矩阵,于是:,把两只黑球和两只白球平均放在两个坛子中, 每次从坛子中随机地各取出一球, 然后把被取出的球交换放到坛子中. 设 X(0) 表示开始时第一个坛子中的白球数,说明 X(n) 构成一个齐次马尔可夫

7、链, 并写出状态空间.,(2) 写出一步和二步转移概率矩阵.,例9,解,4.2 马尔可夫链的状态分类,一、状态分类,注： 从状态是否常返，如常返的话是否正常返，如正常返的话是否非周期等三层次上将状态区分为以下的类型：,证,证 令,从而由归纳法，我们有d=t证毕。,求从状态1出发经n步转移 首次到达各状态的概率。,解 如用（4.16）式计算将会很复杂，我们直接通过状态转移图（4.5）来计算。利用归纳法可得,同理可得,二、常返态的判别及其性质,对于常返态i，为判别它是遍历或零常返，我们不加证明地给出下面定理。,由C-K方程，总有,-(4.27),-(4.28),(2) 仍令,下面先看上节的一个例题

8、,(4.29),对固定的状态k，记,则由全概率公式,(4.30),上式两边求和注意U(k)=0，得,由（4.30）式得,由此知状态0是常返的。,4.3 状态空间的分解,引理得证。,闭集的意思是自C的内部不能到达C的外部。这意味着一旦质点进入闭集C中，它将永远留在C中运动。,称状态I为吸收的，如=1。显然状态i吸收等价于单点集i为闭集。,例4.12 无限制随机游动为不可约马氏链，各状态的周期为2且是正常返的。,我们知道自常返状态只能到达常返状态，因此I中全体常返状态组成一闭集C。在C中互通关系具有自返性，对称性和传递性，因而它决定一分类关系。按互通关系我们可得到状态空间的分解定理。,证 记C为全

9、体常返状态所成的集合, D=I-C为非常返状态全体。将C按互通关系进行分解，则,试分解此链并指出各状态的常返性及周期性。,可见1为正常返状态且周期等于3。含1的基本常返闭集为,从而状态3及5也为正常返且周期为3。同理可知6为正常返状态。,可见2是遍历状态。,IDC1C241,3,52,6。,定理4.11 周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交地子集之和，即,实际上,例4.14 设不可约马氏链的状态空间为C=1,2,3,4,5,6，转移阵为,由右状态转移图易见各状态的周期d=3。今固定状态i=1，令,故,此链在C中的运动如图,例 设X为一齐次马氏链，状态空间为Sa,b,c

10、,d,e，转移概率矩阵为,试分析其状态类型。,解 画出其状态转移概率图，如下页图所示。从图中不难发现Ca,c,e是一个状态闭集，Db,d是非常返态集，自然C是正常返的而且是非周期的。,如果我们能够发现转移矩阵能够重排为,这相当于将状态的次序重排为Sa,c,e,b,d。由上及P的标准形式即知非常返态集Db,d和遍历态集Ca,c,e。D和C也是S的两个等价类，显然C是闭集，D不是闭集。,例 设一齐次马氏链的状态空间为S1,2,3,4,5,6,7,8，转移概率矩阵为,例 设一齐次马氏链的状态空间为S1,2,3,4,5,6,7,8,9，其转移概率矩阵有如下形式：,其中*表示正的一个数，其余均为零。试确

11、定此齐次马氏链的状态类型。,例 设一齐次马氏链的状态空间为S0,1,2,，其转移矩阵如下（状态转移图如下）：,试讨论此链是常返链的充分必要条件。,4.4 的渐近性质与平稳分布,证 由定理4.4，对Nn我们有,推论1 有限状态的马氏链，不可能全是非常返状态，也不可能含有零常返状态，从而不可约的有限马氏链必为正常返的。,这就产生了矛盾。,矛盾,证毕。,推论2 如马氏链有一个零常返状态，则必有无限多个零常返状态。,则我们有下面一般性定理。,因此（4.37）式得证。,定理 4.15 对任意状态i,j有,二、平稳分布,根据归纳法可得,故有,事实上，因为,如此类推即可得。,再证必要性，设马氏链是正常返的，于是,由C-K方程，对任意正数N，有,下面要进一步证明等号成立，由,(I),将(I)式对j求和，并假定对某个j， (I)式为严格大于，则,于是有自相矛盾得结果：,故有,推论1 有限状态的不可约非周期马尔可夫链必存在平稳分布。,推论