U.C. Berkeley — CS70: Discrete Mathematics and Probability Problem Set 11Lecturers: Umesh Vazirani & Christos H. Papadimitriou Due November 20, 2006 at 4:00pmProblem Set 111. Machi ne failuresTwo faulty machines, M1and M2, are repea tedly run synchronously in parallel (i.e., both machinesexecute one run, then both execute a second run, and so on). On each run, M1fails with probability p1and M2with probability p2, all failure events being independent. Let the random variables X1, X2denote the number of runs until the first failure of M1, M2respectively; thus X1, X2have geometricdistributions with parameters p1, p2respectively.Let X = min{X1, X2} denote the number of runs until the first failure of either machine. Show thatX also has a geometric distribution, with parameter p1+ p2− p1p2.2. Geometric DistributionJames Bond is imprisoned in a cell from which there are three possible ways to escape: an air-conditioning duct, a sewer pipe and the door (which is unlocked). The air-conditioning duct leadshim on a two-hour trip whereupon he falls through a trap door onto his head, much to the amusementof his captors . The sewer pipe is similar but takes five hours to traverse. Each fall produces temporaryamnesia and he is returned to the cell immediately after each fall. Assume that he always immediatelychooses one of the three exits from the cell with probability13. On the average, how long does it takebefo re he realizes that the door is unlocke d and escapes?3. Po isson Distribution A textbook has on average one misprint per page. What is the chance thatyou see exac tly 4 misprints on page 1? What is the chance that you see exactly 4 misprints on somepage in the textbook of 250 pages?4. Normal DistributionThe average life of a certain type of engine is 10 years, with a standard deviation of 3.5 years. Themanufacturer repla c e s free all engines that fail while under guarantee. If he is willing to re place only2% of the engines , how long a guarantee should he offer? Assume a no rmal distribution.5. Multiple ChoiceA multiple-choice quiz has 1 00 questions each with four possible answers of which only one is correct.What is the proba bility that sheer gusswork yields between 10 and 30 correct a ns wers for the 40 of the100 problems about which the student has no knowledge?6. Lo ad balancing in actionThis problem as ks you to try out in practice the load balancing scheme discussed in class and tocompare the results with the theory. It will als o lead you on to try out a more sophistica ted strategythat (we hope!) works even better.(a) You will find on the we b page a Scheme program (and a java program if you prefer) that simulatesthe load balancing experiment (i.e., balls-and-bins with n balls and n bins). The function calledbb on input n will run the experiment with n balls and n bins, and output a single numbe r whichis the maximum load.Perform 20 simulations with n = 1000 and 20 simulations with n = 106, and draw up a histogramof the maximum loads you observe. How well do these values correspond to those that we derivedin class? Report the sample mean and variance of your trials.(b) Now consider the following alternative scheme, which uses a minimal amount of c ommunication:jobs arrive in sequence as before, but instead of simply choosing a single processor at ra ndom,each job now chooses two processors at random, inspects their cur rent loads, and goes to the lessheavily loaded of the two. (If both loads are the same, the job chooses one of the two arbitrarily.)1Modify the program to implement this str ategy. Again, perform 2 0 simulations with n = 1000and n = 106and tabulate the maximum loads you observe. Are you surprised by your results?What are the sample mean and variance this time?(c) [Extra credit] Would you expe c t a similarly dramatic effect if the jobs were allowed three choicesrather than two? Modify your program again and se e what happens.7. Non-transitive Dice (Extra Credit)Consider three six-sided dice A, B, and C, whose sides are la beled with any numbers of your cho ice.Say that A beats B if P [A shows a numb e r greater than B] > 1/2.Choose numbers to label each of the sides of A, B and C such that A beats B, B beats C, and C beatsA. Try to create your la bels to maximize the probabilties in each case.Notice that armed with a set of three non-transitive dice, you could challenge s omeone to a game ofdice, where to ensure fairness, you would give your opponent fir st choice o f die to play
View Full Document
Unlocking...