扔几个骰子，怎么算出期望？——拼多多校招笔试算法题的数学故事
By Long Luo
在上一篇文章我们剖析了 拼多多 2020 年校招笔试算法题中第一题: 多多的魔术盒子 ，今天来挑战下其中的第 4 题：骰子期望 1 ，题目如下：
骰子期望
扔 \(n\) 个骰子，第 \(i\) 个骰子有可能投掷出 \(X_i\) 种等概率的不同的结果，数字从 \(1\) 到 \(X_i\) 。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。
- 输入描述:
- 第一行一个整数 \(n\) ，表示有 \(n\) 个骰子。( \(1 \le n \le 50\) )
- 第二行 \(n\) 个整数，表示每个骰子的结果数 \(X_i\) 。( \(2 \le X_i \le 50\) )
- 输出描述:
- 输出最终结果的期望，保留两位小数。
- 输入例子 \(1\) :
- 2
- 2 2
- 输出例子 \(1\) :
- 1.75
要解答这道题，我们需要先从脑海里把中学数学知识捡起来，弄清楚什么是期望 2？
在概率论和统计学中，一个离散性随机变量的数学期望是试验中每次可能的结果乘以其结果概率的总和：
\[ \operatorname {E} [X] = \sum _{i=1}^{\infty }x_{i}\,p_{i} \]
具体到这道题示例 \(1\) ，很明显 \(2\) 个骰子只能取到 \(1\) 或者 \(2\) 个值：
假设这 \(2\) 个骰子取到的最大值为 \(1\) ，那么这 \(2\) 个骰子都只能选择 \(1\) ，概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} = \dfrac {1}{4}\) ；
假设这 \(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]\) ，如何计算每个结果的概率值呢？
对于单个骰子，很显然每个结果的概率均为 \(\dfrac {1}{M}\) ，那多个不同骰子一起呢？如何计算最终结果的概率值呢？
概率卷积
在上一节我们遇到一个问题，多个不同骰子一起的结果概率应该如何求解呢？
待完善
3Blue1Brown Convolutions | Why X+Y in probability is a beautiful mess
在概率论中，卷积公式是用于计算两个独立随机变量之和的概率密度函数的重要工具。
\(Z=X+Y\)
\[ P(Z=z) = \sum _{k=-\infty }^{\infty }P(X=k)P(Y=z-k)} \]
在概率论问题中, 我们常常会遇到已知多个随机变量的概率密度, 而随机变量通过函数关系构成一个新的随机变量, 求这个新随机变量的概率密度的问题.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
46private 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;
}
从暴力到优雅 —— 基于累积分布函数的期望计算
待完善1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22private 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;
}