Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
The birthday approximation estimates the probability of a collision among n independent hashes into M equally likely values.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
dimensionless probability; n and M are counts
| Symbol | Meaning | Unit |
|---|---|---|
| Pcoll | Probability of at least one collision | dimensionless |
| Number of independently hashed items | count | |
| Size of the uniform hash space | number of possible hash values |
P_{coll}=1-\frac{M!}{(M-n)!M^n}\approx1-e^{-n(n-1)/(2M)}The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It assumes independent uniform values. For cryptographic hashes, this describes random collisions, not every attack or the security of a specific implementation.
The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It assumes independent uniform values. For cryptographic hashes, this describes random collisions, not every attack or the security of a specific implementation.
The birthday approximation estimates the probability of a collision among n independent hashes into M equally likely values.
Defining relation
The equation states the defining relation within its stated domain.
Use the example for Hash collision probability (birthday bound) to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
The birthday approximation estimates the probability of a collision among n independent hashes into M equally likely values.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It.
Formula cluster
The birthday approximation estimates the probability of a collision among n independent hashes into M equally likely values.
For M=365 and n=23, the approximation gives 1−e^(−23·22/(2·365))≈0.500; the exact probability is slightly above one half.
Estimate hash-space sizes, deduplication risks and birthday-bound collision risks.
Here is how to work through a typical Hash collision probability (birthday bound) (Pcoll ≈ 1−exp(−n(n−1)/(2M))) task step by step:
Task
Use the example for Hash collision probability (birthday bound) to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
The birthday approximation estimates the probability of a collision among n independent hashes into M equally likely values.
The relation applies only under its stated assumptions.
The relation Pcoll=1-\frac{M!}{(M-n)!M^n}\approx1-e^{-n(n-1)/(2M)} summarizes The birthday approximation estimates the probability of a collision among n independent hashes into M equally likely values. Read it as a model for defined quantities, not as an automatic claim about every real situation. In the example For M=365 and n=23, the approximation gives 1−e^(−23·22/(2·365))≈0.500; the exact probability is slightly above one half., symbols are connected to concrete values and the result is interpreted in context. Validity limit: The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It Source: MIT OpenCourseWare 6.1200J, Mathematics for Computer Science, Lecture 20: Independence and the Birthday Principle.
First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example For M=365 and n=23, the approximation gives 1−e^(−23·22/(2·365))≈0.500; the exact probability is slightly above one half. provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It Source: MIT OpenCourseWare 6.1200J, Mathematics for Computer Science, Lecture 20: Independence and the Birthday Principle.
The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It Source: MIT OpenCourseWare 6.1200J, Mathematics for Computer Science, Lecture 20: Independence and the Birthday Principle.
The stated units are: dimensionless probability; n and M are counts. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It Source: MIT OpenCourseWare 6.1200J, Mathematics for Computer Science, Lecture 20: Independence and the Birthday Principle.
Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source MIT OpenCourseWare 6.1200J, Mathematics for Computer Science, Lecture 20: Independence and the Birthday Principle. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: The exact probability is one minus the probability that all n hash values are distinct: M(M−1)…(M−n+1)/Mn. For large M and n much smaller than M, approximate it by 1−e^(−n(n−1)/(2M)). It Source: MIT OpenCourseWare 6.1200J, Mathematics for Computer Science, Lecture 20: Independence and the Birthday Principle.
Quanta exam set
Curated exam set for "Hash collision probability (birthday bound)":
Question (front)
Which formula describes Hash collision probability (birthday bound)?
Answer in your set
Question (front)
How do you rearrange Hash collision probability (birthday bound) for Defining relation?
Answer in your set
Question (front)
Which common mistake happens with Hash collision probability (birthday bound)?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for Pcoll ≈ 1−exp(−n(n−1)/(2M)): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential