Optional Stopping Time: Gambler’s Ruin Problem

Definition

Let (X_n) be a martingale and let T be a stopping time. If:

$$\mathbb E[|X_T|]<$$

\infty

$$\lim_{n\to\infty}\mathbb E\bigl[|X_n|\mathbf 1(T>n)\bigr]=0$$

then

$$\mathbb E[X_T]=$$

\mathbb E[X_0].$$

问题： $X_n$ 是 SRW，$X_0 = a$（$0 < a < c$），$T = \inf{t \geq 0 : X_t \in {0, c}}$。求 $P(X_T = c)$。

Step 1： $X_n$ 本身就是 martingale（partial sum 型，增量 $\pm 1$ 均值为零）。

Step 2： $T$ 是 first exit time from ${1, 2, \ldots, c-1}$，是 stopping time。

Step 3： 在 $T$ 之前，$X_n$ 始终在 ${0, 1, \ldots, c}$ 中，所以 $|X_n| \leq c$ for all $n \leq T$。推论适用。

Step 4： $E[X_T] = E[X_0] = a$。

Step 5： $X_T$ 只能取 0 或 $c$。设 $p = P(X_T = c)$。

$$E[X_T] = c \cdot p + 0 \cdot (1 - p) = cp$$

所以 $cp = a$，$p = a/c$。

1. 故事背景（翻译问题）

  • $X_n$ 是 SRW：你在玩一个绝对公平的抛硬币游戏，赢了赚 1 块，输了亏 1 块。
  • $X_0 = a$：你带着 $a$ 块钱走进赌场（假设是 30 块钱）。
  • $c$：你给自己定了一个目标金额（假设是 100 块钱）。
  • $T$ 和离场规则：你要么把钱输光（资产变成 0），要么达到目标（资产变成 100），只要触发其中一个，你立刻离场。
  • 求 $P(X_T = c)$：问你最终能成功带着 100 块钱走出赌场的概率是多少？

2. 如果没有 OST，你要怎么算？

如果你硬算，你需要计算：

  • 第 100 步刚好走到 100 的概率
  • 第 102 步刚好走到 100 的概率（中间有输有赢）
  • 第 1000 步、第 10000 步… 由于路径有无穷多种组合，靠暴力穷举根本算不出来。

3. OST 是如何秒杀这个问题的？（逐行解析图片）

OST 告诉我们：只要满足条件，你可以完全无视中间无穷无尽的曲折路径，直接利用“期望守恒”列方程。

  • Step 1: 确认游戏是公平的（Martingale）。

  • Step 2: 你的离场规则明确清晰，到点就停（Stopping Time）。

  • Step 3（核心前提）: 在你离场之前，你手里的钱始终在 $0$ 到 $c$ 之间（最多 100 块，最少 0 块）。这意味着你不可能无限度地输下去。因为变量被“框住”了（Bounded），所以完美满足 OST 的安全阀条件！

  • Step 4（魔法生效）: 既然满足 OST，那么直接套用公式：你离场时的平均预期总资产 $E[X_T]$，必须绝对等于你刚进场时的本金 $E[X_0]$。 因为你带了 $a$ 块钱进场，所以 $E[X_T] = a$。

  • Step 5（算概率）: 思考一下你离场时的状态，只有两种可能：

    1. 你赢了，手里拿着 $c$ 块钱（概率我们设为 $p$）。
    2. 你输光了，手里拿着 0 块钱（概率自然是 $1-p$）。

    根据数学期望的定义，把你离场的这两种状态加起来，必须等于你的本金：

    $$E[X_T] = c \cdot p + 0 \cdot (1-p) = c \cdot p$$

    再结合 Step 4 得到的 $E[X_T] = a$，我们就得到了一个极其简单的一元一次方程：

    $$c \cdot p = a$$

    $$p = a / c$$

结论：OST 到底在做什么？

在这个例子中，你想带着 30 块钱（$a=30$）去赢到 100 块钱（$c=100$）。 OST 直接告诉你，不用算复杂的路径了，你成功的概率就是 30/100 = 30%。你带的本金占目标的比例，就是你赢的概率。

OST 的作用就是帮你建立这样一个等式：最终所有结局的加权平均值 = 初始状态。 借此，你可以极其优雅地解出原本无法计算的概率。

1. SRW (Symmetric Simple Random Walk) 的数学定义

SRW 是一种最基础的离散时间随机过程。

