Robert P. Dobrow

Probability


Скачать книгу

upper B right-parenthesis minus upper P left-parenthesis upper A upper B right-parenthesis 2nd Row 1st Column Blank 2nd Column plus upper P left-parenthesis upper C right-parenthesis minus left-bracket upper P left-parenthesis upper A upper C right-parenthesis plus upper P left-parenthesis upper B upper C right-parenthesis minus upper P left-parenthesis upper A upper B upper C right-parenthesis right-bracket period EndLayout"/>

      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 upper A 1 comma ellipsis comma upper A Subscript n Baseline, the probability that at least one event occurs is

StartLayout 1st Row 1st Column Blank 2nd Column upper P left-parenthesis upper A 1 union midline-horizontal-ellipsis union upper A Subscript n Baseline right-parenthesis equals sigma-summation Underscript i Endscripts upper P left-parenthesis upper A Subscript i Baseline right-parenthesis minus sigma-summation Underscript i less-than j Endscripts upper P left-parenthesis upper A Subscript i Baseline upper A Subscript j Baseline right-parenthesis 2nd Row 1st Column Blank 2nd Column plus sigma-summation Underscript i less-than j less-than k Endscripts upper P left-parenthesis upper A Subscript i Baseline upper A Subscript j Baseline upper A Subscript k Baseline right-parenthesis minus midline-horizontal-ellipsis plus left-parenthesis negative 1 right-parenthesis Superscript n plus 1 Baseline upper P left-parenthesis upper A 1 comma ellipsis comma upper A Subscript n Baseline right-parenthesis period EndLayout

       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.

      The Monte Carlo simulation approach is based on the relative frequency model for probabilities. Given a random experiment and some event upper A, the probability upper P left-parenthesis upper A right-parenthesis is estimated by repeating the random experiment many times and computing the proportion of times that upper A occurs.

      More formally, define a sequence upper X 1 comma upper X 2 comma ellipsis comma where

upper X Subscript k Baseline equals StartLayout Enlarged left-brace 1st Row 1st Column 1 comma 2nd Column if upper A occurs on the k th trial 2nd Row 1st Column 0 comma 2nd Column if upper A does not occur on the k th trial comma EndLayout

      for k equals 1 comma 2 comma ellipsis. Then

StartFraction upper X 1 plus midline-horizontal-ellipsis plus upper X Subscript n Baseline Over n EndFraction

      is the proportion of times in which upper A occurs in n trials. For large n, the Monte Carlo method estimates upper P left-parenthesis upper A right-parenthesis by

      (1.7)upper P left-parenthesis upper A right-parenthesis almost-equals StartFraction upper X 1 plus midline-horizontal-ellipsis plus upper X Subscript n Baseline Over n EndFraction period

      MONTE CARLO SIMULATION

      Implementing a Monte Carlo simulation of upper P left-parenthesis upper A right-parenthesis requires three steps:

      1 Simulate a