马尔可夫链课件

1第一节基本概念第二节状态的分类及性质第三节极限性态及平稳分布第四节Markov链的应用第一节基本概念2第一节基本概念一、Markov链的定义二、转移概率三、Markov链的例子四、n步转移概率，C-K方程第一节基本概念一、Markov链的定义3

过程(或系统)在时刻t0所处的状态为已知的条件下，过程在时刻t>t0所处状态的条件分布与过程在时刻t0之前所处的状态无关。

通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。第一节基本概念马尔可夫性(无后效性)用分布函数表述马尔可夫性：一、Markov链的定义过程(或系统)在时刻t0所处的状态为已知的条件下，过4定义设随机过程的状态空间为：若对任意的，及有马氏性…………则称为离散时间、离散状态的马尔可夫过程，或简称为马尔可夫链。定义设随机过程的状态空5

设是马尔可夫链，对任意的，计算的联合分布律二、转移概率

乘法公式

马氏性

即马尔可夫链的有限维分布完全由初始分布和条件概率确定.

马氏性设是马尔可夫链，对任意的6注

当固定时，一步转移概率实质上就是在的条件下，随机变量的条件分布律，所以条件分布律满足：

定义1设是马尔可夫链，记称为马尔可夫链在时刻时的一步转移概率。二、转移概率注当固定时，一步转移概率实质7

定义2

设是马尔可夫链，若其一步转移概率与时间无关，即则称为齐次马尔可夫链，称为从状态转移到状态的一步转移概率.

若马尔科夫链的状态空间是有限集，则称为有限状态的马尔科夫链；

若马尔科夫链的状态空间是可列集，则称为可列状态的马尔科夫链.二、转移概率定义2设是马尔可夫链，若其一8矩阵的每一行都是一条件分布律

记.称为齐次马尔可夫链的初始分布.

齐次马尔科夫链的有限维分布族完全由其一步转移概率矩阵

和初始分布

确定.则称矩阵为齐次马尔科夫链的一步转移概率矩阵.

定义3设是齐次马尔可夫链，其一步转移概率为，记二、转移概率矩阵的每一行都记9例1(一个简单的疾病死亡模型)三、马氏链的例子例1(一个简单的疾病死亡模型)三、马氏链的例子10

例2(0-1传输系统或简单信号模型)如图所示，只传输数字0和1的串联系统中，设每一级的传真率为p，误码率为q=1-p。并设一个单位时间传输一级，X0是第一级的输入，Xn是第n级的输出(n≥1)，那么{Xn,n=0,1,2…}是一随机过程，状态空间S={0,1}，而且当Xn=i为已知时，Xn+1所处的状态的概率分布只与Xn=i有关，而与时刻n以前所处的状态无关，所以它是一个马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为：……n21X0X1X2XnXn-1三、马氏链的例子例2(0-1传输系统或简单信号模型)……n21X011

例3(带有一个吸收壁的随机游动)质点在直线上作随机游动.在某一时刻质点位于，则下一步质点以概率向右移动一格到达；或以概率向左移动一格到达.但当质点一旦到达原点，则质点永远停留在原点，不再移动.状态称为吸收态.以表示质点在时刻的位置.则是齐次马尔可夫链，称其为带一个吸收壁的随机游动.求其一步转移概率矩阵.三、马氏链的例子例3(带有一个吸收壁的随机游动)质点在直线上作随机12

解：马尔科夫链的的状态空间为：一步状态概率为：一步状态概率矩阵为：三、马氏链的例子解：马尔科夫链的的状态空1313452

例4设一醉汉Q(或看作一随机游动的质点)在直线上的点集S={1,2,3,4,5}作随机游动，且仅在1秒、2秒等时刻发生游动，游动的概率规则是：如果Q现在位于点i(1<i<5)，则下一时刻各以的概率向左或向右移动一格，或以的概率留在原处；如果Q现在处于1(或5)这一点上，则下一时刻就以概率1移动到2(或4)这点上，1和5这两点称为反射壁，这种游动称为带有两个反射壁的随机游动。以Xn表示时刻n时Q的位置，说明{Xn,n=0,1,2…}是一齐次马氏链，并写出它的一步转移概率矩阵。三、马氏链的例子13452例4设一醉汉Q(或看作一随机游动的质点)在14解：它的一步转移概率矩阵为：

