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.
INCLUSION–EXCLUSION
Given events
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
1.9 A FIRST LOOK AT SIMULATION
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.
The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully? After spending a lot of time trying to estimate them by pure combinatorial calculations, I wondered whether a more practical method than “abstract thinking” might not be to lay it out say one hundred times and simply observe and count the number of successful plays. This was already possible to envisage with the beginning of the new era of fast computers, and I immediately thought of problems of neutron diffusion and other questions of mathematical physics, and more generally how to change processes described by certain differential equations into an equivalent form interpretable as a succession of random operations. Later [in 1946], I described the idea to John von Neumann, and we began to plan actual calculations.
The Monte Carlo simulation approach is based on the relative frequency model for probabilities. Given a random experiment and some event
More formally, define a sequence
for
is the proportion of times in which
(1.7)
