《2012第四章马尔可夫链》由会员分享，可在线阅读，更多相关《2012第四章马尔可夫链（65页珍藏版）》请在金锄头文库上搜索。
1、随机过程第四章：马尔可夫链第四章：马尔可夫链4.1 马尔可夫链定义4.2 一步转移概率及多步转移概率4.3 初始概率及绝对概率4.4 遍历的马尔可夫链及平稳分布4.5 马尔可夫链状态分类4.6 状态空间的分解 时间、状态 都是 离散 的 马尔可夫过程 ，称为 马尔可夫链 。 时间连续、状态离散 的 马尔可夫过程 ，称为连续时间的 马尔可夫链 。 时间、状态 都是 连续 的 马尔可夫过程 ，就是 马尔可夫过程 。例如 ： 天气预报质点的随机游动赌博输光问题生死链4.1 马尔可夫链定义马尔可夫链定义：设有随机过程 Xn,nT ，若对于任意的整数nT和任意的i0,i1, ,in+1I，条件概率满足：
2、|,|11110011nnnnnnnniXiXPiXiXiXiXP=+null则称Xn,nT为 马尔可夫链 ，简称 马氏链。将来的状态只与当前状态有关，与过去状态无关。例如 ： 在某数字通信系统中传递0，1两种信号，且传递需要经过若干级。因为系统中有噪声，各级将造成错误，若某级输入 0，1信号后，其输出不产生错误的概率为p，产生错误的概 率为1-p，则该级的输入输出状态构成了一个两个状态的 马氏链 。为了描述马尔可夫链（n+1）维分布率，最重要的是 条件概率 PXn+1=in+1|Xn=in，它表示在 时刻n取in值的条件下，下一时刻n+1取值为in+1的概率（一步转移概率） 。称条件概率为马
3、尔可夫链 Xn,nT 在时刻n的 一步转移概率 ，其中i, jI，简称 转移概率 。一步转移概率定义：|)(1iXjXPnpnnij=+4.2 一步转移概率及多步转移概率若对任意的 i, jI，马尔可夫链 Xn,nT 的转移概率与 n 无关，则称马尔可夫链是 齐次马尔可夫链 。我们只讨论 齐次马氏链 。并将 记为()ijp nijp齐次马尔可夫链：()ij ijpn p=设P表示一步转移概率所组成的矩阵，则：=nullnullnullnullnullnullnullnullnullnnppppppP2122211211称为系统状态的 一步转移概率矩阵 ，它具有如下性质：1.2.Ijipij ,
4、0IjipIjij=,1满足上述两个性质的矩阵称为随机矩阵。称条件概率为马尔可夫链 Xn,nT 的 n步转移概率 ，并称：1,0,|)(=+nmIjiiXjXPpmnmnij)()()( nijnp=P为马尔可夫链的 n步转移矩阵 。规定：(0)0, 1, ijijpij=() () ()11 12 1() () ()21 22 2nn nmnn nmpp ppp p = nullnullnullnullnullnullnullnullnulln步转移概率定义：例题4-1:设马尔可夫链Xn,nT有状态空间I=0,1，其一步转移概率矩阵为求 和两步转移概率矩阵P(2) 。=11100100ppp
5、pP0|02=+ mmXXP(2)m2 m00 m 2 mmm2 m m2 mmmm2 m1 mmm2m1 m1m1 mmmm1 m1mPX 0, X 0PPX 0|X0PX 0PX0, X0 PX0, ,X0PX 0 PXX0, X1PX 0,X 0PX 0,X0PX 0, X 0,X 0PX 0PX 0, X 10,X 0PX+= = =+=mm1mm1 m2m1m m1mm2 m1 m m1 mPX 0PX 0|X 0,X0PX 0|X0PX1,X 0P0|X 1,X 0PX 1|XX 1,X 00+= =+= =解：(2)00 00 01(2)2 01 01(2) (2)10 11 1
6、0010011 1P PPPP PPPPP P = m 2 m1 m1 mm 2 m1 m1 m(1) (1) (1) (1)00 00 10 0100 00 10 01PX 0|X 0PX 0|X 0PX 0 | X 1PX 1|X 0=P P P P=P P P P+ += = =+nnPP =)(结论：n步转移矩阵设Xn,nT为马尔可夫链，则对任意整数n0，0LP null绝对概率定义：称 为马尔可夫链的 初始概率 ；简记为称 为马尔可夫链的 初始概率向量 。0(0) , ( )jpPXjjI= =),()0(21nullppT=Pjp初始概率定义：例题4-6：设马尔可夫链有k个状态，已
7、知第n-1时刻的绝对概率向量 为：)1(,),1(),1(21 npnpnpk求第n时刻绝对概率向量。(1)TnP设Xn,nT为马尔可夫链，则对任意jI和n1，绝对概率pj(n)具有下列性质：（1）（2）（3）（4）=Iinijijppnp)()(=Iiijijpnpnp )1()()()0()(nTTn PPP =PPP )1()( = nnTT绝对概率性质：000()111() , |() , | (1)jnniIniIniijiIjnnniInn niIiijiIPn PX jPX iX jPX jX iPX iPPPn PX jPX jX iPX j XiPXiPn P=证明：（1）（
8、2）定理4.3设Xn,nT为马尔可夫链，则对任意i1, ,inI和n1，有=IiiiiiinnnnpppiXiXP11,11nullnull证明：11 1 0 11 101110110 11 ,. ( , ,. ), ,. | . | nniIniInn n niIPX i X i P X i X i X iPX iX i X iPX iPX i X i PX i X i= =11110 .nnnnii i iiIiii iiiIPX ip ppp p=例题4-7：设某地区有1600居民，有甲、乙、丙三个工厂的产品在该地区销售，据调查8月份买甲、乙、丙三个工厂产品的户数分别为480，320，8
9、00，9月份调查发现原买48户转买乙，96户转买丙；原买乙的有32户转买甲，有64户转买丙；原来买丙的有64户转买甲，有32户转买乙， 估算9月份及12月份，甲、乙、丙三个工厂的产品在该地区市场占用率 。4.4 遍历的马尔可夫链及平稳分布遍历性定义：例题4-8：遍历问题平稳分布定义：例题4-9：平稳分布解: （1）pij 0，所以是遍历的。 极限分布平稳分布01 011/2 1/2(,)(,)2/5 3/5 =001010110112254/9135/9251=+=+=+=解: （2）pij 0，所以是遍历的。 极限分布平稳分布012 0120120.5 0.4 0.1( , , ) ( ,
10、, ) 0.3 0.4 0.30.2 0.3 0.51 =+=01221 23 18,62 62 62=周期、非周期常返、非常返其中，常返分为 正常返、零常返；非周期的正常返称为 遍历状态。到达和互通4.5 马尔可夫链状态分类设马尔可夫链的状态空间 I=1,2,3,4,5,6,7,8,9，状态转移图 如下图：观察状态1如集合 n: n1,pii(n)0 非空，则称该集合的最大公约数 d=d(i)=G.C.Dn:pii(n)0 为状态 i 的周期。如 d1就称 i 为 周期的 ，如d=1就称 i 为 非周期的 。由定义知,当n不能被d整除时,pii(n)=0。引理4.1如 i 的周期为d，则存在
11、正整数M，对一切nM，有pii(nd) 0。周期、非周期定义：例题4-10 :设有4个状态的马尔可夫链,它的一步转移概率矩阵为:画出其状态传递图，该过程是否具有周期性?001/21/2001/21/21/2 1/2 0 01/2 1/2 0 0001/21/2001/21/21/2 1/2 0 01/2 1/2 0 0所有状态周期为2。解:如果有下面四个状态转移图：状态2和3具有相同的周期，但是状态2,3有区别。为此引入 常返性 的概念。首中概率定义：它表示质点由状态 i 出发，经 n 步首次到达状态 j 的概率，表示为：)|,11,()(iXjXnvjXPfmnmvmnij=+同时我们令表示
12、质点由状态 i 出发，经有限步终于到达状态 j 的概率。=1)(nnijijff称状态i为 常返的 ，如 fii= 1；称状态i为 非常返的 ，如 fii0，即由状态 i 出发， 经过n次转移以正的概率达到状态 j，则称自状态 i 可 到达状态 j，并记为 。反之如果状态 i 不能到达 j，记为例如： 无限制的随机游动中，每个状态都能够到达任何其它状态。当带有吸收壁的随机游动中，吸收状态却不能到达其他状态。iji j到达定义：有两个状态 i 和 j，如果由状态 i 可以到达状态 j，且由状态 j 也可以到达状态 i，则称状态 i，j 互通 。记为：定理: 如果由状态 i 可以到达 j 状态,由
13、 j 状态可以到达 k状态,则由 I 状态可以到达 k 状态。证明省略。ij互通定义：状态 i 特性（常返和非常返）的判断准则：定理4.5：状态 i 常返的充要条件为：()0niinp=状态 i 非常返的充要条件为：()011niiniipf= 其中，周期为d时候：()nlimniiidpu=非周期时,（遍历）：()n1limniiipu=零常返和正常返的判断准则：定理4.9：如果状态 i，j 互通，则：（1）i 和 j 同为常返或非常返。如为常返，同为正常返或零常返。（2） i 和 j 有相同的周期。判断各状态的性质（从常返和周期性两方面）。例题4-11 :解：4.6 状态空间的分解CiCk
14、状态空间 i 的子集C称为 闭集 ，如果对任意及都有 。0=ikp闭集C称为 不可约 的，如果C中所有状态互通。马尔可夫链称为不可约 的，如果其状态空间不可约的闭集。闭集定义：不可约定义：不可约马氏链定义：如果单个状态构成一个闭集，则称这个闭集为 吸收态 。它是比较小的闭集。（1）闭集意味着质点一旦进入闭集中，将永远留在该闭集中。（2）一个大的闭集可以包含几个小的闭集。问 ：找出该马氏链中所有闭集，马氏链是否不可约？设马氏链Xn的状态空间 i = 1,2,3,4,5，转移矩阵为:1/2 0 0 1/2 01/201/200001 00100 00010 00例题4-12：任一马尔可夫链的状态空间 I ，可唯一的分解成有限个或可列个互不相交的子集D,C1,C2, 之和，使得： 每一Cnn=1,2,3是常返态组成的
