Hacker News Reader

Comment by loonoddoo | Hacker News Reader

In what sense is the birthday paradox a paradox?

It is not a logical paradox, it is very counterintuitive. With just about 23 samples, you'll have a birthday collision with 50% chance. Many people would think to get 50%, you'd need 183 samples.

It is also counterintuitive, because it is unavoidable. Even with a very large hash range, one can force a collision with a relatively small number of samples.

It's sometimes called the Birthday Problem to avoid the paradox label. (See, for example, the wikipedia article.)

The paradoxy bits of the problem are the things that people find confusing. "Only 23?!" or "So if there are 23 people in a room there's a 50% chance that one of them will share a birthday with me?"

Is "So if there are 23 people in a room there's a 50% chance that one of them will share a birthday with me?" correct? If you pick a fixed person (you) that would break the pigeonhole principle, I think.

I would think that saying "So if there are 23 people in the room there is a 50% chance any 2 of those people share the same birthday" is better.

Edit: I misunderstood, you're saying that other people are misunderstanding. My mistake!

You're misquoting or misunderstanding. The comment to which you are replying said:

    The paradoxy bits of the problem are the things that
    people find confusing. "Only 23?!" or "So if there are
    23 people in a room there's a 50% chance that one of
    them will share a birthday with me?"

In that comment he is saying that people mis-understand the question, and assume that it means that once there are 23 people in the room, then there's a 50:50 chance they will share a birthday with them specifically.

And that's exactly the wrong question, as you point out. So when you say:

    Is "So if there are 23 people in a room there's a 50% chance
    that one of them will share a birthday with me?" correct?

No, that's not correct, but it is what people think they hear, and it's that confusion that makes this whole thing sometimes called a paradox.

So let's be clear:

    If you're in a room with 22 other people, the chance
    that one of them shares a birthday specifically with
    you is nowhere near 50%

    However, the chance that among the 23 people in the
    room there is, somewhere, a shared birthday, is indeed
    slightly greater than 50%

And my experience is that it really doesn't matter how carefully you word this, some people simply will not understand it.

You're right, I misunderstand the comment I replied was using that as an example of how other people misunderstand the problem. D'oh. Edited!

The same sense that the Banach-Tarksi paradox[1] is: it's a counter-intuitive mathematical truth.

[1]: https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

"a seemingly absurd or self-contradictory statement or proposition that when investigated or explained may prove to be well founded or true: in a paradox, he has discovered that stepping back from his job has increased the rewards he gleans from it."

Reply on news.ycombinator.com