Birthday Problem

In one sentence: The birthday problem asks how likely it is that some pair of items in a random group match, and the answer rises faster than most people expect.

$P(\text{no collision}) = \prod_{k=0}^{n-1}\left(1 - \frac{k}{N}\right) \approx e^{-n(n-1)/(2N)}$

Read it out loud: “The chance of no collision equals the product, for k from 0 to n minus 1, of one minus k over N. That is roughly e to the power of minus n times n minus 1, over 2 N. The product sign means multiply the factors together. Here n is the number of random items, N is the number of equally likely values, and e is about 2.718.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Probability, or chance: A probability is a chance written as a number from 0 to 1. 0 means impossible, 1 means certain, and 0.5 means a 50 percent chance, which is one in two. The answer 0.5073 means a 50.73 percent chance of a shared birthday, which is about even odds.
Shares, like $\frac{k}{N}$: A fraction $\frac{k}{N}$ is the share of $N$ equally likely values that $k$ of them make up. With $N = 10$ values and $k = 3$ of them taken, the share is $\frac{3}{10} = 0.3$ , which is 30 percent. Dividing by the total is how a share is found.
The product sign $\prod$: The capital Greek letter pi, written $\prod$ , means multiply the terms together, the way the sum sign adds them. For example $\prod_{k=0}^{2}\left(1 - \frac{k}{10}\right)$ means $(1 - 0) \times (1 - 0.1) \times (1 - 0.2) = 1 \times 0.9 \times 0.8 = 0.72$ . Here pi is a multiplication sign, not the number 3.14159.
One minus a chance: If the chance of an event is $p$ , then the chance that it does not happen is $1 - p$ . So if the chance of no match is 0.4927, the chance of at least one match is $1 - 0.4927 = 0.5073$ . Finding ‘at least one’ is often easier by first finding ‘none’ and subtracting it from 1.
Euler’s number $e$ and $e^{x}$: $e$ is a fixed number, about 2.718, that appears whenever a quantity shrinks or grows in proportion to its size. $e^{x}$ is read ‘e to the power x’. A negative exponent, such as $e^{-0.6931}$ , gives a number near 0.5. The exponent $e^{0}$ equals 1, because any number to the power 0 is 1.
Powers of two, like $2^{32}$ , and bits: $2^{32}$ means 2 multiplied by itself 32 times, which equals 4,294,967,296. A bit is a single 0 or 1, and a 32-bit hash is a pattern of 32 bits. So a 32-bit hash has $2^{32}$ possible values, and each extra bit doubles that number.
Random and independent: Random means each outcome is equally likely. Independent means one draw does not change the chance of the next. Knowing one person’s birthday does not change the chance for the next person. Real birthdays are not perfectly even across the year, but this formula assumes they are, so it is a simplified model.

What each symbol means

Symbol	Meaning
$P(\text{no collision})$	The probability that every item gets a different value, so no two match. It is a number from 0 to 1, with no unit. For birthdays, a collision is a shared birthday. For 23 people, it is about 0.4927.
$n$	The number of items drawn at random, such as the number of people in a room. It is a whole number, such as 23, and it has no unit. The formula gets harder to compute as $n$ grows, which is why a shortcut is used.
$N$	The number of equally likely values, such as 365 birthdays in a year, or $2^{32}$ possible 32-bit hash values. It has no unit. A bigger $N$ means collisions are less likely for the same number of items.
$k$	The counter in the product, running from 0 up to $n - 1$ . Each value of $k$ is the number of values already taken. The factor $1 - \frac{k}{N}$ is the chance that the next item avoids those $k$ values. The counter has no unit.
$\prod$	The product sign: multiply together the factors for every $k$ from 0 to $n - 1$ . The result of a product of chances is a chance, a number from 0 to 1, with no unit.
$e$	Euler’s number, about 2.718, the base of the natural logarithm. It has no unit. In this formula it gives a quick estimate of the product, so $e^{-n(n-1)/(2N)}$ is close to $P(\text{no collision})$ .

The formula piece by piece

$\frac{k}{N}$: The share of the $N$ equally likely values that the $k$ values already taken make up. With $N = 365$ days and $k = 22$ birthdays already taken, $\frac{22}{365}$ is about 0.06, which is about 6 percent of the year.
$1 - \frac{k}{N}$: The chance that the next item avoids all $k$ taken values. Those values make up $\frac{k}{N}$ of the year, so the free share is one minus that. For the 23rd person, $k = 22$ , and the free chance is $1 - \frac{22}{365} = \frac{343}{365}$ , which is about 0.94.
$\prod_{k=0}^{n-1}\left(1 - \frac{k}{N}\right)$: The chance that every item avoids the earlier ones. Multiply the chances for each person, from the first at $k = 0$ , whose chance is 1, to the last at $k = n - 1$ . Every step must succeed for the whole product to be the answer, so the chances are multiplied.
$e^{-n(n-1)/(2N)}$: A quick estimate of the same product. Each factor is close to $e$ raised to minus $\frac{k}{N}$ , and the total of those exponents for $k$ from 0 to $n - 1$ is $\frac{n(n-1)}{2N}$ . The estimate is accurate when $n$ is small compared with $N$ .
$P(\text{no collision}) = \prod_{k=0}^{n-1}\left(1 - \frac{k}{N}\right) \approx e^{-n(n-1)/(2N)}$: In one plain sentence: the chance that $n$ random items all have different values equals the product of the chances that each new item avoids the earlier ones, which is roughly $e$ raised to minus $n(n-1)$ divided by $2N$ .

What the formula is doing, and why

