随机算法 (Fall 2011)/Birthday Problem
There are students in the class. Assume that for each student, his/her birthday is uniformly and independently distributed over the 365 days in a years. We wonder what the probability that no two students share a birthday.
Due to the pigeonhole principle, it is obvious that for , there must be two students with the same birthday. Surprisingly, for any this event occurs with more than 99% probability. This is called the birthday paradox. Despite the name, the birthday paradox is not a real paradox.
We can model this problem as a balls-into-bins problem. different balls (students) are uniformly and independently thrown into 365 bins (days). More generally, let be the number of bins. We ask for the probability of the following event
- : there is no bin with more than one balls (i.e. no two students share birthday).
We first analyze this by counting. There are totally ways of assigning balls to bins. The number of assignments that no two balls share a bin is .
Thus the probability is given by:
Recall that . Then
There is also a more "probabilistic" argument for the above equation. To be rigorous, we need the following theorem, which holds generally and is very useful for computing the AND of many events.
By the definition of conditional probability, . Thus, . This hints us that we can compute the probability of the AND of events by conditional probabilities. Formally, we have the following theorem:
- Let be any events. Then
Proof: It holds that . Thus, let and , then
Recursively applying this equation to until there is only left, the theorem is proved.
- Let be any events. Then
Now we are back to the probabilistic analysis of the birthday problem, with a general setting of students and possible birthdays (imagine that we live in a planet where a year has days).
The first student has a birthday (of course!). The probability that the second student has a different birthday is . Given that the first two students have different birthdays, the probability that the third student has a different birthday from the first two is . Continuing this on, assuming that the first students all have different birthdays, the probability that the th student has a different birthday than the first , is given by . So the probability that all students have different birthdays is the product of all these conditional probabilities:
which is the same as what we got by the counting argument.
There are several ways of analyzing this formular. Here is a convenient one: Due to Taylor's expansion, . Then
The quality of this approximation is shown in the Figure.
Therefore, for , the probability that .