随机游走

**隨機漫步**（英語：Random Walk，縮寫為 RW），是一種數學統計模型，它是一連串的軌跡所組成，其中每一次都是隨機的。它能用來表示不規則的變動形式，如同一個人酒後亂步，所形成的隨機過程記錄。1905 年，由卡爾・皮爾遜首次提出。

隨機漫步可以在各種空間上進行：通常研究的包括圖，整數或實數線，向量空間，曲面，高維的黎曼流形，以及群，有限生成群或李群。在最簡單的情況中，時間是離散的，隨機漫步的路徑為一個由自然數索引的隨機變量序列 (X 
t) = (X 
1, X 
2, ...)。但是，也可以定義在隨機時間採取步驟的隨機遊走，在這種情況下，必須定義 X 
t 的所有時間 t ∈ [0,+∞)。

通常，我們可以假設隨機漫步是以馬爾可夫鏈或馬可夫過程的形式出現，但是比較複雜的隨機漫步則不一定以這種形式出現。在某些限制條件下，會出現一些比較特殊的模式，如擴散作用的模型布朗運動，醉漢走路（drunkard's walk）或萊維飛行。

隨機漫步在各個領域有許多應用，例如在工程學和許多科學領域，包括生態學，心理學，計算機科學，物理，化學，生物學以及經濟學。在數學中，我們可以用個體為本模型的隨機漫步來估算 π 的值。它可以用來模擬分子在液體或氣體中傳播時的路徑，覓食動物的搜索路徑，波動的股票價格和賭徒的財務狀況。在這些領域中，隨機遊走可以用來解釋許多觀察到的現象，因此它是記錄隨機活動的基本統計模型。

## 點陣隨機漫步

一種較常見的模型是在規則點陣上的隨機漫步。在每一步中，標記的位置根據特定的概率分布從一點跳到另一個點。 在**簡單隨機漫步**中，每一點只能跳到點陣中的相鄰位置，形成點陣路徑。 在一個局部有限點陣上的**簡單對稱隨機漫步**，跳到其每個直接相鄰的位置的概率是相同的。最被廣泛研究的例子是『d』維整數點陣 $\mathbb {Z} ^{d}$ （有時稱為超立方格）上的隨機漫步.

如果狀態空間的大小是有限的，則在此空間上的隨機漫步模型稱為**簡單邊界對稱隨機漫步**。在此情況下，移動的概率取決於當前的位置，因為在邊緣和角落狀態下移動是受制的。例如，若當前位置在邊緣上，則不能向邊緣的外側移動（概率為零）。

### 一維隨機漫步

一個簡單的隨機漫步的例子是在整數 $\mathbb {Z} $ 軸上的隨機漫步。它從 0 開始，然後每一步以相同的概率移動 + 1 或−1。實際操作如下：我們首先在 0 的位置放上一個標記，然後擲一枚公平硬幣。若頭朝上，則將標記向右移動一個單位；反之將標記向左移動一個單位。 五次翻轉後，標記現在可能在 1,-1,3,-3,5 或 - 5 的位置。 若五個翻轉中得到三個頭和兩個尾，不管任何順序，標記都會落在 1。一共有 10 種方式落在 1（三個頭和兩個尾），10 種方式落在 - 1（三個尾和兩個頭），5 種方式落在 3（4 個頭和 1 個尾），5 種方式落在 - 3（4 個尾和 1 個頭），1 種方式 5（5 個頭） ，以及一種方式落在 - 5（五個尾）。下圖列出了 5 次翻轉後的所有可能結果。

要正式定義此路徑，我們採用獨立的隨機變量 $Z_{1},Z_{2},\dots $ , 每一個變量分別有 50% 的概率為 1 或−1。設 $S_{0}=0\,\!$ ， $S_{n}=\sum _{j=1}^{n}Z_{j}.$ 級數 $\{S_{n}\}\,\!$ 稱爲 **$\mathbb {Z} $ 上的簡單隨機漫步**。若每一步的長度為 1，這個級數（由 - 1 和 1 組成的數列的和）就是已經行走的距離。
它的期待值 $E(S_{n})\,\!$ of $S_{n}\,\!$ 為 0。也就是說，隨著擲硬幣次數的增加，所有已擲硬幣的平均值接近零。它遵循了期望值的有限加性屬性：

　
: $E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.$

這些隨機變量的獨立性以及 $E(Z_{n}^{2})=1$ , 顯示了:

　
: $E(S_{n}^{2})=\sum _{i=1}^{n}\sum _{j=1}^{n}E(Z_{j}Z_{i})=n.$

