4
$\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?

$\endgroup$
2
  • 1
    $\begingroup$ 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)? $\endgroup$
    – Lopsy
    Commented Dec 29, 2011 at 2:35
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 29, 2011 at 2:48

2 Answers 2

13
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ +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. $\endgroup$ Commented Dec 29, 2011 at 15:21
  • $\begingroup$ @Dilip Sarwate Thanks for the compliment Dilip. $\endgroup$ Commented Dec 29, 2011 at 15:30
  • $\begingroup$ 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. $\endgroup$
    – Mars
    Commented Jan 17, 2018 at 17:21
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .