0
$\begingroup$

As most of you probably know, the birthday problem is about finding the probability that any two people share the same birthday, in a room with N people. Since 23 people in the room is the number more frequently used, let's use it here as well.

On Wikipedia and on most probability books the approach to solve this is to first calculate P', the probability that no two people will share the same birthday, and then do 1 - P'. So you basically do (364/365)(364/365)...(343/365). This multiplication will give you 0.4927, 1-P' is 0.5073. So far so good.

What I want to know is how you do the calculation the other way around. That is, how you calculate P straight away, and not by finding 1-P'.

The first idea that came to me is this one:

  1. Put the first person in the room. The probability of this person sharing a birthday is 0.
  2. Put the second person in the room. The probability of this person sharing the birthday with the first would be 1/365.
  3. Put the third person in the room. The probability of this person sharing the birthday with anyone would be 2/365.

So on and so forth, until the 23rd person, whose probability of sharing a birthday would be 22/365.

However this reasoning is flawed, as if you sum those probabilities the result would be 244/365, which is 0.6684 and not 0.5073.

What's wrong with the above reasoning, and what's the correct approach?

Update: As Thomas Andrews points out below, the problem is probably related to some cases being counted twice (i.e., 1 and 2 share and birthday and 3 and 4 share too). In this case we need to shave the individual probabilities a bit, which makes sense since the result should be lower that what we have right now. How to do it though?

Update 2: I think I found the answer. See below.

$\endgroup$
  • 1
    $\begingroup$ What are you doing with those indidual probabilities? You can't add them, or you'll get a total greater than one when you have 183 people. You can't multiply them, because you'll get $0$. The problem is that you are counting some cases twice - if person $1$ and $2$ share a birthday, and $3$ and $4$ share a birthday, you've counted that case twice. $\endgroup$ – Thomas Andrews Oct 9 '13 at 17:46
  • $\begingroup$ @Thomas, I agree with counting some cases twice. But you said I can't add the probabilities, but I don't agree. I might not be calculated each individual probability correctly, but once I do it to get the right answer I'll certainly need to add them, right? $\endgroup$ – Daniel Scocco Oct 9 '13 at 17:50
  • 1
    $\begingroup$ It's step 3. It's simply not linear like that. P(person 3 shares bday with neither person 1 nor person 2) $\neq$ P(person 3 doesn't share bday with person 1) + P(person 3 doesn't share bday with person 2). $\endgroup$ – Brendan W. Sullivan Oct 9 '13 at 17:51
  • $\begingroup$ So is the probability zero? No. Is the probability ever greater than $1$? It will be if you add with $184$ people in the room. So, no, it doesn't have to be one or the other. The point is, your quest to find a "direct" way of solving this is doomed. $\endgroup$ – Thomas Andrews Oct 9 '13 at 17:52
  • $\begingroup$ @Thomas Andrews, see my comment above. Once the individual probabilities get calculated correctly it should never go above 1. It's going above one cause the value of each probability is wrong. Once you get this right the correct way to do this is to add the individual probabilities, since it's an OR situation (or the second person share a birthday, or the third, or the fourth, etc ) $\endgroup$ – Daniel Scocco Oct 9 '13 at 17:54
2
$\begingroup$

Well, you can certainly compute $p(n+1)/p(n)$. But it's not a trivial expression. Let $q(n)=1-p(n)$. Then we know that $$q(n+1)=q(n)\left(1-\frac{n}{365}\right)$$ So $$\begin{align}p(n+1) = 1-q(n+1) &= 1-q(n)\left(1-\frac{n}{365}\right)\\& = 1-(1-p(n))\left(1-\frac{n}{365}\right)\\=p(n) +\frac{(1-p(n))n}{365}\end{align}$$

So $\dfrac{p(n+1)}{p(n)}$ is going to be a messy expression of $p(n)$.

Similarly $p(n+1)-p(n)=\frac{(1-p(n))n}{365}$.

Essentially, this means that we get a matching birthday in $n+1$ people if we get a matching birthday in the first $n$, or if we don't in the first $n$ and the $n+1$st matches one of the $n$ previous ones.

For the example of $n=3$:

$$\begin{align}p(1)&=0\\p(2)&=p(1)+\frac{1(1-p(1))}{365} = \frac{1}{365}\\p(3)&=p(2)+\frac{2(1-p(2))}{365}=\frac{1}{365} + \frac{2\cdot 364}{365^2}\approx 0.0082042\end{align}$$

$\endgroup$
  • $\begingroup$ Party time - that's my 1000th answer. :) $\endgroup$ – Thomas Andrews Oct 9 '13 at 18:13
  • $\begingroup$ Thanks for that, but it's still not that clear for me. Are you saying it's too complex to calculate the probability the way I want? If not, how do you use your formula to get to the 0.5073 number? $\endgroup$ – Daniel Scocco Oct 9 '13 at 18:15
  • $\begingroup$ You are correct. I formulated another way of explaining it below, but it was based on your idea. I'll select yours as the right answer. Could you take a look at my answer below and confirm it's the same thing (i.e., correct too)? $\endgroup$ – Daniel Scocco Oct 9 '13 at 18:44
0
$\begingroup$

I think I found it (partially based on Thomas answer above). Here's the correct reasoning:

  1. Put the first person in the room. His probability of sharing a birthday with anyone is 0.
  2. Put the second person in the room. His probability of sharing a birthday with anyone is 1/365.
  3. Put the third person in the room. His probability of sharing a birthday with anyone, given that the previous people didn't, is (1 - 1/365) * (2/265). Therefore (364/365)(2/365)
  4. Put the fourth person in the room. His probability of sharing a birthday with anyone, given that none of the previous people did, is (1-P(3)) * (3/365).

So on and so forth.

So basically for the Nth person, the probability of him sharing a birthday with anyone in the room already, given that no one before did, P(N), is:

P(N) = (1 - P(N-1)) * ((N-1)/365) 

And P(1) = 0.

If you want to calculate the probability with 23 people in the room, therefore, you just need to add all the individual P(N).

$\endgroup$
  • $\begingroup$ Line (3) is wrong, that calculates the probability that the third person in the room is the first person who matches some previous person. If person 1 and person 2 match, then the probability that the third person matches someone previous is only $\frac{1}{365}$. $\endgroup$ – Thomas Andrews Oct 9 '13 at 18:54
  • $\begingroup$ I think the wording is not precise then, but the numbers must be, cause they are equal to yours after all. For instance, If you stop on my step 3 you'll have 1/365 + (364*2)/(365*365) = 0.0082042 too. Ain't that the case? $\endgroup$ – Daniel Scocco Oct 9 '13 at 19:04
  • $\begingroup$ Yeah, I was not talking about the numbers, I was talking about the words. $\endgroup$ – Thomas Andrews Oct 9 '13 at 19:07
  • $\begingroup$ For example, the entire sentence starting, "So, basically,..." is wrong. $\endgroup$ – Thomas Andrews Oct 9 '13 at 19:08
  • 1
    $\begingroup$ Gotcha. I think I fixed the wording now. Thanks for the help! $\endgroup$ – Daniel Scocco Oct 9 '13 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.