第二十一章：隨機漫步
隨機漫步（Random Walk）是描述一個個體在每個時步隨機移動的數學模型。它是布朗運動、股價模型、PageRank 演算法的數學基礎。
21.1 基本定義
一維隨機漫步：
從位置 0 出發，在每個時步以機率 p 向右移動 +1，以機率 q = 1 − p 向左移動 −1。
當 p = q = 1/2 時，稱為對稱隨機漫步（公平遊戲）。
從位置 0 出發，在每個時步以機率 p 向右移動 +1，以機率 q = 1 − p 向左移動 −1。
當 p = q = 1/2 時，稱為對稱隨機漫步（公平遊戲）。
設 Sn 為第 n 步時的位置，Xi ∈ {+1, −1} 為第 i 步的移動：
S_n = X_1 + X_2 + ... + X_n
E[S_n] = n(p - q) Var[S_n] = 4npq
E[S_n] = n(p - q) Var[S_n] = 4npq
對稱漫步（p = 1/2）的期望位移為 0，但標準差為 √n，說明位置的擴散程度隨時間平方根增長。
21.1 賭徒破產問題
一位賭徒持有 k 元，目標是贏到 n 元（或破產歸零）。每局以機率 p 贏 1 元，機率 q = 1 − p 輸 1 元。
定理（賭徒破產機率）：
設 r = q/p。若 p ≠ 1/2：
P(達到 n 元) = (1 − r^k) / (1 − r^n)
若 p = 1/2（公平遊戲）：
P(達到 n 元) = k / n
設 r = q/p。若 p ≠ 1/2：
P(達到 n 元) = (1 − r^k) / (1 − r^n)
若 p = 1/2（公平遊戲）：
P(達到 n 元) = k / n
重要結論：若 p < 1/2（對賭場有利），初始資金 k 再多，只要 n 夠大（賭場資金無限），最終必然破產。即使是公平遊戲（p = 1/2），破產機率也隨 n → ∞ 趨近 1。
期望達到目標所需步數 (p ≠ 1/2):
E[T] = k/(q−p) − n·(1−r^k)/((q−p)(1−r^n))
E[T] = k/(q−p) − n·(1−r^k)/((q−p)(1−r^n))
🧪 互動：賭徒漫步模擬器
調整參數，觀察一維隨機漫步的路徑。也可以自動跑多局，統計破產率。
理論預測：
0
總局數
0%
破產率
0%
達標率
等待模擬...
21.2 圖上的隨機漫步
在圖上，漫步者從一個頂點出發，每步均勻隨機選擇一條相鄰邊走過去。長期運行後，停留在各頂點的機率趨近平穩分布（Stationary Distribution）。
定理：對於連通非二部圖，平穩分布 π(v) 正比於頂點 v 的度數（degree）：
π(v) = deg(v) / (2|E|)
π(v) = deg(v) / (2|E|)
顏色深度代表停留頻率。
右側顯示各節點訪問次數與理論平穩分布。
總步數：0
應用：PageRank 演算法
Google 的 PageRank 演算法將「重要網頁」定義為：一個隨機衝浪者（random surfer）長期停留在該頁面的機率。
- 隨機衝浪者以機率 d（阻尼係數，通常 0.85）跟隨頁面上的連結隨機點擊。
- 以機率 1 − d 跳到任意一個隨機頁面（防止沉入沒有出連結的頁面）。
PR(v) = (1−d)/N + d · Σ PR(u)/deg(u) （對所有指向 v 的頁面 u 求和）
這本質上就是在加了「隨機跳轉」的有向圖上做隨機漫步，其平穩分布即為各頁面的 PageRank 值。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)