The Birthday Problem, revisited…?

I'm currently facing a problem I have been stuck in for almost half a day and I really can't keep this because I have a lot of work to do! It obviously has to do with the birthday problem.

The original birthday problem solves the question of "what is the probability of having at least two persons with the same birthday in a room of $N$ persons", and I'm trying to get to this in a different way of that of the canonical solution, which is pretty easy to understand.

I started asking "what is the probability of exactly $k$ persons, out of $N$, having the same birthday as me". Having the same "birthday as me" is the same as asking "birthday on January 1st" or "birthday on December 31", which have $p=1/365$. To me, this looked like a binomial problem (i.e. tossing a coin with probability $p$ of being heads, where I ask for exactly $k$ heads out of $N$ tosses), so my answer to this question is, simply, \begin{equation} p(k|N)=\binom{N}{k}p^{k}(1-p)^{N-k}\text{.} \end{equation} I think here's where my argument starts to fall appart: I say that if I want to ask "what is the probability of exactly $k$ persons, out of $N$, having a birthday on January 1st" OR "having a birthday on January 2nd"...OR "having a birthday on December 31th", is \begin{equation} 365p(k|N)=365\binom{N}{k}p^{k}(1-p)^{N-k}\text{.} \end{equation} Finally, in order to answer the question "what is the probability of having at least two persons with the same birthday in a room of $N$ persons", I ask "what is the probability of having $k=2$ persons with the same birthday in the room" OR "$k=3$"...OR "$k=N", so the probability would be: \begin{equation} 365\sum_{k=2}^{k=N}p(k|N)\text{.} \end{equation} However, this is not the answer, as when I compare the results with the canonical answer it makes no sense. Can anyone help me with this? • Do you think the independence assumption is valid? – Dason Mar 22 '12 at 15:22 • You need to become familiar with PIE. – whuber Mar 22 '12 at 15:23 • Néstor, rather than updating your question as "solved", please consider accepting @Martin's answer (check the green mark below his response votes) if you feel that solved your problem. I'm giving you +1 so that you can even vote on his reply. – chl Mar 22 '12 at 16:10 1 Answer The events "$k$people have a birthday on Jan 1" and "$k\$ people have a birthday on Jan 2" are not mutually exclusive, and so the probability that either of them occurs is not equal to the sum of their individual probabilities. You would need to subtract the probability that both events occur, but this is likely to become extremely complex once you scale up to all 365 days.

• Can't believe I overlooked this fact! It was on my tougths at first, but I discarded it in order to try to come up with a quick answer. I'll be more careful from now on :-), thanks! – Néstor Mar 22 '12 at 15:36