Markov链的定义和例子.ppt

《Markov链的定义和例子.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、考虑一个随机过程X={Xt,tT}.我们假设随机变量Xt的取值在某个集合S中,则集合S称为状态空间.独立随机试验模型最直接的推广就是Markov模型.粗略地说,一个随机过程如果给定了当前时刻t的值Xt,未来s>t的值Xs不受过去Xu(u

2、定义和例子对于离散时间Markov链{Xn,n=0,1,…},状态空间也可记为S={0,1,2,…}.此时,“Xn=i”就表示过程在n时刻处于状态i.定义3.1如果对任何一列状态i0,i1,…,in-1,i,j,及对任何n0,随机过程{Xn,n0}满足Markov性质:则称随机过程{Xn,n0}为离散时间Markov链.定义3.2设{Xn,n0}为一离散时间Markov链.对于任意i,jS,则称为Markov链的一步转移概率,记作.当这一概率与n无关时,称该Markov链为有平稳转移概率,并记为.有平稳转移概率的Markov链,也称为时齐Markov链.它的平稳转

3、移概率具有下面性质:通常把转移概率排成一个(无穷维的)方阵,记作称为Markov链的转移概率矩阵.例3.1下图为一个迷宫,其中房间9放有一块奶酪,而房间7里隐藏着一只猫.现有一只老鼠从房间1出发.假设老鼠没有任何信息,即:当老鼠在一个给定房间时,它进入相邻房间的概率为,其中k表示与该给定房间相邻的房间个数.假设一旦老鼠进入奶酪或猫所在的房间,则永远停留在该房间.设Xn表示老鼠在n次变换房间之后所在房间号,则随机过程{Xn,n=0,1,2,…}是一个以S={1,2,…,9}为状态空间的Markov链,并且初始概率向量为S(0)=(1,0,…,0),转移概率矩阵为:对于例3.1

4、,我们特别感兴趣的问题是:老鼠在遇到猫之前找到奶酪的概率;老鼠在遇到猫之前找到奶酪所用时间的概率分布;老鼠在遇到猫之前找到奶酪需要经过的房间数的概率分布.思考:假如在例3.1中,猫在房间9里,奶酪在房间5里,并且老鼠在寻找奶酪过程中具有记忆性,即不会回到自己刚刚过来的房间.问老鼠在遇到猫之前可以寻找到奶酪的概率是多少?(0.75)例3.2(直线上的随机游动)考虑在直线上整数点上运动的粒子.当它处于位置j时,这里姑且假定j就是所处的状态,向右游动到j+1的概率为p而向左游动到j-1的概率为q=1-p.假定时刻0时粒子处在原点,即X0=0,于是粒子在时刻n所处的位置Xn就是一个

5、Markov链,它有转移概率:例3.3(带吸收壁的随机游动)一个粒子在直线上整数点0,1,…,n上运动,每次向右或左运动一步,概率分别为p和q=1-p.如果粒子到达了0或n,则停止运动.用Xn表示粒子经过n步运动后所在的位置,则它是一个Markov链,状态空间为S={0,1,…,n},并且有转移概率:当时,称为简单对称随机游动.它可用于刻画公平赌博问题.例如:考虑出现正、反面概率均为0.5的扔硬币游戏.让粒子的位置Xn代表赌徒甲在第n次赌博之后所赢的钱数(每扔硬币一次的输赢为1元).假如甲方有赌本a,乙方有赌本b,则可以证明甲先输光的概率为.例3.4(排队论问题)假设一个修

6、鞋匠有四把椅子,其中一把椅子为修鞋时顾客使用,另外三把椅子共顾客等待使用.当三把椅子全都被使用时,新到的顾客将会去其他地方寻找服务.假设该修鞋匠服务每一位顾客恰好都是10分钟.用Xn表示恰好第n个顾客服务完时正在等待需要服务的顾客数,An表示在第n个顾客服务期间到达希望服务的顾客数.用Xn表示恰好第n个顾客服务完时正在等待需要服务的顾客数,An表示在第n个顾客服务期间到达希望服务的顾客数.我们假设顾客的到达与离开不会同时发生,并且因此,转移概率矩阵为:对于例3.4,我们特别感兴趣的问题是:(1)平均每小时内未被服务而离开的顾客数;(2)该修鞋匠平均每小时空闲时间长度.定义3

7、.3设{Xn,n0}为任一时齐的离散时间Markov链.则对于任意i,jS,都与m无关,称为Markov链的n步转移概率,记作即:通常把以为元素的矩阵称为n步转移概率矩阵,记作.若时齐Markov链的n步转移概率矩阵为,初始概率向量为S(0),则经过n步转移后的概率向量为:.定理3.1对于任意的n,m0及i,jS,证:按时刻n的状态进行分解,再用Markov性,有注:定理3.1称为Chapman-Kolmogorov方程.它的直观意义十分明显,从状态i出发经过n+m步到达状态j可分成两阶段走:先从状态i出发