The Birthday Problem: Shared Birthdays in a Room
You are at a party and wondering about birthday coincidences.
Part 1: There are $N \leq 365$ people in the room. What is the probability that at least two of them share the same birthday? Assume birthdays are uniformly distributed across 365 days and independent.
Part 2: Now focus on yourself. Given $N$ people in the room (including you), what is the probability that at least one other person shares your birthday?
Hints
- Both parts are easier via the complement: compute the probability of no match and subtract from 1.
- For Part 1, count how many ways $N$ people can have all-distinct birthdays out of $365^N$ total assignments. For Part 2, each of the other $N-1$ people independently avoids your fixed birthday with probability $364/365$.
- Part 1 answer: $1 - \frac{365 \cdot 364 \cdots (365-N+1)}{365^N}$. Part 2 answer: $1 - \left(\frac{364}{365}\right)^{N-1}$.
Worked Solution
How to Think About It: Both parts are easiest via the complement -- compute the probability of no match and subtract from 1. The twist is that Part 1 and Part 2 are measuring very different things. Part 1 is asking about any collision among $N$ people, which is a much higher-probability event because there are $\binom{N}{2}$ pairs that could match. Part 2 fixes your birthday and asks only whether the remaining $N-1$ people avoid it. If you see $N = 23$, the answer to Part 1 is already above 50%, but the answer to Part 2 is only around 6%. Mixing these up is the most common mistake.
Quick Estimate: For Part 1 with $N = 23$: there are $\binom{23}{2} = 253$ pairs. Each pair matches with probability $1/365 \approx 0.0027$. Treating pairs as independent (rough), the expected number of matches is $253/365 \approx 0.69$. By Poisson approximation, $P(\text{at least one match}) \approx 1 - e^{-0.69} \approx 1 - 0.50 = 0.50$. So around $N = 23$ the crossover hits 50% -- that is the famous birthday paradox threshold.
For Part 2 with $N = 23$: the other 22 people each independently avoid your birthday with probability $364/365$. So $P(\text{no match}) = (364/365)^{22} \approx e^{-22/365} \approx e^{-0.060} \approx 0.942$. Thus $P(\text{at least one match}) \approx 1 - 0.942 = 0.058$, only about 6%.
Approach: Complement rule. Compute $P(\text{no collision})$ in closed form for each part.
Formal Solution:
Part 1:
We want $P(\text{at least two people share a birthday})$. Work via the complement: compute $P(\text{all } N \text{ birthdays are distinct})$.
Assign birthdays sequentially. Person 1 can have any of 365 days. Person 2 must avoid person 1: $364/365$ choices. Person $k$ must avoid the $k-1$ previous birthdays: $(365-k+1)/365$ choices. So:
$$P(\text{all distinct}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365-N+1}{365} = \frac{365!}{(365-N)! \cdot 365^N}$$
Therefore:
$$P(\text{at least one shared birthday}) = 1 - \frac{365!}{(365-N)! \cdot 365^N}$$
This can also be written using the falling factorial notation:
$$= 1 - \frac{365^{\underline{N}}}{365^N}$$
where $365^{\underline{N}} = 365 \cdot 364 \cdots (365-N+1)$ is the falling factorial.
Part 2:
Now your birthday is fixed. You want to know if any of the other $N-1$ people share it. Each of them independently has your birthday with probability $1/365$, so each avoids it with probability $364/365$.
$$P(\text{no one else has your birthday}) = \left(\frac{364}{365}\right)^{N-1}$$
$$P(\text{at least one person shares your birthday}) = 1 - \left(\frac{364}{365}\right)^{N-1}$$
Answer:
- Part 1: $\displaystyle 1 - \frac{365!}{(365-N)!\cdot 365^N}$
- Part 2: $\displaystyle 1 - \left(\frac{364}{365}\right)^{N-1}$
At $N = 23$: Part 1 $\approx 50.7\%$, Part 2 $\approx 6.1\%$. To get Part 2 above 50% you need $N \geq 254$.
Intuition
The birthday problem is the canonical example of how badly human intuition handles coincidences among pairs. Part 1 reaches 50% at $N \approx 23$ because there are $\binom{N}{2}$ pairs competing -- that grows like $N^2/2$. With 23 people you have 253 pairs, each with a 1-in-365 chance of matching, so you expect well over half a match on average. Part 2 is the question most people think they are answering when they hear 'birthday problem': the chance that someone in the room shares YOUR birthday. That grows much more slowly because you are only one anchor, and you need roughly $365 \ln 2 \approx 253$ other people for a 50-50 shot.
In quant work this intuition matters whenever you are reasoning about coincidences in large datasets. If you are scanning a universe of 500 stocks for 'suspiciously correlated' pairs, you have over 100,000 pairs -- even genuinely uncorrelated assets will produce some high-correlation pairs by chance. The birthday problem is the mental model that stops you from over-interpreting random coincidences as signals.