随机游走（random walk）是随机过程中最经典的模型之一。

它看起来只是“每一步随机往左或往右走”，但真正研究的是一个非常普遍的结构：

大量微小随机变化不断累积以后，会出现什么宏观规律？\boxed{\text{大量微小随机变化不断累积以后，会出现什么宏观规律？}}

随机游走把随机变量、Markov 性质、独立增量、中心极限定理、recurrence 和 Brownian motion 全部连接在了一起。

1. 一维随机游走

1.1 一维简单随机游走

从 X0=0X_0=0 开始。

每一步定义一个随机增量 ϵt\epsilon_t：

ϵt={+1,1/2−1,1/2\epsilon_t= \begin{cases} +1,&1/2\\ -1,&1/2 \end{cases}

然后：

Xt+1=Xt+ϵt+1(1)\boxed{X_{t+1}=X_t+\epsilon_{t+1}} \tag{1}

这就是最简单的一维对称随机游走。

一次 sample path 可能是：

0 → 1 → 2 → 1 → 0 → -1 → 0

另外一次可能是：

0 → -1 → 0 → 1 → 2 → 3 → 2

1.2 随机的是增量，状态是累积结果

把式 (1) 不断展开：

Xt=X0+ϵ1+ϵ2+⋯+ϵtX_t=X_0+\epsilon_1+\epsilon_2+\cdots+\epsilon_t

如果 X0=0X_0=0，则：

Xt=∑i=1tϵi(2)X_t=\sum_{i=1}^t\epsilon_i \tag{2}

所以随机游走的本质非常清楚：

  • ϵt\epsilon_t 是每一步新的随机扰动；
  • XtX_t 是所有历史扰动累积后的状态。

常见设定中，ϵ1,ϵ2,…\epsilon_1,\epsilon_2,\dots 是 i.i.d. 的，但 X1,X2,…X_1,X_2,\dots 显然不是独立的。

因为 Xt+1X_{t+1} 直接包含 XtX_t。

1.3 为什么随机游走是 Markov 的

假设当前已经知道 Xt=5X_t=5。

那么下一步只有两种可能：

  • 以 1/2 的概率走到 4；
  • 以 1/2 的概率走到 6。

至于过去是怎样走到 5 的，对下一步没有额外影响。

因此：

P(Xt+1∣Xt,Xt−1,… )=P(Xt+1∣Xt)P(X_{t+1}\mid X_t,X_{t-1},\dots)=P(X_{t+1}\mid X_t)

所以简单随机游走是一个标准的一阶 Markov process。

2. 波动尺度与漂移

2.1 平均位置和波动尺度

对对称随机游走，有 E[ϵt]=0E[\epsilon_t]=0，因此：

E[Xt]=0E[X_t]=0

但这并不意味着随机游走一直待在原点附近。

因为：

Var⁡(Xt)=t\operatorname{Var}(X_t)=t

所以标准差为：

t\sqrt t

也就是说，走了 tt 步以后，典型距离是 t\sqrt t 量级，而不是 tt。

这正是中心极限定理的直接结果。

2.2 为什么是 t\sqrt t 而不是 tt

如果每一步都朝同一个方向走，距离当然会线性增长成 tt。

但随机游走中的正负增量会大量抵消。

中心极限定理告诉我们：

Xtt⇒N(0,1)\frac{X_t}{\sqrt t}\Rightarrow N(0,1)

所以 XtX_t 本身的典型尺度就是 t\sqrt t。

这是随机过程里非常重要的扩散尺度。

2.3 带漂移的随机游走

如果每一步不再完全对称，例如 P(ϵt=+1)=pP(\epsilon_t=+1)=p，P(ϵt=−1)=1−pP(\epsilon_t=-1)=1-p，并且 p≠1/2p\neq1/2，那么增量具有非零期望。

记：

μ=E[ϵt]\mu=E[\epsilon_t]

则：

E[Xt]=μtE[X_t]=\mu t

于是随机游走可以理解成：

Xt≈μt+随机波动X_t\approx \mu t+\text{随机波动}

其中长期趋势按 tt 增长，而随机波动仍然通常是 t\sqrt t 量级。

这就是最基础的 drift + noise 结构。

3. 维度与常返性

3.1 二维随机游走

二维随机游走把位置扩展成二维向量：

Xt=(xt,yt)X_t=(x_t,y_t)

每一步随机选择：

(1,0),(−1,0),(0,1),(0,−1)(1,0),\quad(-1,0),\quad(0,1),\quad(0,-1)

中的一个方向。

形式仍然是：

Xt+1=Xt+ϵt+1X_{t+1}=X_t+\epsilon_{t+1}

只是此时 ϵt\epsilon_t 本身是二维随机向量。

所以一维和二维随机游走在数学结构上并没有本质区别。

3.2 高维随机游走

进一步可以定义 dd 维随机游走：

Xt∈ZdX_t\in\mathbb Z^d

每一步在 2d2d 个坐标方向中随机选择一个。

此时会出现一个非常漂亮的维度效应。

对于最经典的对称简单随机游走：

  • d=1d=1：最终回到原点的概率为 1；
  • d=2d=2：最终回到原点的概率仍然为 1；
  • d≥3d\ge3：最终回到原点的概率小于 1。

也就是说，一维和二维是 recurrent，而三维及以上是 transient。

3.3 为什么二维会回来，三维却可能逃走

走 nn 步以后，随机游走的典型距离大约是 n\sqrt n。

在 dd 维空间中，半径 n\sqrt n 的区域体积大约按：

(n)d=nd/2(\sqrt n)^d=n^{d/2}

增长。

因此回到某一个固定位置的概率大致具有：

P(Xn=0)∼n−d/2(3)P(X_n=0)\sim n^{-d/2} \tag{3}

的尺度。

于是考虑总的返回机会：

∑nP(Xn=0)\sum_n P(X_n=0)

当 d=1d=1 时类似于 ∑n−1/2\sum n^{-1/2}，发散。

当 d=2d=2 时类似于调和级数 ∑n−1\sum n^{-1}，仍然发散。

而 d=3d=3 时变成 ∑n−3/2\sum n^{-3/2}，开始收敛。

所以 d=2d=2 正好是 recurrence 和 transience 之间的临界维度。

4. 到达时间与赌徒破产

4.1 Hitting time

随机游走还会自然产生一类非常重要的问题：

第一次什么时候到达某个位置？

例如定义：

τa=inf⁡{t≥0:Xt=a}\tau_a=\inf\{t\ge0:X_t=a\}

τa\tau_a 表示第一次到达位置 aa 的时间。

这个时间本身也是随机变量。

类似地，可以研究：

  • 第一次回到原点；
  • 第一次超过某个阈值；
  • 第一次碰到边界；
  • 第一次破产。

这些问题会进一步发展成 hitting time、first passage time 和 stopping time。

4.2 赌徒破产问题

假设一个人初始有 kk 元，每局以相同概率赢 1 元或输 1 元。

财富过程满足：

Xt+1=Xt+ϵt+1X_{t+1}=X_t+\epsilon_{t+1}

同时设置两个边界：

  • 00：破产；
  • NN：达到目标财富。

于是问题变成：

从 kk 出发，先到 NN 还是先到 0？

这就是经典的 Gambler’s Ruin（赌徒破产问题）。

它本质上就是带吸收边界的随机游走。

5. 随机游走的扩展

5.1 图上的随机游走

随机游走不一定发生在直线或规则网格上。

如果状态空间是一个图，每一步随机选择当前节点的一个邻居，就得到 random walk on graph。

这类过程广泛出现在：

  • PageRank；
  • 网络分析；
  • 图算法；
  • 社区发现；
  • MCMC；
  • 扩散和传播模型。

PageRank 的经典直觉，就是一个用户不断在网页之间随机点击链接，并研究长期在哪些网页停留得更多。

5.2 和布朗运动的关系

随机游走还有一个非常重要的连续极限。

如果把每一步的空间步长变得越来越小，同时把时间间隔也越来越小，并进行适当缩放，那么随机游走的整条 sample path 会逐渐趋近布朗运动。

因此可以把布朗运动理解为：

随机游走的连续时间极限\boxed{\text{随机游走的连续时间极限}}

这条联系是中心极限定理在“整个随机过程”层面的推广。

6. 小结

随机游走最基本的形式是：

Xt+1=Xt+ϵt+1X_{t+1}=X_t+\epsilon_{t+1}

它表示：

当前状态 = 上一步状态 + 新的随机扰动。

虽然定义极其简单，却自然产生了：

  • Markov 性质；
  • 独立增量；
  • t\sqrt t 波动尺度；
  • recurrence / transience；
  • hitting time；
  • absorbing boundary；
  • random walk on graph；
  • Brownian motion。

因此，随机游走不是一个孤立的小例子，而是随机过程理论中连接大量核心概念的中心模型。