飞船空间跳跃问题
本文的问题出自 Williams 的教材 Probability with Martingales，虽然不算很难但是综合使用了许多知识，展示了抽象的鞅理论其实有着丰富多彩的应用。
问题：一艘太空船正在宇宙中做星际航行时，飞船的控制系统出了故障，飞船不能正常地进行空间跳跃，而是只能预先设定一个距离，然后以此距离进行一次方向完全随机的跳跃。现在飞船想要返回太阳系。假设太阳系的半径是 \(r\)，发生故障时飞船与太阳的距离为 \(R>r\)。好消息是在每个时刻，飞船能够知道自身与太阳系的距离。
求证：不论采用怎样的跳跃策略，飞船返回太阳系的概率都小于 \(r/R\)；但是对任何 \(\epsilon>0\)，可以采取适当的策略，使得飞船返回太阳系的概率大于 \((r-\epsilon)/R\)，即 \(r/R\) 是最优概率。这个最优策略是什么？
预备知识
条件期望的预备知识
通常的条件期望是用 Radon-Nikodym 导数定义的，这个定义有时候用起来并不方便。譬如设 \(X,Y\) 是两个随机变量，如果事件 \(\{X=x\}\) 是零概率事件，那么我们不能对它取条件概率；但是在已知 \(X=x\) 的前提下，期望值 \(f(x)=\mathbb{E}[Y|X=x]\) 常常是有直观的概率意义的，即给定 \(X\) 的值 \(x\)，\(Y\) 的期望值是 \(f(x)\)，于是直观上应该有 \(\mathbb{E}[Y|X]=f(X)\)。但是怎么说明这个直观上的条件期望与抽象的条件期望一致呢？这就是下面的 freezing lemma: （见 Williams 教材 9.10 小节，或者 Durrett 概率论 4.1 小节）
引理 1：设 \((\Omega,\mathcal{F},\mu)\) 是一个概率空间，\(X, Y\) 是两个取值在某可测空间 \((S,\mathcal{S})\) 中的随机变量，子 \(\sigma\) 域 \(\mathcal{G}\subseteq\mathcal{F}\) 满足 \(X\in\mathcal{G}\) 且 \(\mathcal{G}\) 与 \(Y\) 独立。可测函数 \(\varphi: S\times S\to\mathbb{R}\) 满足 \(\varphi\) 非负或者 \(\mathbb{E}|\varphi(X, Y)|<\infty\)。令 \(g(x)=\mathbb{E}\varphi(x, Y)\)，则 \[\mathbb{E}[\varphi(X, Y)|\mathcal{G}]=g(X).\]
我们举个例子：假设 \(X, Y\) 是两个独立的随机变量，\(Y\) 服从的是 \([0, 1]\) 上的均匀分布，\(X\) 服从的分布我们可以不用关心。问条件期望 \(\mathbb{E}[\sin(XY)|X]\) 是什么？这相当于在引理中取 \(\varphi(X,Y)=\sin(XY)\) 和 \(\mathcal{G}=\sigma(X)\)。引理告诉我们可以把 \(\sin(XY)\) 中的 \(X\) 冻结为常数 \(X=x\)，把 \(\mathbb{E}[\sin(XY)|X]\) 视作关于常数 \(x\) 的积分 \[\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\) 即得 \[\mathbb{E}[\sin(XY)|X] = \frac{1-\cos X}{X}.\]
引理中的可测空间 \((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)\) 独立，那么条件期望 \(\mathbb{E}[\varphi(X,Y)|\mathcal{G}]\) 就是一个以 \((x_1,\ldots,x_n)\) 为参变元的多重积分 \[\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-\) 系。根据可测函数的单调类定理 （见 Durrett 概率论第四版定理 6.1.3 或 Williams 教材附录 3），结论对所有非负或者可积函数都成立。
分析的预备知识
引理 2：设 \(B=B(A,R)\) 是 \(\mathbb{R}^3\) 中以点 \(A\) 为中心，半径为 \(R\) 的球，\(X\) 是球面上均匀分布的随机点，则 \(X\) 与原点 \(O\) 之间距离倒数的期望为 \[\mathbb{E}\frac{1}{|X|}=\begin{cases}1/a & a>R,\\ 1/R & a\leq R.\end{cases}\] 其中 \(a=|A|\) 是 \(A\) 与原点之间的距离。
这个引理其实是我们都熟悉的高中物理知识：假设以 \(A\) 为中心，半径为 \(R\) 的球壳上有总量为 1 的均匀分布的电荷，则球壳表面和内部的电势处处等于 \(1/R\)，球壳外部任意一点 \(P\) 的电势等于 \(P\) 和球心距离的倒数，即 \(1/|P-A|\)（不计物理常数），此即为结论。
当然这不是一个严格的证明，实际上这个积分正是 Newton 势函数的简单情形。由于这不是本文的重点，就不再展开讲了，读者可以参考下面的文献：
Donoghue, William F. Distributions and Fourier transforms. Vol. 32. Academic Press, 2014.
证明在第八章可以找到。
建立模型
初始时刻设为 0，太阳系是以原点为圆心，半径为 \(r\) 的球体，飞船初始位置在 \((R,0,0)\) 处。
设 \(\{U_n\}_{n\geq 1}\) 是定义在某个概率空间 \((\Omega,\mathcal{F},\mathbb{P})\) 上的一组独立同分布的、在单位球面上均匀分布的随机向量，它们表示飞船每次空间跳跃的随机方向。并设 \(\mathcal{F}_n=\sigma(U_1,\ldots,U_n)\) 以及 \(\mathcal{F}_0=(\Omega,\emptyset)\)。
设第 \(n\) 次空间跳跃的距离为 \(l_n(n\geq1)\)，因为在第 \(n\) 次空间跳跃时要根据以前的信息来决定第 \(n\) 次的跳跃距离，所以 \(l_n\) 关于 \(\mathcal{F}_{n-1}\) 可测。
于是若设第 \(n\) 次空间跳跃后飞船的坐标为 \(X_n\)，那么 \[X_n=X_{n-1} + l_n U_n.\quad n=1,2,\ldots.\] 其中 \(X_0=(R,0,0)\) 是飞船的初始位置。
设 \(T\) 是飞船首次返回太阳系的时间： \[T = \inf\ \{ n:|\ 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 和关于 Newton 势的引理 2 得到
\[ \mathbb{E}\left[\left.\frac{1}{R_n}\right|\mathcal{F}_{n-1}\right] =\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\}\) 关于 \(\{\mathcal{F}_n\}\) 构成一个上鞅 （与策略无关）。特别地如果跳跃距离总是不超过当前飞船与太阳系的距离，即对任何 \(n\geq1\) 有 \(l_n\leq R_{n-1}\)，则 \(\{1/R_n\}\) 还是一个鞅。
证明：只要再说明每个 \(1/R_n\) 是可积的随机变量即可。由于 \(1/R_n\) 是非负的随机变量因此 \(\mathbb{E}[1/R_n|\mathcal{F}_{n-1}]\) 是有定义的且已经证明其小于等于 \(1/R_{n-1}\)，于是 \[\mathbb{E}[1/R_n]=\mathbb{E}[\mathbb{E}[1/R_n|\mathcal{F}_{n-1}]]\leq\mathbb{E}[1/R_{n-1}],\] 所以对 \(n\) 归纳即可。
定理 1 是解决整个问题最关键的一步，有了它就海阔天空，没有它就寸步难行。由它我们立刻可以导出一个有趣的观察：由于非负上鞅总是几乎处处收敛的，因此定理 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\)。所以飞船要么飞向无穷远，即迷失在宇宙的深处，要么被吸引到某个有限的位置。
现在我们可以证明：
定理 2：不论飞船采取怎样的策略，返回太阳系的概率都严格小于 \(r/R\)。
证明只用到非常基础的鞅的知识：
设 \(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 引理有 \[\mathbb{E}[\lim_{n\to\infty}Z_{T\wedge n}]\leq\varliminf_{n\to\infty}\mathbb{E}[Z_{T\wedge n}]\leq \mathbb{E}[Z_0]=\frac{1}{R}.\] 另一方面
\[ \begin{align*} \mathbb{E}[\lim_{n\to\infty}Z_{T\wedge n}]&=\mathbb{E}[Z_T\mathbb{1}_{\{T<\infty\}}]+\mathbb{E}[\lim_{n\to\infty}Z_n\mathbb{1}_{\{T=\infty\}}] \\&\geq \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\) 的，我们只要证明上面式子的最后一个不等号是严格成立的： \[\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) =\mathbb{E}[\mathbb{1}_{A_n}]=\mathbb{E}[\mathbb{E}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]]\)，我们只要证明 \(\mathbb{E}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]\) 是几乎处处为 0 的即可。而根据 freezing lemma， \[\mathbb{E}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]=\mathbb{E}[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\bigg|\mathcal{F}_{n-1}]=\mathbb{E}\left[\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\right].\] 其中上式最右边的期望是对单位球面上均匀分布的 \(U_n\) 进行积分。
根据归纳假设 \(|X_{n-1}|\in\{0,r\}\) 的概率是 0，而修改一个零测集上的值对条件期望没有影响，所以在上面对 \(U_n\) 的积分中可以不考虑这部分点，只看 \(|X_{n-1}|\ne 0,r\) 的情形。这时以 \(X_{n-1}\) 为中心，半径为 \(l_n\geq0\) 的球面上的随机点与原点距离等于 0 或 \(r\) 的概率是 0，即 \(\mathbb{1}_{\{0,r\}}\circ |X_{n-1}+l_nU_n|\) 是一个单位球面上几乎处处为 0 的函数，其积分当然也是 0，于是 \(\mathbb{E}[\mathbb{1}_{A_n}|\mathcal{F}_{n-1}]=0\)，从而结论得证。
对策略的进一步分析
现在我们把注意力转移到飞船不能返回太阳系这个事件上来。前面已经说过，飞船的运动只有两种可能，迷失在无穷远处或者被禁锢在一个有限的区域内，所以如果飞船不能返回太阳系，则飞船要么飞向无穷远，要么在太阳系之外的一个有限区域内打转。我们想知道，怎么判断这两种情形哪一种会发生呢？
举个例子，考虑这样一个明显不合理的策略：第 \(n\) 次的跳跃距离总是设定为 \(1/2^n\)，在这个策略下飞船永远飞不出一个半径为 1 的空间，所以这种策略是应该避免的。
你可以注意到这个糟糕的策略的问题出在跳跃距离之和是收敛的。如果我们强迫每次跳跃的距离都大于一个固定的值 \(\epsilon\)（\(\epsilon\) 可以是任意的正数），就可以避免这种情形出现，这就是下面的定理：
定理 3：设 \(\epsilon\) 是任一正数 \[E:=\{\omega:\ T(\omega)=\infty,\ l_n(\omega)\geq\epsilon,\ \forall n\geq1\},\] 则我们有 \[\lim_{n\to\infty} R_n=+\infty,\quad \text{for a.e.}\ \omega\in E.\]
定理 3 的证明也很有趣，同时使用了几何和概率两方面的知识。
设 \(\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 啦）
\[ \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}] &= \mathbb{E}[\mathbb{1}_A\mathbb{1}_B] = \mathbb{E}[\mathbb{E}[\mathbb{1}_A\mathbb{1}_B|\mathcal{F}_{n_k-1}]]\\&=\mathbb{E}[\mathbb{1}_A\mathbb{E}[\mathbb{1}_B|\mathcal{F}_{n_k-1}]]\\&=\frac{1}{4}\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\)，也知道只要策略得当，就可以避免飞船在原地打转的糟糕情况。接下来的问题是：最好的策略到底是什么？
定理 4：定义如下的跳跃策略：在准备第 \(n\) 次跳跃时，如果飞船已经在太阳系内，则令 \(l_n=0\)，否则令 \(l_n=R_{n-1}-r+\epsilon\)，这里 \(0<\epsilon<r\)。在这个跳跃策略下，飞船返回太阳系的概率大于 \((r-\epsilon)/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 证明的重复：
这次根据控制收敛定理有 \[\mathbb{E}[\lim_{n\to\infty}Z_{T\wedge n}]=\lim_{n\to\infty}\mathbb{E}[Z_{T\wedge n}]=\mathbb{E}[Z_0]=\frac{1}{R}.\] 另一方面 \[\mathbb{E}[\lim_{n\to\infty}Z_{T\wedge n}]=\mathbb{E}[Z_T\mathbb{1}_{\{T<\infty\}}]+\mathbb{E}[\lim_{n\to\infty}Z_n\mathbb{1}_{\{T=\infty\}}].\] 这个时候要注意到在 \(\{T=\infty\}\) 上总是有 \(l_n\geq\epsilon\)，因此根据定理 3 的结论，飞船几乎必然飞向无穷远，即 \[\lim_{n\to\infty}Z_n=0,\quad \omega\in\{T=\infty\}.\] 所以 \[\mathbb{E}[\lim_{n\to\infty}Z_{T\wedge n}]=\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\)。