4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Can you quote the part of the article you refer to (where they're talking about independence) so people can see what is being claimed while reading your question? $\endgroup$ – Glen_b Sep 21 '16 at 4:41
  • 2
    $\begingroup$ They might mean the birth days are independent? For example, if the room was a twins convention, or a Virgo breakout group at an astrology convention, then this would not be true. $\endgroup$ – GeoMatt22 Sep 21 '16 at 12:38
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you more clearly indicate which of the three (or more) original questions you are addressing and what your answer(s) are? $\endgroup$ – whuber Sep 21 '16 at 14:21
  • $\begingroup$ @whuber Kindly, I don't quite get what you are getting at with you comment. Please let me know if there is something conceptually incorrect or misleading, and I'll follow through either correcting or deleting my answer. $\endgroup$ – Antoni Parellada Sep 21 '16 at 17:03
  • $\begingroup$ Although the OP has asked "I'm not quite sure how they're independent," "aren't the events dependent?", and how do I calculate the probability of both elements happening?", it's not clear to me where in your post you address any of these or what specifically your answers are. $\endgroup$ – whuber Sep 21 '16 at 17:19
  • $\begingroup$ @whuber Thank you. Either I am falling short on my stats lexicon, or I am making a conceptual mistake - You know I'm not being fastidious. I was comparing the event $A'_{21}=\text{none of 21 guests share bth-day}$ to an urn experiment (hypergeometric): rhyper(nn = 100, m = 5, n = 10, k = 7) will yield 100 random independent draws corresponding to 100 experiments; yet, within each urn ball picking "experiment" having drawn a red ball on the second pick, say, changes the probability of the third. $\endgroup$ – Antoni Parellada Sep 21 '16 at 17:32
  • $\begingroup$ I haven't been able to follow your discussion, because you do not motivate the introduction of the hypergeometric distribution yet you immediately write that it "wouldn't make much sense." Therefore, in order to figure out what you might be trying to say, I looked for a definite statement of an answer to some part of the question, but was unable to find anything like that. $\endgroup$ – whuber Sep 21 '16 at 17:37
2
$\begingroup$

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}$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What's the rule saying that the probability of them having all the same birthday is (1/365)^n if you say that it proves independence. $\endgroup$ – Simon Sep 21 '16 at 17:51
  • $\begingroup$ @Simon By the definition of independence: $P(X_1, \dots, X_n) = P(X_1) \times \dots \times P(X_n)$ $\endgroup$ – Tim Sep 21 '16 at 18:28
  • $\begingroup$ again, this doesn't make sense. You're saying: independent events are proven by this rule. But where do you get this rule? Well it's simple, it's because they're independent. But why are they independent, because they correspond to the rule... $\endgroup$ – Simon Sep 22 '16 at 3:04
  • $\begingroup$ Please refer to the last sentences of my question. $\endgroup$ – Simon Sep 22 '16 at 4:06
  • $\begingroup$ @Simon I thought my answer was clear enough but it seems it wasn't. I'll edit it later today for more details and example. $\endgroup$ – Tim Sep 22 '16 at 4:57

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.