Empty Bins — Hao Wu

Suppose we throw $m$ balls into $n$ bins uniformly at random, what is the probability that at least $\epsilon n$ ( $0 < \epsilon < 1$ ) bins remain empty?

When we throw a ball, if there are at least $\epsilon n$ empty bins, we increase the number of non-empty bins with probability at least $\epsilon$ . Let $X_1, X_2, ..., X_m$ be $m$ i.i.d Bernoulli random variable that takes $1$ with probability $\epsilon$ . The event that $\epsilon n$ empty bins remains is upper bounded by

\Pr [\sum_{i=1}^m X_i \le (1 - \epsilon) n] = \Pr [\sum_{i=1}^m X_i \le \frac{\epsilon m - \epsilon m + n - \epsilon n}{\epsilon m} \epsilon m] = \Pr [\sum_{i=1}^m X_i \le (1 - (1 - \frac{(1 - \epsilon ) n}{\epsilon m}) \frac{}{} \epsilon m]

When $\epsilon$ is fixed, by setting $\frac{1}{\lambda} \doteq \frac{n}{m} =\frac{\epsilon}{1 - \epsilon} (1 - \sqrt{\frac{2n }{\epsilon m} })$ (this is solvable since the left hand side is increasing with $1 / \lambda$ while the right hand side is decreasing with $1 / \lambda$ ), we have $(1 - \frac{(1 - \epsilon) n}{\epsilon m })^2\frac{\epsilon m}{2} = n$ . Then by Chernoff bound we get

\Pr [\sum_{i=1}^m X_i \le (1 - \epsilon) n] \le = \exp (-n)