求可重复抽样生成的随机序列中未出现元素的期望数量

这道题用指示变量+线性期望的思路来解非常直观，刚好能利用你提到的类似“尾和公式”的线性性质——线性期望的优势在于完全不要求变量之间独立，完美适配这种计数类的期望问题！

步骤1：定义指示变量 #

我们给集合$N$中的每个元素都分配一个“状态指示器”：

• 对任意元素$i \in N$，定义：

  X_i = 1，如果元素i从未出现在抽取的k个有序序列中
  X_i = 0，如果元素i至少出现过一次
  

  那么我们要求的“未出现元素数量”$X$，就是所有指示器变量的和：$X = X_1 + X_2 + ... + X_n$。

步骤2：计算单个指示器的期望 #

对单个元素$i$来说：

• 每次抽样时，不选中$i$的概率是$\frac{n-1}{n}$（因为总共有$n$个元素，均匀随机选取）；
• 由于是可重复抽样，$k$次抽样相互独立，因此$k$次都不选中$i$的概率是$\left(\frac{n-1}{n}\right)^k$；
• 而期望$E[X_i]$本质就是$X_i=1$的概率，所以：
  $$E[X_i] = \left(\frac{n-1}{n}\right)^k$$

步骤3：利用线性期望求总期望 #

线性期望的核心性质是：无论变量是否独立，和的期望等于期望的和。把步骤2的结果代入，就能得到：
$$
E[X] = E[X_1] + E[X_2] + ... + E[X_n] = n \times \left(\frac{n-1}{n}\right)^k
$$

也可以整理成更简洁的形式：
$$
E[X] = n\left(1 - \frac{1}{n}\right)^k
$$

如果$n$很大的话，还可以用近似公式$\left(1-\frac{1}{n}\right)^k \approx e^{-k/n}$，得到近似期望：
$$
E[X] \approx n e^{-k/n}
$$

内容的提问来源于stack exchange，提问作者alexw