Mathematical Foundations: Balls in Bins

The number of ways to partition \(n\) objects into groups of sizes \(k_1, k_2, \ldots, k_r\) (where \(\sum k_i = n\)):

The binomial coefficient is the special case \(r = 2\).

The number of unordered pairs from \(m\) items appears constantly in birthday-type problems:

For \(m\) balls thrown into bins, there are \(\binom{m}{2}\) pairs that could potentially collide.

To show a collision is likely when \(m \approx \sqrt{n}\) balls land in \(n\) bins, we need to estimate the probability of no collision:

Using Stirling to approximate the factorials converts this to a tractable exponential form.

To collect all \(n\) coupons, the expected time is:

Each "phase" (going from \(k-1\) distinct to \(k\) distinct) is geometric with success probability \((n-k+1)/n\), contributing \(\frac{n}{n-k+1}\) in expectation. Summing over all \(n\) phases gives \(n\,H_n\).

A related but different series:

This converges (unlike the harmonic series) and appears in variance calculations for the coupon collector problem.

The coupon collector decomposes into \(n\) phases. In phase \(i\) (already have \(i-1\) distinct coupons, waiting for the \(i\)-th new one), each trial succeeds with probability:

The waiting time \(T_i \sim \text{Geometric}(p_i)\) with \(\mathbb{E}[T_i] = \frac{n}{n-i+1}\). The total time is \(T = \sum_{i=1}^{n} T_i\), and by linearity:

For \(X = \sum_i X_i\):

The covariance terms vanish when \(X_i, X_j\) are pairwise independent (i.e., \(\mathbb{E}[X_i X_j] = \mathbb{E}[X_i]\mathbb{E}[X_j]\)).

Let \(C = \sum_{\{i,j\}} \mathbf{1}_{ij}\) count collisions among \(m\) balls in \(n\) bins, where \(\mathbf{1}_{ij}\) indicates balls \(i,j\) land in the same bin. There are \(\binom{m}{2}\) such indicators. Computing \(\operatorname{Var}[C]\) requires analyzing \(\mathbb{E}[\mathbf{1}_{ij}\,\mathbf{1}_{kl}]\) for all pairs of pairs. Three cases arise:

The "magic": overlapping pairs have \(\mathbb{E}[\mathbf{1}_{ij}\mathbf{1}_{jk}] = 1/n^2 = \mathbb{E}[\mathbf{1}_{ij}]\cdot\mathbb{E}[\mathbf{1}_{jk}]\), so even though \(\mathbf{1}_{ij}\) and \(\mathbf{1}_{jk}\) share ball \(j\), they are uncorrelated! This makes the variance calculation much cleaner:

The key power of the Poisson model: if we throw \(\text{Poisson}(\lambda)\) balls (instead of exactly \(m\)) uniformly into \(n\) bins, then the bin loads \(B_1, B_2, \ldots, B_n\) are mutually independent, each distributed as \(\text{Poisson}(\lambda/n)\).

This makes the maximum load analysis tractable — we can analyze each bin separately and apply a union bound.

Key Instance: \(\mathbb{E}[\ln X] \leq \ln \mathbb{E}[X]\)

Since \(\ln\) is concave, Jensen gives \(\mathbb{E}[\ln X] \leq \ln(\mathbb{E}[X])\). Equivalently, by exponentiation:

for any random variable \(Y\) (using \(f(y) = e^y\), which is convex).

To bound the maximum of random variables, convert it to a sum using the exponential function. For any \(t > 0\):

The inequality holds because \(\max \leq \sum\) for non-negative quantities.

The bound holds for all \(t > 0\), so we choose \(t\) to minimize \(e^{e^t - 1 - tk}\). Taking the derivative and setting to zero:

Substituting: the exponent becomes \(k - 1 - k\ln k \approx -k\ln k\) for large \(k\). Combined with the union bound factor \(n\), we get the maximum load is \(O(\ln n / \ln\ln n)\) with high probability — by balancing \(n \cdot e^{-k\ln k} \leq 1/n\).