Mathematics > QUESTIONS & ANSWERS > University of California, Berkeley - CS 70 HW 12. CS 70 Discrete Mathematics and Probability Theory (All)

CS 70 Discrete Mathematics and Probability Theory Fall 2015 Jean Walrand HW 12 Due Wednesday November 18 at 10PM Please note that understanding all questions on this homework is necessary to prepar... e for your midterm 3. Since midterm 3 is on November 16, solution will not be provided before the midterm. Please reach out to your TAs for help or ask questions on Piazza. 1. Geometric Distribution Two faulty machines, M1 and M2, are repeatedly run synchronously in parallel (i.e., both machines execute one run, then both execute a second run, and so on). On each run, M1 fails with probability p1 and M2 fails with probability p2, all failure events being independent. Let the random variables X1, X2 denote the number of runs until the first failure of M1, M2 respectively; thus X1, X2 have geometric distributions with parameters p1, p2 respectively. Let X denote the number of runs until the first failure of either machine. Show that X also has a geometric distribution, with parameter p1 + p2 - p1p2. 2. Poisson Distribution (a) It is fairly reasonable to model the number of customers entering a shop during a particular hour as a Poisson random variable. Assume that this Poisson random variable X has mean l. Suppose that whenever a customer enters the shop they leave the shop without buying anything with probability p. Assume that customers act independently, i.e. you can assume that they each simply flip a biased coin to decide whether to buy anything at all. Let us denote the number of customers that buy something as Y and the number of them that do not buy anything as Z (so X = Y + Z). What is the probability that Y = k for a given k? How about Pr[Z = k]? Prove that Y and Z are Poisson random variables themselves. Hint: you can use the identity ex = ∑¥ k=0 xkk!. (b) Assume that you were given two independent Poisson random variables X1;X2. Assume that the first has mean l1 and the second has mean l2. Prove that X1 + X2 is a Poisson random variable with mean l1 + l2. 3. Variance This problem will give you practice using the “standard method” to compute the variance of a sum of random variables that are not pairwise independent (so you cannot use “linearity” of variance). If you don’t even know what is “linearity” of variance, read the lecture note and slides first. (a) A building has n floors numbered 1;2;:::;n, plus a ground floor G. At the ground floor, m people get on the elevator together, and each gets off at a uniformly random one of the n floors (independently of everybody else). What is the variance of the number of floors the elevator does not stop at? (In fact, the variance of the number of floors the elevator does stop at must be the same (do you see why?) but the former is a little easier to compute.) (b) A group of three friends has n books they would all like to read. Each friend (independently of the other two) picks a random permutation of the books and reads them in that order, one book per week (for n consecutive weeks). Let X be the number of weeks in which all three friends are reading the same book. Compute VarX. 4. Coupon Collection Suppose you take a deck of n cards and repeatedly perform the following step: take the current top card and put it back in the deck at a uniformly random position. (I.e., the probability that the card is placed in any of the n possible positions in the deck — including back on top — is 1=n.) Consider the card that starts off on the bottom of the deck. What is the expected number of steps until this card rises to the top of the deck? (Hint: Let T be the number of steps until the card rises to the top. We have T = Tn + Tn-1 + ••• + T2, where the random variable Ti is the number of steps until the bottom card rises from position i to position i - 1. Thus, for example, Tn is the number of steps until the bottom card rises off the bottom of the deck, and T2 is the number of steps until the bottom card rises from second position to top position. What is the distribution of Ti? 5. Markov’s Inequality and Chebyshev’s Inequality A random variable X has variance VarX = 9 and expectation E(X) = 2. Furthermore, the value of X is never greater than 10. Given this information, provide either a proof or a counterexample for the following statements. 6. Umbrella Store Bob has a store that sells umbrellas. The number of umbrellas that Bob sells on a rainy day is a random variable Y with mean 25 and standard deviation p105. But if it is a clear day, Bob doesn’t sell any umbrellas at all. The weather forecast for tomorrow says it will rain with probability 15. Let Z be the number of umbrellas that Bob sells tomorrow. (a) Let X be an indicator random variable that it will rain tomorrow. Write Z in terms of X and Y. (b) What is the mean and standard deviation of Z? (c) Use Chebyshev’s inequality to bound the probability that Bob sells at least 25 umbrellas tomorrow. [Show More]

Last updated: 1 year ago

Preview 1 out of 7 pages

Connected school, study & course

**About the document**

Uploaded On

Apr 16, 2021

Number of pages

7

Written in

This document has been written for:

Uploaded

Apr 16, 2021

Downloads

0

Views

39

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We're available through e-mail, Twitter, Facebook, and live chat.

FAQ

Questions? Leave a message!

Copyright © Browsegrades · High quality services·