如果把1这点改为吸收壁，即Q一旦到达1这一点，则永远留在点1时，此时的转移概率矩阵为：三、马氏链的例子解：它的一步转移概率矩阵为：如果把1这点改为吸收壁，即15

例5(无限制随机游动)质点在直线上作随机游动.在某一时刻质点位于，则下一步质点以概率向右移动一格到达；或以概率向左移动一格到达.以表示质点在时刻的位置.则是状态无限的马尔科夫链，求其一步转移概率矩阵.解：马尔科夫链的的状态空间为：一步状态概率为：一步状态概率矩阵为：例5(无限制随机游动)质点在直线上作随机游动.在某一16称为马尔可夫链在时刻时处于状态经过时间后转移到状态的概率.设是马尔可夫链，其状态空间为①记马尔可夫链的步转移概率为四、n步转移概率、C-K方程②称为马尔可夫链在时刻时处于状态经过时间17称此式为切普曼－柯尔莫洛夫方程，简称C-K方程.

定理设是马尔可夫链，其状态空间为，则对任意的，有直观意义从状态出发经过步到达状态，可分成两步走：①先从状态出发经过步到达状态；②然后再先从状态出发经过步到达状态；

由马氏性知，后一阶段的状态转移与前一阶段的状态转移独立，故两个阶段的转移概率可相乘.四、n步转移概率、C-K方程称此式为切普曼－柯尔莫洛夫方程，简称C-K方程.定18ikjk0证明：四、n步转移概率、C-K方程ikjk0证明：四、n步转移概率、C-K方程19注记齐次马尔科夫链的步转移概率矩阵为：

则齐次马尔科夫链的切普曼－柯尔莫洛夫方程可用如下矩阵形式表示：四、n步转移概率、C-K方程注记齐次马尔科夫链的步转移概率矩阵为：则齐次马尔20四、n步转移概率、C-K方程四、n步转移概率、C-K方程21解：解：22

例(天气预测简单模型)假设明天是否下雨仅与今天的天气(是否下雨)有关，而与过去的天气无关.假设今天下雨、明天有雨的概率为，今天无雨而明天有雨的概率为；又假设把有雨称为状态天气，把无雨称为状态天气.记表示第天的天气状态.则是状态有限的马尔科夫链.1.求其一步转移概率矩阵；

2.若，且今天有雨，求第四天有雨的概率.四、n步转移概率、C-K方程例(天气预测简单模型)假设明天是否下雨仅与今天的23解一步状态概率矩阵为：②因为所以若今天无雨，第四天下雨的概率为0.5749①四、n步转移概率、C-K方程解一步状态概率矩阵为：②因为所以若今天无雨，第四天下雨的概率24第二节状态的分类及性质一、到达与相通二、首达时间与首达概率三、首达概率的基本性质四、状态的分类五、闭集和状态空间的分解第二节状态的分类及性质一、到达与相通25一、到达与相通一、到达与相通26一、到达与相通一、到达与相通27二、首达时间与首达概率二、首达时间与首达概率28二、首达时间与首达概率二、首达时间与首达概率29二、首达时间与首达概率二、首达时间与首达概率30三、首达概率的基本性质三、首达概率的基本性质31三、首达概率的基本性质三、首达概率的基本性质32三、首达概率的基本性质现在来推导基本性质2以此类推三、首达概率的基本性质现在来推导基本性质233三、首达概率的基本性质一旦确定了这些首达概率，便可用来计算各种概率和所关心的量如下：（1）系统初始状态为i在m次转移内进入状态j（至少1次）的概率为：（2）系统自状态i开始最终达到状态j的概率即可由下式给出：（3）系统自状态i开始最终回到状态i的概率为：三、首达概率的基本性质一旦确定了这些首34（4）状态i的平均循环时间为系统自离开状态i的时间开始直到后来首次回到状态i的时间止这段的加权平均时间。因此，

此外，状态i的期望持续期的长度为直到系统首次离开状态i时为止的加权平均时间。因此，期望持续时间为为了说明，可以考虑二类状态的马尔可夫链。应用以上方程，例如（4）状态i的平均循环时间为系统自35

