Follow-on from this post

I was trying Birthday Paradox for 5-day calendar, with 3 people

The probability that NONE of them have matching birthday is

$5/5 * 4/5 * 3/5 = 0.48$

The probability there is AT LEAST one matching pair is

$1 - 0.48 = 0.52$


What if I wanted to use inclusion-exclusion, i.e. the "long-cut", how to calculate this

$P = 0.52 = P(A_1,_2) + P(A_1,_3) + P(A_2,_3)$

$P = 0.52 = P(A_1,_2 \cup A_1,_3 \cup A_2,_3) - P(A_1,_2 \cap A_1,_3 \cap A_2,_3)$

This has been puzzling me for days, please assist.

  • 1
    $\begingroup$ Actually probability of no match is $\frac55\frac45\frac35=0.48$ $\endgroup$ – paw88789 Jan 7 '16 at 17:15
  • $\begingroup$ @paw88789 Thanks, I corrected OP $\endgroup$ – Rhonda Jan 7 '16 at 17:23

We'll let $$A = \{\text{At least one match}\}$$ and so $$\bar A = \{\text{No match}\}.$$ So, mechanically \begin{align*} P(A) &= P(A_{1,2}\cup A_{1,3}\cup A_{2,3})\\ &= P(A_{1,2})+ P(A_{1,3})+P(A_{2,3})\tag 1\\ &\qquad-[P(A_{1,2},A_{1,3})+P(A_{1,2}, A_{2,3})+P(A_{1,3}, A_{2,3})]\\ &\qquad+[P(A_{1,2},A_{1,3},A_{2,3})]\\ &= 3P(A_{1,2})-3P(A_{1,2},A_{2,3})+P(A_{1,2},A_{1,3},A_{2,3})\tag 2\\ &=3\binom{5}{1}\left(\frac{1}{5}\right)^2-3\binom{5}{1}\left(\frac{1}{5}\right)^3+\binom{5}{1}\left(\frac{1}{5}\right)^3\\ &= 0.52 \end{align*} where in $(1)$ I invoke inclusion-exclusion, and in $(2)$ I recognize that some terms are identical in probability and simply multiply by 3. There are $\binom{5}{1} = 5$ ways to choose a day in a 5-day year.

Verify, using the complement and independence, $$P(A) = 1-P(\bar A) = 1-\frac{5}{5}\cdot\frac{4}{5}\cdot\frac{3}{5} = 0.52.$$

Diagram here.

  • $\begingroup$ I'm trying to do this pictorially, i.e. three intersecting circles $\endgroup$ – Rhonda Jan 8 '16 at 19:59
  • $\begingroup$ @Rhonda Does this help? $\endgroup$ – Em. Jan 8 '16 at 20:31
  • $\begingroup$ Holy Cow! That's what I'm trying to do right now. I believe this shall help, let me check. $\endgroup$ – Rhonda Jan 8 '16 at 20:32
  • $\begingroup$ So the $P(AB,B2,AC)$ gets subtracted three times with $-[P(AB,BC)+P(BC,AC)+P(AB,AC)]$, hence we must add it back once? Because $[P(AB,BC)+P(BC,AC)+P(AB,AC)]$ adds the intersection of $A \cap B \cap C$ three times? $\endgroup$ – Rhonda Jan 8 '16 at 20:38
  • $\begingroup$ @Rhonda Yeah, notice that $P(AB,BC)$ is just saying $P(ABC)$. This why in the green box you subtract it $3$ times. Finally, inclusion-exclusion tells you to add one back. So in the end, in the green box, you only subtract 2. $\endgroup$ – Em. Jan 8 '16 at 20:43

Essentially according to the inclusion-exclusion principle, we have the following line of reasoning: The probability that the first and second people share a birthday is $p_{12} = 1/5$. Similarly, $p_{13} = p_{23} = 1/5$. If we add these three probabilities up, we get $3/5$.

However, in so doing, we have triple-counted the probability that all three share the same birthday. That probability is $(1/5)(1/5) = 1/25$, and since it is triple-counted in the sum, we should subtract twice that amount. Therefore, the overall probability that at least two people share a birthday is

$$ P(\text{birthday shared}) = \frac{3}{5}-\frac{2}{25} = \frac{13}{25} = 0.52 $$

  • $\begingroup$ I'm trying to draw a picture of this. I understand everything up to and since it is triple-counted in the sum, we should subtract twice that amount $\endgroup$ – Rhonda Jan 8 '16 at 20:00

Since the events you are considering, $P_{1,2}, P_{1,3}, P_{2,3}$ are not disjoint, you cannot just sum their probabilities in order to get the probability of the union. You can therefore resort to the inclusion-exclusion principle which, as you know, states that for events $A_1, A_2, \dots, A_n$ $$     \mbox{P}\biggl(\bigcup_{i=1}^n A_i\biggr) {} =\sum_{i=1}^n \mbox{P}(A_i) -\sum_{i<j}\mbox{P}(A_i\cap A_j) +\sum_{i<j<k}\mbox{P}(A_i\cap A_j\cap A_k)-\ \cdots\ +(-1)^{n-1}\, \mbox{P}\biggl(\bigcap_{i=1}^n A_i\biggr), $$

In a nutshell, you add the probabilities of all possible intersections of an odd number of events and subtract the probabilities of all possible intersections of an even number of events.

In your case this translates to $$ \frac {3}{5} - \frac {3}{25} + \frac {1}{25} =0.52 $$


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.