Birthday Paradox Calculator
Solve the standard birthday-collision approximation for any of its three unknowns — the collision probability, the number of people, or the number of possible outcomes — with step-by-step math, a scaled probability schematic, and companion metrics including exact-probability validation.
Why 23 people is enough for 50%
The confusion behind the birthday paradox comes from confusing the number of comparisons with the number of people. With n people, there are n(n−1)/2 pairs — for n = 23 that is 253 pairs, each with roughly a 1/365 chance of matching. Multiply that out and you get roughly 50%. The number of pairs, not the number of people, is what drives the probability, and pairs grow quadratically while people grow linearly. That quadratic growth is exactly what the formula P ≈ 1 − e−n²/(2m) captures.
The approximation is stunningly accurate
The formula P ≈ 1 − e−n²/(2m) uses the fact that ln(1−x) ≈ −x for small x. It is an approximation of the exact product formula P = 1 − m!/(mn(m−n)!). For the classical 365-day case, the approximation is within 0.1% of the exact value for every n from 1 to 100. That level of accuracy is why this compact expression is used everywhere from statistics textbooks to cryptography courses — the exact formula is a factorial mess; the approximation is a clean, differentiable expression you can solve for any variable.
The formula behind cryptographic security
The birthday paradox is the entire basis of collision resistance for cryptographic hash functions. SHA-256 produces 256-bit hashes, so m = 2256. By the birthday formula, a collision becomes likely after roughly sqrt(2 · m · ln 2) ≈ 2128 hashes — the "birthday bound." That is why cryptographic standards require an output length of 2N bits to protect against N-bit attacks. Every modern hash function, from SHA-2 to SHA-3 to BLAKE3, is designed with this exact formula in mind.
Small changes in m have huge effects
Changing the number of possible outcomes from 365 to 366 (leap year) barely moves the collision probability. Changing it from 365 to 1000 moves the 50% crossover from 23 people to 38. Changing it from 365 to 1,000,000 moves the crossover to 1,178. The crossover scales as roughly 1.18 · sqrt(m), which is why doubling the number of hash buckets increases the collision-free group size by only about 41%. This 1/sqrt(m) scaling is one of the most important facts in hashing and cryptography.
How to Use This Calculator
The birthday-paradox relation links three quantities: the collision probability, the group size, and the number of possible outcomes. Pick which one you want the tool to solve, then fill in the others.
1. Choose what to solve for
Pick P, n, or m. The calculator rearranges the formula automatically for whichever variable you choose and locks that field.
2. Use the domain preset
The top-right selector switches m between 365 (classical), 366 (leap), 12 (months), 7 (weekdays), and 10,000 (typical hash bucket count). Everything updates instantly.
3. Watch the exact probability alongside
The mini-card "EXACT P" always shows the true probability computed with the product formula, so you can verify how close the approximation is for your inputs.
4. Read the result and verdict
The result card shows the solved value plus a colour-coded verdict from negligible collision risk through unlikely, meaningful, likely, very likely, and near-certain.
5. Check the schematic
A probability bar shows the current value on a 0% to 100% scale, and the milestone strip shows the classical group sizes (23, 41, 57, 70).
6. Switch to Advanced for depth
Advanced mode adds a target-probability input, a second chart showing how the required group size scales with the target, sensitivity, and fifteen companion metrics including collision-pair counts.
What This Tool Offers
Built around the classic birthday-paradox approximation — the counter-intuitive result that just 23 people are enough to make a shared birthday more likely than not.
Three-way solving
Solve for the probability, the group size, or the number of outcomes. The calculator rearranges the formula for whichever variable you choose.
Exact vs approximation
Every result is compared against the exact product-formula probability so you can see precisely how much error the approximation introduces.
Target probability planner
Enter any target — 50%, 99%, 99.99% — and the calculator reports the minimum group size needed to reach or exceed it.
Cryptographic mode
Set m = 232 or 264 and see the birthday bound for hash collisions in real time — the same calculation used in cryptographic security analysis.
Dual comparison charts
Probability vs. group size for the approximation and exact formulas, plus a second chart of group size vs. target probability.
Reference tables
A full probability lookup across classical group sizes for m = 365, common values of m with their 50% crossover sizes, and the underlying variables.
Reference Tables & Conversions
A probability lookup for the classical m = 365 case, common values of m with their 50% crossovers, and the underlying variables.
Classical birthday probability (m = 365)
Computed from P ≈ 1 − e−n²/(2·365), with the exact value shown alongside for comparison.
| Group size n | Approximation P | Exact P | Error |
|---|
Common Values of m and Their 50% Crossover Sizes
The number of people needed for a 50% collision probability scales as roughly 1.18 · sqrt(m).
| Value of m | Domain | 50% crossover n | 99% crossover n |
|---|---|---|---|
| 2 | Binary outcome | 2 | 3 |
| 6 | Dice rolls | 4 | 7 |
| 7 | Weekdays | 4 | 8 |
| 12 | Months | 5 | 10 |
| 30 | Days in a month | 7 | 16 |
| 52 | Card deck | 9 | 21 |
| 100 | Percentile buckets | 12 | 29 |
| 365 | Days in a year | 23 | 57 |
| 1,000 | Random IDs | 38 | 95 |
| 10,000 | Small hash space | 119 | 300 |
| 1,000,000 | 6-digit IDs | 1,178 | 3,000 |
| 232 | 32-bit hash | ≈ 77,000 | ≈ 200,000 |
| 264 | 64-bit hash | ≈ 5.1 billion | ≈ 13 billion |
| 2128 | 128-bit hash (MD5) | ≈ 2.2 × 1019 | ≈ 5.6 × 1019 |
| 2256 | 256-bit hash (SHA-256) | ≈ 4.0 × 1038 | ≈ 1.0 × 1039 |
Variable Reference
| Symbol | Meaning | Typical range | Notes |
|---|---|---|---|
| n | Number of people (or items) | 0 – 109 | Non-negative integer |
| m | Number of possible outcomes | 1 – 1012 | 365 for classical birthday, 2N for N-bit hash |
| P | Collision probability | 0 – 1 | Probability at least two items share a value |
| Q | No-collision probability | 0 – 1 | Q = 1 − P |
| n50% | 50% crossover size | ≈ 1.18·√m | 23 for m = 365 |
| n99% | 99% crossover size | ≈ 3.03·√m | 57 for m = 365 |
What Does the Birthday Paradox Measure?
The birthday paradox measures the probability that at least two people in a group of size n share the same birthday, assuming all birthdays are equally likely and independently assigned. The counter-intuitive result — that just 23 people are enough for the probability to exceed 50% — is why it is called a "paradox": it contradicts the intuition that you would need far more people to guarantee a match.
The reason is that the probability is not driven by the number of people but by the number of pairs. With n people there are n(n−1)/2 pairs, and each pair has a 1/m chance of matching. That quadratic growth in the number of pairs overwhelms the linear growth in the number of people, and drives the probability up far faster than intuition suggests. With 23 people there are 253 pairs — each with roughly a 1/365 chance — which multiplies out to about a 50% total chance of at least one match.
The approximation P ≈ 1 − e−n²/(2m) captures this quadratic dependence in a single compact expression. It is derived from the exact product formula P = 1 − m!/(mn(m−n)!) by using the small-x expansion ln(1 − x) ≈ −x, and it is accurate to within a fraction of a percent for essentially all practical values of n and m. That accuracy, combined with its differentiability, is why it appears everywhere in statistics, cryptography, and computer science.
The Birthday Paradox Formula
The defining approximation is:
The exact probability (for comparison) is:
Rearranged to solve for the other unknowns:
m ≈ −n² / (2 · ln(1 − P))
Two useful crossover formulas:
n99% ≈ 3.034 · √m (99% probability)
Birthday Paradox Variables
| Symbol | Meaning | Notes |
|---|---|---|
| n | Group size | Number of people (or items) in the collision check |
| m | Number of possible outcomes | 365 for classical, 2N for N-bit hash |
| P | Collision probability | Probability at least two share the same value |
| Q | No-collision probability | The complement: Q = 1 − P |
| Pairs | Number of pairs in the group | = n(n−1)/2 |
How Each Variable Affects the Result
The probability depends on n and m through the ratio n²/(2m). Doubling n quadruples the exponential argument and dramatically increases the probability. Doubling m halves the argument and decreases it. That is why the crossover group size scales as √m — to achieve the same probability with a larger m, you need proportionally more people, but only as the square root. This square-root relationship is the single most important fact about the birthday paradox and the basis for all cryptographic collision bounds.
The exponential form means the probability rises very quickly near the crossover point. At m = 365, the probability goes from 47.5% at n = 22 to 50.7% at n = 23 to 89% at n = 40 to 99.4% at n = 57. The transition from "unlikely" to "almost certain" happens over a range of only 30–40 people — a difference of less than a factor of two in group size. This sharpness is what makes the birthday paradox so counter-intuitive and so useful as a security metric.
The approximation is better for large m and moderate n, and slightly worse near the extremes. For m = 365 the approximation is within 0.1% for the entire range n = 1 to 100. For m = 2 (a coin flip), the approximation is quite poor and the exact formula should be used instead. For cryptographic m (2128, 2256), the approximation is extremely accurate — the error is on the order of 1/m, which is 10−77 for SHA-256.
Birthday Paradox Calculation Examples
P ≈ 1 − e−23² / (2·365) = 1 − e−0.7247 = 1 − 0.4845 = 51.55%
Exact = 50.73% (approximation error ~0.8%)
n ≈ √(−2·365 · ln(0.5)) = √(505.9) = 22.49
Minimum integer group size = 23
P ≈ 1 − e−41² / (2·365) = 1 − e−2.303 = 90.0%
P ≈ 1 − e−57² / (2·365) = 1 − e−4.451 = 98.84%
n ≈ √(−2·4.29e9 · ln(0.5)) ≈ 77,000
This is the "birthday bound" for a 32-bit hash — a collision becomes likely after ~77,000 hashes.
Frequently Asked Questions
It is called a paradox because the answer contradicts most people's intuition — but it is not a paradox in the logical sense. The intuition says "with 365 possible birthdays and 23 people, the probability of a match should be small." That intuition implicitly compares 23 to 365 and thinks "23 out of 365 is only 6%, so probably no match." But that is the wrong comparison. The right comparison is the number of pairs, not the number of people. With 23 people there are 23·22/2 = 253 pairs, and 253 comparisons against 365 possibilities is enough to push the collision probability over 50%.
Extremely accurate for realistic values of m. For m = 365 the approximation is within 0.1% for the entire range of practical group sizes (n from 1 to 100). For larger m — like cryptographic hash sizes — the approximation is even more accurate, with error on the order of 1/m. The approximation uses the fact that ln(1 − x) ≈ −x for small x, which is a very good approximation whenever n is much smaller than √m and both are much smaller than m. It only breaks down when m is very small (like m = 2) or when n approaches m.
The classical milestones for m = 365 are: 23 people for 50% probability, 32 people for 75%, 41 people for 90%, 47 people for 95%, 57 people for 99%, and 70 people for 99.9%. The exact value at n = 23 is 50.73%, and the approximation gives 51.55% — a difference of less than a percentage point. The 50% crossover is the most famous, but the 99% crossover at 57 is also widely cited because it is the group size used in many cryptographic security arguments.
The birthday paradox sets the collision resistance bound for any hash function. If a hash function produces N-bit outputs, there are m = 2N possible values. By the birthday formula, an attacker who computes roughly 2N/2 hashes can expect to find a collision with about 50% probability. That is why NIST and other standards require hash outputs to be twice as long as the security level they claim: SHA-256, with 256-bit outputs, is only 128-bit secure against birthday attacks. SHA-1, with 160-bit outputs, is only 80-bit secure — which is why it was deprecated. Every modern cryptographic primitive is designed with this formula in mind.
Not well. For m = 2 (a coin flip), the approximation gives P(n=2) ≈ 1 − e−4/4 = 63.2%, while the exact value is 50%. For m = 6 (dice), the approximation is somewhat better but still off by several percentage points at small n. The approximation is designed for the case m ≫ n, which is the realistic case for the birthday problem. For very small m, use the exact product formula directly. This calculator always shows both values side-by-side, so you can see at a glance when the approximation is safe.
The exact formula is P = 1 − m!/(mn(m−n)!). This comes from computing the probability that all n values are distinct: the first value can be anything (probability 1), the second must avoid the first (probability (m−1)/m), the third must avoid both (probability (m−2)/m), and so on. Multiplying all these probabilities together gives the no-collision probability Q = m·(m−1)·(m−2)·…·(m−n+1)/mn, and P = 1 − Q. The factorial form is exact but impractical for large m because it involves huge numbers; the approximation is used instead.
The e comes from the mathematical identity limx→∞(1 − 1/x)x = 1/e. The no-collision probability can be written as a product of terms like (1 − k/m), and when you take the logarithm of this product and use ln(1 − x) ≈ −x, you get a sum of the form −(1 + 2 + 3 + … + (n−1))/m = −n(n−1)/(2m). Exponentiating back gives Q ≈ e−n(n−1)/(2m), which for large n simplifies to e−n²/(2m). That is where the e and the n² term come from — they emerge naturally from the product structure of the exact formula.
The birthday paradox appears wherever you need to estimate collision risk among randomly-generated identifiers. Examples include: cryptographic hash collision resistance (SHA-256, MD5), UUID and session token uniqueness, database record ID collisions, network packet sequence number wraparound (TCP, IPsec), hash table load factor and resize thresholds, DNA fingerprinting and forensic match probability, credit card fraud detection (transaction hash collisions), randomised load balancing (job scheduler collisions), and even polling sample analysis. Any time you generate random values and want to know the probability that two of them match, the birthday formula gives you the answer in closed form.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| P | Probability of at least one collision | |
| n | Number of items hashed | |
| m | Number of possible hash values |
What it means
The birthday paradox is a counter‑intuitive probability result that the chance of a collision (two items hashing to the same bucket) grows quickly with the number of items. For a hash table with m buckets, and n inserted keys, the approximate probability of at least one collision is P ≈ 1 − exp(−n²/(2m)), assuming a uniform hash function. This approximation is derived from the Poisson distribution and is accurate for n much smaller than m. It shows that even with a seemingly large number of buckets, collisions become likely as n approaches √m. For example, with m = 10⁶, a collision is already probable for n ≈ 1200. This analysis is crucial for designing hash tables: to keep collision probability low, either increase the number of buckets (lower load factor) or use a better hash function. The birthday problem also appears in cryptography (e.g., birthday attacks on hash functions) and in data deduplication. Understanding this approximation helps in tuning hash table parameters and in estimating the performance of hash‑based algorithms.
Worked example
Hash Collision Probability – Two Examples
Real‑World| Parameter | Value |
|---|---|
| n (items) | 100,000 |
| m (hash space) | 4.29×10⁹ |
| Parameter | Value |
|---|---|
| n (items) | 100,000 |
| m (hash space) | 1.84×10¹⁹ |
Common mistakes
- Approximation: The formula is an approximation for large m and n; for small values, the exact probability may differ.
- Units: n is the number of keys, m is the number of buckets – both integers.
- Assumption: Assumes a uniform hash function; if the hash is poor, collisions are more likely.
- Complement probability: The formula gives the probability of at least one collision; the probability of no collision is e^(−n²/(2m)).
- n²/(2m): If this product is large, the probability approaches 1; for small values, it’s close to n²/(2m).
Applications
The Birthday paradox approximation for hash collisions, P ≈ 1 − e^(−n²/(2m)), estimates the probability of at least one collision when storing n keys in m buckets. This probability grows quickly with n, making it a critical consideration in hash table design, password security, and cryptography. Engineers use this formula to choose an appropriate table size and load factor to keep collision probability acceptably low. It also appears in the analysis of distributed hash tables, birthday attacks on cryptographic hashes, and in data deduplication. Understanding this formula helps in designing robust hash‑based systems, in assessing security risks, and in balancing performance with memory usage.
- Hash table sizing and performance tuning
- Cryptography – analysis of collision attacks
- Distributed hash tables (DHTs)
- Data deduplication and similarity detection
- Randomised algorithms and probabilistic analysis
Related calculators · Data Structures
Recently updated formulas
Suggest an improvement
Found a mistake? Have a better example? Let us know.
You may send up to 3 suggestions per 24 hours.