随机游走

随机游走（英语：Random Walk，缩写为 RW），是一种数学统计模型，它是一连串的轨迹所组成，其中每一次都是随机的。它能用来表示不规则的变动形式，如同一个人酒后乱步，所形成的随机过程记录。1905年，由卡尔·皮尔逊首次提出。

随机游走可以在各种空间上进行：通常研究的包括图，整数或实数线，向量空间，曲面，高维的黎曼流形，以及群，有限生成群或李群。在最简单的情况中，时间是离散的，随机游走的路径为一个由自然数索引的随机变量序列(X
t) = (X
1, X
2, ...)。但是，也可以定义在随机时间采取步骤的随机游走，在这种情况下，必须定义X
t的所有时间t ∈

一种较常见的模型是在规则点阵上的随机漫步。在每一步中，标记的位置根据特定的概率分布从一点跳到另一个点。 在简单随机漫步中，每一点只能跳到点阵中的相邻位置，形成点阵路径（英语：lattice path）。 在一个局部有限（英语：locally finite）点阵上的简单对称随机游走，跳到其每个直接相邻的位置的概率是相同的。最被广泛研究的例子是‘d’维整数点阵${\displaystyle {\mathbb{Z}}^d}$, 或. 最后一个名字的来历如下：若一个拥有有限财富的赌徒和一家拥有无限金钱的银行玩“公平游戏”，最终赌徒一定会输掉。 赌徒的钱的数量将经过随机游走的过程，并且在某个时刻达到零，游戏结束。

设和为正整数。在一维线上从0开始一个随机游走过程，那么从0到第一次碰到或-时的期待时间是。先到达后到达的几率为${\displaystyle a/(a+b)}$的不同路径的数量为2。在简单随机游走的情况下，每一条路径的概率是相同的。等于任意一个数，当且仅当+1的数量比-1的数量多。那么+1在步中必须出现( + )/2次，所以满足${\displaystyle S_n=k}$个元素的集中选择( + )/2个元素，写作$(\genfrac{}{}{0ex}{}{{\displaystyle n}}{(n+k)/2})$ + 必须为偶数，也就是说和要么两个都是奇数，要么都是偶数。所以${\displaystyle S_n=k}$来阐明。0次掷硬币后，标记只可能停在0。一次掷硬币后，标记可能停在-1或1。两次后，1可以移动到2或0，而-1可以移动到-2或0。因此，有一种可能停在2，一种可能停在-2，两种可能会停在0。

中心极限定理和重对数律描述了${\displaystyle \mathbb{Z}}$也可以看作一个马尔可夫链，其状态空间由整数${\displaystyle i=0,\pm <!--\; \pm \; -->1,\pm <!--\; \pm \; -->2,\dots <!--\; \dots \; -->.}$满足移动到状态的概率）为

在更高的维度中，随机行走点集具有一些特别的的几何属性。我们得到一个离散的分形，它一个在很大的尺度上有着随机的自相似特性。在小尺度上，可以观察到因点阵的形状产生的锯齿。 下面引用的两本劳勒(Lawler)的书里有不少关于这个这个主题的资料。若我们忽略到达每一点的时间，那么随机游走的轨迹就是所有曾经到达的点的集合。在一维中，随机游走的轨迹就是最小高度和最大高度之间的所有点（平均来讲，两者均为${\displaystyle \sqrt{n}}$，则需要走一段长度为/ε 2 的距离。 随着步长趋于0，步数成比例地增加，随机游走将在一定意义上意义收敛到维纳过程。严格来说，如果“B”是所有长度为“L”的具有最大拓扑的路径的空间，并且如果“M”是具有范数拓扑“B”的度量空间，那么它将收敛在空间。类似地，在多个维度上的维纳过程是在相同维数的随机游走的缩放限制。

在二维上，一个随机游走在其轨迹的边缘上具有的平均点数是 4/3 。这与维纳过程轨迹的边界是维数4/3的分形的事实相应。曼德博使用模拟的方式预测了这一点，但仅在2000年被劳勒（英语：Greg Lawler），施拉姆（英语：Oded Schramm）和沃纳（英语：Wendelin Werner）证明。

维纳过程有着许多随机游走没有的对称。例如，维纳过程的漫步对于旋转是不变的，但是随机游走不是这样的，因为它行走的网格没有这样的对称。（随机游走对旋转90度是不变的，但维纳过程对任何角度的旋转都不变，例如17度）。这意味着，如果我们有一个随机游走的问题，在许多情况下可以将它们转换为维纳过程，解决问题，然后再转换回来。另一方面，由于它的离散性，一些问题更容易通过随机游走来解决。

随机游走和维纳过程可以被耦合（英语：Coupling (probability)），即以相依的方式表现在相同的概率空间上，迫使它们非常接近。 最简单的耦合是Skorokhod嵌入，而更精确的耦合有Komlós-Major-Tusnády逼近定理。

随机游走向维纳过程的收敛由中心极限定理和唐斯科定理（英语：Donsker's theorem）控制。 对于在t = 0时已知固定位置的粒子，中心极限定理告诉我们，在随机游走中的许多独立步骤之后，步行者的位置的分布遵循总方差的正态分布：

其中t是自随机游走开始以来经过的时间，${\displaystyle \mathrm{\epsilon <!--\; \epsilon \; -->}}$是随机游走的步长，而${\displaystyle \mathrm{\delta <!--\; \delta \; -->}t}$是两个连续步骤之间经过的时间。

这对应了控制维纳过程的扩散方程的格林函数，表明在大量的步骤之后，随机游走逐渐向维纳过程收敛。

在三维空间中，对应于扩散方程的格林函数的方差是：

若将这个量与随机游走者的位置相关联的方差相等，对随机游走渐近的维纳过程，可以获得与其等同的扩散系数：

备注：上面方差的两个表达式对应于与三维空间中随机游走的两端链接的向量${\displaystyle \stackrel{\to <!--\; \to \; -->}{R}}$相关联的分布。与每个分量${\displaystyle R_x}$，${\displaystyle R_y}$或${\displaystyle R_z}$相关联的方差仅为该值的三分之一。

在二维上:

在一维上: