Problem
Let’s say you go to a research conference with some other people. There are a total of n people in the room. You are really bored after a while, and start off thinking about birthdays! You want to find out what number of people share the same birthday, or better still, share it with you.
Assuming that these people are randomly chosen and have birthdays which can be equally likely on any day of the year. You need to find the probability that two people selected randomly share the same birthday. As an addition, you also want to find out what is the probability that someone shares the same birthday as you! This would be a function of n, and let’s try to see what is the value of the probability as n changes. For example, what should be the value of n for this probability to be greater than half?
Solution
Let’s just disregard that some variations in the distribution such as leap years, twins, weekly variations, etc. since that just complicates the problem but does not change the main idea of it.
From the pigeonhole principle, (fancy name for a simple idea), if n>365, then there definitely are two people at the conference with the same birthday. This is simple, but what about n=365 or slightly less?
At first glance, it seems that due to the number of birthdays possible, the required n would be large. Let’s try to mathematically formulate the problem now:
We need to compute P(n) which is the probability that at least two people in a room of n people have the same birthday. However, it is simpler to calculate P(n’), the probability that no two people in that room have the same birthday. These two possibilities are mutually exclusive, and can never occur at the same time. Hence, both add up to one.
Let’s say the first person has a birthday on day x, then the second person should not have a birthday on that day. This can occur with a probability of 364/365 since he can select any of the other 364 days. Similarly, the third person cannot select any of the already selected 2 days and is left with 363/365. Hence, for any generic person who comes to select at place i, he will not have i-1 places left for him. The probability for him to select a day, such that there are no common birthdays would be (366-i)/365.
Multiplying them together, we will get:
This looks like a complicated equation, hence we can just use some code to plot the graph corresponding to this. This is the plot of the probability that two people share a birthday as a function of n, (effectively plotting 1-P(n’))
You can see from here that for the probability to be greater than 0.5, you need only 23 people in the room! There are some interesting approximations which can be derived using Taylor series/Poisson approximation for the above formula, which makes it easier to handle the calculation in an interview! (Head to this)
What if you want to find a person who has the same birthday as you? What would be the answer then? Note that in the above question, neither of the two people are chosen in advance. The probability that no one has the same birthday as you would be: (364/365)^n. Thus, for any general n, the probability is:
Putting in n=23, which we got from the above question, we get a probability of 6.12% only! You need around 220 people for even cross the 50% barrier, which is 10 times more hard. Plotting this alongside the previous curve, we get:
Looks like the probability for someone to share the birthday with you is very less, even when there are a lot of people!
Hope you liked this puzzle! Please drop a like and share this newsletter amongst your friends. We would appreciate any kind of feedback, so do comment if you want us to cover any specific topics, or tweak something!