本文的问题出自 Williams 的教材 Probability with Martingales，虽然不算很难但是综合使用了许多知识，展示了抽象的鞅理论其实有着丰富多彩的应用。

预备知识

条件期望的预备知识

设 \(X,Y\) 是两个随机变量，\(\varphi\) 是可测函数。我们考虑条件期望 \(\mathop{\mathrm{\mathbb{E}}}[\varphi(X,Y)|X]\)，这是一个关于 \(\sigma(X)\) 可测的随机变量，根据 Doob-Dynkin 引理，它可以写成 \[\mathop{\mathrm{\mathbb{E}}}[\varphi(X,Y)|X]=g(X)\] 的形式，其中 \(g\) 是一个 Borel 可测函数。但是这个 \(g\) 具体是什么呢？下面的 freezing lemma (Williams 1991, sec. 9.10) or (Durrett 2019, sec. 4.1) 告诉我们，在一定条件下我们可以先将 \(X\) 冻结为一个实数值 \(x\)，上式的右边变成 \(g(x)\)，左边变成 \(\{X=x\}\) 条件下的期望 \[\mathop{\mathrm{\mathbb{E}}}[\varphi(X,Y)|X=x]=\mathop{\mathrm{\mathbb{E}}}\varphi(x,Y).\] 即 \(g(x)=\mathop{\mathrm{\mathbb{E}}}\varphi(x,Y)\)。这就找到了 \(g\) 的表达式。

我们举个例子：假设 \(X, Y\) 是两个独立的随机变量，\(Y\) 服从的是 \([0, 1]\) 上的均匀分布，\(X\) 服从的分布我们可以不用关心。问条件期望 \(\mathop{\mathrm{\mathbb{E}}}[\sin(XY)|X]\) 是什么？这相当于在引理中取 \(\varphi(X,Y)=\sin(XY)\) 和 \(\mathcal{G}=\sigma(X)\)。引理 1.1 告诉我们可以把 \(\sin(XY)\) 中的 \(X\) 冻结为常数 \(X=x\)，把 \(\mathop{\mathrm{\mathbb{E}}}[\sin(XY)|X]\) 视作关于常数 \(x\) 的积分 \[\mathop{\mathrm{\mathbb{E}}}[\sin(xY)]=\int_0^1 \sin(xy)\,\mathrm{d}y = \frac{1}{x}\int_0^x \sin(z)\,\mathrm{d}z=\frac{1-\cos x}{x}.\] 然后把 \(x\) 解冻为 \(X\) 即得 \[\mathop{\mathrm{\mathbb{E}}}[\sin(XY)|X] = \frac{1-\cos X}{X}.\]

引理 1.1 中的可测空间 \((S,\mathcal{S})\) 可以是多维空间 \((\mathbb{R}^d,\mathcal{B}(\mathbb{R}^d))\)，\(X,Y\) 也可以是独立的随机向量。即如果 \(\varphi(X_1,\ldots,X_n,Y_1,\ldots,Y_m)\) 是关于随机变量的可测函数，\(\sigma(X_1,\ldots,X_n)\subset\mathcal{G}\) 并且 \(\mathcal{G}\) 和 \(\sigma(Y_1,\ldots,Y_m)\) 独立，那么条件期望 \(\mathop{\mathrm{\mathbb{E}}}[\varphi(X,Y)|\mathcal{G}]\) 就是一个以 \((x_1,\ldots,x_n)\) 为参变元的多重积分 \[\mathop{\mathrm{\mathbb{E}}}[\varphi(x_1,\ldots,x_n,Y_1,\ldots,Y_m)]=g(x_1,\ldots,x_n).\]

证明：我们要证明对任何可测集 \(C\in\mathcal{G}\) 有

