Читать книгу Probability - Robert P. Dobrow - Страница 35

1.8 PROBLEM-SOLVING STRATEGIES: COMPLEMENTS AND INCLUSION–EXCLUSION

Оглавление

Consider a sequence of events In this section, we consider strategies to find the probability that at least one of the events occurs, which is the probability of the union , i.e., .

Sometimes the complement of an event can be easier to work with than the event itself. The complement of the event that at least one of the s occurs is the event that none of the s occur, which is the intersection

Check with a Venn diagram (and if you are comfortable working with sets prove it yourself) that


Complements turn unions into intersections, and vice versa. These set-theoretic results are known as DeMorgan's laws. The results extend to infinite sequences. Given events ,



 Example 1.29 Four dice are rolled. Find the probability of getting at least one 6.The sample space is the set of all outcomes of four dice rollsBy the multiplication principle, there are elements. If the dice are fair, each of these outcomes is equally likely. It is not obvious, without some new tools, how to count the number of outcomes that have at least one 6.Let be the event of getting at least one 6. Then the complement is the event of getting no sixes in four rolls. An outcome has no sixes if the dice rolls a 1, 2, 3, 4, or 5 on every roll. By the multiplication principle, there are possibilities. Thus, and

Recall the formula in Equation 1.3 for the probability of a union of two events. We generalize for three or more events using the principle of inclusion–exclusion.

For events , , and ,


As we first include the sets, then exclude the pairwise intersections, then include the triple intersection, this is called the inclusion–exclusion principle. The proof is intuitive with the help of a Venn diagram, which we leave to the reader. Write


The bracketed sets and are disjoint. Thus,

(1.6)

Write as the disjoint union


Rearranging gives


Together with Equation 1.6, we find


Extending further to more than three events gives the general principle of inclusion–exclusion. We will not prove it, but if you know how to use mathematical induction, give it a try.

Probability

Подняться наверх