Probability And Stochastic Processes : A Friendly Introduction For Electrical And Computer Engineers, 3rd Edition Solution Manual

Problem Solutions – Chapter 2 Problem 2.1.1 Solution A sequential sample space for this experiment is 1/4 H1 1/4 H2 •H1 H2 T2 •H1 T2 1/16 3/16 3/4 X XXX 1/4 X H2 •T1 H2 3/16 3/4 X T1 XX XXX 3/4 X T2 •T1 T2 9/16 (a) From the tree, we observe P [H2 ] = P [H1 H2 ] + P [T1 H2 ] = 1/4. (1) 1/16 P [H1 H2 ] = = 1/4. P [H2 ] 1/4 (2) This implies P [H1 |H2 ] = (b) The probability that the first flip is heads and the second flip is tails is P[H1 T2 ] = 3/16. Problem 2.1.2 Solution The tree with adjusted probabilities is 3/4 G2 •G1 G2 XXX 1/4 X R2 •G1 R2 3/8 1/2 G1 XX HH H H 1/4 G2 •R1 G2 XXX X 3/4 X R2 •R1 R2 1/8 1/8 1/2HH R1 X 30 3/8 From the tree, the probability the second light is green is P [G2 ] = P [G1 G2 ] + P [R1 G2 ] = 3/8 + 1/8 = 1/2. (1) The conditional probability that the first light was green given the second light was green is P [G1 |G2 ] = P [G1 G2 ] P [G2 |G1 ] P [G1 ] = = 3/4. P [G2 ] P [G2 ] (2) Finally, from the tree diagram, we can directly read that P[G2 |G1 ] = 3/4. Problem 2.1.3 Solution Let Gi and Bi denote events indicating whether free throw i was good (Gi ) or bad (Bi ). The tree for the free throw experiment is 3/4 G2 •G1 G2 1/2 G1 XXX XX 1/4 X B2 •G1 B2 HH H H 1/4 G2 •B1 G2 XXX X 3/4 X B2 •B1 B2 3/8 1/8 1/8 1/2HH B1 X 3/8 The game goes into overtime if exactly one free throw is made. This event has probability P [O] = P [G1 B2 ] + P [B1 G2 ] = 1/8 + 1/8 = 1/4. Problem 2.1.4 Solution The tree for this experiment is 1/2 A 1/4 H •AH 1/8 T •AT 3/8 X XXX 3/4 X •BH 1/2 X B XX XXX H 1/4 X T •BT 1/8 3/4 31 3/8 (1) The probability that you guess correctly is P [C] = P [AT ] + P [BH] = 3/8 + 3/8 = 3/4. (1) Problem 2.1.5 Solution The P[− |H ] is the probability that a person who has HIV tests negative for the disease. This is referred to as a false-negative result. The case where a person who does not have HIV but tests positive for the disease, is called a false-positive result and has probability P[+|H c ]. Since the test is correct 99% of the time, P [−|H] = P [+|H c ] = 0.01. (1) Now the probability that a person who has tested positive for HIV actually has the disease is P [+, H] P [+, H] P [H|+] = = . (2) P [+] P [+, H] + P [+, H c ] We can use Bayes’ formula to evaluate these joint probabilities. P [+|H] P [H] P [+|H] P [H] + P [+|H c ] P [H c ] (0.99)(0.0002) = (0.99)(0.0002) + (0.01)(0.9998) = 0.0194. P [H|+] = (3) Thus, even though the test is correct 99% of the time, the probability that a random person who tests positive actually has HIV is less than 0.02. The reason this probability is so low is that the a priori probability that a person has HIV is very small. Problem 2.1.6 Solution Let Ai and Di indicate whether the ith photodetector is acceptable or defective. 3/5 A1 4/5 A2 •A1 A2 12/25 D2 •A1 D2 3/25 X X XXX 2/5 A2 •D1 A2 2/5 X D1 XX XXX 3/5 X D2 •D1 D2 4/25 1/5 32 6/25 (a) We wish to find the probability P[E1 ] that exactly one photodetector is acceptable. From the tree, we have P [E1 ] = P [A1 D2 ] + P [D1 A2 ] = 3/25 + 4/25 = 7/25. (1) (b) The probability that both photodetectors are defective is P[D1 D2 ] = 6/25. Problem 2.1.7 Solution The tree for this experiment is 3/4 H2 •A1 H1 H2 1/4 H1 T2 •A1 H1 T2 1/4 3/4 T1 XX H2 •A1 T1 H2 1/2 A1 3/4 XX X X T2 •A1 T1 T2 1/4 H HH H 3/32 1/32 9/32 3/32 1/4 H2 •B1 H1 H2 3/32 T2 •B1 H1 T2 XXX 3/4 1/4 X X T1 XX H2 •B1 T1 H2 1/4 XXX 3/4 X T2 •B1 T1 T2 1/32 1/2HH B1 X 3/4 H1 9/32 3/32 The event H1 H2 that heads occurs on both flips has probability P [H1 H2 ] = P [A1 H1 H2 ] + P [B1 H1 H2 ] = 6/32. (1) The probability of H1 is P [H1 ] = P [A1 H1 H2 ] + P [A1 H1 T2 ] + P [B1 H1 H2 ] + P [B1 H1 T2 ] = 1/2. (2) Similarly, P [H2 ] = P [A1 H1 H2 ] + P [A1 T1 H2 ] + P [B1 H1 H2 ] + P [B1 T1 H2 ] = 1/2. (3) Thus P[H1 H2 ] 6= P[H1 ] P[H2 ], implying H1 and H2 are not independent. This result should not be surprising since if the first flip is heads, it is likely that coin B was picked first. In this case, the second flip is less likely to be heads since it becomes more likely that the second coin flipped was coin A. 33 Problem 2.1.8 Solution We start with a tree diagram: 0.999 T + •H 0.99 A 10−4 D XXXX X 0.01 X Ac HH H H 0.001 T− + 0.1 A XX 0.001 XXX T •H X 0.999 T− XX XXX c 0.9 A 1−10−4HH Dc X (a) Here we are asked to calculate the conditional probability P[D|A]. In this part, its simpler to ignore the last branches of the tree that indicate the lab test result. This yields P [D|A] = P [DA] P [AD] = P [A] P [DA] + P [Dc A] (10−4 )(0.99) = (10−4 )(0.99) + (0.1)(1 − 10−4 ) = 9.89 × 10−4 . (1) The probability of the defect D given the arrhythmia A is still quite low because the probability of the defect is so small. (b) Since the heart surgery occurs if and only if the event T + occurs, H and T + are the same event and (from the previous part) P [DT + ] P [H|D] = P T + |D = P [D] 10−4 (0.99)(0.999) = = (0.99)(0.999). 10−4 34 (2) (c) Since the heart surgery occurs if and only if the event T + occurs, H and T + are the same event and (from the previous part) P [Dc T + ] P [H|Dc ] = P T + |Dc = P [Dc ] (1 − 10−4 )(0.1)(0.001) = = 10−4 . 1 − 10−4 (3) (d) Heart surgery occurs with probability P [H] = P [H|D] P [D] + P [H|Dc ] P [Dc ] = (0.99)(0.999)(10−4 ) + (10−4 )(1 − 10−4 ) = 1.99 × 10−4 . (4) (e) Given that heart surgery was performed, the probability the child had no defect is P [Dc |H] = P [Dc H] P [H] (1 − 10−4 )(0.1)(0.001) (0.99)(0.999)(10−4 ) + (10−4 )(1 − 10−4 ) 1 − 10−4 = = 0.5027. 2 − 10−2 − 10−3 + 10−4 = (5) Because the arrythmia is fairly common and the lab test is not fully reliable, roughly half of all the heart surgeries are performed on healthy infants. Problem 2.1.9 Solution (a) The primary difficulty in this problem is translating the words into the correct tree diagram. The tree for this problem is shown below. 35 H1 •H1 1/2 H3 •T1 H2 H3 1/2 1/8 1/2 1/2 H4 •T1 H2 T3 H4 1/16 T3 T4 •T1 H2 T3 T4 1/16 1/2 H2 1/2 1/2 XX XXX 1/2 1/2 1/16 T2 H 3 XX H •T T H H T1 1/2 1/2 Z XXX 4 1 2 3 4 •T T H T 1/16 T 1 2 3 4 4 Z 1/2 Z Z 1/2 Z T3 •T1 T2 T3 1/8 (b) From the tree, P [H3 ] = P [T1 H2 H3 ] + P [T1 T2 H3 H4 ] + P [T1 T2 H3 H4 ] = 1/8 + 1/16 + 1/16 = 1/4. (1) Similarly, P [T3 ] = P [T1 H2 T3 H4 ] + P [T1 H2 T3 T4 ] + P [T1 T2 T3 ] = 1/8 + 1/16 + 1/16 = 1/4. (2) (c) The event that Dagwood must diet is D = (T1 H2 T3 T4 ) ∪ (T1 T2 H3 T4 ) ∪ (T1 T2 T3 ). (3) The probability that Dagwood must diet is P [D] = P [T1 H2 T3 T4 ] + P [T1 T2 H3 T4 ] + P [T1 T2 T3 ] = 1/16 + 1/16 + 1/8 = 1/4. (4) The conditional probability of heads on flip 1 given that Dagwood must diet is P [H1 |D] = P [H1 D] = 0. P [D] (5) Remember, if there was heads on flip 1, then Dagwood always postpones his diet. 36 (d) From part (b), we found that P[H3 ] = 1/4. To check independence, we calculate P [H2 ] = P [T1 H2 H3 ] + P [T1 H2 T3 ] + P [T1 H2 T4 T4 ] = 1/4 P [H2 H3 ] = P [T1 H2 H3 ] = 1/8. (6) Now we find that P [H2 H3 ] = 1/8 6= P [H2 ] P [H3 ] . (7) Hence, H2 and H3 are dependent events. In fact, P[H3 |H2 ] = 1/2 while P[H3 ] = 1/4. The reason for the dependence is that given H2 occurred, then we know there will be a third flip which may result in H3 . That is, knowledge of H2 tells us that the experiment didn’t end after the first flip. Problem 2.1.10 Solution (a) We wish to know what the probability that we find no good photodiodes in n pairs of diodes. Testing each pair of diodes is an independent trial such that with probability p, both diodes of a pair are bad. From Problem 2.1.6, we can easily calculate p. p = P [both diodes are defective] = P [D1 D2 ] = 6/25. (1) The probability of Zn , the probability of zero acceptable diodes out of n pairs of diodes is pn because on each test of a pair of diodes, both must be defective. n n Y 6 (2) P [Zn ] = p = pn = 25 i=1 (b) Another way to phrase this question is to ask how many pairs must we test until P[Zn ] ≤ 0.01. Since P[Zn ] = (6/25)n , we require n 6 ln 0.01 ≤ 0.01 ⇒ n ≥ = 3.23. (3) 25 ln 6/25 Since n must be an integer, n = 4 pairs must be tested. 37 Problem 2.1.11 Solution The starting point is to draw a tree of the experiment. We define the events W that the plant is watered, L that the plant lives, and D that the plant dies. The tree diagram is 0.7 W 0.8 L •W L 0.56 D •W D 0.14 0.2 X XXX X c 0.3 X W c XX 0.1 XXX L •W L 0.03 X 0.9 D •W c D 0.27 It follows that (a) P[L] = P[W L] + P[W c L] = 0.56 + 0.03 = 0.59. (b) P [W c |D] = P [W c D] 0.27 27 = = . P [D] 0.14 + 0.27 41 (1) (c) P[D|W c ] = 0.9. In informal conversation, it can be confusing to distinguish between P[D|W c ] and P[W c |D]; however, they are simple once you draw the tree. Problem 2.1.12 Solution The experiment ends as soon as a fish is caught. The tree resembles p C1 1−p C1c p C2 1−p C2c p C3 1−p C3c … From the tree, P[C1 ] = p and P[C2 ] = (1 − p)p. Finally, a fish is caught on the nth cast if no fish were caught on the previous n − 1 casts. Thus, P [Cn ] = (1 − p)n−1 p. 38 (1) Problem 2.2.1 Solution Technically, a gumball machine has a finite number of gumballs, but the problem description models the drawing of gumballs as sampling from the machine without replacement. This is a reasonable model when the machine has a very large gumball capacity and we have no knowledge beforehand of how many gumballs of each color are in the machine. Under this model, the requested probability is given by the multinomial probability 2 2 2 2 8! 1 1 1 1 P [R2 Y2 G2 B2 ] = 2! 2! 2! 2! 4 4 4 4 8! = 10 ≈ 0.0385. (1) 4 Problem 2.2.2 Solution In this model of a starburst package, the pieces in a package are collected by sampling without replacement from a giant collection of starburst pieces. (a) Each piece is “berry or cherry” with probability p = 1/2. The probability of only berry or cherry pieces is p12 = 1/4096. (b) Each piece is “not cherry” with probability 3/4. The probability all 12 pieces are “not pink” is (3/4)12 = 0.0317. (c) For i = 1, 2, . . . , 6, let Ci denote the event that all 12 pieces are flavor i. Since each piece is flavor i with probability 1/4, P[Ci ] = (1/4)12 . Since Ci and Cj are mutually exclusive, P[F1 ] = P[C1 ∪ C2 ∪ · · · ∪ C4 ] = 4 X P[Ci ] = 4 P[C1 ] = (1/4)11 . i=1 Problem 2.2.3 Solution (a) Let Bi , Li , Oi and Ci denote the events that the ith piece is Berry, Lemon, Orange, and Cherry respectively. Let F1 denote the event that all three pieces 39 draw are the same flavor. Thus, F1 = {S1 S2 S3 , L1 L2 L3 , O1 O2 O3 , C1 C2 C3 } (1) P [F1 ] = P [S1 S2 S3 ] + P [L1 L2 L3 ] + P [O1 O2 O3 ] + P [C1 C2 C3 ] Note that P[L1 L2 L3 ] = 1 3 2 1 · · = 12 11 10 220 and by symmetry, P[F1 ] = 4 P[L1 L2 L3 ] = (2) (3) 1 . 55 (4) (b) Let Di denote the event that the ith piece is a different flavor from all the prior pieces. Let Si denote the event that piece i is the same flavor as a previous piece. A tree for this experiment is 2/11 1 D1 9/11 S2 D2 4/10 S3 6/10 D3 Note that: • P[D1 ] = 1 because the first piece is “different” since there haven’t been any prior pieces. • The second piece is the same as the first piece with probability 2/11 because in the remaining 11 pieces there are 2 pieces that are the same as the first piece. Alternatively, out of 11 pieces left, there are 3 colors each with 3 pieces (that is, 9 pieces out of 11) that are different from the first piece. • Given the first two pieces are different, there are 2 colors, each with 3 pieces (6 pieces) out of 10 remaining pieces that are a different flavor from the first two pieces. Thus P[D3 |D2 D1 ] = 6/10. It follows that the three pieces are different with probability 6 27 9 = . P [D1 D2 D3 ] = 1 11 10 55 40 (5) Problem 2.2.4 Solution (a) Since there are only three pieces of each flavor, we cannot draw four pieces of all the same flavor. Hence P[F1 ] = 0. (b) Let Di denote the event that the ith piece is a different flavor from all the prior pieces. Let Si denote the event that piece i is the same flavor as a previous piece. A tree for this experiment is relatively simple because we stop the experiment as soon as we draw a piece that is the same as a previous piece. The tree is 2/11 1 D1 9/11 S2 D2 4/10 S3 6/9 6/10 D3 S4 3/9 D4 Note that: • P[D1 ] = 1 because the first piece is “different” since there haven’t been any prior pieces. • For the second piece, there are 11 pieces left and 9 of those pieces are different from the first piece drawn. • Given the first two pieces are different, there are 2 colors, each with 3 pieces (6 pieces) out of 10 remaining pieces that are a different flavor from the first two pieces. Thus P[D3 |D2 D1 ] = 6/10. • Finally, given the first three pieces are different flavors, there are 3 pieces remaining that are a different flavor from the pieces previously picked. Thus P[D4 |D3 D2 D1 ] = 3/9. It follows that the three pieces are different with probability 6 3 9 9 = . (1) P [D1 D2 D3 D4 ] = 1 11 10 9 55 An alternate approach to this problem is to assume that each piece is distinguishable, say by numbering the pieces 1, 2, 3 in each flavor. In addition, 41 we define the outcome of the experiment to be a 4-permutation of the 12 distinguishable pieces. Under this model, there are (12)4 = 12! 8! equally likely outcomes in the sample space. The number of outcomes in which all four pieces are different is n4 = 12 · 9 · 6 · 3 since there are 12 choices for the first piece drawn, 9 choices for the second piece from the three remaining flavors, 6 choices for the third piece and three choices for the last piece. Since all outcomes are equally likely, P [F4 ] = n4 12 · 9 · 6 · 3 9 = = (12)4 12 · 11 · 10 · 9 55 (2) (c) The second model of distinguishable starburst pieces makes it easier to solve this last question. In this case, let the outcome of the experiment be the 12 4 = 495 combinations or pieces. In this case, we are ignoring the order in which the pieces were selected. Now we count the number of combinations in which we have two pieces of each of two flavors. We can do this with the following steps: 1. Choose two of the four flavors. 2. Choose 2 out of 3 pieces of one of the two chosen flavors. 3. Choose 2 out of 3 pieces of the other of the two chosen flavors. Let ni equal the number of ways to execute step i. We see that 4 3 3 n1 = = 6, n2 = = 3, n3 = = 3. 2 2 2 (3) There are n1 n2 n3 = 54 possible ways to execute this sequence of steps. Since all combinations are equally likely, P [F2 ] = n1 n2 n3 54 6 = = . 12 495 55 4 (4) Problem 2.2.5 Solution Since there are H = 52 7 equiprobable seven-card hands, each probability is just the number of hands of each type divided by H. 42 (a) Since there are 26 red cards, there are 26 seven-card hands with all red 7 cards. The probability of a seven-card hand of all red cards is 26 26! 45! 7 P [R7 ] = 52 = = 0.0049. (1) 52! 19! 7 (b) There are 12 face cards in a 52 card deck and there are 12 7 seven card hands with all face cards. The probability of drawing only face cards is 12 12! 45! 7 P [F ] = 52 = = 5.92 × 10−6 . (2) 5! 52! 7 (c) There are 6 red face cards (J, Q, K of diamonds and hearts) in a 52 card deck. Thus it is impossible to get a seven-card hand of red face cards: P[R7 F ] = 0. Problem 2.2.6 Solution There are H5 = 52 5 equally likely five-card hands. Dividing the number of hands of a particular type by H will yield the probability of a hand of that type. (a) There are 26 5 five-card hands of all red cards. Thus the probability getting a five-card hand of all red cards is 26 26! 47! 5 = 0.0253. (1) P [R5 ] = 52 = 21! 52! 5 Note that this can be rewritten as P[R5 ] = 26 25 24 23 22 , 52 51 50 49 48 which shows the successive probabilities of receiving a red card. (b) The following sequence of subexperiments will generate all possible “full house” 1. Choose a kind for three-of-a-kind. 2. Choose a kind for two-of-a-kind. 43 3. Choose three of the four cards of the three-of-a-kind kind. 4. Choose two of the four cards of the two-of-a-kind kind. The number of ways of performing subexperiment i is 13 12 4 4 n1 = , n2 = , n3 = , n4 = . (2) 1 1 3 2 Note that n2 = 12 1 because after choosing a three-of-a-kind, there are twelove kinds left from which to choose two-of-a-kind. is The probability of a full house is P [full house] = n1 n2 n3 n4 = 52 5 3, 744 = 0.0014. 2, 598, 960 (3) Problem 2.2.7 Solution There are 25 = 32 different binary codes with 5 bits. The number of codes with exactly 3 zeros equals the number of ways of choosing the bits in which those zeros occur. Therefore there are 53 = 10 codes with exactly 3 zeros. Problem 2.2.8 Solution Since each letter can take on any one of the 4 possible letters in the alphabet, the number of 3 letter words that can be formed is 43 = 64. If we allow each letter to appear only once then we have 4 choices for the first letter and 3 choices for the second and two choices for the third letter. Therefore, there are a total of 4 · 3 · 2 = 24 possible codes. Problem 2.2.9 Solution We can break down the experiment of choosing a starting lineup into a sequence of subexperiments: 1. Choose 1 of the 10 pitchers. There are N1 = 10 1 = 10 ways to do this. 2. Choose 1 of the 15 field players to be the designated hitter (DH). There are N2 = 15 1 = 15 ways to do this. 44 3. Of the remaining 14 field players, choose 8 for the remaining field positions. There are N3 = 14 8 to do this. 4. For the 9 batters (consisting of the 8 field players and the designated hitter), choose a batting lineup. There are N4 = 9! ways to do this. So the total number of different starting lineups when the DH is selected among the field players is 14 N = N1 N2 N3 N4 = (10)(15) 9! = 163,459,296,000. (1) 8 Note that this overestimates the number of combinations the manager must really consider because most field players can play only one or two positions. Although these constraints on the manager reduce the number of possible lineups, it typically makes the manager’s job more difficult. As for the counting, we note that our count did not need to specify the positions played by the field players. Although this is an important consideration for the manager, it is not part of our counting of different lineups. In fact, the 8 nonpitching field players are allowed to switch positions at any time in the field. For example, the shortstop and second baseman could trade positions in the middle of an inning. Although the DH can go play the field, there are some coomplicated rules about this. Here is an excerpt from Major League Baseball Rule 6.10: The Designated Hitter may be used defensively, continuing to bat in the same position in the batting order, but the pitcher must then bat in the place of the substituted defensive player, unless more than one substitution is made, and the manager then must designate their spots in the batting order. If you’re curious, you can find the complete rule on the web. Problem 2.2.10 Solution When the DH can be chosen among all the players, including the pitchers, there are two cases: • The DH is a field player. In this case, the number of possible lineups, NF , is given in Problem 2.2.9. In this case, the designated hitter must be chosen 45 from the 15 field players. We repeat the solution of Problem 2.2.9 here: We can break down the experiment of choosing a starting lineup into a sequence of subexperiments: 1. Choose 1 of the 10 pitchers. There are N1 = 10 1 = 10 ways to do this. 2. Choose 1 of the 15 field players to be the designated hitter (DH). There are N2 = 15 1 = 15 ways to do this. 3. Of the remaining 14 field players, choose 8 for the remaining field positions. There are N3 = 14 8 to do this. 4. For the 9 batters (consisting of the 8 field players and the designated hitter), choose a batting lineup. There are N4 = 9! ways to do this. So the total number of different starting lineups when the DH is selected among the field players is 14 N = N1 N2 N3 N4 = (10)(15) 9! = 163,459,296,000. (1) 8 • The DH is a pitcher. In this case, there are 10 choices for the pitcher, 10 choices for the DH among the pitchers (including the pitcher batting for himself), 15 8 choices for the field players, and 9! ways of ordering the batters into a lineup. The number of possible lineups is 15 0 N = (10)(10) 9! = 233, 513, 280, 000. (2) 8 The total number of ways of choosing a lineup is N + N 0 = 396,972,576,000. Problem 2.2.11 Solution (a) This is just the multinomial probability 19 19 2 40 19 19 2 P [A] = 19, 19, 2 40 40 40 19 19 2 40! 19 19 2 = . 19!19!2! 40 40 40 46 (1) (b) Each spin is either green (with probability 19/40) or not (with probability 21/40). If we call landing on greeen a success, then G19 is the probability of 19 successes in 40 trials. Thus 19 21 21 40 19 . (2) P [G19 ] = 40 40 19 (c) If you bet on red, the probability you win is 19/40. If you bet green, the probability that you win is 19/40. If you first make a random choice to bet red or green, (say by flipping a coin), the probability you win is still p = 19/40. Problem 2.2.12 Solution (a) We can find the number of valid starting lineups by noticing that the swingman presents three situations: (1) the swingman plays guard, (2) the swingman plays forward, and (3) the swingman doesn’t play. The first situation is when the swingman can be chosen to play the guard position, and the second where the swingman can only be chosen to play the forward position. Let Ni denote the number of lineups corresponding to case i. Then we can write the total number of lineups as N1 + N2 + N3 . In the first situation, we have to choose 1 out of 3 centers, 2 out of 4 forwards, and 1 out of 4 guards so that 3 4 4 N1 = = 72. (1) 1 2 1 In the second case, we need to choose 1 out of 3 centers, 1 out of 4 forwards and 2 out of 4 guards, yielding 3 4 4 N2 = = 72. (2) 1 1 2 Finally, with the swingman on the bench, we choose 1 out of 3 centers, 2 out of 4 forward, and 2 out of four guards. This implies 3 4 4 N3 = = 108, (3) 1 2 2 and the total number of lineups is N1 + N2 + N3 = 252. 47 Problem 2.2.13 Solution What our design must specify is the number of boxes on the ticket, and the number of specially marked boxes. Suppose each ticket has n boxes and 5 + k specially marked boxes. Note that when k > 0, a winning ticket will still have k unscratched boxes with the special mark. A ticket is a winner if each time a box is scratched off, the box has the special mark. Assuming the boxes are scratched off randomly, the first box scratched off has the mark with probability (5 + k)/n since there are 5 + k marked boxes out of n boxes. Moreover, if the first scratched box has the mark, then there are 4 + k marked boxes out of n − 1 remaining boxes. Continuing this argument, the probability that a ticket is a winner is p= 5+k4+k 3+k 2+k 1+k (k + 5)!(n − 5)! = . n n−1n−2n−3n−4 k!n! (1) By careful choice of n and k, we can choose p close to 0.01. For example, n 9 11 14 17 k 0 1 2 3 p 0.0079 0.012 0.0105 0.0090 (2) A gamecard with N = 14 boxes and 5 + k = 7 shaded boxes would be quite reasonable. Problem 2.3.1 Solution (a) Since the probability of a zero is 0.8, we can express the probability of the code word 00111 as 2 occurrences of a 0 and three occurrences of a 1. Therefore P [00111] = (0.8)2 (0.2)3 = 0.00512. (b) The probability that a code word has exactly three 1’s is 5 P [three 1’s] = (0.8)2 (0.2)3 = 0.0512. 3 48 (1) (2) Problem 2.3.2 Solution Given that the probability that the Celtics win a single championship in any given year is 0.32, we can find the probability that they win 8 straight NBA championships. P [8 straight championships] = (0.32)8 = 0.00011. The probability that they win 10 titles in 11 years is 11 P [10 titles in 11 years] = (.32)10 (.68) = 0.00084. 10 (1) (2) The probability of each of these events is less than 1 in 1000! Given that these events took place in the relatively short fifty year history of the NBA, it should seem that these probabilities should be much higher. What the model overlooks is that the sequence of 10 titles in 11 years started when Bill Russell joined the Celtics. In the years with Russell (and a strong supporting cast) the probability of a championship was much higher. Problem 2.3.3 Solution We know that the probability of a green and red light is 7/16, and that of a yellow light is 1/8. Since there are always 5 lights, G, Y , and R obey the multinomial probability law: 2 2 5! 7 1 7 P [G = 2, Y = 1, R = 2] = . (1) 2!1!2! 16 8 16 The probability that the number of green lights equals the number of red lights P [G = R] = P [G = 1, R = 1, Y = 3] + P [G = 2, R = 2, Y = 1] + P [G = 0, R = 0, Y = 5] 3 2 2 5! 7 7 1 7 7 1 5! = + 1!1!3! 16 16 8 2!1!2! 16 16 8 5 5! 1 + 0!0!5! 8 ≈ 0.1449. 49 (2) Problem 2.3.4 Solution For the team with the homecourt advantage, let Wi and Li denote whether game i was a win or a loss. Because games 1 and 3 are home games and game 2 is an away game, the tree is 1−p W2 •W1 W2 p W1 X XXX X 1−p X L1 p 1−p HH H p(1−p) p W3 •W1 L2 W3 L2 1−p W2 XX p p3 L3 •W1 L2 L3 p2 (1−p) W •L W W p(1−p)2 3 1 2 3 XX X 1−p X L3 •L1 W2 L3 (1−p)3 HH p H L2 •L1 L2 p(1−p) The probability that the team with the home court advantage wins is P [H] = P [W1 W2 ] + P [W1 L2 W3 ] + P [L1 W2 W3 ] = p(1 − p) + p3 + p(1 − p)2 . (1) Note that P[H] ≤ p for 1/2 ≤ p ≤ 1. Since the team with the home court advantage would win a 1 game playoff with probability p, the home court team is less likely to win a three game series than a 1 game playoff! Problem 2.3.5 Solution (a) There are 3 group 1 kickers and 6 group 2 kickers. Using Gi to denote that a group i kicker was chosen, we have P [G1 ] = 1/3, P [G2 ] = 2/3. (1) In addition, the problem statement tells us that P [K|G1 ] = 1/2, P [K|G2 ] = 1/3. (2) Combining these facts using the Law of Total Probability yields P [K] = P [K|G1 ] P [G1 ] + P [K|G2 ] P [G2 ] = (1/2)(1/3) + (1/3)(2/3) = 7/18. 50 (3) (b) To solve this part, we need to identify the groups from which the first and second kicker were chosen. Let ci indicate whether a kicker was chosen from group i and let Cij indicate that the first kicker was chosen from group i and the second kicker from group j. The experiment to choose the kickers is described by the sample tree: 2/8 c1 •C11 3/9 c1 c2 •C12 6/8 XXX XX 3/8 c1 •C21 6/9 X c2 XX XXX X c 2 •C22 5/8 1/12 1/4 1/4 5/12 Since a kicker from group 1 makes a kick with probability 1/2 while a kicker from group 2 makes a kick with probability 1/3, P [K1 K2 |C11 ] = (1/2)2 , P [K1 K2 |C12 ] = (1/2)(1/3), 2 P [K1 K2 |C21 ] = (1/3)(1/2), P [K1 K2 |C22 ] = (1/3) . (4) (5) By the law of total probability, P [K1 K2 ] = P [K1 K2 |C11 ] P [C11 ] + P [K1 K2 |C12 ] P [C12 ] + P [K1 K2 |C21 ] P [C21 ] + P [K1 K2 |C22 ] P [C22 ] 1 1 11 11 1 5 = + + + = 15/96. 4 12 6 4 6 4 9 12 (6) It should be apparent that P[K1 ] = P[K] from part (a). Symmetry should also make it clear that P[K1 ] = P[K2 ] since for any ordering of two kickers, the reverse ordering is equally likely. If this is not clear, we derive this result by calculating P[K2 |Cij ] and using the law of total probability to calculate P[K2 ]. P [K2 |C11 ] = 1/2, P [K2 |C12 ] = 1/3, P [K2 |C21 ] = 1/2, P [K2 |C22 ] = 1/3. 51 (7) (8) By the law of total probability, P [K2 ] = P [K2 |C11 ] P [C11 ] + P [K2 |C12 ] P [C12 ] + P [K2 |C21 ] P [C21 ] + P [K2 |C22 ] P [C22 ] 1 1 11 11 1 5 7 = + + + = . 2 12 3 4 2 4 3 12 18 (9) We observe that K1 and K2 are not independent since 15 P [K1 K2 ] = 6= 96 7 18 2 = P [K1 ] P [K2 ] . (10) Note that 15/96 and (7/18)2 are close but not exactly the same. The reason K1 and K2 are dependent is that if the first kicker is successful, then it is more likely that kicker is from group 1. This makes it more likely that the second kicker is from group 2 and is thus more likely to miss. (c) Once a kicker is chosen, each of the 10 field goals is an independent trial. If the kicker is from group 1, then the success probability is 1/2. If the kicker is from group 2, the success probability is 1/3. Out of 10 kicks, there are 5 misses iff there are 5 successful kicks. Given the type of kicker chosen, the probability of 5 misses is 10 10 5 5 P [M |G1 ] = (1/2) (1/2) , P [M |G2 ] = (1/3)5 (2/3)5 . (11) 5 5 We use the Law of Total Probability to find P [M ] = P [M |G1 ] P [G1 ] + P [M |G2 ] P [G2 ] 10 = (1/3)(1/2)10 + (2/3)(1/3)5 (2/3)5 . 5 (12) Problem 2.4.1 Solution From the problem statement, we can conclude that the device components are configured in the following way. 52 W1 W3 W2 W5 W4 W6 To find the probability that the device works, we replace series devices 1, 2, and 3, and parallel devices 5 and 6 each with a single device labeled with the probability that it works. In particular, P [W1 W2 W3 ] = (1 − q)3 , (1) P [W5 ∪ W6 ] = 1 − P [W5c W6c ] = 1 − q 2 . (2) This yields a composite device of the form (1-q) 3 2 1-q 1-q The probability P[W 0 ] that the two devices in parallel work is 1 minus the probability that neither works: P W 0 = 1 − q(1 − (1 − q)3 ). (3) Finally, for the device to work, both composite device in series must work. Thus, the probability the device works is P [W ] = [1 − q(1 − (1 − q)3 )][1 − q 2 ]. (4) Problem 2.4.2 Solution Suppose that the transmitted bit was a 1. We can view each repeated transmission as an independent trial. We call each repeated bit the receiver decodes as 1 a success. Using Sk,5 to denote the event of k successes in the five trials, then the probability k 1’s are decoded at the receiver is 5 k P [Sk,5 ] = p (1 − p)5−k , k = 0, 1, . . . , 5. (1) k 53 The probability a bit is decoded correctly is P [C] = P [S5,5 ] + P [S4,5 ] = p5 + 5p4 (1 − p) = 0.91854. (2) The probability a deletion occurs is P [D] = P [S3,5 ] + P [S2,5 ] = 10p3 (1 − p)2 + 10p2 (1 − p)3 = 0.081. (3) The probability of an error is P [E] = P [S1,5 ] + P [S0,5 ] = 5p(1 − p)4 + (1 − p)5 = 0.00046. (4) Note that if a 0 is transmitted, then 0 is sent five times and we call decoding a 0 a success. You should convince yourself that this a symmetric situation with the same deletion and error probabilities. Introducing deletions reduces the probability of an error by roughly a factor of 20. However, the probability of successfull decoding is also reduced. Problem 2.4.3 Solution Note that each digit 0 through 9 is mapped to the 4 bit binary representation of the digit. That is, 0 corresponds to 0000, 1 to 0001, up to 9 which corresponds to 1001. Of course, the 4 bit binary numbers corresponding to numbers 10 through 15 go unused, however this is unimportant to our problem. the 10 digit number results in the transmission of 40 bits. For each bit, an independent trial determines whether the bit was correct, a deletion, or an error. In Problem 2.4.2, we found the probabilities of these events to be P [C] = γ = 0.91854, P [D] = δ = 0.081, P [E] = = 0.00046. (1) Since each of the 40 bit transmissions is an independent trial, the joint probability of c correct bits, d deletions, and e erasures has the multinomial probability ( 40! c d e γ δ c + d + e = 40; c, d, e ≥ 0, P [C = c, D = d, E = d] = c!d!e! (2) 0 otherwise. 54 Problem 2.4.4 Solution From the statement of Problem 2.4.1, the configuration of device components is W1 W2 W3 W5 W4 W6 By symmetry, note that the reliability of the system is the same whether we replace component 1, component 2, or component 3. Similarly, the reliability is the same whether we replace component 5 or component 6. Thus we consider the following cases: I Replace component 1 In this case q P [W1 W2 W3 ] = (1 − )(1 − q)2 , 2 P [W4 ] = 1 − q, 2 P [W5 ∪ W6 ] = 1 − q . (1) (2) (3) This implies P [W1 W2 W3 ∪ W4 ] = 1 − (1 − P [W1 W2 W3 ])(1 − P [W4 ]) q2 (5 − 4q + q 2 ). 2 In this case, the probability the system works is =1− P [WI ] = P [W1 W2 W3 ∪ W4 ] P [W5 ∪ W6 ] q2 2 = 1 − (5 − 4q + q ) (1 − q 2 ). 2 (4) (5) II Replace component 4 In this case, P [W1 W2 W3 ] = (1 − q)3 , q P [W4 ] = 1 − , 2 P [W5 ∪ W6 ] = 1 − q 2 . 55 (6) (7) (8) This implies P [W1 W2 W3 ∪ W4 ] = 1 − (1 − P [W1 W2 W3 ])(1 − P [W4 ]) q q = 1 − + (1 − q)3 . 2 2 (9) In this case, the probability the system works is P [WII ] = P [W1 W2 W3 ∪ W4 ] P [W5 ∪ W6 ] i h q q = 1 − + (1 − q)3 (1 − q 2 ). 2 2 (10) III Replace component 5 In this case, P [W1 W2 W3 ] = (1 − q)3 , P [W4 ] = 1 − q, P [W5 ∪ W6 ] = 1 − q2 2 . (11) (12) (13) This implies P [W1 W2 W3 ∪ W4 ] = 1 − (1 − P [W1 W2 W3 ])(1 − P [W4 ]) = (1 − q) 1 + q(1 − q)2 . (14) In this case, the probability the system works is P [WIII ] = P [W1 W2 W3 ∪ W4 ] P [W5 ∪ W6 ] q2 1 + q(1 − q)2 . = (1 − q) 1 − 2 (15) From these expressions, its hard to tell which substitution creates the most reliable circuit. First, we observe that P[WII ] > P[WI ] if and only if 1− q2 q q + (1 − q)3 > 1 − (5 − 4q + q 2 ). 2 2 2 (16) Some algebra will show that P[WII ] > P[WI ] if and only if q 2 P[WIII ] for all values of 0 ≤ q ≤ 1. Thus the best policy is to replace component 4. 56 Problem 2.5.1 Solution Rather than just solve the problem for 50 trials, we can write a function that generates vectors C and H for an arbitrary number of trials n. The code for this task is function [C,H]=twocoin(n); C=ceil(2*rand(n,1)); P=1-(C/4); H=(rand(n,1)< P); The first line produces the n × 1 vector C such that C(i) indicates whether coin 1 or coin 2 is chosen for trial i. Next, we generate the vector P such that P(i)=0.75 if C(i)=1; otherwise, if C(i)=2, then P(i)=0.5. As a result, H(i) is the simulated result of a coin flip with heads, corresponding to H(i)=1, occurring with probability P(i). Problem 2.5.2 Solution Rather than just solve the problem for 100 trials, we can write a function that generates n packets for an arbitrary number of trials n. The code for this task is function C=bit100(n); % n is the number of 100 bit packets sent B=floor(2*rand(n,100)); P=0.03-0.02*B; E=(rand(n,100)< P); C=sum((sum(E,2)q; D=(W(:,1)&W(:,2)&W(:,3))|W(:,4); D=D&(W(:,5)|W(:,6)); N=sum(D); The n × 6 matrix W is a logical matrix such that W(i,j)=1 if component j of device i works properly. Because W is a logical matrix, we can use the Matlab logical operators | and & to implement the logic requirements for a working device. By applying these logical operators to the n × 1 columns of W, we simulate the test of n circuits. Note that D(i)=1 if device i works. Otherwise, D(i)=0. Lastly, we count the number N of working devices. The following code snippet produces ten sample runs, where each sample run tests n=100 devices for q = 0.2. >> for n=1:10, w(n)=reliable6(100,0.2); end >> w w = 82 87 87 92 91 85 85 83 90 >> 89 As we see, the number of working devices is typically around 85 out of 100. Solving Problem 2.4.1, will show that the probability the device works is actually 0.8663. Problem 2.5.4 Solution The code 58 function n=countequal(x,y) %Usage: n=countequal(x,y) %n(j)= # elements of x = y(j) [MX,MY]=ndgrid(x,y); %each column of MX = x %each row of MY = y n=(sum((MX==MY),1))’; for countequal is quite short (just two lines excluding comments) but needs some explanation. The key is in the operation [MX,MY]=ndgrid(x,y). The Matlab built-in function ndgrid facilitates plotting a function g(x, y) as a surface over the x, y plane.The x, y plane is represented by a grid of all pairs of points x(i), y(j). When x has n elements, and y has m elements, ndgrid(x,y) creates a grid (an n × m array) of all possible pairs [x(i) y(j)]. This grid is represented by two separate n × m matrices: MX and MY which indicate the x and y values at each grid point. Mathematically, MX(i,j) = x(i), MY(i,j)=y(j). Next, C=(MX==MY) is an n × m array such that C(i,j)=1 if x(i)=y(j); otherwise C(i,j)=0. That is, the jth column of C indicates indicates which elements of x equal y(j). Lastly, we sum along each column j to count number of elements of x equal to y(j). That is, we sum along column j to count the number of occurrences (in x) of y(j). Problem 2.5.5 Solution For arbitrary number of trials n and failure probability q, the following functions evaluates replacing each of the six components by an ultrareliable device. 59 function N=ultrareliable6(n,q); % n is the number of 6 component devices %N is the number of working devices for r=1:6, W=rand(n,6)>q; R=rand(n,1)>(q/2); W(:,r)=R; D=(W(:,1)&W(:,2)&W(:,3))|W(:,4); D=D&(W(:,5)|W(:,6)); N(r)=sum(D); end This code is based on the code for the solution of Problem 2.5.3. The n × 6 matrix W is a logical matrix such that W(i,j)=1 if component j of device i works properly. Because W is a logical matrix, we can use the Matlab logical operators | and & to implement the logic requirements for a working device. By applying these logical opeators to the n × 1 columns of W, we simulate the test of n circuits. Note that D(i)=1 if device i works. Otherwise, D(i)=0. Note that in the code, we first generate the matrix W such that each component has failure probability q. To simulate the replacement of the jth device by the ultrareliable version by replacing the jth column of W by the column vector R in which a device has failure probability q/2. Lastly, for each column replacement, we count the number N of working devices. A sample run for n = 100 trials and q = 0.2 yielded these results: >> ultrareliable6(100,0.2) ans = 93 89 91 92 90 93 From the above, we see, for example, that replacing the third component with an ultrareliable component resulted in 91 working devices. The results are fairly inconclusive in that replacing devices 1, 2, or 3 should yield the same probability of device failure. If we experiment with n = 10, 000 runs, the results are more definitive: >> ultrareliable6(10000,0.2) ans = 8738 8762 8806 >> >> ultrareliable6(10000,0.2) ans = 8771 8795 8806 >> 60 9135 8800 8796 9178 8886 8875 In both cases, it is clear that replacing component 4 maximizes the device reliability. The somewhat complicated solution of Problem 2.4.4 will confirm this observation. 61