Robert P. Dobrow - Probability

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.

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

Using random numbers on a computer to simulate probabilities is called the Monte Carlo method. Today, Monte Carlo tools are used extensively in statistics, physics, engineering, and across many disciplines. The name was coined in the 1940s by mathematicians John von Neumann and Stanislaw Ulam working on the Manhattan Project. It was named after the famous Monte Carlo casino in Monaco.

Ulam's description of his inspiration to use random numbers to simulate complicated problems in physics is quoted in Eckhardt [1987]:

The first thoughts and attempts I made to practice [the Monte Carlo method] were suggested by a question which occurred to me in 1946 as I was convalescing from an illness and playing solitaires.