PHP培训教程之php的正则表达式完全手册

1/32第五章Markov过程第一节基本概念第二节Markov链的状态分类及性质第三节极限定理及平稳分布第四节Markov链的应用第五节连续时间Markov链第六节转移概率和柯尔莫哥洛夫微分方程2/32简称马氏过程。设{)(tX，Tt}对任意n个不同的1t,2t,…,Ttn且nntttt121，有|)((nnxtXP11)(nnxtX，…，))(11xtX=|)((nnxtXP11)(nnxtX），则称()Xt为马尔可夫（Markov）过程已知“现在”的条件下，“过去”与“将来”是独立的。马氏性（无后效性）3/32第一节基本概念一、Markov链的定义1．Markov链设随机过程{)(tX,Tt}，其中时间T={0,1,…}，状态空间I={0,1,2,…}，若对任一时刻n，以及任意状态jiiiin,,,,,110，有,)1(,)(|)1({1ninXinXjnXP})0(,)1(,01iXiX})(|)1({inXjnXP则称{)(tX,Tt}为一个马尔可夫链（或马氏链）简记为{nX,0n}4/32有限马氏链状态空间是有限集I={0,1,2,…，k}2．一步转移概率马氏链在时刻n处于状态i的条件下，到时刻n+1转移到状态j的条件概率，即}|{1iXjXPnn称为在时刻n的一步转移概率，记作)(npij注:马氏链由和条件概率决定00{}PXi11{|}nnnnPXiXi5/32注:由于概率是非负的，且过程从一状态出发，经过一步转移后，必到达状态空间中的某个状态一步转移概率满足3．一步转移矩阵称为在时刻n的一步转移矩阵（1）0)(npij,Iji,（2）1)(npijIj,Ii如果固定时刻Tn则由一步转移概率为元素构成的矩阵1P：随机矩阵6/32即有有限马氏链状态空间I={0，1，2，…，k})()()()()()(10111001001npnpnpnpnpnpPnn)()()()()()()()()(1011110001001npnpnpnpnpnpnpnpnpPkkkkkk7/324．齐次马氏链即则称此马氏链为齐次马氏链（即关于时间为齐次）如果马氏链的一步转移概率)(npij与n无关，ijnnpiXjXP}|{15．初始分布设}{)(00iXPip，Ii，如果对一切Ii都有0)(0ip1)(0ipIi称)(0ip为马氏链的初始分布8/32注马氏链在初始时刻有可能处于I中任意状态，初始分布就是马氏链在初始时刻的概率分布。6．绝对分布概率分布}{)(iXPipnn，Ii，0n称为马氏链的绝对分布或称绝对概率例1天气预报问题9/32例2不可越壁的随机游动设一质点在线段[1，5]上随机游动，状态空间I={1，2，3，4，5}，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在2，3，4处，则均以概率1/3向左或向右移动一单位，或停留在原处；（2）若移动前在1处，则以概率1移到2处；（3）若移动前在5处，则以概率1移到4处。用nX表示在时刻n质点的位置，则{nX，0n}是一个有限齐次马氏链，试写出一步转移矩阵.10/32分析555453525145444342413534333231252423222115141312111pppppppppppppppppppppppppP01000313131000313131000313131000101P故1234511/32其一步转移矩阵为10000210210002102100021021000011P若将移动规则改为（1）若移动前在2，3，4处，则均以概率1/2向左或向右移动一单位；（2）若移动前在1，5处，则以概率1停留在原处。因为质点在1，5两点被“吸收”，故称有两个吸收壁的随机游动12/32分析例3赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为q=1-p，求甲先输光的概率。这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a+b（即乙输光）这个游动就停止。这时的状态空间为{0，1，2，…，c}，c=a+b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。au13/32考虑质点从j出发移动一步后的情况解设cj0设ju为质点从j出发到达0状态先于到达c状态的概率。在以概率p移到1j的假设下，到达0状态先于到达c状态的概率为1ju同理以概率q移到1j的前提下，到达0状态先于到达c状态的概率为1ju根据全概率公式有qupuujjj11这一方程实质上是一差分方程，它的边界条件是0,10cuu14/32于是设（p+q）11jjjqupuu))((11jjjjuupquupqr1jjjuud则可得到两个相邻差分间的递推关系1jjrdd于是0221drdrrddjjjj欲求au先求ju需讨论r15/32当而1rcuu01)(110jjcjuujcjd10010drjcj011drrccjjuuu)(11iicjiuu011drdicjiicji01)1(drrrjcj01drrrcj两式相比ccjjrrru116/32故ccaarrru1ccapqpqpq)(1)()(当1r001cduuc而0)(djcuj因此cjcuj故cbcacua17/32用同样的方法可以求得乙先输光的概率由以上计算结果可知当1r即qp时，甲先输光的概率为ccapqpqpq)(1)()(当1r即qp时，甲先输光的概率为cb当qp时，乙输光的概率为capqpq)(1)(1当qp时，乙先输光的概率为ca||18/32说明：二、基本性质性质1设{0,nXn}为马氏链，其状态空间为I，则},,,{110nniXiXiXP=}{0iXP}|{011iXiXP}|{1122iXiXP…}|{11nnnniXiXPnXXX,,,10的联合分布可由初始分布及转移概率所决定，即有},,,{110nniXiXiXPniiiiiinpppip11120)(19/32则性质2设{0,nXn}为马氏链，其状态空间为I，表明},,|{11mnmnnnnniXiXiXP}|{11nnnniXiXP一个马氏链，如果按相反方向的时间排列，所成的序列也是一个马氏链。20/32性质3设{0,nXn}为马氏链，其状态空间为I，表明若已知现在，则过去与未来是独立的。若nrs0，则在rriX的条件下，有}|,{rrssnniXiXiXP=}|{rrnniXiXP}|{rrssiXiXP21/32则性质4设{0,nXn}为马氏链，其状态空间为I，表明若已知现在，则过去同时对将来各时刻的状态都不产生影响。},,|,,{0011iXiXiXiXPnnmnmnnn=}|,,{11nnmnmnnniXiXiXP特别},,|{00iXiXiXPnnmnmn=}|{nnmnmniXiXP22/32则性质5设{0,nXn}为马氏链，其状态空间为I，表明马氏链的子链也是马氏链对任意给定的n个整数，nkkk210，有},,|{1111kkkkkkiXiXiXPnnnn=}|{11nnnnkkkkiXiXP23/32在马氏链的研究中，须研究“从已知状态i出发，经过n次转移后，系统将处于状态j”的概率.三、n步转移矩阵1．n步转移概率系统在时刻m从状态i经过n步转移后处于状态j的概率设{0,nXn}为齐次马氏链，其状态空间为I，}|{iXjXPmnmIji.称为n步转移概率由于马氏链是齐次的，这个概率与m无关所以简记为)(nijp24/32显然有2．n步转移矩阵0)(nijp，1)(nijIjp，Iji.由所有n步转移概率)(nijp为元素组成的矩阵)()(nijnpPIji.称为n步转移矩阵规定jijipPij，当，当01)()0(0)()()1(1ijijppP25/323．绝对概率公式定理1绝对概率由初始分布和n维转移概率完全确定即有)(0)()(nijIinpipjp证}{jXPn},{0iXjXPnIi}|{}{00iXjXPiXPnIi)(0)(nijIipip},{0iXjXPin26/324．切普曼—柯尔莫哥洛夫方程（C－K方程）定理2则证设{0,nXn}为一个马氏链，具有初始分布)(0ip，Ii和n步转移概率)(nijp，Iji.，0n，)()()(mkjIknikmnijppp)(mnijp}|{0iXjXPmn}|,{0iXkXjXPnIkmn}|,{0iXkXjXPnmnIk}|{0iXkXPnIk},|{0kXiXjXPnmn}|{}|{0kXjXPiXkXPnmnnIk)()(mkjIknikpp27/32注（1）用一步转移概率表示多步转移概率kjIkikijppp)2(jkkkIkkiknijnnpppp2111,,)1(（2）n步转移矩阵nP与一步转移矩阵1P之间的关系nnPP128/32注（3）}{)(jXPjpnn为元素的行矩阵记为))(,),2(),1(()(NpppnPnnnI={1，2，…，N}由矩阵的乘法规则，得nPPnP)0()(表示：在时刻n，各状态的概率等于其初始状态的概率与n步转移概率矩阵之积。若链是齐次的，则有nPPnP1)0()(Eg.29/32例4甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是q，和局的概率是r,（p+q+r=1）。设每局比赛后，胜者记“+1”分，负者记“-1”分，和局不记分。当两人中有一人获得2分结束比赛。以表示比赛至第n局时甲获得的分数。nX（1）写出状态空间；（2）求2P；（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？30/32解（1）记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为}54321{，，，，I一步转移概率矩阵10000000000000011prqprqprqP31/32（2）二步转移概率矩阵212PP100002022202000012222222rpppqrqrqpprpqrrqqpprpqrrpq32/32（3）在2P中)2(45p是在甲得1分的情况下经二步转移至2分从而结束比赛的概率；)2(41p是在甲得1分的情况下经二步转移至—2分（即乙得2分）从而结束比赛的概率。所以题中所求概率为)2(45p)2(41p)1(0)(rprppEnd