Birthday Problem and Hash Collisions
- Show why 23 people are enough for a better-than-even chance that two share a birthday. Set up the complement, and explain intuitively why the answer is so much smaller than 365/2.
- A team generates 6-character IDs from a 36-character alphabet (36^6 ≈ 2.18 billion possibilities) and assumes collisions are "practically impossible" until they have billions of records. Using the birthday approximation P(\text{collision}) \approx 1 - e^{-n^2 / (2H)}, estimate the number of IDs at which the collision probability reaches 50%. Is the assumption right?
- Explain the Monty Hall result (switching wins with probability 2/3), and state exactly which assumption about the host the result depends on.
1. The birthday problem
Compute the complement — the probability that all n birthdays are different:
Each new person must avoid all birthdays already taken. For n = 23 the product is about 0.493, so P(\text{at least one shared}) \approx 0.507.
The intuition failure is comparing each person to yourself (23 chances at 1/365 each, roughly 6%). But the event is "any pair matches", and 23 people form \binom{23}{2} = 253 pairs, each with a 1/365 chance. With 253 chances at roughly 1/365 the odds of at least one hit are about 1 - (364/365)^{253} \approx 0.50. The number of pairs grows as n^2, which is why the threshold is near \sqrt{365}, not 365/2.
2. Hash / ID collisions
Set 1 - e^{-n^2/(2H)} = 0.5, so n^2 = 2H \ln 2 and n = \sqrt{2 \ln 2 \cdot H} \approx 1.177 \sqrt{H}. With H = 2.18 \times 10^9: \sqrt{H} \approx 46{,}700, so n \approx 55{,}000.
The team hits a coin-flip chance of at least one duplicate ID after only about 55 thousand IDs — not billions. Collisions scale with the square root of the space, because what matters is the number of pairs. Either use a much larger space (128-bit UUIDs, H = 2^{128}, first collision expected around 2^{64} keys) or check-and-retry on insert.
3. Monty Hall
Your initial door hides the car with probability 1/3; the other two doors jointly hold 2/3. The host, who knows where the car is, always opens one of the other two doors and always reveals a goat. His action cannot change the 1/3 on your door (he can always find a goat to show regardless of where the car is), so the entire 2/3 collapses onto the single remaining closed door. Switching wins 2/3 of the time.
The critical assumption: the host deliberately opens a goat door with knowledge of the car's location. If the host opened a random door and it merely happened to be a goat, the situation would be symmetric between the two closed doors and switching would win only 1/2 of the time — the information content of the reveal comes from the host's constraint, not from the open door itself.
Share this question