随机游走 · aiwiki.page

随机游走是一种随机过程，描述通过连续的随机步进所到达的一系列位置。在标准的数学形式中，每个位置都等于前一个位置加上一个随机增量，各增量相互独立且服从相同的分布。更广义地说，这一术语也包括在图的相邻顶点之间的移动。随机游走为累积波动提供了模型，并将概率论与扩散、离散几何及计算方法联系起来。其行为取决于步长分布、所在空间以及所施加的边界条件。(math.uchicago.edu)

数学定义

对于实数轴上或欧几里得空间中的游走，设 $X_1,X_2,\ldots$ 为表示连续增量的随机变量。从固定位置 $S_0=s$ 出发，定义

S_n=s+\sum_{j=1}^{n}X_j.

通常假定各增量满足统计独立性，并服从同一个概率分布。增量可以取离散值或连续值，不必具有相同的长度，也不必关于零对称。(math.uchicago.edu)

这样的游走是一条马尔可夫链：在给定当前位置的条件下，其未来演化不依赖于先前的位置。这就是马尔可夫性质。增量独立性比单独的这一性质更强；一般马尔可夫链的转移概率可以随当前状态而变化。不规则图上的随机游走体现了这种区别，因为可选择的移动取决于当前所在的顶点。(math.mit.edu)

一维简单随机游走

最简单的例子是在整数上移动，以概率 $p$ 迈出 $+1$ 的一步，以概率 $q=1-p$ 迈出 $-1$ 的一步。当 $p=q=1/2$ 时，游走是对称的；否则就是有偏的。从零出发，若 $B_n$ 表示正向步数，则 $B_n$ 服从二项分布，且 $S_n=2B_n-n$ 。因此，

\Pr(S_n=k)= \binom{n}{(n+k)/2} p^{(n+k)/2}q^{(n-k)/2},

其中须满足 $|k|\le n$ ，且 $n+k$ 为偶数；否则概率为零。例如，这一奇偶性限制意味着，只有在走过偶数步之后才可能返回零点。(math.mit.edu)

其期望值和方差为

\mathbb E[S_n]=n(p-q), \qquad \operatorname{Var}(S_n)=4npq.

因此，对称游走的平均位移为零，但位置分布越来越分散：其标准差为 $\sqrt n$ 。均值为零并不意味着一条典型路径会始终停留在零点附近；它只是说明，对所有可能路径取平均时，正负位移相互抵消。更一般地，若增量的均值为 $\mu$ ，有限方差为 $\sigma^2$ ，则位置的均值为 $s+n\mu$ ，方差为 $n\sigma^2$ 。(ocw.mit.edu)

常返性与暂留性

如果游走以概率一返回出发点，就称其为常返的；如果返回概率小于一，就称其为暂留的。对于格点 $\mathbb Z^d$ 上的简单对称游走，每一步都从 $2d$ 个最近邻中等概率地选择一个。1921 年确立的波利亚常返定理指出，这种游走在一维和二维中是常返的，而在三维及更高维中是暂留的。这一结论适用于上述特定的格点游走，并不能自动推广到这些维度中的所有随机运动。(arxiv.org)

常返性意味着几乎必然会返回无穷多次，但并不意味着等待返回的期望时间有限。一维对称游走是零常返的：它必定返回，但首次返回时间的期望为无穷大。对于暂留游走，任何固定位置几乎必然都只会被访问有限次。这些区别将最终返回、反复访问和平均返回时间区分开来。(cs.yale.edu)

首达时间与边界

首达时间记录游走首次到达指定状态或集合的时刻。边界条件可以显著改变这一过程：吸收边界会使运动停止，而反射边界则会改变运动方向或限制运动。(math.mit.edu)

经典的赌徒破产问题研究集合 $\{0,1,\ldots,N\}$ 上的最近邻游走，游走在到达任一端点时停止。对于从 $i$ 出发的对称游走，先到达 $N$ 而非零的概率为 $i/N$ ，停止时间的期望为 $i(N-i)$ 。这些结果可通过对第一步进行条件分析，并求解具有指定端点值的递推关系得到。它们说明，涉及边界的问题不同于固定时刻的位置分布问题。(stat.berkeley.edu)

缩放极限与扩散

对于独立同分布、均值有限且方差为正的有限值的增量，中心极限定理给出

\frac{S_n-s-n\mu}{\sigma\sqrt n} \ \xrightarrow{\mathrm{distribution}}\ N(0,1).

这解释了为什么即使单步增量不服从正态分布，长时间的位置统计中仍会出现正态分布。这一结果讨论的是分布的收敛，而不是某条单独路径收敛到固定轨迹。(ocw.mit.edu)

一个更强的函数型极限定理将整条经过缩放的路径与布朗运动联系起来，后者在数学上由维纳过程表示。在这一缩放中，时间被加速，而中心化后的空间位移按平方根尺度缩小。这建立了离散随机游走与连续介质中扩散之间的联系，扩散的密度演化由热方程描述。方差无穷大的重尾增量，或步与步之间的强相关性，可能产生不同的缩放行为。(math.uchicago.edu)

图上的游走及其推广

在图论中，简单随机游走从当前顶点的邻接顶点中等概率地选择下一个顶点。对于相邻顶点，其转移矩阵满足 $P_{uv}=1/\deg(u)$ 。在至少有一条边的有限连通无向图上，唯一的平稳分布为

\pi(u)=\frac{\deg(u)}{2|E|}.

因此，度数较高的顶点具有更大的平稳概率。要收敛到这一分布，还需要满足非周期性；允许游走者以正概率停留在原地，可以消除二分图中周期为二所造成的障碍。(cs.yale.edu)

推广形式包括具有随机等待时间的连续时间游走、移动方向之间存在相关性的持续性游走，以及禁止再次访问已到过位置的自避游走。这些形式分别修改了基本模型的不同假设。持续性游走和自避游走用于聚合物建模，而长等待时间和重尾跳跃则为反常扩散提供了模型。(math.mit.edu)