飞船空间跳跃问题

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

问题 一艘太空船正在宇宙中做星际航行时,飞船的控制系统出了故障,飞船不能正常地进行空间跳跃,而是只能预先设定一个距离,然后以此距离进行一次方向完全随机的跳跃。现在飞船想要返回太阳系。假设太阳系的半径是 r,发生故障时飞船与太阳的距离为 R>r。好消息是在每个时刻,飞船能够知道自身与太阳系的距离。

求证:不论采用怎样的跳跃策略,飞船返回太阳系的概率都小于 r/R;但是对任何 ϵ>0,可以采取适当的策略,使得飞船返回太阳系的概率大于 (rϵ)/R,即 r/R 是最优概率。这个最优策略是什么?

预备知识

条件期望的预备知识

X,Y 是两个随机变量,φ 是可测函数。我们考虑条件期望 E[φ(X,Y)|X],这是一个关于 σ(X) 可测的随机变量,根据 Doob-Dynkin 引理,它可以写成 E[φ(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} 条件下的期望 E[φ(X,Y)|X=x]=Eφ(x,Y).g(x)=Eφ(x,Y)。这就找到了 g 的表达式。

引理 1.1. (Ω,F,μ) 是一个概率空间,X,Y 是两个取值在某可测空间 (S,S) 中的随机变量,子 σGF 满足 XGGY 独立。可测函数 φ:S×SR 满足 φ 非负或者 E|φ(X,Y)|<。令 g(x)=Eφ(x,Y),则 E[φ(X,Y)|G]=g(X).

在进入证明之前,我们来看个例子:

X,Y 是两个独立的随机变量,Y 服从的是 [0,1] 上的均匀分布,X 服从的分布我们可以不用关心。问条件期望 E[sin(XY)|X] 是什么?

这相当于在 引理 1.1 中取 φ(X,Y)=sin(XY)G=σ(X)引理 1.1 告诉我们可以把 sin(XY) 中的 X 冻结为常数 X=x,把 E[sin(XY)|X] 视作关于常数 x 的积分 E[sin(xY)]=01sin(xy)dy=1x0xsin(z)dz=1cosxx. 然后把 x 解冻为 X 即得 E[sin(XY)|X]=1cosXX.

引理 1.1 中的可测空间 (S,S) 可以是多维空间 (Rd,B(Rd))X,Y 也可以是独立的随机向量。即如果 φ(X1,,Xn,Y1,,Ym) 是关于随机变量的可测函数,σ(X1,,Xn)G 并且 Gσ(Y1,,Ym) 独立,那么条件期望 E[φ(X,Y)|G] 就是一个以 (x1,,xn) 为参变元的多重积分 E[φ(x1,,xn,Y1,,Ym)]=g(x1,,xn).

证明:我们要证明对任何可测集 CG

Cφ(X,Y)dμ=Cg(X)dμ.φ(x,y)=1A(x)1B(y) 时,g(x)=1A(x)P({YB}),从而 C1A(X)1B(Y)dμ=P({XA}C{YB})=P({XA}C)P({YB})=C1A(X)dμP({YB})=Cg(X)dμ.

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

分析的预备知识

引理 1.2. B=B(A,R)R3 中以点 A 为中心,半径为 R 的球,X 是球面上均匀分布的随机点,则 X 与原点 O 之间距离倒数的期望为 E1|X|={1/aa>R,1/RaR. 其中 a=|A|A 与原点之间的距离。

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

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

建立模型

我们开始正式求解本文开头的问题。

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

  2. {Un}n1 是定义在某个概率空间 (Ω,F,P) 上的一组独立同分布的、在单位球面上均匀分布的随机向量,它们表示飞船每次空间跳跃的随机方向。并设 Fn=σ(U1,,Un) 以及 F0=(Ω,)

  3. 设第 n 次空间跳跃的距离为 ln(n1),由于 ln 是根据 n 时刻之前的信息决定的,所以 ln 关于 Fn1 可测。

  4. 设第 n 次空间跳跃后飞船的坐标为 Xn,那么 Xn=Xn1+lnUn.n=1,2,. 其中 X0=(R,0,0) 是飞船的初始位置。

  5. T 是飞船首次返回太阳系的时间: T=inf{nXnB(0,r)},T 的取值范围是 N+{+}。我们要估算的是事件 {T<+} 的概率,这正是飞船能够在有限时间内回到太阳系的概率。

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

Rn 为第 n 次跳跃以后飞船与太阳系的距离,R0=R,我们想知道 RnRn+1 之间的关系。

F=Fn,G=Fn1,X=(Xn1,ln),Y=Un,φ(X,Y)=1/|Xn1+lnY| 应用前面的关于条件期望的 引理 1.1引理 1.2 得到

E[1Rn|Fn1]=E1|Xn1+lnUn||Xn1=A1|A|=1Rn1.

这里由于 Xn1ln 都是关于 Fn1 可测的,而 UnFn1 是独立的,所以应用 引理 1.1 的条件是满足的。

总结一下:

定理 2.1. {1/Rn} 关于 {Fn} 构成一个上鞅 (与策略无关)。特别地如果跳跃距离总是不超过当前飞船与太阳系的距离,即对任何 n1lnRn1,则 {1/Rn} 还是一个鞅。

证明:只要再说明每个 1/Rn 是可积的随机变量即可。由于 1/Rn 是非负的随机变量因此 E[1/Rn|Fn1] 是有定义的且已经证明其小于等于 1/Rn1,于是 E[1/Rn]=E[E[1/Rn|Fn1]]E[1/Rn1].n 归纳即可。

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

现在我们可以证明:

定理 2.2. 不论飞船采取怎样的策略,返回太阳系的概率都严格小于 r/R

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

Zn=1/Rn,则 {Zn} 是一个非负上鞅,所以 Z=limnZn 是几乎处处存在的。考虑由停时 T 截断得到的非负上鞅序列 {ZTn},这个上鞅序列也是几乎处处收敛的,其中 limnZTn={limnZnT=,ZTT<. 一方面根据非负可积函数列的 Fatou 引理有 E[limnZTn]limnE[ZTn]E[Z0]=1R. 另一方面

E[limnZTn]=E[ZT1{T<}]+E[limnZn1{T=}]E[ZT1{T<}]P(T<)r.

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

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

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

我们来证明对每个 n0,事件 An={Rn=0 or Rn=r} 都是零概率事件。

n 归纳:n=0R0=R>r,结论成立。设结论在小于 n 时都成立,来看 n 的情形。

由于 P(An)=E[1An]=E[E[1An|Fn1]],我们只要证明 E[1An|Fn1] 是几乎处处为 0 的随机变量即可。

引理 1.1 中取 X=(Xn1,ln),Y=Un,G=Fn1,我们得到 E[1An|Fn1]=E[1{0,r}|Xn1+lnUn||Fn1]=E[1{0,r}|Xn1+lnUn|]. 其中上式最右边的期望是对单位球面上均匀分布的 Un 进行积分,结果是一个关于 (Xn1,ln) 的函数。显然无论如何上式右边作为一个只取 {0,1} 两个值的函数的积分,结果必然在 [0,1] 中。

  • 如果 |Xn1|{0,r},我们已经知道结果在 [0,1] 中。
  • 如果 |Xn1|{0,r},这时以 Xn1 为中心,ln 为半径的球面上,与原点之间的距离为 0 或者 r 的点的测度为 0,即积分项 1{0,r}|Xn1+lnUn| 对几乎处处的 Un 都是 0,当然积分值 E[1{0,r}|Xn1+lnUn|]=0

于是我们有 E[1{0,r}|Xn1+lnUn|]={[0,1],|Xn1|{0,r}0,|Xn1|{0,r}

根据归纳假设,|Xn1|{0,r} 的概率是 0,即 E[1{0,r}|Xn1+lnUn|] 是一个几乎处处为 0 的函数,从而 E[1An|Fn1] 也几乎处处为 0,即得所证。

对策略的进一步分析

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

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

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

定理 3.1. ϵ 是任一正数 E:={ω: T(ω)=, ln(ω)ϵ, n1}, 则我们有 limnRn=+,for a.e. ωE.

证明:设 θnXn1Un 之间的夹角,利用关系 Xn=Xn1+lnUn 以及三角形的余弦公式可得 Rn2=Rn12+ln2+2Rn1lncosθn.Bn={cosθn1/2},则在事件 Bn 上我们有

Rn2Rn12+ln2+Rn1ln(Rn1+ln/2)2. 结合在事件 E 上有 lnϵ,于是在事件 BnE 上有 RnRn1+ln/2Rn1+ϵ/2,ωBnE. 如果我们能证明 P({Bn i.o.})=1,再排除掉使得 Rn(ω) 不收敛的零测集,则对几乎处处的 ωE 都有 RnRn1+ϵ/2 对无穷多个 n 成立。对这些 ωRn 是不可能收敛到一个有限的点的,只能是 limnRn(ω)=,这就说明飞船在 E 上几乎处处飞向无穷远。

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

注意到(又用到 引理 1.1 啦)

P[Bn|Fn1]=P[cos(Un,v)1/2]|v=Xn1=P[Un{(x,y,z)R3: z1/2}]=14.

于是对任何一组下标 n1<n2<<nk,记 A=Bn1Bnk1 以及 B=Bnk,并注意到由于 nk1nk1 因此 AFnk1,所以

P[Bn1Bnk]=E[1A1B]=E[E[1A1B|Fnk1]]=E[1AE[1B|Fnk1]]=14E[1A]=14P(Bn1Bnk1).

从而由递推可见对每个 n 都有 P(Bn)=14 且它们是互相独立的。

最优策略

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

定理 4.1. 定义如下的跳跃策略:在准备第 n 次跳跃时,如果飞船已经在太阳系内,则令 ln=0,否则令 ln=Rn1r+ϵ,这里 0<ϵ<r。在这个跳跃策略下,飞船返回太阳系的概率大于 (rϵ)/R

注意在这个策略中总是有 ln<Rn1,因此 {Zn=1/Rn} 实际上是一个鞅。此外由于总是有 Rnrϵ,所以 Zn1/(rϵ),即 {Zn} 被常数 1/(rϵ) 所控制。

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

这次根据控制收敛定理有 E[limnZTn]=limnE[ZTn]=E[Z0]=1R. 另一方面 E[limnZTn]=E[ZT1{T<}]+E[limnZn1{T=}]. 这个时候要注意到在 {T=} 上总是有 lnϵ,因此根据 定理 3.1 的结论,飞船几乎必然飞向无穷远,即 limnZn=0,ω{T=}. 所以 E[limnZTn]=E[ZT1{T<}]1rϵP(T<). 综合两个式子就证明了 P(T<)(rϵ)/R

References

Donoghue, W. F. 2014. Distributions and Fourier Transforms. ISSN. Elsevier Science. https://books.google.com/books?id=P30Y7daiGvQC.
Durrett, Rick. 2019. Probability: Theory and Examples. 5th ed. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
Williams, David. 1991. Probability with Martingales. Cambridge University Press.