绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
11588 一道「小黄鸭」概率题及其有趣扩展 (4)
2020-01-18 08:48:46

  上篇讲到,在 d 维空间里的 d-1 维超球面上随机、均匀地选取 n 个点,它们位于同一个半超球面的概率等于一个分数,其分母等于 2^d,而分子是 n 个过超球心的 d-1 维超平面把超球面切成的块数。我们仅考虑这 n 个超平面处于一般位置的情况,因为特殊位置(比如它们在超球面上交于同一点)的概率都是 0。

  把这个块数记为 f_d(n) 。我们已经数出来了:

  ● 在二维情况下,n 条直径会把圆周切成 f_2(n) = 2n 块;
  ● 在三维情况下,3 个大圆面会把球面切成 f_3(3) = 8 块;

但是,在数 f_3(4) 的时候遇到了困难,因为图形已经难以观察了。在更高维的情况下,想靠手工的「数」就更不可能了,必须要想办法「算」。

  这回我们从一维开始。一维空间,就是一条直线;其中的「0 维超球面」,就是与「超球心」等距的两个点。而用来分割这两个点的「0 维超平面」,就是「超球心」这个点本身。可以看到,不管怎么切,「0 维超球面」永远是分成两块儿的,所以有

f_1(n) = 2, \quad \forall n \ge 1 \\

图 4.1:一维空间中的「超球面」是两个蓝点

  现在来到二维。二维空间中,一条直径可以把圆周切成两块,所以 f_2(1) = 2。之后每加一条直径,都会把已经切出的某两块进一步一分为二,所以会多出两份来,即:

f_2(n) = f_2(n-1) + 2 \\

加的这个 2 其实有讲究,只是我们暂时还看不出来。

图 4.2:二维空间中,添加一条直径(粗线),会把圆周上原有的两块(黄色)一分为二

  现在进入三维。如下图 4.3,三维空间中,一个大圆面(红圈所在平面)可以把球面切成两块,所以 f_3(1) = 2。再增加一个大圆面(绿圈所在平面)时,会发生什么呢?新增的大圆面本身确定了一个二维空间。球面与这个二维空间的交集,就是绿圈这个圆周;之前已有的一个大圆面(红圈所在平面)与这个二维空间的交集,是一条直径(虚线)。绿圈被这条直径切成了 f_2(1) = 2 段,而其中的每一段,又把球面上的一块给一分为二了。所以,引入第二个大圆面时,会让球面被切成的块数增加 f_2(1) ,即:

f_3(2) = f_3(1) + f_2(1) = 4 \\

图 4.3:红圈把球面切成 2 块,绿圈把每一块又切成 2 块,一共 4 块

  两个大圆面把球面切成了 4 块。那再加入第三个大圆面时呢?如下图 4.4,新增的大圆面(蓝圈所在平面)与已有的两个大圆面交于两条直径,这两条直径把蓝圈切成了 f_2(2) = 4 段,其中每一段都会把球面上的 4 块进一步一分为二。所以有:

f_3(3) = f_3(2) + f_2(2) = 8 \\

图 4.4:蓝圈又把球面多切出 4 块,一共 8 块

  终于可以计算 f_3(4) 了。第四个大圆面的圆周(黄圈),被三条直径切成了 f_2(3) = 6 段,它们会把球面上的 6 块进一步一分为二,即:

f_3(4) = f_3(3) + f_2(3) = 14 \\

图 4.5:黄圈又把球面多切出 6 块,一共 14 块

  上面的递推过程,也可以推广到高维。一般地,在 d 维空间中加入第 n 个超平面时,超球面与这个超平面的交集,会被之前的 n-1 个超平面切成 f_{d-1}(n-1) 块,其中的每一块,会把超球面上的某一块进一步一分为二。所以有:

f_d(n) = f_d(n-1) + f_{d-1}(n-1) \\

  我们可以回头看一下二维情况。二维里的递推式为 f_2(n) = f_2(n-1) + 2,其中的 2,其实是 f_1(n-1) 。怎么理解呢?二维空间里新增的一条直径,本身确定了一个一维空间,这个一维空间里的「超球面」(即两个点)被原有的 n-1 条直径分割成了 f_1(n-1) = 2 个点,每个点会导致二维空间中的圆周被多切出一块来。

  根据 f_d(n) 的递推式,我们可以很容易地推出一些项来:

图 4.6:用递推式计算 f_d(n) 的一些项

比如,在 4 维空间中,6 个超平面可以把超球面切成 f_4(6) = 52 块,所以超球面上 6 个点位于同一个半超球面的概率为 f_4(6) / 2^6 = 52/64 = 0.8125

  现在我们有了 f_d(n) 的递推式,剩下的就是求通项了!求通项的方法有很多,比如多项式拟合、z 变换等,但我发现容易的方法,就是直接观察上面的递推表。

  就以 f_4(6) = 52 这一项为例。它等于左边一列中 22 与 30 的和。而 22 与 30,又分别是再左边一列中 8 与 14、14 与 16 的和,其中 14 被算了两遍。再往左推一列,就是 2、6、8、8 的和,它们分别被算了 1、3、3、1 遍 —— 有没有看出,1、3、3、1 就是 (x+1)^3 的展开式系数,也是杨辉三角中的一行呢?

图 4.7:从 f_4(6) = 52 往左递推

  一直往左推,直到推到列。出界没关系,界外的元素全当成 0 就可以了。不难看出, f_4(6) = 52 可以拆成列中四个 2 和两个 0 的和,它们的系数分别是 C_5^0, \ldots, C_5^5 。忽略 0,只保留 2,可以得到:

f_4(6) = 2 (C_5^0 + C_5^1 + C_5^2 + C_5^3) \\

  用上面的观察法,可以得到 f_d(n) 的通项:

f_d(n) = 2 \sum_{i=0}^{d-1} C_{n-1}^i \\

于是,在 d 维空间中的 d-1 维超球面上随机、均匀地选取 n 个点,它们位于同一个半超球面上的概率就是:

f_d(n) / 2^n = \frac{1}{2^{n-1}}\sum_{i=0}^{d-1} C_{n-1}^i \\

  我们终于解决了「小黄鸭」问题在任意维空间中的推广版本!

  后的概率公式有一些值得注意的特殊情况:当 n \le d 时,所有二项式系数都齐全,概率等于 1;当 n=2d 时,二项式系数恰好有一半、缺一半,概率等于 1/2


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

分享好友

分享这个小栈给你的朋友们,一起进步吧。

人工智能的世界
创建时间:2020-06-15 14:31:10
人工智能那点事儿
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

技术专家

查看更多
  • 栈栈
    专家
戳我,来吐槽~