U.C. Berkeley – CS70: Discrete Mathematics for Computer Science Problem Set 12Lecturer: Luca Trevisan Due May 8, 2007 at 2:30pmProblem Set 121. Saving the Spotted FoobarAs you may’ve heard, there’s an endangered population of the rar e and e lus ive spotted foobars livingin the tunnels deep under Evans Hall. They only venture outside to eat through the grate outsideEvans, usually in the middle of the night.To comply with new safety laws, the campus plans to put in a new grating, which has 5-inch-wideholes. You’ve been hired by the Save the Spotted Foobar Coalition to ensure the new grating doesn’tseriously impact the spotted foobars’ feeding.According to the latest zoology studies, the spotted foobars in the current population are, on average,skinny enough to fit through a hole of diameter 1.9 in, with a variance of 2.3 in2.(a) Out of the bounds we’ve shown in the CS70, use the strongest one you can to obtain a definitebound on these probabilities:i. The probability of a random spotted foobar fitting through the g rating to go out to fo rage.ii. The probability that a random spotted foobar will drop through the new grating no ma tterhow it o rients itself, assuming that the zoolog ists have measured their longest dimension tobe 3.1 inches on average, with a variance of 4.3 in2. (After all, it’s dark, and the spottedfo obars might be trying to get back in in a rush if a predator appears.)iii. The probability that, out of the curr ent population of 343 spotted foobars, no mo re than 20starve to death due to not being able to get outside. (The spotted foobars don’t share theirfo od — and there are no vending machines in the steam tunnels.)(b) You appeal to PPCS to use a wider grating: s ince the spotted foobars are a lmost extinct as is,losing 20 more would be terrible. The p e ople in charge tell you, “ tha t’s ridiculous, the previousgrate had holes 2.4 inches wide, how could we make it worse by putting in one with wider holes?”Using the data given, can you definitively prove that they’re lying a bout the s iz e of the previousgrate? Assume any spotted foobar that couldn’t squeeze through the previous grate at all would’vestarved to death before the statistics above were collected.2. Me ssing with ChernoffOne night, word spreads in the 2nd floor labs that there are 4 dozen free donuts upstairs. The 25 peoplein 271 are working on a looming midnight 61C deadline, and are each 30% likely to stay put a nd ignorethe donuts. The 40 pe ople in the o ther labs aren’t as stre ssed, but are each 10% likely to have alreadyfilled up on pizza (per midterm 2). Assume that everyone makes their decision independently.(a) Use the Chernoff b ound from class to bound the probability that there’ll b e enough donuts foreveryone (assuming, unrea lis tically, that no one takes seconds).(b) We derived the Chernoff bound by a pplying the Markov b ound to αX1+...+Xn. What happens inthis problem if you use the same pro c e dure but start by applying the Markov bound to 2X1+...+Xn?3. To infinities, and beyondShow whether each of the following s e ts is finite, countably infinite, or uncountable:(a) The set of all primes.(b) The set of all real-valued random variables on a finite sample space.(c) The set of a ll integer-valued random variables defined on the sample space Ω of positive integers ,with Pr[ω] = 1/2ω1(d) The set of all integer -valued random variables on a finite sample space.(e) The set of all possible functions from Z97to Z97.(f) The set of all
View Full Document
Unlocking...