马尔可夫过程基础

马尔可夫过程第一节马尔可夫链的定义及其性质第二节马尔可夫链的状态分类第三节平稳分布与遍历性第四节时间连续的马尔可夫链第一节马尔可夫链的定义及其性质一、马尔可夫链的定义1．马尔可夫链设随机过程{)(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}注:而与以前的状态表明)(tX在时刻n+1的状态jnX)1(的概率分布只与时刻n的状态inX)(有关，1)1(ninX，…，0)0(iX无关。有限马氏链状态空间是有限集I={0,1,2,…，k}2．一步转移概率马氏链在时刻n处于状态i的条件下，到时刻n+1转移到状态j的条件概率，即}|{1iXjXPnn称为在时刻n的一步转移概率，记作)(npij注:由于概率是非负的，且过程从一状态出发，经过一步转移后，必到达状态空间中的某个状态一步转移概率满足3．一步转移矩阵称为在时刻n的一步转移矩阵（1）0)(npij,Iji,（2）1)(npijIj,Ii如果固定时刻Tn则由一步转移概率为元素构成的矩阵1P：即有有限马氏链状态空间I={0，1，2，…，k})()()()()()(10111001001npnpnpnpnpnpPnn)()()()()()()()()(1011110001001npnpnpnpnpnpnpnpnpPkkkkkk4．齐次马氏链即则称此马氏链为齐次马氏链（即关于时间为齐次）如果马氏链的一步转移概率)(npij与n无关，ijnnpiXjXP}|{15．初始分布设}{)(00iXPip，Ii，如果对一切Ii都有0)(0ip1)(0ipIi称)(0ip为马氏链的初始分布注马氏链在初始时刻有可能处于I中任意状态，初始分布就是马氏链在初始时刻的概率分布。6．绝对分布概率分布}{)(iXPipnn，Ii，0n称为马氏链的绝对分布或称绝对概率定态分布若绝对分布)(ipn与n无关，即}{)(iXPipn，Ii，0n则称{)(ipn，Ii}为马氏链{0,nXn}的定态分布例1不可越壁的随机游动设一质点在线段[1，5]上随机游动，状态空间I={1，2，3，4，5}，每秒钟发生一次随机游动，移动的规则是：（1）若移动前在2，3，4处，则均以概率向左或向右移动一单位，或停留在原处；（2）若移动前在1处，则以概率1移到2处；（3）若移动前在5处，则以概率1移到4处。31用nX表示在时刻n质点的位置，则{nX，0n}是一个有限齐次马氏链，试写出一步转移矩阵.分析555453525145444342413534333231252423222115141312111pppppppppppppppppppppppppP01000313131000313131000313131000101P故12345其一步转移矩阵为10000210210002102100021021000011P若将移动规则改为（1）若移动前在2，3，4处，则均以概率向左或向右移动一单位；（2）若移动前在1，5处，则以概率1停留在原处。21因为质点在1，5两点被“吸收”，故称有两个吸收壁的随机游动分析例2赌徒输光问题赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，没有和局，直赌至两人中有一人输光为止。设在每一局中，甲获胜的概率为p，乙获胜的概率为，求甲输光的概率。pq1这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看，他初始时刻处于a，每次移动一格，向右移（即赢1元）的概率为p，向左移（即输1元）的概率为q。如果一旦到达0（即甲输光）或a+b（即乙输光）这个游动就停止。这时的状态空间为{0，1，2，…，c}，c=a+b，。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。考虑质点从j出发移动一步后的情况解设cj0设ju为质点从j出发到达0状态先于到达c状态的概率。在以概率p移到1j的假设下，到达0状态先于到达c状态的概率为1ju同理以概率q移到1j的前提下，到达0状态先于到达c状态的概率为1ju根据全概率公式有qupuujjj11这一方程实质上是一差分方程，它的边界条件是0,10cuu于是设))((11jjjjuupquupqr1jjjuud则可得到两个相邻差分间的递推关系1jjrdd于是0221drdrrddjjjj欲求au先求ju需讨论r当而1rcuu01)(110jjcjuujcjd10010drjcj011drrccjjuuu)(11iicjiuu011drdicjiicji01)1(drrrjcj01drrrcj两式相比ccjjrrru1故ccaarrru1ccapqpqpq)(1)()(当1r001cduuc而0)(djcuj因此cjcuj故cbcacua用同样的方法可以求得乙先输光的概率由以上计算结果可知当1r即qp时，甲先输光的概率为ccapqpqpq)(1)()(当1r即qp时，甲先输光的概率为cb当qp时，乙输光的概率为capqpq)(1)(1当qp时，乙先输光的概率为ca例3排队问题顾客到服务台排队等候服务，在每一个服务周期中只要服务台前有顾客在等待，就要对排在前面的一位提供服务，若服务台前无顾客时就不能实施服务。设在第n个服务周期中到达的顾客数为一随机变量nY且诸nY独立同分布：)nkPYkp（，,2,1,0k，1kkp记nX为服务周期n开始时服务台前顾客数则有0,1,11nnnnnnXYXYXX若若此时{nX，1n}为一马氏链，求其转移矩阵在第n周期已有一个顾客在服务，到第n+1周期已服务完毕解先求出转移概率)0|0(0100XXPp)0(0YP0p)0|1(0101XXPp)1(0YP1p)1|0(110nnXXPp)1|01(nnnXYXP)0(nYP0p)1|1(111nnXXPp)1|11(nnnXYXP)1(nYP1p)2|0(120nnXXPp)2|01(nnnXYXP)1(nYP0)2|1(121nnXXPp)2|11(nnnXYXP)0(nYP0p)2|2(122nnXXPp)1(nYP1p所以转移矩阵为210321043210432101000pppppppppppppppppP说明：二、基本性质性质1设{0,nXn}为马氏链，其状态空间为I，则},,,{110nniXiXiXP=}{0iXP}|{011iXiXP}|{1122iXiXP…}|{11nnnniXiXPnXXX,,,10的联合分布可由初始分布及转移概率所决定，即有},,,{110nniXiXiXPniiiiiinpppip11120)(则性质2设{0,nXn}为马氏链，其状态空间为I，表明},,|{11mnmnnnnniXiXiXP}|{11nnnniXiXP一个马氏链，如果按相反方向的时间排列，所成的序列也是一个马氏链。性质3设{0,nXn}为马氏链，其状态空间为I，表明若已知现在，则过去与未来是独立的。若nrs0，则在rriX的条件下，有}|,{rrssnniXiXiXP=}|{rrnniXiXP}|{rrssiXiXP则性质4设{0,nXn}为马氏链，其状态空间为I，表明若已知现在，则过去同时对将来各时刻的状态都不产生影响。},,|,,{0011iXiXiXiXPnnmnmnnn=}|,,{11nnmnmnnniXiXiXP特别},,|{00iXiXiXPnnmnmn=}|{nnmnmniXiXP则性质5设{0,nXn}为马氏链，其状态空间为I，表明马氏链的子链也是马氏链对任意给定的n个整数，nkkk210，有},,|{1111kkkkkkiXiXiXPnnnn=}|{11nnnnkkkkiXiXP在马氏链的研究中，须研究“从已知状态i出发，经过n次转移后，系统将处于状态j”的概率.三、n步转移矩阵1．n步转移概率系统在时刻m从状态i经过n步转移后处于状态j的概率设{0,nXn}为齐次马氏链，其状态空间为I，}|{iXjXPmnmIji.称为n步转移概率由于马氏链是齐次的，这个概率与m无关所以简记为)(nijp显然有2．n步转移矩阵0)(nijp，1)(nijIjp，Iji.由所有n步转移概率)(nijp为元素组成的矩阵)()(nijnpPIji.称为n步转移矩阵规定jijipPij，当，当01)()0(0)()()1(1ijijppP3．绝对概率公式定理1绝对概率由初始分布和n维转移概率完全确定即有)(0)()(nijIinpipjp证}{jXPn},{0iXjXPnIi}|{}{00iXjXPiXPnIi)(0)(nijIipip注若对定态分布，则ijIipipjp)()(},{0iXjXPin4．切普曼---柯尔莫哥洛夫方程定理2则证设{0,nXn}为一个马氏链，具有初始分布)(0ip，Ii和n步转移概率)(nijp，Iji.，0n，)()()(mkjIknikmnijppp)(mnijp}|{0iXjXPmn}|,{0iXkXjXPnIkmn}|,{0iXkXjXPnmnIk}|{0iXkXPnIk},|{0kXiXjXPnmn}|{}|{0kXjXPiXkXPnmnnIk)()(mkjIknikpp注（1）用一步转移概率表示多步转移概率kjIkikijppp)2(jkkkIkkiknijnnpppp2111,,)1(（2）n步转移矩阵nP与一步转移矩阵1P之间的关系nnPP1注（3）}{)(jXPjpnn为元素的行矩阵记为))(,),2(),1(()(NpppnPnnnI={1，2，…，N}由矩阵的乘法规则，得nPPnP)0()(表示：在时刻n，各状态的概率等于其初始状态的概率与n步转移概率矩阵之积。若链是齐次的，则有nPPnP1)0()(例4甲、乙两人进行比赛，设每局比赛中甲胜的概率是p，乙胜的概率是q，和局的概率是，（）。设每局比赛后，胜者记“+1”分，负者记“—1”分，和局不记分。当两人中有一人获得2分结束比赛。以表示比赛至第n局时甲获得的分数。r1rqpnX（1）写出状态空间；（2）求2P；（3）问在甲获得1分的情况下，再赛二局可以结束比赛的概率是多少？解（1）记甲获得“负2分”为状态1，获得“负1分”为状态2，获得“0分”为状态3，获得“正1分”为状态4，获得“正2分”为状态5，则状态空间为}54321{，，，，I一步转移概率矩阵