Markov链的定义.ppt

《Markov链的定义.ppt》由会员分享，可在线阅读，更多相关《Markov链的定义.ppt（28页珍藏版）》请在三一办公上搜索。

1、考虑一个随机过程X=Xt,tT.我们假设随机变量Xt的取值在某个集合S中,则集合S称为状态空间.独立随机试验模型最直接的推广就是Markov模型.粗略地说,一个随机过程如果给定了当前时刻t的值Xt,未来st的值Xs不受过去Xu(ut)的影响就称为是有Markov性.如果一个过程具有Markov性,则称该过程为Markov过程.特别地,当状态空间S为至多可列集时,Markov过程称为Markov链.,第3章 Markov过程,对于Markov链,当指标集T是非负整数时,称为离散时间Markov链;当指标集T是连续时间时,称为连续时间Markov链.,3.1 Markov链的定义和例子,对于离散时

2、间Markov链Xn,n=0,1,状态空间也可记为S=0,1,2,.此时,“Xn=i”就表示过程在n时刻处于状态i.,定义3.1 如果对任何一列状态i0,i1,in-1,i,j,及对任何n0,随机过程Xn,n0满足Markov性质:则称随机过程Xn,n0为离散时间Markov链.,定义3.2 设Xn,n0为一离散时间Markov链.对于任意i,jS,则 称为Markov链的一步转移概率,记作.当这一概率与n无关时,称该Markov链为有平稳转移概率,并记为.,有平稳转移概率的Markov链,也称为时齐Markov链.它的平稳转移概率具有下面性质:,例3.1 下图为一个迷宫,其中房间9放有一块奶

3、酪,而房间7里隐藏着一只猫.现有一只老鼠从房间1出发.假设老鼠没有任何信息,即:当老鼠在一个给定房间时,它进入相邻房间的概率为,其中k表示与该给定房间相邻的房间个数.假设一旦老鼠进入奶酪或猫所在的房间,则永远停留在该房间.,设Xn表示老鼠在n次变换房间之后所在房间号,则随机过程Xn,n=0,1,2,是一个以S=1,2,9为状态空间的Markov链,并且初始概率向量为S(0)=(1,0,0),转移概率矩阵为:,对于例3.1,我们特别感兴趣的问题是:老鼠在遇到猫之前找到奶酪的概率;老鼠在遇到猫之前找到奶酪所用时间的概率分布;老鼠在遇到猫之前找到奶酪需要经过的房间数的概率分布.,思考:假如在例3.1

4、中,猫在房间9里,奶酪在房间5里,并且老鼠在寻找奶酪过程中具有记忆性,即不会回到自己刚刚过来的房间.问老鼠在遇到猫之前可以寻找到奶酪的概率是多少?(0.75),例3.2(直线上的随机游动)考虑在直线上整数点上运动的粒子.当它处于位置j时,这里姑且假定j就是所处的状态,向右游动到j+1的概率为p而向左游动到j-1的概率为q=1-p.假定时刻0时粒子处在原点,即X0=0,于是粒子在时刻n所处的位置Xn就是一个Markov链,它有转移概率:,例3.3(带吸收壁的随机游动)一个粒子在直线上整数点0,1,n上运动,每次向右或左运动一步,概率分别为p和q=1-p.如果粒子到达了0或n,则停止运动.用Xn表

5、示粒子经过n步运动后所在的位置,则它是一个Markov链,状态空间为S=0,1,n,并且有转移概率:,当 时,称为简单对称随机游动.它可用于刻画公平赌博问题.,例如:考虑出现正、反面概率均为0.5的扔硬币游戏.让粒子的位置Xn代表赌徒甲在第n次赌博之后所赢的钱数(每扔硬币一次的输赢为1元).假如甲方有赌本a,乙方有赌本b,则可以证明甲先输光的概率为.,例3.4(排队论问题)假设一个修鞋匠有四把椅子,其中一把椅子为修鞋时顾客使用,另外三把椅子共顾客等待使用.当三把椅子全都被使用时,新到的顾客将会去其他地方寻找服务.假设该修鞋匠服务每一位顾客恰好都是10分钟.用Xn表示恰好第n个顾客服务完时正在等

6、待需要服务的顾客数,An表示在第n个顾客服务期间到达希望服务的顾客数.,用Xn表示恰好第n个顾客服务完时正在等待需要服务的顾客数,An表示在第n个顾客服务期间到达希望服务的顾客数.我们假设顾客的到达与离开不会同时发生,并且因此,转移概率矩阵为:,对于例3.4,我们特别感兴趣的问题是:(1)平均每小时内未被服务而离开的顾客数;(2)该修鞋匠平均每小时空闲时间长度.,定义3.3 设Xn,n0为任一时齐的离散时间Markov链.则对于任意i,jS,都与m无关,称为Markov链的n步转移概率,记作 即:,通常把以 为元素的矩阵 称为n步转移概率矩阵,记作.,定理3.1 对于任意的n,m0 及 i,j

7、S,证:按时刻n的状态进行分解,再用Markov性,有,注:定理3.1称为Chapman-Kolmogorov方程.它的直观意义十分明显,从状态i出发经过n+m步到达状态j可分成两阶段走:先从状态i出发经过n步到达状态k,然后从状态k出发经过m步到达状态j.由Markov性,后一阶段的状态转移与前一阶段的状态转移独立,故两个阶段的转移概率相乘.由于状态k不受任何限制,因此应对全部的k求和.,推论1 对于任意的n,m0,注:推论中的矩阵可以是无穷阶的,但是乘法规则与有限矩阵一样.,推论2 对于任意的n0,例3.5 考虑一个三状态的Markov链Xn,其转移概率矩阵为:其中p,q,r0,p+q+r

8、=1.这一Markov链从状态1出发,一旦进入状态0或2就被吸收了.求:(1)过程从状态1出发被状态0吸收的概率;(2)需要多长时间过程会进入吸收状态.,解:令,注意到:如果X1=0,则T=1,于是XT=0,因此,如果X1=2,则T=1,于是XT=2,因此,由全概率公式得:,求解上述方程得:.,由全概率公式得:,求解上述方程得:.,练习 某市场上只有A,B,C三种啤酒.A种啤酒改变广告方式后经市场调查发现:买啤酒的顾客每两个月平均转移率如下:设A,B,C三种啤酒的目前市场份额为25%,40%,35%,求半年后A种啤酒的市场份额.,解:转移概率矩阵为:,半年后顾客的转移概率矩阵为:,因此,即:半年后A种啤酒占有的市场份额为49.26%.,课外作业:Page 58 Ex 3,8,