剖析馬氏鏈平穩(wěn)分布的講解
——談《應(yīng)用隨機過程》教學

劉秀芹，趙金玲，范玉妹

（北京科技大學數(shù)理學院數(shù)力系，北京 100083）

剖析馬氏鏈平穩(wěn)分布的講解
——談《應(yīng)用隨機過程》教學

劉秀芹，趙金玲，范玉妹

（北京科技大學數(shù)理學院數(shù)力系，北京 100083）

通過平穩(wěn)分布在Google搜索技術(shù)中的應(yīng)用角度講解馬氏鏈的平穩(wěn)分布的概念，并在此基礎(chǔ)上對應(yīng)用隨機過程的教學做了粗淺的探討.

應(yīng)用隨機過程教學；馬氏鏈的平穩(wěn)分布；Google搜索；PageRank

1 引 言

應(yīng)用隨機過程是一門以概率論和復(fù)變函數(shù)為基礎(chǔ)的面向理工科高年級學生的課程，它的理論在物理、生物、工程、經(jīng)濟和管理等方面都有廣泛的應(yīng)用，隨機過程已經(jīng)成為近代科技工作者必須掌握的一個理論工具.隨機過程是研究隨機現(xiàn)象的變化過程的數(shù)學學科，也是一門接近現(xiàn)實生活的理論與實際相結(jié)合的課程，但是對工科學生來說隨機過程是一門相對比較難的課程.如何使學生既能準確掌握其中的理論知識，又能把理論應(yīng)用于實際是大多數(shù)教隨機過程的教師在教學過程中追求的目標.本文通過對隨機過程中馬氏鏈的平穩(wěn)分布概念的講解，擬對應(yīng)用隨機過程的教學作一些粗淺的探討.

2 平穩(wěn)分布的概念及其在Google搜索技術(shù)中的應(yīng)用

2.1 馬氏鏈的平穩(wěn)分布的定義.

馬氏鏈的平穩(wěn)分布定義：設(shè)｛X n，n≥1｝是齊次馬爾可夫鏈，狀態(tài)空間為I，轉(zhuǎn)移概率為p ij，稱概率分布｛πj，j∈I｝為馬爾可夫鏈的平穩(wěn)分布，若它滿足

由上述定義可知，只要知道馬氏鏈的一步轉(zhuǎn)移概率矩陣，即可通過求解上面的線性方程組得到它的平穩(wěn)分布.在應(yīng)用隨機過程的教材中，一般只有平穩(wěn)分布的定義以及平穩(wěn)分布的求解方法兩部分內(nèi)容，對于平穩(wěn)分布在實際中的應(yīng)用涉及的很少.

僅從平穩(wěn)分布的定義來看，大多數(shù)同學對它不會有什么深刻的認識，可能像其它一些數(shù)學名詞一樣匆匆劃過腦海，不留任何痕跡.而馬氏鏈的平穩(wěn)分布是隨機過程這門課中非常重要的內(nèi)容，并且它在其它許多交叉學科中有著廣泛的應(yīng)用，為此，我們在教學過程中采用先引入平穩(wěn)分布的抽象概念，然后結(jié)合平穩(wěn)分布在實際中的應(yīng)用來理解抽象概念的導(dǎo)入式教學方法.

2.2 平穩(wěn)分布應(yīng)用.

平穩(wěn)分布與Google搜索.

提出問題：Google搜索是人們最常用的搜索引擎之一，若我們在搜索引擎中輸入一個關(guān)鍵詞，Google就會非常迅速地（有的連0.01秒都不到）在窗口中輸出大量的結(jié)果（有時有上千萬條結(jié)果）.一般情況下，用戶所關(guān)心的信息大多在前面幾條結(jié)果中就能獲得.那么，Google是如何實現(xiàn)快速的搜索，如何合理定義網(wǎng)頁的重要性的呢？

近年來，網(wǎng)絡(luò)信息在不斷突飛猛進地增長.在海量的信息中完成搜索自然不易，但采用適當?shù)姆绞絹砜坍嬀W(wǎng)頁的重要性，從而將用戶最需要的信息迅速返回則更具挑戰(zhàn)性.Google用于分辨網(wǎng)頁重要性的工具，就是其具有突破性的PageRank（網(wǎng)頁級別）技術(shù)［1］.

PageRank技術(shù)：假設(shè)Google數(shù)據(jù)庫中有N（N非常大）個網(wǎng)頁.為了描述這些網(wǎng)頁之間的關(guān)系，定義一個N×N的矩陣G＝｛g ij｝，如果從網(wǎng)頁i到網(wǎng)頁j有超鏈接，則令g ij＝1，否則令g ij＝0.顯然G是巨大的但非常稀疏的矩陣.記矩陣G的列和以及行和分別是

