11588 一道「小黄鸭」概率题及其有趣扩展 (2)

  3blue1brown 频道曾经讲解过一道 Putnam 数学竞赛题目 [YouTube] [Bilibili],恰好就给出了小黄鸭问题的三维版本的解答。

  这道 Putnam 竞赛题目是这样的:在一个球面上均匀随机地取 4 个点,它们连成的四面体包含球心的概率是多少?

图 2.1:在球面上取四个点,连成一个四面体

  这道题跟小黄鸭问题有什么关系呢?注意到,「四面体包含球心」跟「4 个点位于同一个半球面」恰好是互补事件(忽略四点共面、球心位于四面体的面上等零概率事件),所以「4 只小黄鸭位于同一个半球面」的概率,就等于 1 减去「四面体包含球心」的概率。

  要解决高维问题,有效的办法还是降维。不过,在上一篇的结尾已经说了,小黄鸭问题无法直接从二维推广到三维,因为「排头」的概念在球面上不适用了。怎么办呢?Putnam 竞赛题里提到了「四面体」的概念,这正好给我们提供了另一种降维的思路:「四面体」在二维里的对应物是「三角形」,所以我们考虑圆周上有 3 只小黄鸭的情况。

  我们在圆周上依次放置 3 只小黄鸭。在放了 2 只之后,第 3 只如果想跟前两只构成一个三角形把圆心包含在内,它就只能放在圆周上特定的某一段内。具体地说,设前两只小黄鸭位于 A、B,它们关于圆心的对称点是 A'、B',那么第 3 只小黄鸭就必须位于 A'、B' 之间的劣弧上。

图 2.2:二维空间中,第 3 只小黄鸭必须放在劣弧 A’B’上

  在 A、B 两点确定之后,三角形 ABC 包含圆心的概率,等于劣弧 A'B' 的长度除以圆周长。但是劣弧 A'B' 的长度不是固定的,它与 A、B 两点的位置有关;而三角形 ABC 包含圆心的概率,应该等于 A、B 遍历所有位置时,劣弧 A'B' 的长度与圆周长比值的期望。这个期望当然可以用微积分来算,不过 3blue1brown 频道给出了一种绕开微积分的巧妙算法。这种巧妙算法的精髓在于,把「在圆周上取三点」的过程用如下的步骤描述:

  1. 随机、均匀地选取两条直径;
  2. 随机、均匀地在圆周上选取点 C;
  3. 在两条直径上,分别等可能地选取一个端点作为 A、B,另一端作为 A'、B'。

  这种描述有什么好处呢?我们看第 3 步,这一步里选端点一共有 4 种选法,其中只有一种能让三角形 ABC 包含圆心 —— 把 C 所在的那一段劣弧的端点选为 A'、B'。4 种选法是等可能的,所以在直径和点 C 确定之后,三角形 ABC 包含圆心的概率是 1/4。剩下的事情,就是要遍历直径和点 C 的所有位置,对这个概率对求期望。然而这个概率 1/4 是个常数啊!于是求期望的步骤就可以免了,1/4 就是答案。「先选直径、再选端点」的描述法的精彩之处,就在于让最后一步达到目的的概率,与前面的步骤无关。

  于是我们得到,圆周上三个点组成的三角形包含圆心的概率是 1/4,那么三个点位于同一个半圆弧上的概率就是 1 - 1/4 = 3/4。可以验证,这个结果与用上一篇中的方法算出的结果是一致的。

  现在我们推广回三维。把「在球面上取四点」的过程用如下的步骤描述:

  1. 随机、均匀地选取三条直径;
  2. 随机、均匀地在球面上选取点 D;
  3. 在三条直径上,分别等可能地选取一个端点作为 A、B、C,另一端作为 A'、B'、C'。

图 2.3:三维空间中,点 D 必须位于球面三角形 A’B’C’内

  正如二维中两条直径把圆周分成 4 段劣弧那样,在三维中,三条直径两两确定一个平面,这些平面会把球面切成 8 个球面三角形。点 D 会落在某一个球面三角形里,第 3 步必须把这个球面三角形的顶点选为 A'、B'、C',才能让四面体 ABCD 包含球心,这个概率是 1/8。注意它跟点 D 所在的球面三角形大小无关!于是可以免去对前两步求期望的步骤,直接得到「四面体包含球心」的概率等于 1/8。如果要问「球面上 4 只小黄鸭位于同一个半球面」的概率,那就是 1 - 1/8 = 7/8 了。

  上面的推理过程还可以继续向高维推广。考虑 d 维空间中的 d-1 维超球面,在上面随机、均匀地选取 d+1 个点,它们构成一个 d 维单纯形。这个单纯形包含超球心的概率是多少呢?同样地,把选取 d+1 个点的过程描述成如下三步:

  1. 随机、均匀地选取 d 条直径;
  2. 随机、均匀地在超球面上选取一个点 P;
  3. 在 d 条直径上,分别等可能地选取一个端点,一边标上不带撇的字母,另一边标上带撇的字母。

  所有 d 条直径,每 d-1 条一组合,可以得到 d 个过球心的超平面,它们将超球面分割成 2^d 份。第 2 步中选取的点 P,会落在其中一份上。点 P 与所有其它不带撇字母表示的点构成一个单纯形,它若要包含超球心,则超球面上 P 点所在的那一块儿的顶点,必须都标有带撇的字母,其概率为 1/2^d。这是个常数,所以可以免去对前两步求期望的步骤,直接得到「d-1 维球面上 d+1 个点构成的单纯形包含球心」的概率为 1/2^d。那么,「d-1 维球面上 d+1 个点位于同一个半超球面」的概率就是 1 - 1/2^d 了。

  现在我们成功打破了次元壁,得到了高维情况的一些结论。不过,这些结论有一个局限性:点数只能等于空间维数加 1。如果我在任意维空间中的超球面上选取任意多个点,它们位于同一个半超球面的概率,又应该怎样计算呢?


  本系列共有 5 篇文章,以下是传送门:(1) (2) (3) (4) (5)

请使用浏览器的分享功能分享到微信等