剖析马氏链平稳分布的讲解——谈《应用随机过程》教学

刘秀芹，赵金玲，范玉妹

（北京科技大学数理学院数力系，北京 100083）

剖析马氏链平稳分布的讲解
——谈《应用随机过程》教学

刘秀芹，赵金玲，范玉妹

（北京科技大学数理学院数力系，北京 100083）

通过平稳分布在Google搜索技术中的应用角度讲解马氏链的平稳分布的概念，并在此基础上对应用随机过程的教学做了粗浅的探讨.

应用随机过程教学；马氏链的平稳分布；Google搜索；PageRank

1 引 言

应用随机过程是一门以概率论和复变函数为基础的面向理工科高年级学生的课程，它的理论在物理、生物、工程、经济和管理等方面都有广泛的应用，随机过程已经成为近代科技工作者必须掌握的一个理论工具.随机过程是研究随机现象的变化过程的数学学科，也是一门接近现实生活的理论与实际相结合的课程，但是对工科学生来说随机过程是一门相对比较难的课程.如何使学生既能准确掌握其中的理论知识，又能把理论应用于实际是大多数教随机过程的教师在教学过程中追求的目标.本文通过对随机过程中马氏链的平稳分布概念的讲解，拟对应用随机过程的教学作一些粗浅的探讨.

2 平稳分布的概念及其在Google搜索技术中的应用

2.1 马氏链的平稳分布的定义.

马氏链的平稳分布定义：设｛X n，n≥1｝是齐次马尔可夫链，状态空间为I，转移概率为p ij，称概率分布｛πj，j∈I｝为马尔可夫链的平稳分布，若它满足

由上述定义可知，只要知道马氏链的一步转移概率矩阵，即可通过求解上面的线性方程组得到它的平稳分布.在应用随机过程的教材中，一般只有平稳分布的定义以及平稳分布的求解方法两部分内容，对于平稳分布在实际中的应用涉及的很少.

仅从平稳分布的定义来看，大多数同学对它不会有什么深刻的认识，可能像其它一些数学名词一样匆匆划过脑海，不留任何痕迹.而马氏链的平稳分布是随机过程这门课中非常重要的内容，并且它在其它许多交叉学科中有着广泛的应用，为此，我们在教学过程中采用先引入平稳分布的抽象概念，然后结合平稳分布在实际中的应用来理解抽象概念的导入式教学方法.

2.2 平稳分布应用.

平稳分布与Google搜索.

提出问题：Google搜索是人们最常用的搜索引擎之一，若我们在搜索引擎中输入一个关键词，Google就会非常迅速地（有的连0.01秒都不到）在窗口中输出大量的结果（有时有上千万条结果）.一般情况下，用户所关心的信息大多在前面几条结果中就能获得.那么，Google是如何实现快速的搜索，如何合理定义网页的重要性的呢？

近年来，网络信息在不断突飞猛进地增长.在海量的信息中完成搜索自然不易，但采用适当的方式来刻画网页的重要性，从而将用户最需要的信息迅速返回则更具挑战性.Google用于分辨网页重要性的工具，就是其具有突破性的PageRank（网页级别）技术［1］.

PageRank技术：假设Google数据库中有N（N非常大）个网页.为了描述这些网页之间的关系，定义一个N×N的矩阵G＝｛g ij｝，如果从网页i到网页j有超链接，则令g ij＝1，否则令g ij＝0.显然G是巨大的但非常稀疏的矩阵.记矩阵G的列和以及行和分别是

显然，cj和r i分别表示网页j的链入网页数和网页i的链出网页数.

把所有网页的集合看成随机过程的状态空间，假定上网者浏览网页并选择下一个网页的过程只依赖于当前浏览的网页而与过去浏览过哪些网页无关.那么这一选择过程可以认为是一个有限状态的Markov链.定义矩阵P＝｛p i｝jN×N如下

其中d是阻尼系数，指的是上网者按照网页的实际链接选择下一张网页的可能性，1－d则是上网者随机选择下一张网页的可能性，d取值在［0，1］之间.实际运算中，一般取d＝0.85，P是Markov链的转移概率矩阵，p ij表示从页面i到页面j的转移概率.根据Markov链的性质［2］，有限状态的齐次Markov链，如果对任意i，j∈I，都有p ij＞0，则该Markov链存在平稳分布π＝（π1，π2，…，πN），使得

其中马氏链的平稳分布π表示转移次数趋于无限时各网页被访问的概率的大小，Google将马氏链的平稳分布π定义为各网页的PageRank值.Google公司就是按照这个值的大小对网页进行重要性排序的.π的分量满足方程

从（2）式右侧可以看到，网页i将它的PageRank值分成ri份（它链出的页面数），分别“投票”给它链出的网页.πj为网页j的PageRank值，即网络上所有页面“投票”给网页j的最终值.从上可见，网页的PageRank值本质上就是马氏链的平稳分布.

2.3 数值模拟.

我们在教学过程中给出如下数值模拟：

考虑一个只有6张网页的网络，如图1所示，它的链接矩阵G和转移概率矩阵P如下：

图1 网络结构示意图

由（1）式解线性方程组得平稳分布

这里平稳分布π给出了各网页的PageRank值，见图2.

