随机过程第7讲

《随机过程第7讲》由会员分享，可在线阅读，更多相关《随机过程第7讲（12页珍藏版）》请在装配图网上搜索。

1、7 马尔可夫链内容提要口马尔可夫链的概念及转移概率口马尔可夫链的状态分类口状态空间的分解口 p.(n)的渐近性质与平稳分布ij马尔可夫过程的四种类型马尔可夫链时间、状态都离散马尔可夫序列时间离散、状态连续 连续时间马尔可夫过程时间连续、状态离散 连续马尔可夫过程(或扩散过程)时间、状态都连续7.1 马尔可夫链的概念及转移概率定义设有随机过程 Xn , n gT ，若对于任意的整数n gT和任意的i , i ,i e I,0 1n+1PX = i X = i , X = i，,X = i 条件概率满足n+1n+1 0 011 n n=PX= i |X = i n+1 n+1 n n则称 Xn ,

2、 n gT 为马尔可夫链，简称马氏链。马氏性(无后效性)PX 二 i X 二 i , X 二 i，X 二 i n+1n+10011n n二 P X二 i X 二 i n+1n+1n nPX = i , X = i，X = i 0011n n=P X = i |X = i , X = i，,X = i n n 0011n-1 n-1-PX = i，X = i，X = i 0011n-1n-1=P X = i |X = i - P X = i，X = i，X = i n n n-1 n-10011n-1n-1=PX = i |X = i -PX= i X = i n n n-1 n-1n-1n-1

3、n-2n-2-P X = i |X = i - P X110 0 0马尔可夫链的统计特性完全由以下条件概率所决定：PX = i |X = i n+1 n+1 n n转移概率定义称条件概率p (n) = P X= j X = ijn+1n为马尔可夫链 Xn , n gT 在时刻n的一步转移概率，其中i , j el ,简称 为转移概率。 P (n)不仅与状态i,j有关，而且与时刻n有关。 ij当P (n)与时刻n无关时，表示马尔可夫链具有平稳转移概率，此时称齐次马尔可夫 ij链，我们只研究齐次的，通常将齐次省略。齐次马尔可夫链定义若对任意的i,j el,马尔可夫链 Xn,nwT 的转移概率P 与

4、时刻 n 无关 ij 则称马尔可夫链是齐次的，并记为P (n )为P 。p p p 1112In一步转移概率矩阵p = p21 p”p221222n性质：(1) p 0, i, j e Iij 2 p = 1, i e Iiel随机矩阵)n 步转移概率=PX = jX = i,(i, j e l, m 0, n 1)为马m+nm尔可夫链 Xn , neT 的n步转移概率，并称P()=(J为马尔可夫链的nij定义 称条件概率p (n)ij步转移矩阵。规定：p (0) =r心jij 1, i = jn 步转移概率 p(n) 的性质ij淀理设 Xn , neT 为马尔可夫链，则对于任意整数n0,0l

5、 0)12绝对概率 p (n) 的性质j定理设 Xn,nwT 为马尔可夫链，则对于任意整数n 1和jwl,绝对概率P .(n)具j(1) p (n)=工 p p (n)j i ij(2) p (n)=乙 p (n -1) - P有下列性质： j i ij ie!(3) PT (n) = PT (0) - P(n)(3) Pt (n) = Pt (n -1) - P有限维概率分布 定理设 Xn , neT 是马尔可夫链，则对任意i，,i e 1，有1npx = i，,X = i =Y p p p11 n ni ii i i1n -1 nieI马尔可夫链的有限维分布完全由它的初始概率和一步转移概率

6、所决定。马尔可夫链的几个简单例子例 1 二进制对称信道模型是常用于表征通信系统的错误产 生机制的离散无记忆信道模型。假设某级信道输入0,1 数字信号 后，其输出正确的概率为P，产生错误的概率为q,则该级信道输 入状态和输出状态构成一个两状态的齐次马尔可夫链。步转移概率矩阵：P = q二步转移概率矩阵：P(2) = P 2 =p 2 + q 22pq2pqp 2 + q 2p，i = j p.= j q, . h j(i, . =0,1) 例 2 无限制随机游动设质点在数轴上游动。每次游动一格，向右游动的概率为P，向左游动的概率为q=l-P, 若以 Xn 表示质点在时刻 n 所处的位置，则 Xn

