Suppose that we throw mm balls into nn bins uniformly at random, where nn is a fixed number. What is the probability that some pair of balls are placed in the same bin?

Define Xi,jX_{i, j} be the indicator variable that the ii-th ball and the jj-th ball go to the same bin. Its expectation is given by

E[Xi,j]=1⋅Pr⁡[Xi,j=1]+0⋅Pr⁡[Xi,j=0]=1n. \mathbb{E}\left[ X_{i,j} \right] = 1\cdot \Pr\left[ X_{i,j} = 1\right] + 0 \cdot \Pr\left[X_{i,j} = 0\right] = \frac{1}{n}.

By linearity of expectation, we have

E[∑1≤i<j≤mXi,j]=∑1≤i<j≤mE[Xi,j]=m(m−1)2n. \mathbb{E}\left[\sum_{1 \le i < j \le m} X_{i,j}\right] = \sum_{1 \le i < j \le m} \mathbb{E}\left[X_{i,j}\right] = \frac{m (m - 1)}{2n}.

When m≈2nm \approx \sqrt{2n}, in expectation, there is a pair of ball going to the same bin. However, this estimate is loose.

Define p(m,n)p(m, n) the exact probability that no ball goes to the same bin. Then

p(m,n)=∏i=0mn−in=∏i=0m(1−in). p(m, n) = \prod_{i = 0}^m \frac{n - i}{n} = \prod_{i = 0}^m \left(1 - \frac{i}{n}\right).

By inequality 1−in≤e−in1 - \frac{i}{n} \le e^{- \frac{i}{n} }, we have a upper bound for the above probability:

p(m,n)≤e−m(m−1)2n. p(m, n) \le e^{- \frac{m (m - 1)}{2n} }.

Therefore, the probability that there is at least one collision is lower bounded by

1−e−m(m−1)2n. 1 - e^{- \frac{m (m - 1)}{2n} }.

If m=nm = \sqrt n, we get e−m(m−1)2n≈e−12≈0.6e^{- \frac{m (m - 1)}{2n} } \approx e^{-\frac{1}{2} } \approx 0.6. If m=2nm = 2 \sqrt n, we get e−m(m−1)2n≈e−2≈0.14e^{- \frac{m (m - 1)}{2n} } \approx e^{-2} \approx 0.14.

In the case n=365n = 365, we say that if there are n≈19\sqrt n \approx 19 people, 40%40\% of times some pair of them share the same birthday. If there are 3636 people, the probability is over 80%80\%.

Remark: let's play some math to bound p(m,n)p(m, n) asymptotically. First, it can be proven that

ex≤1+2x,∀x∈[0,1]. e^x \le 1 + 2 x, \qquad \forall x \in [0, 1].

Hence,

p(m,n)≤e−m(m−1)2n≤exp⁡(−m22n)⋅(1+mn). p(m, n) \le e^{- \frac{m (m - 1)}{2n} } \le \exp \left( -\frac{m^2}{2n} \right) \cdot \left( 1 + \frac{m}{n} \right).

On the other hand, it can be proven that

ln⁡(1−x)≥−x−x2,∀x∈[0,1/2]. \ln (1 - x) % \ge - x - \frac{x^2}{2} \left( \sum_{i = 0}^\infty (\frac{1}{2})^i \right) \ge -x - x^2, \quad \forall x \in [0, 1 / 2].

So, when m<n/2m < n / 2,

p(m,n)=∏i=0m(1−in)≥exp⁡(−∑i=0min−∑i=0mi2n2)≥exp⁡(−m(m−1)2n)(1−∑i=0mi2n2)≥exp⁡(−m22n)(1−O(m3n2)). \begin{aligned} p(m, n) &= \prod_{i = 0}^m \left(1 - \frac{i}{n} \right) \\ &\ge \exp \left( - \sum_{i = 0}^m \frac{i}{n} - \sum_{i = 0}^m \frac{i^2}{n^2} \right) \\ &\ge \exp \left( - \frac{m (m - 1)}{2n} \right) \left( 1 - \sum_{i = 0}^m \frac{i^2}{n^2} \right) \\ &\ge \exp \left( - \frac{m^2}{2n} \right) \left( 1 - O \left( \frac{m^3}{n^2} \right) \right). \end{aligned}

Combined, we get

exp⁡(−m22n)(1−O(m3n2))≤p(m,n)≤exp⁡(−m22n)(1+mn). \exp\left( - \frac{m^2}{2n} \right) \left( 1 - O \left( \frac{m^3}{n^2} \right) \right) \le p(m, n) \le \exp\left( - \frac{m^2}{2n} \right) \left( 1 + \frac{m}{n} \right).

If m<nm < \sqrt n, then m3/n2<m/nm^3 / n^2 < m / n. In this case,

p(m,n)=exp⁡(−m22n)(1±Θ(mn)). p(m, n) = \exp\left( - \frac{m^2}{2n} \right) \left( 1 \pm \Theta \left( \frac{m}{n} \right) \right).

Replacing m=2nln⁡2m = \sqrt{2 n\ln 2}, then

p(m,n)=12+Θ(1n). p(m, n) = \frac{1}{2} + \Theta \left( \frac{1}{\sqrt{n}} \right).

Reference.

[1]. Ryan O'Donnell, Lecture 3, CS Theory Toolkit, CARNEGIE MELLON UNIVERSITY