Ball in Bins — Hao Wu

Suppose we would like to throw $n$ balls into $n$ bins uniformly at random. We claim that the bin with maximum load has $\Theta( \frac{\ln n}{\ln \ln n})$ ball with high probability.

Preliminary

For all $x \ge 0$ , it holds that
$e^x = 1 + x + \frac{x^2}{2!} + ...\ge \frac{x^k}{ k! }.$

For all $x \in \mathbb{R}$ , $1 + x \le \exp (x)$ . Therefore for all $n \in \mathbb{N}_+$ ,
$\left( 1 + \frac{1}{n} \right)^n \le \exp \left( \frac{1}{n} \cdot n \right) = e,$
and for $n > 1$ ,
$\left( \frac{ n - 1}{n} \right)^{n - 1} = \frac{1}{ \left( 1 + \frac{1}{n - 1} \right)^{n - 1} } \ge \frac{1}{e} .$

For $n \in \mathbb{N}_+$ , $k \in [n]$ ,
$\binom{n}{k} \frac{k^k}{n^k} \le \left( 1 + \frac{k}{n} \right)^n = e^k.$

For $n \in \mathbb{N}_+$ , $k \in [n]$ ,
$\binom{n}{k} = \frac{n (n - 1) \ldots (n - k + 1) }{k (k - 1) \ldots 1} \ge \frac{n^k}{k^k}.$

Upper Bound

Via union bound, the probability that a particular bin receives at least $k$ balls is given by

\Pr[ \exists k \text{ balls in the bin} ] \le \binom{n}{k}\frac{1}{n^k} \le \frac{1}{k!} \le \frac{ e^k }{ k^k},

We want to find a $k$ , such that

\left( \frac{e}{ k} \right)^k = \frac{1}{n^2}.

Taking $\ln$ of both sides,

\begin{aligned} k \ln k - k = 2 \ln n\, \implies k \ln k \in \Theta( \ln n)\, \implies \ln k \in \Theta( \ln \ln n). \end{aligned}

(By using asymptotically notations, the relationship only holds for reasonably large enough $k$ and $n$ .)

Substituting $\ln k \in \Theta( \ln \ln n)$ into $k \ln k \in \Theta( \ln n)$ , we get

k \in \Theta\left( \frac{\ln n}{\ln \ln n} \right).

Finally, by union bound over the number of possible bins, the probability that there is a bin which receives $\ge k$ ball is bounded by $1 / n$ .

Lower Bound

Given $k \in \mathbb{N}_+$ , define the indicator variables $X_i$ for the event that the $i$ -th bin receives exactly $k$ balls, and let $X = \sum X_i$ . Then

\begin{aligned} \Pr[X_i = 1] = \binom{n}{k}\frac{1}{n^k} \left( 1 - \frac{1}{n} \right)^{n - k} \ge \frac{n^k}{k^k} \cdot \frac{1}{n^k} \cdot \left( \frac{ n - 1}{n} \right)^{n - 1} \ge \frac{1}{k^k} \frac{1}{e}. \end{aligned}

and

\begin{aligned} \Pr[X_i = 1] = \binom{n}{k}\frac{1}{n^k} \left( 1 - \frac{1}{n} \right)^{n - k} \le \binom{n}{k} \frac{1}{n^k} \le \frac{ (en)^k }{ k^k } \frac{1}{n^k} = \frac{e^k}{k^k}. \end{aligned}

We shall prove that $\mathbb{Cor}(X_i, X_j) < 0,\, \forall i \neq j$ . Intuitively, that bin $i$ obtains ball makes it more difficult for bin $j$ to obtain ball. It follows that

\begin{aligned} \mathbb{E}[X] &= \sum \mathbb{E}[X_i] \ge n \cdot \frac{1}{k^k} \frac{1}{e}. \\ \mathbb{Var}[X] &= \sum_{ i \in [n] } \mathbb{Var}[X_i] + \sum_{i \neq j} \mathbb{Cor}(X_i, X_j) \\ &\le \sum_{ i \in [n] } \mathbb{Var}[X_i] \le \sum_{ i \in [n] } \mathbb{E}[X_i^2] \\ &= \sum_{ i \in [n] } \mathbb{E}[X_i] \le n \cdot \frac{e^k}{k^k}. \end{aligned}

