随机过程课件：第四章 马尔科夫连.ppt

1第三章第三章 马尔可夫链马尔可夫链1.马尔可夫链定义马尔可夫链定义2.一步转移概率及多步转移概率一步转移概率及多步转移概率3.初始概率及绝对概率初始概率及绝对概率4.Chapman-Kolmogorov方程方程5.马尔可夫链状态分类马尔可夫链状态分类6.遍历的马尔可夫链及平稳分布遍历的马尔可夫链及平稳分布2马尔可夫过程马尔可夫过程将来的状态只与当前状态有关，与过去状态无关将来的状态只与当前状态有关，与过去状态无关，即无后效性，即无后效性3马尔可夫链定义马尔可夫链定义定义：设有随机过程定义：设有随机过程{Xn,n∈ ∈T}，若对于任意的整数，若对于任意的整数n∈ ∈T和任意的和任意的 i0,i1, …,in+1∈∈I，条件概率满足，条件概率满足则称则称{Xn,n∈ ∈T}为马尔可夫链，简称马氏链为马尔可夫链，简称马氏链时间和状态都离散的马尔可夫过程称为马尔可夫链马尔可夫链4定义定义称条件概率称条件概率为马尔可夫链为马尔可夫链{Xn,n∈ ∈T}在时刻在时刻n的一步转移概率，其中的一步转移概率，其中i,j∈ ∈I，简称转移概率简称转移概率定义定义若对任意的若对任意的i,j∈ ∈I，马尔可夫链，马尔可夫链{Xn,n∈ ∈T}的转移概率与的转移概率与n无关，则称马尔可无关，则称马尔可夫链是齐次马尔可夫链。

