隨機漫步

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

一維的隨機遊走。縱軸表示當前的位置，橫軸表示時間步數

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

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

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

點陣隨機漫步

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

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

一維隨機漫步

一個簡單的隨機漫步的例子是在整數${\displaystyle \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次翻轉後的所有可能結果。

5次擲硬幣後所有可能的結果

二維平面上的隨機漫步 (動態版)

二維平面上的隨機漫步（5000步） (動態版)

二維隨機漫步（兩百萬步），每一步的距離變得更小。在這張圖上，重複到達的點會顯得更暗。在極限情況下，每一步的距離變得非常小，可以獲得布朗運動.

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

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

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

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

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

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

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

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

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

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

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

k	−5	−4	−3	−2	−1	0	1	2	3	4	5
${\displaystyle P[S_{0}=k]}$						1
${\displaystyle 2P[S_{1}=k]}$					1		1
${\displaystyle 2^{2}P[S_{2}=k]}$				1		2		1
${\displaystyle 2^{3}P[S_{3}=k]}$			1		3		3		1
${\displaystyle 2^{4}P[S_{4}=k]}$		1		4		6		4		1
${\displaystyle 2^{5}P[S_{5}=k]}$	1		5		10		10		5		1

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

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

作爲馬爾可夫鏈

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

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

在更高的維度上

三個三維空間中的隨機漫步

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

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

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

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

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

與維納過程的關係

機器模擬的二維平面上的維納過程

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

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

在二維上，一個隨機遊走在其軌跡的邊緣上具有的平均點數是r ^4/3 。這與維納過程軌跡的邊界是維數4/3的分形的事實相應。曼德博使用模擬的方式預測了這一點，但僅在2000年被勞勒（英語：Greg Lawler），施拉姆（英語：Oded Schramm）和沃納（英語：Wendelin Werner）證明。^[11]

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

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

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

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

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

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

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

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

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

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

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

在二維上:^[12]

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

在一維上:^[13]

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

相關

• ER隨機圖
• 自避行走

參考文獻

1. Wirth, E.; Szabó, G.; Czinkóczky, A. MEASURE LANDSCAPE DIVERSITY WITH LOGICAL SCOUT AGENTS. ISPRS – International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. 2016-06-08, XLI–B2: 491–495. Bibcode:2016ISPAr49B2..491W. doi:10.5194/isprs-archives-xli-b2-491-2016.
2. Wirth E. (2015). Pi from agent border crossings by NetLogo package （頁面存檔備份，存於網際網路檔案館）. Wolfram Library Archive
3. Pearson, K. The Problem of the Random Walk. Nature. 1905, 72 (1865): 294. Bibcode:1905Natur..72..294P. doi:10.1038/072294b0.
4. Pal, Révész (1990) Random walk in random and nonrandom environments, World Scientific
5. Kohls (2016), Expected Coverage of Random Walk Mobility Algorithm （頁面存檔備份，存於網際網路檔案館）, arxiv.org.
6. Weisstein, Eric W. (編). Random Walk-1-Dimensional. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2016-11-02]. （原始內容存檔於2016-11-18） （英語）.
7. Edward A. Colding et al, Random walk models in biology, Journal of the Royal Society Interface, 2008
8. Kotani, M. and Sunada, T. Spectral geometry of crystal lattices. Contemporary. Math. Contemporary Mathematics. 2003, 338: 271–305. ISBN 9780821833834. doi:10.1090/conm/338/06077.
9. Kotani, M. and Sunada, T. Large deviation and the tangent cone at infinity of a crystal lattice. Math. Z. 2006, 254 (4): 837–870. doi:10.1007/s00209-006-0951-9.
10. Weisstein, Eric W. (編). Pólya's Random Walk Constants. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2016-11-02]. （原始內容存檔於2021-05-09） （英語）.
11. MacKenzie, D. MATHEMATICS: Taking the Measure of the Wildest Dance on Earth. Science. 1883, 290 (5498): 1883–4. PMID 17742050. doi:10.1126/science.290.5498.1883.
12. Chapter 2 DIFFUSION （頁面存檔備份，存於網際網路檔案館）. dartmouth.edu.
13. Diffusion equation for the random walk （頁面存檔備份，存於網際網路檔案館）. physics.uakron.edu.