资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
3. 状态空间的分解状态空间的分解 iiii若,则.则约定互通满足: (1) (2) (3), ii ijji ij jkik 即互通是一种等价关系.利用该等价关系划分S为 12 mnn n SSmSnSmn= =? , , , ( ), n ii称S 为一个以后将包含等价类.S的等价类记为则 ( )S iij ji= ( )( )S iS jij= ( ) nn S iSiS= ( ) i 有何S特性? 定义定义(1)闭集 ( ) 0, n ij p=则称C为闭集. (2) 吸收状态 0,iCjCn 设C为S的子集.若对,,和有 iSii设,若子集是闭集,则称状态 为吸收态. (3) 不可约闭集 设C为闭集,若C中不再含任何非空真 则称C 闭子集, 不是可约闭集. 不可约(4)马尔可夫链 S若状态空间 是不可约的,则称该马尔可夫链 是.否则称为不可约的可约的. 引理引理7 (有关闭集的判定和性质有关闭集的判定和性质) 0( ),1 ij CpiC jC= 是闭集 (2)1, ij j C CpiC = 是闭集 ( ) 1(,30) ij n j C CpiC n = 是闭集 1(4) ii iip=是吸收态(即为闭集) 证明证明(1)C若 是闭集, 0, ij iC jCp=由定义 ,0 ij iC jCp =反之,若对, ( ) 0,0 n ij iCjCnp =(要证:,,和有) 用数学归纳法用数学归纳法 (0) 0 ij piCjC= , (1) 0 ij piCjC= , ( ) 0 k ij pnkiCjC= 假设时, 1C-Knk=+则时,由方程 (1)( )kk ijillj l ppp + = iCjC (,) )(k l k ill C jjil ll C pppp =+ 0= C是闭集 00, n ij npiCjC = ( ) 对, 引理引理8( )( )S iS i若等价类是闭集,则不可约的. 设CS(i)是非空闭集.证明证明 jCjkk 对,(若,则由闭集定义:C) ( ) ilS任取 ()(jSS iCi又为等价类,且 ljlC ( )CS i= ( ) i 从而SC ( )S i所以,不可约的. 引理引理9设设C是闭集是闭集,则当且仅当其中任何两个状态则当且仅当其中任何两个状态 互通时互通时,C为不可约的为不可约的. 证明证明设C中任何两状态互通. 8与引理 证明相同, C为不可约的. C为不反之,若可约的. C(反正法证明 中任意两状态互通) ,i jC ijij假设且 :,Dil ilC il= 令 D则 一定是非空闭集 DlD kDlk(事实上,若 不是闭集,则有,使 ,Dilik再由 的构造知:且kD 矛盾) jD又 DC是 的非空的真闭子集.与C不可约矛盾. .ij .jjii同理所以 推论推论 齐次马尔可夫链是不可约的充要条件是齐次马尔可夫链是不可约的充要条件是 它的任何两个状态互通它的任何两个状态互通 特别关于特别关于有限状态的马尔可夫链有限状态的马尔可夫链有下面结论有下面结论 定理定理7 (1)有限齐次马尔可夫链所有有限齐次马尔可夫链所有非常返状态集非常返状态集D不可能不可能 是闭集是闭集. (2) 有限齐次马尔可夫链有限齐次马尔可夫链不可能存在零常返状态不可能存在零常返状态. (3) 不可约的有限齐次马尔可夫链的所有状态都是不可约的有限齐次马尔可夫链的所有状态都是 正常返状态正常返状态. 01)1( n ij j D DinpD = ( ) 若 是闭集,则对,有, lim0 n ij n jDp = ( ) 又为非常返, 证明证明 limli1m0 nn ijij j DD nn j pp = ( )( ) D矛盾!所以 不是闭集 2i若有某状态 是( )零常返,则令 i Cjij=: i C则可以证明为闭集.1则与()相同的证明,矛盾! 132由()()可得. 定理定理8 ( ) ( ) iSiS i S i 设是常返态,则包含的等价类是闭集. 从而是不可约的. ( ),jS ikSjkkj 对若,则 (常返态的可达,即互通) 证明证明 ( )kS i ( )S i是不可约集. ( )S i是闭集. 由以上的分析由以上的分析,可以得到状态空间的分解定理可以得到状态空间的分解定理 定理定理9 齐次马尔可夫链的齐次马尔可夫链的状态空间状态空间S可唯一地分解成有限个可唯一地分解成有限个 或可列无限多个互不相交的状态子集的并或可列无限多个互不相交的状态子集的并.即即 12 CDCS =? D是所有是所有非常返状态非常返状态构成的状态子集构成的状态子集.其中其中 1,2, n C n?( =)所有 所有常返状态常返状态构成的构成的不可约闭集不可约闭集. 每个状态子集中的状态有着相同的状态类型每个状态子集中的状态有着相同的状态类型: (即 或者均为零常返即 或者均为零常返,或者均为正常返非周期或者均为正常返非周期, 或者均为正常返周期且周期相同或者均为正常返周期且周期相同.) ,1 nij i jCf=且对 引理引理10 12 ()() 2 1 , 0,0 nn ijij di jC ppd nn 设C是不可约闭集,周期为对,若 ,则 C是不可约闭集 证明证明 Cjiji对,有 ( ) 0,0 n ji np 使 1122 ()()()()( )( ) 00 nnnnnnnn iiijjiiiijji pppppp + 12 d nnd nn+ 2 1 d nn 定理定理10 (周期链分解定理周期链分解定理) 12 , d dd J JJ? 设C是周期为 的不可约闭集,C可为 个 互 唯一分解 不相交的状态子集之并,即 1 ,1,2, mm d m l JJmlldCmJ = = =? 1 11 ,1,2, .1 m kj j J m d pkJmd JJ + + = = ?而且对有 并约定 证明思路证明思路: 从三个方面证明从三个方面证明 (1) 分解式的存在性分解式的存在性 (2) 转移规则的合理性转移规则的合理性(正确性正确性) (3) 分解式的唯一性分解式的唯一性 证明证明(1) 分解式的存在性分解式的存在性 () ,0,0 nd m imj CJjnpi + = 取记, 1 d m m CJ = = 则 1,2,md=? ml mlJJ= 且时, ml jJJ(事实上,若 12 0 m Jnn则由的构造知:0,使 12 ()() 00 n d mn d l ijij pp + , 10-d l m由引理知:, lmd但1, ml JJ= ) 0lmlm =,即 (2) 转移规则的正确性转移规则的正确性 1 ,1 m mkj j J kJp + = (即对有) , m kJC 对有 C 为闭集, 1 kj j C p = 11mm kj j J k C Jj j pp + =+ mm JkJn由的构造知:0使 () 0 nd m ik p + 11mm jCJjJ + 又即 1 1 0 nd m mij Jp + + = () 又由的构造知:对,有n n对上述 有 (1)() 00 k nd mnd m ijikj ppp + = 0 kj p= 1 1 m kj j J p + = () 0 nd m ikkj pp + = (3) 分解式的唯一性分解式的唯一性 1 d m m iCJ = = 设对状态, 1 d m m iCJ = = 设对另一状态 , , mm j kJj kJ (下证:对,一定也有) l iJ 不妨设 ml若, -2 ,. m lm ldm ld jk + ? 则从i 出发,能且只能在步,步,步 到达 或 , m lm j kJJ 由的定义知: ml ( ) ,使 , m j kJNnd只 能 是 形 如的 正 整 数 ,0,1,2, n Y njk=?对而言, kj同理, jk m J是不可约的. id又由于的周期为 , 5.3.5由定理 1 0,0,0 ndnd iiii NnNpp + ()() ) 当时, ,0,1,2, n Y ni=?对而言,状态 是非周期的. ,0,1,2, ,0,1,2,. 3 n n Xn Y n = = ? ? 如果的所有状态皆为常返状态,则, 的所有状态也 ( 都是常返状态 ) m jJdn 对,由周期定义:当 不能整除 时,有 ( ) 0 n jj p= ( ) 0 n jj f= 1 jj f = ( )() 11 nnd jjjj nn ff = = j 是常返态 ,0,1,2,. n jY n=?对而言也是常返的 例例1设状态空间设状态空间S=0,1,2的马尔可夫链的马尔可夫链,它的一步它的一步 转移概率矩阵为转移概率矩阵为 11 0 22 111 244 12 0 33 P = 研究其状态间的关系以及状态类型研究其状态间的关系以及状态类型 1 2 0 1 2 1 2 1 2 1 4 1 4 1 3 2 3 (都是遍历态) 例例2设状态空间设状态空间S=1,2,3,4的马尔可夫链的马尔可夫链,它的一步 转移概率矩阵为 它的一步 转移概率矩阵为 11 00 22 11 00 22 1111 4444 0001 P = 试分析状态类型试分析状态类型 1 2 34 1 2 1 2 1 2 1 2 1 4 1 4 1 4 1 4 1 例例3设设Xn,n=0,1,2,是一齐次马尔可夫链是一齐次马尔可夫链, 状态空间状态空间 S=1,2,3,4,5,其一步转移概率矩阵为其一步转移概率矩阵为 0.500.500 00.2500.750 000.300.7 0.250.500.250 0.300.300.4 P = 试分析状态类型试分析状态类型 例例4设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S=0,1,2,3,其一步其一步 转移概率矩阵为转移概率矩阵为 11 00 22 11 00 22 11 00 22 11 00 22 P = 试分析过程的周期性试分析过程的周期性 1 20 1 2 1 2 1 2 3 1 2 1 2 1 2 1 2 1 2 0,12,30,12,3? 周期为2. 例例5设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S=1,2,3,4,5,6, 其一步转移概率矩阵为其一步转移概率矩阵为 111 333 11 22 001000 000001 000010 000 100000 0000 P = 试分解此马尔可夫链试分解此马尔可夫链,并写出各状态类型及周期并写出各状态类型及周期. 1 2
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号