# Question regarding the birthday problem

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?

• 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. – shrimpabcdefg Sep 8 '17 at 6:06
• 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? – fleablood Sep 8 '17 at 6:39
• 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. – Mark Bennet Sep 8 '17 at 7:07
• Oh, I get it now! Thanks, fleablood and Mark Bennet! – Train Heartnet Sep 8 '17 at 7:21
• 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? – Train Heartnet Sep 8 '17 at 7:24

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")


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.