随机过程 7：随机游走

随机游走（random walk）是随机过程中最经典的模型之一，表面上只是”每一步随机往左或往右走”，实际上研究的是一个非常普遍的结构：大量微小随机变化不断累积以后，会出现什么宏观规律？随机游走把随机变量、Markov 性质、独立增量、中心极限定理、recurrence 和布朗运动连结在一起，是理解后续各种随机过程的中心模型。

1. 一维随机游走

1.1 定义：增量独立，状态是累积结果

从 $X_0=0$ 开始，每一步的随机增量 $\epsilon_t$ 以相同概率取 $+1$ 或 $-1$，状态按 $X_{t+1}=X_t+\epsilon_{t+1}$ 递归更新，这就是最简单的一维对称随机游走。展开递归式可得 $X_t=X_0+\epsilon_1+\epsilon_2+\cdots+\epsilon_t=\sum_{i=1}^t\epsilon_i$：$\epsilon_t$ 是每一步新的随机扰动，$X_t$ 是所有历史扰动累积后的状态。$\epsilon_1,\epsilon_2,\dots$ 通常设定成 i.i.d.，但 $X_1,X_2,\dots$ 显然不独立——$X_{t+1}$ 的定义本身就包含 $X_t$。一次具体的 sample path 可能是 0 → 1 → 2 → 1 → 0 → -1 → 0，另一次可能是完全不同的 0 → -1 → -2 → -1 → 0 → 1 → 0：两条路径用的是同一套规则、同样以相同概率选择每一步方向，却可以走出截然不同的轨迹，这正是”随机”在随机游走中的真正含义——规则固定，实现不固定。

1.2 为什么随机游走是 Markov 的

假设已知 $X_t=5$，下一步只有两种可能：以 $1/2$ 的概率走到 4，以 $1/2$ 的概率走到 6；至于过去是怎么走到 5 的，对下一步没有额外影响，即 $P(X_{t+1}\mid X_t,X_{t-1},\dots)=P(X_{t+1}\mid X_t)$。简单随机游走因此是一个标准的一阶 Markov process，这也是随机过程 5：马尔可夫过程里条件独立性质最直接的例子。

2. 波动尺度与漂移

2.1 平均位置是 0，典型距离却不是 0

对对称随机游走，$E[\epsilon_t]=0$，因此 $E[X_t]=0$；但这不代表随机游走一直待在原点附近。$\operatorname{Var}(X_t)=t$，标准差是 $\sqrt t$：走了 $t$ 步以后，典型距离的量级是 $\sqrt t$，而不是 $t$。原因是正负增量会大量互相抵消，中心极限定理给出 $X_t/\sqrt t\Rightarrow N(0,1)$，说明 $X_t$ 本身的自然尺度就是 $\sqrt t$——这正是随机过程 4里 $1/\sqrt n$ 标准误尺度的另一种呈现方式，只是这个尺度描述的是累积和本身，而不是平均值。

2.2 带漂移的随机游走

若每一步不再对称，$P(\epsilon_t=+1)=p\neq1/2$，增量具有非零期望 $\mu=E[\epsilon_t]=p-(1-p)=2p-1$，此时 $E[X_t]=\mu t$，随机游走可以理解成”确定性趋势 $\mu t$ 加上随机波动”：长期趋势按 $t$ 线性增长，随机波动仍然是 $\sqrt t$ 量级，这就是最基础的 drift + noise 结构，也是后续随机微分方程里漂移项与扩散项的雏形。

3. 维度与常返性

3.1 一维、二维、三维以上的关键差异

把位置扩充成 $d$ 维向量 $X_t\in\mathbb Z^d$，每一步在 $2d$ 个坐标方向中随机选择一个，数学结构跟一维并没有本质区别。但对称简单随机游走的长期行为却随维度出现质变：一维和二维的随机游走几乎必然会回到原点（recurrent），三维以上则存在正概率永远不再回到原点（transient）。这是随机过程理论里最著名的维度效应之一。

3.2 为什么 $d=2$ 恰好是临界维度

走 $n$ 步以后，随机游走的典型距离量级是 $\sqrt n$，在 $d$ 维空间中，半径 $\sqrt n$ 的区域体积大约按 $(\sqrt n)^d=n^{d/2}$ 增长，因此回到某个固定位置的概率大致有 $P(X_n=0)\sim n^{-d/2}$ 的量级。判断是否常返，等于判断级数 $\sum_nP(X_n=0)$ 是否发散：$d=1$ 时级数形如 $\sum n^{-1/2}$，发散；$d=2$ 时形如调和级数 $\sum n^{-1}$，仍然发散；$d=3$ 时形如 $\sum n^{-3/2}$，是 $p>1$ 的 p-级数，开始收敛。级数发散代表”有无穷多次机会累积出至少一次真正的回归”，这正是一维、二维 recurrent 而三维以上 transient 的根本原因，$d=2$ 恰好落在调和级数这个发散与收敛的临界点上。

3.3 三维以上”逃走”的概率其实可以精确算出来

