In a set of n people what is the probability that two share a birthday? Funnily enough, we need only 23 people to have a 50% chance of two people sharing the same birthday. So how many for a 100% chance? Of course, 365 people. But what about a 99% chance?
With only 70 people you will have a 99% chance of two people sharing a birthday!
Can you think of any reason this might be true? We consider each pair of individuals. With 10 people, for example, we have (10x9)/2 = 45 pairs to consider. This is much more than just 10 pairs. However, the number of total pairs to consider definitely does not vary linearly.
We exclude, for the sake of simplicity, leap years, seasonal variations or any variables that may cause uneven distribution of elements in the sample space. Having an uneven distribution undoubtedly increases the likelihood of two people sharing a birthday. We consider the worst-case scenario: a perfectly random distribution.
It is far easier to compute the probability P(X) of no two people sharing a birthday in each set than the other way around. Let’s see why that is.
In a set of 10 people, numbered from 1 to 10, we can proceed person by person, utilizing conditional probability. The probability of no two people sharing a birthday is the same as the event of person 2 not sharing a birthday with person 1, person 3 with neither person 1 or person 2 and so on.
Person 1 definitely has a birthday. There is only a one in 365 chance that person 2 shares this birthday, and therefore a 364/365 chance they don’t. Proceeding similarly we can see that there is a probability of 363/365 that the third person does not share a birthday with either person 1 or person 2.
Continuing for 10 people,
This equates to an 88.3052% chance of two people not sharing a birthday, and therefore approximately an 11.7% chance of sharing a birthday.
Can you compute the probabilities of not sharing a birthday for some other values of n? You will find that you obtain a value very close to 50% at n=23.
Computing for different values of n,
Can you plot these values on a graph? You will observe that this probability varies logarithmically.
We now have sufficient information to obtain a generalized formula for this probability for any n number of people. Of course, n must be less than 366. From the pigeonhole principle, or common sense, it is obvious that at least two people must share a birthday for n=366. There is 100% likelihood of a shared birthday thereafter, since there are only 365 days in a year.
And there you have it! This “counterintuitive” problem isn’t that counterintuitive at all. This is in fact true for many probability problems. Do you have “Eureka” moments after reading solutions? I certainly do :)
The mathematics behind the birthday paradox is also exploited extensively in cryptography. A famous application is the birthday attack, a cryptographic attack that cracks algorithms by matches in hash functions (a fancy word for codes). The heart of this attack lies in the fact the likelihood of finding an intersection between target codes is more than expected. Attackers can find matching bits of code with fewer iterations.
Can you think of any other ways one might use the birthday paradox?
If you liked this article, let me know using the contact forms below! Please feel free to email me at arushee.tj@gmail.com with any questions, problems, solutions or suggestions for future blog posts. Until next time :D
Comments