Birthday Paradox Calculator

The birthday paradox, or birthday problem, asks how large a group has to be before it is more likely than not that two of its members share a birthday. The answer, 23 people, is far smaller than most people expect. That is why it is called a paradox, although nothing in it contradicts anything: it is only surprising.

With 23 people the chance is 50.7297%. With 57 people it passes 99%, and with 366 people it is certain, because a year has only 365 days (leaving out February 29). The same arithmetic answers a more general question: how many values can you draw at random from d possibilities before two of them are likely to be equal? Hash collisions, duplicate IDs and repeated random numbers all follow the birthday problem with d equal to the number of possible values.

• Chance of a shared birthday in a group. Enter the number of people n and the number of days d. The result is the chance that at least two of the n people share a birthday.
• People needed for a target chance. Enter the chance you want, in percent, and the number of days. The result is the smallest group that reaches it, with the chance for that group and for one person fewer.
• The days field starts at 365 and takes any whole number of up to 60 digits. Write a power as 2^64 for a 64-bit hash, which has 18,446,744,073,709,551,616 possible values.
• The result is exact while the product of the fractions can be worked out in whole numbers, which is up to 60,000 digits in the denominator. Beyond that the calculator uses a logarithmic form that is accurate to about 13 significant digits, and the steps say which method was used.
• A group size above 9,007,199,254,740,991 people is refused, and so is a target that lies too close to the chances of two neighbouring group sizes for the logarithm to tell them apart. That starts at about 10^13 people. The chance mode still works for such sizes.

Here n is the number of people and d the number of equally likely days. The first person can have any birthday. The second must avoid the first person's day, which happens with chance (d − 1)/d. The third must avoid two days, with chance (d − 2)/d, and so on. Multiplying gives q(n), the chance that all n birthdays differ, and the chance that at least two match is what is left, 1 − q(n).

q(n) becomes 0 at n = d + 1, because the factor (d − n + 1)/d is then 0. With more people than days two of them must share a day, whatever the birthdays are (the pigeonhole principle).

Choose Load example to enter 23 people and 365 days. Each new person lowers the chance that all birthdays are still different:

• q(23) = (365/365) × (364/365) × … × (343/365) = 0.492703, so the chance of a shared birthday is 1 − 0.492703 = 0.507297, which is 50.7297%.
• With 22 people the chance is 47.5695%, below one half, so 23 is the smallest group that reaches 50%.
• The chance that one of the 23 people has your birthday is 1 − (364/365)^23 = 6.1151%, far lower, because it needs a match with one particular day.
• There are 23 × 22 / 2 = 253 pairs of people, so 253 / 365 = 0.6932 pairs are expected to share a birthday.

Choose People needed for a target chance, enter 90 and 365 days. The calculator multiplies the factors one person at a time and compares each chance with 90% exactly. With 40 people the chance is 89.1232%, still below the target. With 41 people it is 90.3152%, so 41 people are needed. For 99% the answer is 57 and for 99.9% it is 70, so the last few percent cost only a few more people.

The number of pairs grows much faster than the number of people. A group of n people contains n(n − 1)/2 pairs: 253 pairs among 23 people, 1,225 among 50 and 4,950 among 100. Each pair has the same birthday with chance 1/365, so 23 people already give 253 / 365 = 0.69 expected matching pairs.

The chance of a match is not 253/365 = 69%. Adding up the pair chances counts a group with several matching pairs more than once, and the pairs are not independent: if A and B share a day and B and C share a day, then A and C do as well. The expected number of matching pairs is 0.69, and the chance that there is at least one is 50.7297%. For small groups the chance is close to n(n − 1)/(2d), so it grows with the square of the group size and not in proportion to it.

The birthday problem asks for a match between any two people. If instead you want someone in the group to match your birthday, each person has only a 1/365 chance, and the chance for n people is 1 − (364/365)^n. That needs 253 people for a 50.0477% chance (with 252 it is 49.9105%) and 840 people for 90%. The calculator shows this chance next to the shared birthday chance so the two are not confused.

Choose the number of days d equal to the number of possible values. A hash function with b bits has d = 2^b outputs, and the chance that two of n random outputs collide is the birthday problem with those numbers. A collision becomes likely after about 2^(b/2) values, not 2^b, which is why a 128-bit hash gives only about 64 bits of collision resistance against a birthday attack.

For 128 bits or more the group is beyond what the group size mode can decide, but the chance mode still works: 2^64 values drawn from 2^128 possibilities collide with chance 39.3469%. These numbers are for random values. They say nothing about attacks that exploit the structure of a particular hash function.

Two approximations are common. The chance of at least one match is close to 1 − e^(−n(n − 1)/(2d)), and the group size for a chance of one half is close to 1.1774 √d, where 1.1774 is the square root of 2 ln 2. They are good for estimates and for very large d, but they are not exact: for 23 people and 365 days the first gives 50.0002% where the exact chance is 50.7297%, and for 32 bits the second gives about 77,163 where the smallest group is 77,164. The calculator works out the exact value, or the verified logarithmic form for sizes too large for it, and never an approximation.

• Every day is equally likely and the birthdays are independent. Real birthdays are not evenly spread, and twins are not independent. Any uneven spread makes a match more likely, never less, so the figures here are a lower bound for real groups.
• February 29 is left out. With 366 days (choose d = 366) the group for 50% is still 23, and the chance for 23 people becomes 50.6323%.
• "Shared" means any two people, not you. The chance that someone matches your own birthday is much smaller; the calculator shows it separately.
• It is not n/365. The chance of a match is 1 − q(n), which grows with the square of the group size at first and then levels off; it is 50.7297% for 23 people, not 6.3%.
• At least two, not exactly two. The result includes groups with three or more sharing a day and groups with several matching pairs.

Each returns the same answer as the calculator for 365 days. The calculator also handles sizes that overflow a spreadsheet, and it gives the group size for any chance.