前言

本报告整理了利用鞅理论和停时方法解决“一维随机游动”问题的解题过程要点，并初步探究了二维随机游动的相关问题。给出了包括有吸收壁的简单对称随机游走、单边游走与常返性、有偏的随机游走等三种典型情形的详细分析，讨论了吸收概率、期望停止时间等关键量的计算方法。

关键字：鞅，可选停止定理，吸收概率，期望停时，离散调和函数。

---

一维随机游走

Case I：有吸收壁的简单对称随机游走

设 $X_1, X_2, \dots$ 独立同分布（i.i.d.），且 $P(X_i=1)=P(X_i=-1)=1/2$，随机游走过程定义为 $S_0=0,\; S_n=\sum_{i=1}^n X_i$，$\mathcal{F}_n=\sigma(X_1,\dots,X_n)$。

定义停时 $T=\inf\{n:\; S_n=-a \text{ 或 } S_n=b\}$，其中 $a,b>0$。

Step 1-3：计算吸收结果分布 $P(S_T=-a)、P(S_T=b)$

1. 构造鞅： 过程 $S_n$ 是一个鞅，因为 $E[S_n|\mathcal{F}_{n-1}] = S_{n-1} + E[X_n] = S_{n-1}$。 根据 Doob 可选停止定理，对于停时 $T$，过程 $S_{n \wedge T}$ 也是一个鞅，因此 $E[S_{n \wedge T}] = E[S_0] = 0$。
2. 控制收敛（DCT）： 我们的目标是证明 $E[S_T]=0$。 由于 $S_n$ 在停时 $T$ 之前始终位于 $(-a, b)$ 区间内，所以 $|S_{n \wedge T}| \le \max(a,b)$，即 $S_{n \wedge T}$ 是一致有界的。 当 $n \to \infty$ 时，$S_{n \wedge T} \to S_T$。根据控制收敛定理，我们可以交换期望和极限： $E[S_T] = E[\lim_{n \to \infty} S_{n \wedge T}] = \lim_{n \to \infty} E[S_{n \wedge T}] = 0$
3. 吸收概率：在停时 $T$ 刻，$S_T$ 的取值只能是 $-a$ 或 $b$。设 $P_a = P(S_T=-a)$ 和 $P_b = P(S_T=b)$。

$$\begin{cases} -aP_a + bP_b = 0,\\ P_a + P_b = 1 \end{cases}\\ \Rightarrow \begin{cases} P(S_T=-a)=\dfrac{b}{a+b},\\ P(S_T=b)=\dfrac{a}{a+b} \end{cases}$$

Step 4：计算期望停止时间 $E[T]$

1. 新的鞅：构造一个新过程 $M_n = S_n^2 - n$。这是一个鞅，因为：

$$\begin{align*} E[M_n|\mathcal{F}_{n-1}] &= E[S_n^2 - n | \mathcal{F}_{n-1}] \\ &= E[(S_{n-1}+X_n)^2 - n | \mathcal{F}_{n-1}] \\ &= E[S_{n-1}^2 + 2S_{n-1}X_n + X_n^2 - n | \mathcal{F}_{n-1}] \\ &= S_{n-1}^2 + 2S_{n-1}E[X_n] + E[X_n^2] - n \\ &= S_{n-1}^2 + 0 + 1 - n = (S_{n-1}^2 - (n-1)) = M_{n-1} \end{align*}$$

2. 应用可选停止与收敛定理（OST）：对鞅 $M_n$ 应用可选停止定理，有 $E[M_{n \wedge T}] = E[M_0] = 0$，即 $E[S_{n \wedge T}^2] = E[n \wedge T]$。 当 $n \to \infty$ 时，由于 $S_{n \wedge T}^2$ 有界，由 DCT 可得 $E[S_{n \wedge T}^2] \to E[S_T^2]$。 同时，由单调收敛定理 (MCT) 可得 $E[n \wedge T] \to E[T]$。 因此，我们得到 $E[S_T^2] = E[T]$，这即是 $Wald's Identity$ 的一个特例。
3. 求解 $E[T]$：

