《马尔科夫链ppt课件.ppt》由会员分享,可在线阅读,更多相关《马尔科夫链ppt课件.ppt(78页珍藏版)》请在三一办公上搜索。
1、关键词: 马尔可夫性 时齐马尔可夫链 n步转移概率 C-K方程 马氏链的有限维分布律 常返 暂留 正常返 零常返 互达 周期 不可约 平稳分布,第十一章 马尔可夫链,浙江大学随机过程,3,浙江大学随机过程,4,4,浙江大学随机过程,5,浙江大学随机过程,6,浙江大学随机过程,7,浙江大学随机过程,8,浙江大学随机过程,9,浙江大学随机过程,10,浙江大学随机过程,11,如果把1这点改为吸收壁,即Q一旦到达1这一点, 则永远留在点1时,此时的转移概率矩阵为:,浙江大学随机过程,12,例4:排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成。服务规则为:先到先服务,后来者需在等候室依次
2、排队,假设一个需要服务的顾客到达系统时发现系统内已有3个顾客,则该顾客立即离去。 设时间间隔t内有一个顾客进入系统的概率为q,有一接受服务的顾客离开系统(即服务完毕)的概率为p,又设当t充分小时,在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的,再设有无顾客来到与服务是否完毕是相互独立的。,浙江大学随机过程,13,现用马氏链来描述这个服务系统: 设Xn=X(nt)表示时刻nt时系统内的顾客数,即系统的状态。Xn,n=0,1,2是一随机过程,状态空间I=0,1,2,3,且如前例1、例2的分析可知,它是一个时齐马氏链,它的一步转移概率矩阵为:,浙江大学随机过程,14,例5:设甲、乙两袋共装
3、5个球,每次任取一袋,并从袋中 取出一球放入另一袋(若袋中无球则不取)。Xn表示 第n次抽取后甲袋的球数,n=1,2,.Xn,n=1,2, 是一随机过程,状态空间I=0,1,2,3,4,5,当Xn=i 时,Xn+1=j的概率只与i有关,与n时刻之前如何取到 i值是无关的,这是时齐马氏链,一步转移矩阵为:,浙江大学随机过程,15,例6:卜里耶(Polya)罐子模型。设一罐子装有r个红球, t个黑球,现随机从罐中取出一球,记录其颜色,然后将 球放回,并加入a个同色球。持续进行这一过程,Xn表示 第n次试验结束时罐中的红球数,n=0,1,2,. Xn,n=0,1,2,是一随机过程, 状态空间I=r,
4、r+a,r+2a,当Xn=i 时,Xn+1=j的概率只 与i有关,与n时刻之前如何取到i值是无关的, 这是一马氏链,但不是时齐的,一步转移概率为:,浙江大学随机过程,16,浙江大学随机过程,17,浙江大学随机过程,18,浙江大学随机过程,19,浙江大学随机过程,20,浙江大学随机过程,21,浙江大学随机过程,22,浙江大学随机过程,23,浙江大学随机过程,24,证毕!,浙江大学随机过程,25,浙江大学随机过程,26,浙江大学随机过程,27,浙江大学随机过程,28,浙江大学随机过程,29,浙江大学随机过程,30,浙江大学随机过程,31,浙江大学随机过程,32,浙江大学随机过程,33,浙江大学随机
5、过程,34,浙江大学随机过程,35,浙江大学随机过程,36,浙江大学随机过程,37,浙江大学随机过程,38,浙江大学随机过程,39,浙江大学随机过程,40,浙江大学随机过程,41,浙江大学随机过程,42,浙江大学随机过程,43,浙江大学随机过程,44,浙江大学随机过程,45,浙江大学随机过程,46,浙江大学随机过程,47,浙江大学随机过程,48,浙江大学随机过程,49,浙江大学随机过程,50,浙江大学随机过程,51,浙江大学随机过程,52,浙江大学随机过程,53,浙江大学随机过程,54,浙江大学随机过程,55,浙江大学随机过程,56,浙江大学随机过程,57,浙江大学随机过程,58,浙江大学随机
6、过程,59,浙江大学随机过程,60,浙江大学随机过程,61,浙江大学随机过程,62,浙江大学随机过程,63,浙江大学随机过程,64,浙江大学随机过程,65,浙江大学随机过程,66,浙江大学随机过程,67,浙江大学随机过程,68,例6:设有6个球(2个红球,4个白球)随机平分放入甲,乙两个盒中.今每次从两盒中各任取一球并进行交换. 表示开始时甲盒中的红球数, 表示经n次交换 后甲盒中的红球数.(1)求此马氏链的初始分布;(2)求一步转移矩阵;(3)计算,浙江大学随机过程,69,浙江大学随机过程,70,浙江大学随机过程,71,平稳分布的意义,浙江大学随机过程,72,浙江大学随机过程,73,Markov链的应用PageRank,PageRank, 就是网页排名,又称网页级别,是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术,Google用它来体现网页的重要性。是Google的创始人拉里佩奇和谢尔盖布林在斯坦福大学发明了这项技术, 并最终以拉里佩奇(Larry Page)之姓来命名。,浙江大学随机过程,74,Markov链的应用-PageRank,浙江大学随机过程,75,链接源I D 链接目标 1 1 2,3,4,5, 7 2 1 3 1,2 4 2,3,5 5 1,3,4,6 6 1,5 7 5,浙江大学随机过程,76,浙江大学随机过程,77,浙江大学随机过程,78,