顯然，cj和r i分別表示網(wǎng)頁j的鏈入網(wǎng)頁數(shù)和網(wǎng)頁i的鏈出網(wǎng)頁數(shù).

把所有網(wǎng)頁的集合看成隨機過程的狀態(tài)空間，假定上網(wǎng)者瀏覽網(wǎng)頁并選擇下一個網(wǎng)頁的過程只依賴于當前瀏覽的網(wǎng)頁而與過去瀏覽過哪些網(wǎng)頁無關(guān).那么這一選擇過程可以認為是一個有限狀態(tài)的Markov鏈.定義矩陣P＝｛p i｝jN×N如下

其中d是阻尼系數(shù)，指的是上網(wǎng)者按照網(wǎng)頁的實際鏈接選擇下一張網(wǎng)頁的可能性，1－d則是上網(wǎng)者隨機選擇下一張網(wǎng)頁的可能性，d取值在［0，1］之間.實際運算中，一般取d＝0.85，P是Markov鏈的轉(zhuǎn)移概率矩陣，p ij表示從頁面i到頁面j的轉(zhuǎn)移概率.根據(jù)Markov鏈的性質(zhì)［2］，有限狀態(tài)的齊次Markov鏈，如果對任意i，j∈I，都有p ij＞0，則該Markov鏈存在平穩(wěn)分布π＝（π1，π2，…，πN），使得

其中馬氏鏈的平穩(wěn)分布π表示轉(zhuǎn)移次數(shù)趨于無限時各網(wǎng)頁被訪問的概率的大小，Google將馬氏鏈的平穩(wěn)分布π定義為各網(wǎng)頁的PageRank值.Google公司就是按照這個值的大小對網(wǎng)頁進行重要性排序的.π的分量滿足方程

從（2）式右側(cè)可以看到，網(wǎng)頁i將它的PageRank值分成ri份（它鏈出的頁面數(shù)），分別“投票”給它鏈出的網(wǎng)頁.πj為網(wǎng)頁j的PageRank值，即網(wǎng)絡(luò)上所有頁面“投票”給網(wǎng)頁j的最終值.從上可見，網(wǎng)頁的PageRank值本質(zhì)上就是馬氏鏈的平穩(wěn)分布.

2.3 數(shù)值模擬.

我們在教學過程中給出如下數(shù)值模擬：

考慮一個只有6張網(wǎng)頁的網(wǎng)絡(luò)，如圖1所示，它的鏈接矩陣G和轉(zhuǎn)移概率矩陣P如下：

圖1 網(wǎng)絡(luò)結(jié)構(gòu)示意圖

由（1）式解線性方程組得平穩(wěn)分布

這里平穩(wěn)分布π給出了各網(wǎng)頁的PageRank值，見圖2.

從上面可以看出，網(wǎng)頁的PageRank和得票數(shù)不成正比，比如，網(wǎng)頁2在‘選舉’中只得了一票，但它的PageRank值卻高于其它幾個得票數(shù)為2或3的網(wǎng)頁，這是因為它被網(wǎng)頁1選中，而網(wǎng)頁1的PageRank值很高.被PageRank值高的網(wǎng)頁選中的網(wǎng)頁，其PageRank值也會高.這樣來定義網(wǎng)頁的重要程度顯然是比較合理的.

圖2 網(wǎng)絡(luò)的PageRank

Google搜索是每位同學所熟知的事情，通過對平穩(wěn)分布在Google搜索中的應(yīng)用實例的講解，既加深了同學們對平穩(wěn)分布這一概念的理解，也激發(fā)了他們對隨機過程的學習興趣.

3 隨機過程教學的若干探討

上述在抽象概念的講解過程中結(jié)合它在交叉學科中的應(yīng)用的方法還可以在隨機過程的整個教學中得到應(yīng)用.

3.1 其它內(nèi)容的講解.

