Deriving equation for $P(A\cup B \cup C \cup D)$

Question

So I'm asked to derive this formula and this is my attempt so far:

$P(A\cup B \cup C \cup D)=P((A\cup B)\cup (C\cup D))$

$=P(A\cup B) + P(C\cup D) - P\big((A\cup B) \cap (C\cup D)\big)$

$P(A\cup B) = P(A) + P(B) - P(AB)$

$P(C\cup D) = P(C) + P(D) - P(CD)$

$P\big((A\cup B) \cap (C\cup D)\big)$

$=P\big((AC\cup AD) \cup (BC \cup BD)\big)$

$=P(AC \cup AD) + P(BC \cup CD) - P\big(( AC \cup AD) \cap (BC \cup CD) \big)$

$P(AC \cup AD) = P(AC)+P(AD)-P(ACD)$

$P(BC\cup BD) = P(BC)+ P(BD) - P(BCD)$

$P\big(( AC \cup AD) \cap (BC \cup BD) \big)=$???

This is the part I am stuck on. Can someone please help me? and are my steps correct so far?

Answer 1

Let’s build the PIE scenario for this case with 4 I guess.
Start with a blank slate for which we want to find the union of all 4 circles.

and we will want to add each part once, which gives(i drew this one out of order oops)

$$+P(D)$$ $$+P(A)$$ $$+P(B)$$ $$+P(C)$$

So far, we have $$P(A)+P(B)+P(C)+P(D)$$ Blue is counted once, green twice, orange 3 times, and pink 4 times.

Now let’s subtract off the greens which give

$$-P(A\cap B)$$ $$-P(A\cap C)$$ $$-P(A\cap D)$$ $$-P(B\cap C)$$ $$-P(B\cap D)$$ $$-P(C\cap D)$$

$$P(A)+P(B)+P(C)+P(D)$$ $$-P(A\cap B)-P(A\cap C)-P(A\cap D)-P(B\cap C)-P(B\cap D)-P(C\cap D)$$

Light red is an extra subtracted region, solid red is subtracted twice. To fix this, we’ll add back a the triple intersection regions which give us

$$+P(A\cap B\cap C)$$ $$+P(A\cap B\cap D)$$ $$+P(A\cap C\cap D)$$ $$+P(B\cap C\cap D)$$

$$P(A)+P(B)+P(C)+P(D)$$ $$-P(A\cap B)-P(A\cap C)-P(A\cap D)-P(B\cap C)-P(B\cap D)-P(C\cap D)$$ $$+P(A\cap B\cap C)+P(A\cap B\cap D)+P(A\cap C\cap D)+P(B\cap C\cap D)$$

Lastly we subtract the over-added region to get

$$-P(A\cap B\cap C\cap D)$$

Which is what is desired. Hence, $$P(A\cup B\cup C\cup D)=$$ $$P(A)+P(B)+P(C)+P(D)$$ $$-P(A\cap B)-P(A\cap C)-P(A\cap D)-P(B\cap C)-P(B\cap D)-P(C\cap D)$$ $$+P(A\cap B\cap C)+P(A\cap B\cap D)+P(A\cap C\cap D)+P(B\cap C\cap D)$$ $$-P(A\cap B\cap C\cap D)$$

Edit: Sammy Black pointed out that

By the way, this is not a good Venn diagram for an arbitrary collection of 4 sets, as it only has 14 regions (rather than the expected $2^4=16$ regions). There's no region for opposite pairs of circles: ∩ or ∩. One alternative is this “fan” shape made of ellipses.

However as far as I can tell the general gist of the derivation is still the same, so it should be fine

Answer 2

Some hints/previous steps for your proof.

1. It is true that $P(A\cup B)=P(A)+P(B)-P(A\cap B)$. Prove as an exercise, noticing that $A\cup B=[A\setminus (A\cap B)]\cup [A\cap B] \cup [B\setminus(A\ \cap B)]$ the union of 3 disjoint sets and using Kolmogorov´s axiom 3: probability of the union of disjoints sets is the sum of the probabilities of these sets.

2. $P(A\cup B \cup C) = P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C) + P(A\cap B \cap C)$ Prove as an exercise. Hint: Make a substitution $F=A\cup B$, use the result in 1. for finding $P(F\cup C)$ and after that replace $F$ and use the definition for $P(A\cup B)$ in 1.

3. Prove the final result, noticing that $P(A\cup B \cup C\cup D)=P(G\cup D)$, with $G=A\cup B\cup C$, using 1. and 2. The steps in the proof will be obvious if you solve the previous problems.

If you are comfortable with 1 to 3 it will be easy to use induction to proof the case considering the union of $n$ sets.

Answer 3