对于平均持续时间，由前面方程得同理，平均循环时间为对于平均持续时间，由前面方程得同理，平均循环36同理，例以天气预测简单模型为例子，试确定（a）设今日为雨天，问后天首次又为雨天的概率如何？（b）设今日为雨天，问后五日内至少有一晴天的概率如何？（c）问持续晴天的期望长度为何？持续雨天的期望长度？（d）如今日为雨天，则直到下一雨天止，这段时间的期望长度为何？马尔可夫链课件37(a)从今天起两天以后首次为雨天的概率为：(b)后五日至少有一晴天的概率为：(c)持续晴天和持续雨天的平均天数分别为：(d)雨天的期望循环时间为：(a)从今天起两天以后首次为雨天的概率为：38四、状态的分类定义对于状态，如果，则称状态i为循环状态（常返态）；如果，则称状态i为瞬时状态（非常返态）。

在有两种状态的马尔可夫链的情况下，可用代入方程，中求出。如果为一阶转移概率，即，则，表明状态1和2为循环状态。另一方面，如果，则，表明状态2可能不再来到，因而，状态2是瞬时状态。

指系统自状态i开始，一定最终回到状态i；指系统自状态i开始将具有一个有限的概率不再回到状态i。四、状态的分类定义对于状态，39马尔可夫链课件40马尔可夫链课件41对于马尔可夫链中的状态j，如果其一阶转移概率为，则称此状态为吸收状态。因此，吸收状态被定义为一种状态，系统在此状态中除去它本身状态之外，不能再转移到任何其他状态中去。如果在马尔可夫链中存在着一种吸收状态，则系统最终将到达并进入该吸收状态。一个马尔可夫链可以含有一个以上的吸收状态。这种情况下，只有一个吸收状态能够永远到达。重要的是对于具有给定的初始状态i的系统会被吸收到某一特定吸收状态j的概率。此吸收概率等于自状态i永远到达状态b的概率，即。对于马尔可夫链中的状态j，如果其一阶转移概率为42应用全概率公式，得当初始状态为j时，则系统已经被吸收再j中；而当初始状态处于某一其他吸收状态，例如在a，则系统将不再能被吸收到j，因而。应用全概率公式，得43另一重要的量是系统自某给定的初始状态开始到被吸收以前的平均时间。如果初始状态为i，令吸收的平均时间为mj，则

此方程为一组线性联立方程式，因此可求得以转移概率表达的平均吸收时间mj。可以看出，如果状态i为一吸收状态，则系统已处于吸收状态，此时，。另一重要的量是系统自某给定的初始状态开始44第三节极限性态及平稳分布问题question问题question第三节极限性态及平稳分布问题question问题quest45第三节极限性态及平稳分布一、的极限性态第三节极限性态及平稳分布一、的极限性态46第三节极限性态及平稳分布一、的极限性态告诉我们极限如何来求！第三节极限性态及平稳分布一、的极限性态告诉我们极限47第三节极限性态及平稳分布一、的极限性态第三节极限性态及平稳分布一、的极限性态48二、平稳分布第三节极限性态及平稳分布二、平稳分布第三节极限性态及平稳分布49二、平稳分布第三节极限性态及平稳分布二、平稳分布第三节极限性态及平稳分布50二、平稳分布二、平稳分布51二、平稳分布第三节极限性态及平稳分布三、的存在性二、平稳分布第三节极限性态及平稳分布三、52四、例子第三节极限性态及平稳分布四、例子第三节极限性态及平稳分布53四、例子第三节极限性态及平稳分布四、例子第三节极限性态及平稳分布54四、例子第三节极限性态及平稳分布四、例子第三节极限性态及平稳分布55例雨伞问题续例雨伞问题续56续续57012N-1N1不下雨1-p下雨pN-2不下雨1-p下雨p不下雨1-p下雨p不下雨下雨p不下雨1-p下雨p续012N-1N1不下雨1-p下雨pN-2不下雨1-p下雨p不58

所以该马氏链是遍历的不可约马氏链，故平稳分布存在且唯一.身边没雨伞的概率为其一步转移转移概率矩阵为续所以该马氏链是遍历的不可约马氏链，故平稳分布59

