The birthday paradox
Tonight's idea
There are 365 days in a year, so you might guess you need about 183 people before a shared birthday becomes likely. The real number is 23.
Work out the opposite event, as in the complement trick: the chance that all \(n\) birthdays are different. Line the people up. The first person can have any birthday. The second must avoid one day: probability \(\tfrac{364}{365}\). The third must avoid two: \(\tfrac{363}{365}\). Each new person has one more day to avoid, and we multiply, because each of these must happen in turn.
\[P(\text{all different}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 - n + 1}{365}, \qquad P(\text{shared}) = 1 - P(\text{all different}).\]
Each factor is a little less than 1, and a long product of numbers a little less than 1 shrinks fast. By the 23rd factor the product has dropped below one half.
Why so few? Because matches come from pairs, and 23 people make \(\tfrac{23 \times 22}{2} = 253\) pairs. Each pair has a \(\tfrac{1}{365}\) chance to match, and 253 attempts at a 1-in-365 event is a fair fight. The 183 guess is nearer to a different question, how many people before one shares a birthday with you, and even that takes 253 (question 4).
Watch one: 23 people
Twenty-two factors (the first person's factor is 1):
\[\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdots \frac{343}{365} = 0.4927.\]
So \(P(\text{shared}) = 1 - 0.4927 = 0.507\), just over one half. With 22 people the product is 0.524 and the shared chance is 0.476, just under. On a calculator, multiply by \(\tfrac{364}{365}\), then \(\tfrac{363}{365}\), and so on, watching the display shrink.
Simulate 1000 rooms of up to 60 people and compare with the exact curve: mathdetours.com/demos/birthday.html.
Your turn
- Find \(P(\text{shared})\) for 3 people and for 4 people, to three decimal places.
- How many pairs are there in a room of 23 people? Of 50? Explain in one sentence why the number of pairs, not the number of people, is what matters.
- Birth months instead, with 12 equally likely months. Compute \(P(\text{shared month})\) for 4 people and for 5 people. How many people make a shared month more likely than not?
- The other question: the chance that at least one of \(n\) other people shares your birthday is \(1 - \left(\tfrac{364}{365}\right)^n\). Use a calculator to show that \(n = 253\) is the first \(n\) where this passes one half. Why is 253 so much bigger than 23?
Stretch: how many matches to expect
Each pair of people matches with probability \(\tfrac{1}{365}\). Using expected value, find the expected number of matching pairs in a class of 30, and in a school of 1000 students. Then explain why a class of 30 can have an expected 1.19 matches but only a 71% chance of any match.
Answers
- Three: \(1 - \tfrac{364 \cdot 363}{365^2} = 1 - 0.99180 = 0.008\). Four: \(1 - \tfrac{364 \cdot 363 \cdot 362}{365^3} = 1 - 0.98364 = 0.016\).
- \(\tfrac{23 \cdot 22}{2} = 253\) and \(\tfrac{50 \cdot 49}{2} = 1225\). A match is an event between two people, so every pair is a separate chance of a match, and the number of pairs grows roughly like the square of the number of people.
- Four people: \(1 - \tfrac{12 \cdot 11 \cdot 10 \cdot 9}{12^4} = 1 - 0.573 = 0.427\). Five: \(1 - \tfrac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{12^5} = 1 - 0.382 = 0.618\). Five people suffice.
- \(\left(\tfrac{364}{365}\right)^{252} = 0.5009\) and \(\left(\tfrac{364}{365}\right)^{253} = 0.4995\), so the chance passes one half at 253. Only the \(n\) pairs that include you can count, instead of all \(\tfrac{n(n-1)}{2}\) pairs. You need about 253 chances at a 1-in-365 event either way; 23 people supply 253 pairs, but 253 "pairs with you" need 253 people.
Stretch. Expected matches \(= \text{pairs} \times \tfrac{1}{365}\). Class of 30: \(\tfrac{30 \cdot 29}{2} = 435\) pairs, so \(435/365 \approx 1.19\). School of 1000: \(\tfrac{1000 \cdot 999}{2} = 499{,}500\) pairs, so about 1368 matching pairs. An expected value is an average: some classes have no match (29%), and the rest average more than one, with some having two or three. The average of 1.19 says nothing about the chance of zero.