当然可以证明这个结论！你一开始从期望入手的思路完全没问题，只是Chernoff界要求随机变量独立，这里的指示变量确实不独立（两个箱子的状态会互相影响），所以我们换用不需要独立性的集中不等式或者二阶矩方法就能搞定，下面一步步来：

第一步：计算单球箱子数的期望，确认它是Θ(n) #

首先定义指示变量：对每个箱子i（1≤i≤m），令
X_i = 1 如果箱子i恰好有1个球，否则X_i=0
总单球箱子数就是 X = X₁ + X₂ + ... + X_m

每个X_i的期望就是箱子i恰好有1个球的概率：
$$E[X_i] = \binom{n}{1} \cdot \left(\frac{1}{m}\right)^1 \cdot \left(1-\frac{1}{m}\right)^{n-1} = \frac{n}{m} \cdot \left(1-\frac{1}{m}\right)^{n-1}$$

那么总期望：
$$E[X] = m \cdot E[X_i] = n \cdot \left(1-\frac{1}{m}\right)^{n-1}$$

因为题目中n < m，所以(1-1/m)^{n-1}有下界：
$$\left(1-\frac{1}{m}\right)^{n-1} \geq \left(1-\frac{1}{m}\right)^{m-1} \approx \frac{1}{e}$$
同时它的上界是1，所以E[X]满足：
$$\frac{n}{e} \leq E[X] \leq n$$
显然E[X] = Θ(n)，这一步先坐实了期望的量级。

第二步：用集中不等式证明X高概率集中在期望附近 #

这里有两个常用的方法，都不需要变量独立：

方法1：二阶矩 + Chebyshev不等式 #

我们计算X的方差，再用Chebyshev不等式来约束X偏离期望的概率。

方差的展开式：
$$Var(X) = Var\left(\sum_{i=1}^m X_i\right) = \sum_{i=1}^m Var(X_i) + 2\sum_{1≤i<j≤m} Cov(X_i,X_j)$$

• 先算单个变量的方差：Var(X_i) = E[X_i²] - (E[X_i])² = E[X_i] - (E[X_i])²，因为X_i是0-1变量，所以X_i²=X_i。这部分的总和是m(E[X_i] - (E[X_i])²) = E[X] - m(E[X_i])²，量级是Θ(n)。
• 再算协方差项：Cov(X_i,X_j) = E[X_iX_j] - E[X_i]E[X_j]，其中E[X_iX_j]是箱子i和j都恰好有1个球的概率：
  $$E[X_iX_j] = \frac{n(n-1)}{m²} \cdot \left(1-\frac{2}{m}\right)^{n-2}$$
  当n < m时，(1-2/m)^{n-2} ≈ e^{-2n/m}，而(E[X_i])² ≈ \left(\frac{n}{m}e^{-n/m}\right)^2 = \frac{n²}{m²}e^{-2n/m}，所以两者的差非常小，协方差项的总和量级是O(n)。

根据Chebyshev不等式：
$$P(|X - E[X]| ≥ t) ≤ \frac{Var(X)}{t²}$$
取t = εn（ε是任意小的正数），右边会趋近于0当n足够大。这说明X高概率落在E[X] ± O(√n)范围内，而√n远小于n，所以X必然是Θ(n)。

方法2：McDiarmid不等式（更简洁） #

McDiarmid不等式适合这种“每个输入对输出的影响有限”的场景：我们把X看作n个球投放结果的函数，每个球的投放最多能让X改变多少？

• 如果把一个球投到原本空的箱子：X增加1
• 如果投到原本有1个球的箱子：X减少1
• 如果投到原本有≥2个球的箱子：X不变

也就是说，每个球的投放对X的改变量最多是1（Lipschitz常数为1）。根据McDiarmid不等式：
$$P(|X - E[X]| ≥ εE[X]) ≤ 2\exp\left(-\frac{2ε²(E[X])²}{n}\right)$$

因为E[X] = Θ(n)，所以(E[X])²/n = Θ(n)，指数部分是-Θ(ε²n)，当n→∞时，这个概率会指数级趋近于0。这直接说明X高概率和期望同量级，也就是Θ(n)。

总结 #

核心思路就是：先确认期望是Θ(n)，再用不需要变量独立的集中工具（二阶矩/McDiarmid）证明X不会偏离期望太多，从而得出高概率下X=Θ(n)的结论。

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