首页 > 代码库 > 飞船空间跳跃问题
飞船空间跳跃问题
一艘太空船正在宇宙中做星际航行时，飞船的控制系统出了故障，飞船不能正常地进行空间跳跃，而是只能预先设定一个距离，然后以此距离进行一次方向完全随机的跳跃。现在的问题是飞船想要返回太阳系。假设太阳系的半径是 $r$，发生故障时飞船与太阳的距离为 $R$，这里 $R>r$。在每个时刻，飞船能够知道自身与太阳系的距离。
求证：不论采用怎样的跳跃策略，飞船返回太阳系的概率都小于 $r/R$；但是对任何 $\epsilon>0$，可以采取适当的策略，使得飞船返回太阳系的概率大于 $(r-\epsilon)/R$，即 $r/R$ 是最优概率。这个最优策略是什么？
这个有趣的问题来自 Williams 的教材 "Probability with Martingales"，和本系列的其它文章一样，展示了抽象的鞅理论其实有着丰富多彩的应用。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
分析的预备知识
引理 ：设 $S$ 是 $\mathbb{R}^3$ 中以一点 $A$ 为中心，半径为 $R$ 的球面，$X$ 是 $S$ 上均匀分布的随机点，则 $X$ 与原点 $O$ 的距离倒数的期望值
\[E\frac{1}{|X|}=\left\{\begin{array}{l}1/a&R<a,\\1/R&R\geq a.\end{array}\right.\]
这里 $a$ 和 $|X|$ 分别表示 $A$ 和 $X$ 与原点 $O$ 之间的距离。
这个引理其实是我们都熟悉的高中物理知识：假设在球面 $S$ 上有总量为 1 的均匀分布的电荷，则在原点 $O$ 处的电势（忽略物理常数）就是所求的 $E\frac{1}{|X|}$。
我们知道在均匀带电球壳 $S$ 上以及 $S$ 的内部，电势是常数，等于 $1/R$；在球壳 $S$ 外部一点的电势等于该点到球心距离的倒数，从而引理得证。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
条件期望的预备知识
通常的条件期望是用 Radon - Nikodym 导数定义的，这个定义有时候用起来并不方便。譬如设 $X,Y$ 是两个随机变量，如果事件 $\{X=x\}$ 是零概率事件，但是在已知 $X=x$ 的前提下，期望值 $f(x)=E[Y|X=x]$ 又是有明显的概率意义的，即给定 $X$ 的信息，$Y$ 的期望值是 $f(X)$，于是直观上应该有 $E[Y|X]=f(X)$。但是怎么说明这个直观上的条件期望与抽象的条件期望一致呢？这就是下面的 "freezing lemma"。
引理：设 $(\Omega,\mathcal{F},P)$ 是一个概率空间，$\mathcal{G}\subset\mathcal{F}$ 是一个子 $\sigma-$ 代数，随机变量 $X:\Omega\rightarrow E$ 关于 $\mathcal{G}$ 可测，随机变量 $Y:\Omega\rightarrow F$ 与 $\mathcal{G}$ 独立（从而 $X,Y$ 独立），这里 $E,F$ 是两个可测状态空间。设 $f:E\times F\rightarrow\mathbb{R}$ 是非负可测函数（或者有界可测函数），则
\[ E[f(X,Y)|\mathcal{G}] = E[f(x,Y)].\]
或者写成更直观的形式： \[ E[f(X,Y)|\mathcal{G}] = E[f(X,Y)|X=x].\]
引理的证明就是从示性函数 $1_A\times 1_B$ 出发的标准方法，不再费笔墨了。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
模型的建立
初始时刻设为 0，太阳系是以原点为圆心，半径为 $r$ 的球体，飞船初始位置在 $(R,0,0)$ 处。
设 $\{\overrightarrow{U_n}\}_{n\geq 1}$ 是定义在某个概率空间 $(\Omega,\mathcal{F},\mathbf{P})$ 上的一组独立同分布的、在单位球面上均匀分布的随机向量，它们表示飞船每次空间跳跃的随机方向。并设 $\mathcal{F}_n=\sigma(\overrightarrow{U_1},\ldots,\overrightarrow{U_n})$ 以及 $\mathcal{F}_0=(\Omega,\emptyset)$。
设第 $n$ 次空间跳跃的距离为 $l_n(n\geq1)$，因为在第 $n$ 次空间跳跃时要根据以前的信息来决定第 $n$ 次的跳跃距离，所以 $l_n$ 关于 $\mathcal{F}_{n-1}$ 可测。
于是若设第 $n$ 次空间跳跃后飞船的坐标为 $\overrightarrow{X_n}$，那么\[\overrightarrow{X_n}=\overrightarrow{X_{n-1}} + l_n\overrightarrow{U_n}.\quad n=1,2,\ldots\]其中 $\overrightarrow{X_0}=(R,0,0)$ 是飞船的初始位置。
设 $T$ 是飞船首次返回太阳系的时间： \[ T = \inf\ \{ n:|\ \overrightarrow{X_n}\in B(0,r)\ \},\]则 $T$ 的取值范围是 $\mathbb{N^+}\cup\{+\infty\}$。我们要估算的是事件 $\{T<+\infty\}$ 的概率，这正是飞船能够在有限时间内回到太阳系的概率。
现在我们着手研究一下飞船的运动规律。
实际上只要搞清楚第一次跳跃会发生什么就足够了，因为以后的每次跳跃不过是第一次跳跃的 "情景重复"。那么第一次跳跃以后会有什么事情发生呢？
设 $R_n$ 为第 $n$ 次跳跃以后飞船与太阳系的距离，$R_0=R$，把前面的引理 1 套用过来，我们得到
\[E\left[\frac{1}{R_1}\right]=\left\{\begin{array}{l}1/R&l_1<R,\\1/l_1&l_1\geq R.\end{array}\right.\]
特别地可以发现，不论怎样设置 $l_1$，都会有 $E[1/R_1]\leq 1/R$，这就是说，在期望的意义下，飞船跳跃以后与太阳系的距离的导数是递减的！
我们可以立刻把这个现象应用到后面的每次跳跃中去：在 $n-1$ 时刻，给定飞船与太阳系的距离 $R_{n-1}$，则不论如何设定第 $n$ 次的跳跃距离 $l_n$，总是有
\[ E\left[\frac{1}{R_n}\left|\right.R_{n-1}=a\right]\leq\frac{1}{a}.\]
也就是
\[ E\left[\frac{1}{R_n}\left|\right.\mathcal{F}_{n-1}\right]\leq \frac{1}{R_{n-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$ 是非负的随机变量因此 $E[\frac{1}{R_n}|\mathcal{F}_{n-1}]$ 是有定义的且小于等于 $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} = \left\{ \begin{array}{l}\lim_{n\to\infty}Z_n& T=\infty,\\ Z_T& T<\infty.\end{array}\right.\]
一方面根据非负可积函数列的 Fatou 引理有\[ E[\lim_{n\to\infty}Z_{T\wedge n}]\leq\varliminf_{n\to\infty}E[Z_{T\wedge n}]\leq E[Z_0]=\frac{1}{R}.\]
另一方面
\[E[\lim_{n\to\infty}Z_{T\wedge n}]=E[Z_T1_{\{T<\infty\}}]+E[\lim_{n\to\infty}Z_n1_{\{T=\infty\}}] \geq E[Z_T 1_{\{T<\infty\}}]\geq\frac{1}{r}\mathbf{P}(T<\infty).\]
其中最后一个不等号是因为 $Z_T\geq 1/r$。综合这两个不等式就得到了 $\mathbf{P}(T<\infty)\leq r/R$，即任何策略下飞船最终返回太阳系的概率不大于 $r/R$。
要证明这个概率是严格小于 $r/R$ 的，我们只要证明上面式子的最后一个不等号是严格成立的：\[ E[Z_T 1_{\{T<\infty\}}]>\frac{1}{r}\mathbf{P}(T<\infty).\]
当然需要假定这里的 $\{T<\infty\}$ 有正概率（返回概率是 0 的话当然小于 $r/R$，没什么好证的）。
为此只要证明在事件 $\{T<\infty\}$ 上几乎处处有 $R_n<r$ 即可。
我们可以证明一个更精细的结论：令
\[A_n:=\{R_n=r\text{ or } R_n=0\}.\]
我们要证明对每个 $n\geq0$，$A_n$ 都是零概率事件。
对 $n$ 归纳：$n=0$ 时 $R_0=R>r$，结论自然成立。设当 $k<n$ 时有 $\mathbf{P}(A_k)=0$，对 $k=n$ 我们利用
\[ E[1_{A_n}|\mathcal{F}_{n-1}]=\mathbf{P}(A_n|\mathcal{F}_{n-1})=0.\quad \text{a.e. $\omega\in\mathcal{F_n}$}.\]
这里 $\mathbf{P}(A_n|\mathcal{F}_{n-1})$ 几乎处处是 0 是利用了归纳假设 $\mathbf{P}(A_{n-1})=0$ 和明显的几何事实：在不考虑零测集 $A_{n-1}$ 后，对 $\omega\notin A_{n-1}$，一次跳跃恰好落在太阳系中心或者距离太阳系中心为 $r$ 的球面上的概率是 0。因此
\[\mathbf{P}(A_n)=E[E[1_{A_n}|\mathcal{F}_{n-1}]]=0,\]
从而结论对 $n$ 也成立。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
现在我们把注意力转移到 "飞船不能返回太阳系" 这个事件上来。前面已经说过，飞船的运动只有两种可能，迷失在无穷远处或者被禁锢在一个有限的区域内，所以如果飞船不能返回太阳系，则飞船要么飞向无穷远，要么在太阳系之外的一个有限区域内打转。我们想知道，怎么判断这两种情形哪一种会发生呢？
举个例子，考虑这样一个明显不合理的策略：第 $n$ 次的跳跃距离总是设定为 $1/2^n$，在这个策略下飞船永远飞不出一个半径为 1 的空间，所以这种策略是应该避免的。
你可以注意到这个糟糕的策略的问题出在跳跃距离之和是收敛的。实际上如果我们给跳跃距离加上一个发散的限制，就可以避免飞船在太阳系外某个地方原地打转的情形。这就是下面的定理：
定理 3：设\[ E:=\{\omega:\ T(\omega)=\infty,\ \sum_{l=1}^\infty l_n(\omega)=\infty\},\]
则我们有
\[ \lim_{n\to\infty} R_n=+\infty,\quad \text{for a.e. $\omega\in E$.}\]
定理 3 的结论是说如果飞船不能返回太阳系（$T=\infty$），跳跃距离还是发散的（$\sum\limits_{n}l_n=\infty$），那么飞船几乎一定是飞向无穷远。
定理 3 的证明也很有趣，糅合了几何学和概率两方面的知识。
设 $\theta_n$ 为 $\overrightarrow{X_{n-1}}$ 与 $\overrightarrow{U_n}$ 之间的夹角，利用关系 $\overrightarrow{X_n}=\overrightarrow{X_{n-1}}+l_n\overrightarrow{U_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\}$，则在事件 $E\cap B_n$ 上我们有
\[ R_n^2\geq R_{n-1}^2+l_n^2+R_{n-1}l_n\geq(R_{n-1}+\frac{l_n}{2})^2.\]
即\[ R_n\geq R_{n-1}+\frac{l_n}{2},\quad \omega\in E\cap B_n.\]
当然就有
\[ R_n\geq R_{n-1}+\frac{l_n}{2}\ \text{i.o.}\quad \omega\in E\cap\{B_n\ \text{i.o.}\}.\]
因为在球面上均匀分布的随机点，其坐标分量也都是均匀分布，因此\[\mathbf{P}(B_n) =\mathbf{P}[\overrightarrow{U_n}\in \{(x,y,z)\in\mathbb{R}^3:\ z\geq\frac{1}{2}\}]=\frac{1}{4}>0.\]
事件列 $\{B_n\}$ 是独立的，且 $\sum\limits_n\mathbf{P}(B_n)=\infty$，根据 Borel-Cantelli 第二引理有 $\mathbf{P}(\{B_n\ \text{i.o.}\})=1$，于是 $E\cap\{B_n\ \text{i.o.}\}$ 与 $E$ 只差一个零测集，这样我们就证明了
\[ R_n\geq R_{n-1}+\frac{l_n}{2}\ \text{i.o.}\quad \text{for a.e. $\omega\in E$}.\]
注意 $\lim\limits_{n\to\infty}R_n$ 总是存在的，以及 $\sum\limits_n l_n(\omega)=\infty(\omega\in E)$，这立刻意味着
\[ \lim_{n\to\infty}R_n=+\infty\quad \text{for a.e. $\omega\in E$}.\]
这就证明了定理。
这里有个细节需要注意：为什么事件列 $\{B_n\}$ 是独立的呢？首先要注意到有
\[ \mathbf{P}(B_n|\mathcal{F}_{n-1})=\frac{1}4{}.\]
这是因为给定飞船在 $n-1$ 时刻的位置信息，下一次跳跃方向 $\overrightarrow{U_n}$ 与 $\overrightarrow{X_{n-1}}$ 的夹角的分布是可以计算的。这里的关键在于这个条件概率是个常数，因此 $\mathbf{P}(B_n|\mathcal{F}_{n-1})=\mathbf{P}(B_n)$，即事件 $B_n$ 的概率不依赖于 $\mathcal{F}_{n-1}$，这就证明了 $\{B_n\}$ 是独立的事件列。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
现在我们已经知道飞船返回太阳系的概率总是小于 $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 证明的重复：
这次根据控制收敛定理有
\[E[\lim_{n\to\infty}Z_{T\wedge n}]=\lim_{n\to\infty}E[Z_{T\wedge n}]=E[Z_0]=\frac{1}{R}.\]
另一方面
\[E[\lim_{n\to\infty}Z_{T\wedge n}]=E[Z_T1_{\{T<\infty\}}]+E[\lim_{n\to\infty}Z_n1_{\{T=\infty\}}].\]
这个时候要注意到在 $\{T=\infty\}$ 上总是有 $l_n\geq\epsilon$，因此根据定理 3 的结论，飞船几乎必然飞向无穷远，即
\[\lim_{n\to\infty}Z_n=0\quad \omega\in\{T=\infty\},\]
所以
\[E[\lim_{n\to\infty}Z_{T\wedge n}]=E[Z_T1_{\{T<\infty\}}]\leq\frac{1}{r-\epsilon}\mathbf{P}(T<\infty).\]
综合两个式子就证明了 $\mathbf{P}(T<\infty)\geq(r-\epsilon)/R$。
飞船空间跳跃问题