中科院研究生院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 , iC, jC 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）在不可约马氏链中，所有状态具有相同的状态类型 定义：对 iS ，若正整数集 ; 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 , jC 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, iS ，研究各状态的分类。 解：画出状态转移图，可知： 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 是遍历的。 对于其它状态，由于 1i ,iS ，因此也是遍历的。 例 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 =
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 c,={16,7},它们互不相交,它们的并是整个状态空间,该过程具 有确定的周期转移,即:c1→c2→c3→c→c,周期为4 例5设齐次马氏链的状态空间为12,3},一步转移矩阵为: 1/21/41/4 P=03/41/4 001 求:(1)T的分布率及ET1,(2)f1(i=1,2,3) 解:(1)画出状态转移图,可得T的分布率为 1234 P=n 因此,E7=2mPT2==E3-4 (2)由于: f=1/2,fm=0,n>1,故f1=1/21,故f1=3/4 ∫=1,fm=0,n>1,故f3=1 因此,状态1和2为非常返态,3为常返态。 例6设齐次马氏链的状态空间为2,34},一步转移矩阵为: 1/21/200 1000 01/32/30 1/201/20
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 6 {6,7} c4 = ，它们互不相交，它们的并是整个状态空间，该过程具 有确定的周期转移，即： 1 2 3 4 1 c → c → c → c → c ，周期为 4。 例 5 设齐次马氏链的状态空间为 {1,2,3} ，一步转移矩阵为： = 0 0 1 0 3/ 4 1/ 4 1/ 2 1/ 4 1/ 4 P 求：（1） T13 的分布率及 ET13 ，（2） f (i =1,2,3) i i 解：（1）画出状态转移图，可得 T13 的分布率为： T13 = n 1 2 3 4 … n … { } P T13 = n 4 1 2 4 3 3 2 4 3 4 3 4 3 … n n 4 3 −1 … 因此， 4 4 3 { } 1 1 1 13 = 13 = = = = − = n n n n ET nP T n n 。 （2）由于： 1/2, 0 , 1 ( ) 11 (1) f 11 = f = n n ，故 f 11 =1/ 2 1 3/ 4, 0 , 1 ( ) 11 (1) f 22 = f = n n ，故 f 11 = 3/ 4 1 1, 0 , 1 ( ) 11 (1) f 33 = f = n n ，故 f 33 =1 因此，状态 1 和 2 为非常返态，3 为常返态。 例 6 设齐次马氏链的状态空间为 {1,2,3,4} ，一步转移矩阵为： = 1/ 2 0 1/ 2 0 0 1/3 2/3 0 1 0 0 0 1/ 2 1/ 2 0 0 P
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 试研究其状态关系。 解:画出状态转移图,可知: f4=0(m≥1)→f4=01)→f3=5<1 故状态3和4为非常返态。 f1=f+f1+0+…+ f2=∑/2”=0+x 24 1=∑mf1"=1×+2 2=∑nf2=1×0+2×+…+n 故状态1和2都是正常返的,易知它们是非周期的,从而是遍历 状态。 例7设一齐次马氏链的状态空间为S={01,…},其状态转移 矩阵为: PoP。000 0p100 1-p200P20 试讨论此链状态的分类及常返的充分必要条件。 例8设一口袋中装有三种颜色(红、黄、白)的小球,其数 量分别为3、4、3。现在不断地随机逐一摸球,有放回,且视摸 出球地颜色计分:红、黄、白分别计1、0、-1分。第一次摸球 之前没有积分。以y表示第n次取出球后的累计积分,n=01
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 7 试研究其状态关系。 解：画出状态转移图，可知： 0 ( 1) 44 0 1 ( ) f 44 = n f = n 1 3 2 , 0 ( 1) 3 2 33 ( ) 33 (1) f 33 = f = n f = n 故状态 3 和 4 为非常返态。 0 0 1 (2) 11 (1) f 11 = f 11 + f + ++ += 1 2 1 4 1 2 1 0 1 1 ( ) 22 = 22 = + + + + + = − = n n n f f = = + = = 2 3 2 1 2 2 1 1 1 ( ) 1 11 n n nf = = + + + − + = = 3 2 1 2 1 1 0 2 1 1 ( ) 2 22 n n n nf n 故状态 1 和 2 都是正常返的，易知它们是非周期的，从而是遍历 状态。 例 7 设一齐次马氏链的状态空间为 S ={0,1,2, } ，其状态转移 矩阵为： − − − 1 0 0 0 1 0 0 0 1 0 0 0 2 2 1 1 0 0 p p p p p p 试讨论此链状态的分类及常返的充分必要条件。 例 8 设一口袋中装有三种颜色（红、黄、白）的小球，其数 量分别为 3、4、3。现在不断地随机逐一摸球，有放回，且视摸 出球地颜色计分：红、黄、白分别计 1、0、-1 分。第一次摸球 之前没有积分。以 Yn 表示第 n 次取出球后的累计积分， n = 0,1,
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (a)y,n=01…是否齐次马氏链?说明理由。 (b)如果不是马氏链,写出它的有穷维分布函数族;如果是, 写出它的一步转移概率p和两步转移概率p(2) (c)令tn=mn{n;yn=0,n>0,求P{r=5}。 附录:转移矩阵估计问题 设{Xn;n≥0}为一齐次马氏链,状态空间为S,我们有此马氏 链的一次实现(样本)x,x,…,x,而转移矩阵未知,如何用现 有数据来估计转移矩阵P? 记在状态i之后首次出现状态j的时间为n(,j,定义似然函 数 L=∏P 相应的对数似然函数为: L=∑m()hp ∑∑m(i,j)hp JES i∈sj∈ 利用约束条件∑P=lv∈S,由极大似然估计法(MLEs)我们 有如下估计式: P n(i,j) ∑n(i,k) 注:此估计为局部最大估计。也可以由以下引理得到以上的 估计。 引理:设:20(i≤N),则在约束条件∑x=1,x≥0(≤N)下, 函数∑hx在x=x(i≤N)处取得最大
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 8 （a） Yn ， n = 0,1, 是否齐次马氏链？说明理由。 （b）如果不是马氏链，写出它的有穷维分布函数族；如果是， 写出它的一步转移概率 ij p 和两步转移概率 (2) pij 。 （c）令 min{ ; 0, 0} 0 = n Yn = n ，求 { 5} P 0 = 。 附录：转移矩阵估计问题 设 {X ; n 0} n 为一齐次马氏链，状态空间为 S ，我们有此马氏 链的一次实现（样本） N x , x , , x 0 1 ，而转移矩阵未知，如何用现 有数据来估计转移矩阵 P ? 记在状态 i 之后首次出现状态 j 的时间为 n(i, j) ，定义似然函 数： = i j S n i j L pij , ( , ) 相应的对数似然函数为： = = i S j S ij i j S L n(i, j)ln pij n(i, j)ln p , 利用约束条件 p i S j S ij = 1 ，由极大似然估计法（MLEs）我们 有如下估计式： = k S ij n i k n i j p ( , ) ( , ) ˆ 注：此估计为局部最大估计。也可以由以下引理得到以上的 估计。 引理：设 z 0 (i N) i ，则在约束条件 1, 0 ( ) 1 x xi i N N i i = = 下， 函数 = N i i i z x 1 ln 在 ( ) 1 i N z z x N i i i i = = 处取得最大
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 5.马氏链的极限性态与平稳分布 关心的问题 (1)当n→∞时,P{Xn=i}=z、(n)的极限是否存在? (2)在什么情况下,一个马氏链是一个平稳序列? 关于第一个问题,由于:x、n)=∑x(O)P,其中 ,(O)=P{X0=i},{z、(),i∈S}是马氏链的初始分布,因此,问题 可以转化为研究p的极限性质,即研究mP是否存在?存在 的话,其极限是否与i有关? 关于第二个问题,实际上是一个平稳分布是否存在的问题。 (一)P"的极限性态 定理:设有一有限状态的马氏链,若存在一个正整数m,使 得对于vi,∈S,有p)>0,则imP"=丌,其中z是一随机矩阵, 且它的各行都相同。 如果状态空间是无限可列的马氏过程,则定理要修改为: (1)或者是x中的所有元素都大于零(此时仍为随机矩阵) (2)或者是x中的所有元素都等于零
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 9 5．马氏链的极限性态与平稳分布 关心的问题： （1） 当 n → 时， P{X i} (n) n = = i 的极限是否存在？ （2） 在什么情况下，一个马氏链是一个平稳序列？ 关 于 第 一 个 问 题 ， 由 于 ： = i S n j n i pi j ( ) ( ) (0) ， 其 中 (0) { } 0 P X i i = = ， { (0), i S} i 是马氏链的初始分布，因此，问题 可以转化为研究 (n) i j p 的极限性质，即研究 ( ) lim n i j n p → 是否存在？存在 的话，其极限是否与 i 有关？ 关于第二个问题，实际上是一个平稳分布是否存在的问题。 （一） n P 的极限性态 定理：设有一有限状态的马氏链，若存在一个正整数 m ，使 得对于 i, jS ，有 0 ( ) m pi j ，则 = → n n lim P ，其中 是一随机矩阵， 且它的各行都相同。 如果状态空间是无限可列的马氏过程，则定理要修改为： （1） 或者是 中的所有元素都大于零（此时仍为随机矩阵） （2） 或者是 中的所有元素都等于零
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 推论1P"的极限矩阵x是唯一的,且满足: 丌,P 0,即:m= (2)∑兀=1 推论2mP{Xn=}=mp=x,即mP{Xn=所取的值与初 始状态的分布无关。 证:由于: P{X=丹}=∑PXn=X0=1P{X0=1 ∑P”P{X=} 故 mP(X,=}=m∑PP(X=} ∑丌,PX0=l}=z∑P(X。=l} 丌1= lim p 即,经过无穷次转移后处于j状态的概率与初始状态无关,与初 始状态的分布也无关。 下面不加证明地给出几个常用的定理 定理:若j是非常返或零常返,则对于任意的i∈S,有 imP{Xn=j}=limp/=0
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 10 推论 1 n P 的极限矩阵 是唯一的，且满足： （1） = , 0 j i i S i pi j ，即： P = 。 （2） =1, iS i 推论 2 j n i j n n n P X = j = p = → → ( ) lim { } lim ，即 lim P{X j} n n = → 所取的值与初 始状态的分布无关。 证：由于： = = = = = = = i S n i j i S n n p P X i P X j P X j X i P X i { } { } { } { } 0 ( ) 0 0 故 ( ) 0 0 0 ( ) lim { } { } lim { } lim { } n i j n j i S j i S j i S n i j n n n p P X i P X i P X j p P X i → → → = = = = = = = = = 即，经过无穷次转移后处于 j 状态的概率与初始状态无关，与初 始状态的分布也无关。 下面不加证明地给出几个常用的定理 定理：若 j 是非常返或零常返，则对于任意的 iS ，有 lim { } lim 0 ( ) = = = → → n i j n n n P X j p