Calculate Inclusion-Exclusion in Birthday Paradox

Question

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$

Question

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.

Answer 1

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

---

Answer 2

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

Answer 3

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