Mind Games: The Birthday Paradox Will Blow You Away!

Added on 15 March 2017, 19:44, Updated on 17 March 2017, 11:41

If we told you that there are a number of people gathered in a room next door and that there’s better than a 1-in-2 chance that two of them share the same birthday. How many people would you think are in that room?

The number is in fact quite small — just 23. In a room of 75, there’s a 99.9% chance of two people matching.

This is what’s known as the birthday problem. More specifically, it refers to the chances that any two people in a given group share a birthday. The reason it is a “problem” is that most people — puzzle lovers and math majors excepted — tend to underestimate its likelihood.

Let’s see why the paradox happens and how it works.

Source: https://betterexplained.com/articles/und...

Exponents aren’t intuitive.

We’ve taught ourselves mathematics and statistics, but let’s not kid ourselves: it’s not natural.

Here’s an example: What’s the chance of getting 10 heads in a row when flipping coins? The untrained brain might think like this:

“Well, getting one head is a 50% chance. Getting two heads is twice as hard, so a 25% chance. Getting ten heads is probably 10 times harder… so about 50%/10 or a 5% chance.”

And there we sit, smug as a bug on a rug. No dice bub.

After pounding your head with statistics, you know not to divide, but use exponents. The chance of 10 heads is not .5/10 but .510, or about .001.

What’s striking is that such a small increase of the size of the group can totally skew the odds against you.

At 5% interest, we’ll double our money in 14 years, rather than the “expected” 20. Did you naturally infer the Rule of 72 when learning about interest rates? Probably not. Understanding compound exponential growth with our linear brains is hard.

No you're not as unique as you think. Neither is your birthday...

As math professor Steven Strogatz mentions in this New York Times post, the birthday problem highlights how wrong our intuition can be when it comes to coincidences and chance. We often don’t consider the question carefully enough to conceive such a high number of potential birthday matches.

In a room of 23, do you think of the 22 comparisons where your birthday is being compared against someone else’s? Probably.

We start comparing how small one number is to the other: “Well… my birthday is Oct. 6… and there are 22 other birthdays in the room… and 22 divided by 365 is pretty small…”

But this question isn’t just about you — it’s about every person in the room and the chance that anyone might find a match. The first person in the group has 22 potential birthday matches. The second has 21 (one less because we already counted the first person/second person pair). The third has 20. The fourth has 19. When you add all these up, you get 253 potential birthday pairs.

The fact that we neglect the 10 times as many comparisons that don’t include us helps us see why the “paradox” can happen.

Maybe because birthdays are so intensely personal, it’s easy to turn a question about finding any birthday matches into one about finding my birthday match. It might be why this puzzle is illustrated with birthdays in the first place.

Ok, fine, I was wrong: Show me the math!

The question: What are the chances that two people share a birthday in a group of 23?

Sure, we could list the pairs and count all the ways they could match. But that’s hard: there could be 1, 2, 3 or even 23 matches!

It’s like asking “What’s the chance of getting one or more heads in 23 coin flips?” There are so many possibilities: heads on the first throw, or the 3rd, or the last, or the 1st and 3rd, the 2nd and 21st, and so on.

How do we solve the coin problem? Rather than counting every way to get heads, find the chance of getting all tails, our “problem scenario.”

If there’s a 1% chance of getting all tails (more like .5^23 but work with me here), there’s a 99% chance of having at least one head. I don’t know if it’s 1 head, or 2, or 15 or 23: we got heads, and that’s what matters. If we subtract the chance of a problem scenario from 1 we are left with the probability of a good scenario.

The same principle applies for birthdays. Instead of finding all the ways we match, find the chance that everyone is different, the “problem scenario.” We then take the opposite probability and get the chance of a match. It may be 1 match, or 2, or 20, but somebody matched, which is what we need to find.

Explanation: Counting Pairs.

With 23 people we have 253 pairs: (23x22)/2=253

(Brush up on combinations and permutations if you like).

The chance of 2 people having different birthdays is: 1-(1/365)=0.997260.

Makes sense, right? When comparing one person's birthday to another, in 364 out of 365 scenarios they won't match. Fine.

But making 253 comparisons and having them all be different is like getting heads 253 times in a row -- you had to dodge "tails" each time (let’s assume birthdays are independent). We use exponents to find the probability: (364/365)^253=0.4995.

Our chance of getting a single miss is pretty high (99.7260%), but when you take that chance hundreds of times, the odds of keeping up that streak drop. Fast.

The chance we find a match is: 1 – 49.95% = 50.05%, or just over half!

Here are a few lessons from the birthday paradox:

sqrt(n) is roughly the number you need to have a 50% chance of a match with n items. sqrt(365) is about 20. This comes into play in cryptography for the birthday attack.
Even though there are 2128 (1e38) GUIDs, we only have 264 (1e19) to use up before a 50% chance of collision. And 50% is really, really high.
You only need 13 people picking letters of the alphabet to have 95% chance of a match. Try it above (people = 13, items = 26).
Exponential growth rapidly decreases the chance of picking unique items (aka it increases the chances of a match). Remember: exponents are non-intuitive and humans are selfish!

After thinking about it a lot, the birthday paradox finally clicks with me. But I still check out the interactive example just to make sure.

How do you feel?