# Birthday Problem: How am I wrong? [duplicate]

Before reading the Wikipedia article, my idea to calculate the probability was as follows:

$1-\left(\frac{364}{365}\right)^{_nC_{2}}$

Basically, I thought to compare all combinations of pairs ($_nC_{2}$) and require them to have different birthday ($\frac{364}{365}$). It gave a very similar result to the wiki method, but is slightly different and I can't tell how my way of thinking is wrong.

Can anyone tell me what I'm missing?

## marked as duplicate by Juho Kokkala, mdewey, Community♦Jun 29 '17 at 15:12

I think the logic is wrong since the probability of two persons having different birthdays is dependent on the fact that they need to have different birthdays than all the others. A simple example birthday paradox for A,B and C not having birthday on the same weekday. Each of these pairs are 1/7 in a vacuum. But given A had birthday an a Monday and B and C did not have birthday the same day. The probability of B and C not having birthday on the same day given they not having birthday on the same day as A is 1/6.

The logic you should apply is the following. Let the person enter one by one and stop the experiment if two has the same birthday.

• Person 1 enters, so cant have the same birthday as anyone else
• Person 2 enters, so there is 1/365 chance that she has the same birthday as person 1. If so the experiments stops otherwise the number of days taking goes up to 2.
• Person 3 enters, so there is 2/365 chance that he will have the same birthday as either person 1 or 2.

Now the pattern is clear. The probability of k (k < 366) persons all having different birthdays are: $$P(k)=\prod^{k}_{i=1}\left[1-\frac{i-1}{365}\right]=\prod^{k}_{i=1}\frac{366-i}{365}=\frac{365!}{(365-k)!*365^k}$$

Notice that your answer is never equal to $1$ regardless of how high $n$ is. However, obviously if $n=366$ then there must be two people with the same birthday.

So basically, the correct answer captures the fact that for everyone to have a different birthday, you begin running out of dates the more people are in the room.

• Point of interest -- the term of art for this idea is "the Dirichlet box principle" or "the pigeonhole principle." en.wikipedia.org/wiki/Pigeonhole_principle – Sycorax Jun 29 '17 at 5:03
• @Sycorax I've never heard anybody call it (in English) anything other than the pigeonhole principle. – David Richerby Jun 29 '17 at 12:55

If you have three days $x$, $y$, $z$, the events $x\ne y$, $x\ne z$, and $y\ne z$ are not independent, but you treat them as such.