The Birthday Problem

 

A Generalization                      

We will generalize the birthday problem to apply to any number of days in the year and to any probability that two birthdays are the same.

 On a planet that revolves around the Sun in  n days, the number of native-born partygoers needed to make the probability of two identical birthdays at least  1 - p is the smallest integer  k such that:

where 
is the number of permutations of  n partygoers taken  k at a time.
 The number of pairings of those  k partygoers is:

b= C(k, 2)

where 
is the number of combinations of  k partygoers taken 2 at a time.
 The number of partygoers, in addition to yourself, needed to make the probability that one of them shares your birthday at least 1 - p is 
, where:

We will show that   b and  c are approximately equal, not only for  n= 365  and  p= .5, the parameters of the standard problem, but for all reasonable values of  n and   p. The fact that both  b and  c are 253 is not much of a coincidence at all.

 We can use this knowledge to relate  c and  k as follows:

Solving for k:


This formula computes an excellent approximation to  k , with error<1.0 when  n> 4 and  p> .04. It can be expressed as a function of  n and  p as follows:


With a calculator or computer, it is easier to use this formula to compute  k than to iteratively multiply probabilities.

  1. The Proof