The Birthday Problem

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.