《最新-第三章马尔科夫连1-PPT精品课件》由会员分享，可在线阅读，更多相关《最新-第三章马尔科夫连1-PPT精品课件（41页珍藏版）》请在金锄头文库上搜索。
1、1第三章第三章 马尔可夫链马尔可夫链1.马尔可夫链定义马尔可夫链定义2.一步转移概率及多步转移概率一步转移概率及多步转移概率3.初始概率及绝对概率初始概率及绝对概率4.Chapman-Kolmogorov方程方程5.马尔可夫链状态分类马尔可夫链状态分类6.遍历的马尔可夫链及平稳分布遍历的马尔可夫链及平稳分布2马尔可夫过程马尔可夫过程将来的状态只与当前状态有关，与过去状态无关将来的状态只与当前状态有关，与过去状态无关，即无后效性，即无后效性3马尔可夫链定义马尔可夫链定义定义：设有随机过程定义：设有随机过程Xn,n T，若对于任意的整数，若对于任意的整数n T和任意的和任意的 i0,i1, ,in
2、+1I，条件概率满足，条件概率满足则称则称Xn,n T为马尔可夫链，简称马氏链为马尔可夫链，简称马氏链时间和状态都离散的马尔可夫过程称为马尔可夫链马尔可夫链4定义定义称条件概率称条件概率为马尔可夫链为马尔可夫链Xn,n T在时刻在时刻n的一步转移概率，其中的一步转移概率，其中i,j I，简称转移概率。，简称转移概率。定义定义若对任意的若对任意的i,j I，马尔可夫链，马尔可夫链Xn,n T的转移概率与的转移概率与n无关，则称马尔可无关，则称马尔可夫链是齐次马尔可夫链。我们只讨论齐次马氏链。夫链是齐次马尔可夫链。我们只讨论齐次马氏链。5设设P表示一步转移概率所组成的矩阵，则表示一步转移概率所组成
3、的矩阵，则称为系统状态的一步转移概率矩阵，它具有如下性质：称为系统状态的一步转移概率矩阵，它具有如下性质： 满足上述两个性质的矩阵称为随机矩阵。满足上述两个性质的矩阵称为随机矩阵。6例：一维随机游动一维随机游动。设一醉汉Q(或看作一随机游动的 质点)在直线上的点集I=1,2,3,4,5作随机游动，游动的概率规则是：如果Q现在位于点i(1i=0为齐次马尔科夫链，其转移概率为例：仓储系统例：仓储系统维修点有一仓库，存储某配件以备维修时使用，该配件每周的消耗量为独立同分布的随机变量，其概率分布为：每周要对该配件进行补充，用Xn表示该仓库在第n周开始未补充配件时的配件个数，补充的原则是如果库存不少于s
4、件，则不补充；如果少于s件，则补充到S件。则随机过程Xn，n=0,1,是一个马尔科夫链。10定义定义称条件概率称条件概率为马尔可夫链为马尔可夫链Xn,n T的的n步转移概率，并称步转移概率，并称为马尔可夫链的为马尔可夫链的n步转移矩阵。规定步转移矩阵。规定例题例题设马尔可夫链设马尔可夫链Xn,n T有状态空间有状态空间I=0,1，其一步转移概率矩阵为，其一步转移概率矩阵为求求 和两步转移概率矩阵和两步转移概率矩阵P(2)11定理定理设设Xn,nT为马尔可夫链，则对任意整数为马尔可夫链，则对任意整数n0，0l0非空，则称该集合的最大公约数非空，则称该集合的最大公约数d=d(i)=G.C.Dn:p
5、ii(n)0为状态为状态i的周期。的周期。引理引理如如i的周期为的周期为d，则存在正整数，则存在正整数M，对一切，对一切nM，有，有pii(nd)0。如如d1就称就称i为周期的，如为周期的，如d=1就称就称i为非周期的。为非周期的。如果如果i有周期有周期D，则对一切非零的，则对一切非零的n0(mod(D)都有都有pii(n)=0。但这也并不是说对任意但这也并不是说对任意n有有pii(nd)0。例如上图中状态。例如上图中状态1的的d=2，但，但pii(2)=0。23例：状态转移概率图例：状态转移概率图状态的常返性状态的常返性24首中概率首中概率它表示质点由它表示质点由i出发，经出发，经n步首次到
6、达步首次到达j 的概率的概率 表示质点由表示质点由i出发，经有限步终于到达出发，经有限步终于到达j 的概率。的概率。定义定义 称状态称状态i为常返的，如为常返的，如fii=1；称状态；称状态i为非常返的，如为非常返的，如fii1。对于常返态对于常返态i，由定义知，由定义知fii(n),n1构成一概率分布构成一概率分布表示由表示由i出发再返回出发再返回i的平均返回时间。的平均返回时间。25定义定义如如ui，则称常返态，则称常返态i为正常返的；如为正常返的；如ui= ，则称常返态，则称常返态i为零常返的。为零常返的。非周期的正常返态称为遍历状态。非周期的正常返态称为遍历状态。常返性的判别常返性的判
7、别含义：当含义：当i常返时，返回常返时，返回i的次数为无限多次；当的次数为无限多次；当i非常返时，返回的次数只非常返时，返回的次数只能是有限多次。能是有限多次。262728状态空间的分解状态空间的分解定义：定义：状态空间状态空间I的子集的子集C称为闭集，如果对任意称为闭集，如果对任意 及及 都有都有定义：定义：闭集闭集C称为不可约的，如果称为不可约的，如果C的状态互通。的状态互通。定义：定义：马尔可夫链称为不可约的，如果其状态空间不可约。马尔可夫链称为不可约的，如果其状态空间不可约。29例：无限制随机游动为不可约马尔可夫链，各状态周期为例：无限制随机游动为不可约马尔可夫链，各状态周期为2，当，
8、当p=q时时是零常返，是零常返，pq时是非常返。时是非常返。303）D由全体非常返状态组成，自由全体非常返状态组成，自Cn中的状态不能到达中的状态不能到达D中的状态。中的状态。状态空间的分解定理：状态空间的分解定理：任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的，可唯一的分解成有限个或可列个互不相交的子集子集D,C1,C2, 之和，使得之和，使得1） 每一每一Cn是常返态组成的不可约闭集；是常返态组成的不可约闭集；2）Cn中的状态同类，或全是正常返，或全是零常返。中的状态同类，或全是正常返，或全是零常返。 它们有相同的周期且它们有相同的周期且fjk=
9、1,j,k Cn。3132 的渐进性质与平稳分布的渐进性质与平稳分布333435定义定义称概率分布称概率分布j,j I为马尔可夫链的平稳分布，若它满足为马尔可夫链的平稳分布，若它满足定理定理不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此平稳分布就是极限分布平稳分布就是极限分布 。推论推论1：有限状态的不可约非周期马氏链必存在平稳分布。：有限状态的不可约非周期马氏链必存在平稳分布。推论推论2： 若所有状态是非常返或零常返的，则不存在平稳分布。若所有状态是非常返或零常返的，则不存在平稳分布。36例题例题若马尔可夫链有三状态，
10、其概率转移矩阵为若马尔可夫链有三状态，其概率转移矩阵为问此马尔可夫链是否遍历，若遍历求其平稳分布。问此马尔可夫链是否遍历，若遍历求其平稳分布。例：马尔科夫连的状态空间为例：马尔科夫连的状态空间为1,2,3,4,5,6,7，其转移概率矩阵为，其转移概率矩阵为任一马尔可夫链的状态空间任一马尔可夫链的状态空间I，可唯一的分解成有限个或可列个互不相交的，可唯一的分解成有限个或可列个互不相交的子集子集D,C1,C2, 之和，使得每一之和，使得每一Cn是常返态组成的不可约闭集；是常返态组成的不可约闭集；D由全体非常返状态组成，自由全体非常返状态组成，自Cn中的状态不能到达中的状态不能到达D中的状态。中的状
11、态。把一步转移概率矩阵行、列按照分解的次序重新排列，不可约闭集在把一步转移概率矩阵行、列按照分解的次序重新排列，不可约闭集在前，前，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=WR。6：41作业：4.1 4.6 4.12
