隨機過程 7：隨機遊走

隨機遊走（random walk）是隨機過程中最經典的模型之一，表面上只是「每一步隨機往左或往右走」，實際上研究的是一個非常普遍的結構：大量微小隨機變化不斷累積以後，會出現什麼宏觀規律？隨機遊走把隨機變數、Markov 性質、獨立增量、中心極限定理、recurrence 和布朗運動連結在一起，是理解後續各種隨機過程的中心模型。

1. 一維隨機遊走

1.1 定義：增量獨立，狀態是累積結果

從 $X_0=0$ 開始，每一步的隨機增量 $\epsilon_t$ 以相同機率取 $+1$ 或 $-1$，狀態按 $X_{t+1}=X_t+\epsilon_{t+1}$ 遞迴更新，這就是最簡單的一維對稱隨機遊走。展開遞迴式可得 $X_t=X_0+\epsilon_1+\epsilon_2+\cdots+\epsilon_t=\sum_{i=1}^t\epsilon_i$：$\epsilon_t$ 是每一步新的隨機擾動，$X_t$ 是所有歷史擾動累積後的狀態。$\epsilon_1,\epsilon_2,\dots$ 通常設定成 i.i.d.，但 $X_1,X_2,\dots$ 顯然不獨立——$X_{t+1}$ 的定義本身就包含 $X_t$。一次具體的 sample path 可能是 0 → 1 → 2 → 1 → 0 → -1 → 0，另一次可能是完全不同的 0 → -1 → -2 → -1 → 0 → 1 → 0：兩條路徑用的是同一套規則、同樣以相同機率選擇每一步方向，卻可以走出截然不同的軌跡，這正是「隨機」在隨機遊走中的真正含義——規則固定，實現不固定。

1.2 為什麼隨機遊走是 Markov 的

假設已知 $X_t=5$，下一步只有兩種可能：以 $1/2$ 的機率走到 4，以 $1/2$ 的機率走到 6；至於過去是怎麼走到 5 的，對下一步沒有額外影響，即 $P(X_{t+1}\mid X_t,X_{t-1},\dots)=P(X_{t+1}\mid X_t)$。簡單隨機遊走因此是一個標準的一階 Markov process，這也是隨機過程 5：馬爾可夫過程裡條件獨立性質最直接的例子。

2. 波動尺度與漂移

2.1 平均位置是 0，典型距離卻不是 0

對對稱隨機遊走，$E[\epsilon_t]=0$，因此 $E[X_t]=0$；但這不代表隨機遊走一直待在原點附近。$\operatorname{Var}(X_t)=t$，標準差是 $\sqrt t$：走了 $t$ 步以後，典型距離的量級是 $\sqrt t$，而不是 $t$。原因是正負增量會大量互相抵消，中心極限定理給出 $X_t/\sqrt t\Rightarrow N(0,1)$，說明 $X_t$ 本身的自然尺度就是 $\sqrt t$——這正是隨機過程 4裡 $1/\sqrt n$ 標準誤尺度的另一種呈現方式，只是這個尺度描述的是累積和本身，而不是平均值。

2.2 帶漂移的隨機遊走

若每一步不再對稱，$P(\epsilon_t=+1)=p\neq1/2$，增量具有非零期望 $\mu=E[\epsilon_t]=p-(1-p)=2p-1$，此時 $E[X_t]=\mu t$，隨機遊走可以理解成「確定性趨勢 $\mu t$ 加上隨機波動」：長期趨勢按 $t$ 線性增長，隨機波動仍然是 $\sqrt t$ 量級，這就是最基礎的 drift + noise 結構，也是後續隨機微分方程裡漂移項與擴散項的雛形。

3. 維度與常返性

3.1 一維、二維、三維以上的關鍵差異

把位置擴充成 $d$ 維向量 $X_t\in\mathbb Z^d$，每一步在 $2d$ 個座標方向中隨機選擇一個，數學結構跟一維並沒有本質區別。但對稱簡單隨機遊走的長期行為卻隨維度出現質變：一維和二維的隨機遊走幾乎必然會回到原點（recurrent），三維以上則存在正機率永遠不再回到原點（transient）。這是隨機過程理論裡最著名的維度效應之一。

3.2 為什麼 $d=2$ 恰好是臨界維度

走 $n$ 步以後，隨機遊走的典型距離量級是 $\sqrt n$，在 $d$ 維空間中，半徑 $\sqrt n$ 的區域體積大約按 $(\sqrt n)^d=n^{d/2}$ 增長，因此回到某個固定位置的機率大致有 $P(X_n=0)\sim n^{-d/2}$ 的量級。判斷是否常返，等於判斷級數 $\sum_nP(X_n=0)$ 是否發散：$d=1$ 時級數形如 $\sum n^{-1/2}$，發散；$d=2$ 時形如調和級數 $\sum n^{-1}$，仍然發散；$d=3$ 時形如 $\sum n^{-3/2}$，是 $p>1$ 的 p-級數，開始收斂。級數發散代表「有無窮多次機會累積出至少一次真正的回歸」，這正是一維、二維 recurrent 而三維以上 transient 的根本原因，$d=2$ 恰好落在調和級數這個發散與收斂的臨界點上。

3.3 三維以上「逃走」的機率其實可以精確算出來

