最多球的盒子中的球数

hbghlyj

Mathematics for Computer Science, Assignment 12
Problem 6. 将 $n$ 个球 独立、概率均匀地随机扔进 $n$ 个盒子。
(a) 随机变量 $X_i$ 为 1 若盒子 $i$ 为空, 否则为 0. 写出 $X_i$ 的分布. $X_1, X_2, \dots, X_n$ 是否独立?
(b) 空盒数 $∼cn$. 求常数$c$.
(c) 证明 $\Pr(\text {盒子1中的球数} ≥k ) \leq\binom nk\left(\frac{1}{n}\right)^{k}$
(d) 令 $R$ 为 $n$ 个盒子中的球数的最大值。证明 $\Pr\{R \geq k\} \leq \frac{n}{k !}$
(e) $\lim _{n \rightarrow \infty} \operatorname{Pr}\left\{R \geq n^{\epsilon}\right\}=0$ for all $ϵ > 0$.

---

MSE 类似问题
(a) $\Pr(X_i=0)=(1-\frac1n)^n,\Pr(X_i=1)=1-(1-\frac1n)^n$. [Bernoulli分布]
因为 $\Pr(X_1=1\mid X_2=1)<\Pr(X_1=1)$, 所以 $X_1, X_2$ 不独立.
(b) $c=(1-\frac1n)^n$
(c) 见2#或这帖

Czhang271828

左式: $n$ 个 $\mathbb M$ 独立且随机挑选 $n$ 只哈士奇中的一只, 最终第一只哈士奇被至少 $k$ 个 $\mathbb M$ 挑选到的概率.

右式: 第一只哈士奇挑选 $k$ 个 $\mathbb M$, 规定哈士奇成功 $\Leftrightarrow $ 这 $k$ 个 $\mathbb M$ 都选择了它. 第一只哈士奇遍历 $\binom{n}{k}$ 中挑选方式的成功概率之和.

那么自然是右式概率大.

hbghlyj

(d) 由(c), $\Pr(盒子i的球数\ge k)\le\binom nk\left(\frac1n\right)^k={(1-\frac1n)\dots(1-\frac kn)\over k!}\le\frac1{k!}$
$\Pr(R\ge k)=\Pr(\bigcup_{i=1}^n盒子i的球数\ge k)$
根据subadditivity $\Pr(R\ge k)\le\sum_{i=1}^n\Pr(盒子i的球数\ge k)\le\frac n{k!}$      
(e) $\lim _{n \rightarrow \infty} \operatorname{Pr}\left\{R \geq n^{\epsilon}\right\}\le\lim _{n \rightarrow \infty} \frac n{(n^{\epsilon})!}=0$