Sender: Gordon
Subject: the birthday problem
Who is asking: Teacher
Level: Secondary
Question:
How do I explain the rapid rise in the probability that at least two people in a group of n have the same birthday. We have derived the formula for p(n) and have graphed it and have seen how the results are counter-intuitive. At around n=23 p(n)=.5 and at n=50 p(n) is very close to 1. It does not help to simplify the problem (eg use months instead of days) because then our intuition does correspond more closely to reality. Is there some way we can see how the probabiltiy of a "collision" increases with n? It makes me think of data storage problems and hash tables in computer science. thanks if you can help
Hi Gordon
This is a difficult problem. I am not sure that there is a way to explain the birthday problem that is intuitive. The only way that I see it is from the form of the expression
The key here is that in the fractional part both the numerator and denominator increase with increasing n, but the denominator increases at a much faster rate than the numerator.
Your comment that simplifying the problem by using months (I think of this as a 12 day year) where n = 5 gives p(n) approxiamtely 0.5, made me wonder what happens for "years" of different lengths. If a year is y days long then the appropriate probability, now a function of y and n is
The birthday problem is then, for each y, find the smallest n that gives p(y,n) > 0.5. If this number is called f(y) then the traditional birthday problem has answer f(365) = 23 and your "12 day year" problem gives f(12) = 5. In fact f(y) = 5 if y is anywhere from 10 to 16 days. I did some calculations and produced the following table
| f(y) | Range of y |
|---|---|
| 5 | 10 to 16 |
| 6 | 17 to 23 |
| 7 | 24 to 32 |
| 8 | 33 to 42 |
| 9 | 43 to 54 |
| 10 | 55 to 68 |
| 11 | 69 to 82 |
| 12 | 83 to 99 |
| 13 | 100 to 116 |
| 14 | 117 to 135 |
| 15 | 136 to 156 |
| 16 | 157 to 178 |
| 17 | 179 to 201 |
| 18 | 202 to 226 |
| 19 | 227 to 252 |
| 20 | 253 to 280 |
| 21 | 281 to 309 |
| 22 | 310 to 340 |
| 23 | 341 to 372 |
This is not an answer to your question but experimenting with the numbers does help me understand why n = 23 is the correct answer to the birthday problem even though it is still counter-intuitive.
Cheers
Harley
To return to the previous page use your browser's back button.