這説明 $E(|S_{n}|)\,\!$ , n 步後的期望的移動距離應爲 ${\sqrt {n}}$ 階。事實上，

　
: $\lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.$

如果隨機漫步永不停止，那麽它會穿過邊界綫多少次？ $\mathbb {Z} $ 上的簡單隨機漫步將會無限次走過每一個點。這個結果被稱爲_平交道現象（level-crossing phenomenon）_ , _重現（recurrence）_ 或_賭徒破產理論_. 最後一個名字的來歷如下：若一個擁有有限財富的賭徒和一家擁有無限金錢的銀行玩「公平遊戲」，最終賭徒一定會輸掉。 賭徒的錢的數量將經過隨機漫步的過程，並且在某個時刻達到零，遊戲結束。

設 _a_ 和 _b_ 為正整數。在一維綫上從 0 開始一個隨機漫步過程，那麽從 0 到第一次碰到 _b_ 或 -_a_ 時的期待時間是 _ab_。先到達 _b_ 後到達 _a_ 的幾率為 $a/(a+b)$ ，因爲簡單隨機漫步是鞅。

上文的一些結論可以從帕斯卡三角的性質中得出。若每一步為 + 1 或 - 1，那麽長度爲 _n_ 的不同路徑的數量為 2n。在簡單隨機漫步的情況下，每一條路徑的概率是相同的。_Sn_ 等於任意一個數 _k_，當且僅當 + 1 的數量比 - 1 的數量多 _k_。那麽 + 1 在 _n_ 步中必須出現 (_n_ + _k_)/2 次，所以滿足 $S_{n}=k$ 的步數等於從一個有 _n_ 個元素的集中選擇 (_n_ + _k_)/2 個元素，寫作 $n \choose (n+k)/2$ 。其中 _n_ + _k_ 必須為偶數，也就是説 _n_ 和 _k_ 要麽兩個都是奇數，要麽都是偶數。所以 $S_{n}=k$ 的幾率等於 $2^{-n}{n \choose (n+k)/2}$ 。若將帕斯卡三角用階乘數寫出，用斯特林公式我們可以在 $n$ 較大的情況下准確地估算這些概率。

爲了簡便，我們將空間局限於 $\mathbb {Z} $ +，那麽指定任意一個數，在 5 次擲硬幣後，隨機漫步停留在這個數的不同方式的數量可被證為 {0,5,0,4,0,1}.

隨機漫步與帕斯卡三角的關係可以用較小的 _n_ 來闡明。0 次擲硬幣後，標記只可能停在 0。一次擲硬幣後，標記可能停在 - 1 或 1。兩次後，1 可以移動到 2 或 0，而 - 1 可以移動到 - 2 或 0。因此，有一種可能停在 2，一種可能停在 - 2，兩種可能會停在 0。

中心極限定理和重對數律描述了 $\mathbb {Z} $ 上的簡單隨機漫步。前者意味著隨著「n」的增加，概率分佈（與每行中的數字成比例）接近常態分布。

這樣的理論可以直接推廣到晶格上的隨機漫步，它是有限圖上的無限摺疊阿貝爾覆蓋圖。在這樣的情境中，我們可以設立中心極限定理和大偏差定理。

#### 作爲馬爾可夫鏈

一維上的'_隨機漫步_也可以看作一個馬爾可夫鏈，其狀態空間由整數 $i=0,\pm 1,\pm 2,\dots .$ 給出。若數字 _p_ 滿足 $\,0<p<1$ , 轉移概率（從狀態 _i_ 移動到狀態 _j_ 的概率 _Pi,j_）為

　
: $\,P_{i,i+1}=p=1-P_{i,i-1}.$

### 在更高的維度上

在更高的維度中，隨機行走點集具有一些特別的的幾何屬性。我們得到一個離散的分形，它一個在很大的尺度上有著隨機的自相似特性。在小尺度上，可以觀察到因點陣的形狀產生的鋸齒。 下面引用的兩本勞勒 (Lawler) 的書裏有不少關於這個這個主題的資料。若我們忽略到達每一點的時間，那麽隨機漫步的軌跡就是所有曾經到達的點的集合。在一維中，隨機漫步的軌跡就是最小高度和最大高度之間的所有點（平均來講，兩者均爲 ${\sqrt {n}}$ 階）。

