0
$\begingroup$

I was trying to work through the Birthday problem with the assumptions that

($1$) February $29$th is excluded as a possible birthday, and
($2$) All days are equally likely for birthdays to occur,

when I noticed something:

If there are $366$ people in the room, the number of $2$-people combinations that can be formed out of those people is $366 \choose 2$. Then, the probability of not getting a birthday match in any of those combinations is given by $(\frac{364}{365})^{366 \choose 2}$

This is a very small positive number close to $0$. But we know by the pigeonhole principle, that any group of 366 people is bound to give a birthday match (with the above assumptions in place), which means that the above probability has to be strictly equal to $0$. Where am I going wrong with my reasoning?

$\endgroup$
  • 2
    $\begingroup$ In your first argument you are assuming that all the $366 \choose 2$ events are independent, but I think they are not (because as you mentioned there should be some two people with same birthday), which makes a different result. $\endgroup$ – shrimpabcdefg Sep 8 '17 at 6:06
  • 3
    $\begingroup$ Try it with a smaller example. There are three people in a room all of whom are either male or female. There are 3 pairs. The probability of each pair not being a match is .5. So the probability of not getting any matches is $.5^3$ or one in eight. Do you see the error? Here's one way to get no match: A is male and B is female; that is possible. B is female and C is male; that is possible. And C is male and A is female. Each of those three is possible so surely it's possible for all three to be possible. So why does the pigeon hole see all three are impossible? $\endgroup$ – fleablood Sep 8 '17 at 6:39
  • 1
    $\begingroup$ If A and B have different birthdays and A and C have different birthdays, then you can't use A's birthday as an option when you are comparing B and C - that is why your events aren't independent. $\endgroup$ – Mark Bennet Sep 8 '17 at 7:07
  • $\begingroup$ Oh, I get it now! Thanks, fleablood and Mark Bennet! $\endgroup$ – Train Heartnet Sep 8 '17 at 7:21
  • $\begingroup$ I'm trying to see why increasing the number of people drastically increases the probability of a match. This obviously has to do with the number of $2$-people combinations increasing, but is there a better way of looking at it, than what I tried to do above? I mean, how do I see mathematically that more the combinations there are, more is the chance of a birthday match? $\endgroup$ – Train Heartnet Sep 8 '17 at 7:24
0
$\begingroup$

Comment:

This is much-traveled territory; searching this site will get you many hits and googling the Internet will get you at least hundreds of them.

Under your assumptions (1) and (2), and with $n$ randomly chosen people $(1 \le n \le 365)$ we have $$P(\text{No Match}) = \frac{{}_{365}P_n}{365^n} =\prod_{i=1}^n \left(1-\frac{i-1}{365}\right).$$

Going through a loop in R statistical software (to avoid using a calculator) with $n = 1, 2, \dots 60$ allows you to make a graph of $P(\text{No Match})$ against $n.$

n = 1:60;  p = numeric(60)
for (i in n) { p[i] = prod(1 - (0:(i-1))/365)  }
plot(n, p)
abline(h=0:1, col="green2")

enter image description here

You speculation on no match with 366 people in the room makes no sense; of course, then there must be a match. Even with only 60 people in the room it is essentially impossible to avoid a match.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.