统计计算 课件 4.1 马尔科夫链

第四章蒙特卡洛马尔科夫链（MCMC）4.1马尔科夫链4.2M-H方法4.3Gibbs抽样4.1马尔科夫链4.1.1马尔可夫链与一步状态转移概率矩阵4.1.2多步状态转移概率矩阵4.1.3不可约性和遍历性4.1.4非周期性4.1.1马尔可夫链与一步状态转移概率矩阵马尔可夫链是俄国数学家马尔可夫提出的，为了证明独立性不是大数定律和中心极限定理成立的必要条件，他构造了一个按条件概率相互依赖的随机过程，并证明其在一定条件下收敛于一组向量，该随机过程被称为马尔可夫链。称为随机过程，t为参数，T称为参数集。参数集T可以是时间集，也可以是长度、重量等，本章为时间集。称为随机过程在时刻t的状态，所有的状态形成一个集合称为状态空间，用S表示。常见的随机过程有随机游走、布朗运动和排队模型。随机过程的研究对象是随时间而变化的随机现象。为了描述该过程，需要一系列随机变量

来描述。把依赖于参数t的一族随机变量

某十字路口在时间［0,t］内违章的车辆数是一个与时间t有关的随机变量，对于固定的时间t，车辆数

是一个只取非负值的随机变量，t变化时，车辆数

是一个随机过程。随机过程是时间t的函数，在任意时刻进行观察时，它是一个随机变量一、马尔科夫过程

马尔科夫（Markov）过程是具有无后效性的随机过程。所谓无后效性是指：当过程在时刻所处的状态为已知时，过程在大于的时刻所处状态的概率特性只与过程在时刻所处的状态有关，而与过程在时刻以前的状态无关。

如果把时刻作为“现在”，以后的时刻作为“将来”，

以前的时刻作为“过去”，那么无后效性也可解释为：

过程在已知现在状态的条件下，将来的状态只与现在的状态有关，而与过去的状态无关。例1（直线上的随机游动）一个醉汉在路上行走，以概率p前进一步，以概率1-p后退一步（假定步长相同），以X(n)记他在时刻n

路上的位置，则{X(n)，n≥0}是随机过程。

很明显，已知醉汉现在的位置，将来的情况只与现在的位置有关，而与过去的情况无关。随机游动具有无后效性，所以它是一个马尔科夫过程。

马尔科夫过程按参数集T和状态空间（值域）S的情况一般可分为下列四类：

（1）时间离散、状态离散的马尔科夫过程，称为马尔可夫链（3）时间连续、状态离散的马尔科夫过程

（4）时间连续、状态连续的马尔科夫过程（2）时间离散、状态连续的马尔科夫过程1、贝努利过程，为一系列取值为0或者1的随机变量的集合。2、某股票的日k线图可以看出每日开盘价和收盘价是一个随机过程，如果只看几日的价格，它的过程是离散的，时间也是离散的，属离散型离散参数的随机过程。3、如果看一年的收盘价，则可以认为时间是离散的，而过程是连续的。4、由股价的日分时图可以看出股价是连续的，它对应的时间是连续的，属于连续型连续参数的随机过程。5、某急救中心在一昼夜接到的急救电话次数服从泊松分布，时间t是连续的，而次数是离散的，这属于离散型连续参数的随机过程。二、马尔科夫链“将来”“现在”“过去”则称为马尔科夫链,简称马氏链。“将来”“现在”定义1设随机序列的离散状态空间为S，若对于任意n,

（1）

（1）式中右边条件概率形式为称之为马尔科夫链在n

时刻的1步状态转移概率.记为

状态转移概率表示已知n

时刻处于状态i,经1个单位时间后过程处于状态j的概率。

k步状态转移概率表示已知n

时刻处于状态i,经k

个单位时间后过程处于状态j的概率。

若马尔科夫链的状态转移概率不依赖于n

，则称其为时齐马尔科夫链。这种马尔科夫链的状态转移概率仅与转移出发状态i、转移步数k、转移到达状态j有关，而与转移的起始时刻n

无关。注：以后只讨论时齐马尔科夫链。

此时，k

步状态转移概率可记为，即(2)定义2

(3)

当k=1时，称为一步状态转移概率，简记，显然，一步状态转移概率具有下列两个性质．（有限个或无限个）

一步状态转移概率可写成矩阵形式。对有限状态空间，矩阵(4)对无限状态空间，矩阵式(4)、(5)都称为一步状态转移概率矩阵。(5)

由一步状态转移概率性质可见，P

的所有元素都是非负的，且每行元素之和等于1.

如果一个方阵或无限矩阵（无限多行无限多列矩阵）的所有元素都是非负的。且每一行元素之和等于1，则称此矩阵为随机矩阵。因此，一步状态转移概率矩阵P是随机矩阵。定义3

例2贝努利试验设贝努利试验每次试验“成功”的概率为

p(0<p<1)，失败的概率为q(q=1-p)，且各次试验是相互独立的。“成功”用状态‘1’表示，“失败”用状态‘2’表示。第n

次试验的结果记为，进行无限多次试验得

由于试验的独立性，（l）式中的概率而因此，X(n)是马尔科夫链。于是，一步状态转移概率所以（1）式成立。

一般地说，独立同分布的离散随机变量序列亦是马尔科夫链。因为随机序列的将来不依赖于现在，更不依赖于过去。一步转移概率矩阵为例3直线上带吸收壁的随机游动一质点只能处在实数轴上

1，2，3，4，5五个点的位置，每次只能移动一格。当它

处在2，3，4位置时，下一时刻右移一格的概率为p(0<p<1),左移一格的概率为q(q=1-p).

当质点处在1位置时，它永远停留在1上；又当质点处在5位置时，它永远停留在5上。把1和5点看作分别放置有吸收壁。质点的随机游动用表示，其中表示第n时刻质点的位置。

12345一质点只能处在实数轴上1，2，3，4，5五个点的位置，每次只能移动一格。当它处在2，3，4位置时，下一时刻右移一格的概率为p(0<p<1),左移一格的概率为q(q=1-p).

当质点处在1位置时，它永远停留在1上；当质点处在5位置时，它永远停留在5上。一步转移概率如下：

例4直线上带反射壁的随机游动.

设在上例中，当质点处于2、3、4位置时，下一时刻的移动规则仍保持。当质点处于1位置时，下一时刻留在原位置的概率为q，右移一格的概率为p；当质点处于5位置时，下一时刻左移一格的概率为q，留在原位置的概率为p，可看作在1，5位置分别放置有反射壁。qp

显然，质点在第n时刻的位置X(n),n=0,1,2,...是马尔科夫链。它的一步转移概率矩阵是

例5直线上完全反射壁的随机游动设在例1中，当质点处于2、3、4位置时，下一时刻的移动规则仍保持。当质点处于1位置时，下一时刻必定移到2

位置；当质点处于5位置肘，下一时刻必定移到4位置，可看作在1，5位置分别放置具有完全弹性的反射壁。11

显然，质点随机游动的位置是一个马尔科夫链。它的一步转移概率矩阵是

例6直线上带完全反射壁允许停留的随机游动。

设，且。相同于例1．质点只能处于1,2,3,4,5五个点的位置。当质点处于2、3、4

时，下一时刻保留在原来位置的概率为r，右移一格的概率为p，左移一格的概率为q。当质点在1位置时,下一时刻必定移到2位置；当质点在5位置时，下一时刻必定移到4位置。11rqp

此例中，过程从中间位置出发时有三种可能情况：不动，右移一格，左移一格。

显然，质点作随机游动的位置是马尔科夫链。它的一步转移概率矩阵是:

例7正半轴上带反射壁的随机游动.

设，且。质点只能处在正整数点的位置上。当质点处于1位置时，下一时刻留在原位置的概率为q，

右移一格的概率为p。当它处在2、3、…位置时，下一时

刻右移一格的概率为p，左移一格的概率为q。q

显然，质点随机游动的位置是具有无限多个状态的马尔科夫链。它的一步转移概率矩阵为

n

步转移概率亦可以写成矩阵形式。对有限状态空间矩阵

在时齐马氏链中，

n步转移概率当时，称为高阶转移概率。4.1.2多步状态转移概率矩阵(6)因而n步转移概率矩阵P(n)是随机矩阵。和(有限个或无限个)它们都称为n

步转移概率矩阵。显然有对无限状态空间，矩阵0步转移概率阵为：特别规定：显然，0步转移概率矩阵也是随机矩阵。0步转移概率为：.例8甲乙两人进行比赛，每局比赛中甲胜的概率为，乙胜的概率为，平局的概率为每局赛后胜者计1分，负者计-1分，平局不计分，比赛中有人得2分时，比赛结束。表示比赛局后，甲的累积得分，.解-2-1012

(2).-2-1012（3）.例9.解（1）.（2）.（3）由（2）:.（4）（5）.解例10先求出转移概率矩阵P=1/201011/21/32/3.1/21/21/32/30101.注该例是在假定：“今日的天气只与昨日天气有关”的基础上建立的简单马尔科夫模型。这样的马尔科夫模型也称一阶马尔科夫模型。有时候，当前状态可能不是只与前一状态有关，而是与前K个状态有关，这种情形，也可以建立模型，称为K阶马尔科夫模型。比如若假定：“每日的天气与前两天气有关”这样可以建立2阶马尔科夫模型..假设观察某地的天气，按日依次是“晴，雨，晴，晴，晴，雨，晴……”，具有一定的规律。假设天气的变化具有马尔可夫性，即明天的天气只依赖于今天的天气，而与昨天及以前的天气无关。转移矩阵为根据这个马尔可夫链模型，可以计算第二天、第三天及之后的天气概率分布（状态分布）如果第一天是晴天的话，其天气概率分布（初始状态分布）为[1,0],

具有有限多个状态的马尔科夫链简称为有限马尔科夫链。

马尔科夫链理论中一个重要问题是讨论当时转移概率的极限。4.1.3不可约性和遍历性