Formal Definition: Symmetric Simple Random Walk Let $Y_1, Y_2, \dots$ be a sequence of independent and identically distributed (i.i.d.) random variables such that:

$$P(Y_i = 1) = \frac{1}{2}, \quad P(Y_i = -1) = \frac{1}{2}$$

Let $X_0 = a$, where $a \in \mathbb{R}$ is the initial state. The stochastic process $(X_n)_{n \ge 0}$ defined by:

$$X_n = X_0 + \sum_{i=1}^n Y_i$$

is called a Symmetric Simple Random Walk (SRW).

逻辑推演：为什么 SRW 是 Martingale？ 为了证明 $(X_n)$ 构成一个 Martingale，需要验证给定当前时刻 $n$ 的过滤 $\mathcal{F}_n$ 下，下一时刻的条件期望等于当前状态：

$$E[X_{n+1} \mid \mathcal{F}_n] = E[X_n + Y_{n+1} \mid \mathcal{F}_n]$$

由于 $X_n$ 在 $\mathcal{F}_n$ 下是可测的（已知信息），而 $Y_{n+1}$ 独立于 $\mathcal{F}_n$：

$$E[X_{n+1} \mid \mathcal{F}_n] = X_n + E[Y_{n+1}]$$

根据定义，$E[Y_{n+1}] = 1 \cdot (1/2) + (-1) \cdot (1/2) = 0$。因此：

$$E[X_{n+1} \mid \mathcal{F}_n] = X_n$$

这证明了 SRW 严格满足 Martingale 的定义。因此，对于任意固定的离散时间 $n$，必然有 $E[X_n] = E[X_0]$。

2. OST (Optional Stopping Theorem) 定理本身的逻辑解析

你已经理解了对固定的绝对时间 $n$，$E[X_n] = E[X_0]$ 成立。OST 探讨的唯一核心问题是：如果把固定的常数时间 $n$，替换为一个随机变量 $T$（Stopping Time），期望的等式 $E[X_T] = E[X_0]$ 是否还能无条件成立？

答案是否。我们需要从测度论和积分极限的角度来审视定理的必要性。

Formal Theorem: Optional Stopping Theorem Let $(X_n)_{n \ge 0}$ be a martingale with respect to a filtration $\{\mathcal{F}_n\}$, and let $T$ be a stopping time. If the following conditions are satisfied:

  1. $E[|X_T|] < \infty$
  2. $\lim_{n \to \infty} E[|X_n| \mathbf{1}(T > n)] = 0$ Then, $E[X_T] = E[X_0]$.

为什么常数 $n$ 可以，随机变量 $T$ 就不行？

从微观状态空间 $\Omega$ 来看：

  • 对于常数时间 $n$：$E[X_n]$ 是对所有样本路径 $\omega \in \Omega$ 在同一个绝对时间切片 $n$ 上的状态求积分（或求和）。由于 Martingale 的结构，这个切片的均值被严格守恒。
  • 对于随机时间 $T$：$X_T$ 的完整写法是 $X_{T(\omega)}(\omega)$。这意味着，不同的样本路径 $\omega$ 会在不同的时间切片上被截取。你正在将时间 $t=5, t=100, t=10000$ 等不同时刻的数据缝合在一起组成一个新的随机变量 $X_T$。

由于无穷级数和积分交换次序必须满足严格的收敛条件，这种跨越不同时间切片的“缝合”操作，并不自然保证期望依然守恒。

两个约束条件的代数本质

在测度论中，证明 $E[X_T] = E[X_0]$ 的标准路径是引入截断停止时间 $T \wedge n = \min(T, n)$。由于 $T \wedge n$ 有界，必定有 $E[X_{T \wedge n}] = E[X_0]$。

我们将 $X_{T \wedge n}$ 展开为两部分：

$$X_{T \wedge n} = X_T \mathbf{1}(T \le n) + X_n \mathbf{1}(T > n)$$

对两边取数学期望：

$$E[X_{T \wedge n}] = E[X_T \mathbf{1}(T \le n)] + E[X_n \mathbf{1}(T > n)]$$

已知左边恒等于 $E[X_0]$，所以：

$$E[X_0] = E[X_T \mathbf{1}(T \le n)] + E[X_n \mathbf{1}(T > n)]$$

