3
$\begingroup$

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?

  • 1
    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.2011-12-29

2 Answers 2

12

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:

enter image description 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

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

  • 0
    I agree with Dilip's first remark about this answer. It's not easy to find a clear statement or explanation of the addition rule for arbitrary $n$ on the web, or even in some textbooks. I am disappointed that I can only add one vote.2018-01-17
2

You essentially do, but as others have pointed out, the above formula is incorrect. A classical way of calculating this is based in the following sieve formula:

http://en.wikipedia.org/wiki/Inclusion–exclusion_principle,

but of course there are other ways to break this down (eg, see above). The sieve formula is an easy inductive proof.