朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

飞船空间跳跃问题

2011-04-05


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

问题:一艘太空船正在宇宙中做星际航行时,飞船的控制系统出了故障,飞船不能正常地进行空间跳跃,而是只能预先设定一个距离,然后以此距离进行一次方向完全随机的跳跃。现在的问题是飞船想要返回太阳系。假设太阳系的半径是 \(r\),发生故障时飞船与太阳的距离为 \(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":

引理 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).\]

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

\[\int_C \varphi(X, Y)\mathrm{d}\mu = \int_C g(X)\mathrm{d}\mu.\]\(\varphi(x, y)=1_A(x)1_B(y)\) 时,\(g(x)=1_A(x)\mathbb{P}(\{Y\in B\})\),从而 \[\begin{align*}\int_C 1_A(X)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_C1_A(X)\mathrm{d}\mu\cdot\mathbb{P}(\{Y\in B\})\\&=\int_C g(X)\mathrm{d}\mu.\end{align*}\]

于是结论对所有形如 \(A\times B\) 的集合的示性函数成立。根据可测函数的单调类定理 (见 Durrett 的 Probability: theory and examples 第四版定理 6.1.3 或 Willianms 的 Probability with martingales 附录 3) 知道结论对所有非负或者可积函数都成立。

分析的预备知识

引理 2:设 \(B_R\)\(\mathbb{R}^3\) 中以原点 \(O\) 为中心,半径为 \(R\) 的球,\(X\) 是球面上均匀分布的随机点,\(A\) 是空间中任意一点,则 \(X\)\(A\) 之间距离倒数的期望值为 \[\mathbb{E}\frac{1}{|X-A|}=\begin{cases}1/a & a>R,\\ 1/R & a\leq R.\end{cases}\] 其中 \(a=|A|\)\(A\) 与原点之间的距离。

这个引理其实是我们都熟悉的高中物理知识:假设以原点为中心,半径为 \(R\) 的球壳上有总量为 1 的均匀分布的电荷,则空间任意一点 \(A\) 处的电势 (忽略物理常数) 就是所求的 \(\mathbb{E}\frac{1}{|X-A|}\)。而我们知道在均匀带电球壳上及其内部,电势是常数,等于 \(1/R\);在球壳外部一点的电势等于该点到原点距离的倒数,此即为结论。

当然这不能算是一个严格的数学证明,实际上这个积分正是分析中的 Newton 势函数的简单情形。由于这不是本文的重点,就不再展开讲了,读者可以参考下面的文献:

Donoghue, William F. Distributions and Fourier transforms. Vol. 32. Academic Press, 2014.

证明在第八章可以找到。

建立模型

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

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

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

  4. 于是若设第 \(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)\) 是飞船的初始位置。

  5. \(T\) 是飞船首次返回太阳系的时间: \[T = \inf\ \{ n:|\ \overrightarrow{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=R_{n-1}, Y=U_n,\varphi(X, Y)=1/R_n\) 应用前面的关于条件期望的引理 1 和关于 Newton 势的引理 2 得到

\[\mathbb{E}\left[\left.\frac{1}{R_n}\right|\mathcal{F}_{n-1}\right] =\mathbb{E}\left.\frac{1}{\left|\overrightarrow{X_{n-1}}+ l_n\overrightarrow{U_n}\right|}\right|_{X_{n-1}=A}\leq\frac{1}{|A|}=\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\) 是非负的随机变量因此 \(\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}.\] 另一方面 \[\mathbb{E}[\lim_{n\to\infty}Z_{T\wedge n}]=\mathbb{E}[Z_T\mathbf{1}_{\{T<\infty\}}]+\mathbb{E}[\lim_{n\to\infty}Z_n\mathbf{1}_{\{T=\infty\}}] \geq \mathbb{E}[Z_T \mathbf{1}_{\{T<\infty\}}]\geq\frac{\mathbb{P}(T<\infty)}{r}.\]

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

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

当然需要假定这里的 \(\{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\) 时有 \(\mathbb{P}(A_k)=0\),对 \(k=n\) 由于 \(\mathbb{P}(A_n)=\mathbb{E}[\mathbb{E}[\mathbf{1}_{A_n}|\mathcal{F}_{n-1}]]\),所以只要证明条件期望 \(\mathbb{E}[\mathbf{1}_{A_n}|\mathcal{F}_{n-1}]\) 几乎处处是零即可。由归纳假设 \(A_{n-1}\) 是零测集,在除去这个零测集以后我们有 \[\mathbb{E}[\mathbf{1}_{A_n}|R_{n-1} = a] = 0,\quad a\ne0, a\ne r.\]

这一步是利用了明显的几何事实:对 \(\omega\notin A_{n-1}\),一次跳跃恰好落在太阳系中心或者距离太阳系中心为 \(r\) 的球面上的概率是 0。因此 \[\mathbb{E}[\mathbf{1}_{A_n}|\mathcal{F}_{n-1}]=0, \quad \text{a.e.}\] 从而结论对 \(n\) 也成立。

对策略的进一步分析

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

举个例子,考虑这样一个明显不合理的策略:第 \(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\)\(\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\}\),则在事件 \(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}\geq R_{n-1}+\epsilon/2,\quad\omega\in B_n\cap E.\] 在事件 \(E\) 上,飞船一直在跳跃,因此有 \[R_n\geq R_{n-1}+\epsilon/2,\quad \text{i.o.}\quad \omega\in \{B_n\ \text{i.o.}\}\cap E.\] 如果我们能证明 \(\mathbb{P}(\{B_n\ \text{i.o.}\})=1\),则对几乎处处的 \(\omega\in E\) 都有 \(R_n\geq R_{n-1}+\frac{\epsilon}{2}\) 对无穷多个 \(n\) 成立,当然就说明了飞船在 \(E\) 上几乎处处飞向无穷远。

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

注意到 (又用到引理 1 啦) \[\mathbb{P}[B_n| \mathcal{F}_{n-1}] = \mathbb{P}[\left.\cos(\overrightarrow{U_n}, v)\geq\frac{1}{2}] \right|_{v=\overrightarrow{X_{n-1}}} = \mathbb{P}[\overrightarrow{U_n}\in \{(x,y,z)\in\mathbb{R}^3:\ z\geq\frac{1}{2}\}]=\frac{1}{4}.\] 于是对任何一组下标 \(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}[\mathbf{1}_A\mathbf{1}_B] = \mathbb{E}[\mathbb{E}[\mathbf{1}_A\mathbf{1}_B|\mathcal{F}_{n_k-1}]]\\&=\mathbb{E}[\mathbf{1}_A\mathbb{E}[\mathbf{1}_B|\mathcal{F}_{n_k-1}]]\\&=\frac{1}{4}\mathbb{E}[\mathbf{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\mathbf{1}_{\{T<\infty\}}]+\mathbb{E}[\lim_{n\to\infty}Z_n\mathbf{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\mathbf{1}_{\{T<\infty\}}]\leq\frac{1}{r-\epsilon}\mathbb{P}(T<\infty).\] 综合两个式子就证明了 \(\mathbb{P}(T<\infty)\geq(r-\epsilon)/R\)