随机过程18(4.3).ppt

1、3. 状态空间的分解状态空间的分解iiii若，则.则约定互通满足：(1)(2)(3),iiijjiij jkik自反性：对称性：传递性：即互通是一种等价关系.利用该等价关系划分S为12mnnnSSmSnSmn ， ， ，( ),nii称S 为一个以后将包含等价类.S的等价类记为则( )S iij ji( )( )S iS jij ( )nnS iSiS( ) i 有何S特性？定义定义(1) 闭集( )0,nijp则称C为闭集.(2) 吸收状态(3) 不可约闭集设C为闭集,若C中不再含任何非空真则称C闭子集,不是可约闭集.不可约(4)马尔可夫链S若状态空间 是不可约的，则称该马尔可夫链是.否则称

2、为不可约的可约的.0,iCjCn 设C为S的子集.若对，,和有iSii设,若子集是闭集,则称状态 为吸收态.引理引理7 (有关闭集的判定和性质有关闭集的判定和性质)0( ),1ijCpiC jC 是闭集(2)1,ijj CCpiC 是闭集( )1(,30)ijnj CCpiC n 是闭集1(4)iiiip是吸收态(即为闭集)证明证明 (1)C若 是闭集, 0,ijiC jCp由定义,0ijiC jCp 反之，若对，( )0,0nijiCjCnp （要证：，,和有）用数学归纳法用数学归纳法(0)0ijpiCjC ，(1)0ijpiCjC ，( )0kijpnkiCjC 假设时，1C-Knk则时，

