Probability. Robert P. Dobrow

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