《markov链的状态分类》由会员分享，可在线阅读，更多相关《markov链的状态分类（41页珍藏版）》请在金锄头文库上搜索。
1、3.2 Markov链的状态分类,互达性和周期性,注: 引入互达性概念是为了对状态进行分类.,命题3.1 互达性是等价关系, 即满足: (1) 自反性: ii ; (2) 对称性: 若ij, 则ji ; (3) 传递性: 若ik 且kj, 则ij .,证: (3) 若ik 且kj, 则存在整数n和m使得:,由Chapman-Kolmogorov方程得:,即: ij. 类似可证ji.,在数学上, 等价关系可以用于对集合进行分割. 因此, 我们也可以利用互达性对状态空间进行分类, 并且这些类在互达关系下是等价类.,定义3.4 一个Markov链的状态空间, 如果在互达性这一等价关系下都居于同一类,
2、 那么就称这个Markov链是不可约的. 否则, 这个Markov链就被称为是可约的.,注: 引入可约/不可约概念是为了以后研究状态的周期,进一步是为了研究转移概率的极限性质.,则显然1, 2和3, 4, 5是状态在互达意义下的两个等价类. 因此, 这个Markov链是可约的. 比如其中一个子链为:,例3.6 若Markov链有转移概率矩阵,给出这个Markov链状态的等价类, 并且试给出其n步转移概率矩阵.,练习: 若Markov链有转移概率矩阵,答: 等价类为: 1, 4, 2, 5和3. 其中3为吸收态.,用Mathematica软件计算知:,所以,定义3.5 设i为Markov链的一个
3、状态, 使 的所有正整数n (n1)的最大公约数, 称为状态i的周期, 记作d(i) 或 di . 如果对所有n1, 都有 , 则约定周期为; d(i)=1的状态i称为是非周期的.,推论: 如果n不能被周期d(i)整除, 则必有 .,注: 当状态i的周期为d时, 不一定成立.,解: 状态转移可以用下图表示,用数学归纳法不难求出:,所以 d(0) = 2.,解: 状态转移可以用下图表示,所以 d(1) = 2. 您能求出状态2的周期吗?,命题3.2 如果ij, 则 di = dj.,证: 设m1, n1,使得 , 则,因此, m+n同时能被di及dj整除. 对于任意的s1,即: m+s+n也能被
4、dj整除. 因此, s能被dj整除. 从而dj整除的 最大公因子di. 根据对称性, di也整除dj , 所以 di = dj .,满足 , 则,引理3.1 设m2, 正整数s1, s2, sm的最大公因子为d, 则存在正整数N, 使得nN时, 必有非负整数c1, c2,cm使 .,我们引入状态周期概念的目的，是为了研究状态转移矩阵的极限性质，即当n时P(n)的极限，这个矩阵可以反映出Markov链在平稳状态时的特征。因此，下面我们将讨论周期的基本性质，为此先给出一个数论中的结论：,推论3.1 设状态i的周期为di. 如果 , 则存在整数N, 使得对所有nN恒有,证: 这时存在正整数s1, s
5、2, sm, 使得它们的最大公因子为d, 且 .,命题3.3 如果状态i有周期d, 则存在整数N, 使得对所有nN恒有 .,由引理3.1, 存在正整数N, 使得nN时, 必有非负整数c1, c2,cm使 . 从而,因为状态空间有限, 对全部的状态对(i,j), 求出N(i,j). 并取 , 则显然对所有状态i和j, 当nN时有 .,证: 由于Markov链是不可约的, 过程的任两个状态i和j都是互达的, 于是m (与i和j有关)使得 . 由推论3.1及链的非周期性知, 存在N, 使得当nN时, .,命题3.4 设P为一个不可约、非周期、有限状态Markov链的转移矩阵, 则必存在N, 使得当n
6、N时, P(n)的所有元素都大于0.,常返与瞬过,定义： 则 表示从状态i出发在第n次转移时首次到达状态j的概率。,定义： 则 表示从状态i出发在第n次转移时首次回到状态i的概率。,定义： 则 表示从状态i出发最终到达状态j的概率.,定义3.5 如果 fii = 1, 则称状态i是常返的. 否则, 即fii1, 称状态i为非常返的或瞬过的.,注: 如果状态i是常返的, 那么从状态i出发经过有限步转移后最后又回到i的概率为1.,定义： 表示在0时刻从状态i出发首次到达状态j的所需要转移的步数, 即 如果 , 则,补充:,我们有 , 因此,注: 上式告诉我们为什么fii=1表示常返.,证:,由过程
7、的Markov性, 一旦回到i, 过程以后的发展只依赖当前, 因此从i出发至少回到i两次的概率是 , 依此类推. 用随机变量K表示过程返回i的次数, 则,于是K的条件期望为:,显然,下面我们将证明:,令 , 则 , 于是,因此,推论3.2 如果i是常返的, 且ij, 则i也是常返的.,证: 由ij知存在m,n使 和 , 于是对任何正整数 s 0, 有,因此,例3.9 考虑整数点上的随机游动. 向右移动一格的概率为p, 向左移动一格的概率为q=1-p. 从原点0出发, 则一步转移概率矩阵为:,所以,利用Stirling公式知, 当n充分大时,于是,因此, 当p=0.5时 , 当p0.5时,即当p
8、=0.5时状态0是常返的; 当p0.5时0是瞬过的.,定义 对常返状态i我们定义Ti为首次返回状态i的时刻, 即: 称作常返时. 记 , 则有 , 所以是首次返回i的期望步数, 叫作状态i的平均常返时.,定义 一个常返状态i当且仅当i=时称为是零常返的, 当且仅当i时称为正常返的.,课外作业: Page 58, Ex 9 Page 59, Ex 11, 14 其中14(1) 的矩阵改为:,根据转移矩阵的不同结构，马氏链可以分为多个不同的类型，这里，我们只简单介绍其中常见而又较为重要的两类：正则链与吸收链,定义C1. 对于马氏链，若存在一正整数k，使其转移矩阵M的k次幂Mk 0（每一分量均大于0
9、），则称此马尔链为一正则链(regular chain),补充：正则链与吸收链,定理C1. 若A为正则链的转移矩阵，则必有： (1) ，其中W为任一分量均大于零的随机矩阵； (2) W的所有行向量均相同,定理C2. 记定理 C1中W的行向量为=(1, m)，则： (1) 对任意随机向 量x，有 ； (2) 是P的不动点向量,即P=, P的不动点向量是唯一的,定义C2. 状态Si 称为马氏链的吸收状态，若转移矩阵P的第i 行满足：Pii=1，Pij=0 (ji),定义C3. 马氏链被称为吸收链，若其满足： (1) 至少存在一个吸收状态 ； (2) 从任一状态出发，经有限步转移总可到达某一吸收 状
10、态,根据定义C3，例3.1中Xn即 为一吸收链,定理C3. 吸收链的基矩阵B中的每个元素，表示过程从一个非吸收状态出发到达每个非吸收状态的平均转移次数,定理C4. 设N=BC, B为吸收链的基矩阵, C=(1,1,1)T，则N的每个元素表示从非吸收状态出发，到达某个吸收状态被吸收之前的平均转移次数,定理C5. 设F=BR=(fij)，其中B为吸收链的基矩阵，R为T中的子阵，则fij表示从非吸收状态i出发，被吸收状态 j吸收的概率,例C1.1 (竞赛问题) 甲乙两队进行一场抢答竞赛，竞赛规则规定：开始时每队各记2分，抢答题开始后，如甲取胜则甲加1分而乙减1分，反之则乙加1分甲减1分 (每题必需决
11、出胜负 )规则还规定，当其中一方的得分达 到4分时，竞赛结束求： (1) 甲队获胜的概率有多大？ (2) 竞赛从开始到结束，平均转移的次数为多少？ (3) 甲获得1、2、3分的平均次数是多少？,设甲取胜一题的概率为p (0p1)，p与两队的实力有关甲队得分有5种可能，即0，1，2，3，4 我们分别记为状态S0，S1，S2，S3，S4，其中S0和S4是吸收状态，S1，S2和S3是非吸收状态过程以S2作为初始状态根据甲队赢得1分的概率为p，建立转移矩阵P：,S 0 S 1 S 2 S 3 S 4,将上式改记为标准形 式T：,其中,计算基矩阵B：,记q=1-p，则,因为S2是初始状态，根据定理C3，甲队获分为1，2，3分的平均次数为,又,根据定理C4，以S2为初始状态，甲队最终获胜的平均转移次数为,又因为,根据定理C5，甲队最后获胜的概率,。,练习（例3.1）：老鼠在迷宫里找奶酪问题,老鼠在遇到猫之前找到奶酪的概率,
