随机过程Ch4马尔可夫链.ppt

第四章 马尔可夫链 1 4.1 马尔可夫链与转移概率 定义 设 x(t)，t t 为随机过程，若对任意 正整数n及t10，且条件分布 px(tn)xn|x(t1)=x1, x(tn-1)=xn-1 = px(tn) xn|x(tn-1)=xn-1， 则称x(t)，t t 为马尔可夫过程。 若t1,t2,tn-2表示过去，tn-1表示现在，tn表示 将来，马尔可夫过程表明：在已知现在状态 的条件下，将来所处的状态与过去状态无关 。 2 4.1 马尔可夫链与转移概率 常见马尔可夫过程通常有三类： (1)时间、状态都是离散的，称为马尔可夫链 (2)时间连续、状态离散的，称为连续时间马尔 可夫链 (3)时间、状态都是连续的，称为马尔可夫过程 （时间离散、状态连续的马尔可夫过程，通常 用泛函中二元函数的范数进行研究） 3 随机过程xn，nt ， 参数t=0, 1, 2, ,状态空间i=i0, i1, i2, 定义 若随机过程xn，nt ，对任意nt和 i0,i1,in+1 i，条件概率 pxn+1=in+1|x0=i0,x1=i1,xn=in = pxn+1=in+1|xn=in， 则称xn，nt 为马尔可夫链，简称马氏链 。 4.1 马尔可夫链与转移概率 4 4.1 马尔可夫链与转移概率 马尔可夫链的性质 px0=i0, x1=i1, , xn=in =pxn=in|x0=i0, x1=i1, , xn-1=in-1 px0=i0, x1=i1, , xn-1=in-1 = pxn=in|xn-1=in-1 pxn-1=in-1 |x0=i0,x1=i1,xn-2=in-2 px0=i0,x1=i1,xn-2=in-2 =pxn=in|xn-1=in-1pxn-1=in-1 |xn-2=in-2 px0=i0,x1=i1,xn-2=in-2 5 4.1 马尔可夫链与转移概率 = =pxn=in|xn-1=in-1pxn-1=in-1 |xn-2=in-2 px1=i1|x0=i0px0=i0 马尔可夫链的统计特性完全由条件概率 pxn+1=in+1|xn=in确定。 6 4.1 马尔可夫链与转移概率 定义 称条件概率pij(n)= pxn+1=j|xn=i 为 马尔可夫链xn，nt 在时刻n的一步转移 概率，简称转移概率，其中i,ji。 定义 若对任意的i,ji，马尔可夫链 xn,nt 的转移概率pij(n)与n无关，则称 马尔可夫链是齐次的，并记pij(n)为pij。 齐次马尔可夫链具有平稳转移概率， 状态空间i=1, 2, 3, ，一步转移概率为 7 4.1 马尔可夫链与转移概率 转移概率性质 (1) (2) p称为随机矩阵 8 4.1 马尔可夫链与转移概率 例例4.14.1 赌博问题。甲乙二人进行一系列赌 博，甲有a元，乙的赌本无限，每赌一 局输者给赢者1元，没有和局，如果甲 输光，再输则赌本为负。设在每一局中 ，甲赢的概率为p，输的概率为q=1-p。 设xn表示第n次赌博结束后甲的赌本， 则xn，n1是马尔科夫链，求xn的转移矩 阵 9 4.1 马尔可夫链与转移概率 例例4. 4.1 1 无限制随机游动 q p -1 0 1 i-1 i i+1 一步转移概率: 10 4.1 马尔可夫链与转移概率 n步转移概率: i经过k步进入j,向右移了x步,向左移了y步 则 11 4.1 马尔可夫链与转移概率 例例4.44.4 具有吸收壁和反射壁的随机游动 状态空间1,2,3,4，1为吸收壁，4为反射壁 状态转移图 状态转移矩阵 12 4.1 马尔可夫链与转移概率 定义 称条件概率 = pxm+n=j|xm=i 为马尔可夫链xn，nt 的n步转移概 率(i,ji, m0, n1)。 n步转移矩阵 其中 p(n)也为随机矩阵 13 4.1 马尔可夫链与转移概率 定理4.1 设xn，nt 为马尔可夫链， 则对任意整数n0,0l0 (最大公约数greatest common divisor) 如果d1，就称i为周期的， 如果d=1，就称i为非周期的 32 4.2 马尔可夫链的状态分类 例例4.64.6 设马尔可夫链的状态空间 i=1,2,9，转移概率如下图 从状态1出发再返回状态1的可能步数为 t=4,6,8,10, ，t的最大公约数为2，从 而状态1的周期为2 33 4.2 马尔可夫链的状态分类 注(1)如果i有周期d，则对一切非零的n, n0 mod d，有 （若 ，则n=0 mod d ） (2)对充分大的n， （引理4.1） 例题中当n=1时， 当n1时， 34 4.2 马尔可夫链的状态分类 例例4.74.7 状态空间i=1,2,3,4，转移概率如图 ， 状态2和状态3有相同的周期d=2，但状态2 和状态3有显著的区别。当状态2转移到状 态3后，再不能返回到状态2，状态3总能 返回到状态3。这就要引入常返性概念。 35 4.2 马尔可夫链的状态分类 由i出发经n步首次到达j的概率(首达概率) 规定 由i出发经有限步终于到达j的概率 36 4.2 马尔可夫链的状态分类 若fii=1，称状态i为常返的； 若fii0,使 状态i与状态j互通，ij：ij且ji 定理4.8 可达关系与互通关系都具有传 递性，即 (1)若ij ，jk，则ik (2)若i j ，j k，则i k 4.3 状态空间的分解 59 4.2 马尔可夫链的状态分类 证 (1)ij ，存在l 0，使 jk，存在m 0，使 由c-k方程 所以ik (2)由(1)直接推出 60 4.2 马尔可夫链的状态分类 定理4.9 如ij，则 (1) i与j同为常返或非常返，如为常返，则 它们同为正常返或零常返 (2) i与j有相同的周期 61 4.2 马尔可夫链的状态分类 例例4.94.9 设马氏链xn的状态空间为 i=0,1,2,，转移概率为 考察状态0的类型 62 4.2 马尔可夫链的状态分类 可得出0为正常返的 由于 ，所以0的周期为d=1 0为非周期的，从而为遍历状态 对于其它状态i,由于i0,所以也是遍历的 63 4.3 状态空间的分解 定义 状态空间i 的子集c称为闭集，如 对任意ic及kc都有pik=0; 闭集c称为不可约的，如c的状态互通； 马氏链xn称为不可约的，如其状态空 间不可约 引理4.4 c是闭集的充要条件为对ic 及kc都有 64 4.3 状态空间的分解 证 充分性显然成立 必要性（数学归纳法） 设c为闭集，由定义当n=1时结论成立 设n=m时， ，ic及kc ，则 注：如pii=1，称状态i为吸收的，等价于 单点集i为闭集。 65 4.3 状态空间的分解 例例4.114.11 设马氏链xn的状态空间为 i=1, 2, 3, 4, 5，转移概率矩阵为 状态3是吸收的，故3是闭集，1,4， 1,3,4，1,2,3,4都是闭集，其中3， 1,4是不可约的。i含有闭子集，故xn 不是不可约的链。 66 4.3 状态空间的分解 例例4.124.12 无限制随机游动为不可约马氏 链，各状态的周期为2，当p=q=1/2时， 是零常返的，当pq时，是非常返的。 67 4.3 状态空间的分解 定理4.10 任一马氏链的状态空间i，可 唯一地分解成有限个或可列个互不相交 的子集d,c1,c2,之和，使得： (1)每一cn是常返态组成的不可约闭集； (2)cn中的状态同类型，或全是正常返，或 全是零常返，它们有相同的周期，且 fij=1，i,jcn； (3)d由全体非常返态组成，自cn中状态不 能到达d中的状态。 68 4.3 状态空间的分解 例例4.134.13 马氏链的状态空间i =1,2,3,4,5,6, 状态转移矩阵为 分解此链并指出各状态的常返性及周期性 。 69 4.3 状态空间的分解 解 由状态转移图知 可见1为正常返状态且周期为3，含1的基 本常返闭集为 c1=k:1k=1,3,5，从 而状态3及5也为正常返状态且周期为3 。 同理可知6为正常返状态，6=3/2，周期为 1。含6的基本常返闭集为 c2=k:6k =2,6，可见2，6为遍历状态。 70 4.3 状态空间的分解 于是i可分解为 i=dc1c2 =41,3,52,6 定义4.10 称矩阵a=(aij)为随机矩阵，若 显然k步转移矩阵 为随机矩阵 。 71 4.3 状态空间的分解 引理4.5 设c为闭集， g是c上所得的k步转移子矩阵，则g仍是 随机矩阵。 证 任取ic，由引理4.4有 从而 且 ，故 是随机矩阵 。 72 4.3 状态空间的分解 注：对i的一个闭子集，可考虑c上的原 马氏链的子马氏链，其状态空间为c， 转移矩阵为g=(pij)，i,jc是原马氏链的 转移矩阵为p=(pij)，i,ji的子矩阵。 73 4.3 状态空间的分解 定理4.11 周期为d的不可约马氏链，其 状态空间c可唯一地分解为d个互不相交 的子集之和，即 且使得自gr中任一状态出发，经一步转 移必进入gr+1中(gd = g0)。 注：任取一状态i，对每一r=0,1,d-1定 义集 74 123 1 1 例：已知马氏链转移图如下，求从状态1出 发再返回1的n步转移概率，n=1,2,8 75 4.3 状态空间的分解 例例4.144.14 设不可约马氏链的状态空间为 c=1, 2, 3, 4, 5, 6，转移矩阵为 76 4.3 状态空间的分解 77 4.3 状态空间的分解 由状态转移图可知各状态的周期d=3, 固定状态i=1，令 故c=g0g1g2 =1,4,63,52 78 4.3 状态空间的分解 定理4.12 设xn,n0是周期为d的不可 约马氏链，则在定理4.11的结论下有 (1)如只在0,d,2d,上考虑xn，即得一新 马氏链xnd ，其转移矩阵 ， 对此新链，每一gr是不可约闭集，且gr 中的状态是非周期的； (2)如原马氏链xn常返，则新马氏链xnd 也常返。 79 4.3 状态空间的分解 例例4.154.15 设xn为例4.14中的马氏链，已 知d=3，则xnd, n0的转移矩阵为 80 4.3 状态空间的分解 由子链 x3n的状态转移图可知 g0=1,4,6，g1=3,5，g2=2 各形成不可约闭集，周期为1 81 g0=1,4,6g1=3,5g3=2 xnd=3d=3d=3 xnd 非周期, 不 可集 非周期, 不可 集 非周期, 不 可集 82 4.3 状态空间的分解 周期性di常返性fii 正常返i1非周期di=1 遍非常返fii0, pi +ri+qi=1。此马尔可夫链为生灭链，它 是不可约的。记a0=1， 证此马尔可夫链存在平稳分布的充要条 件为 105 4.4 渐近性质与平稳分布 证 设j , ji是平稳分布 106 4.4 渐近性质与平稳分布 107 4.4 渐近性质与平稳分布 例例4.184.18 设马尔可夫链转移概率矩阵为 求每一个不可约闭集的平稳分布。 108 4.4 渐近性质与平稳分布 解 从状态转移图 看出，状态空间可 分解为两个不可约 常返闭集 c1=2,3,4和 c2=5,6,7，一个 非常返集n=1。 在常返集上求平稳 分布。 109 4.4 渐近性质与平稳分布 在c1上，对应的转移概率矩阵为 c1上的平稳分布为0, 0.4, 0.2, 0.4,