《马尔可夫过程.ppt》由会员分享,可在线阅读,更多相关《马尔可夫过程.ppt(83页珍藏版)》请在三一文库上搜索。
1、第5章 马尔可夫过程,马春光, http:/ 哈尔滨工程大学,5 马尔可夫过程,5.1 马尔可夫过程的定义 5.2 马尔可夫链的转移概率与概率分布 5.3 齐次马尔可夫链的分类 5.4 转移概率的稳定性能,5 马尔可夫过程,5.1 马尔可夫过程的定义 5.2 马尔可夫链的转移概率与概率分布 5.3 齐次马尔可夫链的分类 5.4 转移概率的稳定性能,5.1 马尔可夫过程的定义,马尔可夫过程是无后效性的随机过程 马尔可夫性 定义 5.1.1 设X(t), t T是一个随机过程,如果X(t), t T 在 t0 时刻所处的状态为已知时,它在时刻 tt0 所处状态的条件分布与其在 t0 之前所处的状态
2、无关. 通俗地说,就是知道过程“现在”的条件下,其“将来”的条件分布不依赖于“过去”,则称X(t), t T具有马尔可夫(Markov)性。,马尔可夫过程 定义 5.1.2 设X(t), t T的状态空间为S,如果 在条件 X(ti)=xi, xiS, i=1,2,n-1下,X(tn)的条件分布函数恰好等于在条件 X(tn-1)=xn-1下的条件分布函数,即 则称X(t), t T为马尔可夫过程。,5.1 马尔可夫过程的定义,马尔可夫链 定义 5.1.3 参数集和状态空间都是离散的马尔可夫过程称为马尔科夫链 . 为了讨论简单起见,在以后取马尔科夫链的状态空间为有限或可列无限,此时马尔可夫性可表
3、示为,5.1 马尔可夫过程的定义,特别地,取T=0,1,2,的马尔可夫链常记为X(n),n0或Xn, n0,此时马尔可夫性为n1,i0 , i1, inS, P(X(n)=in|X(0)=i0 , X(1)=i1, , X(n-1)=in-1) = P(X(n)=in|X(n-1)=in-1) (5.1.3) 或 P(Xn=in|X0=i0 , X1=i1, Xn-1=in-1) = P(Xn=in|Xn-1=in-1) (5.1.4) 容易证明,对于马尔可夫链X(n),n0, (5.1.2)式等价于(5.1.3)式或(5.1.4)式。,5.1 马尔可夫过程的定义,5 马尔可夫过程,5.1 马
4、尔可夫过程的定义 5.2 马尔可夫链的转移概率与概率分布 5.3 齐次马尔可夫链的分类 5.4 转移概率的稳定性能,5.2 马尔可夫链的转移概率与概率分布,1. 转移概率 定义 5.2.1 设Xn, n0是马尔可夫链,称Xn, n0在 n 时处于状态i 的条件下经过 k 步转移,于n+k 时到达状态 j 的条件概率 n0, k1为Xn, n0 在n 时的k 步转移概率;称以 为第i 行第j 列元素的矩阵 为Xn, n0在n 时的k 步转移概率矩阵. 特别地,当k=1时, Xn, n0在n 时的一步转移概率和一步转移概率矩阵分别简记为 和P(n) .,定义 5.2.2 称可数维的矩阵P=(pij
5、)为随机矩阵,如果 显然,Xn, n0的 k 步转移概率矩阵 是一随机矩阵. 事实上,由于 ,并且 如果我们进一步约定 ,则 为单位矩阵.,5.2 马尔可夫链的转移概率与概率分布,2. Chapman-Kolmogorov方程 定理5.2.1(C-K方程) 或 Xn, n0在n 时处于状态 i 的条件下经过 k+m 步转移于 n+k+m 时到达状态 j,可以先在 n 时从状态 i 出发,经过 k 步于 n+k时到达某种中间状态 l,再在 n+k 时从状态 l 出发经过 m 步转移于 n+k+m 时到达最终状态 j,而中间状态 l 要取遍整个状态空间。,5.2 马尔可夫链的转移概率与概率分布,证
6、明,5.2 马尔可夫链的转移概率与概率分布,在C-K方程矩阵形式中,取m=1,得 一直推下去,有 其分量形式为 在上式中把 k+1换成 k,便可得如下结论 : 定理5.2.2 马尔可夫链的k 步转移概率由一步转移概率所完全确定.,5.2 马尔可夫链的转移概率与概率分布,3. 马尔可夫链的分布 1) 初始分布称 为马尔可夫链Xn, n0的初始分布; 称第i个分量为 的(行)向量 为马尔可夫链Xn, n0 的初始分布向量,即 2) 有限维分布 定理 5.2.3 马尔可夫链 Xn, n0 的有限维分布由其初始分布和一步转移概率所完全确定.,5.2 马尔可夫链的转移概率与概率分布,证明,5.2 马尔可
7、夫链的转移概率与概率分布,3) 绝对分布 称 为马尔可夫链Xn, n0的绝对分布;称第j 个分量为 的(行)向量 为马尔可夫链Xn, n0 的绝对分布向量,即 . 显然,绝对分布与初始分布和n步转移概率有如下关系: 或,5.2 马尔可夫链的转移概率与概率分布,事实上,5.2 马尔可夫链的转移概率与概率分布,4. 齐次马尔可夫链 定义 5.2.3 设Xn, n0是一马尔可夫链,如果其一步转移概率 pij (n) 恒与起始时刻n无关,记为pij ,则称Xn, n0 为齐次(时间齐次或时齐)马尔可夫链.否则,称为非齐次马尔可夫链. 对于齐次马尔可夫链 Xn, n0 ,k 步转移概率 也恒与起始时刻n
8、无关,可记为 . 因此在具体讨论时,总可以假定时间起始为零,即 进而k步转移概率矩阵 和一步转移概率矩阵 P(n) 也恒与起始时刻n无关,分别记为 和P.,5.2 马尔可夫链的转移概率与概率分布,对于马尔可夫链我们有以下定理 定理 5.2.4 (1) (2) (3) Xn, n0的有限维分布由其初始分布和一步转移概率 所完全确定.,5.2 马尔可夫链的转移概率与概率分布,例 5.2.1 (天气预报问题) 如果明天是否有雨仅与今天的天气有关,而与过去的天气无关,并设今天下雨、明天有雨的概率为,今天无雨而明天有雨的概率为;又假定把有雨称为 0 状态天气,把无雨称为1状态天气,Xn 表示时刻n时的状
9、态天气,则Xn, n0是以S=0,1为状态空间的齐次马尔可夫链,其一步转移概率矩阵为,5.2 马尔可夫链的转移概率与概率分布,例5.2.2 (有限制随机游动问题) 设有一质点只能在0,1,2,a中的各点上作随机游动,移动规则如下:移动前若在点i1,2 ,a-1上,则以概率p向右移动一格到i+1处,以概率q 向左移动一格到i-1处,而以概率r 停留在i 处,其中p, q, r0, p+q+r=1 ;移动前若在0处,则以概率p0 向右移动一格到1处,而以概率r0停留在0处,其中p0, r00,p0+r0=1;移动前若在a 处,则以概率qa 向左移动一格到a-1处,而以概率ra停留在a处,其中,qa
10、,ra 0, qa+ra =1.,5.2 马尔可夫链的转移概率与概率分布,设Xn表示质点在n时刻所处的位置,则Xn, n0是以S=0,1,2,a为状态空间的齐次马尔可夫链,其一步转移概率矩阵为,5.2 马尔可夫链的转移概率与概率分布,其中0和a是限制质点游动的两道墙壁,当r0=1, p0 =0时称0 为吸收壁;当r0=0, p0 =1时,称0为完全反射壁;当0r01,0 p01 时,称0为部分吸收壁或部分反射壁. 对于a也有类似的含义.,5.2 马尔可夫链的转移概率与概率分布,例5.2.3 (无限制随机游动问题) 设有一质点只能在,-a,-(a-1),-2,-1,0,1,2,a,中的各点上作随
11、机游动,移动规则如下:移动前若点在i ,-a,-(a-1),-2,-1,0,1,2,a,上,则以概率p向右移动一格到i+1处,以概率q向左移动一格到i-1处,其中p,q0. p+q=1.设Xn 表示质点在n时刻所处的位置,则Xn, n0是以S= ,-a,-(a-1),-2,-1,0,1,2,a,为状态空间的齐次马尔可夫链.,5.2 马尔可夫链的转移概率与概率分布,其一步转移概率矩阵为,5.2 马尔可夫链的转移概率与概率分布,例5.2.4 (赌徒输光问题) 有两个赌徒甲、乙进行一系列赌博. 在每一局中甲获胜的概率为p,乙获胜的概率为q,p+q=1 每一局后,负者要付1元给胜者.如果起始时甲有资本
12、a元,乙有资本b元,a+b=c 元,两人赌博直到甲输光或乙输光为止,求甲输光的概率.,5.2 马尔可夫链的转移概率与概率分布,解 根据题设,这个问题可以看成以S=0,1,2,c为状态空间的随机游动Xn, n0,质点从a点出发到达0状态先于到达c状态的概率就是甲先输光的概率.设0jc,uj 为质点从j出发到达0状态先于到达c状态的概率.由全概率公式有 uj=uj+1p+uj-1q 显然u0=1, uc=0,从而得到了一个具有边界条件的差分方程.设,5.2 马尔可夫链的转移概率与概率分布,则可得到两个相邻差分间的递推关系: dj=rdj-1 于是 当r1时, 于是,5.2 马尔可夫链的转移概率与概
13、率分布,而 所以 故,5.2 马尔可夫链的转移概率与概率分布,当r=1时, u0-uc=1=cd0 而 uj=(c-j) d0 故 根据以上计算结果可知,当r1即pq时,甲先输光的概率为 当r=1即p=q时,甲先输光的概率为bc.,5.2 马尔可夫链的转移概率与概率分布,例5.2.5 (艾伦菲斯特问题) 设一个坛子中装有m个球,它们或是红色的,或是黑色的,从坛中随机地摸出一个球,并换入一个相反颜色的球.设经过n次摸换坛中黑球数为Xn,则Xn, n0是以S=0,1,2,m为状态空间的齐次马尔可夫链.,5.2 马尔可夫链的转移概率与概率分布,其一步转移概率矩阵为,5.2 马尔可夫链的转移概率与概率
14、分布,例5.2.6(卜里耶问题) 设坛子中有a只红球,b只黑球,从坛中随机地摸出一个球,然后把该球放回,并加入与摸出的球颜色相同的球c只.设经过n次摸取坛中黑球数为Xn ,则Xn, n0是以S=b,b+c,b+2c,为状态空间的非齐次马尔可夫链.,5.2 马尔可夫链的转移概率与概率分布,其一步转移概率矩阵为,5.2 马尔可夫链的转移概率与概率分布,例 5.2.7 设Xn, n0具有三个状态0,1,2的齐次马尔可夫链,其一步转移概率矩阵为 初始分布 试求: (1) (2),5.2 马尔可夫链的转移概率与概率分布,解 由于 因此 (1) (2),5.2 马尔可夫链的转移概率与概率分布,例 5.2.
15、8 有一多级传输系统只传输数字0和1,设每一级的传真率为p,误码率为q=1-p,且一个单位时间传输一级,X0是第一级的输入, Xn是第n级得输出,则Xn, n1是以S=0,1为状态空间的齐次马尔可夫链,其一步转移概率矩阵为 (1) 设p=0.9,求系统二级传输后的传真率与三级传输后的误码率; (2)设初始分布 ,又已知系统经n级传输后输出为1,求原发数字也是1的概率.,5.2 马尔可夫链的转移概率与概率分布,解 由于 有相异特征值 1=1, 2=p-q ,则P 可表示成对角阵 的相似矩阵.,5.2 马尔可夫链的转移概率与概率分布,又1 ,2 对应的特征向量分别为 令 则,5.2 马尔可夫链的转
16、移概率与概率分布,从而 (1)当p=0.9时,系统经二级传输后的传真率与三级传输后的误码率分别为,5.2 马尔可夫链的转移概率与概率分布,(2)根据贝叶斯公式,当已知系统经n级传输后输出为1,原发数字也是1的概率为,5.2 马尔可夫链的转移概率与概率分布,5 马尔可夫过程,5.1 马尔可夫过程的定义 5.2 马尔可夫链的转移概率与概率分布 5.3 齐次马尔可夫链的分类 5.4 转移概率的稳定性能,5.3 齐次马尔可夫链状态的分类,1 状态的基本属性 定义 5.3.1 设i,jS,称 为系统在0时从状态i 出发经过n 步转移后首次到达状态 j 的概率,简称首达概率. 称 为系统在0时从状态i 出
17、发经过有限步转移后迟早要回到状态j 的概率,简称迟早概率.,称 为系统在0时从状态i 出发永远也不能回到状态j 的概率. 引理 5.3.1 (1) (2) (3),5.3 齐次马尔可夫链状态的分类,定义 5.3.2 设jS,称 为系统首次到达状态 j 的时间,简称首达时.当n|n1, Xn=j= ,即n1, Xnj 时, ,即系统在有限时间内不可能到达状态 j.显然 Tj 是一个随机变量. 引理 5.3.2 (1) (2) (3),5.3 齐次马尔可夫链状态的分类,定义 5.3.3 设iS,若 , ,则称其最大公约数为状态 i 的周期,记为di,即 若 , ,则记其最大公约是为hi ,即 引理
18、 5.3.3 (1) 若 ,则存在 m1,使得 n=mdi (2) 若 ,则存在 ,使得 (3) 若 di 和 hi 中一个存在,则另一个也存在,且 di= hi .,5.3 齐次马尔可夫链状态的分类,定义 5.3.4 设iS (1)若fii=1则称状态i为常返状态,或称状态i为返回状态; 若fii1则称状态i为周期状态,且周期为di,若di=1则称状态i为非周期状态;若状态i是正常返的非周期状态,则称状态i为遍历状态.,5.3 齐次马尔可夫链状态的分类,定义 5.3.5 设i, jS,若n1,使 ,则称状态 i 可达状态 j,记为i j;若i j且j i,则称状态 i 与状态 j 互通,记为
19、i j. 引理 5.3.4 (1) 可达的传递性:若i j, j k则ik . (2) 互通的传递性:若i j, j k 则i k. (3) 互通的对称性:若i j则j k. 引理 5.3.5 设 ,则 引理 5.3.6 设 是常返状态, ,则 , 且,5.3 齐次马尔可夫链状态的分类,引理 5.3.5 设 则 引理 5.3.6 设 是常返状态, ,则 ,且 2. 状体属性的判定 定理 5.3.1 (Doeblin公式) ,有,5.3 齐次马尔可夫链状态的分类,2. 状态属性的判定 定理 5.3.1 (Doeblin公式) ,有 推论 5.3.1 设 ,则 推论 5.3.2 设 ,则 (1)
20、(2),5.3 齐次马尔可夫链状态的分类,定理 5.3.2 是常返状态的充要条件是以下三条件之一成立: (1) (2) (3) 是非常返状态的充要条件是以下三条件之一成立: (1) (2) (3),5.3 齐次马尔可夫链状态的分类,定理 5.3.3 对任意给定的状态 i ,如果i 是常返状态且周期为 di ,则存在极限 . 规定当 时, 定理 5.3.4 设 是常返状态,则 (1) i 是零常返的充要条件是 (2) i 是遍历的充要条件是 (3) i 是正常返周期的充要条件是 不存在,但此时有一收敛于某正数的子列.,5.3 齐次马尔可夫链状态的分类,推论 5.3.3 设 是非常返状态或零常返状
21、态,则 有 定理 5.3.5 设 (1) 若存在正整数n,使得 则i 非周期; (2) 若存在正整数 m,使得m 步转移概率矩阵 中相应于状态 的那列元素全不为零,则 j 非周期. (3) 设状态i 的周期为d,则必存在正整数 ,使得当 时,都有 .,5.3 齐次马尔可夫链状态的分类,定理 5.3.6 互通的两个状态有相同的状态类型. 即设 且 则i 和 j 或者同为非常返状态,或者同为零常返状态,或者同为正常非周期状态,或者同为正常返周期状态且周期相同.,5.3 齐次马尔可夫链状态的分类,3. 状态空间的分解 我们约定若 ,则 ,从而互通满足: (1) 自反性: (2) 对称性:若 则 (3
22、) 传递性:若 则 即,互通是一种等价关系. 利用互通这一等价关系,可将状态空间 进行划分:,5.3 齐次马尔可夫链状态的分类,显然,同一子集 中的所有状态都互通,不同子集中 和 的状态不互通(但单向可达是可以的). 称 为一个等价类,包含 i 的等价类 也常记为 ,于是,5.3 齐次马尔可夫链状态的分类,定义 5.3.6 (1) 闭集:设 C 是S 的子集,如果 和 有 ,则称C 为闭集. 显然状态空间 S 是闭集. (2) 吸收状态:设 如果状态子集 是闭集,则状态 i 称为吸收状态. (3) 不可约闭集:设C 是闭集,如果C中不再含有任何非空真闭子集,则称 C 是不可约闭集. 或称 C
23、是不可约的,或不可分的,或最小的. (4) 不可约的齐次马尔可夫链:如果状态空间S 是不可约的,那么称该齐次马尔可夫链是不可约的,否则称为可约的.,5.3 齐次马尔可夫链状态的分类,引理 5.3.7 (1) 是闭集的充要条件是 (2) 是闭集的充要条件是 (3) 是闭集的充要条件是 (4) 是吸收状态的充要条件是,5.3 齐次马尔可夫链状态的分类,引理5.3.8 等价类 若是闭集,则 是不可约的. 引理5.3.9 设C是闭集,当且仅当C中的任何两个状态都互通时,C 是不可约的. 推论5.3.4 齐次马尔可夫链不可约的充要条件是它的任何两个状态都互通.,5.3 齐次马尔可夫链状态的分类,定理 5
24、.3.7 (1) 有限齐次马尔可夫链的所有非常返状态之集 不可能是闭集. (2) 有限齐次马尔可夫链不可能存在零常返状态. (3) 不可约的有限齐次马尔可夫链的所有状态都是正常返状态. 定理 5.3.8 设 是常返状态,则包含 的等价类S(i) 是闭集,从而是不可约的.,5.3 齐次马尔可夫链状态的分类,定理 5.3.9 齐次马尔可夫链的状态空间 可唯一地分解成有限个或可列无限多个互不相交的状态子集 之并,即 其中 是所有非常返状态构成的状态子集, 是由常返状态构成的不可约闭集,每个状态子集中的状态有着相同的状态类型,且 总有,5.3 齐次马尔可夫链状态的分类,引理 5.3.10 设 是不可约
25、闭集,周期为 如果 则 定理 5.3.10 设 是周期为 的不可约闭集,则 可惟一地分解为 个互不相交的状态子集 之并,即 而且 有 其中,5.3 齐次马尔可夫链状态的分类,定理 5.3.11 设 是周期为 的不可约的齐次马尔可夫链,其状态空间 已被唯一地分解为 个互不相交的状态子集 之并.现仅在时刻 上考虑 即令 则: (1) 是以 为一步转移概率矩阵的新的齐次马尔可夫链; (2)对 而言,每个 都是不可约闭集,而且 中的状态都是非周期的; (3)如果Xn, n=0,1,2,的所有状态皆为常返状态,那么Yn, n=0,1,2,的所有状态也都是常返状态.,5.3 齐次马尔可夫链状态的分类,例
26、5.3.1 设状态空间S=0,1,2的齐次马尔可夫链,它的一步转移概率矩阵为 研究其各个状态间的关系以及状态类型.,5.3 齐次马尔可夫链状态的分类,解 由于 ,其中圈中的数字代表状态,箭头上的数字代表概率。于是可得到如图所示状态转移图.由于 ,由周期的定义可知,状态0是非周期的.由于三个状态互通,故该齐次马尔可夫链是不可约的,且只有三个状态,故三个状态都是正常返状态,从而都是遍历状态.,5.3 齐次马尔可夫链状态的分类,例 5.3.2 设状态空间 的齐次马尔可夫链,其一步转移概率矩阵为 试分析其状态类型.,5.3 齐次马尔可夫链状态的分类,解 状态转移图如图所示.状态3可达状态1,2和4,但
27、这三个状态不能可达状态3,故3是非常返状态集,闭集有两个1,2和4,其中4是吸收状态集.,5.3 齐次马尔可夫链状态的分类,例 5.3.3 设Xn, n=0,1,2,是一齐次马尔可夫链,状态空间S=1,2,3,4,5 ,其中一步转移概率矩阵为 试分析状态类型.,5.3 齐次马尔可夫链状态的分类,解 状态转移图如图所示.状态2,4可达状态1,3,5,但反过来不可达的,于是一旦离开状态集2,4就不可能回到状态2或4,所以2,4为非常返状态集,1,3,5是闭集.,5.3 齐次马尔可夫链状态的分类,例 5.3.4 设齐次马尔可夫链的状态空间S=0,1,2,3,4, 5,6,7,8 其一步转移概率矩阵为
28、 其中*表示一个正数.试分析状态类型.,5.3 齐次马尔可夫链状态的分类,解 由于p00=0,因此0是一个吸收状态,又p600,故6是非常返状态,从而可达状态6的状态7、8也是非常返状态,故D=6,7,8是非常返状态集.状态1只可达2,同时2只可达1,所以1,2是周期为2的正常返状态集,可分解为J1 =1, J2 =2.3,4,5 是状态闭集,由于p440,因此其周期为1.,5.3 齐次马尔可夫链状态的分类,例5.3.5 设状态空间S=0,1,2,3的齐次马尔可夫链,其一步转移概率矩阵为 试对其状态进行分类.,5.3 齐次马尔可夫链状态的分类,解 状态转移图如下图所示.它是一个有限齐次马尔可夫
29、链,所有状态都是互通的,所以所有状态均为常返状态,整个状态空间 S =0,1,2,3 构成一个不可约闭集.,5.3 齐次马尔可夫链状态的分类,例5.3.6 设齐次马尔可夫链的状态空间S=0,1,2,3,4它的一步转移概率矩阵为 试对其状态进行分类.,5.3 齐次马尔可夫链状态的分类,解 (1) 从一步转移概率矩阵可知状态2和3不能和其它状态互通,2,3组成一个闭集.如果过程初始就处于2状态或3状态,则过程永远处于2、3状态,故2,3是常返状态. (2) 状态4可转移到0,1状态,但0,1两个状态不能到达4状态,0,1组成一个闭集,并且0,1是常返状态,4是非常返状态.,5.3 齐次马尔可夫链状
30、态的分类,例5.3.7 设齐次马尔可夫链的状态空间S=0,1,2,3其一步转移概率矩阵为 试分析过程的周期性.,5.3 齐次马尔可夫链状态的分类,解 状态转移图如图所示.四个状态可以分成0,1,2,3两个子集,该过程有确定性的周期转移. 0,12,30,12,3显然它的周期d=2.,5.3 齐次马尔可夫链状态的分类,例 5.3.8 设齐次马尔可夫链的状态空间S=1,2,3,4,5,6,7,8,其一步转移概率矩阵为 试研究过程的周期性.,5.3 齐次马尔可夫链状态的分类,解 状态转移图如图所示.八个状态可以分成四个状态子集J1 =1, J2 =2,3,4, J3 =5,6, J4 =7,8. J
31、1 ,J2 ,J3 ,J4 是互不相交的状态子集,它们的并是整个状态空间,该过程有确定的周期转移J1 J2 J3 J4 J1 显然它的周期d=4.,5.3 齐次马尔可夫链状态的分类,例 5.3.9 设状态空间S=0,1,2,的齐次马尔可夫链,其一步转移概率矩阵为 试研究该链是常返链的充要条件.,5.3 齐次马尔可夫链状态的分类,解 状态转移图如上图所示.由于,5.3 齐次马尔可夫链状态的分类,故 从而 所以f00=1的充要条件是 即0是常返状态的充要条件是 由于链中的所有状态互通,所以所有状态都是常返,故该链是常返链的充要条件是 此条件相当于以下正项级数发散,即,5.3 齐次马尔可夫链状态的分类,反之,如果级数 收敛则该链为非常返链.例如,若 则 时齐次马尔可夫链是常返链. 若 则 级数收敛,此时齐次马尔可夫链是非常返链,而且,5.3 齐次马尔可夫链状态的分类,
链接地址:https://www.31doc.com/p-3227367.html