从上面可以看出，网页的PageRank和得票数不成正比，比如，网页2在‘选举’中只得了一票，但它的PageRank值却高于其它几个得票数为2或3的网页，这是因为它被网页1选中，而网页1的PageRank值很高.被PageRank值高的网页选中的网页，其PageRank值也会高.这样来定义网页的重要程度显然是比较合理的.

图2 网络的PageRank

Google搜索是每位同学所熟知的事情，通过对平稳分布在Google搜索中的应用实例的讲解，既加深了同学们对平稳分布这一概念的理解，也激发了他们对随机过程的学习兴趣.

3 随机过程教学的若干探讨

上述在抽象概念的讲解过程中结合它在交叉学科中的应用的方法还可以在随机过程的整个教学中得到应用.

3.1 其它内容的讲解.

随机过程作为一门理论与实际相结合的学科，其理论体系已得到广泛的应用，如在天气预报、遗传学、传染病问题、排队论、天体物理、化学反应、统计物理、放射性问题、原子反应、生物中的群体生长、信息论、安全科学、人口理论、可靠性、经济数学以及自动控制、无线电技术、计算机科学等很多领域都要以随机过程为基础来构建数学模型.因此我们在讲授中不但注意其数学的严密性，也要结合其应用进行导入式教学，如讲到平稳过程的谱分析时应该讲解它在故障诊断和滤波中的应用，在讲到连续时间马氏链的Chapman－Kolmogorov方程时我们介绍它在推断物种间系统发育树中的应用，在讲到分支过程时我们讲解它在肿瘤突变中的应用，在讲到更新过程时我们讲解它在人口学中的应用等.总之，在讲解与其它学科有关联的相关知识时，应充分体现随机过程的实践性和应用性，结合本学科的前沿技术与发展动向，才能拓宽学生的视野［3］.

3.2 对教师素质的要求.

要实现理论和实际及科技前沿相结合，这对任课教师提出了很高的要求.首先任课教师必须具有比较高的学术水平及科研能力，对随机过程在交叉学科中的应用非常清楚.任课教师除了注重教材以外，还要求任课教师认真阅读相关方向的各种资料，也可以借助于在本学科教师之间开设教学讨论班，以及积极参加与随机过程相关的学术会议等手段不断提高教师的学术水平和教学水平，真正做到师者解惑也.

3.3 教学手段的应用.

当前多媒体教学已经是各大高校里普遍使用并且非常有效的手段，多媒体教学不仅可以为教师加大课堂容量，提高课堂效率，而且可以使教学内容形象化、具体化，使学生的视觉、听觉等多种感官得以充分运用到学习中，从而提高学习效率，优化课堂教学的效果［3］.在随机过程的教学过程中同样应该引入多媒体教学手段，除此之外还应进一步引入网络资源，比如，在平稳分布的讲解过程中，一般教材重点只讲平稳分布的概念和求解方法，要引入平稳过程在交叉学科中的应用，用传统的教学方法很难图文并茂的将理论及应用展示给学生，如讲到google搜索时，如果直接通过网络在搜索引擎中输入关键字，给同学演示google搜索的快速和搜索结果的重要性排序过程，则能起到事半功倍的效果.要在规定的学时内完成教学任务，必须使用现代化多媒体教学手段，才能容纳与交叉学科相关的教学内容.

3.4 开发学生的应用能力.

在教学过程中实现理论与实际相结合，必须要求学生具有“应用意识”［4］.理论固然重要，但是对一个即将走向现代化社会的成员来说，解决实际问题的能力是必不可少的.我们在随机过程的教学中采用导入式的教学方法，对学生将抽象的数学概念与实际应用相结合方面是一个较好的训练，进一步的做法是让学生自己能够自觉选择一些与日常生活、生产或管理相关的例子，运用所学知识和技能进行解决实际问题的实践活动，以便学生毕业后能够很快地把书本知识应用到实际工作当中.

4 小 结

应用随机过程对工科学生而言是一门相对比较难的学科，从而要求任课教师在教学过程中尽量穿插一些它在交叉学科中的应用实例，充分巩固学生对理论知识的理解，并在教学过程中利用现代化教学手段，从而提高课堂效率，优化课堂教学的效果；同时也要求学生在学习过程中具有“应用意识”，主动地把学到的理论知识运用到生活实践之中.只有多方面相互结合，才能在教学过程中收到事半功倍的效果.

［1］Brin S，Page L.The anatomy of a large－scale hypertextual web search engine［J］.Computer Networks and ISDN Systems，1998，30：107－117.

［2］龚光鲁，钱敏平.应用随机过程教程［M］.北京：清华大学出版社，2004.

［3］吕芳，王振辉.关于《应用随机过程》教学的思考［J］.中国科教创新导刊，2009（30）：50－52.

［4］严士健.高师教育改革应该面向21世纪［J］.高等师范教育研究，1998（4）：17－22.

Analyzing the Teaching Process of Stationary Distribution of Markov Chain——on the Teaching of Stochastic Process

LIUXiu－qin，ZHAOJin－ling，FANYu－mei
（School of Mathematics and Physics，University of Science and Technology Beijing 100083，China）

We explain the concept of the stationary distribution of Markov chain in view of the application of the stationary distribution in the Google search technology，and then we give a simple discussion on the teaching of stochastic process.

the teaching of applied stochastic process；stationary distribution of Markov chain；Google searching；PageRank

O211.6

C

1672－1454（2011）04－0199－04

2010－04－16；［修改日期］2011－04－06

北京科技大学教育教学研究立项项目（JY2009Y44）