\[\int_C \varphi(X, Y)\mathrm{d}\mu = \int_C g(X)\mathrm{d}\mu.\] 当 \(\varphi(x, y)=\mathbb{1}_A(x)\mathbb{1}_B(y)\) 时，\(g(x)=\mathbb{1}_A(x)\mathbb{P}(\{Y\in B\})\)，从而 \[\begin{align*}\int_C \mathbb{1}_A(X)\mathbb{1}_B(Y)\mathrm{d}\mu&=\mathbb{P}(\{X\in A\}\cap C\cap\{Y\in B\})\\&=\mathbb{P}(\{X\in A\}\cap C)\cdot\mathbb{P}(\{Y\in B\})\\&=\int_C\mathbb{1}_A(X)\mathrm{d}\mu\cdot\mathbb{P}(\{Y\in B\})\\&=\int_C g(X)\mathrm{d}\mu.\end{align*}\]

于是结论对所有形如 \(A\times B\) 的集合的示性函数成立。这些函数构成一个 \(\pi-\) 系。根据可测函数的单调类定理 (monotone class theorem)，结论对所有非负或者可积函数都成立。

分析的预备知识

这个引理其实是我们都熟悉的高中物理知识：假设以 \(A\) 为中心，半径为 \(R\) 的球壳上有总量为 1 的均匀分布的电荷，则球壳表面和内部的电势处处等于 \(1/R\)，球壳外部任意一点 \(P\) 的电势等于 \(P\) 和球心距离的倒数，即 \(1/|P-A|\)（不计物理常数），此即为结论。

当然这不是一个严格的证明，实际上这个积分正是 Newton 势函数的简单情形。由于这不是本文的重点，就不再展开讲了，读者可以参考 (Donoghue 2014, chap. 8)。

建立模型

1. 初始时刻为 0，太阳系是以原点为圆心，半径为 \(r\) 的球，飞船初始位置在 \((R,0,0)\) 处。

2. 设 \(\{U_n\}_{n\geq 1}\) 是定义在某个概率空间 \((\Omega,\mathcal{F},\mathbb{P})\) 上的一组独立同分布的、在单位球面上均匀分布的随机向量，它们表示飞船每次空间跳跃的随机方向。并设 \(\mathcal{F}_n=\sigma(U_1,\ldots,U_n)\) 以及 \(\mathcal{F}_0=(\Omega,\emptyset)\)。

3. 设第 \(n\) 次空间跳跃的距离为 \(l_n(n\geq1)\)，由于 \(l_n\) 是根据 \(n\) 时刻之前的信息决定的，所以 \(l_n\) 关于 \(\mathcal{F}_{n-1}\) 可测。

4. 设第 \(n\) 次空间跳跃后飞船的坐标为 \(X_n\)，那么 \[X_n=X_{n-1} + l_n U_n.\quad n=1,2,\ldots.\] 其中 \(X_0=(R,0,0)\) 是飞船的初始位置。

5. 设 \(T\) 是飞船首次返回太阳系的时间： \[T = \inf\,\{ n\mid X_n\in B(0,r)\},\]则 \(T\) 的取值范围是 \(\mathbb{N^+}\cup\{+\infty\}\)。我们要估算的是事件 \(\{T<+\infty\}\) 的概率，这正是飞船能够在有限时间内回到太阳系的概率。

现在我们着手研究一下飞船的运动规律。

设 \(R_n\) 为第 \(n\) 次跳跃以后飞船与太阳系的距离，\(R_0=R\)，我们想知道 \(R_n\) 和 \(R_{n+1}\) 之间的关系。

对 \(\mathcal{F}=\mathcal{F}_n,\,\mathcal{G}=\mathcal{F}_{n-1},\,X=(X_{n-1},l_n),\,Y=U_n,\,\varphi(X, Y)=1/|X_{n-1}+l_nY|\) 应用前面的关于条件期望的 引理 1.1 和 引理 1.2 得到

\[ \mathop{\mathrm{\mathbb{E}}}\left[\left.\frac{1}{R_n}\right|\mathcal{F}_{n-1}\right] =\mathop{\mathrm{\mathbb{E}}}\left.\frac{1}{\left|X_{n-1}+ l_nU_n\right|}\right|_{X_{n-1}=A}\leq\frac{1}{|A|}=\frac{1}{R_{n-1}}. \]

这里由于 \(X_{n-1}\) 和 \(l_n\) 都是关于 \(\mathcal{F}_{n-1}\) 可测的，而 \(U_n\) 和 \(\mathcal{F}_{n-1}\) 是独立的，所以应用 引理 1.1 的条件是满足的。

