马尔可夫链课件.pptx

第一节第一节 基本概念基本概念第二节第二节 状态的分类及性质状态的分类及性质第三节第三节 极限性态及平稳分布极限性态及平稳分布第四节第四节 MarkovMarkov链的应用链的应用第1页/共65页第一节 基本概念一、一、MarkovMarkov链的定义链的定义二、转移概率二、转移概率三、三、MarkovMarkov链的例子链的例子四、四、n n步转移概率，步转移概率，C-KC-K方程方程第2页/共65页 过程(或系统)在时刻t t0 0所处的状态为已知的条件下，过程在时刻tttt0 0所处状态的条件分布与过程在时刻t t0 0之前所处的状态无关。通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。第一节 基本概念马尔可夫性马尔可夫性(无后效性无后效性)用分布函数表述马尔可夫性：用分布函数表述马尔可夫性：一、一、MarkovMarkov链的定义链的定义第3页/共65页定义 设随机过程 的状态空间为：若对任意的 ，及 有则称 为离散时间、离散状态的马尔可夫过程，或简称为马尔可夫链。第4页/共65页 设 是马尔可夫链，对任意的 ，计算 的联合分布律二、转移概率二、转移概率 乘法公式乘法公式乘法公式乘法公式 马氏性马氏性 即马尔可夫链 的有限维分布完全由初始分布 和 条件概率 确定.马氏性马氏性第5页/共65页 当 固定时，一步转移概率 实质上就是在 的条件下，随机变量 的条件分布律，所以条件分布律满足：定义1 1 设 是马尔可夫链，记称 为马尔可夫链 在时刻 时的一步转移概率。二、转移概率二、转移概率第6页/共65页 定义2 2 设 是马尔可夫链，若其一步转移概率 与时间 无关，即则称 为齐次马尔可夫链，称 为从状态 转移到状态 的一步转移概率.若马尔科夫链 的状态空间是有限集，则称 为有限状态的马尔科夫链；若马尔科夫链 的状态空间是可列集，则称 为可列状态的马尔科夫链.二、转移概率二、转移概率第7页/共65页矩阵的每一行都矩阵的每一行都是一条件分布律是一条件分布律 记 .称 为齐次马尔可夫链的初始分布.齐次马尔科夫链的有限维分布族完全由其一步转移概率矩阵 和初始分布 确定.则称矩阵 为齐次马尔科夫链的一步转移概率矩阵.定义3 3 设 是齐次马尔可夫链，其一步转移概率为 ，记二、转移概率二、转移概率第8页/共65页例1(1(一个简单的疾病死亡模型)三、马氏链的例子三、马氏链的例子第9页/共65页 例2 2(0-1(0-1传输系统或简单信号模型)如图所示，只传输数字0 0和1 1的串联系统中，设每一级的传真率为p p，误码率为q=1-pq=1-p。并设一个单位时间传输一级，X X0 0是第一级的输入，X Xn n是第n n级的输出(n1)(n1)，那么XXn n,n=0,1,2,n=0,1,2是一随机过程，状态空间S=0,1S=0,1，而且当X Xn n=i=i为已知时，X Xn+1n+1所处的状态的概率分布只与X Xn n=i=i有关，而与时刻n n以前所处的状态无关，所以它是一个马氏链，而且还是齐次的，它的一步转移概率和一步转移概率矩阵分别为：n21X0X1X2XnXn-1三、马氏链的例子三、马氏链的例子第10页/共65页 例3(3(带有一个吸收壁的随机游动)质点在直线上作随机游动.在某一时刻质点位于 ，则下一步质点以概率 向右移动一格到达 ；或以概率 向左移动一格到达 .但当质点一旦到达原点 ，则质点永远停留在原点 ，不再移动.状态 称为吸收态.以 表示质点在时刻 的位置.则 是齐次马尔可夫链，称其为带一个吸收壁的随机游动.求其一步转移概率矩阵.三、马氏链的例子三、马氏链的例子第11页/共65页 解：马尔科夫链的 的状态空间为：一步状态概率为：一步状态概率矩阵为：三、马氏链的例子三、马氏链的例子第12页/共65页13452 例4 4设一醉汉Q(Q(或看作一随机游动的质点)在直线上的点集S=1,2,3,4,5S=1,2,3,4,5作随机游动，且仅在1 1秒、2 2秒等时刻发生游动，游动的概率规则是：如果Q Q现在位于点i(1i5)i(1i5)，则下一时刻各以 的概率向左或向右移动一格，或以 的概率留在原处；如果Q Q现在处于1(1(或5)5)这一点上，则下一时刻就以概率1 1移动到2(2(或4)4)这点上，1 1和5 5这两点称为反射壁，这种游动称为带有两个反射壁的随机游动。以X Xn n表示时刻n n时Q Q的位置，说明 X Xn n,n n=0,1,2 =0,1,2 是一齐次马氏链，并写出它的一步转移概率矩阵。三、马氏链的例子三、马氏链的例子第13页/共65页解：它的一步转移概率矩阵为：如果把1 1这点改为吸收壁，即Q Q一旦到达1 1这一点，则永远留在点1 1时，此时的转移概率矩阵为：三、马氏链的例子三、马氏链的例子第14页/共65页 例5 5(无限制随机游动)质点在直线上作随机游动.在某一时刻质点位于 ，则下一步质点以概率 向右移动一格到达 ；或以概率 向左移动一格到达 .以 表示质点在时刻 的位置.则 是状态无限的马尔科夫链，求其一步转移概率矩阵.解：马尔科夫链的 的状态空间为：一步状态概率为：一步状态概率矩阵为：第15页/共65页称 为马尔可夫链在时刻 时处于状态 经过时间 后转移到状态 的概率.设 是马尔可夫链，其状态空间为记马尔可夫链的 步转移概率为四、四、n n步转移概率、步转移概率、C-KC-K方程方程第16页/共65页称此式为切普曼柯尔莫洛夫方程，简称C-KC-K方程 .定理 设 是马尔可夫链，其状态空间为 ，则对任意的 ，有从状态 出发经过 步到达状态 ，可分成两步走：先从状态 出发经过 步到达状态 ；然后再先从状态 出发经过 步到达状态 ；由马氏性知，后一阶段的状态转移与前一阶段的状态转移独立，故两个阶段的转移概率可相乘.四、四、n n步转移概率、步转移概率、C-KC-K方程方程第17页/共65页i ik kj jk k0 0证明：证明：四、四、n n步转移概率、步转移概率、C-KC-K方程方程第18页/共65页记齐次马尔科夫链的 步转移概率矩阵为：则齐次马尔科夫链的切普曼柯尔莫洛夫方程可用如下矩阵形式表示：四、四、n n步转移概率、步转移概率、C-KC-K方程方程第19页/共65页四、四、n n步转移概率、步转移概率、C-KC-K方程方程第20页/共65页解：解：第21页/共65页 例 (天气预测简单模型)假设明天是否下雨仅与今天的天气(是否下雨)有关，而与过去的天气无关.假设今天下雨、明天有雨的概率为 ，今天无雨而明天有雨的概率为 ；又假设把有雨称为 状态天气，把无雨称为 状态天气.记 表示第 天的天气状态.则 是状态有限的马尔科夫链.1.1.求其一步转移概率矩阵；2.2.若 ，且今天有雨，求第四天有雨的概率.四、四、n n步转移概率、步转移概率、C-KC-K方程方程第22页/共65页一步状态概率矩阵为：因为所以若今天无雨，第四天下雨的概率为0.57490.5749四、四、n n步转移概率、步转移概率、C-KC-K方程方程第23页/共65页第二节 状态的分类及性质一、到达与相通一、到达与相通二、首达时间与首达概率二、首达时间与首达概率三、首达概率的基本性质三、首达概率的基本性质四、状态的分类四、状态的分类五、闭集和状态空间的分解五、闭集和状态空间的分解第24页/共65页一、到达与相通一、到达与相通第25页/共65页一、到达与相通一、到达与相通第26页/共65页二、首达时间与首达概率二、首达时间与首达概率第27页/共65页二、首达时间与首达概率二、首达时间与首达概率第28页/共65页二、首达时间与首达概率二、首达时间与首达概率第29页/共65页三、首达概率的基本性质三、首达概率的基本性质第30页/共65页三、首达概率的基本性质三、首达概率的基本性质第31页/共65页三、首达概率的基本性质三、首达概率的基本性质现在来推导基本性质2以此类推第32页/共65页三、首达概率的基本性质三、首达概率的基本性质 一旦确定了这些首达概率，便可用来计算各种概率和所关心的量如下：（1）系统初始状态为i在m次转移内进入状态j（至少1次）的概率为：（2）系统自状态i开始最终达到状态j的概率即可由下式给 出：（3）系统自状态i开始最终回到状态i的概率为：第33页/共65页 （4）状态i的平均循环时间为系统自离开状态i的时间开始直到后来首次回到状态i的时间止这段的加权平均时间。因此，此外，状态i的期望持续期的长度为直到系统首次离开状态i时为止的加权平均时间。因此，期望持续时间为 为了说明，可以考虑二类状态的马尔可夫链。应用以上方程，例如第34页/共65页 对于平均持续时间，由前面方程得同理，平均循环时间为第35页/共65页同理，例 以天气预测简单模型为例子，试确定（a）设今日为雨天，问后天首次又为雨天的概率如何？（b）设今日为雨天，问后五日内至少有一晴天的概率如何？（c）问持续晴天的期望长度为何？持续雨天的期望长度？（d）如今日为雨天，则直到下一雨天止，这段时间的期望长度为何？第36页/共65页(a)从今天起两天以后首次为雨天的概率为：(b)后五日至少有一晴天的概率为：(c)持续晴天和持续雨天的平均天数分别为：(d)雨天的期望循环时间为：第37页/共65页四、四、状态的分类状态的分类定义 对于状态 ，如果 ，则称状态i为循环状 态（常返态）；如果 ，则称状态i为瞬时状态（非常返态）。在有两种状态的马尔可夫链的情况下，可用 代入方程 ，中求出。如果为一阶转移概率，即 ，则 ，表明状态1和2为循环状态。另一方面，如果 ，则 ，表明状态2可能不再来到，因而，状态2是瞬时状态。指系统自状态指系统自状态i i开始，一定最终回到状态开始，一定最终回到状态i i；指系统自状态指系统自状态i i开始将具有一个有限的概率不再开始将具有一个有限的概率不再回到状态回到状态i i。第38页/共65页第39页/共65页第40页/共65页 对于马尔可夫链中的状态j，如果其一阶转移概率为 ，则称此状态为吸收状态。因此，吸收状态被定义为一种状态，系统在此状态中除去它本身状态之外，不能再转移到任何其他状态中去。如果在马尔可夫链中存在着一种吸收状态，则系统最终将到达并进入该吸收状态。一个马尔可夫链可以含有一个以上的吸收状态。这种情况下，只有一个吸收状态能够永远到达。重要的是对于具有给定的初始状态i的系统会被吸收到某一特定吸收状态j的概率。此吸收概率等于自状态i永远到达状态b的概率，即 。第41页/共65页 应用全概率公式，得 当初始状态为j时，则系统已经被吸收再j中；而当初始状态处于某一其他吸收状态，例如在a，则系统将不再能被吸收到j，因而 。第42页/共65页 另一重要的量是系统自某给定的初始状态开始到被吸收以前的平均时间。如果初始状态为i，令吸收的平均时间为mj，则 此方程为一组线性联立方程式，因此可求得以转移概率表达的平均吸收时间mj。可以看出，如果状态i为一吸收状态，则系统已处于吸收状态，此时，。第43页/共65页第三节 极限性态及平稳分布第44页/共65页第三节 极限性态及平稳分布一、一、的极限性的极限性态态第45页/共65页第三节 极限性态及平稳分布一、一、的极限性的极限性态态告诉我们告诉我们极限极限 如何来求如何来求！第46页/共65页第三节 极限性态及平稳分布一、一、的极限性的极限性态态第47页/共65页二、平稳分布二、平稳分布第三节 极限性态及平稳分布第48页/共65页二、平稳分布二、平稳分布第三节 极限性态及平稳分布第49页/共65页二、平稳分布二、平稳分布第50页/共65页二、平稳分布二、平稳分布第三节 极限性态及平稳分布三、三、的存在的存在性性第51页/共65页四、例子四、例子第三节 极限性态及平稳分布第52页/共65页四、例子四、例子第三节 极限性态及平稳分布第53页/共65页四、例子四、例子第三节 极限性态及平稳分布第54页/共65页例 雨伞问题续第55页/共65页续第56页/共65页012N-1N1不下雨不下雨1-p下雨下雨pN-2不下雨不下雨1-p下雨下雨p不下雨不下雨1-p下雨下雨p不下雨不下雨下雨下雨p不下雨不下雨1-p下雨下雨p续第57页/共65页 所以该马氏链是遍历的不可约马氏链，故平稳分布存在且唯一.身边没雨伞的概率为其一步转移转移概率矩阵为续第58页/共65页 长时间后，概率 与初始分布无关，近似于其平稳分布续第59页/共65页第60页/共65页小结：关于离散马氏链的分析小结：关于离散马氏链的分析 (1)(1)先确定马氏链的一步转移概率矩阵先确定马氏链的一步转移概率矩阵P P；整个研究的出发点整个研究的出发点.(2)(2)根据一步转移概率矩阵根据一步转移概率矩阵P P，对状态进行分类，对状态进行分类，确定状态的周期性；确定状态的周期性；(3)(3)判断状态的常返性非常返、正常返、零判断状态的常返性非常返、正常返、零常返；常返；(4)(4)分析马氏链的平稳分布和转移概率的极限分分析马氏链的平稳分布和转移概率的极限分布；布；(5)(5)根据实际问题，作相关分析根据实际问题，作相关分析.第61页/共65页 例 (离散分支过程)考虑一生物种群的繁殖.假设开始时种群的个体数为 ，称之为第 代.由第 代个体繁殖产生的后代称为第一代，第一代个体的数目记为 .如此继续下去，第 代个体繁殖产生的个体称为第 代，第 代个体的数目记为 .假设同一代中各个个体繁殖产生的后代个数是相互独立的，且与种群以前的繁殖过程无关.每一个个体均可产生 个后代，是非负整数值随机变量.则 是齐次马尔科夫链.第四节 马尔可夫链的应用第62页/共65页第 代个体第 代个体 即第 代个体总数 是第 代各个个体繁殖的后代个体数之和.所以第 代个体的总数 完全由第 代的个体数 决定.由题意知，随机变量序列 相互独立且与 同分布，且有解：解：称此形式的马氏链为分支过程.第63页/共65页分支过程主要关心的问题是：分支过程主要关心的问题是：种群灭绝的概率及时间.种群是否会爆炸？第64页/共65页感谢您的观看！第65页/共65页