隨機漫步

随机游走（英語：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.