一枚硬幣，一步路：建構漫步
在前兩篇裡，你認識了隨機過程的概念——一整族以時間為指標的隨機變數——也學會了讀它的樣本路徑，也就是當你讓隨機性實際跑一次時，所觀察到的那條曲折的線。[[simple-random-walk|簡單隨機漫步]]是最乾淨不過的例子，也是接下來這一整階段都該牢記在心的那一個。配方簡單到近乎欺人：從位置 0 出發，時鐘每跳一下就擲一枚公正硬幣。正面，走 +1;反面，走 -1。你走了 n 步之後的位置，就是你最終落腳的地方。
讓我們把它精確寫下，好用它來計算。令 X_1, X_2, X_3, ... 為各個步伐，每一步都是一次擲幣，以各 1/2 的機率取 +1 或 -1,而且彼此互相獨立。走了 n 步之後的位置，就是這些步伐的累加和 S_n = X_1 + X_2 + ... + X_n,並依慣例令 S_0 = 0。整個過程就是序列 S_0, S_1, S_2, ...——一個部分和過程。接下來漫步的每一個性質,其實都是這些不斷累積的和的性質。
step X_k : +1 with prob 1/2 (heads)
-1 with prob 1/2 (tails)
position after n steps:
S_0 = 0, S_n = X_1 + X_2 + ... + X_n
E[X_k] = 0, Var(X_k) = 1為什麼它具有獨立、平穩的增量
在第 2 篇裡,你認識了一個過程可能擁有的兩份結構性禮物:[[independent-stationary-increments|獨立且平穩的增量]]。隨機漫步兩者兼具,而看清它「為何」如此,正是理解它的核心。增量不過就是某段時間內的位移:從第 m 步到第 n 步,增量是 S_n - S_m = X_(m+1) + ... + X_n。由於這個和只牽涉到時刻 m 之後的擲幣,它與更早的增量(例如 S_m - S_0)完全不共用任何一次擲幣。互不相交的獨立擲幣彼此獨立——所以在不重疊的時間窗上的增量是相互獨立的。未來的跳躍對過去的跳躍一無所知。
平穩增量的意思是:一次跳躍的分布只取決於跳了多長,而與它從何時開始無關。增量 S_(m+k) - S_m 永遠是恰好 k 次公正 +/-1 擲幣的和,不論 m 是 0 還是 1000——而既然所有擲幣都同分布,這個和的分布就與 m 無關。所以一段 10 步的跳躍,無論發生在最開頭、還是在一百萬步之後,看起來在統計上都一模一樣。這兩個性質合在一起,正是使這個漫步成為「積木」的原因:長的路段可以由短的、可互換的、獨立的小塊拼接而成。
漫步會走到哪?均值為零,變異數逐漸擴散
現在來看支配漫步行為的那兩個數。由於每一步都對稱,E[X_k] = 0,而依期望值的線性,位置對每個 n 都有 E[S_n] = E[X_1] + ... + E[X_n] = 0。平均而言漫步哪兒也沒去——它的期望位置永遠被釘在原點。這是一個真實而有用的事實,但也是一個著名的陷阱:它並不代表漫步會待在 0 附近。在許多想像中重複的平均下是 0;而任何一條單獨的路徑,都可能遊蕩到驚人地遠。
這份擴散由變異數捕捉。每一步有 Var(X_k) = E[X_k^2] - (E[X_k])^2 = 1 - 0 = 1。由於步伐獨立,變異數就直接相加:Var(S_n) = Var(X_1) + ... + Var(X_n) = n。所以位置的標準差是 n 的平方根。走了 100 步後,漫步通常離家約 sqrt(100) = 10 個單位;走了 10000 步後,約 100 個單位。這種 sqrt(n) 的成長,正是擴散的招牌節奏——漫步的典型距離會增長,但只以時間平方根的速度增長,遠慢於它已邁出的那 n 步。
在那個「獨立步伐之和」的結構裡,藏著一份美麗的回報。把位置用它的標準差來重新縮放,形成 S_n / sqrt(n)。由於 S_n 是許多獨立同分布、且變異數有限的小塊之和,中央極限定理便派上用場:當 n 很大時,S_n / sqrt(n) 的分布會趨近 Normal(0, 1)。所以縱然每一步都只是粗糙的 +/-1,累積的位置卻會平滑成那條熟悉的鐘形曲線。(中央極限定理需要那個有限的變異數——這裡它等於 1,所以我們很安全;若是步伐尾部很重、變異數無限的漫步,根本不會收斂到常態。)
無記憶:漫步忘了它是怎麼走到這裡的
接下來這個性質,正是讓漫步成為通往本階段其餘部分的門戶:它具有[[markov-property|馬可夫性質]]。假設我告訴你漫步目前位在位置 S_n = 3。要預測它下一步往哪走,你需要知道整段歷史嗎——它是慢慢爬上來的,還是一飛沖天又跌回來的?不需要。下一步只是又一次嶄新、獨立的擲幣,所以未來只透過現在的值 3 來依賴過去。帶你來到 3 的那條路徑無關緊要;唯一重要的,是你正站在 3 這件事。
留意這又是增量結構在發揮作用。由於未來的步伐與過去的步伐獨立,以整段過去為條件,所得的預測,與僅以當前位置為條件所得的完全相同。用符號寫:給定整段歷史 (S_0, ..., S_n) 之下 S_(n+1) 的條件分布,等於僅給定 S_n 之下的分布。這正是「給定現在,未來與過去獨立」的正式陳述,也是馬可夫鏈的定義性特徵——而馬可夫鏈正是緊接著下一階段的主題。這謙遜的隨機漫步,是你的第一個、也最友善的馬可夫鏈。
漫步接下來開啟了什麼
這一個漫步,是接下來幾乎一切的發射台。問漫步是否必定回到 0,你問的就是常返與暫態——也就是第 4 篇的主題。值得注意的是,答案竟取決於維度:一維或二維的簡單對稱漫步以機率 1 回到起點(它是常返的),但在三維或更高維,它有正的機率永遠遊蕩不歸(它是暫態的)。正如那句話所說:「醉漢終會找到回家的路,醉鳥卻可能永遠迷失。」
把漫步夾在兩道牆之間——比方說,碰到 -a 就輸、碰到 +b 就贏——你便得到了經典的賭徒破產問題,同樣在第 4 篇登場:它告訴一個手握有限資金、面對無盡賭場的賭徒,他破產的確切機率。而與其放大,不如拉遠來看:把時鐘加快、把步幅縮小,並以恰好的 sqrt 耦合比例配對,那條鋸齒狀的漫步便會平滑成布朗運動那條連續、處處不可微的路徑——它是後面某一階段的主角。簡單隨機漫步,簡直可以說,就是透過一張粗糙的像素格子看到的布朗運動。
所以,雖然配方只用了一句話,這個漫步卻悄悄地把增量、擴散的縮放、馬可夫性質,以及布朗運動的種子,全都一次包含在內。第 4 篇會讓漫步在常返與賭徒破產上大顯身手;第 5 篇則會替它披上過濾族與停時的正式語言,讓我們能嚴謹地推理「漫步首次碰到 +5 的那一刻」。把這條一枚硬幣接一枚硬幣的路徑牢記在心——接下來幾乎每一個抽象概念,不過就是這個漫步,從一個新角度去看罷了。