7、 , n e T 是一个齐次马尔可夫链，试写 出它的一步和 k 步转移概率。 例 3 具有吸收壁和反射壁的随机游动设质点在线段1,4上作随机游动。假设它只能在时刻neT发生移动，且只能停留在 1,2,3,4点上。当质点转移到2,3点时，它以1/3的概率向左或向右移动一格，或停留在原 处。当质点移动到点1时，它以概率1停留在原处。当质点移动到点4时，它以概率1移动 到点3。若以Xn表示质点在时刻n所处的位置，贝叽Xn , n e T 是一个齐次马尔可夫 链。例4赌徒输光问题两赌徒甲和乙进行一系列赌博，赌徒甲有a元，赌徒乙有b元，每赌一局输者给赢者1 元，没有和局,直到两人中有一个输光为止。设在每

8、局中，甲赢的概率为P，输的概率为q=1-p， 求甲输光的概率。例5 天气预报问题设昨日、今日都下雨，那么明日有雨的概率为0.7；昨日无雨，今日有雨，那么明日有雨的概率为 0.5；昨日有雨 那么明日有雨的概率为0.2 描述马氏链的三种方式 （1）状态转移图2）（3）例今日无雨，那么明日有雨的概率为0.4；昨日、今日均无雨 若星期一、星期二均下雨，求星期四下雨的概率。1/31/3反射转移概率矩阵11/30001/31/3001/31/311/3反射壁0 _01/30函数表达式ng T 1/402/5设 Xn ,1/22/33/5pij曰f（i,j）个马尔可夫链，其状态空间I = a, b, c，转

9、移矩阵为1/41/30求：(1) P X 二 b, X 二 c, X 二 a, X 二 cX1 2P Xn+23c X bn解： (1)PX b,X c,X23a, X c|X c410二 P X0二 c,X 二 b,X 二 c,X 二 a,X 二 c/PX12340 ccX a - P X a|X c - P X cX b33221c/P X c P X4-P X b|X c - P X1 0 0二 P - P - P - Pac ca bc cb13121X X X 45 3550(2) PX c|X bn+2n=Pbc47-9-5304024-8子十1510617317302090二步转

10、移概率矩阵：P =P 27.2 马尔可夫链的状态分类设Xn,nO是齐次马尔可夫链，其状态空间1=0,1,2,转移概率是P , i,jeI, ij初始分布为P , j gI 。j1）状态的周期性 定义如集合n:n1, p（ n） 0非空，则称该集合的最大公约数d=d（i）=G.C.Dn: p（ “） 0 ii ii为状态 i 的周期。女口 d1就称i为周期的：如d=1就称i为非周期的。定理如果状态i的周期为d ,则存在正整数M,对一切n M，有p（严0。（2）状态的常返性首中概率状态 i 经 n 步首次到达状态 j 的概率：f（n）= PX= j, X丰 j,1 v 1ijm+nm+vmf （0

11、） = 0ij系统从状态 i 出发，经有限步迟早会（首次）到达状态 j 的概率：f上f （n）0 f （n） f 1ijijijijn=1常返性的定义1、若f. =1，则称状态i是常返的：若f. 1，则称状态i是非常返的（或滑过的）。iiii2、 称期望值卩=艺n- f（n）为状态i的平均返回时间。iiin =13、若u 5，则称常返态i是正常返的；i4、若u =s，则称常返态i是零常返的。 i非周期的正常返态称为遍历状态。P（n）与f（n啲关系定理对任意状态i , j g I及1 n 1, p(n) 0 = G.C.D n: n 1, f (n) 0iiii设马尔可夫链的状态空间 I= 1,

