By Long Luo

在上一篇文章我们剖析了 拼多多 2020 年校招笔试算法题中第一题: 多多的魔术盒子 ，今天来挑战下其中的第 4 题：骰子期望 ¹ ，题目如下：

要解答这道题，我们需要先从脑海里把中学数学知识捡起来，弄清楚什么是期望 ²？

在概率论和统计学中，一个离散性随机变量的数学期望是试验中每次可能的结果乘以其结果概率的总和：

\[ \operatorname {E} [X] = \sum _{i=1}^{\infty }x_{i}\,p_{i} \tag{1} \label{1} \]

具体到这道题示例 \(1\) ，很明显 \(2\) 个骰子只能取到 \(1\) 或者 \(2\) 个值：

1. 假设这 \(2\) 个骰子取到的最大值为 \(1\) ，那么这 \(2\) 个骰子都只能选择 \(1\) ，概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} = \dfrac {1}{4}\) ；

2. 假设这 \(2\) 个骰子取到的最大值为 \(2\) ，那么存在 \(2\) 种可能，要么都取 \(2\) 或者 \(2\) 个骰子中有一个骰子投出了 \(2\) ，其概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} + \dfrac {1}{2} \times 1 = \dfrac {3}{4}\) 。

那么期望为： \(\dfrac {1}{4} \times 1 + \dfrac {3}{4} \times 2 = 1.75\) 。

对于骰子数少的时候还可以枚举，如果骰子数量很多呢？用上述方法就会遇到困难，比如有 \(N\) 个骰子，最大值为 \(M\) ，那么骰子结果为 \([1, 2, \dots, M]\) ，如何计算每个结果的概率值呢？

直接算当然是可行的，但是如果骰子数量很多的话，计算会非常繁琐，所以有没有更简单的方法呢？

概率分布的叠加

在上一节我们遇到一个问题，多个不同骰子一起的结果概率应该如何求解呢？

当我们只掷一个骰子时，结果的概率分布很简单——每个面出现的概率相等，例如一个常见的六面骰的结果是 \(\{ 1,2,3,4,5,6 \}\) ，每个结果的概率都是 \(\dfrac {1}{6}\)。

但如果我们掷两个骰子呢？结果的总和从 \(2\) 到 \(12\) ，很显然结果将不再是均匀分布，显然投出 \(7\) 的概率最高，而 \(2\) 和 \(12\) 的概率最低。

在实际工作生活中，常常会遇到已知多个随机变量的概率, 而随机变量又通过各种关系构成一个新的随机变量，求这个新随机变量的概率问题。假设第一个骰子的结果是随机变量 \(X\) ，第二个骰子是 \(Y\) ，它们的和 \(Z=X+Y\) 的概率分布，等价于两个独立分布的“叠加”，即：

\[ P(Z=z) = \sum _{k=-\infty }^{\infty }P(X=k)P(Y=z-k) \tag{2} \label{2} \]

这就是离散形式的 卷积(Convolution ) 公式 ³ 。

每一个可能的结果 \(k\) 的概率，是所有可能组合 \(i + (k - i) = k\) 的概率乘积之和，也就是说卷积就是概率分布的“加法规则” ⁴ 。在概率论中，卷积公式是用于计算两个独立随机变量之和的概率密度函数的重要工具。它告诉我们，两个独立随机事件的结果相加后，其概率分布会如何变化。

推广到多个不同骰子

如果每个骰子的面数不同，例如一个是 \(4\) 面，一个是 \(6\) 面等，我们只需依次卷积它们的分布：

\[ P_{total} ​= P_{D1}​​ \ast P_{D2}​​ \ast P_{D3}​​ \cdots \tag{3} \label{3} \]

每次卷积，都会将结果分布的长度扩大，并产生新的概率组合，而最终得到的分布就描述了所有骰子和的可能性及其概率。

由于题目中所有骰子的结果的最大值将作为最终结果，需要对概率卷积适当变形，最终代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

