4 ms·

The Birthday Problem [1]: How many people do you have to put in a room before there's a 50% chance of two having the same birthday. Assuming a uni

The Birthday Problem [1]: How many people do you have to put in a room before there's a 50% chance of two having the same birthday. Assuming a uniform distribution of birthdays. The answer turns out to be about 23. In general, for M possible birthdays (other than 365, say), you need about sqrt(M) people before you get a 50% chance. The article is a standard introduction to the Birthday Problem with some real world data thrown in. The 'paradox' comes from the surprise that the number is so low (23) compared with the number of days in the year (365). As the article points out, one short description of why the number is so low is that you're comparing each new person with every person already in the room instead of drawing two numbers at random and seeing if they're the same. For the curious, I have a minimal post on how to derive the Birthday Paradox and other canonical probability problems [2]. [1] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem [2] https://mechaelephant.com/dev/Assorted-Small-Probability-Problems/ https://mechaelephant.com/dev/Assorted-Small-Probability-Pro...

bhl 7y ago
An even, shorter intuition would be that: number of pairs in a group of n people grows O(n^2), which implies some square root factor. I would lead with that before starting a more rigorous proof.
- waterhouse 7y ago
  Agreed. To narrow down some of the details: There are n*(n-1)/2 = roughly n^2 / 2 pairs. If each pair has a 1/k chance of matching, then the expected number of pairs that match is (n^2 / 2) / k. Therefore, if we set n = √k, we get roughly 0.5 pairs on average. Now, if it were impossible to ever get multiple matching pairs, then "the chance there's at least one match" would be equal to "the expected number of matches". Specifically: "chance of at least 1 match" = "expected number of matches" - "chance of at least 2 matches" - "chance of at least 3 matches" - ... . Since it's possible but unlikely to get multiple matches, the approximation should be reasonably close.
yitchelle 7y ago
It feels that the number of 23 is specific to the context of birthdays. If it was switched to a different context such as coming from the same part of the word, or driving the same car, would the result be as surprising?
- arithma 7y ago
  I believe statistician ecologists use the reverse in an interesting way. Tag 100 units from a species, say goats (failure of imagination on my part) from a certain location. Then sample 100 other animals at a different time, controlling for time spent and so on, and the ratio of tagged animals that come up in the result will give statistical information about the total population of said species.

bhl 7y ago

An even, shorter intuition would be that: number of pairs in a group of n people grows O(n^2), which implies some square root factor. I would lead with that before starting a more rigorous proof.

waterhouse 7y ago
Agreed. To narrow down some of the details: There are n*(n-1)/2 = roughly n^2 / 2 pairs. If each pair has a 1/k chance of matching, then the expected number of pairs that match is (n^2 / 2) / k. Therefore, if we set n = √k, we get roughly 0.5 pairs on average. Now, if it were impossible to ever get multiple matching pairs, then "the chance there's at least one match" would be equal to "the expected number of matches". Specifically: "chance of at least 1 match" = "expected number of matches" - "chance of at least 2 matches" - "chance of at least 3 matches" - ... . Since it's possible but unlikely to get multiple matches, the approximation should be reasonably close.

yitchelle 7y ago

It feels that the number of 23 is specific to the context of birthdays. If it was switched to a different context such as coming from the same part of the word, or driving the same car, would the result be as surprising?

arithma 7y ago
I believe statistician ecologists use the reverse in an interesting way. Tag 100 units from a species, say goats (failure of imagination on my part) from a certain location. Then sample 100 other animals at a different time, controlling for time spent and so on, and the ratio of tagged animals that come up in the result will give statistical information about the total population of said species.