Birthday Problem¶

Description¶

Consider a group of $n$ people and assume that each person's birthday is independently and uniformly distributed over $365$ possible days. The birthday problem asks for the probability that at least two people in the group share a birthday.

Interpretation¶

The birthday problem shows that coincidences can happen much sooner than intuition suggests. It is usually easier to solve by first finding the chance that no match occurs.

Under the model of independent birthdays uniformly distributed over 365 days, the probability of a shared birthday among $n\le365$ people is $1-365\cdot364\cdots(365-n+1)/365^n$$1)/365^n$. With 23 people there are $\binom{23}{2}=253$ pairs that could match, and the probability exceeds one half.

Naive probability counts equally likely birthday assignments. The complement event has distinct birthdays, so count assignments without repetition and divide by all $365^n$ assignments before subtracting from one.

Key Results¶

• Computing the complement usually gives the simplest formula for at least one match.
• For $n$ draws from $m$ equally likely labels, the no-match probability is $\frac{m(m-1)\cdots(m-n+1)}{m^n}$.
• The same calculation applies to hash collisions, repeated IDs, and sampled labels.

Examples¶

• In a group of $23$ people, the probability of at least one shared birthday is already above one half under the usual simplified assumptions.
• If $1000$ IDs are sampled with replacement from a million possible IDs, the collision probability can be found from the no-repeat probability.
• A database using short random codes faces a birthday-type collision risk.

Prerequisites¶

• Naive Probability
• Complement of an Event

Related Concepts¶

• Independent Events
• Counting
• k-Permutation
• Sampling With and Without Replacement

Sources¶

• Probability Theory for EOR · Week 1

Aliases: birthday paradox Keywords: collision probability

Last updated: 20 October 2026 03:02