What goes in and what comes out. You give the number of random items $n$ and the number of equally likely values $N$ . You get the chance that every item is different, a number from 0 to 1. The chance of at least one match is one minus that number. With 365 days in a year, a group of only 23 people already has better than even odds of a shared birthday, which surprises most people.

Why build it one item at a time? The first item cannot clash with anything, so its factor is 1. The second item must avoid one taken value, which has chance $1 - \frac{1}{N}$ . The third must avoid two taken values, with chance $1 - \frac{2}{N}$ . In general, the factor after $k$ values are taken is $1 - \frac{k}{N}$ . Multiplying all the factors gives the chance that every item is different.

Why does the shortcut work? Multiplying many numbers close to 1 by hand is slow. Each factor is close to $e$ raised to minus $\frac{k}{N}$ , and the sum of $k$ from 0 to $n - 1$ is $\frac{n(n-1)}{2}$ . That gives the shortcut $P \approx e^{-n(n-1)/(2N)}$ , which is accurate when $n$ is small compared with $N$ .

Why does the chance grow so fast? The number of pairs grows much faster than the number of people. With 23 people there are 253 pairs, and every pair is another chance for a match. The chance of at least one match is $1 - P(\text{no collision})$ . For 23 people and 365 days, the exact value is about 50.7%, and the shortcut gives about 50.0%, which is close but not exact.

How fast do collisions come? The number of items needed grows with the square root of $N$ , not with $N$ itself. For a 32-bit hash with $N = 2^{32}$ , about 77,000 random keys already give roughly a 50% chance of a collision. That is far fewer than the 4 billion possible values, which is why collisions come sooner than intuition suggests.

An everyday picture

Think of guests at a party who each pick a random day of the year as their birthday. The first guest’s day cannot match anyone yet. Each new guest has one more day already taken, so the chance of avoiding all of them shrinks. The number of pairs grows much faster than the number of guests, and each pair is another chance for a match.

Worked example: A shared birthday in a group of 23

A group of $n = 23$ people is picked at random. Each birthday is one of $N = 365$ equally likely days, and leap years are ignored. What is the chance that at least two people share a birthday? We find the chance that no two share one, and then subtract it from 1.

Write the chance of no match. We need $P(\text{no collision}) = \prod_{k=0}^{22}\left(1 - \frac{k}{365}\right)$ . The product runs from $k = 0$ up to $k = 22$ , which is 23 factors, one for each person in the group.
Write out the first few factors. The first person’s factor is $1 - \frac{0}{365} = 1$ , because nobody has been placed yet. The second person’s factor is $1 - \frac{1}{365} = \frac{364}{365}$ , about 0.9973. The third is $\frac{363}{365}$ . The last factor, for the 23rd person, is $\frac{343}{365}$ , about 0.9397.
Multiply all 23 factors. Multiply the chances together, one after another. The product comes to about 0.4927, which is the chance that all 23 birthdays are different. Each step must succeed for the whole product to be the answer.
Subtract from 1 to get the match chance. The chance of at least one shared birthday is $1 - 0.4927 = 0.5073$ . Multiplying by 100 gives a percentage of about 50.7 percent, which is more than even odds.
Check with the shortcut. The exponent is $\frac{23 \cdot 22}{2 \cdot 365} = \frac{506}{730} \approx 0.6932$ . Then $e^{-0.6932} \approx 0.5000$ , which gives 50.0 percent. That is close to the exact 50.7 percent, so the shortcut is a good estimate here.
See what 50 people does. The same method with 50 people gives a chance of about 97 percent, which is almost certain. The chance climbs fast because each new person adds more pairs to compare with everyone else.

Answer: With only 23 people, the chance of a shared birthday is about 50.7%, which is more than even odds. With 50 people the chance rises to about 97%.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Confusing a shared birthday with a match for one person. For a fixed person, a match with any of 22 others is about 6 percent, because $\frac{22}{365} \approx 0.06$ . A 50 percent chance that someone shares your birthday needs about 253 other people.
Forgetting to subtract from 1. The product gives the chance of no match. The chance of a match is one minus that number.
Using the shortcut for very large $n$ without checking. It is close when $n$ is small compared with $N$ . The exact product is safer when the two numbers are close in size.

Where you will meet it

Estimating how many random hash values can be stored before a collision is likely. A 32-bit hash has $2^{32}$ possible values, and about 77,000 random keys give roughly a 50 percent chance of a collision.
Checking the risk of duplicate IDs when random identifiers are generated, such as random 64-bit or 128-bit IDs, where each bit doubles the number of possible IDs.
Cryptography, where a birthday attack finds two inputs with the same hash value faster than trying every possible input. A hash is a fixed-size fingerprint of some data.
Teaching probability, as a classic case where intuition about chance fails.

Questions people ask

How many people give a better than even chance of a shared birthday?

23 is the smallest group where the chance passes one half. With 22 people the chance is about 47.6 percent, and with 23 it is about 50.7 percent.

What does N mean for hash collisions?

$N$ is the number of possible hash values. For a 32-bit hash, $N = 2^{32}$ , and about 77,000 random keys give roughly a 50 percent chance of a collision.

Does the formula assume people are random?

It assumes each birthday is equally likely and independent of the others. Real birthdays are not perfectly even across the year, and uneven spreads make matches a little more likely. The model is still a useful guide.

Pigeonhole Principle: If you put more things than boxes into the boxes, at least one box must hold two or more things.
Hash Table Load Factor: The load factor is how full a hash table is on average: the number of keys divided by the number of buckets.
Bloom Filter False Positive Rate: This formula gives the chance that a Bloom filter, a small memory-saving checklist, wrongly says an item is on the list, based on how many bits and checks it uses.