使用鞅（Martingale）的早停方法解决赌徒破产问题

题干

非对称随机游走过程的一个实现

对于一个（不对称的）随机游走过程 $S_n=\sum_{i=0}^n X_i$ ，其中 $X_1,\cdots,X_n$ 为离散的独立同分布随机变量，服从以下变化：

$X_i=\left\{\begin{array} \\ 1 & \text{with probability $p$} \\ -1 & \text{with probability $q:=1-p$} \end{array}\right.,\qquad p\neq q,\;\;p+q=1$

假设过程初始在零点，即 $S_0=0$ ；假设两个边界 $\alpha<0<\beta$ ，若过程在某一时刻 $\tau$ 接触到任意一条边界则停止，请问过程停止于边界 $\alpha$ 的概率 $p_a:=\mathbb{P}(X_\tau=\alpha)$ 是多少。

注意： 区分随机过程的上升概率 $p$ 以及停止于边界的概率 $p_a,p_\beta$ 。

题解

针对赌徒破产问题有许多种不同的求解方法，这里我们将介绍其中一种使用鞅（Martingale）的方法。对于题干所述的随机过程 $S_n$ ，很明显由于限定 $p\neq q$ ， $S_n$ 自身并不是一个鞅。对于此类非对称随机游走过程而言，我们发现 $M_n:=\left(\frac{q}{p}\right)^{S_n}$ 是一个期望为 $1$ 的鞅，具体证明过程如下：

$\begin{aligned} \mathbb{E}[M_{n+1}|\mathcal{F}_n] &= \mathbb{E}\left[ \left( \frac{q}{p} \right)^{S_{n+1}} |\mathcal{F}_n \right] \\ \\ &= \mathbb{E}\left[ \left( \frac{q}{p} \right)^{S_{n}}\left( \frac{q}{p} \right)^{X_{n+1}} |\mathcal{F}_n \right] \\ \\ &= \left( \frac{q}{p} \right)^{S_{n}}\mathbb{E}\left[ \left( \frac{q}{p} \right)^{X_{n+1}} |\mathcal{F}_n \right],&\text{在可测集$\mathcal{F}_n$的信息下，$S_n$为已知量} \\ \\ &= \left( \frac{q}{p} \right)^{S_{n}} \left[ p\left( \frac{q}{p} \right)^{+1}+q\left( \frac{q}{p} \right)^{-1} \right] \\ \\ &= \left( \frac{q}{p} \right)^{S_{n}}\underset{=1}{\left[ q+p \right]} \\ \\ &= \left( \frac{q}{p} \right)^{S_{n}} =: M_n&\hfill\square \end{aligned}$

同样可知 $M_0=\left(\frac{q}{p}\right)^0=1$ ，即 $M_n$ 为一个期望为 $1$ 的鞅。根据可选停时定理（Optional Stopping Theorem），一个早停（Early Stopped）的鞅依然具有同样的期望。我们设 $\tau$ 为 $S_n$ 接触到 $\alpha$ 或 $\beta$ 的步数，则有：

$\begin{aligned} \mathbb{E}[M_\tau] = p_\alpha M_\tau|_{S_n=\alpha} + p_\beta M_\tau|_{S_n=\beta} &\overset{!}{=} 1 \\ \\ p_\alpha \left( \frac{q}{p} \right)^\alpha + (1-p_\alpha)\left( \frac{q}{p} \right)^\beta &= 1 \\ \\ p_\alpha\left( \left( \frac{q}{p} \right)^a - \left( \frac{q}{p} \right)^\beta \right) &= 1 - \left( \frac{q}{p} \right)^\beta \\ \\ p_a &= \frac{1 - \left( \frac{q}{p} \right)^\beta}{\left( \frac{q}{p} \right)^a - \left( \frac{q}{p} \right)^\beta}&\hfill\square \end{aligned}\tag{1.1}$

同理可根据 $p_\alpha+p_\beta=1$ 得出 $p_\beta$ 。

注意： 该结论只用于非对称随机游走，即 $p\neq q$ 的情况。对于对称随机游走（ $p=q$ ），我们发现公式 $1.1$ 的结果是未定义的（分母为零）。针对这种情况，直接使用 $S_n$ 为鞅的性质，并同样应用可选时停定理即可得 $p_\alpha=\frac{\beta}{\beta-\alpha}$ 。

参考

"Martingale Theory and Applications" by Dr Nic Freeman
https://zhuanlan.zhihu.com/p/345820722

如有错误欢迎指出，感谢。

使用鞅（Martingale）的早停方法解决赌徒破产问题

题干

题解

参考

推荐阅读更多精彩内容