酒鬼漫步的數(shù)學(xué)——隨機(jī)過(guò)程 | 張?zhí)烊貙?/h3>
2017/08/13
導(dǎo)讀
一個(gè)醉鬼能自己走回家么？
?圖片來(lái)源：pixabay.com
編者按：
前幾篇主要介紹了概率與統(tǒng)計(jì)中的兩個(gè)重要學(xué)派：頻率學(xué)派和貝葉斯學(xué)派，從而引申出了概率與統(tǒng)計(jì)領(lǐng)域最基本的問題：什么是概率、它又從何而來(lái)。
而此篇?jiǎng)t將以概率與統(tǒng)計(jì)中一個(gè)重要的概念——隨機(jī)過(guò)程作為起點(diǎn)，去探討一個(gè)酒鬼回家的可能。
撰文 | 張?zhí)烊?strong style="max-width: 100%; color: rgb(62, 62, 62); font-family: 微軟雅黑; font-size: 16px; text-align: justify; background-color: rgb(255, 255, 255); box-sizing: border-box !important; word-wrap: break-word !important;"> （美國(guó)德州大學(xué)奧斯汀分校理論物理博士）
責(zé)編 | 呂浩然
概率論專欄
2017-03-16 上帝教人擲骰子——“神童”帕斯卡與概率論
2017-03-31 似是而非的答案：概率論悖論
2017-04-18 別相信直覺：概率論幫助偵破“財(cái)務(wù)造假”
2017-05-15 賭徒謬誤：賭博與大數(shù)定律
2017-06-24 無(wú)所不在的概率分布鐘型曲線
2017-07-26 概率之本質(zhì)—從主觀概率到量子貝葉斯
● ● ●
想象在曼哈頓東西南北格點(diǎn)化的街道中有一個(gè)小醉漢，他每次到達(dá)一個(gè)交叉路口時(shí)都會(huì)隨機(jī)選擇前后左右四個(gè)方向其中的一個(gè)，然后繼續(xù)前進(jìn)（或后退）；在走到下一個(gè)路口時(shí)又隨機(jī)選擇一次方向……如此繼續(xù)下去，他所經(jīng)過(guò)的路徑會(huì)具有什么樣的特點(diǎn)呢？
數(shù)學(xué)家們將這樣的問題稱之為“酒鬼漫步”，甚至將酒鬼的路徑抽象為一個(gè)數(shù)學(xué)模型：無(wú)規(guī)行走，或稱隨機(jī)游走（random walk）。而因曼哈頓的酒鬼只能在二維的城市地面上游蕩，所以這也是一種“二維無(wú)規(guī)行走”，見圖1。
?圖1：酒鬼漫步和二維無(wú)規(guī)行走路徑
隨機(jī)過(guò)程與伯努利過(guò)程
無(wú)規(guī)行走是一類隨機(jī)過(guò)程。何謂隨機(jī)過(guò)程？之前我們以丟硬幣為例介紹了隨機(jī)變量，隨機(jī)過(guò)程就是一系列隨機(jī)變量的集合。比如說(shuō)，每丟一次硬幣，便產(chǎn)生一個(gè)隨機(jī)變量X，那么，我們一次又一次地丟下去，便產(chǎn)生出一系列的隨機(jī)變量X1，X2…… Xi ……，酒鬼的漫步也類似，總的路徑是酒鬼多次隨機(jī)選擇行走的所有路徑的集合。隨機(jī)變量序列集合起來(lái)，便形成了“隨機(jī)過(guò)程”。隨機(jī)過(guò)程中的Xi，可看作是時(shí)間 ti 的“函數(shù)”。
與經(jīng)典物理學(xué)類似，物理系統(tǒng)隨時(shí)間演化的過(guò)程，要遵循牛頓物理學(xué)的規(guī)律。隨機(jī)過(guò)程也有它的運(yùn)動(dòng)規(guī)律。但不同的是，隨機(jī)過(guò)程的變量是取值不確定的隨機(jī)變量，這使得隨機(jī)過(guò)程相比于“不隨機(jī)的過(guò)程”更難以處理。
此處還應(yīng)介紹一個(gè)新的定義——伯努利過(guò)程。丟一次硬幣產(chǎn)生一個(gè)取值為1或0的隨機(jī)變量X，那么，接連丟下去產(chǎn)生的隨機(jī)變量的集合就被稱為伯努利過(guò)程。伯努利過(guò)程是一個(gè)時(shí)間離散，取值也離散的隨機(jī)過(guò)程，其中隨機(jī)變量的樣本空間只有兩個(gè)取值：成功（1）、或失敗（0），成功的概率為p。例如，擲一個(gè)6面對(duì)稱的骰子，如果將“3”出現(xiàn)的概率定為成功的話，則多次擲骰子的結(jié)果是一個(gè)p=1/6的伯努利過(guò)程。
馬爾可夫鏈[1]
伯努利過(guò)程比較乏味，因?yàn)榈玫秸娴母怕适莻€(gè)固定值p，每次拋擲的結(jié)果互相獨(dú)立，這種獨(dú)立性是構(gòu)成之前所介紹的“賭徒謬誤”的基礎(chǔ)。
然而，真實(shí)隨機(jī)變量之間，往往存在著互相依賴的關(guān)系。比如說(shuō)，考慮明天北京下雨或天晴的可能性，一般來(lái)說(shuō)與北京今天、昨天的氣候狀況有關(guān)。
?圖2：典型的馬爾可夫過(guò)程
簡(jiǎn)單而言，假設(shè)明天下雨的概率只與今天的天氣有關(guān)，則“雨晴”的轉(zhuǎn)換可以用一個(gè)如圖2a的圖形來(lái)描述。圖中，“雨”和“晴” 兩種狀態(tài)之間被數(shù)條帶箭頭的曲線連接。這些連線表示從今天的狀態(tài)，如何預(yù)測(cè)明天的狀態(tài)。比如說(shuō)，從狀態(tài)“雨”出發(fā)有兩條連線：結(jié)束于狀態(tài)“晴”的右邊那一條標(biāo)上了“0.6”，意思是說(shuō)：“今天雨明天晴的概率是60%”；左邊曲線繞了一圈又返回“雨”，標(biāo)識(shí)0.4，即“明天繼續(xù)下雨的概率是40%”。可以類似地理解從狀態(tài)“晴”出發(fā)的兩條曲線：如果今天晴，那么明天有80%的可能性晴，20%的可能性下雨。
時(shí)間上離散的過(guò)程，也被稱為“鏈”，上述例子是一個(gè)典型的、也是最簡(jiǎn)單的馬爾可夫鏈，它也得名于俄羅斯數(shù)學(xué)家安德烈·馬爾可夫（Andreyevich Markov，1856－1922）。馬爾可夫鏈具有馬爾可夫性質(zhì)，也被稱為“無(wú)記憶性”或“無(wú)后效性”，即下一狀態(tài)的概率分布只由當(dāng)前狀態(tài)決定，與過(guò)去的事件無(wú)關(guān)。反映到上述案例中，明天“晴雨”的概率只與今天的狀態(tài)有關(guān)，而與昨天以及更早之前的氣候均無(wú)關(guān)。
除了用圖形來(lái)表示馬爾可夫鏈之外，“雨晴”變換關(guān)系也可以用圖2b的轉(zhuǎn)換矩陣P來(lái)描述。矩陣中的數(shù)值，表示系統(tǒng)演化“一步”后狀態(tài)之間的轉(zhuǎn)移概率。矩陣表示中的狀態(tài)是一個(gè)矢量，圖2b中，今天的狀態(tài)被表示為一個(gè)分量為0.3和0.7的矢量，明天的狀態(tài)則由P乘以今天之狀態(tài)而得到。
?圖3：時(shí)齊馬爾可夫鏈
值得注意的是，上述矩陣中的轉(zhuǎn)移概率并不隨時(shí)間而變化，即矩陣中的各個(gè)元（0.4, 0.6, 0.2, 0.8）的數(shù)值是固定的，這種馬爾可夫過(guò)程頁(yè)叫做時(shí)齊馬爾可夫過(guò)程。比如說(shuō)，如圖3所示，假設(shè)北京任何一天的“晴雨”狀態(tài)都由前一天的狀態(tài)乘以同樣的轉(zhuǎn)換矩陣P而得到，則這個(gè)過(guò)程是時(shí)齊的。通?？紤]的馬爾可夫過(guò)程，都被假定是“時(shí)齊”的。
除了“時(shí)齊”性之外，人們還對(duì)長(zhǎng)時(shí)間后趨于穩(wěn)定狀態(tài)的馬爾科夫過(guò)程頗為感興趣。
假設(shè)一周內(nèi)的股票市場(chǎng)只用簡(jiǎn)單的3種狀態(tài)表示：牛市、熊市、停滯不前。其轉(zhuǎn)移概率如圖4所示。
?圖4：股票市場(chǎng)的極限概率分布
當(dāng)時(shí)間足夠長(zhǎng)的時(shí)候，這個(gè)馬爾可夫鏈產(chǎn)生的一系列隨機(jī)狀態(tài)趨向一個(gè)極限向量，即圖4中右下角所示的矢量Xlimit =[0.47, 0.3, 0.23]，也就是系統(tǒng)最后的穩(wěn)態(tài)向量。按照這個(gè)特殊的股票市場(chǎng)模型，長(zhǎng)遠(yuǎn)的市場(chǎng)趨勢(shì)趨于穩(wěn)定，即每周的股票情況是：47%的概率是牛市、30%熊市、23%停滯不前。
酒鬼失足、賭徒破產(chǎn)及鳥兒回家
無(wú)規(guī)行走可以看做是馬爾科夫鏈的特例[2]，它的狀態(tài)空間不是像上述拋硬幣等例子中那種由簡(jiǎn)單的幾種有限的基本狀態(tài)構(gòu)成的，而是由無(wú)限延伸的“物理空間”構(gòu)成，這兒的“空間”可以是任意維度的。
那么，為什么說(shuō)酒鬼漫步是馬爾可夫鏈呢？因?yàn)?，醉漢在時(shí)刻 ti+1 的狀態(tài)（即位置）僅由他在時(shí)刻 ti 的狀態(tài)（xi, yi），以及他隨機(jī)選擇的方向所決定，與過(guò)去（ti 之前）走過(guò)的路徑無(wú)關(guān)。
我們?cè)賮?lái)討論一個(gè)“酒鬼掉下懸崖”的趣題。前文曾經(jīng)介紹過(guò)高爾頓釘板實(shí)驗(yàn)，可作為一維無(wú)規(guī)行走的例子。高爾頓釘板雖然貌似一個(gè)二維空間，但因?yàn)樾∏蛟诖怪狈较虻倪\(yùn)動(dòng)并不是隨機(jī)的，而是每次固定向下1格，因此可以視作一個(gè)向下的時(shí)間軸，而水平方向則是一個(gè)一維無(wú)規(guī)行走，見圖5。
?圖5：求一維酒鬼掉下懸崖的概率
在圖5中，釘板的水平方向?yàn)閤軸，垂直向下為時(shí)間軸。懸崖處設(shè)為x=0（圖5左邊虛線）。假設(shè)酒鬼（頂端的小球）起始時(shí)位于x=n的格點(diǎn)位置，即離懸崖有n格之遙。酒鬼朝下漫步過(guò)程中的每一步，向右（x增大）概率為p，向左概率為（1-p）?，F(xiàn)在問：酒鬼從位置n漫游，掉下懸崖的概率是多少（懸崖的位置在x=0處，所以，當(dāng)隨機(jī)變量x的值到達(dá)0，可作為酒鬼掉下了懸崖的判據(jù)）？
先考慮一個(gè)簡(jiǎn)化的具體問題，比如說(shuō)，設(shè)酒鬼漫步時(shí)向右走的概率p=2/3，向左走的概率為q=1-p=1/3，那么，酒鬼從x=1的位置開始漫游掉下懸崖的概率是多少？
也許有人會(huì)很快就得出答案：酒鬼從x=1向左走一步就到了懸崖，而他向左走的概率為1/3。那么，他掉下懸崖的概率不就是1/3嗎？事情并不是那么簡(jiǎn)單。1/3是酒鬼第一步向左走掉下懸崖的概率，但他第一步向右走仍然有可能掉下懸崖，比如說(shuō)，右走一步之后又再左走兩步不也一樣到達(dá)x=0的格點(diǎn)嗎？所以，掉下懸崖的總概率比1/3要大，要加上第一步向右走到了x=2的點(diǎn)但后來(lái)仍然掉下懸崖的概率。
為了更清楚地分析這個(gè)問題，我們將酒鬼從x=1處漫步到x=0處的概率記為P1。這個(gè)概率顯然就是剛才簡(jiǎn)化問題中要求解的：從x=1處開始漫步掉入懸崖的概率。同時(shí)，從這個(gè)問題的平移對(duì)稱性考慮，P1也是酒鬼從任何x=k左移一個(gè)格點(diǎn)，漫步（不管多少步）到達(dá)x=k-1格點(diǎn)位置的概率。需要注意：酒鬼走一步，與他的格點(diǎn)位置移動(dòng)一格是兩碼事，位置從x=k左移到x=k-1，也許要走好幾步，這與兩點(diǎn)之間的“路徑與位移”是一個(gè)道理。
除了P1之外，將從x=2處開始漫步掉入懸崖的概率記為P2=P12 ，x=3處的概率記為P3=P13……以此類推，如剛才所分析的，對(duì)P1可以列出一個(gè)等式：
P1 = 1-p+pP12
其中，p是酒鬼朝懸崖反方向游走的概率。由此可以解出P1 = 1或者P1= (1-p)/p。對(duì)這個(gè)問題有意義的解是P1= (1-p)/p，Pn=P1n 。
當(dāng)p=1/2時(shí)，P1=1，意味著酒鬼最終一定會(huì)掉下懸崖；當(dāng)p<1/2，P1>1，Pn也一樣，但概率最多只能為1。所以，如果酒鬼朝懸崖反方向的概率不足1/2的話，無(wú)論他開始時(shí)距離懸崖多遠(yuǎn)，酒鬼也是肯定要掉下懸崖的；如果p=2/3，算出P1=1/2，Pn=(1/2)n，n越大，即酒鬼初始位置離懸崖越遠(yuǎn)，失足的可能性便越小。
無(wú)規(guī)行走模型的應(yīng)用范圍很廣，酒鬼失足懸崖的問題也有許多不同的故事版本，但描述的數(shù)學(xué)模型基本一致。比如說(shuō)，賭徒破產(chǎn)問題就是其中一例：賭徒在賭場(chǎng)賭博，贏的概率是p，輸?shù)母怕?-p，每次的賭注為1元，假設(shè)賭徒最開始時(shí)有賭金n元，贏了賭金加一元，輸了賭金減一元。問：賭徒輸光的概率是多少？這個(gè)問題與上面解決的酒鬼懸崖問題的數(shù)學(xué)模型完全一樣，賭金的數(shù)目對(duì)應(yīng)于酒鬼漫步中的一維距離x，懸崖位置x=0便對(duì)應(yīng)于賭金輸光賭徒破產(chǎn)。從上面分析可知，即使p=1/2，酒鬼也必定掉下懸崖，即賭徒最終一定破產(chǎn)。
酒鬼失足問題還可以稍加變換構(gòu)成一些新型的趣題。比如說(shuō)，假設(shè)酒鬼的路上兩邊都有懸崖，計(jì)算分別掉到兩邊懸崖的概率；賭博問題上，便相當(dāng)于兩個(gè)賭徒A和B賭博，看誰(shuí)先輸光。
也可以假設(shè)酒鬼的路上根本沒有懸崖，且路的兩頭都可以無(wú)限延伸，酒鬼從自家門口出發(fā)，要你計(jì)算，酒鬼出去漫游之后，最后還能夠回到家的概率等于多少？
美籍匈牙利數(shù)學(xué)家波利亞（George Pólya，1887－1985）認(rèn)真研究了以上所提的“酒鬼回家”問題[3]。
根據(jù)剛才的討論，酒鬼隨機(jī)游走在長(zhǎng)度無(wú)限（一維）沒有懸崖的路上，時(shí)左時(shí)右，但只要時(shí)間足夠長(zhǎng)，他最終總能回到出發(fā)點(diǎn)。因此，最終回家的概率是100% 。二維的情形也類似，只要時(shí)間足夠長(zhǎng)，這個(gè)醉鬼總能回到家，概率仍然是 100% 。波利亞在 1921 年證明了這點(diǎn)，但三維的答案又如何呢？
波利亞令人吃驚地證明了在維數(shù)比2更高的情況下，酒鬼回家的概率遠(yuǎn)小于1！比如，在三維網(wǎng)格中隨機(jī)游走，最終能回到出發(fā)點(diǎn)的概率只有 34% ，這也被稱為波利亞定理（見圖6）。
?圖6：“酒鬼小鳥回家”定理
酒鬼不可能在空中游走，而鳥兒的活動(dòng)空間卻是三維的，因此，美國(guó)日裔數(shù)學(xué)家角谷靜夫（Shizuo Kakutani，1911–2004）將波利亞定理用一句通俗又十分風(fēng)趣的語(yǔ)言來(lái)總結(jié)：喝醉的酒鬼總能找到回家的路，喝醉的小鳥則可能永遠(yuǎn)也回不了家[4]。
無(wú)規(guī)行走也是物理學(xué)中布朗運(yùn)動(dòng)的數(shù)學(xué)模型，欲知詳情，且聽下回分解。
參考文獻(xiàn)：
【1】維基百科：馬爾可夫鏈
https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE
【2】wikipedia：https://en.wikipedia.org/wiki/Random_walk
【3】Finch, S. R. "Pólya's Random Walk Constant." §5.9 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 322-331, 2003.
【4】A joke by Shizuo Kakutani at a UCLA colloquium talk as attributed in Rick Durrett's book Probability:Theory and Examples.
參與討論
0 條評(píng)論
評(píng)論
暫無(wú)評(píng)論內(nèi)容
?圖片來(lái)源：pixabay.com
編者按：
前幾篇主要介紹了概率與統(tǒng)計(jì)中的兩個(gè)重要學(xué)派：頻率學(xué)派和貝葉斯學(xué)派，從而引申出了概率與統(tǒng)計(jì)領(lǐng)域最基本的問題：什么是概率、它又從何而來(lái)。
而此篇?jiǎng)t將以概率與統(tǒng)計(jì)中一個(gè)重要的概念——隨機(jī)過(guò)程作為起點(diǎn)，去探討一個(gè)酒鬼回家的可能。
撰文 | 張?zhí)烊?strong style="max-width: 100%; color: rgb(62, 62, 62); font-family: 微軟雅黑; font-size: 16px; text-align: justify; background-color: rgb(255, 255, 255); box-sizing: border-box !important; word-wrap: break-word !important;"> （美國(guó)德州大學(xué)奧斯汀分校理論物理博士）
責(zé)編 | 呂浩然
概率論專欄
2017-03-16 上帝教人擲骰子——“神童”帕斯卡與概率論
2017-03-31 似是而非的答案：概率論悖論
2017-04-18 別相信直覺：概率論幫助偵破“財(cái)務(wù)造假”
2017-05-15 賭徒謬誤：賭博與大數(shù)定律
2017-06-24 無(wú)所不在的概率分布鐘型曲線
2017-07-26 概率之本質(zhì)—從主觀概率到量子貝葉斯
● ● ●
想象在曼哈頓東西南北格點(diǎn)化的街道中有一個(gè)小醉漢，他每次到達(dá)一個(gè)交叉路口時(shí)都會(huì)隨機(jī)選擇前后左右四個(gè)方向其中的一個(gè)，然后繼續(xù)前進(jìn)（或后退）；在走到下一個(gè)路口時(shí)又隨機(jī)選擇一次方向……如此繼續(xù)下去，他所經(jīng)過(guò)的路徑會(huì)具有什么樣的特點(diǎn)呢？
數(shù)學(xué)家們將這樣的問題稱之為“酒鬼漫步”，甚至將酒鬼的路徑抽象為一個(gè)數(shù)學(xué)模型：無(wú)規(guī)行走，或稱隨機(jī)游走（random walk）。而因曼哈頓的酒鬼只能在二維的城市地面上游蕩，所以這也是一種“二維無(wú)規(guī)行走”，見圖1。
?圖1：酒鬼漫步和二維無(wú)規(guī)行走路徑
隨機(jī)過(guò)程與伯努利過(guò)程
無(wú)規(guī)行走是一類隨機(jī)過(guò)程。何謂隨機(jī)過(guò)程？之前我們以丟硬幣為例介紹了隨機(jī)變量，隨機(jī)過(guò)程就是一系列隨機(jī)變量的集合。比如說(shuō)，每丟一次硬幣，便產(chǎn)生一個(gè)隨機(jī)變量X，那么，我們一次又一次地丟下去，便產(chǎn)生出一系列的隨機(jī)變量X1，X2…… Xi ……，酒鬼的漫步也類似，總的路徑是酒鬼多次隨機(jī)選擇行走的所有路徑的集合。隨機(jī)變量序列集合起來(lái)，便形成了“隨機(jī)過(guò)程”。隨機(jī)過(guò)程中的Xi，可看作是時(shí)間 ti 的“函數(shù)”。
與經(jīng)典物理學(xué)類似，物理系統(tǒng)隨時(shí)間演化的過(guò)程，要遵循牛頓物理學(xué)的規(guī)律。隨機(jī)過(guò)程也有它的運(yùn)動(dòng)規(guī)律。但不同的是，隨機(jī)過(guò)程的變量是取值不確定的隨機(jī)變量，這使得隨機(jī)過(guò)程相比于“不隨機(jī)的過(guò)程”更難以處理。
此處還應(yīng)介紹一個(gè)新的定義——伯努利過(guò)程。丟一次硬幣產(chǎn)生一個(gè)取值為1或0的隨機(jī)變量X，那么，接連丟下去產(chǎn)生的隨機(jī)變量的集合就被稱為伯努利過(guò)程。伯努利過(guò)程是一個(gè)時(shí)間離散，取值也離散的隨機(jī)過(guò)程，其中隨機(jī)變量的樣本空間只有兩個(gè)取值：成功（1）、或失敗（0），成功的概率為p。例如，擲一個(gè)6面對(duì)稱的骰子，如果將“3”出現(xiàn)的概率定為成功的話，則多次擲骰子的結(jié)果是一個(gè)p=1/6的伯努利過(guò)程。
馬爾可夫鏈[1]
伯努利過(guò)程比較乏味，因?yàn)榈玫秸娴母怕适莻€(gè)固定值p，每次拋擲的結(jié)果互相獨(dú)立，這種獨(dú)立性是構(gòu)成之前所介紹的“賭徒謬誤”的基礎(chǔ)。
然而，真實(shí)隨機(jī)變量之間，往往存在著互相依賴的關(guān)系。比如說(shuō)，考慮明天北京下雨或天晴的可能性，一般來(lái)說(shuō)與北京今天、昨天的氣候狀況有關(guān)。
?圖2：典型的馬爾可夫過(guò)程
簡(jiǎn)單而言，假設(shè)明天下雨的概率只與今天的天氣有關(guān)，則“雨晴”的轉(zhuǎn)換可以用一個(gè)如圖2a的圖形來(lái)描述。圖中，“雨”和“晴” 兩種狀態(tài)之間被數(shù)條帶箭頭的曲線連接。這些連線表示從今天的狀態(tài)，如何預(yù)測(cè)明天的狀態(tài)。比如說(shuō)，從狀態(tài)“雨”出發(fā)有兩條連線：結(jié)束于狀態(tài)“晴”的右邊那一條標(biāo)上了“0.6”，意思是說(shuō)：“今天雨明天晴的概率是60%”；左邊曲線繞了一圈又返回“雨”，標(biāo)識(shí)0.4，即“明天繼續(xù)下雨的概率是40%”。可以類似地理解從狀態(tài)“晴”出發(fā)的兩條曲線：如果今天晴，那么明天有80%的可能性晴，20%的可能性下雨。
時(shí)間上離散的過(guò)程，也被稱為“鏈”，上述例子是一個(gè)典型的、也是最簡(jiǎn)單的馬爾可夫鏈，它也得名于俄羅斯數(shù)學(xué)家安德烈·馬爾可夫（Andreyevich Markov，1856－1922）。馬爾可夫鏈具有馬爾可夫性質(zhì)，也被稱為“無(wú)記憶性”或“無(wú)后效性”，即下一狀態(tài)的概率分布只由當(dāng)前狀態(tài)決定，與過(guò)去的事件無(wú)關(guān)。反映到上述案例中，明天“晴雨”的概率只與今天的狀態(tài)有關(guān)，而與昨天以及更早之前的氣候均無(wú)關(guān)。
除了用圖形來(lái)表示馬爾可夫鏈之外，“雨晴”變換關(guān)系也可以用圖2b的轉(zhuǎn)換矩陣P來(lái)描述。矩陣中的數(shù)值，表示系統(tǒng)演化“一步”后狀態(tài)之間的轉(zhuǎn)移概率。矩陣表示中的狀態(tài)是一個(gè)矢量，圖2b中，今天的狀態(tài)被表示為一個(gè)分量為0.3和0.7的矢量，明天的狀態(tài)則由P乘以今天之狀態(tài)而得到。
?圖3：時(shí)齊馬爾可夫鏈
值得注意的是，上述矩陣中的轉(zhuǎn)移概率并不隨時(shí)間而變化，即矩陣中的各個(gè)元（0.4, 0.6, 0.2, 0.8）的數(shù)值是固定的，這種馬爾可夫過(guò)程頁(yè)叫做時(shí)齊馬爾可夫過(guò)程。比如說(shuō)，如圖3所示，假設(shè)北京任何一天的“晴雨”狀態(tài)都由前一天的狀態(tài)乘以同樣的轉(zhuǎn)換矩陣P而得到，則這個(gè)過(guò)程是時(shí)齊的。通?？紤]的馬爾可夫過(guò)程，都被假定是“時(shí)齊”的。
除了“時(shí)齊”性之外，人們還對(duì)長(zhǎng)時(shí)間后趨于穩(wěn)定狀態(tài)的馬爾科夫過(guò)程頗為感興趣。
假設(shè)一周內(nèi)的股票市場(chǎng)只用簡(jiǎn)單的3種狀態(tài)表示：牛市、熊市、停滯不前。其轉(zhuǎn)移概率如圖4所示。
?圖4：股票市場(chǎng)的極限概率分布
當(dāng)時(shí)間足夠長(zhǎng)的時(shí)候，這個(gè)馬爾可夫鏈產(chǎn)生的一系列隨機(jī)狀態(tài)趨向一個(gè)極限向量，即圖4中右下角所示的矢量Xlimit =[0.47, 0.3, 0.23]，也就是系統(tǒng)最后的穩(wěn)態(tài)向量。按照這個(gè)特殊的股票市場(chǎng)模型，長(zhǎng)遠(yuǎn)的市場(chǎng)趨勢(shì)趨于穩(wěn)定，即每周的股票情況是：47%的概率是牛市、30%熊市、23%停滯不前。
酒鬼失足、賭徒破產(chǎn)及鳥兒回家
無(wú)規(guī)行走可以看做是馬爾科夫鏈的特例[2]，它的狀態(tài)空間不是像上述拋硬幣等例子中那種由簡(jiǎn)單的幾種有限的基本狀態(tài)構(gòu)成的，而是由無(wú)限延伸的“物理空間”構(gòu)成，這兒的“空間”可以是任意維度的。
那么，為什么說(shuō)酒鬼漫步是馬爾可夫鏈呢？因?yàn)?，醉漢在時(shí)刻 ti+1 的狀態(tài)（即位置）僅由他在時(shí)刻 ti 的狀態(tài)（xi, yi），以及他隨機(jī)選擇的方向所決定，與過(guò)去（ti 之前）走過(guò)的路徑無(wú)關(guān)。
我們?cè)賮?lái)討論一個(gè)“酒鬼掉下懸崖”的趣題。前文曾經(jīng)介紹過(guò)高爾頓釘板實(shí)驗(yàn)，可作為一維無(wú)規(guī)行走的例子。高爾頓釘板雖然貌似一個(gè)二維空間，但因?yàn)樾∏蛟诖怪狈较虻倪\(yùn)動(dòng)并不是隨機(jī)的，而是每次固定向下1格，因此可以視作一個(gè)向下的時(shí)間軸，而水平方向則是一個(gè)一維無(wú)規(guī)行走，見圖5。
?圖5：求一維酒鬼掉下懸崖的概率
在圖5中，釘板的水平方向?yàn)閤軸，垂直向下為時(shí)間軸。懸崖處設(shè)為x=0（圖5左邊虛線）。假設(shè)酒鬼（頂端的小球）起始時(shí)位于x=n的格點(diǎn)位置，即離懸崖有n格之遙。酒鬼朝下漫步過(guò)程中的每一步，向右（x增大）概率為p，向左概率為（1-p）?，F(xiàn)在問：酒鬼從位置n漫游，掉下懸崖的概率是多少（懸崖的位置在x=0處，所以，當(dāng)隨機(jī)變量x的值到達(dá)0，可作為酒鬼掉下了懸崖的判據(jù)）？
先考慮一個(gè)簡(jiǎn)化的具體問題，比如說(shuō)，設(shè)酒鬼漫步時(shí)向右走的概率p=2/3，向左走的概率為q=1-p=1/3，那么，酒鬼從x=1的位置開始漫游掉下懸崖的概率是多少？
也許有人會(huì)很快就得出答案：酒鬼從x=1向左走一步就到了懸崖，而他向左走的概率為1/3。那么，他掉下懸崖的概率不就是1/3嗎？事情并不是那么簡(jiǎn)單。1/3是酒鬼第一步向左走掉下懸崖的概率，但他第一步向右走仍然有可能掉下懸崖，比如說(shuō)，右走一步之后又再左走兩步不也一樣到達(dá)x=0的格點(diǎn)嗎？所以，掉下懸崖的總概率比1/3要大，要加上第一步向右走到了x=2的點(diǎn)但后來(lái)仍然掉下懸崖的概率。
為了更清楚地分析這個(gè)問題，我們將酒鬼從x=1處漫步到x=0處的概率記為P1。這個(gè)概率顯然就是剛才簡(jiǎn)化問題中要求解的：從x=1處開始漫步掉入懸崖的概率。同時(shí)，從這個(gè)問題的平移對(duì)稱性考慮，P1也是酒鬼從任何x=k左移一個(gè)格點(diǎn)，漫步（不管多少步）到達(dá)x=k-1格點(diǎn)位置的概率。需要注意：酒鬼走一步，與他的格點(diǎn)位置移動(dòng)一格是兩碼事，位置從x=k左移到x=k-1，也許要走好幾步，這與兩點(diǎn)之間的“路徑與位移”是一個(gè)道理。
除了P1之外，將從x=2處開始漫步掉入懸崖的概率記為P2=P12 ，x=3處的概率記為P3=P13……以此類推，如剛才所分析的，對(duì)P1可以列出一個(gè)等式：
P1 = 1-p+pP12
其中，p是酒鬼朝懸崖反方向游走的概率。由此可以解出P1 = 1或者P1= (1-p)/p。對(duì)這個(gè)問題有意義的解是P1= (1-p)/p，Pn=P1n 。
當(dāng)p=1/2時(shí)，P1=1，意味著酒鬼最終一定會(huì)掉下懸崖；當(dāng)p<1/2，P1>1，Pn也一樣，但概率最多只能為1。所以，如果酒鬼朝懸崖反方向的概率不足1/2的話，無(wú)論他開始時(shí)距離懸崖多遠(yuǎn)，酒鬼也是肯定要掉下懸崖的；如果p=2/3，算出P1=1/2，Pn=(1/2)n，n越大，即酒鬼初始位置離懸崖越遠(yuǎn)，失足的可能性便越小。
無(wú)規(guī)行走模型的應(yīng)用范圍很廣，酒鬼失足懸崖的問題也有許多不同的故事版本，但描述的數(shù)學(xué)模型基本一致。比如說(shuō)，賭徒破產(chǎn)問題就是其中一例：賭徒在賭場(chǎng)賭博，贏的概率是p，輸?shù)母怕?-p，每次的賭注為1元，假設(shè)賭徒最開始時(shí)有賭金n元，贏了賭金加一元，輸了賭金減一元。問：賭徒輸光的概率是多少？這個(gè)問題與上面解決的酒鬼懸崖問題的數(shù)學(xué)模型完全一樣，賭金的數(shù)目對(duì)應(yīng)于酒鬼漫步中的一維距離x，懸崖位置x=0便對(duì)應(yīng)于賭金輸光賭徒破產(chǎn)。從上面分析可知，即使p=1/2，酒鬼也必定掉下懸崖，即賭徒最終一定破產(chǎn)。
酒鬼失足問題還可以稍加變換構(gòu)成一些新型的趣題。比如說(shuō)，假設(shè)酒鬼的路上兩邊都有懸崖，計(jì)算分別掉到兩邊懸崖的概率；賭博問題上，便相當(dāng)于兩個(gè)賭徒A和B賭博，看誰(shuí)先輸光。
也可以假設(shè)酒鬼的路上根本沒有懸崖，且路的兩頭都可以無(wú)限延伸，酒鬼從自家門口出發(fā)，要你計(jì)算，酒鬼出去漫游之后，最后還能夠回到家的概率等于多少？
美籍匈牙利數(shù)學(xué)家波利亞（George Pólya，1887－1985）認(rèn)真研究了以上所提的“酒鬼回家”問題[3]。
根據(jù)剛才的討論，酒鬼隨機(jī)游走在長(zhǎng)度無(wú)限（一維）沒有懸崖的路上，時(shí)左時(shí)右，但只要時(shí)間足夠長(zhǎng)，他最終總能回到出發(fā)點(diǎn)。因此，最終回家的概率是100% 。二維的情形也類似，只要時(shí)間足夠長(zhǎng)，這個(gè)醉鬼總能回到家，概率仍然是 100% 。波利亞在 1921 年證明了這點(diǎn)，但三維的答案又如何呢？
波利亞令人吃驚地證明了在維數(shù)比2更高的情況下，酒鬼回家的概率遠(yuǎn)小于1！比如，在三維網(wǎng)格中隨機(jī)游走，最終能回到出發(fā)點(diǎn)的概率只有 34% ，這也被稱為波利亞定理（見圖6）。
?圖6：“酒鬼小鳥回家”定理
酒鬼不可能在空中游走，而鳥兒的活動(dòng)空間卻是三維的，因此，美國(guó)日裔數(shù)學(xué)家角谷靜夫（Shizuo Kakutani，1911–2004）將波利亞定理用一句通俗又十分風(fēng)趣的語(yǔ)言來(lái)總結(jié)：喝醉的酒鬼總能找到回家的路，喝醉的小鳥則可能永遠(yuǎn)也回不了家[4]。
無(wú)規(guī)行走也是物理學(xué)中布朗運(yùn)動(dòng)的數(shù)學(xué)模型，欲知詳情，且聽下回分解。
參考文獻(xiàn)：
【1】維基百科：馬爾可夫鏈
https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE
【2】wikipedia：https://en.wikipedia.org/wiki/Random_walk
【3】Finch, S. R. "Pólya's Random Walk Constant." §5.9 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 322-331, 2003.
【4】A joke by Shizuo Kakutani at a UCLA colloquium talk as attributed in Rick Durrett's book Probability:Theory and Examples.
