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