“transient”听起来像是一个模糊的定性描述，但三维简单对称随机游走最终回到原点的概率其实有精确数值：这个常数称为Pólya 随机游走常数，约为 $0.340537$——换句话说，在 $d=3$ 的方格上随机游走，大约只有 34% 的路径最终会回到出发点，其余 66% 永远不会回来。$d=4$ 时这个概率进一步降到约 $0.193$，维度越高，回到原点就越困难。这组数字让”一维二维 recurrent、三维以上 transient”不只是一个二元分类，而是一条随维度连续下降的概率曲线，$d=1,2$ 刚好落在概率恰好等于 1 的边界上。

4. 到达时间与赌徒破产

4.1 Hitting time

随机游走自然引出”第一次什么时候到达某个位置”这类问题。定义 $\tau_a=\inf\{t\ge0:X_t=a\}$ 为第一次到达位置 $a$ 的时间，$\tau_a$ 本身也是一个随机变量。类似地可以研究第一次回到原点、第一次超过某个阈值、第一次碰到边界——这些问题会在后续发展成 hitting time、first passage time 和 stopping time 的完整理论。

4.2 反射原理：算出 $n$ 步内到达某个位置的概率

$\tau_a\le n$（$n$ 步内曾经到达过 $a$）这个事件，可以用**反射原理（reflection principle）**精确算出概率，而不需要穷举所有路径。直觉是：任何一条”曾经到达 $a$、最终停在 $b<a$“的路径，都可以把触碰 $a$ 之后的部分整段上下翻转，一一对应到一条”终点在 $2a-b$“的路径，而且对应是一一且等概率的。整理这个对应关系，可得 $P(\tau_a\le n)=2P(S_n\ge a)-P(S_n=a)$（$a>0$ 为整数）。以 $n=100$、$a=10$ 为例，代入二项分布计算可得 $P(\tau_{10}\le100)\approx0.320$：走 100 步，大约有 32% 的概率曾经到达过位置 10，即使 $S_{100}$ 本身的期望值是 0、标准差只有 10。反射原理是后续计算布朗运动首次穿越概率的离散版本，两者用的是同一个对称论证。

4.3 赌徒破产问题：具体算一次

假设一个人初始有 $k$ 元，每局以相同概率赢 1 元或输 1 元，财富过程就是一个带两个吸收边界（$0$ 表示破产，$N$ 表示达到目标）的简单随机游走，问题是”从 $k$ 出发，先到 $N$ 还是先到 0”，这就是经典的赌徒破产问题（Gambler’s Ruin）。对公平硬币（$p=1/2$），在先到 $N$ 之前先破产的概率恰好等于 $1-k/N$，先达到 $N$ 的概率是 $k/N$——这个简洁结果可以用”财富过程本身是鞅（martingale）“证明，但不需要先懂鞅也能直接使用它。以 $k=30$、$N=100$ 为例，先达到 100 元的概率是 $30/100=0.3$，先归零的概率是 $0.7$；把 $k$ 提高到 90，先达到 100 的概率就提高到 $0.9$——起始资金越接近目标，越可能在破产前先达标，这个线性关系只在公平硬币下成立，一旦 $p\neq1/2$，公式会变成 $\dfrac{1-(q/p)^k}{1-(q/p)^N}$（$q=1-p$），不再是简单的线性比例。

5. 随机游走的推广

5.1 图上的随机游走

随机游走不一定发生在直线或规则网格上：如果状态空间是一个图，每一步随机选择当前节点的一个邻居，就得到 random walk on graph，广泛出现在 PageRank、网络分析、社区发现、MCMC 和扩散传播模型中。PageRank 的经典直觉，就是一个用户不断在网页之间随机点选链接，研究长期在哪些网页停留得更多。

5.2 布朗运动：连续时间极限

如果把每一步的空间步长和时间间隔都变得越来越小、并进行适当缩放，随机游走的整条 sample path 会逐渐趋近布朗运动：布朗运动可以理解成随机游走的连续时间极限，这条联系是中心极限定理在”整个随机过程”层面的推广，而不只是单一时刻分布的推广。

6. 常见误解与小结

随机游走最容易被误解的一点，是把”平均位置是 0”跟”随机游走会一直停留在原点附近”混为一谈——第 2.1 节已经说明，$\sqrt t$ 的典型距离会随时间持续变大，只是远比线性成长慢。另一个常见误解是把常返性跟”一定会回来很多次”画上等号：一维、二维的常返性只保证概率为 1 会回到原点至少一次（实际上是无穷多次），但期望回归时间可能是无限大，常返不代表回归”快”。

随机游走最基本的形式是 $X_{t+1}=X_t+\epsilon_{t+1}$，也就是”当前状态 = 上一步状态 + 新的随机扰动”，定义极其简单，却自然产生了 Markov 性质、独立增量、$\sqrt t$ 波动尺度、维度相关的 recurrence/transience、hitting time、赌徒破产这类吸收边界问题，一路连结到 random walk on graph 和布朗运动。随机游走不是一个孤立的小例子，而是随机过程理论中串连大量核心概念的中心模型。