长时间后，概率与初始分布无关，近似于其平稳分布续长时间后，概率60马尔可夫链课件61小结：关于离散马氏链的分析(1)先确定马氏链的一步转移概率矩阵P；－－－整个研究的出发点.(2)根据一步转移概率矩阵P，对状态进行分类，确定状态的周期性；

(3)判断状态的常返性－－非常返、正常返、零常返；

(4)分析马氏链的平稳分布和转移概率的极限分布；

(5)根据实际问题，作相关分析.小结：关于离散马氏链的分析(1)先确定马氏链的一步转移62

例(离散分支过程)考虑一生物种群的繁殖.假设开始时种群的个体数为，称之为第代.由第代个体繁殖产生的后代称为第一代，第一代个体的数目记为.如此继续下去，第代个体繁殖产生的个体称为第代，第代个体的数目记为.假设同一代中各个个体繁殖产生的后代个数是相互独立的，且与种群以前的繁殖过程无关.每一个个体均可产生个后代，是非负整数值随机变量.则是齐次马尔科夫链.第四节马尔可夫链的应用例(离散分支过程)考虑一生物种群的繁殖.假设开始63第代个体第代个体

即第代个体总数是第代各个个体繁殖的后代个体数之和.所以第代个体的总数完全由第代的个体数决定.

由题意知，随机变量序列相互独立且与同分布，且有解：称此形式的马氏链为分支过程.第代个体第代个体即第代个体总数64分支过程主要关心的问题是：种群灭绝的概率及时间.种群是否会爆炸？分支过程主要关心的问题是：种群灭绝的概率及时间.种群是否会爆65

66第一节基本概念第二节状态的分类及性质第三节极限性态及平稳分布第四节Markov链的应用第一节基本概念67第一节基本概念一、Markov链的定义二、转移概率三、Markov链的例子四、n步转移概率，C-K方程第一节基本概念一、Markov链的定义68

过程(或系统)在时刻t0所处的状态为已知的条件下，过程在时刻t>t0所处状态的条件分布与过程在时刻t0之前所处的状态无关。

通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。第一节基本概念马尔可夫性(无后效性)用分布函数表述马尔可夫性：一、Markov链的定义过程(或系统)在时刻t0所处的状态为已知的条件下，过69定义设随机过程的状态空间为：若对任意的，及有马氏性…………则称为离散时间、离散状态的马尔可夫过程，或简称为马尔可夫链。定义设随机过程的状态空70

设是马尔可夫链，对任意的，计算的联合分布律二、转移概率

乘法公式

马氏性

即马尔可夫链的有限维分布完全由初始分布和条件概率确定.

马氏性设是马尔可夫链，对任意的71注

当固定时，一步转移概率实质上就是在的条件下，随机变量的条件分布律，所以条件分布律满足：

定义1设是马尔可夫链，记称为马尔可夫链在时刻时的一步转移概率。二、转移概率注当固定时，一步转移概率实质72

定义2

设是马尔可夫链，若其一步转移概率与时间无关，即则称为齐次马尔可夫链，称为从状态转移到状态的一步转移概率.

若马尔科夫链的状态空间是有限集，则称为有限状态的马尔科夫链；

若马尔科夫链的状态空间是可列集，则称为可列状态的马尔科夫链.二、转移概率定义2设是马尔可夫链，若其一73矩阵的每一行都是一条件分布律

记.称为齐次马尔可夫链的初始分布.

齐次马尔科夫链的有限维分布族完全由其一步转移概率矩阵

和初始分布

确定.则称矩阵为齐次马尔科夫链的一步转移概率矩阵.

定义3设是齐次马尔可夫链，其一步转移概率为，记二、转移概率矩阵的每一行都记74例1(一个简单的疾病死亡模型)三、马氏链的例子例1(一个简单的疾病死亡模型)三、马氏链的例子75

例2(0-1传输系统或简单信号模型)如图所示，只传输数字0和1的串联系统中，设每一级的传真率为p，误码率为q=1-p。并设一个单位时间传输一级，X0是第一级的输入，Xn是第n级的输出(n≥1)，那么{Xn,n=0,1,2…}是一随机过程，状态空间S={0,1}，而且当Xn=i为已知时，Xn+1所处的状态的概率分布只与Xn=i有关，而与时刻n以前所处的状态无关，所以它是一个马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为：……n21X0X1X2XnXn-1三、马氏链的例子例2(0-1传输系统或简单信号模型)……n21X076

