Those in the know will be very aware that I have had a lot of time on my hands recently. In that time I have chosen to learn various bar scams or magic tricks and also to read up on slightly random subjects that interest me.
One such subject that’s been doing the rounds recently is the Birthday Paradox.
The Birthday Paradox asks the question “How many people would you need in order for 2 of those people to share a birthday?”.
The first answer many people arrive at is 366. One person for each day then 1 extra to share a birthday with someone. After a few minutes this is increased to 367 to account for those born on the 29th of February, but we won’t deal with leap years.
These answers are, of course, correct. For a one hundred percent chance that 2 people in a group share a birthday you will need 367 people. But that’s boring. What makes the Birthday Paradox so much more interesting is just how few people you actually need to get very close to 100% coverage.
Some of you will be shocked, infuriated, surprised and maybe even amazed to hear that you only need 23 people for a 50% chance that 2 of those people share a birthday.
“That doesn’t make any sense!” you scream. It’s certainly not intuitive but read on to see how it makes sense and how you can see it on Facebook.
How does it work?
Let’s look at what is actually happening. Take a group of people who are appropriately named 1, 2, 3, 4, etc, right up to 50 – it’s as if they were born to be in a statistic.
What we’re doing is comparing every persons birthday to every other person in the room and looking for 2 that share a birthday.
So we have 50 people, with 49 pair comparisons and we’re looking for just 2 people with the same birthday. This means we have (50 * 49) / 2 comparisons. Which, as any decent calculator will tell you, is 1,225. The generalised way to write that equation, where n = 50, is n * (n – 1) / 2.
Now as it turns out the simplest way to work out the odds that 2 of these 50 people share a birthday is to work out the chance that 2 people don’t share a birthday and go from there.
And the chance of 2 people not sharing a birthday is 364 / 365 = 0.9972 = 99.72%.
That’s 1 – 1/365 or all but 1 date from a possible 365 (as we know 1 person has that birthday already).
You can apply this to our group of 50 people to find out the odds of 2 people in that group not sharing a birthday by doing: (364 / 365) ^ 1,255 = 0.0319 = 3.19%.
This means that in a room with only 50 people there is a 3.19% chance that 2 of them do not share a birthday. In other words, there is a 96.81% chance that 2 of them do.
In fact it only takes 23 people for there to be a 50-50 chance that 2 people share a birthday.
Whilst this is already an interesting bit of maths I thought it would be interesting to see a real-world example. And what better way to do that than with Facebook. That’s right! I have finally found a use for Facebook!
Simply go here, select the number of friends you want to compare and let the app run.
You can read more on the Birthday Paradox on Wikipedia and this article by Kalid over at Better Explained. There’s also a scene from the excellent Bang Goes The Theory here.
Also, special thanks to Kalid for proofreading this for me. So, erm, any mathematical errors are his fault…
For those that are interested here is a Python function to calculate the odds given n people.
def birthday_paradox(n): NO_SHARED_DAY = 0.9972 comparisons = n * (n-1) / 2 return 100 - (pow(NO_SHARED_DAY, comparisons) * 100)