the portion of the path up until the tie across the axis, giving the outcome in the right diagram. The reflection results in a path that starts with B.Conversely, consider a path that starts with B. As there are more As than Bs, at some point in the count, there must be a tie and the path crosses the -axis. Reflecting the portion of the path up until the tie across the -axis gives a “bad” path that starts with A.Having established a one-to-one correspondence we see that the number of “bad” lists that start with A is equal to the number of lists that start with B. There are lists that start with B. This gives the desired probabilityWe leave it to the reader to check that this last expression simplifies to
To round out this chapter, in the next sections, we examine some problem-solving strategies and take a first look at simulation as tools to help in your study of probability.
1.8 PROBLEM-SOLVING STRATEGIES: COMPLEMENTS AND INCLUSION–EXCLUSION
Consider a sequence of events
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
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
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
Write
Rearranging gives
Together
