《中科院随机过程课件第5-6讲》由会员分享，可在线阅读，更多相关《中科院随机过程课件第5-6讲（20页珍藏版）》请在金锄头文库上搜索。
1、中科院研究生院 20062007 第一学期 随机过程讲稿 孙应飞 第二章第二章 Markov 过程过程 4. 马尔可夫链状态的分类马尔可夫链状态的分类 （六）闭集和状态空间的分解（六）闭集和状态空间的分解 定义：设定义：设C是状态空间是状态空间S的一个子集，如果从的一个子集，如果从C内任何一个状态内任何一个状态i不能到达 外的任何状态，则称 不能到达 外的任何状态，则称C是一个闭集。如果单个状态是一个闭集。如果单个状态i构成的集构成的集是闭集，则 称状态 是闭集，则 称状态i是吸收态。如果闭集是吸收态。如果闭集C中不再含有任何非空闭的真子集，则称中不再含有任何非空闭的真子集，则称C是不可 约的
2、。闭集是存在的，因为整个状态空间 是不可 约的。闭集是存在的，因为整个状态空间 Ci S就是一个闭集，当就是一个闭集，当S不可约时，则 称此马氏链不可约，否则称此马氏链可约。 不可约时，则 称此马氏链不可约，否则称此马氏链可约。 有关的性质：有关的性质： （1）C是闭集是闭集CjCip ji =,0CjCinp n ji =,),1(0 )( （2）C是闭集是闭集Cip Cj ji = , 1 （3）i为吸收态为吸收态1= i i p （4）齐次马氏链不可约任何两个状态均互通）齐次马氏链不可约任何两个状态均互通 （5）所有常返态构成一个闭集）所有常返态构成一个闭集 （6）在不可约马氏链中，所有
3、状态具有相同的状态类型）在不可约马氏链中，所有状态具有相同的状态类型 定义：对定义：对Si，若正整数集，若正整数集0, 1; )( n i i pnn 1 非空，则定义其最大公约数 为状态 非空，则定义其最大公约数 为状态i的周期，记为，当的周期，记为，当 i d= i d时，称该状态无周期。时，称该状态无周期。 定义：称非周期正常返状态为遍历态。定义：称非周期正常返状态为遍历态。 注意：一个不可约的、非周期的、有限状态的马氏链一定是遍历的。注意：一个不可约的、非周期的、有限状态的马氏链一定是遍历的。 （七）常返、非常返、周期状态的分类特性（七）常返、非常返、周期状态的分类特性 设设i，则，则
4、i和或者都是非常返态，或者都是零常返态，或者都是正常和或者都是非常返态，或者都是零常返态，或者都是正常jj 中科院研究生院 20062007 第一学期 随机过程讲稿 孙应飞 返非周期的（遍历） ，或者都是正常返有周期的且有相同的周期。返非周期的（遍历） ，或者都是正常返有周期的且有相同的周期。 非周期（遍历态） 有周期 正常返态 零常返态 常返态 非常返态 状态 （八）周期状态的判别（八）周期状态的判别 （1） 按互通性将状态分类后，在同一类集合中选一个状态判别其周期性即可。） 按互通性将状态分类后，在同一类集合中选一个状态判别其周期性即可。 （2） 如有正整数，使得，则状态 无周期。） 如有
5、正整数，使得，则状态 无周期。 n0,0 )1()( +n i i n i i ppi （3） 如有正整数， 使得步转移概率矩阵） 如有正整数， 使得步转移概率矩阵mm m P中相应某状态的那一列元素 全不为零，则状态无周期 中相应某状态的那一列元素 全不为零，则状态无周期 j j （九）分解定理（九）分解定理 （1） 齐次马氏链的状态空间） 齐次马氏链的状态空间S可唯一地分解为有限多个或可列多个互不相交 的状态子集之并，即有 可唯一地分解为有限多个或可列多个互不相交 的状态子集之并，即有L, 21 CCDLUUU 21 CCDS=。 其中：其中：D是非常返态集，每个是非常返态集，每个L, 2
6、 , 1,=nCn L, 2 , 1, 均是由常返状态组成的不可 约集，其中的状态互通，因此 均是由常返状态组成的不可 约集，其中的状态互通，因此=nCn , 中的状态具有相同的状态类 型：或者均为零常返；或者均为正常返非周期（遍历） ；或者均为正常返 有且有相同的周期；而且对于 中的状态具有相同的状态类 型：或者均为零常返；或者均为正常返非周期（遍历） ；或者均为正常返 有且有相同的周期；而且对于1= jin fCji。 （2） （周期链分解定理）一个周期为的不可约马氏链，其状态空间） （周期链分解定理）一个周期为的不可约马氏链，其状态空间dS可以 分解为 可以 分解为d个互不相交的集之并，
7、即有：个互不相交的集之并，即有： d JJJ, 21 ,L , 1 lkJJJS lk d r r = = I U 且且 L, 2 , 1,1 1 = + rJip r Jj ji r 其中约定。其中约定。 11 JJr= + 中科院研究生院 20062007 第一学期 随机过程讲稿 孙应飞 （3） 基于上面的（） 基于上面的（1） ，我们将状态空间） ，我们将状态空间S中的状态依的次序从 新排列，则转移矩阵具有以下的形式 中的状态依的次序从 新排列，则转移矩阵具有以下的形式 L, 21 CCD MO L 2 1 2 1 21 C C D P P PPP P DDD = 其中均为随机矩阵，他们
8、对应的链是不可约的。称以上形式的 转移矩阵为标准形式。 其中均为随机矩阵，他们对应的链是不可约的。称以上形式的 转移矩阵为标准形式。 L, 21 PP （十）有限马氏链的性质（十）有限马氏链的性质 （1） 所有非常返状态组成的集合不可能是闭集。） 所有非常返状态组成的集合不可能是闭集。 （2） 没有零常返状态。） 没有零常返状态。 （3） 必有正常返状态。） 必有正常返状态。 （4） 不可约有限马氏链只有正常返态。） 不可约有限马氏链只有正常返态。 （5） 状态空间可以分解为） 状态空间可以分解为 k CCCDSULUUU 21 = 其中：每个其中：每个C均是由正常返状态组成的有限不可约闭集，
9、 是非常返态集。 均是由正常返状态组成的有限不可约闭集， 是非常返态集。 kn n , 2 , 1,L= D （十一）例子（十一）例子 例例 1 设有三个状态设有三个状态的齐次马氏链，它的一步转移概率矩阵为：的齐次马氏链，它的一步转移概率矩阵为： 2, 1 , 0 = 3/23/10 4/14/12/1 02/12/1 P 试研究其状态关系。试研究其状态关系。 例例 2 设有四个状态设有四个状态的齐次马氏链，它的一步转移概率矩阵为：的齐次马氏链，它的一步转移概率矩阵为： 3, 2, 1 , 0 中科院研究生院 20062007 第一学期 随机过程讲稿 孙应飞 = 1000 4/14/14/14
10、/1 002/12/1 002/12/1 P 试研究其状态关系。试研究其状态关系。 解：解：正常返，正常返，非常返，非常返，吸收态。吸收态。 1 , 023 例例 3 设马氏链的状态空间为设马氏链的状态空间为5, 4, 3, 2, 1=S，一步转移概率为：，一步转移概率为： = 3/103/103/1 04/102/14/1 3/203/100 04/304/10 002/102/1 P 求此链的闭集。求此链的闭集。 解：画出状态转移图，此链可约，闭集为：解：画出状态转移图，此链可约，闭集为：。 5, 3, 1 例例 4 设马氏链的状态空间为设马氏链的状态空间为, 3 , 2 , 1L=S，转
11、移概率为：， ， ，转移概率为：， ， 2/1 11 =p 2/1 1 = +i i pSipi=,2/1 1 ，研究各状态的分类。，研究各状态的分类。 解：画出状态转移图，可知：解：画出状态转移图，可知： n n f = 2 1 )( 11 ，故，故1 2 1 1 11 = = =n n f，故状态，故状态 1 是常返的。是常返的。 又又=nff n ，故，故12/1 11 =nff n ，故，故14/3 11 =nff n ，故，故1 33 =f 因此，状态因此，状态 1 和和 2 为非常返态，为非常返态，3 为常返态。为常返态。 例例 7 设齐次马氏链的状态空间为设齐次马氏链的状态空间为
12、，一步转移矩阵为：，一步转移矩阵为： 4 , 3 , 2 , 1 = 02/102/1 03/23/10 0001 002/12/1 P 试研究其状态关系。试研究其状态关系。 解：画出状态转移图，可知：解：画出状态转移图，可知： 10) 1(0 44 )( 44 m j = n n Plim，其中，其中 是一随机矩阵，且它的各行 都相同。 是一随机矩阵，且它的各行 都相同。 证明： （证明： （A）时的情形；）时的情形； 1 此时，由题意可知，存在此时，由题意可知，存在 10= ij Si jiip ，即：，即： =P。 （2）, 1= Si i 推论推论 2 j n ji n n n pjX
13、P= )( limlim，即，即limjXP n n = 所取的值与初始状态 的分布无关。 所取的值与初始状态 的分布无关。 证：由于：证：由于： = = Si n ji Si nn iXPp iXPiXjXPjXP 0 )( 00 故故 )( 00 0 )( lim limlim n ji n j Si j Si j Si n ji n n n piXPiXP iXPpjXP = = 即， 经过无穷次转移后处于状态的概率与初始状态无关， 与初始状态的分布也 无关。 即， 经过无穷次转移后处于状态的概率与初始状态无关， 与初始状态的分布也 无关。 j 下面不加证明地给出几个常用的定理下面不加证
14、明地给出几个常用的定理 定 理 ： 若是 非 常 返 或 零 常 返 ， 则 对 于 任 意 的定 理 ： 若是 非 常 返 或 零 常 返 ， 则 对 于 任 意 的jSi， 有 。 ， 有 。 0limlim )( = n jin n pjXP= n 注意：当是正常返时，情况比较复杂，不一定存在，即使存在，注意：当是正常返时，情况比较复杂，不一定存在，即使存在，j )( lim n ji n p 中科院研究生院 20062007 第一学期 随机过程讲稿 孙应飞 也可能与也可能与i有关。有关。 x ) 定理：若是遍历状态，则对于任意的定理：若是遍历状态，则对于任意的jSi，有：，有： j j
15、i n ji n f p = )( lim 定理：对于不可约的遍历链，则对于任意的定理：对于不可约的遍历链，则对于任意的Sji,，有，有 j n ji n p 1 lim )( = 。 定理：若马氏链是不可约的遍历链，则定理：若马氏链是不可约的遍历链，则 =Si i i , 1 是方程组是方程组 Sjpxx Si jiij = , 满足条件满足条件1,0= Sj jj xSj的唯一解。的唯一解。 （二）平稳分布（二）平稳分布 定义： 一个定义在状态空间上的概率分布定义： 一个定义在状态空间上的概率分布= , 21 LL i 称为马氏链 的平稳分布，如有： 称为马氏链 的平稳分布，如有： P = 即，即，Sj，有：，有： = Si jiij p 平稳分
