Birthday problem independent events?

Question

The Wikipedia article about the birthday problem explain how to calculate the probability of birthday collision. They're simply telling in the process that the events are independent :

When events are independent of each other, the probability of all of the events occurring is equal to a product of the probabilities of each of the events occurring.

I don't understand how they're independent. If one person enter the room, the probability that his birthday is different than the previous person is 1 (100%). If the second person enter the room, the probability that his birthday is different than the previous person is 364/365 (99.73%). Therefore, aren't the events dependent?

I know that the event is independent if $P(A \cap B) = P(A) P(B)$. I know the probability of both events (1 and 364/365), but how do I calculate the probability of both elements happening? Saying that I just need to use that formula because they're independent wouldn't make sense since that's what I'm trying to figure.

Answer 1

The important issue with the birthday problem is that each person's BIRTHDAY is independent. Your point that the chance of collisions increases as the number of people in the room increases is exactly the point of the calculation.

An example of a case where birthdays are not independent would be, testing the chance of collision at a twin convention.

The way I think about the solution is to take the inverse of the case where everybody has different birthdays. When two people are in the room, the odds of no collision are $\frac{365}{365} * \frac{364}{365}$, so the odds of a collision are $1-\frac{365}{365} * \frac{364}{365}=\frac{1}{365}$. When a third person enters the room, the odds of no collision are $\frac{365}{365} * \frac{364}{365}* \frac{363}{365}$, so the odds of a collision are $1-\frac{365}{365}*\frac{364}{365}*\frac{363}{365}=\frac{1093}{133225}=1-\frac{\frac{365!}{(365-n)!}}{365^n}$

Answer 2

The issue arose from the Wikipedia post on the birthday problem quoted on the OP (prior iteration):

When events are independent of each other, the probability of all of the events occurring is equal to a product of the probabilities of each of the events occurring. Therefore, if $\small P(A')$ can be described as $\small 23$ independent events, $\small P(A')$ could be calculated as $\small P(1) \times P(2) \times P(3) > \times \dots \times P(23)$.

To focus the discussion, the notation is:

$A' = \text{no two people in the room have the same birthday}$ can be reformulated as:

$A'_i = \text{1-st through i-th subjects have different birthdays }$

The probability of $A_i$ is given by the following function, as can be easily deduced from the Wikipedia post on the birthday problem:

$\Pr(A'_i) =\displaystyle\prod_1^i \frac{365-i+1}{365}$

I believe that the problem is that there is no $\Pr(A'_i\,\vert\, \color{blue}{A_{i-1}})$, i.e. the event of having $i$ individuals with different birthdays given that guest number $i-1$ does in fact share her birthday with one of the prior guests, because the event $A'_i$ implies $A'_{i-1}$ (guest $i-1$ cannot share her birthday with any of the prior guests). Similary, $\Pr(A'_i\,\vert\, A'_{i-1})$ cannot make reference to two independent events: $A'_i$ implies $A'_{i-1}$ is always true - if we are talking about the same party (each party would be the equivalent of a different random experiment).

As an analogy, drawing iid draws from a hypergeometric distribution, say from an urn with $5$ red balls and $15$ balls, wouldn't make much sense in the implication that having drawn $3$ red balls doesn't change the probability of drawing a red ball on the next pick (it obviously does). Instead we would be referring to the number of red balls in, say $7$ draws. Each experiment would not consist of each individual ball drawn, but of the $7$ drawn balls as a unit.

Similarly if we are to talk about independence in the birthday problem it would be in the calculation of the probability of having, for example, $21$ guests in $\text{Party A}$ all with different birthdays $\Pr(A'_{21})$, and $15$ guests all having been born in different days in a different, $\text{Party B}$, or $\Pr(A'_{15})$. These would be two independent events.

---

Check the terminology in dealing with the problem in Mathematical Statistics and Data Analysis by John A. Rice:

... whereas $A^c$ [our $A'$] is much simpler. There are $365^n$ possible outcomes, and $A^c$ can happen in $365 \times 364 \times \dots \times (365 - n + 1)$ ways.

Answer 3

Probability that first person was born on some particular day of the year (say on January 1st) is $\frac{1}{365}$, probability that second person was born on some particular day is $\frac{1}{365}$, the same for any other person, no matter how many persons you have in your room. The probability that everyone in some room have birthday on the same day is $(\frac{1}{365})^n$, what proves independence. Entering some room does not have any connection whatsoever with your, or others birthday.

Obviously, if you ask if $A \ne B$, then the answer will depend on what $A$ is and on what $B$ is. It will be a function of $A$ and $B$ and so the result will be dependent on both of variables. So it is a matter of how do you define an event in this scenario.

Example

Let me illustrate it using simple example. For the sake of argument, let's for a moment ignore the fact that biased coin is impossibility and imagine that you have two coins $A$ with probability of heads $P(A=1) = 0.4$ and $B$ with probability of heads $P(B=1) = 0.7$, that are thrown independently. This translates to the following table of joint probabilities (you can easily re-create it by using your favorite statistical software to simulate such coins and then create pivot table of simulation results):

$$ \begin{array}{c|cc|c} & B=0 & B=1 \\ \hline A=0 & 0.12 & 0.28 & 0.40 \\ A=1 & 0.18 & 0.42 & 0.60 \\ \hline & 0.30 & 0.70 & \end{array} $$

You can easily see that $A$ and $B$ are independent

$$ P(A=0, B=0) = P(A=0)\, P(B=0) = 0.4 \times 0.3 = 0.12 $$

etc. for all combination of such events. Since in Birthday paradox problem you are comparing birth dates of different people, to go further we need to introduce another random variable that is a function of $A$ and $B$:

$$ X_{AB} = \begin{cases} 0 & \text{if } & A=B, \\ 1 & \text{if } & A \ne B \end{cases} $$

what translates to the following probabilities

$$ \begin{aligned} P(X_{AB} = 0) &= P(A=0, B=0) + P(A=1, B=1) \\ &= 0.12 + 0.42 = 0.54 \end{aligned} $$

$$ \begin{aligned} P(X_{AB} = 1) &= P(A=0, B=1) + P(A=1, B=0)\\ &= 0.28 + 0.18 = 0.46 \end{aligned} $$

You can easily check, that $X_{AB}$ is not independent neither of $A$, nor of $B$, e.g.

$$ P(X_{AB} = 1, A = 1) \ne P(X_{AB} = 1) \, P(A = 1)$$

as

$$ 0.18 \ne 0.46 \times 0.60 = 0.28 $$

So if you consider individual tosses of the coins (e.g. $A=1$, or $B=0$) as events, then they are independent. On another hand, if you are interested in random variable $X_{AB}$, and call it's instances as events (e.g. $X_{AB} = 0$ since $A=B$), then it is not independent neither of $A$, nor of $B$. The same with Birthday paradox example, dates of birth of different people are independent, but comparing the dates is obviously dependent on the dates compared.

So the problem does not really lie in probability theory, or numbers, but in using statistical terminology precisely. If you consider as an events that John was born on May 6th, or that Emily was born on September 17th, then the both events are independent^*. On another hand, if you consider as an event in your experiment the fact that John was born on different day of the year then Emily, then this obviously it depends on their days of birth. It is totally up to you and your aims what you consider as an event, but you have to remember to do it precisely. The problem was that you have been comparing different kinds of events and nobody said that they were to be independent. Check also What is meant by a "random variable"? to read more about random variables and "events".

_{* - Well, being precise, they could be dependent in some cases, e.g. they are twins, or simply siblings etc., but imagine we are talking about some "random" people, not related to each other}