12、 2, 3，其转移概率矩阵为例 (例 4.8)_ 0q2p3q3q1p20求从状态1出发经n步转移首次到达各状态的概率。解： f1(2n)(q p )m-iq q ,131 3(q p )mp ,131n 二 2m, m 1n 二 2m +1, m 0f1(3n)f1(1n)(pq )m-1p p ,1 2 1 2(p q )mq ,1 2 1Q= 1n = 2m +1, m 0m-1 p ,12 3213 23p (p q ) m -1p ) m -1q q ,12 32 313 22n = 1n = 2m, m 1n = 2m +1, m 0常返性的判别及其性质定理(1)状态i常返的充要条

13、件为 p(n) = g , iin=0状态i非常返的充要条件为 p(n)=1 - fii2)若状态 i 是常返态，o lim p (n) = 1.卩 0。ii intgiin=0则i是零常返limp(”)二0 oi是遍历状态iintg(3)若i是周期为d的常返态，则limp(n) iintg若i是非常返态，则limp(n)二0。iintg3)可达关系与互通关系定义 (1)若存在 n 0,(2)若 i t j ,且定理1若i t j ,- 右 I o j ,使得P.(n) 0，则称自状态i可达状态j，并记为i t j ； ijj t i ,则称状态i与状态j互通，并记为i o j。 且j t k

14、 ,贝Ii t k ；且j o k ,则 i o k 。定理2若i o j ,贝I(1) i 与 j 同为常返或非常返；( 2) i 与 j 同为正常返或零常返传递性互通关系的状态是同一类型3）i 与 j 有相同的周期。例（例4.9）设马氏链的状态空间I = 0,1, 2,其转移概率为p002 pi+ipi0分析各状态的类型。解：先考查状态 0,fo（oi）=2,f0（02）4, f（n）4002n00n=1可见状态 0 为正常返,且是非周期,因而是遍历的。 因为i ，故i也是遍历的。7.3 状态空间的分解定义状态空间I的子集C,若对于任意i e C及k电C都有p = 0 ,贝I称子集C为ik

15、（随机）闭集。若闭集 C 的状态互通,贝称 C 为不可约的。 若马氏链 Xn 的状态空间是不可约的，则称该马氏链为不可约。闭集的充要条件定理 C 是闭集的充要条件是：对于任意i e C及k电C都有叮）=0, n工】。状态i为吸收态（P =1） o单点集 i 是闭集。ii闭集及不可约性。0.5000.50.500.50P=00101000_ 0100000001/21/21/211/2例（例4.11 ）设马氏链 Xn 的状态空间I = 1, 2, 3, 4, 5 ，转移矩阵为P,试分析其状态 3 为吸收态,故 3 是闭集； 1, 4 , 1, 4, 3 , 1, 4, 2, 3 都是闭集 3 和

16、 1, 4 是不可约闭集；因为I含有闭子集，故马氏链 Xn 不是不可约链。分解1按照常返性和互通性进行定理任一马氏链的状态空间I ,可唯一地分解成有限个或可列个互不相交的子集D, C1, C2, 之和，使得（1）每个 Cn 是常返态组成的不可约闭集；（2）Cn中的状态同类（全为正常返或零常返），它们有相同的周期，且fk = 1 ,j, k eCn ；jk（3）D 由全体非常返态组成。自 Cn 中的状态不能到达 D 中的状态。称Cn是基本常返闭集例（例4.13）设状态空间I = 1, 2,., 6 ，转移矩阵为P,试分解此链并指出各状态的常返性及周期性。11/3O 1/300100000P=00

17、001/31/301/3100001/20000011000000 1/21/2 I = DuC uC12=4u1,3,5u2,6随机矩阵定义若矩阵（a ）的元素非负且对每个i都有工a =1，则称矩阵（a ）为随机矩阵。ijj ijij显然，k步转移矩阵p（k）=C（k）是随机矩阵。ij定理设C是闭集，又G = V（k）丿，i, j e C是C上所得的k步转移子矩阵，则G仍 ij是随机矩阵。分解2对周期的不可约马氏链的分解定理 周期为 d 的不可约马氏链，其状态空间 C 可唯一地分解为 d 个互不相交的子集之和，即 C = t) G , G A G =0 , (r 丰 s)r r sr=0且使