3、由方程(1)( )kkijilljlpppiCjC （，）)(klkillCjjilll Cpppp000,nijnpiCjC （ ）对，C 是闭集引理引理8( )( )S iS i若等价类是闭集，则不可约的.证明证明设CS(i)是非空闭集.jCjkk 对，（若，则由闭集定义：C）()(jSS iCi又为等价类，且( ) ilS任取ljlC ( ) i 从而SC( )CS i( )S i所以，不可约的.引理引理9设设C是闭集是闭集,则当且仅当其中任何两个状态则当且仅当其中任何两个状态互通时互通时,C为不可约的为不可约的.证明证明设C中任何两状态互通.8与引理 证明相同， C为不可约的.C为不反

4、之，若可约的.C（反证法证明 中任意两状态互通）,i jC ijij假设且 :,Dil ilC il 令D则 一定是非空闭集DlD kDlk（事实上,若 不是闭集,则有,使,Dilik再由 的构造知:且kD 矛盾）jD又DC是 的非空的真闭子集.与C不可约矛盾.ij .jjii同理所以推论推论 齐次马尔可夫链是不可约的充要条件是齐次马尔可夫链是不可约的充要条件是它的任何两个状态互通它的任何两个状态互通特别关于特别关于有限状态的马尔可夫链有限状态的马尔可夫链有下面结论有下面结论定理定理7(1) 有限齐次马尔可夫链所有有限齐次马尔可夫链所有非常返状态集非常返状态集D不可能不可能 是闭集是闭集.(2

5、) 有限齐次马尔可夫链有限齐次马尔可夫链不可能存在零常返状态不可能存在零常返状态.(3) 不可约的有限齐次马尔可夫链的所有状态都是不可约的有限齐次马尔可夫链的所有状态都是 正常返状态正常返状态.证明证明01)1(nijj DDinpD （ ）若 是闭集，则对，有，lim0nijnjDp（ ）又为非常返，limli1m0nnijijj DDnnjpp（ ）（ ）D矛盾！所以 不是闭集2i若有某状态 是（ ）零常返，则令iCjij：iC则可以证明为闭集.1则与（）相同的证明，矛盾！132由（）（）可得.定理定理 8( )( )iSiS iS i设是常返态，则包含的等价类是闭集.从而是不可约的.证明

6、证明( ),jS ikSjkkj 对若，则（常返态的可达，即互通）( )kS i( )S i是闭集.( )S i是不可约集.由以上的分析由以上的分析,可以得到状态空间的分解定理可以得到状态空间的分解定理定理定理 9齐次马尔可夫链的齐次马尔可夫链的状态空间状态空间S可唯一地分解成有限个可唯一地分解成有限个或可列无限多个互不相交的状态子集的并或可列无限多个互不相交的状态子集的并.即即12CDCS 其中其中 D是所有是所有非常返状态非常返状态构成的状态子集构成的状态子集.1,2,nC n( =)所有所有常返状态常返状态构成的构成的不可约闭集不可约闭集.每个状态子集中的状态有着相同的状态类型每个状态子

7、集中的状态有着相同的状态类型:(即即 或者均为零常返或者均为零常返,或者均为正常返非周期或者均为正常返非周期,或者均为正常返周期且周期相同或者均为正常返周期且周期相同.),1niji jCf且对引理引理1012()()21,0,0nnijijdi jCppd nn设C是不可约闭集，周期为对，若，则证明证明C是不可约闭集Cjiji对，有( )0,0njinp 使1122()()()()( )( )00nnnnnnnniiijjiiiijjipppppp12d nnd nn21d nn定理定理10 (周期链分解定理周期链分解定理)12,dddJ JJ设C是周期为 的不可约闭集，C可为 个互唯一分解

8、不相交的状态子集之并，即1,1,2,mmdmlJJmlldCmJ 111,1,2, .1mkjj JmdpkJmdJJ而且对有并约定证明思路证明思路: 从三个方面证明从三个方面证明 (1) 分解式的存在性分解式的存在性(2) 转移规则的合理性转移规则的合理性(正确性正确性)(3) 分解式的唯一性分解式的唯一性证明证明 (1) 分解式的存在性分解式的存在性(),0,0nd mimjCJjnpi 取记，1dmmCJ则1,2,mdmlmlJJ 且时，mljJJ（事实上,若120mJnn则由的构造知：0，使12()()00n d mn d lijijpp，10-d l m由引理知：，lmd但1，0lm

9、lm ，即mlJJ ）(2) 转移规则的正确性转移规则的正确性1,1mmkjj JkJp （即对有）,mkJC 对有C 为闭集，11mmkjj JkC Jjjpp mmJkJn由的构造知：0使()0nd mikp11mmjCJjJ又即110nd mmijJp（）又由的构造知：对，有nn对上述 有(1)()00knd mnd mijikjppp1kjj Cp()0nd mikkjpp0kjp11mkjj Jp(3) 分解式的唯一性分解式的唯一性1dmmiCJ设对状态，1dmmiCJ设对另一状态 ，,mmj kJj kJ（下证：对，一定也有）liJ不妨设ml若，-2,.m lm ldm ldjk则

10、从i 出发，能且只能在步，步，步到达 或,m lmj kJJ由的定义知：ml若，-( -)-2.idl mm ldm ldjk则从 出发，能且只能在步，步上，到达 或,mm l dj kJJ 再由的定义知：分解式是唯一的定理定理11012ndn设X ， ， ， 是周期为 的不可约的齐次马尔可夫链.状态空间S被唯一分解为d个互不相交的状态子集的并，即1dmmSJ12nndYXn， ，则0, ,2 ,0,1,nddXn 仅在时刻上考虑即令( )( ),0,1,2,1ddnijY nPp 是以（）为一步转移概率矩阵的新的齐次马（）尔可夫链证明证明 (1)0110, , ,nni iii jS 对及有

11、0011111(,)nnnnYjYPYi YiYii001(1()1)1(,)dnnnddndPXiXiXXjXii(1)()ndndXj XiP1()nnP Yj Yi0()dXjPXi( )dijp,0,1,2,(1,2, )2.nmmY nJmdJ对而言,每个都是不可约闭集，而且中的状态都是非（周期的）,1kjmdj JmkpJ （ ）由定理10知：对有,0,1,2,(1, )nmY nJmd对而言,每个都是闭集.,mj kJ又对,1,2,nXn 因为不可约，00NjkNp（ ），使,mj kJNnd只 能 是 形 如的 正 整 数,0,1,2,nY njk对而言,kj同理,jkmJ是不

12、可约的.id又由于的周期为 ，10,0,0ndndiiiiNnNpp（）（） ）当时，5.3.5由定理,0,1,2,nY ni对而言,状态 是非周期的.,0,1,2,0,1,2,.3nnXnY n如果的所有状态皆为常返状态，则,的所有状态也（都是常返状态）mjJdn 对，由周期定义:当 不能整除 时,有( )0njjp( )0njjf1jjf ( )()11nndjjjjnnffj 是常返态,0,1,2,.njY n对而言也是常返的例例1 设状态空间设状态空间S=0,1,2的马尔可夫链的马尔可夫链,它的一步它的一步 转移概率矩阵为转移概率矩阵为1102211124412033P研究其状态间的关

13、系以及状态类型研究其状态间的关系以及状态类型12012121214141323(都是遍历态）例例2 设状态空间设状态空间S=1,2,3,4的马尔可夫链的马尔可夫链,它的一步它的一步 转移概率矩阵为转移概率矩阵为110022110022111144440001P试分析状态类型试分析状态类型123412121212141414141例例3 设设Xn,n=0,1,2,是一齐次马尔可夫链是一齐次马尔可夫链, 状态空间状态空间 S=1,2,3,4,5,其一步转移概率矩阵为其一步转移概率矩阵为0.500.50000.2500.750000.300.70.250.500.2500.300.300.4P试分析

14、状态类型试分析状态类型0.50.3123540.30.250.250.250.50.50.30.750.30.7例例4 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S=0,1,2,3,其一步其一步 转移概率矩阵为转移概率矩阵为110022110022110022110022P试分析过程的周期性试分析过程的周期性120121212312121212120,12,30,12,3周期为2.例例5 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S=1,2,3,4,5,6,7,8, 其一步转移概率矩阵为其一步转移概率矩阵为1114241122123311220000000000000000

15、000000100000000100000001000000010000000P研究过程的周期性12121312121214141253467823111112,3,45,67,81周期为4.例例5 设齐次马尔可夫链的状态空间设齐次马尔可夫链的状态空间S=1,2,3,4,5,6, 其一步转移概率矩阵为其一步转移概率矩阵为11133311220010000000010000100001000000000P试分解此马尔可夫链试分解此马尔可夫链,并写出各状态类型及周期并写出各状态类型及周期.121312123564111113131,3,542,6S1,3,52,6子集与为闭集为正常返态4为非常返态1,3,52,6子集的周期为3；的周期为1，即为遍历态.