扔几个骰子,怎么算出期望?——拼多多校招笔试算法题的数学故事
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}\) ,那多个不同骰子一起呢?如何计算最终结果的概率值呢?