《随机过程_课件---第五章.doc》由会员分享，可在线阅读，更多相关《随机过程_课件---第五章.doc（27页珍藏版）》请在金锄头文库上搜索。
1、第五章 离散参数Markov链5.1 Markov链的基本概念1、Markov链和转移概率矩阵定义5-1考虑只取有限个或可数个值的随机过程。把过程所取可能值得全体称为它的状态空间，记之为E，通常假设。若就说“过程在时刻n处于状态i”，假设每当过程处于状态i，则在下一个时刻将处于状态j的概率是固定的，即对任意时刻n若对任意状态有这样的随机过程称为Markov链。称矩阵是一步转移概率矩阵，简称为转移矩阵。由的定义可知，这是一种带有平稳转移概率的Markov链，也称作时间齐次Markov链或简称时齐次Markov链。且具有， , 2、例题例5-1（直线上的随机游动）考虑在直线上整数点上运动的粒子，当
2、它处于位置j时，向右转移到j+1的概率为p，而向左移动到j-1的概率为q=p-1，又设时刻0时粒子处在原点，即。于是粒子在时刻n所处的位置就是一个Markov链，且具有转移概率当时，称为简单对称随机游动。例5-6（排队模型）考虑顾客到服务台排队等候服务，在每个服务周期中只要服务台前有顾客在等待，就要对排队在队前的一位顾客提供服务，若服务台前无顾客时就不实施服务。设在第n个服务周期中到达的顾客数为一随机变量，且序列是独立同分布随机序列，即且设为服务周期n开始时服务台前顾客数，则有此时为一Markov链，其转移概率矩阵为。例5-8（生灭链）观察某种生物群体，以表示在时刻n群体的数目，设为i个数量单
3、位，如在时刻n+1增生到i+1个数量单位的概率为，减灭到i-1个数量单位的概率为，保持不变的概率为，则为齐次马尔可夫链，其转移概率为,称此马尔可夫链为生灭链。3、定理5-1设随机过程满足：（1） 其中，且取值在E上；（2）为独立同分布随机变量，且与也相互独立，则是Markov链，而且其一步转移概率为，对于任意，证：设，由上面(1)、(2)可知，与互相独立，所以有同理即是Markov链，由时间齐次性，其一步转移概率为于是定理5-1得证。4、定理5-2时齐次Markov链完全由其初始状态的概率分布和其转移概率矩阵所确定。证：对于任意，计算有限维联合分布，由概率的乘法公式及马氏性可知定理5-2得证。
4、5、例题例5-9（二项过程）设在每次试验中，事件A发生的概率为，独立地重复进行这项试验，以表示到第n次为止事件A发生的次数，则是一个独立平稳增量过程。实际上，由二项分布知识可知，服从二项分布，故称此为二项过程。若令增量易见是第n次试验中事件A发生的次数，其概率为且即为一个独立平稳增量过程，当然是一齐次Markov过程。5.2 Chapman-Kolmogorov方程1、定理5-3（Chapman-Kolmogorov（切普曼-柯尔莫哥洛夫）方程，C-K方程）对任何整数，有或证：这里只需要证明成立，再依次递推即可证明定理5-3。因为根据矩阵的乘法规则，定理得证。注： 定义m步转移概率表示给定时刻
5、n时，过程处于状态i，间隔m步之后过程在时刻n+m转移到了状态j的条件概率。还约定。以表示第i行、第j列的元素矩阵，称为Markov链的n步转移概率矩阵。2、例题（两状态Markov链）例5-10在重复独立贝努里（Bernoulli）试验中，每次试验有两种状态，设表示第n次试验中出现的结果，且有其中，则显然是独立同分布随机序列，从而它是Markov链。于是经过计算有所以，一步转移概率矩阵为而且有5.3 Markov链的状态分类1、互通定义5-2称自状态i可达状态j，并记，如果存在，使，称状态i与j互通（相同，互达），并记为，如且。2、定理5-4可达关系与互通关系都具有传递性，即如果且，则。证：
6、因为有，所以存在，使由C-K方程这里，所以成立。若将可达关系得证明正向进行，再反向进行，就可得出互通关系的传递性，证毕。3、周期定义5-3设为齐次Markov链，其状态空间为E。对于任意，如果集合非空，则称该集合的最大公约数为状态i的周期，若就称状态i为有周期的，且周期为d；若就称状态i为非周期的。4、定理5-5如果Markov链状态i的周期为d，则存在正整数M，对一切，有。证：设，令则故存在正整数N，使得，因此故存在正整数M，对一切，由初等数论有由于，因而当时定理5-5得证。5、首达时间定义5-4设状态，首达时间定义为表示Markov链从状态i出发，首次到达状态j的时间，称为自i到j的首达时
7、间。表示从i出发，首次回到i的时间。6、首达概率设状态，首达概率定义为而且令表示过程从状态i出发经n步首次到达状态j的概率，称为首达概率。再令它表示过程从状态i出发经有限步到达状态j的概率，即从状态i出发经有限步终于到达状态j的概率。7、常返定义5-6称状态i为常返的，如果；称状态i为非常返的（或称为瞬时的），如果。定义5-7设状态i为常返状态（即），如果，则称常返态i为正常返的；如果，则称常返态i为零常返的。非周期的正常返态称为遍历状态。注：对于常返态i，由定义知，即构成一概率分布，此分布的数学期望为，表示由i出发再返回到i的平均返回时间。8、定理5-6对任意状态及，有证：由转移概率的定义得
8、定理5-6讨论了首达概率与转移概率之间的关系。C-K方程即上式是马氏链的关键性公式，它们可以把分解成较低步转移概率之和的形式。9、定理5-7对任意状态，的充分条件是。证：充分性.如果，则存在，使得，由定理5-6有从而中至少有一个为正，所以必要性如果，由，至少有一个，使得。由定理5-6有即说明成立，证毕。10、定理5-8状态i常返的充分条件为如果状态i为非常返，当且仅当推论5-1 若状态j为非常返的，则对于任意，有推论5-2若状态j为常返态，则（1）当，有（2）当时（即不可达时），有11、定理5-9对任意状态，有12、定理5-10状态i常返当且仅当；如果i非常返，则。13、定理5-11设i常返且
9、有周期d，则其中为i的平均返回时间。当时，。推论5-3设i是常返状态，则i是零常返状态i是遍历状态14、定理5-12如果（即互通），则i与j同为常返或非常返，如果为常返，则它们同为正常返或零常返；i与j有同样的周期。5.4 闭集与状态空间的分解1、闭集定义5-8状态空间E的子集C称为（随机）闭集，如果对任意及都有。若C的状态是互通的，闭集C称为不可约的。马氏链称为不可约的，如果其状态空间不可约。2、相关引理引理5-1C是闭集的充要条件是对任意的，都有引理5-2设马氏链的状态空间为E，已知状态i常返，若，则状态必常返，且。引理5-3Markov链具有如下性质：（1） Markov链所有常返态构成
10、一闭集；（2） 不可约Markov链或者全是常返态，或者全是非常返态。3、定理5-13（分解定理）任一马氏链的状态空间E，可唯一的分解成有限个或可列个互不相交的子集之和，使得（1） 每一是常返态组成的不可约闭集；（2） 中的状态同类，或全是正常返，或全是零常返，它们有相同的周期且；（3） D由全体非常返状态组成，自中的状态不能到达D中的状态。注：分解定理中的集D不一定是闭集，但如果E为有限集，D一定是非闭集。因此，如果最初质点是自某一非常返状态出发，则它可能就一直在D中运动，也可能在某一时刻离开D转移到某一常返闭集中。一旦质点进入后，它将永远在此中运动。4、例题例5-14（平面上（或二维）的对
11、称随机游动）设质点的位置是平面上的整数格点，每个位置有4 个相邻的位置，质点分别以1/4的概率转移到这4个相邻位置中的每一个上。讨论平面上对称随机游动的常返性。解：可以看出，平面上对称随机游动是周期为2的不可约马氏链。可以计算质点经过2n步仍回到原位置的概率。这时质点必须与横坐标平行地向右移动k步，向左也移动k步；与纵坐标平行地向上移动步，向下也移动步，而且，所以因此有于是，平面上的对称随机游动也是常返的。5、随机矩阵定义5-9称矩阵为随机矩阵，如果元素非负且对每个有显然Markov链的一步转移矩阵和n步转移矩阵都为随机矩阵。6、定理5-14引理5-4设为闭集，又是C上所得的（即与C相应的）m
12、步转移子矩阵，则G是随机矩阵。定理5-14考虑周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交的子集之和，即，其中当时，而且使得自中任一状态出发，经一步转移必进入中（其中）7、例题例题5-16设不可约Markov链的状态空间，其转移概率矩阵为试分解此链。解：由于第四行第四列都只有一个非零元素，所以考虑状态4，易知其周期，因此根据定理5-14，有于是有5.5 转移概率的极限状态与平稳分布1、定理5-15定理5-15若j为非常返状态或零常返状态，则对任意，有证：当j为常返状态时，由推论5-1有且当j为零常返状态时，取，有固定m，令，由推论5-3的结论知，故上式右方第一项趋于0；再令，
13、第二项因为收敛而趋于0，于是有即证明了定理5-15成立。推论5-4有限Markov链至少有一个常返态，但有限Markov链没有零常返状态。推论5-5不可约有限Markov链只有正常返状态。推论5-6若Markov链有一零常返状态，则必有无限多个零常返状态。2、定理5-16若j为正常返状态，周期为d，则对任意及，有式中为状态j的平均返回时间。3、遍历链定义5-10若对于一切，极限存在，则称该Markov链具有遍历性。此链又称为遍历链。4、定理5-17定理5-17若j是非周期，正常返状态（即遍历态），则其中为状态j的平均返回时间。推论5-7（1）对于不可约Markov链，若它的状态是非周期、正常返的，则它是遍历链，而且有（2）对于不可约Markov链，若它的状态有限且非周期的，则它是遍历链，而且有。5、平稳分布定义5-11设Markov链有转移概率矩阵，若存在一个概率分布，其满足则称为该Markov链的平稳分布。6、定理5-18定理5-18不可约非周期Markov链是正常返的充要条件是它存在平稳分布，且此时平稳分布就是极限分布。推论5-8（1） 对于不可约非周期Markov链，若所有状态是正常返（即链的遍历的），则该链存在平稳分布，且平稳分布就是极限分布；若所有状态是非常返或所有状态是零常返，则不存在平稳分布。（2） 不可
