中科院研究生院《随机过程》讲稿：第二章 Markov 过程（2-6）闭集和状态空间的分解

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 第二章 Markov过程 (六)闭集和状态空间的分解 定义:设C是状态空间S的一个子集,如果从C内任何一个状 态i不能到达C外的任何状态,则称C是一个闭集。如果单个状 态i构成的集l}是闭集,则称状态是吸收态。如果闭集C中不 再含有任何非空闭的真子集则称C是不可约的闭集是存在的, 因为整个状态空间S就是一个闭集,当S不可约时,则称此马氏 链不可约,否则称此马氏链可约 有关的性质: (1)C是闭集台p,=0,Vi∈C,jC台pm)=0(m≥1),V∈C,j丝C (2)C是闭集∑p=1,vi∈C (3)i为吸收态p=1 (4)齐次马氏链不可约分任何两个状态均互通 (5)所有常返态构成一个闭集 (6)在不可约马氏链中,所有状态具有相同的状态类型 定义:对∈S,若正整数集{n;n≥1,p>0}非空,则定义其 最大公约数为状态i的周期,记为d,当d=1时,称该状态无周 期 定义:称非周期正常返状态为遍历态

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 1 第二章 Markov 过程 （六）闭集和状态空间的分解 定义：设 C 是状态空间 S 的一个子集，如果从 C 内任何一个状 态 i 不能到达 C 外的任何状态，则称 C 是一个闭集。如果单个状 态 i 构成的集 {i} 是闭集，则称状态 i 是吸收态。如果闭集 C 中不 再含有任何非空闭的真子集，则称 C 是不可约的。闭集是存在的， 因为整个状态空间 S 就是一个闭集，当 S 不可约时，则称此马氏 链不可约，否则称此马氏链可约。 有关的性质： （1） C 是闭集  pi j = 0 , iC, jC  p n i C j C n i j = 0 ( 1),   ,  ( ) （2） C 是闭集  p i C j C  i j =    1, （3） i 为吸收态  pi i =1 （4）齐次马氏链不可约  任何两个状态均互通 （5）所有常返态构成一个闭集 （6）在不可约马氏链中，所有状态具有相同的状态类型 定义：对 iS ，若正整数集  ; 1, 0 ( )   n n n pi i 非空，则定义其 最大公约数为状态 i 的周期，记为 i d ，当 di =1 时，称该状态无周 期。 定义：称非周期正常返状态为遍历态

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 注意:一个不可约的、非周期的、有限状态的马氏链一定是 遍历的。 (七)常返、非常返、周期状态的分类特性 设ij,则和j或者都是非常返态,或者都是零常返态,或 者都是正常返非周期的(遍历),或者都是正常返有周期的且有 相同的周期。 非常返态 零常返态 状态 常返态 正常返态{有周期 非周期(遍历态) (八)周期状态的判别 (1)按互通性将状态分类后,在同一类集合中选一个状态判别 其周期性即可。 (2)如有正整数n,使得p">0,p)>0,则状态无周期。 (3)如有正整数m,使得m步转移概率矩阵P中相应某状态j 的那一列元素全不为零,则状态j无周期 (九)分解定理 (1)齐次马氏链的状态空间S可唯一地分解为有限多个或可 2

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 2 注意：一个不可约的、非周期的、有限状态的马氏链一定是 遍历的。 （七）常返、非常返、周期状态的分类特性 设 i  j ，则 i 和 j 或者都是非常返态，或者都是零常返态，或 者都是正常返非周期的（遍历），或者都是正常返有周期的且有 相同的周期。                非周期（遍历态） 有周期 正常返态 零常返态 常返态 非常返态 状态 （八）周期状态的判别 （1） 按互通性将状态分类后，在同一类集合中选一个状态判别 其周期性即可。 （2） 如有正整数 n ，使得 0 , 0 ( ) ( 1)   n+ i i n pi i p ，则状态 i 无周期。 （3） 如有正整数 m ，使得 m 步转移概率矩阵 m P 中相应某状态 j 的那一列元素全不为零，则状态 j 无周期 （九）分解定理 （1） 齐次马氏链的状态空间 S 可唯一地分解为有限多个或可

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 列多个互不相交的状态子集D,C1,C2…之并,即有 S=D∪C1∪C2U…° 其中:D是非常返态集,每个Cn,n=1,2…均是由常返状态 组成的不可约集,其中的状态互通,因此C,n=1,2,…中的 状态具有相同的状态类型:或者均为零常返;或者均为正 常返非周期(遍历);或者均为正常返有且有相同的周期; 而且对于i,j∈Cn,f,=1 (2)(周期链分解定理)一个周期为d的不可约马氏链,其状 态空间S可以分解为d个互不相交的集J,2…,J之并, 即有: S=UJ,J∩J=②,k 且 其中约定J=。 (3)基于上面的(1),我们将状态空间S中的状态依 D,C1,C2…的次序从新排列,则转移矩阵具有以下的形式 PPP P 其中P,P…均为随机矩阵,他们对应的链是不可约的。称 以上形式的转移矩阵为标准形式

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 3 列 多 个互 不相 交 的状 态子 集 D , C1 , C2 ,  之 并 ，即有 S = D  C1  C2 。 其中： D 是非常返态集，每个 C n , n =1,2,  均是由常返状态 组成的不可约集，其中的状态互通，因此 C n , n =1,2,  中的 状态具有相同的状态类型：或者均为零常返；或者均为正 常返非周期（遍历）；或者均为正常返有且有相同的周期； 而且对于 i , jC n , f i j =1。 （2） （周期链分解定理）一个周期为 d 的不可约马氏链，其状 态空间 S 可以分解为 d 个互不相交的集 d J , J , , J 1 2  之并， 即有： , , , 1 S J J J k l k l d r = r =   =   且 1, , 1,2, 1  =  =  + p i J r r j J i j r 其中约定 1 1 J J r+ = 。 （3） 基于上面的（ 1）， 我 们 将 状 态空间 S 中的状态依 D , C1 , C2 ,  的次序从新排列，则转移矩阵具有以下的形式    2 1 2 1 1 2 C C D P P P P P P D D D               = 其中 P1 , P2 ,  均为随机矩阵，他们对应的链是不可约的。称 以上形式的转移矩阵为标准形式

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (十)有限马氏链的性质 (1)所有非常返状态组成的集合不可能是闭集。 (2)没有零常返状态。 (3)必有正常返状态。 (4)不可约有限马氏链只有正常返态。 (5)状态空间可以分解为 S=DUC1UC2U…UC 其中:每个C,n=1,2,…,k均是由正常返状态组成的有限不 可约闭集,D是非常返态集 (十一)例子 例1设有三个状态{0,1,2}的齐次马氏链,它的一步转移概率 矩阵为: /21/20 P=1/21/41/4 01/32/3 试研究其状态关系。 例2设有四个状态{02,3的齐次马氏链,它的一步转移概 率矩阵为 /21/200 1/21/200 1/41/41/41/4 000

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 4 （十）有限马氏链的性质 （1） 所有非常返状态组成的集合不可能是闭集。 （2） 没有零常返状态。 （3） 必有正常返状态。 （4） 不可约有限马氏链只有正常返态。 （5） 状态空间可以分解为 S = D  C1  C2  Ck 其中：每个 C n k n , =1,2,  , 均是由正常返状态组成的有限不 可约闭集， D 是非常返态集。 （十一）例子 例 1 设有三个状态 {0,1,2} 的齐次马氏链，它的一步转移概率 矩阵为：           = 0 1/3 2/3 1/ 2 1/ 4 1/ 4 1/ 2 1/ 2 0 P 试研究其状态关系。 例 2 设有四个状态 {0,1,2,3} 的齐次马氏链，它的一步转移概 率矩阵为：               = 0 0 0 1 1/ 4 1/ 4 1/ 4 1/ 4 1/ 2 1/ 2 0 0 1/ 2 1/ 2 0 0 P

中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 试研究其状态关系。 解:{0}正常返,{2}非常返,吕3}吸收态。 例3设马氏链的状态空间为S={12.3…},转移概率为: P1=1/2,pm1=1/2,p1=112,i∈S,研究各状态的分类。 解:画出状态转移图,可知: ,故f1=∑=1,故状态1是常返的 又1=∑叫<∞,故状态1是正常返的 易知状态1是非周期的,从而状态1是遍历的。 对于其它状态,由于1<i,i∈S,因此也是遍历的。 例4设有八个状态{0,1,2,3,4,5,6,7}的齐次马氏链,它的一步转移 概率矩阵为: 01/41/21/40000 00001/21/200 00001/32/300 00000100 P 00000010 0000001/21/2 10000000 10000000 讨论其周期性。 解:主对角线为0,它是具有周期性的转移矩阵的标准形式。 八个状态可以分为四个子集,c1={0},c2={2,3},c={4,5}

中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 5 试研究其状态关系。 解： {0,1} 正常返， {2} 非常返， {3} 吸收态。 例 3 设马氏链的状态空间为 S ={1,2,3, } ，转移概率为： p11 =1/ 2 ， pi i+1 =1/ 2 ， pi1 =1/ 2, iS ，研究各状态的分类。 解：画出状态转移图，可知： n n f       = 2 ( ) 1 11 ，故 1 2 1 1 11  =      =   n= n f ，故状态 1 是常返的。 又         =   =1 1 2 1 n n  n ，故状态 1 是正常返的。 易知状态 1 是非周期的，从而状态 1 是遍历的。 对于其它状态，由于 1i ,iS ，因此也是遍历的。 例 4 设有八个状态 {0,1,2,3,4,5,6,7} 的齐次马氏链，它的一步转移 概率矩阵为：                           = 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1/ 2 1/ 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1/3 2/3 0 0 0 0 0 0 1/ 2 1/ 2 0 0 0 1/ 4 1/ 2 1/ 4 0 0 0 0 P 讨论其周期性。 解：主对角线为 0，它是具有周期性的转移矩阵的标准形式。 八个状态可以分为四个子集， {0} c1 = ， {1,2,3} c2 = ， {4,5} c3 =