Monta Vista High - CS 70 hw12- Solutions. CS 70 Discrete Mathematics and Probability Theory Spring 2020. Questions and Answers. All solutions Worked.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Spring 2020 Course Notes HW 12 1 Buffon’s Needle on a Grid In this problem, we will consider Buffon’s Needle, but with a catch. We now drop a n... eedle at random onto a large grid, and example of which is shown below. The length of the needle is 1, and the space between the grid lines is 1 as well. Recall from class that a random throw means that the position of the center of the needle and its orientation are independent and uniformly distributed. (a) Given that the angle between the needle and the horizontal lines is q, what is the probability that the needle does not intersect any grid lines? Justify your answer. (b) Continue part (a) to find the probability that the needle, when dropped onto the grid at random (with the angle chosen uniformly at random), intersects a grid line. Justify your answer. Hint: You may use the fact that sinq cosq = 12 sin(2q) without proof. (c) Let X be the number of times the needle intersects a gridline (so, in the example shown above, X = 2). Find E[X]. Justify your answer. Hint: Can you do this without using your answer from part (b)? (d) Combine the previous parts to figure out the probability that X = 1, i.e. the needle will only intersects one gridline. Justify your answer. 2 Useful Uniforms Let X be a continuous random variable whose image is all of R; that is, P[X 2 (a;b)] > 0 for all a;b 2 R and a 6= b. (a) Give an example of a distribution that X could have, and one that it could not. (b) Show that the CDF F of X is strictly increasing. That is, F(x+e) > F(x) for any e > 0. Argue why this implies that F : R ! (0;1) must be invertible. (c) Let U be a uniform random variable on (0;1). What is the distribution of F-1(U)? (d) Your work in part (c) shows that in order to sample X, it is enough to be able to sample U. If X was a discrete random variable instead, taking finitely many values, can we still use U to sample X? 3 Just One Tail, Please Let X be some random variable with finite mean and variance which is not necessarily nonnegative. The extended version of Markov’s Inequality states that for a non-negative function f(x) which is monotonically increasing for x > 0 and some constant a > 0, P(X ≥ a) ≤ E[f(X)] f(a) Suppose E[X] = 0, Var(X) = s2 < ¥, and a > 0. (a) Use the extended version of Markov’s Inequality stated above with f(x) = (x+c)2, where c is some positive constant, to show that: P(X ≥ a) ≤ s2 +c2 (a +c)2 (b) Note that the above bound applies for all positive c, so we can choose a value of c to minimize the expression, yielding the best possible bound. Find the value for c which will minimize CS 70, Spring 2020, HW 12 4 the RHS expression (you may assume that the expression has a unique minimum). Plug in the minimizing value of c to prove the following bound: P(X ≥ a) ≤ s2 a2 +s2 : (c) Recall that Chebyshev’s inequality provides a two-sided bound. That is, it provides a bound on P(jX - E[X]j ≥ a) = P(X ≥ E[X] + a) + P(X ≤ E[X] - a). If we only wanted to bound the probability of one of the tails, e.g. if we wanted to bound P(X ≥ E[X]+a), it is tempting to just divide the bound we get from Chebyshev’s by two. Why is this not always correct in general? Provide an example of a random variable X (does not have to be zero-mean) and a constant a such that using this method (dividing by two to bound one tail) is not correct, that is, P(X ≥ E[X]+a) > Var 2a(X2 ) or P(X ≤ E[X]-a) > Var 2a(X2 ). (d) What is a necessary and sufficient condition to place on a random variable X such that dividing by two to bound one tail would be correct? Now we see the use of the bound proven in part (b) - it allows us to bound just one tail while still taking variance into account, and does not require us to assume any property of the random variable. Note that the bound is also always guaranteed to be less than 1 (and therefore at least somewhat useful), unlike Markov’s and Chebyshev’s inequality! (e) Let’s try out our new bound on a simple example. Suppose X is a positively-valued random variable with E[X] = 3 and Var(X) = 2. What bound would Markov’s inequality give for P[X ≥ 5]? What bound would Chebyshev’s inequality give for P[X ≥ 5]? What about for the bound we proved in part (b)? (Note: Recall that the bound from part (b) only applies for zero-mean random variables.) 4 Law of Large Numbers Recall that the Law of Large Numbers holds if, for every e > 0, lim n!¥ P 1 nSn -E 1 nSn > e = 0: In class, we saw that the Law of Large Numbers holds for Sn = X1 + ••• + Xn, where the Xi’s are i.i.d. random variables. This problem explores if the Law of Large Numbers holds under other circumstances. Packets are sent from a source to a destination node over the Internet. Each packet is sent on a certain route, and the routes are disjoint. Each route has a failure probability of p 2 (0;1) and different routes fail independently. If a route fails, all packets sent along that route are lost. You can assume that the routing protocol has no knowledge of which route fails. For each of the following routing protocols, determine whether the Law of Large Numbers holds when Sn is defined as the total number of received packets out of n packets sent. Answer Yes if the CS 70, Spring 2020, HW 12 6 Law of Large Number holds, or No if not, and give a brief justification of your answer. (Whenever convenient, you can assume that n is even.) (a) Yes or No: Each packet is sent on a completely different route. (b) Yes or No: The packets are split into n=2 pairs of packets. Each pair is sent together on its own route (i.e., different pairs are sent on different routes). (c) Yes or No: The packets are split into 2 groups of n=2 packets. All the packets in each group are sent on the same route, and the two groups are sent on different routes. (d) Yes or No: All the packets are sent on one route. CS 70, Spring 2020, HW 12 8 5 Practical Confidence Intervals (a) It’s New Year’s Eve, and you’re re-evaluating your finances for the next year. Based on previous spending patterns, you know that you spend $1500 per month on average, with a standard deviation of $500, and each month’s expenditure is independently and identically distributed. As a college student, you also don’t have any income. How much should you have in your bank account if you don’t want to run out of money this year, with probability at least 95%? (b) As a UC Berkeley CS student, you’re always thinking about ways to become the next billionaire in Silicon Valley. After hours of brainstorming, you’ve finally cut your list of ideas down to 10, all of which you want to implement at the same time. A venture capitalist has agreed to back all 10 ideas, as long as your net return from implementing the ideas is positive with at least 95% probability. Suppose that implementing an idea requires 50 thousand dollars, and your start-up then succeeds with probability p, generating 150 thousand dollars in revenue (for a net gain of 100 thousand dollars), or fails with probability 1 - p (for a net loss of 50 thousand dollars). The success of each idea is independent of every other. What is the condition on p that you need to satisfy to secure the venture capitalist’s funding? (c) One of your start-ups uses error-correcting codes, which can recover the original message as long as at least 1000 packets are received (not erased). Each packet gets erased independently with probability 0:8. How many packets should you send such that you can recover the message with probability at least 99%? 6 Continuous Probability Continued For the following questions, please briefly justify your answers or show your work. (a) If X ∼ N(0;sX2) and Y ∼ N(0;sY2) are independent, then what is E(X +Y)k for any odd k 2 N? (b) Let fm;s(x) be the density of a N(m;s2) random variable, and let X be distributed according to a fm1;s1(x) + (1 - a)fm2;s2(x) for some a 2 [0;1]. Please compute E[X] and Var[X]. Is X normally distributed? (c) Assume Bob1;Bob2;:::;Bobk each hold a fair coin whose two sides show numbers instead of heads and tails, with the numbers on Bobi’s coin being i and -i. Each Bob tosses their coin n times and sums up the numbers he sees; let’s call this number Xi. For large n, what is the distribution of (X1 +•••+Xk)=pn approximately equal to? (d) If X1;X2;::: is a sequence of i.i.d. random variables of mean m and variance s2, what is limn!¥ Ph∑n k=1 Xsk-nam 2 [-1;1]i for a 2 [0;1] (your answer may depend on a and F, the CDF of a N(0;1) variable)? CS 70, Spring 2020, HW 12 11 (e) Assume we wanted to estimate the value of p by repeatedly throwing a needle of length 1 cm on a striped floor, whose stripes all run parallel at distances 1 cm from each other. Please give an estimator of p, and compute an approximate 95% confidence intervals using the central limit theorem. (Hint: You may assume that p(p ±e) ≈ p2 for small e). [Show More]

Last updated: 1 year ago

Preview 1 out of 13 pages