总结一下：

证明：只要再说明每个 \(1/R_n\) 是可积的随机变量即可。由于 \(1/R_n\) 是非负的随机变量因此 \(\mathop{\mathrm{\mathbb{E}}}[1/R_n|\mathcal{F}_{n-1}]\) 是有定义的且已经证明其小于等于 \(1/R_{n-1}\)，于是 \[\mathop{\mathrm{\mathbb{E}}}[1/R_n]=\mathop{\mathrm{\mathbb{E}}}[\mathop{\mathrm{\mathbb{E}}}[1/R_n|\mathcal{F}_{n-1}]]\leq\mathop{\mathrm{\mathbb{E}}}[1/R_{n-1}],\] 所以对 \(n\) 归纳即可。

定理 2.1 是解决整个问题最关键的一步，有了它就海阔天空，没有它就寸步难行。由它我们立刻可以导出一个有趣的观察：由于非负上鞅总是几乎处处收敛的，因此 定理 2.1 的结论蕴含 \(\lim\limits_{n\to\infty}R_n(\omega)\) 是几乎处处存在的（可以是正无穷），而这有两种可能：\(\lim\limits_{n\to\infty}R_n(\omega)=+\infty\) 或者 \(\lim\limits_{n\to\infty}R_n(\omega)=a<+\infty\)。所以飞船要么飞向无穷远，即迷失在宇宙的深处，要么被吸引到某个有限的位置。

现在我们可以证明：

证明只用到非常基础的鞅的知识：

设 \(Z_n=1/R_n\)，则 \(\{Z_n\}\) 是一个非负上鞅，所以 \(Z_\infty=\lim\limits_{n\to\infty}Z_n\) 是几乎处处存在的。考虑由停时 \(T\) 截断得到的非负上鞅序列 \(\{Z_{T\wedge n}\}\)，这个上鞅序列也是几乎处处收敛的，其中 \[\lim_{n\to\infty}Z_{T\wedge n} = \begin{cases}\lim_{n\to\infty}Z_n& T=\infty,\\ Z_T& T<\infty.\end{cases}\] 一方面根据非负可积函数列的 Fatou 引理有 \[\mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_{T\wedge n}]\leq\varliminf_{n\to\infty}\mathop{\mathrm{\mathbb{E}}}[Z_{T\wedge n}]\leq \mathop{\mathrm{\mathbb{E}}}[Z_0]=\frac{1}{R}.\] 另一方面

\[ \begin{align*} \mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_{T\wedge n}]&=\mathop{\mathrm{\mathbb{E}}}[Z_T\mathbb{1}_{\{T<\infty\}}]+\mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_n\mathbb{1}_{\{T=\infty\}}] \\&\geq \mathop{\mathrm{\mathbb{E}}}[Z_T \mathbb{1}_{\{T<\infty\}}]\geq\frac{\mathbb{P}(T<\infty)}{r}.\end{align*} \]

其中最后一个不等号是因为 \(Z_T\geq 1/r\)。综合这两个不等式就得到了 \(\mathbb{P}(T<\infty)\leq r/R\)，即任何策略下飞船最终返回太阳系的概率不大于 \(r/R\)。

要证明这个概率是严格小于 \(r/R\) 的，我们只要证明上面式子的最后一个不等号是严格成立的： \[\mathop{\mathrm{\mathbb{E}}}[Z_T \mathbb{1}_{\{T<\infty\}}]>\frac{\mathbb{P}(T<\infty)}{r}.\]

当然需要假定这里的 \(\{T<\infty\}\) 有正概率 （返回概率是 0 的话当然小于 \(r/R\)，没什么好证的）。为此只要证明在事件 \(\{T<\infty\}\) 上几乎处处有 \(Z_T>1/r\)，即 \(R_T<r\) 即可。

我们来证明对每个 \(n\geq0\)，事件 \(A_n=\{R_n\in\{0,r\}\}\) 都是零概率事件。

