您好,欢迎访问三七文档
当前位置:首页 > IT计算机/网络 > 数据结构与算法 > 随机过程7-2wqh.
第7章随机过程——马尔可夫链第1页§7.2马尔可夫链一、马尔可夫链的定义四、多步转移概率及C-K方程五、遍历性与平稳分布二、转移概率三、马氏链的几个例子第7章随机过程——马尔可夫链第2页无后效性过程在已知现在状态的条件下,将来所处的状态与过去的状态无关。马尔科夫过程的分类(1)时间离散、状态离散的马尔科夫过程通常称之为马尔科夫链,简称马氏链。(2)时间连续、状态离散的马尔科夫过程。(3)时间连续、状态连续的马尔科夫过程。马尔科夫过程马尔可夫(俄)1856-1922过去现在将来第7章随机过程——马尔可夫链第3页定义7-16设随机过程{(),}XttT,状态空间为I,若对于t的任意n个值12,nttt3,,intT有112211()(),(),,()nnnnPXtxXtxXtxXtx11()|(),,,1,1nnnnniPXtxXtxxRxIin则称过程{(),}XttT具有马尔可夫性,或称{(),}XttT为马尔可夫过程。一、马尔可夫链的定义直观上,可以把122,,nttt看成过去,1nt看成现在,nt看成未来,112211(),(),,()nnXtxXtxXtx,()nnXtx是各个时刻时所处的状态,则马尔可夫过程可以理解为在已经知道过程“现在”的条件下,其“将来”不依赖于“过去”。第7章随机过程——马尔可夫链第4页例7-15设{(),0}Xtt是独立增量过程,且(0)0X,证明:{(),0}Xtt是一马尔可夫过程。证:由定义知,只要证明在已知11()nnXtx的条件下()(),1,2,,2njXtXtjn与相互独立即可由独立增量的定义知,当时,10,1,,2jnntttjn增量()(0)jXtX与1()()nnXtXt相互独立。根据条件11(0)0,()nnXXtx即有与()jXt1()nnXtx相互独立。这表明()(),1,2,,2njXtXtjn与相互独立。即{(),0}Xtt是一个马尔可夫过程。第7章随机过程——马尔可夫链第5页状态和时间参数都是离散的马尔可夫过程称为马尔可夫链,或马氏链。定义7-17设随机序列{,0}nXn的状态空间为I,如果对任意的正整数n和任意的01211,,,,,,nnnaaaaaaI,有:11001111,,,|nnnnnnnnPXaXaXaXaPXaXa则称{,0}nXn为马氏链。泊松过程是时间连续状态离散的马尔可夫过程,维纳过程是时间状态都连续的马尔可夫过程。状态空间:参数空间:012{,,,,,}nIaaaa{0,1,2,,,}Tn第7章随机过程——马尔可夫链第6页例7-16记从数1,2,,N中任取一数为0,X当1n时,记从数11,2,,nX中任取一数为nX,证明{,0,1,2,}nXn是一个马氏链。证可见,{,0,1,2,}nXn的状态空间{,1}IiiN011,,,,,nnaaaaI对任意的n及1100111111,,,0|1nnnnnnnnnnnnnPXaXaXaXaaaPXaXaaaa{,0,1,2,}nXn是一个马氏链。第7章随机过程——马尔可夫链第7页由马氏链定义及概率论知识可知定义7-18设{,0,1,}nXn为马尔可夫链,称0X的分布0{},jjPXaaI为该链的初始分布,称nX的分布{},njjPXaaI为该链的绝对分布。0011001100001111,,,||,,,nnnnnnPXaXaXaPXaPXaXaPXaXaXaXa00110011||nnnnPXaPXaXaPXaXa所以,马氏链的有限维分布完全由初始分布和条件概率确定。如何确定这些条件概率是马尔可夫链理论和应用中的重要问题之一。第7章随机过程——马尔可夫链第8页转移概率的性质0(2)(,1)1,0,1,2,ijjPnni定义7-19称条件概率1|njniPXaXa为马氏链{,0,1,}nXn在时刻n的一步转移概率,简称转移概率,记为(,1)ijPnn。二、转移概率(1),+10;ijPnn()事实上,因为链在n时刻从状态ia出发,到1n时刻必然转移到012,,,aaa状态中的一个,从而100(,1)|ijnjnijjPnnPXaXa101|.njnijPXaXa第7章随机过程——马尔可夫链第9页定义7-20当转移概率(,1)ijPnn只与状态,ijaa有关而与n无关时,则称转移概率具有平稳性,这时,马尔可夫链称为是齐次的或时齐的,并记111ijijijnjnipppnnPXaXa()(,)|否则,就称之为非时齐的。本课程只讨论齐次马氏链第7章随机过程——马尔可夫链第10页(1)(1)ijpPP0100001011011101jjjiiiijaaaapppapppappp称为马氏链的一步转移概率矩阵;其中列为1mX的状态,行为mX的状态。由转移概率性质知,一步转移概率矩阵中任一行元素之和为1。1mX的状态mX的状态定义7-21齐次马氏链的所有一步转移概率ijp表示成矩阵的形式,即第7章随机过程——马尔可夫链第11页12n0X1X2X1nXnX显然,当为已知时,所处的状态的概率分布只与有关,而与时刻以前所处的状态无关。,nXiiI1nXnXin所以它是一个马尔可夫链,而且还是齐次的。三、马氏链的几个例子例7-17(0-1传输系统)在只传输数字0和1的串联系统中,设每一级的传真率(输出与输入数字相同的概率称为系统的传真率,相反情形称为误码率)为,误码率为,并设一个单位时间传输一级,是第一级的输入,是第级的输出。那么,是一随机过程。p1qp0XnX(1)nn{,0,1,}nXn{0,1}I状态空间为第7章随机过程——马尔可夫链第12页它的一步转移概率为1,,{},0,1,,ijnnpjipPXjXiijqji从而它的一步转移概率矩阵为01pqPqp01第7章随机过程——马尔可夫链第13页011,,,,nnaaaaI110011|,,nnnnnnPXaXaXaPXa解:对任意的n及11|nnnnPXaXaIiqiXPin,记所以为马氏链。{}nX由于,0,1,2,nXn独立同分布,因而111|{|}nnnjmmPXjXiPXjqPXjXi所以,,.ijjpqijI{}nX为齐次马氏链。其一步转移概率例7-18设是独立同分布的随机变量列,记可能取值的全体为,则为马氏链,并求其一步转移概率。012nX,n,,,nX{,0,1,}Iii{}nX第7章随机过程——马尔可夫链第14页其一步转移概率矩阵为jjjqqqqqqqqqP101010第7章随机过程——马尔可夫链第15页例7-19(赌徒的破产或称带吸收壁的随机游动)系统的状态是0到5,反映赌博者Q在赌博期间拥有的钱数,当他输光或者拥有钱数为5时,赌博停止(0和5称为吸收壁);否则他将继续赌博,每次以概率p赢得钱数1,以概率1qp输掉钱数1。若以nX表示时刻n时Q拥有的钱数,不同的钱数就是nX的不同状态,那么012{,,,,}nXn是一随机过程,状态空间就是012345I{,,,,,},而且当,nXiiI为已知时,1nX所处的状态的概率分布只与nXi有关,而与Q在时刻n以前如何到达i是完全无关的,所以012{,,,,}nXn是一马氏链,且是齐次的。它的一步转移概率矩阵为第7章随机过程——马尔可夫链第16页0123450100000100002000030000400005000001qpqpPqpqp(带反射壁的随机游动)设例5中当Q输光时将获得赞助钱数1让他继续赌下去,就如同一个在直线上做随机游动的质点在到达左侧0点处就立刻反弹回1一样,这就是一个一侧带有反射壁的随机游动,此时第7章随机过程——马尔可夫链第17页0123450010000100002000030000400005000001qpqpPqpqp同样可以讨论带有一个吸收壁及两个反射壁的随机游动,当然也可以讨论没有吸收壁和反射壁的自由随机游动。总之,改变游动的概率规则,就可得到不同方式的游动和相应的马氏链。第7章随机过程——马尔可夫链第18页随机到达者等候室服务台系统离去者例7-20(排队模型)设服务系统由一个服务员和只可以容纳两个人的等候室组成,见图。服务规则是:先到先服务,后来者需在等候室依次排队。假定一个需要服务的顾客到达系统时发现系统内已有3个顾客(一个正在接受服务,两个在等候室排队)则该顾客即离去。设时间间隔内将有一个顾客进入系统的概率为q,有一原来被服务的顾客离开系统(即服务完毕)的概率为p。又设当充分小时,在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的。再设有无顾客来到与服务是否完毕是相互独立的。现用马氏链来描述这个服务系统。tt第7章随机过程——马尔可夫链第19页随机到达者等候室服务台系统离去者设()nXXnt表示时刻nt时,系统内的顾客数,即系统的状态。{,0,1,2,}nXn是一随机过程,状态空间{0,1,2,3}I,它是一个齐次马氏链。下面来计算此马氏链的一步转移概率。第7章随机过程——马尔可夫链第20页01p――在系统内没有顾客的条件下,经t以后有一个顾客的概率,01pq.10p――系统内恰有一顾客正在接受服务的条件下,经t后系统内无人的概率,它等于在t间隔内顾客因服务完毕而离去,且无人进入系统的概率,10(1)ppq.00p――在系统内没有顾客的条件下,经t以后仍没有顾客的概率001pq.条件概率第7章随机过程——马尔可夫链第21页11p――系统内恰有一顾客的条件下,在t间隔内,他因服务完毕而离去,而另一顾客进入系统,或者正在接受服务的顾客将继续要求服务,且无人进入系统的概率13p――正在接受服务的顾客继续要求服务,且在t间隔内有两个顾客进入系统的概率。由假设,后者实际上是不可能发生的,12p――正在接受服务的顾客继续要求服务,且另一个顾客进入系统的概率,11(1)(1).ppqpq12(1).pqp130.p第7章随机过程——马尔可夫链第22页类似地,有2132(1)pppq22(1)(1)ppqpq23(1)pqp0(||2)ijpij33p――或者一人将离去且另一人将进入系统,或者无人离开系统的概率,33(1).ppqp于是该马氏链的一步转移概率矩阵为0(1)001(1)(1)(1)(1)020(1)(1)(1)(1)300(1)(1)qqpqpqpqqpPpqpqpqqppqpqp第7章随机过程——马尔可夫链第23页定义7-22称条件概率ijmnjmiPnPXaXa()|为马尔可夫链在时刻m处于状态ia的条件下,在时刻mn步转移到状态ja的n步转移概率,简称为转移概率。()(())PijnPn为n步转移概率矩阵。性质:(1)()0;ijPn0(2)()1.ijjPn三、多步转移概率及C-K方程第7章随机过程——马尔可夫链第24页定理7-3设{,0,1,}nXn为马氏链,则对于任意的正整数,km,有0()()()ijirrjrPmkPmPkinjkmnijaXaXPkmP|)(此方程称为Chapman-kolmogorov(切
本文标题:随机过程7-2wqh.
链接地址:https://www.777doc.com/doc-1955714 .html