随机游走

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