Birthday Paradox Variance

First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US.

Here's an interesting approach to the birthday paradox using variances.

Suppose we have m people who have birthdays spread uniformly over n days. We want to bound m such that the probability that there are are at least two people with the same birthay is about one-half.

For 1 ≤ i < j ≤ m, let A_i,j be a random variable taking value 1 if the ith and jth person share the same birthday and zero otherwise. Let A be the sum of the A_i,j. At least two people have the same birthday if A ≥ 1.

E(A_i,j) = 1/n so by linearity of expectations, E(A) = m(m-1)/2n. By Markov's inequality, Prob(A ≥ 1) ≤ E(A) so if m(m-1)/2n ≤ 1/2 (approximately m ≤ n^1/2), the probability that two people have the same birthday is less than 1/2.

How about the other direction? For that we need to compute the variance. Var(A_i,j) = E(A_i,j²)-E²(A_i,j) = 1/n-1/n² = (n-1)/n².

A_i,j and A_u,v are independent random variables, obvious if {i,j}∩{u,v} = ∅ but still true even if they share an index: Prob(A_i,jA_i,v = 1) = Prob(The ith, jith and vth person all share the same birthday) = 1/n² = Prob(A_i,j=1)Prob(A_i,v=1).

The variance of a sum of pairwise independent random variables is the sum of the variances so we have Var(A) = m(m-1)(n-1)/2n².

Since A is integral we have Prob(A < 1) = Prob(A = 0) ≤ Prob(|A-E(A)| ≥ E(A)) ≤ Var(A)/E²(A) by Chebyshev's inequality. After simplifying we get Prob(A < 1) ≤ 2(n-1)/(m(m-1)) or approximately 2n/m². Setting that equal to 1/2 says that if m ≥ 2n^1/2 the probability that everyone has different birthdays is at most 1/2.

If m is the value that gives probability one-half that we have at least two people with the same birthday, we get n^1/2 ≤ m ≤ 2n^1/2, a factor of 2 difference. Not bad for a simple variance calculation.

Plugging in n = 365 into the exact formulas we get 19.612 ≤ m ≤ 38.661 where the real answer is about m = 23.

Enjoy the Thanksgiving holiday. We'll be back on Monday.