18、得自G中任一状态出发，经一步转移必进入G 中（其中G = G ）。rr+1d0G = j :对某个n 0, p(nd+r) 0 rij1/2001/201/201/3001/301/3P=010000001000010000_ 001/403/401/21/4例（例4.14）设不可约马氏链的状态空间C = 1, 2, 3, 4, 5, 6 ，转移矩阵为P,试对其 状态空间进行分解。(3,5C = G u G u G0 1 2= 1, 4, 6 u 3, 5 u2周期性不可约马氏链的子链 定理 设 Xn , n 0 是周期为 d 的不可约马氏链，（ 1）若只在时刻 0, d, 2d, 上考虑 X

19、n ，即得一新马氏链（子链），其转移矩阵 P（d）=C（），对此新链，每一子状态空间Gr是非周期的不可约闭集；ij2）若原马氏链 Xn 常返，则子链 X 也常返。 nd阵为j/3 001/301/30 1 0 0 0 000 7/12P (3)=1/3 0001/35/12001/300 7/1205/12G = 1,4,60G = 3,51G 二221/3 001/301/31/31/31/3OZZ35/12 317/121/37.4 P ( n )的渐近性质与平稳分布 ij例(例4.15)设 Xn 是例4.14中的马氏链，已知d = 3,则 X , n 0 的转移矩 3nij有 lim p

20、 (nd+r) = f (r)ns ijij 卩jlim p (nd) =nTw jd：卩,当i,j同属于子集Gt 0,其它s对于转移概率P ( n )的极限lim p(n)nTs 1) 是否存在？2) 是否与 i 有关？1)P (n) 的渐近性质i定理若j非常返或零常返，则limp(n)二0, Vi G Ins j推论 1 有限状态的马氏链，不可能全是非常返态，也不可能含有零常返态；不可约的有限 马氏链必为正常返的。推论 2 若马氏链有一个零常返态，则必有无限多个零常返态。fij(r) 的定义ij自状态 i 出发，在时刻 n = r( mod(d ) ) 首次到达 j 的概率记为：f (r)

21、 = S f(md+r), 0 r d 1ijijm=0显然，艺f.(r)=区艺1 f(md+r)=f(m)ijijijr=0m=0 r=0m=0正常返态的渐近性 定理 若 j 正常返，周期为 d ，则对任意 i 及 0 r d1，推论 对于不可约、周期为 d 的正常返马氏链，其状态空间为 C ，则对任意 i ,jG C ， 有常返或到达的平均次数定理 对于任意状态 i , j ，有lim 丄 n t a nk = 1p (k)ij0,当j非常返或零常返 fj卩j,当j正常返推论 若 Xn 不可约常返，则对任意 i ,j（2）平稳分布lim p( k)ijnta nk =1定义称绝对概率分布兀

22、,j G Z 为齐次马氏链的平稳分布，若它满足j令 n = C, P = C )ij则n = Pt - n平稳分布定理 不可约非周期马氏链是正常返的充要条件：存在平稳分布，且此平稳分布就是极限分布卩.,jg I推论 1 有限状态的不可约非周期马氏链必存在平稳分布。推论 2 若不可约马氏链的所有状态是非常返或零常返的，则不存在平稳分布。推论3若兀j ,j g I是不可约非周期马氏链的平稳分布，则limp.（n）=兀. n ta jR j解：因为该马氏链是不可约的非周期有-0.70.10.2-限状态，所以存在平稳分布。P =0.10.80.1k = 0.7k + 0.1k + 0.05k1 1 2k = 0.1k + 0.8k + 0.05k0.050.050.9例（例4.16）设马尔可夫链的转移概率矩阵为P，求马氏链的平稳分布及各状态的平均返 回时间。J 2123兀=0.2k + 0.1兀 + 0.9k3123k + k + k = 1123平稳分布为：k = 0.1765, k = 0.2353, k = 0.5882123各状态的平均返回时间分别为：R = = 5.67, R = - = 4.25, R = - = 1.701 k2 k3 k123