随机过程马尔可夫链.pptx

《随机过程马尔可夫链.pptx》由会员分享，可在线阅读，更多相关《随机过程马尔可夫链.pptx（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共80页浙江大学随机过程2第2页/共80页浙江大学随机过程3第3页/共80页浙江大学随机过程4第4页/共80页浙江大学随机过程5第5页/共80页浙江大学随机过程6第6页/共80页浙江大学随机过程7第7页/共80页浙江大学随机过程8n21X0X1X2XnXn-1第8页/共80页浙江大学随机过程913452第9页/共80页浙江大学随机过程1013452如果把1这点改为吸收壁，即Q一旦到达1这一点，则永远留在点1时，此时的转移概率矩阵为：一步转移概率矩阵为：第10页/共80页浙江大学随机过程11 例4：排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成。服务规则为：先到先服务，后

2、来者需在等候室依次排队，假设一个需要服务的顾客到达系统时发现系统内已有3个顾客，则该顾客立即离去。设时间间隔t内有一个顾客进入系统的概率为q，有一接受服务的顾客离开系统(即服务完毕)的概率为p,又设当t充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的，再设有无顾客来到与服务是否完毕是相互独立的。等候室服务台系统随机到达者离去者第11页/共80页浙江大学随机过程12现用马氏链来描述这个服务系统：设Xn=X(nt)表示时刻nt时系统内的顾客数，即系统的状态。Xn,n=0,1,2是一随机过程，状态空间I=0,1,2,3,且如前例1、例2的分析可知，它是一个时齐马氏链，它的一步转移概

3、率矩阵为：等候室服务台系统随机到达者离去者第12页/共80页浙江大学随机过程13 例5：设甲、乙两袋共装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值是无关的，这是时齐马氏链，一步转移矩阵为：甲乙第13页/共80页浙江大学随机过程14 例6：卜里耶（Polya)罐子模型。设一罐子装有r个红球，t个黑球，现随机从罐中取出一球，记录其颜色，然后将 球放回，并加入a个同色球。持续进行这一过

4、程，Xn表示 第n次试验结束时罐中的红球数，n=0，1,2,.Xn,n=0，1,2,是一随机过程，状态空间I=r,r+a,r+2a,当Xn=i 时，Xn+1=j的概率只 与i有关，与n时刻之前如何取到i值是无关的，这是一马氏链，但不是时齐的,一步转移概率为：第14页/共80页浙江大学随机过程15第15页/共80页浙江大学随机过程16第16页/共80页浙江大学随机过程17第17页/共80页浙江大学随机过程18第18页/共80页浙江大学随机过程19第19页/共80页浙江大学随机过程20第20页/共80页浙江大学随机过程21第21页/共80页浙江大学随机过程22第22页/共80页浙江大学随机过程23

5、证毕！证毕！第23页/共80页浙江大学随机过程24第24页/共80页浙江大学随机过程25第25页/共80页浙江大学随机过程26第26页/共80页浙江大学随机过程27第27页/共80页浙江大学随机过程28第28页/共80页浙江大学随机过程29第29页/共80页浙江大学随机过程30第30页/共80页浙江大学随机过程31第31页/共80页浙江大学随机过程32第32页/共80页浙江大学随机过程33第33页/共80页浙江大学随机过程34第34页/共80页浙江大学随机过程35第35页/共80页浙江大学随机过程36第36页/共80页浙江大学随机过程37第37页/共80页浙江大学随机过程38第38页/共80页

6、浙江大学随机过程39第39页/共80页浙江大学随机过程40第40页/共80页浙江大学随机过程41第41页/共80页浙江大学随机过程42第42页/共80页浙江大学随机过程43第43页/共80页浙江大学随机过程44第44页/共80页浙江大学随机过程45第45页/共80页浙江大学随机过程46第46页/共80页浙江大学随机过程47第47页/共80页浙江大学随机过程48第48页/共80页浙江大学随机过程49第49页/共80页浙江大学随机过程50第50页/共80页浙江大学随机过程51第51页/共80页浙江大学随机过程52第52页/共80页浙江大学随机过程53第53页/共80页浙江大学随机过程54第54页/

7、共80页浙江大学随机过程55第55页/共80页浙江大学随机过程56第56页/共80页浙江大学随机过程57第57页/共80页浙江大学随机过程58第58页/共80页浙江大学随机过程59第59页/共80页浙江大学随机过程60第60页/共80页浙江大学随机过程61第61页/共80页浙江大学随机过程62第62页/共80页浙江大学随机过程63第63页/共80页浙江大学随机过程64第64页/共80页浙江大学随机过程65第65页/共80页浙江大学随机过程66第66页/共80页浙江大学随机过程67第67页/共80页浙江大学随机过程68第68页/共80页浙江大学随机过程69例6：设有6个球(2个红球,4个白球)随

8、机平分放入甲,乙两个盒中.今每次从两盒中各任取一球并进行交换.表示开始时甲盒中的红球数,表示经n次交换 后甲盒中的红球数.(1)求此马氏链的初始分布;(2)求一步转移矩阵;(3)计算 第69页/共80页浙江大学随机过程70第70页/共80页浙江大学随机过程71第71页/共80页浙江大学随机过程72平稳分布的意义第72页/共80页浙江大学随机过程73第73页/共80页浙江大学随机过程74Markov链的应用PageRank PageRank,就是网页排名，又称网页级别，是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术，Google用它来体现网页的重要性。是Google的创始人拉里佩奇和谢尔盖布林在斯坦福大学发明了这项技术,并最终以拉里佩奇（Larry Page）之姓来命名。第74页/共80页浙江大学随机过程75Markov链的应用-PageRank第75页/共80页浙江大学随机过程76链接源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页/共80页浙江大学随机过程77第77页/共80页浙江大学随机过程78第78页/共80页浙江大学随机过程79第79页/共80页浙江大学随机过程80感谢您的观看！第80页/共80页