Birthday paradox

The birthday paradox states that if there are 23 people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. This means that in a typically-sized school class, where the 'paradox' is often cited, an even higher probability often applies. For 60 or more people, the probability is already greater than 99%. This is not a paradox in the sense of leading to a logical contradiction; it is a paradox in the sense that it is a mathematical truth that contradicts common intuition. Most people estimate that the chance is much lower than 50:50. Calculating this probability (and related ones) is the birthday problem. The mathematics behind it has been used to devise a well-known cryptographic attack named the birthday attack.

Calculating the probability

To compute the approximate probability that in a room of n people, at least two have the same birthday, we disregard distribution variations, such as leap years, twins, seasonal or weekday variations, and assume that d = 365 possible birthdays are equally likely. Real-life birthday distributions are not uniform since not all dates are equally likely.

Related Topics:
Leap year - Twin

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note that keeping d generic allows us to find the (approximate) solution to a more general problem: given n random integers drawn from a discrete uniform distribution with range , what is the probability that at least two numbers are the same?

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The trick is to first calculate the probability p(n;d) that all n birthdays are different. If n > d, by the pigeonhole principle this probability is 100%. On the other hand, if n ≤ d, it is given by

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:ar p(n;d) = 1 cdot left(1-rac{1}{d} ight) cdot left(1-rac{2}{d} ight) cdots left(1-rac{n-1}{d} ight) = prod_{k=1}^{n-1}left(1-{k over d} ight) ,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

because the second person cannot have the same birthday as the first (364/365), the third cannot have the same birthday as the first two (363/365), etc.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Using the Taylor series expansion (some may say the definition) of the exponential function

Related Topics:
Taylor series - Exponential function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: e^x = 1 + x + rac{x^2}{2!}+cdots

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

the above expression can be approximated as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:ar p(n;d) pprox 1 cdot e^{-1/d} cdot e^{-2/d} cdots e^{-(n-1)/d}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

::= 1 cdot e^{-(1+2+ cdots +(n-1))/d}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

::= e^{-(n(n-1))/2d}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The event of at least two of the n persons having the same birthday is complementary to all n birthdays being different. Therefore, its probability p(n;d) is

Related Topics:
Event - Complementary

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: p(n;d) = 1-ar p(n;d) pprox 1 - e^{-(n(n-1))/2d}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Substituting n = 23 and d = 365 gives a probability of about 50.7%. The following table shows other probabilities, numerically computed using the formula above, for d = 365:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Accuracy of the approximation

An even coarser approximation to the answer is given by

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:p(n;d)pprox 1-e^{-n^2/2d},,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

which, as the graph illustrates, is still fairly accurate for d = 365.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~