将n个小球放入n个桶中，球最多的桶的期望球个数。

news/2024/4/27 0:16:39/文章来源:https://blog.csdn.net/fcb_x/article/details/129266162

本质来讲，这也可以看做对于一个n元素哈希表插入n个项的最长哈希链长度期望的计算。
先说结论：
$O(ln⁡nln⁡ln⁡n)\Large O(\frac{\ln n}{\ln\ln n})$
证明分四步走：

1. 定义事件 $A_k$ 为对于特定一个桶，刚好放有k个球的概率。

$P[Ak]=(nk)⋅(1n)k⋅(1−1n)n−k\large P[A_k] = \binom{n}{k} \cdot (\frac{1}{n})^k \cdot (1-\frac{1}{n})^{n-k}$

2. 定义事件 $X_k$ 为球最多的桶的球个数恰好为k、事件 $B_{i,k}$ 为恰好为i号桶球最多，并且球有k个。

可知：
$Xk=⋃iBi,k\large X_k = \bigcup_{i}{B_{i,k}}$
显然，可以推得：
$P[Xk]≤∑iP[Bi,k]\large P[X_k] \le \sum_{i}P[B_{i,k}]$
这是因为等号只会发生在事件B两两互斥时，其余情况概率会更小。
由此有：
$P[Xk]≤n⋅P[B1,k]\large P[X_k] \le n\cdot P[B_{1,k}]$
注意到：
$P[B1,k]≤P[Ak]\large P[B_{1,k}]\le P[A_k]$
这是因为事件 $A_k$ 仅满足特定桶有k个，但不保证其余桶少于k个，所以概率更大。
由此得到重要结论：
$P[Xk]≤n⋅P[Ak]\large P[X_k]\le n\cdot P[A_k]$

3. 证明 $(nk)<(en)kk\binom{n}{k} < \frac{(en)}{k}^k$

这个是斯特林公式的二级结论，此处不再多加赘述。回代本公式到上方结论可以得到：
$P[Xk]<n⋅(ek)k\large P[X_k] < n\cdot (\frac{e}{k})^k$
由于 $(1−1n)n−k<1(1-\frac{1}{n})^{n-k} < 1$ ，所以略去。
此时构造：
$c=3ln⁡ln⁡nln⁡ln⁡n−ln⁡ln⁡ln⁡n,K0=cln⁡nln⁡ln⁡nc=\frac{3\ln\ln n}{\ln\ln n-\ln\ln\ln n}, K_0 = \frac{c\ln n}{\ln\ln n}$
注意到当 $∀k>K0\forall k>K_0$ 有
$(ek)k<1n3\large (\frac{e}{k})^k<\frac{1}{n^3}$

4. 证明 $E[Xk]≤(K0⋅P[X≤K0]+n⋅P[X>K0])E[X_k] \le (K_0 \cdot P[X\le K_0] + n\cdot P[X>K_0])$

这不难证明，因为 $E[Xk]=∑i⋅P[Xi]E[X_k] = \sum_i \cdot P[X_i]$ 这就是把前面小于 $K_0$ 的乘上最大的 $K_0$ ，后面的乘上范围最大的值n。
再次放缩： $P[X≤K0]<1P[X\le K_0]<1$ 且 $P[X>K0]<(n−K0)⋅n⋅(ek)k<1nP[X>K_0]<(n-K_0)\cdot n\cdot (\frac{e}{k})^k<\frac{1}{n}$
带回有：
$E[Xk]<K0+1\large E[X_k] < K_0 + 1$
$E[Xk]<cln⁡nln⁡ln⁡n+1\large E[X_k] < \frac{c\ln n}{\ln\ln n} + 1$
$E[Xk]=O(ln⁡nln⁡ln⁡n)\large E[X_k] = O(\frac{\ln n}{\ln\ln n})$