Collision-probability result
Birthday Paradox
A group needs surprisingly few people before the probability that at least two share a birthday becomes substantial, because the number of possible pairs grows quadratically.
P(match) = 1 - product from k=0 to n-1 of (365-k)/365
The classic calculation assumes 365 equally likely independent birthdays and ignores leap day. Real seasonality and dependence change the number slightly but not the pair-count mechanism.
The room uses deterministic resampling so collisions can be inspected. The exact probability is calculated separately from the displayed random room.
(%)
The primary slider and this instrument share one state.
- CHANGE
- People in the room
- WATCH
- collision probability
- MEANING
- The room uses deterministic resampling so collisions can be inspected. The exact probability is calculated separately from the displayed random room.
The room grows linearly; the number of pairs grows quadratically.
Calendar cells highlight collisions while the pair counter exposes the source of the surprise.
What it actually says
The paradox is a mismatch between intuition and comparison count. With n people there are n(n-1)/2 unordered pairs, so collision opportunities accumulate far faster than room size.
The usual question asks whether any pair matches, not whether somebody matches your own birthday. The latter has only n-1 comparisons and requires a much larger group.
"A useful law compresses a pattern. It does not erase the conditions that make the pattern true."
How the idea developed
The modern form emerged through observation, argument, and later refinement. The timeline separates the first insight from the version now used in textbooks and practice.[1]
Probability texts popularize birthday collision calculations.
Richard von Mises discusses related coincidence problems.
Feller's textbook makes the example a standard probability lesson.
Hashing, cryptography, occupancy models, and data deduplication use birthday bounds.
How the pattern works
The relation becomes useful only when its mechanism, measurement process, and operating range are visible.
It is easier to multiply probabilities that every birthday is distinct.
Potential pairs increase as n squared over two.
Matches become likely near the square root of the number of categories.
Nonuniform dates generally make collisions at least as concentrated.
The classic calculation assumes 365 equally likely independent birthdays and ignores leap day. Real seasonality and dependence change the number slightly but not the pair-count mechanism.
Where it earns its keep
Applications are strongest when the law changes a decision, measurement, model, or experiment rather than merely providing an analogy.
Size hash spaces
ApplicationBirthday bounds estimate accidental collision risk.
Account for adversaries, truncation, and nonuniform inputs.
Understand collision security
ApplicationAn ideal b-bit hash offers roughly b/2 bits of collision resistance.
Preimage and collision goals are different.
Diagnose duplicate identifiers
ApplicationUnexpected repeats can reveal small namespaces or generation bias.
Estimate the actual source distribution.
Where it stops working
The textbook threshold changes with category count, unequal probabilities, dependence, and the definition of a match.
A probability over random rooms does not predict which room or pair will collide.
"Twenty-three people means a match is guaranteed"
Better: The probability is only just above one half."The question is who shares my birthday"
Better: It asks whether any pair matches."Birthdays must be perfectly uniform"
Better: Seasonality changes the exact probability but not the core effect."A hash collision reveals malicious behavior"
Better: Ordinary collisions are expected at sufficient scale.Sources and further reading
Original publications and serious secondary scholarship are prioritized over summaries.
- Diaconis and Mosteller - Methods for Studying CoincidencesSystematic treatment of coincidence problems.https://doi.org/10.1080/01621459.1989.10478847
- Feller - An Introduction to Probability TheoryClassic probability text.https://www.wiley.com/en-us/An+Introduction+to+Probability+Theory+and+Its+Applications%2C+Volume+1%2C+3rd+Edition-p-9780471257080
- NIST - Hash FunctionsAuthoritative cryptographic context.https://csrc.nist.gov/projects/hash-functions
- MIT Mathematics for Computer ScienceOpen combinatorics and probability textbook.https://courses.csail.mit.edu/6.042/spring18/mcs.pdf