对 \(n\) 归纳：\(n=0\) 时 \(R_0=R>r\)，结论自然成立。设当 \(k<n\) 时有 \(\mathbb{P}(A_k)=0\)，来看 \(k=n\) 的情形。

由于 \(\mathbb{P}(A_n) =\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_{A_n}]=\mathop{\mathrm{\mathbb{E}}}[\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]]\)，我们只要证明 \(\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]\) 是几乎处处为 0 的即可。而根据 freezing lemma， \[\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]=\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\bigg|\mathcal{F}_{n-1}]=\mathop{\mathrm{\mathbb{E}}}\left[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\right].\] 其中上式最右边的期望是对单位球面上均匀分布的 \(U_n\) 进行积分，结果是一个关于 \(X_{n-1}\) 的函数。

• 如果 \(|X_{n-1}|\in\{0,r\}\)，显然无论如何上式右边的期望取值在 \([0,1]\) 中。
• 如果 \(|X_{n-1}|\notin\{0,r\}\)，这时以 \(X_{n-1}\) 为中心，\(l_n\) 为半径的球面上，与原点之间的距离为 \(0\) 或者 \(r\) 的点的测度为 0，即积分项 \(\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\) 对几乎处处的 \(U_n\) 都是 0，当然积分值 \(\mathop{\mathrm{\mathbb{E}}}\left[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\right]=0\)。

于是我们有 \[\mathop{\mathrm{\mathbb{E}}}\left[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\right]= \begin{cases} \in[0,1], & |X_{n-1}|\in\{0,r\}\\ 0, & |X_{n-1}|\notin\{0,r\} \end{cases}\]

根据归纳假设，\(|X_{n-1}|\in\{0,r\}\) 的概率是 0，即 \(\mathop{\mathrm{\mathbb{E}}}\left[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\right]\) 是一个几乎处处为 0 的函数，从而 \(\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]\) 也几乎处处为 0，即得所证。

对策略的进一步分析

现在我们把注意力转移到飞船不能返回太阳系这个事件上来。前面已经说过，飞船的运动只有两种可能，迷失在无穷远处或者被禁锢在一个有限的区域内，所以如果飞船不能返回太阳系，则飞船要么飞向无穷远，要么在太阳系之外的一个有限区域内打转。我们想知道，怎么判断这两种情形哪一种会发生呢？

举个例子，考虑这样一个明显不合理的策略：第 \(n\) 次的跳跃距离总是设定为 \(1/2^n\)，在这个策略下飞船永远飞不出一个半径为 1 的空间，所以这种策略是应该避免的。

你可以注意到这个糟糕的策略的问题出在跳跃距离之和是收敛的。如果我们强迫每次跳跃的距离都大于一个固定的值 \(\epsilon\)（\(\epsilon\) 可以是任意的正数），就可以避免这种情形出现，这就是下面的定理：

证明：设 \(\theta_n\) 为 \(X_{n-1}\) 与 \(U_n\) 之间的夹角，利用关系 \(X_n=X_{n-1}+l_nU_n\) 以及三角形的余弦公式可得 \[R_n^2=R_{n-1}^2+l_n^2+2R_{n-1}l_n\cos\theta_n.\] 令 \(B_n=\{\cos\theta_n\geq 1/2\}\)，则在事件 \(B_n\) 上我们有

\[R_n^2\geq R_{n-1}^2+l_n^2+R_{n-1}l_n\geq(R_{n-1}+l_n/2)^2.\] 结合在事件 \(E\) 上有 \(l_n\geq\epsilon\)，于是在事件 \(B_n\cap E\) 上有 \[R_n\geq R_{n-1}+l_n/2\geq R_{n-1}+\epsilon/2,\quad\omega\in B_n\cap E.\] 如果我们能证明 \(\mathbb{P}(\{B_n\ \text{i.o.}\})=1\)，再排除掉使得 \(R_n(\omega)\) 不收敛的零测集，则对几乎处处的 \(\omega\in E\) 都有 \(R_n\geq R_{n-1}+\epsilon/2\) 对无穷多个 \(n\) 成立。对这些 \(\omega\)，\(R_n\) 是不可能收敛到一个有限的点的，只能是 \(\lim\limits_{n\to\infty}R_n(\omega)=\infty\)，这就说明飞船在 \(E\) 上几乎处处飞向无穷远。