private static double calcExpectValue(int n, int[] dice) {
    Arrays.sort(dice);

    for (int i = 0; i < n / 2; i++) {
        int tmp = dice[i];
        dice[i] = dice[n - 1 - i];
        dice[n - 1 - i] = tmp;
    }

    int max = dice[0];

    double[] res = new double[max + 1];
    double[] current = new double[max + 1];

    for (int i = 1; i <= max; i++) {
        res[i] = 1.0 / max;
        current[i] = 1.0 / max;
    }

    for (int k = 1; k < n; k++) {
        int maxVal = dice[k];
        for (int j = 1; j <= maxVal; j++) {
            double less = 0.0;
            for (int t = 0; t < j; t++) {
                less += res[t];
            }
            less *= (1.0 / maxVal);

            double just = res[j] * ((j - 1.0) / maxVal);
            double both = res[j] * (1.0 / maxVal);

            current[j] = less + just + both;
        }

        for (int j = 1; j <= maxVal; j++) {
            res[j] = current[j];
        }
    }

    double ans = 0.0;
    for (int i = 1; i < res.length; i++) {
        ans += i * res[i];
    }

    return ans;
}

更优雅的方法：组合计数法

上面介绍的概率卷积方法，适用于求解多个随机变量的和的分布，但在本题中，只需要关心多个骰子中取最大值的概率分布。卷积方法虽好，但比较繁琐而且不是很好理解。实际上这道题是一个极值问题，我们可以从枚举出发，找到更简单的方法。

假设 \(3\) 枚骰子的取值分别为：\(X_1 \in [1]\) ， \(X_2 \in [1, 2]\) ， \(X3 \in [1, 2, 3]\) ，而要求的是： \(P(\max(X_1, X_2, X_3) = k)\) 最大值为 \(k\) 的概率，可以得到公式如下：

\[ P(\max = k) = P(\textit{all dices} \le k) - P(\textit{all dices} \le k - 1) \tag{4} \label{4} \]

来举个例子加深下理解：

1. 假设 \(3\) 个骰子取到的最大值为 \(1\) ，所有骰子都 \(\le 1\) ，即共有 \(1 \times 1 \times 1 = 1\) 种情况；

2. 假设 \(3\) 个骰子取到的最大值为 \(2\) ， 所有骰子都 \(\le 2\) ，共有 \(1 \times 2 \times 2 = 4\) ，再排除所有骰子 \(\le 1\) 这种情况，共有 \(4 - 1 = 3\) 种情况；

3. 假设 \(3\) 个骰子当中取到的最大值为 \(3\) ，所有骰子都 \(\le 3\) ，排除最大值为 \(2\) 的情况，即共有 \(1 \times 2 \times 3 - 4 = 2\) 种情况。

所有骰子出现的情况共有： \(1 \times 2 \times 3 = 6\) ，因此 \(P(1) = \dfrac {1}{6}\) ， \(P(2) = \dfrac {1}{2}\) ， \(P(3) = \dfrac {1}{3}\) 。

根据上述分析，我们可以写出更优雅的代码，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

private static double calcExpectValue_better(int n, int[] dice) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, dice[i]);
    }

    double ans = 0.0;
    double pre = 0;

    for (int i = 1; i <= max; i++) {
        double current = 1.0;

        for (int j = 0; j < n; j++) {
            current = current * Math.min(i, dice[j]) / dice[j];
        }

        ans += (current - pre) * i;
        pre = current;
    }

    return ans;
}

总结

这道笔试题比 第一题多多的魔术盒子 还是要难不少的，通过这道题，可以学到两种不同的概率分析思路：

1. 概率卷积法：计算独立随机变量之和的分布；
2. 枚举与组合计数法：通过全集减去子集的方式推导出结果分布。

当我们分析多个不同骰子取和时，用卷积最自然，也是最通用的方法。而在处理极值问题时，更简单更合适的做法是枚举与差分分析。

参考资料