3
$\begingroup$

I am reading Sheldon Ross's book 'A first course in Probability'. In the second chapter, he is describing multiple proposition. I cannot understand proposition 4.4. I have it pasted below:

enter image description here

enter image description here

enter image description here

I follow until the moment he introduces (m k)

$\endgroup$
0

2 Answers 2

3
$\begingroup$

This is the inclusion-exclusion principle, which is a general principle for measures on unions of sets. There are a lot of different explanations of this principle available, so if you are having trouble following these specific notes, I recommend you look at some alternative sources on the subject.

In any case, for present purposes, consider a simplified version of this principle with three events , represented on the Venn diagram below with a green circle $A$, an orange circle $B$, and a purple circle $C$. I've numbered the areas in the Venn diagram (other than the outside area) for convenience. Suppose we want to find the probability of the union of these three events. Diagramatically, that is the probability of all the numbered areas in the diagram. Let's denote the probabilities of these areas by $P_1,...,P_7$ and observe that we have can write this as:

$$\begin{align} \mathbb{P}(A \cup B \cup C) &= P_1 + P_2 + P_3 + P_4 + P_5 + P_6 + P_7 \\[6pt] &= (P_1 + P_4 + P_5 + P_7) + (P_2 + P_4 + P_6 + P_7) + (P_3 + P_5 + P_6 + P_7) \\[6pt] &\quad - (P_4 + P_7) - (P_5 + P_7) - (P_6 + P_7) + P_7. \\[6pt] \end{align}$$

It is simple to verify that the second expression is identical to the first. In the latter arrangement of the terms: (1) we have first added the probabilities for the three full circles, but this overcounts things because it adds the areas between each pair twice; so (2) we have then subtracted each of the areas between the pairs of circles, but this now undercounts things because we have taken away the area shared by all three circles one too many times; so (3) we add this middle area back in to complete the equation. This is the general idea behind the inclusion-exclusion method. We first add in the marginal probabilities of the events, then we subtract the probabilities of intersections of pairs, then we add the probabilities of intersections of triples, and so on.

enter image description here

Now, with regard to the use of the binomial coefficients, these values tell you the number of terms in the rule with a given number of included events. If you have $m$ events then there are ${m \choose k}$ ways to choose $k$ events from this group, so the inclusion-exclusion rule will have ${m \choose 1} + {m \choose 2} + \cdots + {m \choose m}$ terms. (In the above example we have $3+3+1$ terms in the expansion.) The explanation in the text you show is a bit confusing and looks to me like a heuristic explanation; I presume it is referring to the case where each outcome in the Venn diagram is equiprobable (i.e., the events are mutually independent with probability one-half).

$\endgroup$
1
$\begingroup$

Moved from Comment format to Answer format per suggestion. Here is a guide to understanding the special case for $P(A\cup B\cup C).$

Start with a Venn Diagram with three circles: one each for $A, B, C$ overlapping. I have in mind a diagram with $2^3 = 8$ regions, including the region outside all of the circles.

[Notice that there is ${3 \choose 0} = 1$ region containing none of the three sets, there are ${3\choose 1} = 3$ regions containing parts of one set, ${3\choose 2} = 3$ (lens-shaped) regions containing parts of two sets, and there is ${3\choose 3} = 1$ (roughly triangular shaped) region containing parts of all three sets. Also, $1 + 3 + 3 + 1 = 2^3 = 8$ regions.]

If you add probabilities for $A$ and $B$ and $C$ to try for $P(A∪B∪C),$ you have double-counted three lens-shaped regions for $A∩B, B∩C$ and $A∩C$ and triple-counted one small almost triangular region for $A∩B∩C.$ So find $$P(A)+P(B)+P(C)−P(A∩B)−P(B∩C)−P(A∩C).$$

Now you have subtracted $P(A∩B∩C)$ three times. So you have $P(A∪B∪C)−P(A∩B∩C).$ Finally, to get $P(A∪B∪C)$ by adding back $P(A∩B∩C).$ In summary,

$$P(A\cup B\cup C) \\ = P(A)+P(B)+P(C)\;−P(AB)−P(BC)−P(AC)\;+P(ABC).$$

This process is called 'inclusion-exclusion'. To get $P(A∪B∪C)$ you have included three probabilities, excluded three smaller ones, and included one relatively very small probability.

The equation in Ross' book shows the inclusion-exclusion process necessary to get the general probability $P(E_1∪E_2,∪⋯∪E_n)$ with the proper number of inclusions, exclusions, inclusions, ..., and so on.

It helps to understand clearly what happens for three events before trying to generalize to $n.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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