关于n个球分配后空箱数的依概率收敛问题

问题背景 #

给定m个箱子，球被独立且均匀地投入箱子中（每个球落入任意箱子的概率都是$\frac{1}{m}$）。用$N_n$表示投完n个球后空箱子的数量。现在要求：当n和m同时趋向无穷大，且满足$\frac{n}{m} \to \lambda$时，证明$\frac{N_n}{n} \stackrel{p}{\to} c$，并确定常数c的值。

提问者初始思路 #

我最开始想到的是把$N_n$拆成指示变量的和：$N_n = \sum_{i=1}^{m} 1_{A_i}$，其中$A_i$代表“第i个箱子是空的”这个事件。本来打算用切比雪夫不等式来推导，但当时觉得这样可能没法得到具体的常数c。

完整推导过程 #

第一步：计算$N_n$的期望

首先，根据指示变量的性质，$E[1_{A_i}] = P(A_i)$，也就是第i个箱子为空的概率——n个球都不落入这个箱子的概率是$\left(1 - \frac{1}{m}\right)^n$。所以：
$$E[N_n] = \sum_{i=1}^{m} E[1_{A_i}] = \sum_{i=1}^{m} P(A_i) = m\left(1 - \frac{1}{m}\right)^n$$

接下来我们看$\frac{E[N_n]}{n}$的极限：
已知$\frac{n}{m} \to \lambda$，即$m = \frac{n}{\lambda} + o(n)$。利用指数近似：当m趋向无穷大时，$\ln\left(1 - \frac{1}{m}\right) \approx -\frac{1}{m} - \frac{1}{2m^2} - \dots$，所以：
$$n \ln\left(1 - \frac{1}{m}\right) \approx -\frac{n}{m} \to -\lambda$$
因此$\left(1 - \frac{1}{m}\right)^n \to e^{-\lambda}$，代入期望的表达式可得：
$$\frac{E[N_n]}{n} = \frac{m}{n} \cdot \left(1 - \frac{1}{m}\right)^n \to \frac{1}{\lambda} e^{-\lambda}$$

第二步：用切比雪夫不等式证明依概率收敛

要证明$\frac{N_n}{n}$依概率收敛到$\frac{e^{-\lambda}}{\lambda}$，我们需要验证：对任意$\epsilon > 0$，$P\left(\left|\frac{N_n}{n} - \frac{e^{-\lambda}}{\lambda}\right| > \epsilon\right) \to 0$。

先计算$Var(N_n)$：
$$Var(N_n) = Var\left(\sum_{i=1}^m 1_{A_i}\right) = \sum_{i=1}^m Var(1_{A_i}) + 2\sum_{1 \leq i < j \leq m} Cov(1_{A_i}, 1_{A_j})$$

• 单个指示变量的方差：$Var(1_{A_i}) = P(A_i)(1 - P(A_i)) = \left(1 - \frac{1}{m}\right)^n \left[1 - \left(1 - \frac{1}{m}\right)^n\right]$
• 协方差部分：$Cov(1_{A_i},1_{A_j}) = P(A_i \cap A_j) - P(A_i)P(A_j)$，其中$P(A_i \cap A_j)$是第i、j两个箱子都为空的概率，即$\left(1 - \frac{2}{m}\right)^n$，因此协方差为$\left(1 - \frac{2}{m}\right)^n - \left(1 - \frac{1}{m}\right)^{2n}$

现在分析$\frac{Var(N_n)}{n^2}$的极限：

1. 第一项：$\frac{m}{n^2} \left(1 - \frac{1}{m}\right)^n \left[1 - \left(1 - \frac{1}{m}\right)^n\right]$，由于$m \sim \frac{n}{\lambda}$，$\left(1 - \frac{1}{m}\right)^n \to e^{{-\lambda}$，所以这一项等价于$\frac{n/\lambda}{n}2} \cdot e^{-\lambda}(1 - e^{-\lambda}) = \frac{e^{-\lambda}(1 - e^{-\lambda})}{\lambda n} \to 0$
2. 第二项：$2 \cdot \binom{m}{2} \left[\left(1 - \frac{2}{m}\right)^n - \left(1 - \frac{1}{m}\right)^{2n}\right] / n^{2$，化简为$\frac{m(m-1)}{n}2} \left[\exp\left(n \ln\left(1 - \frac{2}{m}\right)\right) - \exp\left(2n \ln\left(1 - \frac{1}{m}\right)\right)\right]$。同样用指数近似，$n \ln\left(1 - \frac{2}{m}\right) \to -2\lambda$，$2n \ln\left(1 - \frac{1}{m}\right) \to -2\lambda$，所以括号内的部分趋向$e^{-2\lambda} - e^{-2\lambda} = 0$，结合$\frac{m(m-1)}{n^2} \sim \frac{1}{\lambda^2}$，整个第二项也趋向0

因此$\frac{Var(N_n)}{n^2} \to 0$，根据切比雪夫不等式：
$$P\left(\left|\frac{N_n}{n} - \frac{E[N_n]}{n}\right| > \epsilon\right) \leq \frac{Var(N_n/n)}{\epsilon^2} = \frac{Var(N_n)}{n^2 \epsilon^2} \to 0$$

又因为$\frac{E[N_n]}{n} \to \frac{e^{-\lambda}}{\lambda}$，根据依概率收敛的传递性，可得：
$$\frac{N_n}{n} \stackrel{p}{\to} \frac{e^{-\lambda}}{\lambda}$$
也就是常数$c = \frac{e^{-\lambda}}{\lambda}$

备注：内容来源于stack exchange，提问作者Daileon108