By Chebyshev Inequality, we have

\begin{aligned} \Pr[ X \le 0] &\le \Pr[ |X - \mathbb{E}[X]| \ge \mathbb{E}[X] ] \\ &\le \frac{ \mathbb{Var}[X] }{ \mathbb{E}[X]^2} \le \left( n \cdot \frac{1}{k^k} \frac{1}{e} \right) / \left( n \cdot \frac{e^k}{k^k} \right)^2 = \left( \frac{ k }{ e } \right)^k \cdot \frac{1}{en}. \end{aligned}

If we set $k = (1 / 3) \cdot ( \ln n ) / ( \ln \ln n )$ , then $(k / e)^k \le ( \ln n)^k = n^{1/3}$ and

\begin{aligned} \Pr[ X \le 0 ] \le e^{ -1 } \cdot n^{ - 2 / 3}. \end{aligned}

Remark. For this setting of $k$ ,

\mathbb{E}[X] \ge \left( n \cdot \frac{1}{k^k} \frac{1}{e} \right) \ge e^{-1} n^{2/ 3}.

As in expectation there are $e^{-1} n^{2/ 3}$ such bins, it seems that we are likely to find one. But this alone is not enough to guarantee that $X$ does not deviate from its expectation much. To see why this might cause a problem, consider the random variable $Y$ such that

\begin{aligned} \Pr[Y = e^{-1} n^{ 5 / 3} ] = \frac{1}{n}, \quad \Pr[Y = 0 ] = 1 - \frac{1}{n}. \\ \end{aligned}

$Y$ has expectation $\mathbb{E}[Y] = e^{ - 1} n^{ 2 / 3}$ , but is very likely to be $0$ . The problem with $Y$ is that it has large variance.

Fact. For $i \neq j$ , $\mathbb{Cor}(X_i, X_j) < 0$

Proof.

\begin{aligned} \mathbb{Cor}(X_i, X_j) &= \mathbb{E} [ X_i X_j ] - \mathbb{E} [X_i] \cdot \mathbb{E} [X_j] \\ &= \Pr[X_i = 1, X_j = 1] - \mathbb{E} [X_i] \cdot \mathbb{E} [X_j] \\ &= \binom{n}{k} \binom{n - k}{k} \frac{1}{n^k} \frac{1}{n^k} \left( 1 - \frac{2}{n} \right)^{n - 2k} - \mathbb{E} [X_i] \cdot \mathbb{E} [X_j] \\ &< \binom{n}{k} \binom{n}{k} \frac{1}{n^k} \frac{1}{n^k} \left( 1 - \frac{1}{n} \right)^{n - k} \left( 1 - \frac{1}{n} \right)^{n - k} - \mathbb{E} [X_i] \cdot \mathbb{E} [X_j] \\ &= \mathbb{E} [X_i] \cdot \mathbb{E} [X_j] - \mathbb{E} [X_i] \cdot \mathbb{E} [X_j] \\ &= 0. \end{aligned}

$\square$

The last inequality follows from that

\begin{aligned} \binom{n - k}{k} \left( 1 - \frac{2}{n} \right)^{n - 2k} &= \binom{n}{k} \frac{(n - k) \cdots (n - k + 1)}{n \cdots (n - k + 1)} \left( 1 - \frac{2}{n} \right)^{n - 2k} \\ \end{aligned}

and that (assuming that $k \ge 2$ )

\begin{aligned} \frac{(n - k) \cdots (n - k + 1)}{n \cdots (n - k + 1)} \left( 1 - \frac{2}{n} \right)^{n - 2k} &\le \left( \frac{n - k}{n} \right)^k \left( 1 - \frac{2}{n} \right)^{n - 2k} \\ &\le \left( 1 - \frac{2}{n} \right)^{n - k} \\ &\le \left( \Big( 1 - \frac{1}{n} \Big)^2 \right)^{n - k} \\ &= \left( 1 - \frac{1}{n} \right)^{n - k} \left( 1 - \frac{1}{n} \right)^{n - k}. \end{aligned}

Reference

Sanjeev Arora, Cos 521: Advanced Algorithm Design, Lecture 1: Course Intro and Hashing
Sariel Har-Peled, Chapter 4, The Occupancy and Coupon Collector problems.