为了证明 \(\mathbb{P}(\{B_n\ \text{i.o.}\})=1\)，我们只要证明 \(\{B_n\}\) 是独立的事件列，且对每个 \(n\) 有 \(\mathbb{P}(B_n)=\frac{1}{4}\)，这样由 Borel-Cantelli 第二引理就得到了结论。

注意到（又用到 引理 1.1 啦）

\[ \begin{align*} \mathbb{P}[B_n| \mathcal{F}_{n-1}] &= \mathbb{P}[\cos(U_n, v)\geq 1/2] \bigg|_{v=X_{n-1}} \\&= \mathbb{P}[U_n\in \{(x,y,z)\in\mathbb{R}^3:\ z\geq 1/2\}]\\&=\frac{1}{4}.\end{align*} \]

于是对任何一组下标 \(n_1<n_2<\cdots<n_k\)，记 \(A=B_{n_1}\cap\cdots\cap{B_{n_{k-1}}}\) 以及 \(B=B_{n_k}\)，并注意到由于 \(n_{k-1}\leq n_k-1\) 因此 \(A\in\mathcal{F}_{n_k-1}\)，所以

\[\begin{align*}\mathbb{P}[B_{n_1}\cap\cdots\cap B_{n_k}] &= \mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_A\mathbb{1}_B] = \mathop{\mathrm{\mathbb{E}}}[\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_A\mathbb{1}_B|\mathcal{F}_{n_k-1}]]\\&=\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_A\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_B|\mathcal{F}_{n_k-1}]]\\&=\frac{1}{4}\mathop{\mathrm{\mathbb{E}}}[\mathbb{1}_A]\\&=\frac{1}{4}\mathbb{P}(B_{n_1}\cap\cdots\cap B_{n_{k-1}}).\end{align*}\]

从而由递推可见对每个 \(n\) 都有 \(\mathbb{P}(B_n) =\frac{1}{4}\) 且它们是互相独立的。

最优策略

现在我们已经知道飞船返回太阳系的概率总是小于 \(r/R\)，也知道只要策略得当，就可以避免飞船在原地打转的糟糕情况。接下来的问题是：最好的策略到底是什么？

注意在这个策略中总是有 \(l_n<R_{n-1}\)，因此 \(\{Z_n=1/R_n\}\) 实际上是一个鞅。此外由于总是有 \(R_n\geq r-\epsilon\)，所以 \(Z_n\leq1/(r-\epsilon)\)，即 \(\{Z_n\}\) 被常数 \(1/(r-\epsilon)\) 所控制。

接下来的证明不过是 定理 2.2 证明的重复：

这次根据控制收敛定理有 \[\mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_{T\wedge n}]=\lim_{n\to\infty}\mathop{\mathrm{\mathbb{E}}}[Z_{T\wedge n}]=\mathop{\mathrm{\mathbb{E}}}[Z_0]=\frac{1}{R}.\] 另一方面 \[\mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_{T\wedge n}]=\mathop{\mathrm{\mathbb{E}}}[Z_T\mathbb{1}_{\{T<\infty\}}]+\mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_n\mathbb{1}_{\{T=\infty\}}].\] 这个时候要注意到在 \(\{T=\infty\}\) 上总是有 \(l_n\geq\epsilon\)，因此根据 定理 3.1 的结论，飞船几乎必然飞向无穷远，即 \[\lim_{n\to\infty}Z_n=0,\quad \omega\in\{T=\infty\}.\] 所以 \[\mathop{\mathrm{\mathbb{E}}}[\lim_{n\to\infty}Z_{T\wedge n}]=\mathop{\mathrm{\mathbb{E}}}[Z_T\mathbb{1}_{\{T<\infty\}}]\leq\frac{1}{r-\epsilon}\mathbb{P}(T<\infty).\] 综合两个式子就证明了 \(\mathbb{P}(T<\infty)\geq(r-\epsilon)/R\)。

References

上一篇：洛奇绵羊问题

下一篇：中心单代数的三个基本结论