# Probability of a Union

I know that $$P\left(\bigcup_{i=1}^{n} A_i \right)$$

is the sum of of the probabilities of all the sample points that are contained in at least one of the $A_{i}$'s. This is the probability of sample points belonging to exactly 1 event, exactly 2 events, ...,exactly $n$ events. WLOG this can be written as $$P\left(\bigcup_{i=1}^{n} A_i \right) = P(A_1) + P(A_1 \cap A_2) + \cdots + P(A_1 \cap A_2 \cap \cdots \cap A_n)$$

But the $A_i$'s are arbitrary and we have to account for that. So there are $n$ possibilities for the first probability, $\binom{n}{2}$ possibilities for the second probability, ..., and $1$ possibility for the final probability. So we add and subtract these to prevent overcounting?

-
Do you mean $P(A_1) + P(-A_1 \cap A_2) + \cdots + P(-A_1 \cap -A_2 \cap \cdots \cap A_n)$, or are you talking about the Principe of Inclusion and Exclusion (see Wikipedia or some such)? Also, given that you've posted a lot of probability questions today, I'm wondering if this is homework; if it is, you should tag it as such from now on. –  Lopsy Dec 29 '11 at 2:35
Your assertion about $P(\cup A_i)$ is incorrect. What would be correct is $$P(\cup A_i) = P(A_1) + P(A_1^c\cap A_2) + P(A_1^c\cap A_2^c\cap A_3) + \cdots + P(A_1^c\cap A_2^c \cap \cdots \cap A_{n-1}^c \cap A_n)$$ but then the explanation is all wrong. –  Dilip Sarwate Dec 29 '11 at 2:48

In general, if $A_1, A_2,\ldots, A_n$ are mutually disjoint events, then $$P\Bigl(\,\bigcup\limits_{i=1}^n A_i\,\Bigr ) =\sum_{i=1}^n P(A_i).$$

But (1) does not hold for arbitrary unions. One strategy to find a formula for the probability of a union of arbitrary events is to write the given union as a (different) union of mutually disjoint events.

From this, it follows that your initial statement, "This is the probability of sample points belonging to exactly 1 event, exactly 2 events, ...,exactly $n$ events." , is correct.

$P\Bigl(\,\bigcup\limits_{i=1}^n A_i\,\Bigr )$ is the sum of the probabilities of the events $B_i$ where $B_i$ is the event that exactly $i$ of the events $A_j$ occurs. You have, noting that the $B_i$ are mutually disjoint: $$P\Bigl(\,\bigcup\limits_{i=1}^n A_i\,\Bigr ) =\sum_{i=1}^n P(B_i).$$

But, the subsequent formula you have is incorrect. In fact, the event $B_1$ is somewhat complicated. If exactly one event $A_i$ occurs, then either $A_1$ only occurs, or $A_2$ only occurs, ... . So $$B_1= \bigcup_{j=1}^n \Bigl(\,A_j\cap ({\textstyle\bigcup\limits_{i\ne j }}\, A_i^C\,)\,\Bigr).$$

Trying to write down descriptions of the other $B_i$ might lead you to suspect this particular method is more trouble than its worth (of course, it may prove useful in certain problems).

The formula in Dilip's comment is a nice way to "disjointify" the union $\cup A_i$. If you draw a Venn diagram for the case $n=2$, it is easy to convince yourself that $A_1\cup A_2$ can be written as a union of pairwise disjoint events: $$A_1\cup A_2 = A_1 \cup (A_1^c\cap A_2).$$ So you can write $$P(A_1\cup A_2) =P( A_1)+ P (A_1^c\cap A_2).$$

For the case $n=3$, $A_1\cup A_2\cup A_3$ can be written as a union of pairwise disjoint events: $$A_1\cup A_2\cup A_3 = A_1 \cup(A_1^c\cap A_2)\cup (A_1^c\cap A_2^c\cap A_3).$$ So you can write $$P(A_1\cup A_2\cup A_3) =P( A_1)+P(A_1^c\cap A_2)+P (A_1^c\cap A_2^c\cap A_3).$$

