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

INCLUSION–EXCLUSION

Оглавление

Given events , the probability that at least one event occurs is


 Example 1.30 An integer is drawn uniformly at random from such that each number is equally likely. What is the probability that the number drawn is divisible by 3, 5, or 6?Let , and denote the events that the number drawn is divisible by 3, 5, and 6, respectively. The problem asks for . By inclusion–exclusion,Let denote the integer part of . There are numbers from 1 to 1000 that are divisible by . Because all selections are equally likely,A number is divisible by 3 and 5 if and only if it is divisible by 15. Thus, . If a number is divisible by 6, it is also divisible by 3, so . Also, . And This givesPutting it all together gives us that is equal to

We have presented two different ways of computing the probability that at least one of several events occurs: (i) a “back-door” approach of taking complements and working with the resulting “and” probabilities and (ii) a direct “frontal-attack” by inclusion–exclusion. Here is a third way, which illustrates decomposing an event into a union of mutually exclusive subsets.


 Example 1.31 Consider a random experiment that has equally likely outcomes, one of which we call success. Repeat the experiment times. Let be the event that at least one of the outcomes is a success. We want to find .For instance, consider rolling a die 10 times, where success means rolling a three. Here , , and is the event of rolling at least one 3.Define a sequence of events , where is the event that the th trial is a success. Then and . We cannot use the addition rule on this probability as the s are not mutually exclusive.To define a sequence of mutually exclusive events, let be the event that the first success occurs on the th trial. Then the s are mutually exclusive. Furthermore,Thus, To find , observe that if the first success occurs on the th trial, then the first trials are necessarily not successes and the th trial is a success. There are possible outcomes for each of the first trials, one outcome for the th trial, and possible outcomes for each of the remaining trials. By the multiplication principle, there are outcomes where the first success occurs on the th trial, and there are possible outcomes in all. Thus,for . The desired probability isFor instance, the probability of rolling at least one 3 in 10 rolls of a die is

Probability

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