Sorry for beating on the dead horse, but I would like to ask for one clarification on the Birthday Problem (as a reminder, we want to find the probability that in a roomful of $N$ people, at least two share the same birthday). I was thinking of a following, simple approach:
The probability of any two people having the same birthday is $1/k$, where $k$ is the number of days in a year, so it's $1/365$. There are ${N \choose 2}$ ways of pairing up two people, so one would expect the probability of two people to have the same birthday to be ${N \choose 2}/365$. For instance, choosing P = 0.5 and solving for N, we get N = 19.611, so we would need more than 19 people to have the probability higher than 0.5.
It looks like, however, that this approach is wrong (in fact, the well-accepted solution is 23, as illustrated in the Wikipedia Article). The article furthermore states:
the number of pairings in a group of 23 people is not statistically equivalent to 253 pairs chosen independently
It looks like my mistake is doing exactly this, choosing the pairs independently. Why is this the case, though? Why is the statement on statistical equivalence above actually true?
You simply added up the probabilities as if they were disjoint events. It is nothing to do with independence (even though they are indeed not independent!). Consider that if $a = b$ and $b = c$, then $a = c$.
However, there is an interesting interpretation of the number you calculated. If each person gets one point for every other person he shares a birthday with, then the expected (average) number of points for a single person is $(n-1)\frac{1}{k}$. If each pair of people gets one point if they share a birthday, then the expected number of points in total is $\binom{n}{2}\frac{1}{k}$. Note that this agrees with the observation that the events are not mutually exclusive, since it is possible to get more than one point in total.