隨機過程作為一門理論與實際相結(jié)合的學科，其理論體系已得到廣泛的應(yīng)用，如在天氣預(yù)報、遺傳學、傳染病問題、排隊論、天體物理、化學反應(yīng)、統(tǒng)計物理、放射性問題、原子反應(yīng)、生物中的群體生長、信息論、安全科學、人口理論、可靠性、經(jīng)濟數(shù)學以及自動控制、無線電技術(shù)、計算機科學等很多領(lǐng)域都要以隨機過程為基礎(chǔ)來構(gòu)建數(shù)學模型.因此我們在講授中不但注意其數(shù)學的嚴密性，也要結(jié)合其應(yīng)用進行導(dǎo)入式教學，如講到平穩(wěn)過程的譜分析時應(yīng)該講解它在故障診斷和濾波中的應(yīng)用，在講到連續(xù)時間馬氏鏈的Chapman－Kolmogorov方程時我們介紹它在推斷物種間系統(tǒng)發(fā)育樹中的應(yīng)用，在講到分支過程時我們講解它在腫瘤突變中的應(yīng)用，在講到更新過程時我們講解它在人口學中的應(yīng)用等.總之，在講解與其它學科有關(guān)聯(lián)的相關(guān)知識時，應(yīng)充分體現(xiàn)隨機過程的實踐性和應(yīng)用性，結(jié)合本學科的前沿技術(shù)與發(fā)展動向，才能拓寬學生的視野［3］.

3.2 對教師素質(zhì)的要求.

要實現(xiàn)理論和實際及科技前沿相結(jié)合，這對任課教師提出了很高的要求.首先任課教師必須具有比較高的學術(shù)水平及科研能力，對隨機過程在交叉學科中的應(yīng)用非常清楚.任課教師除了注重教材以外，還要求任課教師認真閱讀相關(guān)方向的各種資料，也可以借助于在本學科教師之間開設(shè)教學討論班，以及積極參加與隨機過程相關(guān)的學術(shù)會議等手段不斷提高教師的學術(shù)水平和教學水平，真正做到師者解惑也.

3.3 教學手段的應(yīng)用.

當前多媒體教學已經(jīng)是各大高校里普遍使用并且非常有效的手段，多媒體教學不僅可以為教師加大課堂容量，提高課堂效率，而且可以使教學內(nèi)容形象化、具體化，使學生的視覺、聽覺等多種感官得以充分運用到學習中，從而提高學習效率，優(yōu)化課堂教學的效果［3］.在隨機過程的教學過程中同樣應(yīng)該引入多媒體教學手段，除此之外還應(yīng)進一步引入網(wǎng)絡(luò)資源，比如，在平穩(wěn)分布的講解過程中，一般教材重點只講平穩(wěn)分布的概念和求解方法，要引入平穩(wěn)過程在交叉學科中的應(yīng)用，用傳統(tǒng)的教學方法很難圖文并茂的將理論及應(yīng)用展示給學生，如講到google搜索時，如果直接通過網(wǎng)絡(luò)在搜索引擎中輸入關(guān)鍵字，給同學演示google搜索的快速和搜索結(jié)果的重要性排序過程，則能起到事半功倍的效果.要在規(guī)定的學時內(nèi)完成教學任務(wù)，必須使用現(xiàn)代化多媒體教學手段，才能容納與交叉學科相關(guān)的教學內(nèi)容.

3.4 開發(fā)學生的應(yīng)用能力.

在教學過程中實現(xiàn)理論與實際相結(jié)合，必須要求學生具有“應(yīng)用意識”［4］.理論固然重要，但是對一個即將走向現(xiàn)代化社會的成員來說，解決實際問題的能力是必不可少的.我們在隨機過程的教學中采用導(dǎo)入式的教學方法，對學生將抽象的數(shù)學概念與實際應(yīng)用相結(jié)合方面是一個較好的訓(xùn)練，進一步的做法是讓學生自己能夠自覺選擇一些與日常生活、生產(chǎn)或管理相關(guān)的例子，運用所學知識和技能進行解決實際問題的實踐活動，以便學生畢業(yè)后能夠很快地把書本知識應(yīng)用到實際工作當中.

4 小 結(jié)

應(yīng)用隨機過程對工科學生而言是一門相對比較難的學科，從而要求任課教師在教學過程中盡量穿插一些它在交叉學科中的應(yīng)用實例，充分鞏固學生對理論知識的理解，并在教學過程中利用現(xiàn)代化教學手段，從而提高課堂效率，優(yōu)化課堂教學的效果；同時也要求學生在學習過程中具有“應(yīng)用意識”，主動地把學到的理論知識運用到生活實踐之中.只有多方面相互結(jié)合，才能在教學過程中收到事半功倍的效果.

［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］龔光魯，錢敏平.應(yīng)用隨機過程教程［M］.北京：清華大學出版社，2004.

［3］呂芳，王振輝.關(guān)于《應(yīng)用隨機過程》教學的思考［J］.中國科教創(chuàng)新導(dǎo)刊，2009（30）：50－52.

［4］嚴士健.高師教育改革應(yīng)該面向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，F(xiàn)ANYu－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）