note[15]
题:数论函数 \(F(x)\) ,在 \(1\) 到 \(n\) 里随机选 \(k\) 个数,可以重复选/不可以重复选,\(F\) 值之和的期望?
解:
不可以重复选: \[ \begin{aligned} \mathbb{E}(X) & =\mathbb{E}\left(\sum_{i=1}^k F\left(c_i\right)\right) \\ & =\sum_{i=1}^k \mathbb{E}\left(F\left(c_i\right)\right) \\ & =k \sum_{i=1}^n \frac{1}{n} \cdot F(i) \\ & =\frac{k}{n} \sum_{i=1}^n F(i) \end{aligned} \]
可以重复选: \[ \begin{aligned} \mathbb{E}(X) & =\mathbb{E}\left(\sum_{i=1}^n c_i \cdot F(i)\right) \\ & =\sum_{i=1}^k \mathbb{E}\left(c_{t_i} \cdot F(t_i)\right) \\ & =\sum_{i=1}^n \frac{\binom{n-1}{k-1}}{\binom{n}{k}} F(i) \\ & =\frac{k}{n} \sum_{i=1}^n F(i) \end{aligned} \] 这里第三步钦定当前数必定被选,于是从剩下的 \(n-1\) 个数中选 \(k-1\) 个数。
参考文献: