University of California, Berkeley - CS 70 hw13-solution. CS 70 Discrete Mathematics and Probability Theory Spring 2019 . All Solutions Worked.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Spring 2019 Babak Ayazifar and Satish Rao HW 13 1 Markov’s Inequality and Chebyshev’s Inequality A random variable X has variance var(X) = 9 an... d 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. (a) EX2 = 13. (b) P[X = 2] > 0. (c) P[X ≥ 2] = P[X ≤ 2]. (d) P[X ≤ 1] ≤ 8=9. (e) P[X ≥ 6] ≤ 9=16. (f) P[X ≥ 6] ≤ 9=32. Solution: 2 Subset Card Game Jonathan and Yiming are playing a card game. Jonathan has k > 2 cards, and each card has a real number written on it. Jonathan tells Yiming (truthfully), that the sum of the card values is 0, and that the sum of squares of the values on the cards is 1. Specifically, if the card values are c1;c2;:::;ck, then we have ∑k i=1 ci = 0 and ∑k i=1 c2 i = 1. Jonathan and Yiming also agree on a positive target value of a. The cards are then going to be dealt randomly in the following fashion: for each card in the deck, a fair coin is flipped. If the coin lands heads, then the card goes to Yiming, and if the coin lands tails, the card goes to Jonathan. Note that it is possible for either player to end up with no cards/all the cards. A player wins the game if the sum of the card values in their hand is at least a, otherwise it is a tie. (a) Prove that the probability that Yiming wins is at most 8a12 . (b) Find a deck of k cards and target value a where the probability that Yiming wins is exactly 1 8a2 . Solution: 3 Sampling a Gaussian With Uniform In this question, we will see one way to generate a normal random variable if we have access to a random number generator that outputs numbers between 0 and 1 uniformly at random. As a general comment, remember that showing two random variables have the same CDF or PDF is sufficient for showing that they have the same distribution. (a) First, let us see how to generate an exponential random variable with a uniform random variable. Let U1 ∼ Uni f orm(0;1). Prove that -lnU1 ∼ Expo(1). CS 70, Spring 2019, HW 13 3 (b) Let N1;N2 ∼ N (0;1), where N1 and N2 are independent. Prove that N12 + N22 ∼ Expo(1=2). Hint: You may use the fact that over a region R, if we convert to polar coordinates (x;y) ! (r;q), then the double integral over the region R will be ZZR f (x;y)dxdy = ZZR f (rcosq;rsinq)•r dr dq: (c) Suppose we have two uniform random variables, U1 and U2. How would you transform these two random variables into a normal random variable with mean 0 and variance 1? Hint: What part (b) tells us is that the point (N1;N2) will have a distance from the origin that is distributed as the square root of an exponential distribution. Try to use U1 to sample the radius, and then use U2 to sample the angle. Solution: CS 70, Spring 2019, HW 13 4 4 Optimal Gambling Jonathan has a coin that may be biased, but he doesn’t think so. You disagree with him though, and he challenges you to a bet. You start off with X0 dollars. You and Jonathan then play multiple rounds, and each round, you bet an amount of money of your choosing, and then coin is tossed. Jonathan will match your bet, no matter what, and if the coin comes up heads, you win and you take both yours and Jonathan’s bet, and if it comes up tails, then you lose your bet. (a) Now suppose you actually secretly know that the bias of the coin is 1 2 < p < 1! You use the following strategy: on each round, you will bet a fraction q of the money you have at the start of the round. Let Xn denote the amount of money you have on round n. X0 represents your initial assets and is a constant value. What is E[Xn] in terms of X0; p, and q? (b) What value of q will maximize E[Xn]? For this value of q, what is the distribution of Xn? Can you predict what will happen as n ! ¥? [Hint: Under this betting strategy, what happens if you ever lose a round?] (c) The problem with the previous approach is that we were too concerned about expected value, so our gambling strategy was too extreme. Let’s start over: again we will use a gambling strategy in which we bet a fraction q of our money at each round. Express Xn in terms of n, q, X0, and Wn, where Wn is the number of rounds you have won up until round n. [Hint: Does the order in which you win the games affect your profit?] (d) By the law of large numbers, Wn=n ! p as n ! ¥. Using this fact, what does (lnXn)=n converge to as n ! ¥? (e) The rationale behind (lnXn)=n is that if (lnXn)=n ! c, where c is a constant, then that means for large n, Xn is roughly ecn. Therefore, c is the asymptotic growth rate of your fortune! Find the value of q that maximizes your asymptotic growth rate. (f) Using the value of q you found in the previous part, compute E[Xn]. (g) Now, Jonathan is not going to always believe that the coin is fair. What he will do is play 100 rounds with you, and observe how many times the coin comes up heads. Jonathan will then construct a 95% confidence interval for the true bias of the coin, p. True or false, the probability that Jonathan’s interval captures p is at least 95%. (h) Let’s say after playing 100 rounds, Jonathan observes that 74 heads have appeared. Help Jonathan construct a 95% confidence interval using the CLT. Also, answer true or false: the probability that this interval contains the true bias p of the coin is 95%. You may assume that F(2)-F(-2) ≈ 0:95, where F is the CDF of the standard Gaussian. Solution: 5 Boba in a Straw Imagine that Jonathan is drinking milk tea and he has a very short straw: it has enough room to fit two boba (see figure). Figure 1: A straw with one boba currently inside. The straw only has enough room to fit two boba. Here is a formal description of the drinking process: We model the straw as having two “components” (the top component and the bottom component). At any given time, a component can contain nothing, or one boba. As Jonathan drinks from the straw, the following happens every second: CS 70, Spring 2019, HW 13 7 1. The contents of the top component enter Jonathan’s mouth. 2. The contents of the bottom component move to the top component. 3. With probability p, a new boba enters the bottom component; otherwise the bottom component is now empty. Help Jonathan evaluate the consequences of his incessant drinking! (a) At the very start, the straw starts off completely empty. What is the expected number of seconds that elapse before the straw is completely filled with boba for the first time? [Write down the equations; you do not have to solve them.] (b) Consider a slight variant of the previous part: now the straw is narrower at the bottom than at the top. This affects the drinking speed: if either (i) a new boba is about to enter the bottom component or (ii) a boba from the bottom component is about to move to the top component, then the action takes two seconds. If both (i) and (ii) are about to happen, then the action takes three seconds. Otherwise, the action takes one second. Under these conditions, answer the previous part again. [Write down the equations; you do not have to solve them.] (c) Jonathan was annoyed by the straw so he bought a fresh new straw (the straw is no longer narrow at the bottom). What is the long-run average rate of Jonathan’s calorie consumption? (Each boba is roughly 10 calories.) (d) What is the long-run average number of boba which can be found inside the straw? [Maybe you should first think about the long-run distribution of the number of boba.] Solution: [Show More]

Last updated: 1 year ago

Preview 1 out of 10 pages