Mathematics.

combinatorial probability

The Birthday Problem

Probability25 minDifficulty4 out of 10

You should know: sample space, pigeonhole principle

Overview

The birthday problem asks: in a group of n randomly chosen people, what is the probability that at least two share the same birthday (assuming 365 equally likely birthdays and ignoring leap years)? Counterintuitively, only 23 people are needed for this probability to exceed 50%, far fewer than most people's intuition suggests. The trick is that the number of PAIRS of people grows quadratically with n (there are C(n,2) pairs), so the chance that at least one pair matches becomes surprisingly large even for modest group sizes. It is easiest to compute via the complement: the probability that ALL birthdays are different, then subtract from 1.

Intuition

The surprise comes from focusing on the wrong quantity. With 23 people, you might think 'only 23 out of 365 days are taken, so the chance of overlap must be low.' But the relevant count isn't people versus days — it's PAIRS of people, since any of them could match. With 23 people there are C(23,2) = 253 distinct pairs, and each pair has a small (1/365) chance of matching. With 253 'chances' for a coincidence, even though each is individually unlikely, the aggregate probability of at least one match climbs past 50%. This is the same phenomenon underlying the pigeonhole principle: with enough pairs to compare, coincidences become likely rather than rare.

Formal Definition

Definition

For n people and 365 possible equally likely birthdays, let p(n) be the probability at least two share a birthday. Using the complement (all different):

P(no shared birthday)=365365⋅364365⋯365−n+1365=365!(365−n)! 365nP(\text{no shared birthday}) = \frac{365}{365}\cdot\frac{364}{365}\cdots\frac{365-n+1}{365} = \frac{365!}{(365-n)!\,365^n}
Probability all n birthdays are distinct
p(n)=1−365!(365−n)! 365np(n) = 1 - \frac{365!}{(365-n)!\,365^n}
Probability of at least one shared birthday
p(23)≈0.507p(23) \approx 0.507
The famous threshold: 23 people gives just over 50%

Worked Examples

  1. Person 1 can have any birthday; person 2 must avoid person 1's day; person 3 must avoid both.

    P(all different)=365365⋅364365⋅363365P(\text{all different}) = \frac{365}{365}\cdot\frac{364}{365}\cdot\frac{363}{365}

  2. Compute the numeric value.

    P(all different)=1×0.99726×0.99452≈0.99180P(\text{all different}) = 1 \times 0.99726 \times 0.99452 \approx 0.99180

Answer: P(all different) ≈ 0.9918, so P(at least one match) ≈ 0.0082 (about 0.82%).

Practice Problems

Difficulty 3/10

In a group of 2 people, find the probability they share a birthday.

Difficulty 4/10

Find the number of distinct pairs of people in a group of 10.

Difficulty 5/10

In a room of 4 people, find the exact probability that at least two share a birthday (ignore leap years, 365 days).

Quiz

The minimum group size for the probability of a shared birthday to exceed 50% is:
The easiest way to compute the birthday problem's probability is to:
The birthday problem's surprising result is driven by the fact that:

Summary

  • The birthday problem asks the probability that, among n people, at least two share a birthday.
  • It's solved via the complement: P(match) = 1 − P(all different) = 1 − 365!/((365-n)!·365ⁿ).
  • Only 23 people are needed to exceed a 50% chance of a shared birthday, because the number of pairs C(n,2) grows quadratically.

References

  1. WebsiteWikipedia — Birthday problem