Birthday Problem

Problem Statement

You're in a room with n people. Assuming birthdays are uniformly distributed across 365 days (ignoring leap years), what is the probability that at least two people share the same birthday?

For a follow-up: how large does n need to be for this probability to exceed 50%?

Hint: Don't try to count the cases where a match occurs directly — there are too many. Instead, compute the probability that no two people share a birthday (all birthdays are distinct), then subtract from 1. This complementary approach is almost always easier for "at least one" problems.

Why It's Surprising

Most people anchor on 365 days and guess you'd need around 180 people for a 50% chance. The true answer — just 23 people — is one of the most-cited counterintuitive results in probability. The reason is that we're not asking whether anyone shares your birthday; we're asking whether any pair in the room shares a birthday. With 23 people, there are C(23,2) = 253 distinct pairs to check.

Solution

Solution

Step 1: Set up the complement. Let A be the event that at least two people share a birthday. It's easier to compute P(A^c) — the probability all n birthdays are distinct — then use P(A) = 1 - P(A^c).

Step 2: Count the favorable outcomes for A^c. The first person can have any of 365 birthdays. The second must avoid the first: 364 choices. The third must avoid both: 363 choices. Continuing, person k has 365 - (k-1) valid choices.

Step 3: Write the probability. Each person independently picks from 365 equally likely days: P(A^c) = (365/365) × (364/365) × (363/365) × ... × (365-n+1)/365 = 365! / ((365-n)! × 365^n)

Step 4: Final answer: P(at least one shared birthday) = 1 - 365! / ((365-n)! × 365^n)

Step 5: Find the crossover. Set P(A) > 0.5 and solve numerically. At n = 22, P ≈ 0.476. At n = 23, P ≈ 0.507. So 23 people suffices.

Probability Table

The probability climbs steeply. By 70 people, a shared birthday is essentially certain.

The Pairs Intuition

A cleaner way to see why 23 is so small: with n people there are C(n,2) = n(n-1)/2 distinct pairs. With n = 23, that's 253 pairs, each with a 1/365 ≈ 0.27% chance of matching. A rough Poisson approximation gives:

P(at least one match) ≈ 1 - e^(-C(n,2)/365)

At n = 23: 1 - e^(-253/365) ≈ 1 - e^(-0.693) ≈ 0.500. This approximation is remarkably accurate and gives the right intuition: you need enough pairs, not enough people.

Key Insight: The birthday problem is fundamentally about the number of pairs, not the number of people. With n people, you get C(n,2) pairs — which grows quadratically. This is why the threshold of 23 feels so low: you only need √(2 × 365 × ln 2) ≈ 23 people.

Variant: Non-Uniform Birthdays

What if birthdays aren't uniformly distributed — as they aren't in reality (late summer birthdays are slightly more common)?

Solution:

1. Non-uniformity actually increases the probability of a collision. Intuitively, if many people cluster around the same few days, matches become more likely.
2. Formally, P(A^c) = ∏(1 - p_i) is maximized when all p_i are equal. Any deviation from uniformity reduces P(A^c), increasing P(A).
3. The uniform assumption gives a lower bound on the true collision probability. The answer of 23 people for 50% is conservative — the real threshold is slightly lower.

Connection to Hashing and Cryptography

The birthday problem underlies the birthday attack in cryptography. If a hash function produces N possible outputs, an attacker only needs to compute roughly √N hashes before finding a collision with 50% probability. This is why SHA-256 (with 2^256 outputs) requires 2^128 operations to break — not 2^256.

Related Problems

This problem is commonly asked at Jane Street, Optiver, Citadel, SIG, and DRW interviews.