X

### Discrete Probability

• An experiment is a procedure that yields one of a given set of possible outcomes. The sample space of the experiment is the set of possible outcomes. An event is a subset of the sample space.

• If "S" is a ﬁnite nonempty sample space of equally likely outcomes, and "E" is an event, that is, a subset of "S", then the probability of "E" is p(E) = |E| / |S|

• The probability of an event can never be negative or more than one!

Q. An urn contains four blue balls and ﬁve red balls. What is the probability that a ball chosen at random from the urn is blue?

• To calculate the probability, note that there are nine possible outcomes, and four of these possible outcomes produce a blue ball.

• Hence, the probability that a blue ball is chosen is 4/9.

Q. There are many lotteries now that award enormous prizes to people who correctly choose a set of six numbers out of the ﬁrst n positive integers, where n is usually between 30 and 60. What is the probability that a person picks the correct six numbers out of 40?

• There is only one winning combination. The total number of ways to choose six numbers out of 40 is C(40, 6) = 3,838,380

• Consequently, the probability of picking a winning combination is 1/3,838,380 ≈ 0.00000026

Q. Find the probability that a hand of ﬁve cards in poker contains four cards of one kind

• By the product rule, the number of hands of ﬁve cards with four cards of one kind is the product of the number of ways to pick one kind, the number of ways to pick the four of this kind out of the four in the deck of this kind, and the number of ways to pick the ﬁfth card. This is C(13, 1)C(4, 4)C(48, 1)

• There are C(52, 5) different hands of ﬁve cards. Hence, the probability that a hand contains four cards of one kind is :

• C(13, 1)C(4, 4)C(48, 1) / C(52, 5)

Q. What is the probability that the numbers 11, 4, 17, 39, and 23 are drawn in that order from a bin containing 50 balls labeled with the numbers 1, 2,...,50 if (a) the ball selected is not returned to the bin before the next ball is selected and (b) the ball selected is returned to the bin before the next ball is selected?

• (a) By the product rule, there are 50 · 49 · 48 · 47 · 46 = 254,251,200 ways to select the balls because each time a ball is drawn there is one fewer ball to choose from. Consequently, the probability that 11, 4, 17, 39, and 23 are drawn in that order is 1/254,251,200. This is an example of sampling without replacement.

• (b) By the product rule, there are 50 5 = 312,500,000 ways to select the balls because there are 50 possible balls to choose from each time a ball is drawn. Consequently, the probability that 11, 4, 17, 39, and 23 are drawn in that order is 1/312,500,000. This is an example of sampling with replacement.

### Probabilities of Complements and Unions of Events

• Let E be an event in a sample space S. The probability of the event E' = S − E, the complementary event of E, is given by