$$\begin{align*} E[S_T^2] &= (-a)^2 P(S_T=-a) + b^2 P(S_T=b) \\ &= a^2 \frac{b}{a+b} + b^2 \frac{a}{a+b} \\ &= \frac{ab(a+b)}{a+b} = ab \end{align*}$$

所以，期望停止时间为 $E[T] = ab$

---

Case II：单边停时与常返性

考虑一维对称随机游走是否会回到任意整数点（常返性）。

1. 设停时 $U = \inf\{n: S_n = -a\}$，其中 $a>0$。我们想计算 $P(U < \infty)$
2. 我们可以借助双边吸收壁的结果。设另一个吸收壁在 $b$ 处，停时为 $H_b = \inf\{n: S_n = b\}$。总停时为 $\tau = U \wedge H_b$
3. 从 Case I 的结果可知，粒子被 $b$ 吸收的概率为 $P(S_\tau = b) = \frac{a}{a+b}$
4. 那么，不被 $b$ 吸收（即被 $-a$ 吸收）的概率为 $P(S_\tau = -a) = P(U < H_b) = \frac{b}{a+b}$
5. $b \to \infty$，则 $P(U < \infty) = \lim_{b \to \infty} \frac{b}{a+b} = 1$ **结论：**一维对称随机游走是常返的，它终将到达任何一个整数点。

尝试求解 $P(U=k)$

方法一：组合计数

这种方法实际上就是在解决伯特兰选票问题(Bertrand’s Ballot Problem,1887). 我们的目标其实就是求解 $P(T_{-a}=k|S_k=-a)=\dfrac{P(T_{-a}=k \cap S_k=-a)}{P(S_k=-a)}=\dfrac{P(T_{-a}=k)}{P(S_k=-a)}=p_0$ 即 “在已知第k步在-a被吸收的条件下，这是首次到达的概率”

定理：若 $k$ 步中向右 $m$ 步，则 $P(T_{-a}=k)=\dfrac{|a|}{k}\cdot\dfrac{\binom{k}{m}}{2^k}$。

下面介绍一下Bertrand选票问题中 $p_0$的证明思路: 在一场选举中候选人A得到了p张选票，而候选人B得到了q张选票(p>q)，那么在整个点票过程中A的票数都严格大于B的概率是多少。这个问题的答案是$\dfrac{p-q}{p+q}$

我们将此概率问题转化为一个二维格路计数 (Lattice Path Counting) 问题。

• A每得一票，路径向上走一步 $(0,1)$。
• B每得一票，路径向右走一步 $(1,0)$。

计票过程可以看作一条从原点 $(0,0)$ 出发，经过 $p+q$ 步到达终点 $(q, p)$ 的路径。因为A获得 $p$ 票（向上），B获得 $q$ 票（向右），所以总的路径数量为： $N_{\text{total}} = \binom{p+q}{p}$

“A的票数始终严格领先于B”这一条件，在格路模型中意味着路径上的任意一点 $(x_k, y_k)$ 均满足 $y_k > x_k$（除了起点 $(0,0)$）。换言之，路径不能触碰或穿过对角线 $y=x$。 下面寻找不合规路径（“坏”路径）的策略。一条“坏”路径是指至少触碰过一次直线 $y=x$ 的路径。所有“坏”路径可以分为两类：

• $B_1$ 类: 第一步向右（即第一张票给B）的所有路径。这样的路径在第一步就到达了 $y=x$下方，终点在上方，由连续性则必然穿过直线，因此所有此类路径都是“坏”路径。
• $B_2$ 类: 第一步向上（即第一张票给A），但在后续过程中至少触碰过一次直线 $y=x$ 的路径。

