Birthday Problem
Suppose you have a room full of people, and each person's birthday is equally likely to fall on any of the 365 days of the year (ignore leap years). Birthdays are independent across people.
What is the minimum number of people needed so that the probability of at least one shared birthday is at least 50%?
Hints
- Instead of computing the probability of a match directly, think about the complementary event -- what is the probability that all birthdays are distinct?
- With $n$ people there are $\binom{n}{2}$ pairs. Each pair collides independently with probability $1/365$. Use this to get a rough estimate before doing any formal work.
- Write $P(\text{all distinct}) = \prod_{i=0}^{n-1} (365 - i)/365$ and use the approximation $1 - x \approx e^{-x}$ to turn the product into a single exponential.
Worked Solution
How to Think About It: This is one of the most famous problems in probability, and it comes up constantly in interviews because it tests whether you have good intuition about collisions. Most people guess way too high -- maybe 100 or 180 -- because they confuse "someone shares MY birthday" with "ANY two people share A birthday." The key insight is that the number of pairs grows quadratically: with $n$ people there are $\binom{n}{2} = n(n-1)/2$ pairs, and each pair has a $1/365$ chance of colliding. Once the expected number of collisions gets close to 1, the probability of at least one collision is already substantial.
Quick Estimate: Think of it this way: with $n$ people, there are roughly $n^2/2$ pairs. Each pair collides with probability $1/365$. The expected number of collisions is about $n^2 / 730$. By a Poisson-style heuristic, the probability of at least one collision is roughly $1 - e^{-n^2/730}$. Set that equal to $0.5$:
$$n^2 \approx 730 \ln 2 \approx 506$$ $$n \approx \sqrt{506} \approx 22.5$$
So we expect the answer to be around 23. That is a shockingly small number relative to 365.
Approach: Compute the probability that all $n$ birthdays are distinct, then find where it drops below $0.5$.
Formal Solution:
Let $P(n)$ be the probability that all $n$ people have distinct birthdays. The first person can have any birthday, the second must avoid 1 day, the third must avoid 2 days, and so on:
$$P(n) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 - n + 1}{365} = \prod_{i=0}^{n-1} \frac{365 - i}{365}$$
We want the smallest $n$ such that $1 - P(n) \geq 0.5$, equivalently $P(n) \leq 0.5$.
To solve analytically, use the standard approximation $1 - x \approx e^{-x}$ for small $x$:
$$P(n) \approx \prod_{i=0}^{n-1} e^{-i/365} = e^{-\sum_{i=0}^{n-1} i/365} = e^{-n(n-1)/(2 \cdot 365)}$$
Setting $e^{-n(n-1)/730} = 0.5$ and solving:
$$n(n-1) = 730 \ln 2 \approx 505.97$$
Solving the quadratic gives $n \approx 23$.
Exact computation confirms this: $P(22) \approx 0.524$ and $P(23) \approx 0.493$, so $1 - P(23) \approx 0.507 > 0.5$.
Answer: You need $n = 23$ people for at least a 50% chance of a shared birthday.
Intuition
The birthday problem is really a problem about collisions, and it teaches you that collisions happen much sooner than most people expect. The reason is combinatorial: the number of pairs grows like $n^2$, so you only need $n$ on the order of $\sqrt{N}$ (where $N$ is the number of possible values) to get a collision with decent probability. For 365 days, $\sqrt{365} \approx 19$, and the exact crossover is 23.
This square-root scaling shows up everywhere in quantitative work. In hashing and computer science, it is the basis of the "birthday attack" -- if a hash function has $N$ possible outputs, you only need about $\sqrt{N}$ random inputs to find a collision. In finance, the same logic applies when you are looking for coincidences in data: if you track 50 stocks, there are 1,225 pairs, so spurious correlations are almost guaranteed. Anytime you hear "what are the odds that two of these match," your first instinct should be to count the pairs, not the individuals.