在讨论遍历性时常需要区分状态空间是有限的还是无限的。此时可设它的状态空间。又设具有无限多个状态马尔科夫链的状态空间为不可约性指的是从任意一个状态出发都有一定的概率转移到其他状态，即所有的状态都是互相连通的，总能通过若干步后互相转移不可约性常返：从状态i出发总能再返回到状态i，则状态i是常返的正常返：从状态i出发首次返回到状态i，花费的时间的期望是有限的，则称状态i是正常返的任何两个状态都是连通的ReducibleMarkovChain1/2若初始状态为1，研究它对应的马尔科夫链的不可约性。使用状态转移概率矩阵计算10个状态。初始状态为1，则状态对应的初始向量X0为(1,0)不可约性初始状态为1，则状态对应的初始向量X0为(1,0)第1次的结果为：[[0.250.75]]第2次的结果为：[[0.31250.6875]]第3次的结果为：[[0.307291670.69270833]]第4次的结果为：[[0.307725690.69227431]]第5次的结果为：[[0.307689530.69231047]]第6次的结果为：[[0.307692540.69230746]]第7次的结果为：[[0.307692290.69230771]]第8次的结果为：[[0.307692310.69230769]]第9次的结果为：[[0.307692310.69230769]]第10次的结果为：[[0.307692310.69230769]无论从哪个初始状态出发，程序运行的结果都是同一个分布，即这个不变分布作为极限分布与初始状态无关。因此由转移概率，可根据不变分布预测以后的状态。因为经过一段时间迭代后，会呈现出一种稳定性，即极限分布是稳定的。

定义4若马尔科夫链转移概率的极限

(7)存在，且与i

无关，则称此马尔科夫链具有遍历性。

(8)

事实上，前者由转移概率的非负性即得，而后者在等式中让可得。此时，我们称为转移概率的极限分布。

易知，对有限马尔科夫链，上述得到的构成一个概率分布。即有则称它是平稳分布。

(9)

定义5若有限或无限数列满足：则称它是概率分布。如果一个概率分布满足

具有遍历性的有限马氏链转移概率的极限分布是平稳分布；具有遍历性的无限多个状态的马氏链，如果转移概率的极限是一个概率分布，那么它是平稳分布.下面介绍平稳分布。设有图上所示马尔可夫链，其转移概率矩阵为求其平稳分布例设有图上所示马尔可夫链，其转移概率分布如下，求其平稳分布。这个马尔可夫链的平稳分布并不唯一等皆为其平稳分布。马尔可夫链可能存在唯一平稳分布，无穷多个平稳分布，或不存在平稳分布下面仅讨论有限马尔科夫链的遍历性，先介绍一个定理。

定理3对有限马尔科夫链，如果存在正整数k，使

(10)则此链是遍历的，即

(11)的唯一解。满足条件(12)且极限分布是方程组

定理表明在（10）条件下极限分布中的概率都是正的，且在计算极限分布时只需求方程组（11)的满足约束条件（12）的解即可。它的所有元素都大于零，即在k=2时，(10)式成立，所以此链具有遍历性。因而有

例11

直线上带反射壁的随机游动，如果质点只能取1，2，

3三个点，其中含有零元素。现计算二步转移概率矩阵一步转移概率矩阵为(13)下面求极限概率。把(13)代入(11)式得有，这时极限分布为等概率分布。二步转移概率矩阵为例12直线上带完全反射壁的随机游动。

一步转移概率矩阵为如果质点只能取1、2、3三个点，

其中n是自然数。显然，转移概率的极限是不存在的。因而此链不具有遍历性。一般地有和三步转移概率矩阵二步转移概率矩阵例13

直线上带吸收壁的随机游动，如果质点只能取1、2、

3三个点.一般地，n步转移概率矩阵,显然，转移概率的极限存在，且一步转移概率矩阵为这个极限与i有关，所以此链不具有遍历性。其中含有零元素。逐个计算转移概率矩阵P(2),P(3),得

例14直线上带完全反射壁允许停留的随机游动.如果质点可以取1、2、3三个点.

设，此时，一步转移概率矩阵为(14)它的所有元素都大于零。因而此链具有遍历性，有下面求极限概率分布。把（14）式代入方程(11),得加上条件可以解得与例8相比，两者都是直线上带完全反射壁的随机游动，但是例8中马尔科夫链没有遍历性。而此链具有遍历性。这是由此链允许质点保持原位置（概率为r）所引起的。4.1.4非周期性周期性指的是由初始状态出发，经过一段时间的迭代后回到原来的初始状态，进而周而复始，循环。这种马尔可夫链的极限分布是不存在的下图的马尔可夫链是周期的转移概率矩阵其平稳分布是（1/3，1/3，1/3）。此马尔可夫链从每个状态出发，返回该状态的时刻都是3的倍数，{3,6,9}，具有周期性，最终停留在每个状态的概率都为1/3.例从初始状态

出发，求其他状态从其他两个状态出发，得到的结果也是一样的，即以后的每个状态都和状态x1相同。该马尔可夫链具