• p(E') = 1 − p(E)

Q. A sequence of 10 bits is randomly generated. What is the probability that at least one of these bits is 0?

• Let E be the event that at least one of the 10 bits is 0. Then E is the event that all the bits are 1s. Because the sample space S is the set of all bit strings of length 10, it follows that

• p(E') = 1 − p(E)

• = 1 - |E'|/|S|

• = 1 - 1/1024

Probability of the union of two events

• Let E1 and E2 be events in the sample space S.

• Then p(E1 ∪ E2) = p(E1) + p(E2) - p(E1 ∩ E2)

Q. What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5?

• E1 = 50

• E2 = 20

• E1 ∩ E2 = 10

• p(E1 ∪ E2) = p(E1) + p(E2) - p(E1 ∩ E2) = (50 + 20 - 10) / 100 = 3/5

Q. What probabilities should we assign to the outcomes H (heads) and T (tails) when a fair coin is ﬂipped? What probabilities should be assigned to these outcomes when the coin is biased so that heads comes up twice as often as tails?

• For a fair coin, the probability that heads comes up when the coin is ﬂipped equals the probability that tails comes up, so the outcomes are equally likely.

• Consequently, we assign the probability 1/2 to each of the two possible outcomes, that is, p(H) = p(T ) = 1/2.

• For the biased coin we have p(H) = 2p(T).

• Because p(H) + p(T ) = 1, it follows that 2p(T) + p(T ) = 3p(T ) = 1

• We conclude that p(T ) = 1/3 and p(H) = 2/3.

Conditional Probability

• Let E and F be events with p(F) > 0. The conditional probability of E given F, denoted by p(E | F), is deﬁned as

• p(E | F) = p(E ∩ F) / p(F)

Q. A bit string of length four is generated at random so that each of the 16 bit strings of length four is equally likely. What is the probability that it contains at least two consecutive 0s, given that its ﬁrst bit is a 0? (We assume that 0 bits and 1 bits are equally likely.)

• Let E be the event that a bit string of length four contains at least two consecutive 0s, and let F be the event that the ﬁrst bit of a bit string of length four is a 0. The probability that a bit string of length four has at least two consecutive 0s, given that its ﬁrst bit is a 0, equals

• p(E | F) = p(E ∩ F) / p(F)

• Because E ∩ F ={0000, 0001, 0010, 0011, 0100}, we see that p(E ∩ F) = 5/16. Because there are eight bit strings of length four that start with a 0, we have p(F) = 8/16 = 1/2. Consequently

• p(E | F) = ( 5/16 ) / ( 1/2 ) = 5 / 8

Q. What is the conditional probability that a family with two children has two boys, given they have at least one boy? Assume that each of the possibilities BB, BG, GB, and GG is equally likely, where B represents a boy and G represents a girl. (Note that BG represents a family with an older boy and a younger girl while GB represents a family with an older girl and a younger boy.)

• Let E be the event that a family with two children has two boys, and let F be the event that a family with two children has at least one boy. It follows that E ={BB}, F ={BB, BG, GB}, and E ∩ F ={BB}. Because the four possibilities are equally likely, it follows that p(F) = 3/4 and p(E ∩ F) = 1/4. We conclude that

• p(E | F) = p(E ∩ F) / p(F) = [1/4] / [3/4] = 1/3

Independence

• The events E and F are independent if and only if p(E ∩ F) = p(E)p(F)

Q. Suppose E is the event that a randomly generated bit string of length four begins with a 1 and F is the event that this bit string contains an even number of 1s. Are E and F independent, if the 16 bit strings of length four are equally likely?

• There are eight bit strings of length four that begin with a one: 1000, 1001, 1010, 1011, 1100, 1101, 1110, and 1111. There are also eight bit strings of length four that contain an even number of ones: 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111. Because there are 16 bit strings of length four, it follows that

• p(E) = p(F) = 8/16 = 1/2.

• Because E ∩ F ={1111, 1100, 1010, 1001}, we see that

• p(E ∩ F) = 4/16 = 1/4.

• Because p(E ∩ F) = 1/4 = (1/2)(1/2) = p(E)*p(F), we conclude that E and F are independent.

Q. Assume, as in Example 4, that each of the four ways a family can have two children is equally likely. Are the events E, that a family with two children has two boys, and F, that a family with two children has at least one boy, independent?

• Because E ={BB},wehavep(E) = 1/4

• we showed that p(F) = 3/4 and that p(E ∩ F) = 1/4.

• But p(E)p(F) = 1/4 · 3/4 = 3/16.

• Therefore p(E ∩ F) ≠ p(E)p(F), so the events E and F are not independent.

Q. Are the events E, that a family with three children has children of both sexes, and F, that this family has at most one boy, independent? Assume that the eight ways a family can have three children are equally likely.

• By assumption, each of the eight ways a family can have three children, BBB, BBG, BGB, BGG, GBB, GBG, GGB, and GGG, has a probability of 1/8. Because E ={BBG, BGB, BGG, GBB, GBG, GGB}, F ={BGG, GBG, GGB, GGG}, and E ∩ F ={BGG, GBG, GGB}, it follows that p(E) = 6/8 = 3/4, p(F) = 4/8 = 1/2, and p(E ∩ F) = 3/8

• Because p(E)p(F) = 3/4 * 1/2 = 3/8

• it follows that p(E ∩ F) = p(E)p(F),so E and F are independent

### Bernoulli Trials and the Binomial Distribution

• Suppose that an experiment can have only two possible outcomes. For instance, when a bit is generated at random, the possible outcomes are 0 and 1.

• When a coin is ﬂipped, the possible outcomes are heads and tails. Each performance of an experiment with two possible outcomes is called a Bernoulli trial.

• In general, a possible outcome of a Bernoulli trial is called a success or a failure.If "p" is the probability of a success and "q" is the probability of a failure, it follows that p + q = 1.

• The probability of exactly "k" successes in "n" independent Bernoulli trials, with probability of success p and probability of failure q = 1 − p, is C(n, k) * (p)k * (q)n - k

Q. A coin is biased so that the probability of heads is 2/3. What is the probability that exactly four heads come up when the coin is ﬂipped seven times, assuming that the ﬂips are independent?

• There are 27 = 128 possible outcomes when a coin is ﬂipped seven times

• The number of ways four of the seven ﬂips can be heads is C(7, 4). Because the seven ﬂips are independent, the probability of each of these outcomes (four heads and three tails) is (2/3)4 * (1/3)3

• Consequently, the probability that exactly four heads appear is C(7, 4) * (2/3)4 * (1/3)3

Suppose that the probability that a 0 bit is generated is 0.9, that the probability that a 1 bit is generated is 0.1, and that bits are generated independently. What is the probability that exactly eight 0 bits are generated when 10 bits are generated?

• b(8; 10, 0.9) = C(10, 8) * (0.9)8 * (0.1)2 = 0.193

### Bayes’ Theorem

• Suppose that E and F are events from a sample space S such that p(E) ≠ 0 and p(F) ≠ 0. Then

• p(F | E) = p(E | F)p(F) / [p(E | F)p(F)+ p(E | F')p(F')]

Q. Suppose that one person in 100,000 has a particular rare disease for which there is a fairly accurate diagnostic test. This test is correct 99.0% of the time when given to a person selected at random who has the disease; it is correct 99.5% of the time when given to a person selected at random who does not have the disease. Given this information can we ﬁnd (a) the probability that a person who tests positive for the disease has the disease? (b) the probability that a person who tests negative for the disease does not have the disease? Should a person who tests positive be very concerned that he or she has the disease?

• (a) Let "F" be the event that a person selected at random has the disease, and let "E" be the event that a person selected at random tests positive for the disease. We want to compute p(F | E). To use Bayes’ theorem to compute p(F | E) we need to ﬁnd p(E | F), p(E | F'), p(F), and p(F').

• We know that one person in 100,000 has this disease, so p(F) = 1/100,000 = 0.00001 and p(F') = 1 − 0.00001 = 0.99999. Because a person who has the disease tests positive 99% of the time, we know that p(E | F) = 0.99; this is the probability of a true positive, that a person with the disease tests positive. It follows that p(E' | F) = 1 − p(E | F) = 1 − 0.99 = 0.01; this is the probability of a false negative, that a person who has the disease tests negative.

• Furthermore, because a person who does not have the disease tests negative 99.5% of the time, we know that p(E' | F') = 0.995. This is the probability of a true negative, that a person without the disease tests negative. Finally, we see that p(E |F') = 1 − p(E' | F') = 1 − 0.995 = 0.005; this is the probability of a false positive, that a person without the disease tests positive.

• The probability that a person who tests positive for the disease actually has the disease is p(F | E). By Bayes’ theorem, we know that

• p(F | E) = p(E | F)p(F) / [p(E | F)p(F)+ p(E | F')p(F')]

• (0.99)(0.00001) / (0.99)(0.00001) + (0.005)(0.99999) ≈ 0.002.

• (b) The probability that someone who tests negative for the disease does not have the disease is p(F' | E'). By Bayes’ theorem, we know that

• p(F' | E') = p(E' | F')p(F') / p(E' | F')p(F')+ p(E' | F)p(F)

• = (0.995)(0.99999) / (0.995)(0.99999) + (0.01)(0.00001) ≈ 0.9999999.

• Consequently, 99.99999% of the people who test negative really do not have the disease.

• In part (a) we showed that only 0.2% of people who test positive for the disease actually have the disease. Because the disease is extremely rare, the number of false positives on the diagnostic test is far greater than the number of true positives, making the percentage of people who test positive who actually have the disease extremely small. People who test positive for the diseases should not be overly concerned that they actually have the disease

Q. Suppose that we have found that the word “Rolex” occurs in 250 of 2000 messages known to be spam and in 5 of 1000 messages known not to be spam. Estimate the probability that an incoming message containing the word “Rolex” is spam, assuming that it is equally likely that an incoming message is spam or not spam. If our threshold for rejecting a message as spam is 0.9, will we reject such messages?

• Using the counts of each of these two words in messages known to be spam or known not to be spam, we obtain the following estimates:

• p(stock) = 400/2000 = 0.2, q(stock) = 60/1000 = 0.06, p(undervalued) = 200/2000 = 0.1, and q(undervalued) = 25/1000 = 0.025.

• Using these probabilities, we can estimate the probability that the message is spam by

• r(stock, undervalued) = p(stock)p(undervalued) / p(stock)p(undervalued) + q(stock)q(undervalued)

• = (0.2)(0.1) / (0.2)(0.1) + (0.06)(0.025) ≈ 0.930.

 Previous Next