Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
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. –  Dilip Sarwate Dec 29 '11 at 2:48

2 Answers 2

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.

share|improve this answer
    
+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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.