从图中可以看出，对于第一步向上的情况，在路径首次触碰 $y=x$ 的点 $P$ 处，将触碰前的路径段关于 $y=x$ 进行反射变换，得到一条以第一步向右开始的路径（即 $B_1$ 类路径）。这种映射是双射，因此 $|B_1|=|B_2|=\binom{p+q-1}{p}$ 最终的合法路径数为： $N_{\text{valid}} = N_{\text{total}} - |B_1| - |B_2| = \binom{p+q}{p} - 2\binom{p+q-1}{p} = \frac{p-q}{p+q} \binom{p+q}{p}$ 因此，A始终领先B的概率为： $P(\text{A始终领先B}) = \frac{N_{\text{valid}}}{N_{\text{total}}} = \frac{p-q}{p+q}$ 问题中的 $p_0$ 即为 $\displaystyle \frac{a}{k}$，从而得出上述定理。

方法二：概率母函数

1. 构造指数鞅：寻找一个参数 $\rho \in (0,1)$，使得 $Z_n = \rho^{S_n} r^n$ 是一个鞅。

$$\begin{align*} E[Z_n|\mathcal{F}_{n-1}] &= E[\rho^{S_{n-1}+X_n} r^n | \mathcal{F}_{n-1}] \\ &= \rho^{S_{n-1}} r^n E[\rho^{X_n}] \\ &= Z_{n-1} r E[\rho^{X_n}] = Z_{n-1} r \left( \frac{1}{2}\rho^1 + \frac{1}{2}\rho^{-1} \right) \end{align*}$$

要使其为鞅，需要 $r \left( \frac{\rho+\rho^{-1}}{2} \right) = 1$，即 $r = \frac{2}{\rho+\rho^{-1}}$。

2. 求解参数：解方程求出 $\rho = \frac{1-\sqrt{1-r^2}}{r}$ 取较小的根（$0<\rho<1$）。

3. 应用可选停止定理 ：考虑停时 $U = \inf\{n: S_n=a\}$。$Z_n$ 是有界鞅（$0 \le S_{n \wedge U} \le a$），因此 $E[Z_U] = E[Z_0] = \rho^{S_0} r^0 = 1$。 $E[Z_U] = E[\rho^{S_U} r^U] = E[\rho^a r^U] = \rho^a E[r^U] = 1$ 因此，停时 $U$ 的概率母函数为： $E[r^U] = \rho^{-a} = \left( \frac{1-\sqrt{1-r^2}}{r} \right)^{-a}$ 通过展开此母函数，可以得到 $P(U=k)$ 的具体分布。

Case III：有偏随机游走（一般情况）

• 设 $P(X_i=1)=p, P(X_i=-1)=q=1-p$，且 $p \neq q$。
• 此时 $E[X_i] = p-q \neq 0$，所以 $S_n$ 不再是鞅。

Step 1-2: 构造鞅并计算 $E[T]$

1. 构造补偿过程: 定义 $M_n = S_n - n(p-q)$。这是一个鞅，因为：

$$\begin{align*} E[M_n|\mathcal{F}_{n-1}] &= E[S_{n-1}+X_n - n(p-q) | \mathcal{F}_{n-1}] \\ &= S_{n-1} + E[X_n] - n(p-q) \\ &= S_{n-1} + (p-q) - n(p-q) \\ &= S_{n-1} - (n-1)(p-q) = M_{n-1} \end{align*}$$

2. 应用可选停止定理: 对停时 $T = \inf\{n: S_n=-a \text{ or } S_n=b\}$，应用可选停止定理于鞅 $M_n$。 与 Case I 类似，可证明 $E[M_T] = E[M_0] = 0$。 $E[S_T - T(p-q)] = 0 \implies E[T] = \frac{E[S_T]}{p-q}$

Step 3: 计算吸收概率

1. 构造指数鞅：定义 $U_n = \left(\frac{q}{p}\right)^{S_n}$。这是一个鞅，因为：

