波利亞的醉漢，及「以概率1」

01-29

這次手繪題圖！——感謝 @尤可幫我處理圖片去噪。

波利亞（George Polya）在 1921 年發表的論文「Pólya G. über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Stra?ennetz[J]. Mathematische Annalen, 1921, 84(1-2):149-160.」的原文，然而，這我哪兒看的懂啊啊啊啊啊啊啊——（桌子乖，不要跑，╰(●』?』●)╮，讓我掀一個的！！）

而且，百度翻譯你過來，我保證不打你，我就是想問問你，你翻譯的這是啥啊——

還是用谷歌翻譯吧——

其實這個問題我很久之前就聽到過，而直到這幾天想到要談一下「以概率1」才決定親手算一下。

問題描述：

現在考慮一個喝醉的酒鬼，他走出家門在一條足夠長的筆直街道上隨機遊走。他每一步都以概率1/2選擇向東走1米，以概率1/2選擇向西走1米（畢竟喝醉了）。假設他只要沒回到家門前，就會按照這種方式無限地走下去。請問，他最終能回到家門口的概率是多少？

答案是驚人的「1」！

使用格路模型的一個計算方法：

先說幾個事兒——

只考慮「一半」情形，就是假設第1步必定是往右（東）走的。剩下一半情形是對稱的，而後原問題的概率就等於這限定了第一步的問題的概率。
很容易知道，必定是走了偶數步後才有可能正好在家門口。
對於 $ngeq1$ ，定義 $S(n)$ 為經過 $2n$ 步才第一次回到家門口的「走路方案數」，例如 $S(1)=1$ （右左）、 $S(2)=1$ （右右左左）、 $S(3)=2$ （右右右左左左、右右左右左左）。

如果將往左（西）走改為往上走，那麼醉漢的隨機游步就相當於在下面的格點圖中，從 $(1,0)$ 出發，每次等概率地向上走1格或者向右走1格。

而回到家門前就相當於走到了直線 $y=x$ 上。

經過 $2n$ 步才第一次回到家門口就相當於從 $left(1,0 right)$ 走到 $(n,n-1)$ 而且不走到直線 $y=x$ 上，最後再向上走一格。例如下圖。

有如下組合數學結果：

格點圖中每次向上一格或者向右一格，從 $(1,0)$ 走到 $(m,n)$ （這裡有 $m>n$ ）而不走到直線 $y=x$ 上的方法數是 $frac{(m+n-1)!}{m!n!}(m-n)$ 。於是從 $(1,0)$ 走到 $(n,n-1)$ 而不走到直線 $y=x$ 的方法數是 $frac{(2n-2)!}{n!(n-1)!}={frac {1}{n}}{2n-2 choose {n-1}}=C_{n-1}$ 。（參看「格路問題」）
在0附近， $sum _{n=0}^{infty }C_{n}x^{n}=frac {1-{sqrt {1-4x}}}{2x}$ 。（參看卡特蘭數（Catalan number）（二））

於是，在確定第一步的走法後，經過 $2n$ 步才第一次回到家門口的概率是 $C_{n-1}timesleft(frac{1}{2} right)^{2n-1}=frac{1}{2}times C_{n-1}timesleft(frac{1}{4} right)^{n-1}$ 。

對所有的正整數 $n$ 求和就得到他最終能回到家門口的概率是 $begin{equation*} begin{split} sum_{n=1}^infty left( C_{n-1}timesleft(frac{1}{2} right)^{2n-1} right)&=&frac{1}{2}sum_{n=1}^{infty}left( C_{n-1}timesleft(frac{1}{4} right)^{n-1} right) &=& frac{1}{2}sum_{n=0}^{infty}left( C_{n}timesleft(frac{1}{4} right)^{n} right) &=&frac {1-{sqrt {1-4timesfrac{1}{4}}}}{2timesfrac{1}{4}}=1 end{split} end{equation*}$

這樣就證明了結論。

2維情況：假設城市的街道呈網格狀分布，他每走到一個十字路口，都會等概率地向東、南、西、北任意走一格，那麼他最終能回到家門口的概率還是1。

3維情況，他最終能回到家門口的概率只是0.34。

之後隨著維度增加，回到出發點的概率變得越來越低：

（可參看：「喝醉的酒鬼總能找到回家的路，喝醉的小鳥則可能永遠也回不了家」具體是什麼定理？）

下面要說的問題是：明明他可以一直往東頭也不回地走下去的！為什麼他最終能回到家門口的概率是「1」？

換言之，什麼叫做他可以「以概率1（with probability one）」回到家？

這是因為——概率1不等於必然，概率0也不等於不可能。

而要解釋這件事，就得說說什麼是「概率」了——不過我也只想粗略地大概說說。

柯爾莫哥洛夫（Andrey Kolmogorov）1933年在著作《概率論基礎》（Foundations of the Theory of Probability）中第一次給出了概率的測度論式的定義和一套嚴密的公理體系。主要就是現在大學工科課程中所說的非負性、規範性、可列可加性（我始終十分懷疑學生對這一條公理的接受和理解的能力水平）。

勒貝格測度（Lebesgue measure），在行列式就是體積/面積？——（三）裡面提過一次；應該說概率和它在規範性上有所不同，而且不要求平移不變性，但可以從直觀上近似地理解。

可以粗略而模糊地認為勒貝格測度類似於「長度/面積/體積」，例如區間 $(0,1)$ 和 $[0,1]$ 的測度都是1，因為「0」和「1」的「長度」（測度）都是0，所以 $(0,1)$ 的長度加上兩個0就構成了 $[0,1]$ 的長度。用測度的語言就是： $mu({0})=mu({1})=0$ ，由測度的可列可加性有 $mu({0})+mu({1})+mu((0,1))=mu({[0,1]})=1$ 。

（這種情況我不建議用「滄海一粟」來形容，因為無論「滄海」還是「粟」，都是有非零測度的。）

所以回到概率1，概率為1隻是概率空間中那個事件的「測度」（粗略講就是集合的一個大小）和樣本空間的「測度」（樣本空間這個集合的一個大小）是一樣大的。但是可能是不同的集合，比如區間 $(0,1)$ 和 $[0,1]$ （是的，的確有些集合和自己的子集是「一樣大」的；此外，我真覺得我自己啰嗦(ｕ◇ｕ〃) ）

而之所以我會由想到「以概率1」而聊到「波利亞的醉漢」，其實是因為我想拋出如下話題：

在開區間 $(0,1)$ 中，任選一個點，雖然區間中的有理數

有無窮多個，
「到處都是」（處處稠密），

然而，你選中的這個點是無理數的概率是1。

而後，於是我終將開始談及我一直想說的，「實數是什麼」！——敬請期待（我不懶的時候一定寫）！！