U.C. Berkeley — CS70: Discrete Mathematics and Probability Problem Set 9Lecturers: Umesh Vazirani & Christos H. Papadimitriou Due October 27, 2006 at 4:00pmProblem Set 91. MarblesBox A contains 2 black and 5 white marbles, and box B contains 1 black and 4 white marbles. A boxis s elected at random, and a marble is drawn at random from the se lected box.• What is the probability that the marble is black?• Given that the marble is white, what is the probability that it c ame from the b ox A?2. Money bagsI have a bag containing either a $1 or $5 bill (with equal probability assigned to both possibilities). Ithen add a $1 bill to the bag, so it now contains two bills. The bag is shaken, and you draw out a $1bill. If a second student draws the remaining bill from the bag, what is the chance that it is a $1 bill?Show your work.3. Happy families(a) Consider a collection of families, each of which has exactly two children. Each of the four possiblecombinations of boys and girls, bg, gb, bb, gg, occurs with the same frequency. A family is chosenuniformly at random, and we are told that it contains at least one boy. What is the (conditional)probability that the other child is a boy? Justify your answer with a precise calculation.(b) On the same probability space as in part (a), let A be the event that the chosen family has childrenof both sexes, and B the event that the family has at least one girl. Are the events A and Bindependent? Justify your answer carefully.(c) Consider now the proba bility space of families with three children, with each of the eight possiblecombinations of boys and girls equally likely. Define the events A and B as in part (b). Are theseevents indepe ndent? Again, justify your answer carefully.4. Triply-repeated onesWe say that a string of bits has k triply-repeated ones if ther e are k positions where three consecutive1’s appear in a row. For exa mple, the string 011100111110 has four triply-r epeated ones.What is the ex pected number of triply-repe ated ones in a random n-bit string, when n ≥ 2 and alln-bit strings are equally likely? Justify your answer.5. Chopping up DNA(a) In a certain biological experiment, a piece of DNA consisting of a linea r sequence (or string) of4001 nucleotides is subjected to bombardment by various enzymes. The effect o f the bombardmentis to randomly cut the string between pair s of adjace nt nucleotides: each of the 4000 possible cutsoccurs independently and with probability1500. What is the expected number of pieces into whichthe string is cut? Justify your calculation.[Hint: Use linearity of expectation! If you do it this way, you can avoid a huge amount of messycalculation. Remembe r to justify the steps in your argument; i.e., do not a ppeal to “commonsense.”](b) Suppose that the cuts are no longer independent, but highly correlated, so that when a cut occursin a particular place other cuts clo se by are much more likely. The probability of each individualcut remains1500. Does the expected number of pieces increase, decrease , or stay the same? Justifyyour answer with a precise explanation.16. How to beat the heatIt’s a hot summer day in the Central Valley. Thr ee children Alice, Bob, and Carlo s are engaged in athree-way duel with water balloons. They start by drawing lots to determine who throws first, second,and third, then take their places at the corners of an equilateral triangle. They a gree to throw singlewater balloons in turn and continue in the same cyclic order until two of them have been soaked. Eachplayer may throw at any other in his or her turn. You should assume the following: all the childrenhave an essentially infinite supply of ammunition; a water balloo n explodes on contact, drenching itstarget (who then leaves the game); when a water balloon misses its target, it e xplodes far enough awaynot to get anyone wet.All three know that Alice always hits her target, Bob is 75% accurate, and Car los is 50% accurate.Of course, if for some reason any of them deliberately decides to miss they can do so with certainty.Suppose that Car los has drawn the first shot, and Bob second. What is Carlos’s best strategy, andwhat is the chance that he comes out the eventual winner? What a bout Alice?7. Extra Creditn points are uniformly and independently picked from the unit interval [0, 1]. This divides the intervalinto n + 1 subintervals. What is the expected length of the leftmost interval (i.e. the one containing0)?Suppose we select one of the n + 1 subintervals at random as follows: pick a point x in the unit interval[0, 1] uniformly at random, and select the subinterval that contains x (think of this as pointing at theline at random and selecting the s ubinterval that you are po inting at). What is the expected length ofthe chosen
View Full Document
Unlocking...