University of California, Berkeley - CS 70 HW13-Solution. CS 70 Discrete Mathematics and Probability Theory Fall 2018. All Solutions Worked.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2018 Course Notes HW 13 1 Buffon’s Needle on a Grid In this problem, we will consider Buffon’s Needle, but with a catch. We now drop a nee... dle 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. (e) We will fold the needle into an equilateral triangle, where each side is length 1 3. What is the expected number of intersections that this triangle will have with the gridlines, when dropped onto the grid? Justify your answer. 2 Variance of the Minimum of Uniform Random Variables Let n be a positive integer and let X1;:::;Xn i.i.d. ∼ Uniform[0;1]. Find varY, where Y := minfX1;:::;Xng: Hint: You may need to perform integration by parts. 3 Erasures, Bounds, and Probabilities Alice is sending 1000 bits to Bob. The probability that a bit gets erased is p, and the erasure of each bit is independent of the others. CS 70, Fall 2018, HW 13 4 Alice is using a scheme that can tolerate up to one-fifth of the bits being erased. That is, as long as Bob receives at least 801 of the 1000 bits correctly, he can decode Alice’s message. In other words, Bob becomes unable to decode Alice’s message only if 200 or more bits are erased. We call this a “communication breakdown”, and we want the probability of a communication breakdown to be at most 10-6. 1. Use Markov’s inequality to upper bound p such that the probability of a communications breakdown is at most 10-6. 2. Use Chebyshev’s inequality to upper bound p such that the probability of a communications breakdown is at most 10-6. 3. As the CLT would suggest, approximate the fraction of erasures by a Gaussian random variable (with suitable mean and variance). Use this to find an approximate bound for p such that the probability of a communications breakdown is at most 10-6. 4 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). (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. 5 Markov Chain Terminology In this question, we will walk you through terms related to Markov chains. 1. (Irreducibility) A Markov chain is irreducible if, starting from any state i, the chain can transition to any other state j, possibly in multiple steps. 2. (Periodicity) d(i) := gcdfn > 0 j Pn(i;i) = P[Xn = i j X0 = i] > 0g, i 2 X . If d(i) = 1 8i 2 X , then the Markov chain is aperiodic; otherwise it is periodic. CS 70, Fall 2018, HW 13 8 3. (Matrix Representation) Define the transition probability matrix P by filling entry (i; j) with probability P(i; j). 4. (Invariance) A distribution p is invariant for the transition probability matrix P if it satisfies the following balance equations: p = pP. 0 1 a b 1-b 1-a (a) For what values of a and b is the above Markov chain irreducible? Reducible? (b) For a = 1, b = 1, prove that the above Markov chain is periodic. (c) For 0 < a < 1, 0 < b < 1, prove that the above Markov chain is aperiodic. (d) Construct a transition probability matrix using the above Markov chain. (e) Write down the balance equations for this Markov chain and solve them. Assume that the Markov chain is irreducible. 6 Analyze a Markov Chain Consider the Markov chain X(n) with the state diagram shown below where a;b 2 (0;1). 0 1 2 a 1 - a b 1 - b 1 (a) Show that this Markov chain is aperiodic; (b) Calculate P[X(1) = 1;X(2) = 0;X(3) = 0;X(4) = 1 j X(0) = 0]; (c) Calculate the invariant distribution; (d) Let Ti = minfn ≥ 0 j X(n) = ig, Ti is the number of steps until we transit to state i for the first time. Calculate E[T2 j X(0) = 1]. 7 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. CS 70, Fall 2018, HW 13 11 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: 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.] [Show More]

Last updated: 1 year ago

Preview 1 out of 14 pages