「transient」聽起來像是一個模糊的定性描述，但三維簡單對稱隨機遊走最終回到原點的機率其實有精確數值：這個常數稱為Pólya 隨機遊走常數，約為 $0.340537$——換句話說，在 $d=3$ 的方格上隨機遊走，大約只有 34% 的路徑最終會回到出發點，其餘 66% 永遠不會回來。$d=4$ 時這個機率進一步降到約 $0.193$，維度越高，回到原點就越困難。這組數字讓「一維二維 recurrent、三維以上 transient」不只是一個二元分類，而是一條隨維度連續下降的機率曲線，$d=1,2$ 剛好落在機率恰好等於 1 的邊界上。

4. 到達時間與賭徒破產

4.1 Hitting time

隨機遊走自然引出「第一次什麼時候到達某個位置」這類問題。定義 $\tau_a=\inf\{t\ge0:X_t=a\}$ 為第一次到達位置 $a$ 的時間，$\tau_a$ 本身也是一個隨機變數。類似地可以研究第一次回到原點、第一次超過某個閾值、第一次碰到邊界——這些問題會在後續發展成 hitting time、first passage time 和 stopping time 的完整理論。

4.2 反射原理：算出 $n$ 步內到達某個位置的機率

$\tau_a\le n$（$n$ 步內曾經到達過 $a$）這個事件，可以用反射原理（reflection principle）精確算出機率，而不需要窮舉所有路徑。直覺是：任何一條「曾經到達 $a$、最終停在 $b<a$」的路徑，都可以把觸碰 $a$ 之後的部分整段上下翻轉，一一對應到一條「終點在 $2a-b$」的路徑，而且對應是一一且等機率的。整理這個對應關係，可得 $P(\tau_a\le n)=2P(S_n\ge a)-P(S_n=a)$（$a>0$ 為整數）。以 $n=100$、$a=10$ 為例，代入二項分佈計算可得 $P(\tau_{10}\le100)\approx0.320$：走 100 步，大約有 32% 的機率曾經到達過位置 10，即使 $S_{100}$ 本身的期望值是 0、標準差只有 10。反射原理是後續計算布朗運動首次穿越機率的離散版本，兩者用的是同一個對稱論證。

4.3 賭徒破產問題：具體算一次

假設一個人初始有 $k$ 元，每局以相同機率贏 1 元或輸 1 元，財富過程就是一個帶兩個吸收邊界（$0$ 表示破產，$N$ 表示達到目標）的簡單隨機遊走，問題是「從 $k$ 出發，先到 $N$ 還是先到 0」，這就是經典的賭徒破產問題（Gambler’s Ruin）。對公平硬幣（$p=1/2$），在先到 $N$ 之前先破產的機率恰好等於 $1-k/N$，先達到 $N$ 的機率是 $k/N$——這個簡潔結果可以用「財富過程本身是鞅（martingale）」證明，但不需要先懂鞅也能直接使用它。以 $k=30$、$N=100$ 為例，先達到 100 元的機率是 $30/100=0.3$，先歸零的機率是 $0.7$；把 $k$ 提高到 90，先達到 100 的機率就提高到 $0.9$——起始資金越接近目標，越可能在破產前先達標，這個線性關係只在公平硬幣下成立，一旦 $p\neq1/2$，公式會變成 $\dfrac{1-(q/p)^k}{1-(q/p)^N}$（$q=1-p$），不再是簡單的線性比例。

5. 隨機遊走的推廣

5.1 圖上的隨機遊走

隨機遊走不一定發生在直線或規則網格上：如果狀態空間是一個圖，每一步隨機選擇當前節點的一個鄰居，就得到 random walk on graph，廣泛出現在 PageRank、網路分析、社群發現、MCMC 和擴散傳播模型中。PageRank 的經典直覺，就是一個使用者不斷在網頁之間隨機點選連結，研究長期在哪些網頁停留得更多。

5.2 布朗運動：連續時間極限

如果把每一步的空間步長和時間間隔都變得越來越小、並進行適當縮放，隨機遊走的整條 sample path 會逐漸趨近布朗運動：布朗運動可以理解成隨機遊走的連續時間極限，這條聯繫是中心極限定理在「整個隨機過程」層面的推廣，而不只是單一時刻分佈的推廣。

6. 常見誤解與小結

隨機遊走最容易被誤解的一點，是把「平均位置是 0」跟「隨機遊走會一直停留在原點附近」混為一談——第 2.1 節已經說明，$\sqrt t$ 的典型距離會隨時間持續變大，只是遠比線性成長慢。另一個常見誤解是把常返性跟「一定會回來很多次」畫上等號：一維、二維的常返性只保證機率為 1 會回到原點至少一次（實際上是無窮多次），但期望回歸時間可能是無限大，常返不代表回歸「快」。

隨機遊走最基本的形式是 $X_{t+1}=X_t+\epsilon_{t+1}$，也就是「當前狀態 = 上一步狀態 + 新的隨機擾動」，定義極其簡單，卻自然產生了 Markov 性質、獨立增量、$\sqrt t$ 波動尺度、維度相關的 recurrence/transience、hitting time、賭徒破產這類吸收邊界問題，一路連結到 random walk on graph 和布朗運動。隨機遊走不是一個孤立的小例子，而是隨機過程理論中串連大量核心概念的中心模型。