Balls and Bins

Balls and bins are a group of classic problems centered around how random objects are distributed around finitely many outcomes.

Probability of No Collisions

This problem is often informally called the Birthday “Paradox”. Suppose we toss \(n\) balls into \(m\) bins, uniformly at random. What is the probability that no two balls end in the same bin? If \(n > m\), the probability of a collision must be \(1\) by the pigeonhole principle. If \(n \leq m\), then:

\[\mathbb{P}[\text{no balls collide}] = \frac{m}{m} \frac{m-1}{m} ... \frac{m-n+1}{m}\]

Probability of Max Load

Suppose we toss \(n\) balls into \(n\) bins. What is the maximum number of balls in any bin?

Proposition: There exists constant \(c\) such that w.h.p., the max load per bin is \(\leq \frac{c \log n}{\log \log n}\).

Proof: First, note that \(\forall k > \frac{3 \log n}{\log \log n}\), the probability that an arbitrarily chosen bin has load exactly \(k\) is \(o(1/n^2)\):

\[{n \choose k} (1/n)^k (1 - 1/n)^{n-k} \leq (\frac{n^k}{k!}) (1/n)^k = 1/(k!)\]

And per Stirling:

\[1/(k!) \leq (e/k)^k \leq \Big(\frac{e \log \log n}{3 \log n} \Big)^{3 \log n / \log \log n}\]

This quantity is upper bounded by:

\[n^{-3 + 3 \log \log \log / \log \log n} = o(1/n^2)\]

Second, we can union bound over all possible \(n\) bins and all \(<n\) relevant values of \(k\):

\[\mathbb{P}[\text{Any bin has load } > \frac{3 \log n}{\log \log n}] = o(1)\]