随机过程7-2wqh.

第7章随机过程——马尔可夫链第1页§7.2马尔可夫链一、马尔可夫链的定义四、多步转移概率及C-K方程五、遍历性与平稳分布二、转移概率三、马氏链的几个例子第7章随机过程——马尔可夫链第2页无后效性过程在已知现在状态的条件下，将来所处的状态与过去的状态无关。马尔科夫过程的分类（1）时间离散、状态离散的马尔科夫过程通常称之为马尔科夫链，简称马氏链。（2）时间连续、状态离散的马尔科夫过程。（3）时间连续、状态连续的马尔科夫过程。马尔科夫过程马尔可夫（俄）1856-1922过去现在将来第7章随机过程——马尔可夫链第3页定义7-16设随机过程{(),}XttT，状态空间为I，若对于t的任意n个值12,nttt3,,intT有112211()(),(),,()nnnnPXtxXtxXtxXtx11()|(),,,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}IiiN011,,,,,nnaaaaI对任意的n及1100111111,,,0|1nnnnnnnnnnnnnPXaXaXaXaaaPXaXaaaa{,0,1,2,}nXn是一个马氏链。第7章随机过程——马尔可夫链第7页由马氏链定义及概率论知识可知定义7-18设{,0,1,}nXn为马尔可夫链，称0X的分布0{},jjPXaaI为该链的初始分布，称nX的分布{},njjPXaaI为该链的绝对分布。0011001100001111,,,||,,,nnnnnnPXaXaXaPXaPXaXaPXaXaXaXa00110011||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)|ijnjnijjPnnPXaXa101|.njnijPXaXa第7章随机过程——马尔可夫链第9页定义7-20当转移概率(,1)ijPnn只与状态,ijaa有关而与n无关时，则称转移概率具有平稳性，这时，马尔可夫链称为是齐次的或时齐的，并记111ijijijnjnipppnnPXaXa()(,)|否则，就称之为非时齐的。本课程只讨论齐次马氏链第7章随机过程——马尔可夫链第10页(1)(1)ijpPP0100001011011101jjjiiiijaaaapppapppappp称为马氏链的一步转移概率矩阵；其中列为1mX的状态，行为mX的状态。由转移概率性质知，一步转移概率矩阵中任一行元素之和为1。1mX的状态mX的状态定义7-21齐次马氏链的所有一步转移概率ijp表示成矩阵的形式，即第7章随机过程——马尔可夫链第11页12n0X1X2X1nXnX显然，当为已知时，所处的状态的概率分布只与有关，而与时刻以前所处的状态无关。,nXiiI1nXnXin所以它是一个马尔可夫链，而且还是齐次的。三、马氏链的几个例子例7-17（0-1传输系统）在只传输数字0和1的串联系统中，设每一级的传真率（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）为，误码率为，并设一个单位时间传输一级，是第一级的输入，是第级的输出。那么，是一随机过程。p1qp0XnX(1)nn{,0,1,}nXn{0,1}I状态空间为第7章随机过程——马尔可夫链第12页它的一步转移概率为1,,{},0,1,,ijnnpjipPXjXiijqji从而它的一步转移概率矩阵为01pqPqp01第7章随机过程——马尔可夫链第13页011,,,,nnaaaaI110011|,,nnnnnnPXaXaXaPXa解:对任意的n及11|nnnnPXaXaIiqiXPin,记所以为马氏链。{}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。又设当充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的。再设有无顾客来到与服务是否完毕是相互独立的。现用马氏链来描述这个服务系统。tt第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).ppqpq12(1).pqp130.p第7章随机过程——马尔可夫链第22页类似地，有2132(1)pppq22(1)(1)ppqpq23(1)pqp0(||2)ijpij33p――或者一人将离去且另一人将进入系统，或者无人离开系统的概率，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;ijPn0(2)()1.ijjPn三、多步转移概率及C-K方程第7章随机过程——马尔可夫链第24页定理7-3设{,0,1,}nXn为马氏链，则对于任意的正整数,km，有0()()()ijirrjrPmkPmPkinjkmnijaXaXPkmP|)(此方程称为Chapman-kolmogorov(切