现在，我们让 $n \to \infty$。我们的目标是证明等式右侧的极限等于 $E[X_T]$。

  1. 第一项 $E[X_T \mathbf{1}(T \le n)]$： 当 $n \to \infty$ 时，指示函数 $\mathbf{1}(T \le n) \to 1$。为了让这一项的极限收敛到 $E[X_T]$（即允许极限符号穿过期望积分号），根据勒贝格控制收敛定理 (Dominated Convergence Theorem)，随机变量 $X_T$ 自身必须是绝对可积的。这正是定理的 Condition 1: $E[|X_T|] < \infty$ 的来源。

  2. 第二项 $E[X_n \mathbf{1}(T > n)]$： 这是整个等式中最危险的误差项（Remainder term）。它代表了“当时间趋于无穷时，系统尚未停止的那部分路径，其当前状态值 $X_n$ 所造成的期望偏差”。 如果我们要得出 $E[X_0] = E[X_T]$ 的最终结论，这一个误差项的极限必须等于 $0$。这正是定理直接规定的 Condition 2: $\lim_{n \to \infty} E[|X_n| \mathbf{1}(T > n)] = 0$。

总结 OST 定理并不是在“选择推论”，它是在声明一个解析分析上的边界：随机变量的缝合 $X_T$ 会产生尾部误差。只有当系统结构能够保证这个尾部误差在无穷远处严格衰减为零时，鞅的期望守恒性质 $E[X_n] = E[X_0]$ 才能被无损地平移到 $E[X_T] = E[X_0]$ 上。

这是一个非常深刻的观察。在 Gambler’s Ruin（赌徒破产问题） 中，这个“尾部误差衰减为零”的性质体现得淋漓尽致，而且它正是依靠**“有界性（Boundedness）”**来强制实现的。

我们可以通过对比来理解：

1. 为什么在 Gambler’s Ruin 中它是成立的？

在你的例子中，游戏有两个硬边界：下限 $0$ 和上限 $c$。

  • 状态的有界性： 只要游戏还没结束（即 $T > n$），赌徒手里的钱 $X_n$ 就必须在 $0$ 和 $c$ 之间。因此，我们可以确定地写出：$|X_n| \le c$。
  • 误差项的放大率被锁死： 我们来看那个尾部误差项 $E[|X_n| \mathbf{1}(T > n)]$。 由于 $|X_n|$ 被常数 $c$ 封顶了，所以： $$E[|X_n| \mathbf{1}(T > n)] \le E[c \cdot \mathbf{1}(T > n)] = c \cdot P(T > n)$$
  • 概率的消失： 在一个有限区间内的随机游走，随着步数 $n$ 趋于无穷，你“既没输光也没赢够”的概率 $P(T > n)$ 会以指数级速度趋于 $0$。
  • 结论： 既然 $c$ 是个死数字，而 $P(T > n) \to 0$，那么乘积必然趋于 $0$。

这就是为什么在有界区间内，你可以放心大胆地使用 $E[X_T] = E[X_0]$。 系统结构（两个边界）保证了没有任何一条路径能在“不停止”的同时，还能把数值 $|X_n|$ 放大到足以抵消概率消失的速度。

2. 为什么在“必胜法”反例中它不成立？

对比一下那个反例：“赢到 1 块钱就走，不设止损（没有下限 0）”。

  • 状态的无界性： 虽然你最终“极大概率”能赢到 1 块钱，但在还没赢到 1 块钱的那些路径（$T > n$）里，赌徒可能已经输掉了几千、几万甚至天文数字。$|X_n|$ 在这里是没有上限的。
  • 误差项的爆炸： 虽然随着 $n$ 增大，还没赢到钱的概率 $P(T > n)$ 确实在变小，但是那些还在玩的路径，由于输得实在太惨，其数值 $|X_n|$ 增长的速度正好抵消了概率减小的速度。
  • 结论： 尾部误差项 $E[|X_n| \mathbf{1}(T > n)]$ 的极限不为 0（在这个特定例子中，它会趋向于一个常数，正好把你的期望从 0 顶到了 1）。

总结

在 Gambler’s Ruin 里，“上限 $c$”和“下限 $0$”就像两堵墙，把随机过程强行关进了一个笼子。 因为 $|X_n|$ 被关住了，它就没法在 $n \to \infty$ 时“搞事情”。所有的能量都被限制在有限范围内，随着时间推移，还在笼子里晃荡的概率不断归零，误差也就随之消失了。