二維平面上的隨機漫步可以想像為一個人在城市中隨機行走。這個城市的大小是無限的，並由一個方形的人行道網格組成。在每個十字路口，該人隨機選擇四條可能路線中的一條（包括最初來的那條路）。這是在整數平面上所有點的一個隨機漫步。

這個人會不會回到原來的步行起點？在二維平面上，該問題與上文中的平交道問題相當。 1921 年波利亞・哲爾吉證明了這在二維隨機漫步中幾乎必然會發生，但對於 3 維或更高維度，返回原點的概率隨著維數的增加而減少。 在 3 個維度中，這個概率降低到大約 34％。

隨著步數的增加，二維隨機漫步的漸近函數遵從瑞利分布。 概率分布是距離原點的半徑的函數，並且每一步的步長是恆定的。

　
: $P(r)={\frac {2r}{N}}e^{-r^{2}/N}$

### 與維納過程的關係

維納過程是一個隨機過程， 它與布朗運動，也就是微小顆粒在流體中擴散的現象有相似之處。（布朗運動是物理現象，而維納過程是模擬該現象的模型。由於概念上的混淆，有時維納過程也被稱爲「布朗運動」）

維納過程是一維空間上隨機漫步的縮放限制。這意味著我們可以用步長非常小的隨機漫步來模擬維納過程。更確切地講，如果步長是 ε，而我們想要近似維納長度 _L_，則需要走一段長度爲 _L_/ε 2 的距離。 隨著步長趨於 0，步數成比例地增加，隨機漫步將在一定意義上意義收斂到維納過程。嚴格來説，如果「B」是所有長度為「L」的具有最大拓撲的路徑的空間，並且如果「M」是具有範數拓撲「B」的度量空間，那麼它將收斂在空間 _M_。類似地，在多個維度上的維納過程是在相同維數的隨機漫步的縮放限制。

 
在二維上，一個隨機漫步在其軌跡的邊緣上具有的平均點數是 _r_ 4/3 。這與維納過程軌跡的邊界是維數 4/3 的分形的事實相應。曼德博使用模擬的方式預測了這一點，但僅在 2000 年被勞勒，施拉姆和沃納證明。

維納過程有著許多隨機漫步沒有的對稱。例如，維納過程的漫步對於旋轉是不變的，但是隨機漫步不是這樣的，因為它行走的網格沒有這樣的對稱。（隨機漫步對旋轉 90 度是不變的，但維納過程對任何角度的旋轉都不變，例如 17 度）。這意味著，如果我們有一個隨機漫步的問題，在許多情況下可以將它們轉換為維納過程，解決問題，然後再轉換回來。另一方面，由於它的離散性，一些問題更容易通過隨機漫步來解決。

隨機漫步和維納過程可以被耦合，即以相依的方式表現在相同的概率空間上，迫使它們非常接近。 最簡單的耦合是 Skorokhod 嵌入，而更精確的耦合有 Komlós-Major-Tusnády 逼近定理。

隨機漫步向維納過程的收斂由中心極限定理和唐斯科定理控制。 對於在 t = 0 時已知固定位置的粒子，中心極限定理告訴我們，在隨機漫步中的許多獨立步驟之後，步行者的位置的分佈遵循總方差的常態分布：

　
: $\sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2},$

其中 t 是自隨機漫步開始以來經過的時間， $\varepsilon $ 是隨機漫步的步長，而 $\delta t$ 是兩個連續步驟之間經過的時間。

這對應了控制維納過程的擴散方程的格林函數，表明在大量的步驟之後，隨機漫步逐漸向維納過程收斂。

在三維空間中，對應於擴散方程的格林函數的方差是：

　
: $\sigma ^{2}=6\,D\,t.$

若將這個量與隨機漫步者的位置相關聯的方差相等，對隨機漫步漸近的維納過程，可以獲得與其等同的擴散係數：

　
: $D={\frac {\varepsilon ^{2}}{6\delta t}}$ (僅在三維空間中有效).

備註：上面方差的兩個表達式對應於與三維空間中隨機漫步的兩端連結的向量 ${\vec {R}}$ 相關聯的分布。與每個分量 $R_{x}$ ， $R_{y}$ 或 $R_{z}$ 相關聯的方差僅為該值的三分之一。

在二維上:

　
: $D={\frac {\varepsilon ^{2}}{4\delta t}}.$

在一維上:

　
: $D={\frac {\varepsilon ^{2}}{2\delta t}}.$

## 相關

* ER 隨機圖
* 自避行走

## 參考文獻