What is the birthday problem and what does it reveal about probability intuition?

How to think about it

The birthday problem asks for the chance that at least two people in a group share a birthday. With 23 people and 365 equally likely birthdays, that chance is 50.7% — because those 23 people create 253 possible pairs, not just 23 chances to compare against one date.

The reasoning an interviewer wants

The clean way to solve it is to calculate the complement, meaning the opposite event.

“At least one shared birthday” is awkward to count directly because several matches can happen at once. Instead, calculate the probability that every birthday is different, then subtract from 1:

P(at least one match) = 1 - P(all birthdays are distinct)

For the first person, there is no restriction. Any birthday is acceptable. For the second person, 364 of the 365 dates are still available. For the third, 363 dates remain available, and so on.

For n people:

P(all distinct) =
(365/365) × (364/365) × (363/365) × ... × ((365 - n + 1)/365)

P(at least one match) = 1 - P(all distinct)

The equivalent factorial form is:

P(all distinct) = 365! / ((365 - n)! × 365^n)

For 23 people, the last person must avoid the 22 dates already occupied:

P(all distinct) =
(365/365) × (364/365) × ... × (343/365)
≈ 0.4927

P(at least one match) = 1 - 0.4927
≈ 0.5073

So the answer is about 50.7%.

The direct approach is tempting but dangerous. There are 253 pairs, and each pair has a 1/365 chance of matching. But pair events overlap. If Alice matches Bob and Bob matches Carol, then Alice necessarily matches Carol too. The collection of pair events is not mutually independent, so simply multiplying or adding pair probabilities does not give the exact answer.

A concrete 23-person example

Imagine a 23-person onboarding session. Someone asks whether two people in the room share a birthday.

The relevant question is not:

Does somebody share my birthday?

It is:

Does any pair in the room share a birthday?

The number of pairs is:

23 × 22 / 2 = 253

That is the source of the surprise. Every new person can match every person already in the room. The number of possible comparisons grows roughly as the square of the group size.

Here are the standard values under the uniform, independent 365-day model:

People	Chance of at least one shared birthday
10	11.7%
23	50.7%
30	70.6%
57	99.0%

The exact calculation is short enough to check rather than trust on faith:

from math import prod

def collision_probability(n, days=365):
    all_distinct = prod((days - i) / days for i in range(n))
    return 1 - all_distinct

for n in (10, 23, 30, 57):
    print(n, format(collision_probability(n), ".1%"))

It prints:

10 11.7%
23 50.7%
30 70.6%
57 99.0%

The common misconception: a fixed birthday

The birthday problem is often confused with a different question.

Suppose your birthday is known to be 12 March. What is the chance that at least one of the other 22 people in the room was also born on 12 March?

Now there is only one target date. Each person has a 1/365 chance of matching it, so:

P(no one matches your birthday) = (364/365)^22
P(at least one match) = 1 - (364/365)^22
≈ 5.9%

That is much lower than 50.7%.

To reach a 50% chance that someone matches your fixed birthday, you need 253 other people, or 254 people total including you. The two questions have different answers because they count different events:

• Fixed target: compare each person with one date.
• Birthday problem: compare every person with every other person.

Common misconception: the 50.7% result does not mean that one particular person has a 50.7% chance of finding a birthday twin in a room of 23. It means that some pair among the 253 possible pairs is likely to match.

What the pair count reveals about intuition

For any particular pair, the chance of a match is only 1/365, or about 0.274%. That feels negligible.

But there are 253 chances for a match in a 23-person room. A useful quantity here is the expected number of matching pairs:

E[number of matching pairs] = number of pairs × probability per pair
                                 = 253 × (1/365)
                                 ≈ 0.693

This is another place where intuition slips. An expected count of 0.693 is not a 69.3% chance of at least one match. An expectation counts all matches, including situations where three or more people share a birthday. A probability asks only whether the count is zero or nonzero.

The broader lesson is that rare events become common when there are enough opportunities for them. The same pattern appears in duplicate identifiers, hash collisions, repeated experiments, and multiple-comparison problems in statistics.

The useful approximation

For a space of D equally likely values and n independent draws, the probability of no collision can be approximated by:

P(no collision) ≈ exp(-n(n - 1) / (2D))

P(at least one collision) ≈ 1 - exp(-n(n - 1) / (2D))

The approximation comes from taking the natural logarithm of the exact product and using ln(1 - x) ≈ -x when x is small.

For a 50% collision probability, this gives:

n ≈ sqrt(2D × ln(2))
  ≈ 1.177 × sqrt(D)

With 365 possible birthdays:

n ≈ 1.177 × sqrt(365)
  ≈ 22.5

Since people come in whole numbers, the threshold is 23.

This square-root rule is why the problem matters outside interview puzzles. Suppose a service generates random 32-bit identifiers. There are about 4.29 billion possible values, so it is easy to think collisions should not matter until billions of IDs have been generated. The birthday approximation says the 50% collision point is only about 77,163 generated IDs:

1.177 × sqrt(2^32) ≈ 77,163

At one million generated IDs, the expected number of matching pairs is about 116. Collisions are then essentially certain, even though any one pair has only a one-in-4.29-billion chance of matching.

The senior-level nuance: assumptions matter

The textbook answer assumes:

1. There are exactly 365 possible dates.
2. Every date is equally likely.
3. People’s birthdays are independent.
4. The event is an exact same-date match.

Real birthdays do not satisfy those assumptions perfectly. Birth rates vary by date, February 29 requires a convention, and family members are not fully independent. If the probability of a birthday on date d is p_d, then the chance that two independent people share a birthday is:

sum of p_d^2 over all dates d

That quantity is at least 1/365, with equality for a perfectly uniform distribution. Concentrating probability on popular dates therefore increases collisions compared with the textbook model.

For ordinary human-birthday estimation, the uniform model is still a good approximation. For a hash or identifier system, however, non-uniformity can be a production bug. If a supposedly random ID generator has biased outputs, or several workers accidentally reuse the same sequence, duplicates arrive earlier than the birthday estimate predicts.

A practitioner usually sees the failure as a database error such as duplicate key value violates unique constraint, at a volume far below the expected threshold. That symptom means the independence or uniformity assumption deserves investigation. Check the output distribution, worker namespaces, modulo operations, and random-number source. If duplicates are unacceptable, do not rely on a low probability alone: use a uniqueness constraint, coordination, or a larger identifier space.

The birthday approximation is also not a security guarantee. For cryptographic hashes, it describes the generic random-collision baseline. An adversary may exploit weaknesses in the hash or control the inputs, so the random model is only part of the analysis.

What they’ll ask next

“What is the chance that someone shares my birthday in a room of 23?”

About 5.9%, because there are only 22 people comparing against one fixed date:

1 - (364/365)^22 ≈ 0.059

That is not the birthday-problem probability.

“Why can’t you multiply the 253 pair probabilities?”

Because the pair events are not mutually independent. Several pairs can share people, and one group of three matching birthdays creates three matching pairs. The exact solution avoids this overlap by calculating the probability that all birthdays are distinct.

“How does this apply to hash collisions?”

Replace 365 with the number of possible hash outputs. For D possible values, the collision threshold is roughly 1.177 × sqrt(D) at 50% probability. A 32-bit identifier reaches that point at about 77,163 random values, not at 2 billion. The estimate changes if outputs are biased, inputs are adversarial, or the system deliberately prevents duplicates.

Say this in the interview

“With 23 people, the chance of at least one shared birthday is 50.7%, because there are 253 possible pairs; I calculate it as one minus the probability that all birthdays are distinct, and the same square-root collision bound appears in hash spaces.”