$$\begin{align*} E[U_n|\mathcal{F}_{n-1}] &= E\left[\left(\frac{q}{p}\right)^{S_{n-1}+X_n} \Big| \mathcal{F}_{n-1}\right] \\ &= \left(\frac{q}{p}\right)^{S_{n-1}} E\left[\left(\frac{q}{p}\right)^{X_n}\right] \\ &= U_{n-1} \left( p \cdot \frac{q}{p} + q \cdot \frac{p}{q} \right) = U_{n-1} (q+p) = U_{n-1} \end{align*}$$

2. 应用可选停止与收敛定理：对停时 $T$ 应用可选停止定理于有界鞅 $U_n$。 $E[U_T] = E[U_0] = \left(\frac{q}{p}\right)^{S_0} = 1$ 展开 $E[U_T]$: $E\left[\left(\frac{q}{p}\right)^{S_T}\right] = \left(\frac{q}{p}\right)^{-a} P(S_T=-a) + \left(\frac{q}{p}\right)^{b} P(S_T=b) = 1$ 结合 $P(S_T=-a) + P(S_T=b) = 1$，解得： $P(S_T=-a) = \frac{\left(\frac{q}{p}\right)^b - 1}{\left(\frac{q}{p}\right)^b - \left(\frac{q}{p}\right)^{-a}}, \quad P(S_T=b) = \frac{1 - \left(\frac{q}{p}\right)^{-a}}{\left(\frac{q}{p}\right)^b - \left(\frac{q}{p}\right)^{-a}}$

Step 4-5: 求解 $E[T]$ 和 $E[S_T]$

将吸收概率代入 $E[S_T] = (-a)P(S_T=-a) + b P(S_T=b)$，然后可以得到 $E[T]$: $E[T] = \frac{1}{p-q} \left( b \frac{1 - (\frac{q}{p})^{-a}}{(\frac{q}{p})^b - (\frac{q}{p})^{-a}} - a \frac{(\frac{q}{p})^b - 1}{(\frac{q}{p})^b - (\frac{q}{p})^{-a}} \right)$

单边吸收（例如 $p>q$ 时，游走趋向于 $+\infty$）的情况，可以通过令 $b \to \infty$ 来分析。

二维随机游走

二维简单对称随机游走

我们考虑一个在二维整数格点 $\mathbb{Z}^2$ 上的随机游走 $P_n = (X_n, Y_n)$，从原点 $P_0 = (0,0)$ 出发。每一步，粒子等概率 (1/4) 地移动到其四个最近邻点之一，即 $(\pm 1, 0)$ 或 $(0, \pm 1)$。 令 $\mathcal{F}_n = \sigma(P_1, \dots, P_n)$ 为自然流（包含到时刻n为止的所有路径信息）。

鞅方法及其应用

构造二维随机游走的鞅

1. 坐标过程：我们定义X和Y坐标的变化$X_n$ 和 $Y_n$ 各自都是关于 $\mathcal{F}_n$ 的鞅。

证明：$E[X_{n+1}|\mathcal{F}_n] = E[X_n + \xi_{n+1}|\mathcal{F}_n] = X_n + E[\xi_{n+1}] = X_n + 0 = X_n$。$Y_n$ 同理。

2. 补偿的距离平方过程： $M_n = |P_n|^2 - n = X_n^2 + Y_n^2 - n$ 是一个鞅。

证明：$E[|P_{n+1}|^2 - (n+1)|\mathcal{F}_n] = E[(X_n+\xi_{n+1})^2 + (Y_n+\eta_{n+1})^2 - (n+1)|\mathcal{F}_n] = X_n^2+Y_n^2 + E[\xi_{n+1}^2+\eta_{n+1}^2] - (n+1) = |P_n|^2 + 1 - (n+1) = |P_n|^2 - n = M_n$。这里利用了 $E[\xi_{n+1}^2+\eta_{n+1}^2]=1$。

3. 基于离散调和函数的鞅 (最通用)：若函数 $f: \mathbb{Z}^2 \to \mathbb{R}$ 是离散调和的，即满足 $f(P) = \frac{1}{4}\sum_{P' \sim P} f(P')$ （P’是P的邻居），则 $M_n = f(P_n)$ 是一个鞅。