We can derive the formula easily by using indicator functions. If you are familiar with them, just skip to the last part. The reason I'm presenting this is because using this tool one can easily derive the general principle of the inclusion-exclusion.

1. An introduction to indicator functions.

For subset $X\subseteq \Omega$ define $1_X\colon\Omega\to \mathbb R$ $$1_X(\omega) = \cases {1,\ \omega\in X \\ 0,\ \omega\in \Omega\setminus X}$$ The point is that these functions basically count the number of elements of $X$. For example, if $\Omega$ is finite, we have $$|X| = \sum_{\omega\in\Omega} 1_X(\omega).$$ Taking a step further $$E(1_X) = \sum_{\omega\in \Omega} 1_X(\omega)P(\{\omega\}) = \sum_{\omega\in X}P(\{\omega\}) = P(X)$$ i.e. the expected value of random variable $1_X$ is $P(X)$. Of course, the above reasoning breaks down for infinite $\Omega$ but in that case you integrate instead of sum and you still get $$P(X) = E(1_X).$$ (Note. This is how integral is defined in measure theory, but we don't need to go there.)

2. Basic properties of indicator functions.

Let's have a look how indicator functions behave with respect to elementary set operations.

(a) $1_{A\cap B} = 1_A\cdot 1_B$

(b) $1_{A^c} = 1 - 1_A$

(c) $1_{A\cup B} = 1_A + 1_B - 1_{A\cap B}$

Proof.

(a) $1_{A\cap B}(\omega) = 1$ iff $\omega\in A\cap B$ iff $\omega\in A$ and $\omega\in B$ iff $1_A(\omega) = 1$ and $1_B(\omega) = 1$ iff $1_A(\omega)\cdot 1_B(\omega) = 1$.

(b) $1_{A^c}(\omega) = 1$ iff $\omega \in A^c$ iff $\omega\not\in A$ iff $1_A(\omega) = 0$ iff $(1-1_A)(\omega) = 1$.

(c) This is actually the basic case of the principle of inclusion-exclusion, which can be shown to hold for example by considering different disjoint cases. I will prove it using De Morgan's law: \begin{align} (A\cup B)^c = A^c\cap B^c &\iff 1_{(A\cup B)^c} = 1_{A^c\cap B^c} \\ &\stackrel{\text {(b)}}{\iff} 1_{(A\cup B)^c} = 1_{A^c}\cdot 1_{B^c} \\ &\stackrel{\text {(b)}}{\iff} 1 - 1_{A\cup B} = (1- 1_A)(1-1_B)\\ &\iff 1 - 1_{A\cup B} = 1 - 1_A - 1_B + 1_A\cdot 1_B\\ &\stackrel{\text {(b)}}{\iff} 1_{A\cup B} = 1_A + 1_B - 1_{A\cap B} \end{align}

I purposely wrote this to show that (c) is equivalent to $1 - 1_{A\cup B} = (1- 1_A)(1-1_B)$. Also notice that taking expected value of both sides of (c) gives us $$P(A\cup B) = P(A) + P(B) - P(A\cap B).$$

3. Derivation of the wanted formula.

$$1-1_{A\cup B \cup C \cup D} = (1-1_{A\cup B})(1-1_{C\cup D}) = (1-1_A)(1-1_B)(1-1_C)(1-1_D).$$

Expanding the RHS gives us:

$$1-1_{A\cup B \cup C \cup D} = 1 - (1_A+1_B+1_C+1_D) + (1_A\cdot 1_B + 1_A\cdot 1_C + 1_A\cdot 1_D + 1_B\cdot 1_C + 1_B\cdot 1_D + 1_C\cdot 1_D) - (1_A\cdot 1_B \cdot 1_C + 1_A\cdot 1_B \cdot 1_D + 1_A\cdot 1_C \cdot 1_D + 1_B\cdot 1_C \cdot 1_D) + 1_A\cdot 1_B \cdot 1_C\cdot 1_D.$$

Rearranging and taking expected value of both sides gives us: \begin{align}P(A\cup B\cup C\cup D) &= P(A) + P(B) + P(C) + P(D)\\ &- (P(A\cap B) + P(A\cap C) + P(A\cap D) + P(B\cap C) + P(B\cap D) + P(C\cap D))\\ &+ (P(A\cap B \cap C) + P(A\cap B \cap D)+P(A\cap C \cap D)+P(B\cap C \cap D))\\ &- P(A\cap B \cap C \cap D).\end{align}

This derivation generalizes to the following formula:

$$P(\bigcup_{i=1}^n A_i) = \sum_{\emptyset \neq I \subseteq \{1,\ldots,n\}}(-1)^{|I|+1}P(\bigcap_{i\in I} A_i).$$