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.

Understanding the paradox

The key to understanding the birthday paradox is to realize that there are many possible pairs of people whose birthdays could match. Specifically, among 23 people, there are C(23,2) = 23 × 22/2 = 253 pairs, each of which being a potential candidate for a match. Looked at in this way, it doesn't seem that unlikely that one of these 253 pairs yields a match.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

To emphasize the point, consider a different scenario: if you enter a room with 22 other people, the chance that somebody there has the same birthday as you is not 50:50, but much lower. This is because now there are only 22 possible pairs that could yield a match. The actual birthday problem is asking if any of the 23 people have a matching birthday with any of the others.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~