马尔科夫链例题整理.ppt

上传人:xt****7 文档编号:3748656 上传时间:2019-12-23 格式:PPT 页数:61 大小:1.26MB
返回 下载 相关 举报
马尔科夫链例题整理.ppt_第1页
第1页 / 共61页
马尔科夫链例题整理.ppt_第2页
第2页 / 共61页
马尔科夫链例题整理.ppt_第3页
第3页 / 共61页
点击查看更多>>
资源描述
若表示质点在时刻n所处的位置,分析它的概率特性。,例1,直线上带吸收壁的随机游动(醉汉游动),设一质点在线段1,5上随机游动,每秒钟发生一次随机游动,移动的规则是:,(1)若移动前在2,3,4处,则均以概率向左或向右移动一单位;(2)若移动前在1,5处,则以概率1停留在原处。,质点在1,5两点被“吸收”,前言:马尔可夫过程的描述分类,首页,无记忆性,未来处于某状态的概率特性只与现在状态有关,而与以前的状态无关,这种特性叫无记忆性(无后效性)。,例4布朗运动,若表示质点在时刻n所处的位置,求一步转移概率。,引例,例1直线上带吸收壁的随机游动(醉汉游动),设一质点在线段1,5上随机游动,每秒钟发生一次随机游动,移动的规则是:,(1)若移动前在2,3,4处,则均以概率向左或向右移动一单位;(2)若移动前在1,5处,则以概率1停留在原处。,质点在1,5两点被“吸收”,一步转移概率矩阵的计算,首页,有两个吸收壁的随机游动,其一步转移矩阵为,状态空间I=1,2,3,4,5,,参数集T=1,2,3,,例2带有反射壁的随机游动,设随机游动的状态空间I=0,1,2,移动的规则是:(1)若移动前在0处,则下一步以概率p向右移动一个单位,以概率q停留在原处(p+q=1);(2)若移动前在其它点处,则均以概率p向右移动一个单位,以概率q向左移动一个单位。,设表示在时刻n质点的位置,则,是一个齐次马氏链,写出其一步转移概率。,首页,首页,首页,例3一个圆周上共有N格(按顺时针排列),一个质点在该圆周上作随机游动,移动的规则是:质点总是以概率p顺时针游动一格,以概率逆时针游动一格。试求转移概率矩阵。,首页,4一个质点在全直线的整数点上作随机游动,移动的规则是:以概率p从i移到i-1,以概率q从i移到i+1,以概率r停留在i,且,试求转移概率矩阵。,首页,5设袋中有a个球,球为黑色的或白色的,今随机地从袋中取一个球,然后放回一个不同颜色的球。若在袋里有k个白球,则称系统处于状态k,试用马尔可夫链描述这个模型(称为爱伦菲斯特模型),并求转移概率矩阵。,解这是一个齐次马氏链,其状态空间为,I=0,1,2,a,一步转移矩阵是,首页,练习题扔一颗色子,若前n次扔出的点数的最大值为j,就说试问是否为马氏链?求一步转移概率矩阵。,I=1,2,3,4,5,6,首页,例1,甲、乙两人进行比赛,设每局比赛中甲胜的概率是p,乙胜的概率是q,和局的概率是,()。设每局比赛后,胜者记“+1”分,负者记“1”分,和局不记分。当两人中有一人获得2分结束比赛。以表示比赛至第n局时甲获得的分数。,(1)写出状态空间;,(3)问在甲获得1分的情况下,再赛二局可以结束比赛的概率是多少?,首页,解,(1),记甲获得“负2分”为状态1,获得“负1分”为状态2,获得“0分”为状态3,获得“正1分”为状态4,获得“正2分”为状态5,则状态空间为,一步转移概率矩阵,首页,(2)二步转移概率矩阵,首页,(3),从而结束比赛的概率;,从而结束比赛的概率。,所以题中所求概率为,首页,分析,例2赌徒输光问题,赌徒甲有资本a元,赌徒乙有资本b元,两人进行赌博,每赌一局输者给赢者1元,没有和局,直赌至两人中有一人输光为止。设在每一局中,甲获胜的概率为p,乙获胜的概率为,求甲输光的概率。,这个问题实质上是带有两个吸收壁的随机游动。从甲的角度看,他初始时刻处于a,每次移动一格,向右移(即赢1元)的概率为p,向左移(即输1元)的概率为q。如果一旦到达0(即甲输光)或a+b(即乙输光)这个游动就停止。这时的状态空间为0,1,2,c,c=a+b,。现在的问题是求质点从a出发到达0状态先于到达c状态的概率。,首页,考虑质点从j出发移动一步后的情况,解,同理,根据全概率公式有,这一方程实质上是一差分方程,它的边界条件是,首页,于是,设,则可得到两个相邻差分间的递推关系,于是,欲求,先求,需讨论r,首页,当,而,两式相比,首页,故,当,而,因此,故,首页,用同样的方法可以求得乙先输光的概率,由以上计算结果可知,首页,例3排队问题,顾客到服务台排队等候服务,在每一个服务周期中只要服务台前有顾客在等待,就要对排在前面的一位提供服务,若服务台前无顾客时就不能实施服务。,则有,求其转移矩阵,在第n周期已有一个顾客在服务,到第n+1周期已服务完毕,解,先求出转移概率,首页,所以转移矩阵为,首页,证,定理4.3马尔科夫链的有限维分布:,练习:马氏链的状态空间I=1,2,3,初始概率为,例4,市场占有率预测,设某地有1600户居民,某产品只有甲、乙、丙3厂家在该地销售。经调查,8月份买甲、乙、丙三厂的户数分别为480,320,800。9月份里,原买甲的有48户转买乙产品,有96户转买丙产品;原买乙的有32户转买甲产品,有64户转买丙产品;原买丙的有64户转买甲产品,有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂,试求,(1)转移概率矩阵;(2)9月份市场占有率的分布;(3)12月份市场占有率的分布;,解,(1)E1,2,3,状态1、2、3分别表示甲、乙、丙的用户,一步转移概率矩阵为,(2)以1600除8月份甲,乙,丙的户数,得初始概率分布(即初始市场占有率),所以9月份市场占有率分布为,(3)12月份市场占有率分布为,例1,其一步转移矩阵为,试研究各状态间的关系,并画出状态传递图。,解,先按一步转移概率,画出各状态间的传递图,首页,由图可知,状态0可到达状态1,经过状态1又可到达状态2;反之,从状态2出发经状态1也可到达状态0。,因此,状态空间I的各状态都是互通的。,又由于I的任意状态i(i=0,1,2)不能到达I以外的任何状态,,所以I是一个闭集,而且I中没有其它闭集,所以此马氏链是不可约的。,首页,例2,其一步转移矩阵为,试讨论哪些状态是吸收态、闭集及不可约链。,解,先按一步转移概率,画出各状态间的传递图,首页,闭集,,由图可知,状态3为吸收态,且,闭集,,闭集,,其中是不可约的。,又因状态空间I有闭子集,,故此链为非不可约链。,首页,3常返态与瞬时态,则称状态i为常返态,则称状态i为瞬时态,注,“常返”一词,有时又称“返回”、“常驻”或“持久”,“瞬时”也称“滑过”或“非常返”,定理4,定理5,定理6,如果i为常返态,且,则j也是常返态。,定理7,所有常返态构成一个闭集,5正常返态与零常返态,平均返回时间,从状态i出发,首次返回状态i的平均时间,称为状态i平均返回时间.,根据的值是有限或无限,可把常返态分为两类:,设i是常返态,,则称i为正常返态;,则称i为零常返态。,首页,例,其一步转移矩阵如下,是对I进行分解。,I可分解为:C1=2,3,4C2=5,6,7两个闭集及N=1,即I=N+C1+C2,用极限判断状态类型的准则,(2)i是零常返态,(3)i是正常返态,(1)i是瞬时态,且,且,首页,例3,转移矩阵,试对其状态分类。,解,按一步转移概率,画出各状态间的传递图,首页,从图可知,此链的每一状态都可到达另一状态,即4个状态都是相通的。,考虑状态1是否常返,,于是状态1是常返的。,又因为,所以状态1是正常返的。,此链所有状态都是正常返的。,三、状态的周期与遍历,1周期状态,对于任意的,令,其中GCD表示最大公约数,则称为周期态,,则称为非周期态。,定理11,2遍历状态,若状态i是正常返且非周期,则称i为遍历状态。,例4,设马氏链的状态空间I=0,1,2,,转移概率为,试讨论各状态的遍历性。,解,根据转移概率作出状态传递图,首页,从图可知,对任一状态都有,,故由定理可知,I中的所以状态都是相通的,,因此只需考虑状态0是否正常返即可。,故,从而0是常返态。,又因为,所以状态0为正常返。,又由于,故状态0为非周期的,从而状态0是遍历的。,故所有状态i都是遍历的。,例5设马氏链的状态空间I=1,2,3,4,其一步转移矩阵为,解,试对其状态分类。,按一步转移概率,画出各状态间的传递图,它是有限状态的马氏链,故必有一个常返态,又链中四个状态都是互通的。因此,所有状态都是常返态,这是一个有限状态不可约的马氏链。,可继续讨论是否为正常返态,可讨论状态1,状态1是常返态,状态1是正常返态,所以,全部状态都是正常返态,首页,例1,其一步转移矩阵为,试证此链具有遍历性,并求平稳分布和各状态的平均返回时间,解,由于,首页,所以,因此,该马氏链具有遍历性。,解得,所以马氏链的平稳分布为,各状态的平均返回时间,例2,设有6个球(其中2个红球,4个白球)分放于甲、乙两个盒子中,每盒放3个,今每次从两个盒中各任取一球并进行交换,以表示开始时甲盒中红球的个数,()表示经n次交换后甲盒中的红球数。,(1)求马氏链,的转移概率矩阵;,(2)证明,是遍历的;,(3)求,(4)求,首页,解,其一步转移矩阵为,甲,乙,红球0白球3,红球2白球1,红球1白球2,红球1白球2,红球2白球1,红球0白球3,由状态传递图,(2)由于它是一个有限马氏链,故必有一个常返态,,又链中三个状态0、1、2都相通,所以每个状态都是常返态。所以是一个不可约的有限马氏链,从而每个状态都是正常返的。,所以此链为非周期的。,故此链是不可约非周期的正常返链,即此链是遍历的。,首页,也可以利用定理1证明遍历性,首页,解之得,故得,首页,(4),首页,例3,市场占有率预测,设某地有1600户居民,某产品只有甲、乙、丙3厂家在该地销售。经调查,8月份买甲、乙、丙三厂的户数分别为480,320,800。9月份里,原买甲的有48户转买乙产品,有96户转买丙产品;原买乙的有32户转买甲产品,有64户转买丙产品;原买丙的有64户转买甲产品,有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂,试求,(1)转移概率矩阵;(2)9月份市场占有率的分布;(3)12月份市场占有率的分布;(4)当顾客流如此长期稳定下去市场占有率的分布。(5)各状态的平均返回时间,首页,解,(1)由题意得频数转移矩阵为,再用频数估计概率,得转移概率矩阵为,(2)以1600除以N中各行元素之和,得初始概率分布(即初始市场占有率),首页,所以9月份市场占有率分布为,(3)12月份市场占有率分布为,首页,(4)由于该链不可约、非周期、状态有限正常返的,所以是遍历的。,解方程组,即得当顾客流如此长期稳定下去是市场占有率的分布为,(5),例4(书中69页例4.18),其一步转移矩阵为,试并每个不可约闭集的平稳分布,的平稳分布得,状态空间可分解为:C=2,3,4D=5,6,7两个闭集,分别求对应转移概率矩阵,
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 图纸专区 > 课件教案


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!