University of California, Berkeley - CS 70. Discrete Mathematics and Probability Theory Fall 2019. All Solutions Worked out.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 13 Note: This homework consists of two parts. The first part (questions 1-6) will be graded and will ... determine your score for this homework. The second part (questions 7-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare. For each problem, justify all your answers unless otherwise specified. Part 1: Required Problems 1 Short Answer (a) Let X be uniform on the interval [0,2], and define Y = 2X +1. Find the PDF, CDF, expectation, and variance of Y. (b) Let X and Y have joint distribution f (x,y) = (cxy 0 else +1/4 x 2 [1,2] and y 2 [0,2] Find the constant c. Are X and Y independent? (c) Let X ⇠ Exp(3). What is the probability that X 2 [0,1]? If I define a new random variable Y = bXc, for each k 2 N, what is the probability that Y = k? Do you recognize this (discrete) distribution? (d) Let Xi ⇠ Exp(li) for i = 1,...,n be mutually independent. It is a (very nice) fact that min(X1,...,Xn) ⇠ Exp(µ). Find µ. 2 Exponential Expectation (a) Let X ⇠ Exp(l). Use induction to show that E[Xk] = k!/l k for every k 2 N. (b) For any |t| < l, compute E[etX] directly from the definition of expectation. (c) Using part (a), compute • k=0 E[kX!k]tk. 3 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 fµ,s(x) be the density of a N(µ,s2) random variable, and let X be distributed according to a fµ1,s1(x) + (1 ' a)fµ2,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 µ and variance s2, what is limn!• PhÂn k=1 Xsk'naµ 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)? (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). 4 Bu↵on’s Needle on a Grid In this problem, we will consider Buffon’s Needle, but with a catch. We now drop a needle 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 = 1 2 sin(2q) without proof. CS 70, Fall 2019, HW 13 6 (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. 5 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? CS 70, Fall 2019, HW 13 8 6 Balls, meet Bins Alice and Bob are tasked with throwing balls into bins (to set up a probability problem for later). They decide to make a game out of it: Alice and Bob will each take a ball, and once per minute, they will both simultaneously (and independently) attempt to throw their balls into a bin. CS 70, Fall 2019, HW 13 9 Once Alice or Bob successfully lands a ball in a bin, that person stops while the other person continues to try until they also land a throw. When this happens, the game is over. Suppose that on every try, the probability of successfully landing the throw in a bin is p. What is the expected number of minutes until the game is over? Solve this using a Markov chain with three states. Then, state how your solution can be interpreted in terms of two geometric random variables. Note: This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare. Part 2: Optional Problems 7 Markov Chains: Prove/Disprove Prove or disprove the following statements, using the definitions from the previous question. (a) There exists an irreducible, finite Markov chain for which there exist initial distributions that converge to different distributions. (b) There exists an irreducible, aperiodic, finite Markov chain for which P(Xn+1 = j | Xn = i) = 1 or 0 for all i, j. CS 70, Fall 2019, HW 13 10 (c) There exists an irreducible, non-aperiodic Markov chain for which P(Xn+1 = j | Xn = i) 6= 1 for all i, j. (d) For an irreducible, non-aperiodic Markov chain, any initial distribution not equal to the invariant distribution does not converge to any distribution. 8 Oski’s Markov Chain When Oski Bear is studying for CS70, he splits up his time between reading notes and working on practice problems. To do this, every so often he will make a decision about what kind of work to do next. When Oski is already reading the notes, with probability a he will decide to switch gears and work on a practice problem, and otherwise, he will decide to keep reading more notes. Conversely, when Oski is already working on a practice problem, with probability b he will think of a topic he needs to review, and will decide to switch back over to the notes; otherwise, he will keep working on practice problems. Assume that (unlike real life, we hope!) Oski never runs out of work to do. CS 70, Fall 2019, HW 13 11 (a) Draw a 2-state Markov chain to model this situation. (b) In the remainder of this problem, we will learn to work with the definitions of some important terms relating to Markov Chains. These definitions are as follows: (a) (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. (b) (Periodicity) d(i) := gcd{n > 0 | Pn(i,i) = P[Xn = i | X0 = i] > 0}, i 2 X . If d(i) = 1 8i 2 X , then the Markov chain is aperiodic; otherwise it is periodic. (c) (Matrix Representation) Define the transition probability matrix P by filling entry (i, j) with probability P(i, j). (d) (Invariance) A distribution p is invariant for the transition probability matrix P if it satisfies the following balance equations: p = pP. For what values of a and b is the Markov chain irreducible? (c) For a = 1, b = 1, prove that the Markov chain is periodic. (d) For 0 < a < 1, 0 < b < 1, prove that the Markov chain is aperiodic. (e) Construct a transition probability matrix using the Markov chain. (f) Write down the balance equations for the Markov chain and solve them. Assume that the Markov chain is irreducible. [Show More]

Last updated: 1 year ago

Preview 1 out of 13 pages