证明：$E[M_{n+1}|\mathcal{F}_n] = E[f(P_{n+1})|P_n] = \frac{1}{4}\sum_{P' \sim P_n} f(P') = f(P_n) = M_n$

常见的离散调和函数包括：

• $f(x,y) = c$ (常数)
• $f(x,y) = x$ (导出 $X_n$ 是鞅)
• $f(x,y) = y$ (导出 $Y_n$ 是鞅)
• $f(x,y) = x^2 - y^2$ (导出 $X_n^2 - Y_n^2$ 是鞅)
• $f(x,y) = xy$ (导出 $X_n Y_n$ 是鞅)

应用一：求解撞击概率

设 $D$ 是 $\mathbb{Z}^2$ 上的一个有限区域，边界 $\partial D = \partial D_A \cup \partial D_B$。粒子从 $P_0 \in D$ 出发，停时 $T = \inf\{n : P_n \in \partial D\}$。求粒子在撞击 $\partial D_B$ 之前先撞击 $\partial D_A$ 的概率 $h(P_0)$。

1. 寻找调和函数: 寻找一个离散调和函数 $h(P)$，满足边界条件：$h(P) = 1$ 对所有 $P \in \partial D_A$，$h(P) = 0$ 对所有 $P \in \partial D_B$。这是一个离散狄利克雷问题。

2. 构造鞅: 令 $M_n = h(P_n)$。由于 $h$ 是调和的，$M_n$ 是一个鞅。

3. 应用可选停止定理 (OST): 停时 $T$ 几乎必然有限，且过程 $M_{n \wedge T} = h(P_{n \wedge T})$ 的值被限制在 $[0, 1]$ 内，是有界的。因此 OST 适用，$E[M_T] = E[M_0]$。

4. 求解概率:

   • $E[M_0] = h(P_0)$。
   • $E[M_T] = E[h(P_T)] = 1 \cdot P(\text{停在}\partial D_A) + 0 \cdot P(\text{停在}\partial D_B) = P(\text{停在}\partial D_A)$。

   联立得到 $P(\text{停在}\partial D_A) = h(P_0)$。 结论: 撞击概率等于满足相应边界条件的离散调和函数在起始点的值。

应用二：求解期望停止时间 $E[T]$

问题设定同上，求解 $E[T|P_0]$。

鞅求解策略：

1. 构造鞅：使用鞅 $M_n = |P_n|^2 - n$。
2. 建立方程：

$$\begin{cases} E[M_0] = |P_0|^2 - 0 = |P_0|^2\\ E[M_T] = E[|P_T|^2 - T] = E[|P_T|^2] - E[T] \end{cases}$$

联立得到 $E[|P_T|^2] - E[T] = |P_0|^2$。

结论: 求解期望时间 $E[T]$ 的问题被转化为了求解粒子在边界上的停止位置的{\bf 期望平方距离} $E[|P_T|^2]$。这需要先知道粒子撞击边界各点的概率分布（即先解决撞击概率问题）。

与物理类比：离散泊松方程

求解期望停止时间 $k(P) = E[T|P_0=P]$ 也可以通过马尔可夫链方法，建立并求解一个差分方程： $k(P) = 1 + \frac{1}{4} \sum_{P' \sim P} k(P')$ 整理后得到离散泊松方程： $\Delta k(P) = -1$ 其中 $\Delta k(P) = (\frac{1}{4} \sum_{P' \sim P} k(P')) - k(P)$ 是离散拉普拉斯算子。边界条件为 $k(P) = 0$ 对所有 $P \in \partial D$。

这与静电学中求解有均匀电荷分布区域的电势问题相对应，而撞击概率问题则对应于求解无源区域电势的拉普拉斯方程。

---

附录

手写推导扫描

原稿位于文末供参考：

常用符号表