我们只讨论齐次马氏链夫链是齐次马尔可夫链我们只讨论齐次马氏链5设设P表示一步转移概率所组成的矩阵，则表示一步转移概率所组成的矩阵，则称为系统状态的一步转移概率矩阵，它具有如下性质：称为系统状态的一步转移概率矩阵，它具有如下性质： 满足上述两个性质的矩阵称为随机矩阵满足上述两个性质的矩阵称为随机矩阵6例：一维随机游动一维随机游动设一醉汉Q(或看作一随机游动的 质点)在直线上的点集I={1,2,3,4,5}作随机游动，游动的概率规则是：如果Q现在位于点i(1

等候室服务台系统随机到达者离去者8例：生灭链生灭链观察某生物群落，以Xn表示在时刻n群体的数目，设为i个数量单位，如在时刻n+1增加到i+1个数量单位的概率为bi，减灭到i-1个数量单位的概率为ai，保持不变的概率为ri=1- ai - bi ，则{Xn，n>=0}为齐次马尔科夫链，其转移概率为例：仓储系统例：仓储系统维修点有一仓库，存储某配件以备维修时使用，该配件每周的消耗量为独立同分布的随机变量，其概率分布为：每周要对该配件进行补充，用Xn表示该仓库在第n周开始未补充配件时的配件个数，补充的原则是如果库存不少于s件，则不补充；如果少于s件，则补充到S件则随机过程{Xn，n=0,1,…}是一个马尔科夫链10定义定义称条件概率称条件概率为马尔可夫链为马尔可夫链{Xn,n∈ ∈T}的的n步转移概率，并称步转移概率，并称为马尔可夫链的为马尔可夫链的n步转移矩阵规定步转移矩阵规定例题例题设马尔可夫链设马尔可夫链{Xn,n∈ ∈T}有状态空间有状态空间I={0,1}，其一步转移概率矩阵为，其一步转移概率矩阵为求求 和两步转移概率矩阵和两步转移概率矩阵P(2)11定理定理设设{Xn,n∈∈T}为马尔可夫链，则对任意整数为马尔可夫链，则对任意整数n≥0，，0≤l

时刻的绝对概率向量定义：定义：称称 为马尔可夫链的初始分布；为马尔可夫链的初始分布；称称 为马尔可夫链的初始分布；为马尔可夫链的初始分布；称称 为马尔可夫链的初始概率向量为马尔可夫链的初始概率向量13定理定理设设{Xn,n∈ ∈T}为马尔可夫链，则对任意为马尔可夫链，则对任意j∈ ∈I和和n≥1，绝对概率，绝对概率pj(n)具有下列具有下列性质：性质：1. 2. 3. 4. 14定理定理设设{Xn,n∈ ∈T}为马尔可夫链，则对任意为马尔可夫链，则对任意i1, …,in∈ ∈I和和n≥1，有，有15例：某计算机机房的一台计算机经常出故障，研究者每隔例：某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计分钟观察一次计算机的运行状态，收集了算机的运行状态，收集了24个小时的数个小时的数(共作共作97次观察次观察)，用，用1表示正常状态，表示正常状态，用用0表示不正常状态，所得的数据序列如下：表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111 设设Xn为第为第n(n=1,2,…,97)个时段的计算机状态，可以认为它是一个齐次马个时段的计算机状态，可以认为它是一个齐次马氏链氏链. 求求 (1)一步转移概率矩阵一步转移概率矩阵; (2)已知计算机在某一时段已知计算机在某一时段(15分钟分钟)的状态为的状态为0，问在此条件下，从此时，问在此条件下，从此时段起，该计算机能连续正常工作段起，该计算机能连续正常工作45分钟分钟(3个时段个时段)的条件概率的条件概率.16例题：天气预报问题例题：天气预报问题1设今日有雨，明日有雨的概率为设今日有雨，明日有雨的概率为0.7；今日无雨，明日有雨的概率为；今日无雨，明日有雨的概率为0.4。

若星期一下雨，求星期四下雨的概率若星期一下雨，求星期四下雨的概率17例题：天气预报问题例题：天气预报问题2设昨日、今日都下雨，明日有雨的概率为设昨日、今日都下雨，明日有雨的概率为0.7；昨日无雨、今日有雨，；昨日无雨、今日有雨，明日有雨的概率为明日有雨的概率为0.5；昨日有雨、今日无雨，明日有雨的概率为；昨日有雨、今日无雨，明日有雨的概率为0.4；昨日、今日均无雨，明日有雨的概率为；昨日、今日均无雨，明日有雨的概率为0.2若星期一、星期二均下若星期一、星期二均下雨，求星期四下雨的概率雨，求星期四下雨的概率例题：无限制随机游动例题：无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动，向左移动的概率为的概率为q=1-p，这种运动称为无限制随机游动以，这种运动称为无限制随机游动以Xn表示时刻表示时刻n质点质点所处的位置，则所处的位置，则{Xn,n∈ ∈T}是一个齐次马尔可夫链，求一步和是一个齐次马尔可夫链，求一步和k步转移概步转移概率例题：有吸收壁随机游动例题：有吸收壁随机游动甲、乙进行赌博，甲有甲、乙进行赌博，甲有a元，乙有元，乙有b元，每赌一局输家给赢家元，每赌一局输家给赢家1元，没有元，没有和局，直到一人输光为止。

设每一局甲赢的概率为和局，直到一人输光为止设每一局甲赢的概率为p，输的概率为，输的概率为q=1-p，求甲输光的概率，求甲输光的概率20马尔可夫链的状态分类马尔可夫链的状态分类v周期、非周期周期、非周期v常返、非常返常返、非常返v正常返、零常返正常返、零常返v遍历状态遍历状态21设马尔可夫链的状态空间设马尔可夫链的状态空间I={1,2,3,4,5,6,7,8,9}，状态间的概率转移图如下图，状态间的概率转移图如下图22假设假设{Xn,n≥0}是齐次马尔可夫链，其状态空间是齐次马尔可夫链，其状态空间I={0,1,2,3, …}，转移概率，转移概率是是pij，，i,j∈ ∈I，初始分布为，初始分布为{pj,j ∈ ∈I}定义定义如集合如集合{n: n≥1,pii(n)>0}非空，则称该集合的最大公约数非空，则称该集合的最大公约数d=d(i)=G.C.D{n:pii(n)>0}为状态为状态i的周期引理引理如如i的周期为的周期为d，则存在正整数，则存在正整数M，对一切，对一切n≥M，有，有pii(nd)>0如如d>1就称就称i为周期的，如为周期的，如d=1就称就称i为非周期的为非周期的如果如果i有周期有周期D，则对一切非零的，则对一切非零的n≠0(mod(D))都有都有pii(n)=0。

但这也并不是说对任意但这也并不是说对任意n有有pii(nd)>0例如上图中状态例如上图中状态1的的d=2，但，但pii(2)=023例：状态转移概率图例：状态转移概率图状态的常返性状态的常返性24首中概率首中概率它表示质点由它表示质点由i出发，经出发，经n步首次到达步首次到达j 的概率的概率 表示质点由表示质点由i出发，经有限步终于到达出发，经有限步终于到达j 的概率定义定义 称状态称状态i为常返的，如为常返的，如fii=1；称状态；称状态i为非常返的，如为非常返的，如fii<1对于常返态对于常返态i，由定义知，由定义知{fii(n),n≥1}构成一概率分布构成一概率分布表示由表示由i出发再返回出发再返回i的平均返回时间的平均返回时间25定义定义如如ui<∞，则称常返态，则称常返态i为正常返的；如为正常返的；如ui= ∞，则称常返态，则称常返态i为零常返的为零常返的非周期的正常返态称为遍历状态非周期的正常返态称为遍历状态常返性的判别常返性的判别含义：当含义：当i常返时，返回常返时，返回i的次数为无限多次；当的次数为无限多次；当i非常返时，返回的次数只非常返时，返回的次数只能是有限多次。

能是有限多次262728状态空间的分解状态空间的分解定义：定义：状态空间状态空间I的子集的子集C称为闭集，如果对任意称为闭集，如果对任意 及及 都有都有定义：定义：闭集闭集C称为不可约的，如果称为不可约的，如果C的状态互通的状态互通定义：定义：马尔可夫链称为不可约的，如果其状态空间不可约马尔可夫链称为不可约的，如果其状态空间不可约29例：无限制随机游动为不可约马尔可夫链，各状态周期为例：无限制随机游动为不可约马尔可夫链，各状态周期为2，当，当p=q时时是零常返，是零常返，p≠q时是非常返时是非常返303））D由全体非常返状态组成，自由全体非常返状态组成，自Cn中的状态不能到达中的状态不能到达D中的状态中的状态状态空间的分解定理：状态空间的分解定理：任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的，可唯一的分解成有限个或可列个互不相交的子集子集D,C1,C2, …之和，使得之和，使得1）） 每一每一Cn是常返态组成的不可约闭集；是常返态组成的不可约闭集；2））Cn中的状态同类，或全是正常返，或全是零常返。

中的状态同类，或全是正常返，或全是零常返 它们有相同的周期且它们有相同的周期且fjk=1,j,k∈ ∈Cn3132 的渐进性质与平稳分布的渐进性质与平稳分布333435定义定义称概率分布称概率分布{πj,j∈ ∈I}为马尔可夫链的平稳分布，若它满足为马尔可夫链的平稳分布，若它满足定理定理不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此平稳分布就是极限分布平稳分布就是极限分布 推论推论1：有限状态的不可约非周期马氏链必存在平稳分布有限状态的不可约非周期马氏链必存在平稳分布推论推论2：： 若所有状态是非常返或零常返的，则不存在平稳分布若所有状态是非常返或零常返的，则不存在平稳分布36例题例题若马尔可夫链有三状态，其概率转移矩阵为若马尔可夫链有三状态，其概率转移矩阵为问此马尔可夫链是否遍历，若遍历求其平稳分布问此马尔可夫链是否遍历，若遍历求其平稳分布例：马尔科夫连的状态空间为例：马尔科夫连的状态空间为{1,2,3,4,5,6,7}，其转移概率矩阵为，其转移概率矩阵为任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的，可唯一的分解成有限个或可列个互不相交的子集子集D,C1,C2, …之和，使得每一之和，使得每一Cn是常返态组成的不可约闭集；是常返态组成的不可约闭集；D由全体非常返状态组成，自由全体非常返状态组成，自Cn中的状态不能到达中的状态不能到达D中的状态。

中的状态把一步转移概率矩阵行、列按照分解的次序重新排列，不可约闭集在把一步转移概率矩阵行、列按照分解的次序重新排列，不可约闭集在前，前，D在后，则在后，则P矩阵可改写为所谓的标准形：矩阵可改写为所谓的标准形： 吸收马尔科夫链吸收马尔科夫链如果只关心非常返状态与各闭集之间的关系，忽略闭集内部的转移，则可把各闭集内部的状态合并成一个状态—吸收态（pii=1），P矩阵可进一步改写为：例如：马尔科夫链的状态空间为例如：马尔科夫链的状态空间为I={1,2,…,10}，其转移概率矩阵为：，其转移概率矩阵为： 吸收马尔科夫链性质吸收马尔科夫链性质2：：Q矩阵中至少有一行的和不为矩阵中至少有一行的和不为1（亚随机矩阵），（亚随机矩阵），Qn收敛到收敛到0矩矩阵（阵（n趋于无限）趋于无限）3：定义：定义W=I+Q+Q2+…为基本矩阵，其中的每一项为基本矩阵，其中的每一项1：：表示从非常返态表示从非常返态i i到非常返态到非常返态j j，在被吸收之前的平均到达次数在被吸收之前的平均到达次数4：令：令F(n)={fij(n)}，其中：，其中：I D，，j C，则，则F(n)=Qn-1R。

5：令：令F={fij}，其中：，其中：I D，，j C，则，则F=WR6：：41作业：4.1 4.6 4.12。