Problem with the Birthday Problem

I recently learned of the Birthday Problem in probability theory, which essentially states that it only takes 23 people in a room to have a 50% chance that 2 of those people have the same birthday. When I try to calculate this myself, I keep coming up with a very different answer, and I am trying to figure out where I am going wrong. Given the problem "how many people does it take to make it 50% likely that 2 will have the same birthday?", here is how I went about solving it:

First, set this up instead as the problem:

"Given $n$ people (where $n$ is selected arbitrarily), what is the probability that 2 people will have the birthday $q$ (where $q$ can be some number between $1$ and $365$ representing a day of the year)"

Well, the probability of having at least 1 person with the birthday of $q$ is $\frac{n}{365}$. To get the probability of 2 people, you would multiply the probability of having one person by $\frac{n-1}{365}$ (based on the Multiplication Rule of Probability, and the fact that we don't want to count the same person twice).

So we can say, given $n$ people, the probability that 2 of them will both have the birthday $q$ (and therefore the same birthday) is $\frac{n(n-1)}{365^2} = \frac{n^2-n}{365^2}$.

Then I just say, given a probability of $\frac12$, solve for $n$.

$$\frac{n^2-n}{365^2} = \frac12$$ $$n^2-n = \frac{365^2}{2}$$ $$n^2 - n - \frac{365^2}{2} = 0$$ $$n\approx259$$

So, based on this method, it should take $259$ people to have a greater than 50% probability that 2 of them will have the same birthday, not $23$.

Where did I go wrong with solving it this way?

• your approach if fundamentally wrong. – Seyhmus Güngören May 5 '15 at 22:45
• @SeyhmusGüngören - care to elaborate? – Ephraim May 5 '15 at 22:46
• Your derivation gives you the number of people you'd need to put in a room to find $2$ of them with the same given birthday. The point is, you're only considering this very specific date. But what about the $259-2=257$ other people in the room (who do not have this specific birthday date). Maybe $2$ of them share the same birthday, albeit not the specific date you're looking for. – Demosthene May 5 '15 at 22:47
• @Demosthene - except $q$ was selected arbitrarily, so if no two people have $q$ as their birthday, then no one in the room shares the same birthday – Ephraim May 5 '15 at 22:50
• Those aren't independent, though. If no one has January $1$ as their birthday, doesn't the probability that at least two people share one of the remaining $364$ days as their birthday go up a little bit as a result? – Brian Tung May 5 '15 at 23:33

Well, the probability of having at least $1$ person with the birthday of $q$ is $n/365$.

Unfortunately, this isn't quite true. If you could guarantee that the $n$ people didn't share a birthday, then it would be true, but if you could guarantee that, there wouldn't be much of a birthday question! The actual probability that at least one person out of $n$ has $q$ as his or her birthday is

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

where we assume (as is typical for initial analyses of this problem) that birthdays are uniformly distributed over a $365$-day year. If $n$ is small, this is approximately equal to $n/365$ (and it is exactly true for $n = 1$), but this is increasingly untrue as $n$ becomes larger.

Note that if $n > 365$ then $n/365 > 1$, but we know it is perfectly possible for each of (let's say) $400$ people to happen not to have May $21$ for their birthday. The above expression gives that probability (usual assumptions applying).

To get the probability of $2$ people, you would multiply the probability of having one person by $(n−1)/365$.

This also isn't true. In order to determine the probability that at least two people have $q$ as their birthday, it's simplest to subtract from the above probability the chance that exactly one person has $q$ as their birthday. This yields

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

As before, what you say is approximately true for small $n$ (and exactly true for $n = 2$), but still is increasingly untrue for larger $n$, for nearly the same reason.

And if you wanted the probability of at least $k$ of the $n$ people sharing $q$ as their birthday, we could continue subtracting all the way up to $k-1$ people sharing $q$ as their birthday:

$$1-\sum_{i=0}^{k-1} \binom{n}{i} \left(\frac{1}{365}\right)^i \left(\frac{364}{365}\right)^{n-i}$$

So we can say, given $n$ people, the probability that $2$ of them will both have the birthday $q$ (and therefore the same birthday) is $(n^2-n)/365^2$.

Even if the above were true, the analysis would have to be expanded to cover all possible $q$, rather than only a single $q$. If you evaluate my second expression above at $n = 2$, the result is $1/365^2$, the probability that two people share $q$ as their birthday. If you multiply that by $365$, the number of possible choices for $q$, you get $1/365$, which is the probability that two people share any day as their birthday. However, that expression cannot be extended to expand beyond $n = 2$ exactly, because it neglects the possibility that more than two people share the same birthday.

The standard analysis of the birthday problem is the most straightforward, in which the probability of at least two of $n$ people sharing a birthday is

$$1-\left(\frac{365}{365}\right) \left(\frac{364}{365}\right) \left(\frac{363}{365}\right) \cdots \left(\frac{366-n}{365}\right)$$

• If we assume any given day is equally likely have someone born on it, then the probability of someone being born on day $q$ is $\frac{1}{365}$. Now, $n$ people, each of which has a $\frac{1}{365}$ chance of being born on day $q$, show up to the party. Since each one being born on $q$ is independent, the chance of $n\vee(n-1)\vee...\vee(n-(n-1))$ being born on $q$ should be $$\frac{1}{365}*n = \frac{n}{365}$$ so even without garunteeing that $n$ people didn't share a birthday, shouldn't the probability of one at the party having birthday $q$ still be $\frac{n}{365}$? – Ephraim May 5 '15 at 23:26
• To make this more concrete, let us say $q$ = January $1$. The probability of $1$ person being born on that day is indeed $1/365$. However, the probability that one of $500$ people is born on that day is not $500/365$ (since that is greater than $1$, it cannot be a probability). It is better calculated as $1$ minus the probability that no on is born on that date. The probability of each individual not being born on that date is $364/365$; thus the probability of all of them not being born on that date is $(364/365)^{500}$. (Independent probabilities are multiplied, not added as you did.) – Brian Tung May 5 '15 at 23:31

What your computation (neaarly) shows is that, if you have fewer than 259 people in the room, then, whatever day $q$ you choose, the probability that two of them share the birthday $q$ is less than $1/2$. So there's only a small (less than $1/2$) chance that two of them have January 1 as their birthday. There's also a small chance that two of them have January 2 as their birthday. Similarly for each of the 365 choices for $q$. But those 365 small chances can combine to a very big chance that two people have January 1 birthdays or two people have January 2 birthdays or $\dots$. So there can be a big chance that two people share a birthday even though the chance of it being January 1 is small, the chance of it being January 2 is small, etc.

The probablity that AT LEAST 2 will have their birthday on the same day is > 50%. You calculated the probability that EXACTLY 2 will have their birthday on the same day.

• +1 I also have read carefully the question and error was in the finish) – bruziuz May 21 '15 at 23:29
• Normally, once I realized I got it wrong, I would delete the offending comment. But since you got a +1, I will leave this embarrassing thing here. I gave you a +1 too. – steven gregory May 22 '15 at 0:23