23 people. In a room of just 23 people there’s a 50-50 chance of two people having the same birthday. In a room of 75 there’s a 99.9% chance of two people matching.

This is a companion discussion topic for the original entry at http://betterexplained.com/articles/understanding-the-birthday-paradox/

The math here is actually wrong. The chances of individual pairs are not independent. You math would work if you take each pair and have them name a random number between 1 and 365.

With this math, taking a group of 365 people still results in a non-zero chance that they all have different birthdays.

Thanks for the info, you’re right. I did some more digging (good paper here) and birthdays aren’t mutually independent.

If Person 1 = Person 3, and Person 3 = Person 5, there isn’t an independent event that Person 1 = Person 5. The probability of 1 matching 5 has already been determined by the other statements.

From what I was able to gather, this is only a problem if there are existing overlapping pairs. For a small n relative to the number of outcomes (365), it’s unlikely to have multiple matches that affect the probability, so assuming independence may be ok for computing approximations.

[…] Understanding the Birthday Paradox | BetterExplained: Understanding the Birthday Paradox […]

[…] Regarding your birthday, whether you are savvy with Hamming’s error correcting code or not, listen to Kalid Azad when he presents Understanding the Birthday Paradox posted at BetterExplained in which he explains the Birthday Paradox from statistics. […]

[…] Understanding the Birthday ParadoxUnderstanding the Pareto Principle (The 80/20 Rule)Law of Unintended ConsequencesSpeed Up Your Javascript, Part 2: Downloadable Examples!Number Systems and Bases Like it? Share on: […]

The last formula is incorrect, it should be:
n ~ sqt(-2 ln(1-p)) sqt(T)
^^^
or else you are finding the probability to miss.

Thanks for the tip! I fixed up the article to use p(different) and p(match), which is much more clear.

The “take-away lesson” about GUIDs is wrong. GUIDs are (theoretically) guaranteed to be globally unique, because they include such things as the MAC address of your network card (something which is globally unique until some cheap NIC manufacturer starts recycling them) and the current time.

The catch is that because of the time factor, the current GUID algorithm won’t last forever. We will run out in a couple of centuries.

Hi, that’s a good point about MAC addresses. However, if you consider GUIDs as just a giant random number (for the purposes of the exercise), you are looking for how many “items” out of a pool of 2^128 you can distribute before having a 50% chance of collision.

For the birthday paradox, it’s about 23 items (of a pool of 365) before a 50% chance of collision. For GUIDs, it will be roughly 2^64 items before a 50% chance of collision.

Hope this helps,

-Kalid

can the math in the birthday paradox applicable to pick3 lottery?

Hi Allan, I’m not too familiar with the rules of Pick3, but I’ll take a shot.

The birthday paradox helps find the chance that any two random numbers will “collide” in a set.

In Pick3, you don’t really care if two guesses collide… you want the guess to collide with the winning number. In this case, two losing tickets that both guessed 123 (when the real answer was 999) isn’t helpful.

I may be missing something though!

Hey, great blog.
"" A coarse first-order Taylor approximation for e^x is: \displaystyle{e^x \approx 1 + x}"

that’s just valid if x

[…] if x

[…] if x is far less than 1

Je suis tombé par hasard (c’est souvent le cas sur Internet de nos jours) sur ce paradoxe des anniversaires qui stipule que dans une réunion regroupant 23 personnes, la probabilité que deux d’entre elles soient nées le même jour est…

I am doin a science fair experiment on this i need help–and i need to know if the math is over my head!!!

@nt: Thanks for the tip, I updated the article to make that more clear.

@Ashton: Hi Ashton, you might want to ask your math teacher to see if you’ve covered the necessary topics in class. You’ll probably need statistics and combinatorics.

hello kalid,
i read a few of your articles and think they are freaking awesome.

thanks and keep up the good work.

Hi Zhao, thanks for the comment! I’ll try to keep cranking out the posts :).