The Birthday Paradox

How many people do you need before the probability that two of them have the same birthday is 50%? The answer to this question is, amazingly, 23. This surprising result is known as the birthday paradox. The word paradox is used here in the sense that the result is intuitively unexpected, not in the usual sense of a logical contradiction.

To determine a formula to compute the probability, and to see that 23 is indeed the correct answer, it is easier to compute the probability that there are no two people in the group that share a birthday. The wanted result is then simply one minus that probability, because there are only two possibilities that are mutually exclusive.

If there is only one person, then the probability that there is no other person with the same birthday is 1. Moreover, one day of the year is now “occupied” by that person. If a second person is added, his or her birthday has to be one of the other 364 days. Hence, the probability that the person has a different birthday is 364/365. Two days of the year are now “occupied”. I assume a year of 365 days, so ignoring leap years. I also assume that al dates are equally probable as a birthday.

If a third person is added, then there are 363 days left if he or she has to have a different birthday from the first two. The total probability is then

\[1\times\frac{364}{365}\times\frac{363}{365}.\]

This can then be extended for \(n\) people, as

\[\frac{365}{365}\times\cdots\times\frac{365-n+1}{365}=\prod_{i=0}^{n-1}\frac{365-i}{365}=\prod_{i=0}^{n-1}\left(1-\frac{i}{365}\right).\]

Hence, for \(n\) people, the probability that two of them have the same birthday is

\[1-\prod_{i=0}^{n-1}\left(1-\frac{i}{365}\right).\]

The probability is 97% for 50 people, and crosses the 99% mark for 57 people. In a group of 70 people, the chance is already 99.9%. Hence, if you invite 70 people to your wedding, there’s only about a one in a thousand chance that there are no two people with the same birthday. For a one in a million chance, invite 97 people…

Python Code

As usual, the Python implementation is short. The example code is for 23 people.

from __future__ import print_function
from __future__ import division
 
n = 23
p = 1
for i in range(n):
    p *= 1 - i / 365
print(1 - p)