例3(带有一个吸收壁的随机游动)质点在直线上作随机游动.在某一时刻质点位于，则下一步质点以概率向右移动一格到达；或以概率向左移动一格到达.但当质点一旦到达原点，则质点永远停留在原点，不再移动.状态称为吸收态.以表示质点在时刻的位置.则是齐次马尔可夫链，称其为带一个吸收壁的随机游动.求其一步转移概率矩阵.三、马氏链的例子例3(带有一个吸收壁的随机游动)质点在直线上作随机77

解：马尔科夫链的的状态空间为：一步状态概率为：一步状态概率矩阵为：三、马氏链的例子解：马尔科夫链的的状态空7813452

例4设一醉汉Q(或看作一随机游动的质点)在直线上的点集S={1,2,3,4,5}作随机游动，且仅在1秒、2秒等时刻发生游动，游动的概率规则是：如果Q现在位于点i(1<i<5)，则下一时刻各以的概率向左或向右移动一格，或以的概率留在原处；如果Q现在处于1(或5)这一点上，则下一时刻就以概率1移动到2(或4)这点上，1和5这两点称为反射壁，这种游动称为带有两个反射壁的随机游动。以Xn表示时刻n时Q的位置，说明{Xn,n=0,1,2…}是一齐次马氏链，并写出它的一步转移概率矩阵。三、马氏链的例子13452例4设一醉汉Q(或看作一随机游动的质点)在79解：它的一步转移概率矩阵为：

如果把1这点改为吸收壁，即Q一旦到达1这一点，则永远留在点1时，此时的转移概率矩阵为：三、马氏链的例子解：它的一步转移概率矩阵为：如果把1这点改为吸收壁，即80

例5(无限制随机游动)质点在直线上作随机游动.在某一时刻质点位于，则下一步质点以概率向右移动一格到达；或以概率向左移动一格到达.以表示质点在时刻的位置.则是状态无限的马尔科夫链，求其一步转移概率矩阵.解：马尔科夫链的的状态空间为：一步状态概率为：一步状态概率矩阵为：例5(无限制随机游动)质点在直线上作随机游动.在某一81称为马尔可夫链在时刻时处于状态经过时间后转移到状态的概率.设是马尔可夫链，其状态空间为①记马尔可夫链的步转移概率为四、n步转移概率、C-K方程②称为马尔可夫链在时刻时处于状态经过时间82称此式为切普曼－柯尔莫洛夫方程，简称C-K方程.

定理设是马尔可夫链，其状态空间为，则对任意的，有直观意义从状态出发经过步到达状态，可分成两步走：①先从状态出发经过步到达状态；②然后再先从状态出发经过步到达状态；

由马氏性知，后一阶段的状态转移与前一阶段的状态转移独立，故两个阶段的转移概率可相乘.四、n步转移概率、C-K方程称此式为切普曼－柯尔莫洛夫方程，简称C-K方程.定83ikjk0证明：四、n步转移概率、C-K方程ikjk0证明：四、n步转移概率、C-K方程84注记齐次马尔科夫链的步转移概率矩阵为：

则齐次马尔科夫链的切普曼－柯尔莫洛夫方程可用如下矩阵形式表示：四、n步转移概率、C-K方程注记齐次马尔科夫链的步转移概率矩阵为：则齐次马尔85四、n步转移概率、C-K方程四、n步转移概率、C-K方程86解：解：87

例(天气预测简单模型)假设明天是否下雨仅与今天的天气(是否下雨)有关，而与过去的天气无关.假设今天下雨、明天有雨的概率为，今天无雨而明天有雨的概率为；又假设把有雨称为状态天气，把无雨称为状态天气.记表示第天的天气状态.则是状态有限的马尔科夫链.1.求其一步转移概率矩阵；

