占坑问题
给定\(n\)个球和\(n\)个盒子，每个球会被串行地随机分配到一个盒子中。
- 求空盒的期望数目。
- 求每个盒子装有的球的期望数目。
- 若每个盒子都会在它已经装有\(1\)个球时，拒绝装下其他的球，然后被拒绝的球消失。求消失的球的期望数目。
注：每个问题的条件相互独立。默认情况下，每个盒子可装任意多个球。
解答
- 记\(X_i\in\{0,1\}\)表示“第\(i\)个盒子为空盒”，则
\[ P(X_i = 1) = \left(\frac{n - 1}{n} \right)^n \]
故\(E(X_i)=\left(\frac{n - 1}{n} \right)^n\)，空盒的期望数目\(E(\sum X_i) = \sum E(X_i) = n\left(\frac{n - 1}{n} \right)^n\)。当\(n\)充分大时，\(E(\sum X_i) = \frac{n}{\mathrm e}\)。
- 记\(Y_i \in \{0,1\}\)表示“第\(j\)个盒子装有第\(i\)个球”（由对称性，\(Y_i\)与\(j\)无关），则\(P(Y_i= 1) = \frac{1}{n}\)。故每个盒子装有的球的期望数目为
\[ E(\sum Y_i) = \sum E(Y_i) = n \cdot \frac{1}{n} = 1. \]
注意：若考虑用期望的定义计算：记\(T\)表示“第\(j\)个盒子里的球的数目”，则
\[ E(T) = 0 \cdot P(T=0) + 1 \cdot P(T=1) + \dots + n \cdot P(T=n) = \sum_{i=1}^n i P(T=i). \]
而且我们已经知道\(E(T) = 1\)。这个式子在下一题是有用的。
- 等价地，将题目的条件转化为：先假设每个盒子可装任意多个球，装完后，再统一地让超出容积的盒子里面的球消失。具体而言，在装完\(n\)个球后，对第\(j\)个盒子，若该盒子中装有\(k(k > 1)\)个球，则抛弃\(k - 1\)个球，否则不抛弃。
记\(S\)表示“如此做后，第\(j\)个盒子抛弃的球的个数”，由期望的线性性质，我们只需求\(nE(S)\)。首先显然有
\[ E(S) = 1 \cdot P(S=1) + 2 \cdot P(S=2) + \dots + (n-1) \cdot P(S=n-1). \]
注意到当\(S \geq 1\)时，\(S\)和\(T\)的关系满足\(S = T - 1\)。于是
\[ \begin{aligned} E(S) &= 1 \cdot P(T = 2) + 2 \cdot P(T=3) + \dots + (n-1) \cdot P(T=n) \\ &= \sum_{i=1}^n (i-1)P(T=i)\\ &= \sum_{i=1}^n i P(T=i) - \sum_{i=1}^n P(T=i). \\ &= 1- (1- P(T=0)) \\ &= P(T=0) \\ &= \frac{n}{\mathrm e}. \end{aligned} \]
另解
由于在这种情况下，所有有球的盒子里都有且只有\(1\)个球，所以在所有球都分配完毕后，有
\[ 非空盒的数目 = 未消失的球的数目 \]
于是
\[ 空盒的数目 = 消失的球的数目。 \]
所以答案是空盒的期望数目。