12-04-2012, 10:14 AM
The Birthday Problem
The Birthday Problem.pdf (Size: 34.7 KB / Downloads: 84)
Find the probability that in a group of n ( n 365) people, at least two people share the same birthday.
Here n = 23 (and n = 106), but let’s solve this first for general n. We assume that all 365 days of the
year (for simplicity, we ignore leap years) are equally likely birthdays and that there are no twins in the
room. Of course, in case of n > 365, the probability is equal to 1 .
Solution. If we ask every person in a group of n randomly chosen people to reveal their birthday, we
get an ordered n-tuple of birthdays. So the sample space
is the set of all n-tuples of birthdays and
|
| = 365n
Each outcome in
is equally likely to occur with probability 1
365n .
We are interested in the probability of the event
A = { there is at least one match among the n birthdays }.
Rather than computing |A| directly (there are a lot of cases to consider, since there could be multiple
matches), let’s look at the complementary event
Ac ={ there is no match at all among the n birthdays }.
The outcomes in Ac are ordered arrangements of n numbers chosen from 365 numbers without repetitions.
Therefore:
|Ac| = 365 · 364 · 363 · · · (365 − n + 1)
and the probability of no match is
P(Ac) =
365 · 364 · 363 · · · (365 − n + 1)
365n
Finally, the probability that there is at least one match is
P(A) = 1 −
365 · 364 · 363 · · · (365 − n + 1)
365n
It is surprising how large those probabilities P(A) turn out to be, even for relatively small groups of
people (small n).
• For n = 23, P(A) = 0.507. For a group of 23 randomly chosen people, there is a more than half
chance that two people share the same birthday!
• For n = 106 (our class size), P(A) = 0.9999999. A birthday match is almost certain! Should we
put this to the test?
• Also see the separate link showing a graph of the probabilities P(A) depending on n.
Now a different Birthday Question: What is the probability that in a group of n people (with
myself in it), at least one other person shares my birthday?
A is the event that at least one person shares my birthday and Ac, the complement, is the event that
everybody in the group ”misses” my birthday. Again, it is easier to compute P(Ac) first. I know my
own birthday and I ask everybody in the group about their birthday. The sample space
is the set of
all possible ordered (n − 1)-tuples of birthdays and
|
| = 365(n−1).
In Ac, all birthdays are allowed, except mine. So
|Ac| = 364(n−1).
We get
P(A) = 1 − P(Ac) = 1 − (
364
365
)(n−1).
• For n = 23, we get P(A) = 0.06 which a lot smaller than the probability for the case of arbitrary
matches.
• For n = 106 , P(A) = 0.25. Still a relatively small probability!