2.若，且今天有雨，求第四天有雨的概率.四、n步转移概率、C-K方程例(天气预测简单模型)假设明天是否下雨仅与今天的88解一步状态概率矩阵为：②因为所以若今天无雨，第四天下雨的概率为0.5749①四、n步转移概率、C-K方程解一步状态概率矩阵为：②因为所以若今天无雨，第四天下雨的概率89第二节状态的分类及性质一、到达与相通二、首达时间与首达概率三、首达概率的基本性质四、状态的分类五、闭集和状态空间的分解第二节状态的分类及性质一、到达与相通90一、到达与相通一、到达与相通91一、到达与相通一、到达与相通92二、首达时间与首达概率二、首达时间与首达概率93二、首达时间与首达概率二、首达时间与首达概率94二、首达时间与首达概率二、首达时间与首达概率95三、首达概率的基本性质三、首达概率的基本性质96三、首达概率的基本性质三、首达概率的基本性质97三、首达概率的基本性质现在来推导基本性质2以此类推三、首达概率的基本性质现在来推导基本性质298三、首达概率的基本性质一旦确定了这些首达概率，便可用来计算各种概率和所关心的量如下：（1）系统初始状态为i在m次转移内进入状态j（至少1次）的概率为：（2）系统自状态i开始最终达到状态j的概率即可由下式给出：（3）系统自状态i开始最终回到状态i的概率为：三、首达概率的基本性质一旦确定了这些首99（4）状态i的平均循环时间为系统自离开状态i的时间开始直到后来首次回到状态i的时间止这段的加权平均时间。因此，

此外，状态i的期望持续期的长度为直到系统首次离开状态i时为止的加权平均时间。因此，期望持续时间为为了说明，可以考虑二类状态的马尔可夫链。应用以上方程，例如（4）状态i的平均循环时间为系统自100

对于平均持续时间，由前面方程得同理，平均循环时间为对于平均持续时间，由前面方程得同理，平均循环101同理，例以天气预测简单模型为例子，试确定（a）设今日为雨天，问后天首次又为雨天的概率如何？（b）设今日为雨天，问后五日内至少有一晴天的概率如何？（c）问持续晴天的期望长度为何？持续雨天的期望长度？（d）如今日为雨天，则直到下一雨天止，这段时间的期望长度为何？马尔可夫链课件102(a)从今天起两天以后首次为雨天的概率为：(b)后五日至少有一晴天的概率为：(c)持续晴天和持续雨天的平均天数分别为：(d)雨天的期望循环时间为：(a)从今天起两天以后首次为雨天的概率为：103四、状态的分类定义对于状态，如果，则称状态i为循环状态（常返态）；如果，则称状态i为瞬时状态（非常返态）。

在有两种状态的马尔可夫链的情况下，可用代入方程，中求出。如果为一阶转移概率，即，则，表明状态1和2为循环状态。另一方面，如果，则，表明状态2可能不再来到，因而，状态2是瞬时状态。

指系统自状态i开始，一定最终回到状态i；指系统自状态i开始将具有一个有限的概率不再回到状态i。四、状态的分类定义对于状态，104马尔可夫链课件105马尔可夫链课件106对于马尔可夫链中的状态j，如果其一阶转移概率为，则称此状态为吸收状态。因此，吸收状态被定义为一种状态，系统在此状态中除去它本身状态之外，不能再转移到任何其他状态中去。如果在马尔可夫链中存在着一种吸收状态，则系统最终将到达并进入该吸收状态。一个马尔可夫链可以含有一个以上的吸收状态。这种情况下，只有一个吸收状态能够永远到达。重要的是对于具有给定的初始状态i的系统会被吸收到某一特定吸收状态j的概率。此吸收概率等于自状态i永远到达状态b的概率，即。对于马尔可夫链中的状态j，如果其一阶转移概率为107应用全概率公式，得当初始状态为j时，则系统已经被吸收再j中；而当初始状态处于某一其他吸收状态，例如在a，则系统将不再能被吸收到j，因而。应用全概率公式，得108另一重要的量是系统自某给定的初始状态开始到被吸收以前的平均时间。如果初始状态为i，令吸收的平均时间为mj，则

此方程为一组线性联立方程式，因此可求得以转移概率表达的平均吸收时间mj。可以看出，如果状态i为一吸收状态，则系统已处于吸收状态，此时，。另一重要的量是系统自某给定的初始状态开始109第三节极限性态及平稳分布问题question问题question第三节极限性态及平稳分布问题question问题quest110第三节极限性态及平稳分布一、