The Number Of Empty Bins.

Problem

There are $n$ balls and $m$ bins, where $m \gg n$. Each ball goes into a bin uniformly and independently at random. What is the number of empty bins?

Analysis

1. The probability of a particular bin being empty is $(1 - 1 / m)^n$.

   Proof: The probability of a particular ball not falling into this bin is $1 - 1 / m$. Therefore,

   $$\Pr[ \text{none of the balls falls into this bin} ] = \left( 1 - \frac{1}{m} \right)^n.$$

2. The expected of empty bins is $m \cdot (1 - 1 / m)^n$.

   Proof: For $j \in [m]$, define the indicator random variable $Z_j$ that equal to $1$ if the $j$-th bin is empty. Then by linearity of expectation,

   $$\mathbb{E} \left[ \sum_{j \in [m] } Z_j \right] = \sum_{j \in [m] } \mathbb{E} [ Z_j ] = m \cdot \left( 1 - \frac{1}{m} \right )^n.$$

3. With probability at least $1 - \delta$ ($\delta \in (0, 1)$), the number of empty bin is

   $$m \cdot (1 - 1 / m)^n \pm \sqrt{ \frac{n}{2} \ln \frac{2}{\delta} }.$$

   Proof: We need to use McDiarmid inequality.

   McDiarmid inequality ( [1] ). Consider an arbitrary set $\mathcal{D}$. The function $f: \mathcal{D} ^n \rightarrow \mathbb{R}$ has bounded difference if there exits nonnegative constants $b_1, ..., b_n \in \mathbb{R}$ such that for $i \in [n]$,

   $$\sup_{ x_1, ..., x_n , x_i' \in \mathcal{D} } | f(x_1, ..., x_n ) - f( x_1, ..., x_{i - 1}, x_i', x_{i + 1}, ..., x_n ) | \le b_i. >$$

   Consider a set of independent random variables $X_1, ..., X_n$ sampled from $\mathcal{D} $. Denote $Y \doteq f(X_1, ..., X_n)$. It holds that

   $$\Pr [ Y - \mathbb{E} [ Y ] \ge \epsilon ] \le \exp \left( - \frac{2 \epsilon^2 }{ \sum_{i \in [n]} b_i^2 }\right). >$$

   The analogous inequality is valid for $\Pr [ \mathbb{E} [Y] - Y \ge \epsilon ]$.

   To apply the theorem, let $\mathcal{D} = [m]$. For $i \in [n]$, define the random variable $X_i \in \mathcal{D}$ to be the index of the bin that the $i$-th ball falls into. Let $Y \doteq f (X_1, ..., X_n)$ be the number of empty bins, which is a random variable that depends on $X_1, ..., X_n$. We have proven that

   $$\mathbb{E} [ Y ] = m \cdot \left( 1 - \frac{1}{m} \right)^n.$$

   Further, the outcome of the $i$-th ball can affect the number of empty bins by at most $1$:

   $$\sup_{ x_1, ..., x_n , x_i' \in \mathcal{D} } | f(x_1, ..., x_n ) - f( x_1, ..., x_{i - 1}, x_i', x_{i + 1}, ..., x_n ) | \le 1.$$

   Hence, by McDiarmid inequality,

   $$\Pr [ | Y - \mathbb{E} [ Y] | \ge \epsilon ] \le 2 \cdot \exp \left( - \frac{2 \epsilon^2 }{ n } \right).$$

   Equating this probability to $\delta$, we get

   $$\epsilon = \sqrt{ \frac{n}{2} \ln \frac{2}{\delta} }.$$

Reference

[1] C. McDiarmid, “Concentration,” in Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, pp. 195–248.