马尔可夫链及其概率分布课件.ppt

1、 马尔可夫链及其概率分布 引言引言 直观上，过程（或系统）在时刻t0所处的状态为已知的条件下,过程在时刻tt0所处状态的条件分布与过程在时刻t0之前所处的状态无关。 用分布函数表达此性质，设随机过程X(t),tT，状态空间为，若对于t 的任意n个值t1t2tn,n3,有 则称过程X(t),tT具有马尔可夫性，或称 X(t),tT为马尔可夫过程。 112211)(,)(,)()( nnnnxtXxtXxtXxtXP RxxtXxtXPnnnnn ,)(|)(11数数。的的条条件件分分布布函函下下布布函函数数等等于于在在条条件件的的条条件件分分条条件件下下，即即在在)()()(1, 2 , 1,)

2、(11nnnniitXxtXtXnixtX );|,(),;,|,(11|121121|1121 nnnnttnnnntttttxtxFtttxxxtxFnnnn或或一、马尔可夫链及其概率分布的定义 状态和时间参数都是离散的马尔可夫过程称为马尔可夫链，或马氏链。 记为Xn=X(n),n=0,1，2，,记链的状态空间为a1，a2，aiR .在链的情况，马尔可夫性通常用分布率表示。 1.1.马氏链的定义马氏链的定义 imjmnimitititjmnaXaXPaXaXaXaXaXPrr |,2211其中a., 称Xn,n=0,1，2，为马氏链。称为马氏链在时刻m系统处于状态ai的条件下，在时刻m+n

3、转移到状态aj的转移概率。 imjmnijaXaXPnmmP |),(定义定义1 1若对于任意的正整数n，r和任意的 有有, 2 , 1 , 0,021nTnmmtmtttir 则称Xn,n0为马氏链。 nnnninininiiinaXaXPaXaXaXaXP |,12011101有有 定义定义2 2设Xn,n0,其状态空间为,若对于任意的正整数n和任意的 110,nniiiiaaaa,例.记从数1,2, ,N中任取一数为X0 0，当n1时，记从数1,2, ,Xn n-1-1中任取一数为Xn n,证明Xn n,n=0，1，2,是一个马氏链。证：Xn n,n=0，1，2,的状态空间=i,1iN,

4、 ,110 xiiiinnn 及及对对任任意意的的 nnnnnnnnnnnnniXiXPiiiiiiXiXiXiXP |10,1111110011可见,Xn n,n=0，1，2,是一个马氏链。 2 2转移概率的性质转移概率的性质 (1)(1) Pij0； , 2 , 1, 1),()2(1 inmmPjij 事实上，因为链在m时刻从状态ai出发，到m+n时刻必然转移到a1，a2，状态中的一个，从而 11|),(jimjnmjijaXaXPnmmP . 1| imjnmjaXaXP2. .定义定义若对任意的正整数m,n及任意的ai，aj，有 1,1, mmPnnPijij即马氏链Xn,n0的转移

5、概率Pij(n,n+1)与n无关，则称转移概率具有平稳性，这时，马尔可夫链称为是齐次的。 imjmijijaXaXPpp |11称为马氏链的一步转移概率；齐次马尔可夫链及一步转移概率齐次马尔可夫链及一步转移概率 )1()1(ijpPP ijiiijjjpppapppapppaaaaP2122221211211121)1( 称为马氏链的一步转移概率矩阵；其中列为Xm的状态，行为Xm+1的状态。例（01传输系统）在一个n级数字传输系统中，设每一级的传真率为p，误码率为q=1-p，并设一个单位时间传输一级，X0是第一级的输入, Xn是第n级的输出（n1）,那么Xn n, n=0，1，2,是一随机过程

6、，状态空间=0,1.0 0 1 1p1-p X0 X1 Xn-1 Xn0 0 1 1p1-p0 0 1 1p1-p 当Xn=i, i为已知时，Xn n+1+1所处的状态的概率分布只与Xn n=i 有关，而与时刻n以前所处的状态无关，所以它是一个马氏链。 定义定义3 3 称条件概率 为马尔可夫链在时刻m处于状态ai的条件下，在时刻m+n步转移到状态aj的n步转移概率，简称为转移概率。 imjnmijaXaXPnmmP |),(且一步转移概率和一步转移概率矩阵分别为 pqqpPjiijqijpiXjXPpnnij1 , 0,|1,且是齐次马氏链.例例(一维随机游动)设一醉汉Q（或看作一随机游动的质

7、点），在如图所示直线的点集I1，2，3，4，5上作游动，仅仅在1秒、2秒等时刻发生游动。游动的概率规则是：如果Q现在位于点i (1i 5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在位于1（或5）这点上，则下一时刻就以概率1移动到2（或4）点上。1和5这两点称为反射壁。上面这种游动称为带有两个反射壁的随机游动。 1 2 3 4 5 若以Xn n表示时刻n时Q的位置，不同的位置就是Xn n的不同状态，那么Xn n,n=0，1,2,是一随机过程，状态空间就是I，而且当Xn n=i,iI为已知时,Xn n+1+1所处的状态的概率分布只与Xn n=i有关，而与Q

8、在时刻n以前如何到达i是完全无关的，所以Xn n,n=0，1,2, 是一马氏链，且是齐次的。它的一步转移概率和一步转移概率矩阵分别为 2|04, 52, 11, 51 , 1, 131|1ijjijiiiijiXjXPpnnij或或 如果把1这一点改为吸收壁，即Q一旦到达1，就永远留在点1上。此时，相应链的转移概率矩阵只须把P中第1横行改为（1，0，0，0，0）。总之，改变游动的概率规则，就可得到不同方式的游动和相应的马氏链。 010003/13/13/10003/13/13/10003/13/13/1000105432154321P例 设Xn,n=0，1，2,是独立同分布的随机变量列,记Xn

9、可能取值的全体为I=i,i 1,则Xn为马氏链，并求其一步转移概率。解 对任意的n及 Iiiiinn 110, 110011,| nnnnnniXPiXiXiXP所以Xn为马氏链。 IiqiXPin ,记记由于Xn, n=0，1，2,独立同分布，因而 nnnniXiXP |11 |111iXjXPqjXPiXjXPmmjnnn 所以Xn为齐次马氏链。其一步转移概率P: .,Ijiqpjij /例3 排队模型设服务系统由一个服务员和只可以容纳两个人的等候室组成，见图73。服务规则是：先到先服务，后来者需在等候室依次排队。假定一个需要服务的顾客到达系统时发现系统内已有3个顾客（一个正在接受服务，两

10、个在等候室排队）则该顾客即离去。设时间间隔t内将有一个顾客进入系统的概率为q，有一原来被服务的顾客离开系统（即服务完毕）的概率为p。又设当t充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的。再设有无顾客来到与服务是否完毕是相互独立的。现用马氏链来描述这个服务系统。 随机到达者等候室服务台系 统离去者设P表示一步转移概率Pij所组成的矩阵，则 称P为一步转移概率矩阵，它具有如下性质 （1） （2） （2）式中对j求和是对状态空间I的所有可能的状态进行的。此性质说明，一步转移概率矩阵中任一行元素之和为1。 表示时刻 时，系统内的顾客数，即系统的状态。xn, n=0，1，2,是一随

11、机过程，状态空间I0，1，2，3，而且仿照例1、例2的分析，可知它是一个齐次马氏链。下面来计算此马氏链的一步转移概率。 p00在系统内没有顾客的条件下，以 后仍没有顾客的概率（此处是条件概率，以下同），p00=1-q. p01系统内没有顾客的条件下, 经 后有一顾客进入系统的概率, p01=q.)(tnXXn p10系统内恰有一顾客正在接受服务的条件下，经 后系统内无人的概率，它等于在 间隔内顾客因服务完毕而离去，且无人进入系统的概率，p10=p(1-q).p11系统内恰有一顾客的条件下，在 间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的

12、概率，这p11pq(1-p) (1-q). p12正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率，p12=q(1-p). p13正在接受服务的顾客继续要求服务，且在 间隔内有两个顾客进入系统的概率。由假设，后者实际上是不可能发生的，p13=0. 类似地，有p21= p32 = p(1-q), p22 = pq+(1-p) (1-q), p23=q(1-p), pij= 0( | i-j |2 ).p33或者一人将离去且另一人将进入系统，或者无人离开系统的概率，p33= pq+(1-p). 于是该马氏链的一步转移概率矩阵为 )1 ()1 (00)1 ()1)(1 ()1 (00)1

13、()1)(1 ()1 (00)1 (3210ppqqppqqppqqppqqppqqpqqp例4 某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共作97次观察），用1表示正常状态，用0表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111设Xn为第n (n=1,2,97)个时段的计算机状态，可以认为它是一个齐次马氏链，状态空间I=0,1, 96次状态转移的情况是：

14、00，8次，01，18次； 10，18次，11，52次。因此，一步转移概率可用频率近似地表示为 ,26818880|0100 nnXXPp,70185218181|0110 nnXXPp,2618188180|1101 nnXXPp,70525218521|1111 nnXXPp /为了进一步讨论马尔可夫链的统计性质，我们需讨论多步转移概率和有限维分布，为此我们先给出几个概念，n步转移概率，初始概率分布，绝对 概率分布。/ 3. 3.多步转移概率及C-K方程 若Xn为齐次马氏链，则对任意非负整数m，任意正整数n,及 jiaa , 无无关关。与与有有maXaXPimjnm | imjnmaXaX

15、P |证明： imjmnjmnjmaXaXaXaXPn |,1111而而 imjmnjmnjmimaXPaXaXaXaXPn |,1111 jjjjijimjjjjijimnnpppaXPpppaXP12111211 ， 12111,11|,nnjjjimjmnjmnjmaXaXaXaXP因此，马氏链的齐次性可写为 imjnmimjnmaXaXPaXaXP 2211|定义定义 称条件概率 1, 0,|)( nmxaaaXaXPnPjiimjnmij 为马氏链Xn,n0的n步转移概率，并称由Pij(n)组成的矩阵 无无关关。与与所所以以maXaXPimjnm | )()()()()()()()(

16、)()()(212222111211npnpnpnpnpnpnpnpnpnpnPijiijjij为马尔可夫链的n步转移概率矩阵。. 1)(, 0)( xaijijjnpnp其中其中 定义 设Xn,n=0,1,为马尔可夫链，称X0 0的分布 pj j(0)=PX0=j, j为Xn,n=0,1,的初始分布. 称Xn的分布pj(n)=PXn=j, j 为Xn,n=0,1,的绝对分布，初始分布和任一时刻 n的绝对分布可用向量表示 q(0)=(p1(0),p2(0), ) q(n)=(p1(n),p2(n), )定理定理 设Xn，n=0,1,为马氏链，则对于任意的正整数k,m，有 rrjirijkPmP

17、kmP)()()(此方程称为Chapman-kolmogorov(切普曼柯尔莫哥洛夫)方程,简称C-K方程.证： injkmnijaXaXPkmP |)( rinjkmnrmnaXaXaXP|, 既:“从Xn=ai出发，经时刻m转移到中间状态ar,再从ar经k时段转移到aj状态”这样一些事件的和事件。 rinjkmnrmninaXPaXaXaXP, rinrjirinaXPkpmpaXP)()( rrjirkpmp)()( 如果把转移概率写成矩阵的形式，那么CK方程具有以下简单的形式 P P(m+k)=P P(m)P P(k) m, k0 特别地，P P(n)=P Pn, n步转移概率由一步转

18、移概率完全决定。例 求带有两个反射壁的一维随机游动的两步转移概率矩阵。 010003/13/13/10003/13/13/10003/13/13/100010010003/13/13/10003/13/13/10003/13/13/100010)2(2PP解：解：例 在n级0-1传输系统中，设p=0.9，求系统二级传输后的传真率与三级传输后的误码率.解 先求出n步转移概率矩阵P P(n)=P Pn。 3/13/13/1009/19/59/29/109/19/29/39/29/109/19/29/59/1003/13/13/1 pqqpP有相异特征值1=1，2=p-q ,由线性代数知识，可将矩阵

19、P表示为对角阵 qp0010021 的相似矩阵。 具体做法是：求出 1 ,2对应的特征向量 2/12/1,2/12/111ee 2/12/12/12/1,21eeH令令则PHH-1。于是，容易算得 nnnnnnqpqpqpqpHHP)(2121)(2121)(2121)(212110101 由上式可知，当p=0.9时，系统经二级传输后的传真率 与三级传输后的误码率分别为 820. 0)1 . 09 . 0(2121)2()2(20011 PP244. 0)1 . 09 . 0(2121)3()3(30110 PP 对于只有两个状态的马氏链，一步转移概率矩阵一 般可表示为： 1,0 ,11 ba

20、bbaaP利用类似的方法，可得n步转移概率矩阵为 bbaababaababbanpnpnpnpPnPnn)1(1)()()()(101011100100 n=1,2,. 四、有限维分布及遍历性 1有限维分布 设马氏链Xn,n0,状态空间，n步转移概率矩阵P(n). (1)一维分布 , 2 , 1,)( jaaXPnpjjnj 设链的，显显然然 11)(jjnp,|010iiijnjnaXPaXaXPaXP 由由全全概概公公式式, 2 , 1,)()0()(1 jnppnpiijij或或 一维分布可用行向量表示p p(n)=(p1(n),p2(n),pj(n),), 利用矩阵的乘法：p(n)=

21、p(0)P(n) 说明马氏链在任一时刻n的一维分布由初始分布与n步 转移概率矩阵确定。 (2)n维分布 对任意n个时刻 0t1t21时就可得到n步转移概率的近似值：jijnp )(1.1.定义定义 设马尔可夫链的状态空间为，如果对于所有的ai , aj, 转移概率pij(n) ,当n时，存在不依赖于i的极限 jijnnp )(lim jjjnnPnP 212121)(或或 则称此链具有遍历性，又若 ,称 =(1,2,)为链的极限分布。 1 jj 2.2.遍历性的定理遍历性的定理 定理定理 设齐次马氏链Xn,n0的状态空间为a1, a2,an，P是它的一步转移概率矩阵，如果存在正整数m，使对任意

22、的ai ,aj，都有 Pij(m)0, i , j =1,2,N 则此链具有遍历性，且有极限分布 =(1,2, N)，它是方程组 NjpPNiijij,.,2 , 11 或或的满足条件 j0, 的唯一解。11 Njj 在定理的条件下，马氏链的极限分布又是平稳分布，意即若用作为链的初始分布，即p(0)=，则链在任一时刻n的分布p(n)永远与一致.因为 PPPnPpnpnn1)()0()(例1: 试说明例2中，带有两个反射壁的随机游动是遍历的，并求其极限分布。 解: 为简便，以符号“”代表转移概率矩阵的正元素。于是，由例2中的一步转移概率矩阵P，得 000000000000000000000000

23、00000000)2(2PP 000000000000)4(4PP 即P(4)无零元。由定理，链是遍历的。再根据定理，极限分布 满足的方程组 13/13/13/13/13/13/13/13/13/1543214554344323321221 先由前四个方程，解得 31=2=3=4=35.将它们代入归一条件，即最后一个方程，解之得唯一解： 1=5=1/11, 2=3=4=3/11 所以极限分布为 =(1/11, 3/11, 3/11, 3/11, 1/11). 例2 设一马氏链的一步转移概率矩阵为 02/102/12/102/1002/102/12/102/10P试讨论它的遍历性。 解: 先算得 2/102/1002/102/12/102/1002/102/1)2(2PPPPP 3)3( 进一步可验证：当n为奇数时，P(n)=P(1)=P； n为偶数时，P(n)P(2)。 这表明对任一固定的 j(=1,2,3,4)，极限 都不存在。按定义，此链不具遍历性。 )(limnpijn