And, of course the general formula in Dilip's comment holds because the union of the $A_i$ is written as a union of pairwise disjoint sets.

The "add and subtract business" you mention seems like what is done in deriving the so-called Inclusion-Exclusion principle, as mentioned in gnometorule's answer. This gives a different method for evaluating the probability of a union (it is not exactly the "disjointification" method above).

As a warm up to the general formula, let's consider the formulas for $P(A\cup B)$ and $P(A\cup B\cup C)$.

Probability of the union of two events:

Let us find the probability of the union of two arbitrary events $A$ and $B$.
One might think $P(A\cup B)=P(A)+P(B)$; however, each of $P(A)$ and $P(B)$ counts the probability of $A\cap B$. We thus have to subtract this probability from $P(A)+P(B)$ to obtain the correct formula:
$$P(A\cup B)=P(A)+P(B)-P(A\cap B).$$ Another way to derive the formula is to note that $A\cup B$ is the disjoint union of $A/B$, $B/A$, and $A\cap B$. Now, since $A$ is the disjoint union of $A\cap B$ and $A/B$, it follows that $P(A)=P(A\cap B)+P(A/B)$; whence $P(A/B)= P(A)-P(A\cap B)$.

In a similar manner, one shows that $P(B/A)= P(B)-P(B\cap A)$.

It follows that \eqalign{ P(A\cup B)&=P(A/B)+P(B/A)+P(A\cap B)\cr &=\bigl( P(A)-P(A\cap B)\bigr)+\bigl(P(B)-P(B\cap A)\bigr)+P(A\cap B) \cr &= P(A)+P(B)-P(A\cap B). }

Probability of the union of three events: For three arbitrary events $A$, $B$, and $C$, to find $P(A \cup B\cup C)$, we first start with the guess $$P(A\cup B\cup C)=P(A )+P(B)+P(C).\tag{1}$$ Now (1) counts each of $P(A \cap B)$, $P(A\cap C)$, and $P(B\cap C)$ twice. To make up for this, we have to subtract $$P(A \cap B)+P(A \cap C)+P(B\cap B).\tag{2}$$ But $P(A )+P(B)+P(C)$ counts $P(A \cap B \cap C)$ thrice, and in (2) we subtracted it thrice. So, we must add $P(A )+P(B)+P(C)$ back in again. We have: $$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).$$ Looking at the Venn diagram may be helpful here:

More generally, for the events $A_1$, $A_2$, $\ldots\,$, $A_n$, we have the inclusion-exclusion principle: \eqalign{ P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = \sum_{i\le n} P(A_i) - &\sum_{i_1<i_2} P(A_{i_1}\cap A_{i_2}) +\sum_{i_1<i_2<i_3} P(A_{i_1}\cap A_{i_2}\cap A_{i_3}) - \cr &\cdots+ (-1)^{n}\sum_{i_1<i_2<\cdots<i_{n-1} } P(A_{i_1}\cap\cdots\cap A_{i_{n-1}} )\cr&\qquad\qquad + (-1)^{n+1}P(A_1\cap A_2\cap\cdots\cap A_n)}.

As pointed out in the comments, this can be proved by induction.

-
+1 for a very well-written and thorough answer. I think the OP's translation of thoughts into notation follows a pattern very often seen in beginners: confusing between an outcome $\omega$ belonging to an event $A$ and an outcome belonging only to an event $A$ and not to other events. $$A\cup B=(A\cap B^c)\cup(A^c\cap B)\cup(A\cap B)$$ is saying "outcome belongs only to $A$ or only to $B$ or to both". The three parts are disjoint, and so probabilities can be added. But we add $P(A\cap B^c)$ and $P(A^c\cap B)$, not $P(A)$ and $P(B)$ as the OP seems trying to do. –  Dilip Sarwate Dec 29 '11 at 15:21
@Dilip Sarwate Thanks for the compliment Dilip. –  David Mitra Dec 29 '11 at 15:30