CS 70 Discrete Mathematics and Probability Theory _ Homework 11. With Answers | University of California, Berkeley

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2021 HW 11 Due: Saturday 11/13, 4:00 PM Grace period until Saturday 11/13, 5:59 PM Sundry Before you start writing your final homework submis... sion, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.) Answer: I worked alone on the assignment. 1 Exploring Concepts The following snippet illustrates a concept about polynomials. Polynomial? Interpolation gives one! Few roots says; No more! Yet another concept. Lo! Delta sub i. Behold! One at x sub i. Sub j? Such empty. And finally. Polynomial in x. A zero at r. Cleft by x minus r. And nothing remains. 1. You should write a poem or snippet to illustrate a concept from this weeks content. We are certain you can do better, but no pressure. It’s all good. Answer: Probability? Use me CS 70, Fall 2021, HW 11 1 calculate possibility I am able Start by providing me A Random variable Give me Sample Space All possible outcomes is the case Give favourable outcome Get the count sum Up favourable outcomes Down Sample Space Use Divisibility Gives us probability Binomial Distribution Toss a Coin N times Binomial Distribution is assigned Coin toss is independent Need probability of Head? Binomial Distribution is Evident Binomial of n and k Power Head to k Power Tail to n-k Multiply them all straight You just found the probability of head 2. In terms of the staff using your content for fun and “profit”. Do you wish to (1) allow us to share to the class without attribution (2) allow us to share to the class with attribution or (3) please, please do not share! Answer: (1): Allowed to share to the class without attribution. This problem will be sampled but only adds to the numerator not the “out of” (or denominator). Also, it will be generously graded and worth 10 points. If we feel this is useful to students (based on the connection to concepts in the course), we may continue it in future problem sets. 2 Will I Get My Package? A delivery guy in some company is out delivering n packages to n customers, where n ∈ N, n > 1. Not only does he hand each customer a package uniformly at random from the remaining packages, he opens the package before delivering it with probability 1/2. Let X be the number of customers who receive their own packages unopened. CS 70, Fall 2021, HW 11 2 (a) Compute the expectation E(X). Answer: Let us define Xi = ( 1 , if the i-th customer gets the correct package unopened, 0, in all other cases. By using the linearity of expectation, we have E(X) = E(∑n i=1 Xi) = ∑n i=1 E(Xi). From the above equation, we have E(Xi) = P[Xi = 1] = 21n. Now, as we know that each customer will have the probability of getting their own product be 1n, also the probability of opening the same package independently is 1 2. So, E(X) = n∗ 21n = 1 2. (b) Compute the variance Var(X). Answer: If we are going to calculate var(X), then we first need to calculate EX2. Using the linearity of expectation: EX2 = E (X1 +X2 + ··· +Xn)2 = E ∑ i, j XiXj! = ∑i, j EXiXj Now, we consider the following two cases, when i = j and the other when i ̸= j. Now we have ∑i, j EXiXj = ∑i EXi2 +∑i̸= j EXiXj. EXi2 = E(Xi) = 1 2n for all i. To find EXiXj, we need to calculate PXiXj = 1. PXiXj = 1 = P[Xi = 1]PXj = 1 | Xi = 1 = 1 2n · 1 2(n- 1) If customer i has received the right package, customer j will have a total of n- 1 choices left. So, EX2 = n· 1 2n +n· (n- 1) · 1 2n · 1 2(n- 1) = 3 4 var(X) = EX2 - E(X)2 = 3 4 - 1 4 = 1 2 CS 70, Fall 2021, HW 11 3 3 Diversify Your Hand You are dealt 5 cards from a standard 52 card deck. Let X be the number of distinct values in your hand. For instance, the hand (A, A, A, 2, 3) has 3 distinct values. (a) Calculate E[X]. Answer: Let the indicator of ith value appearing on the hand be Xi. We can say X = X1 + X2 + X3 + X4 + X5. Let us assume that 13 corresponding to K, 12 is corresponding to Q, 11 is corresponding to J. Using the linearity of the expectation we can say E[X] = ∑5 i=1 E[Xi]. Now, we can calculate the probability P[X = 1] by taking the compliment 1 - Pr[Xi = 0], which is the subtraction of probability that the card does not appear from 1. This value will be 1- (48 5 ) (52 5 ). Now, E[X] = 5P[X1 = 1] = 5(1- (48 5 ) (52 5 )). (b) Calculate Var[X] [Show More]

Last updated: 1 week ago

Preview 3 out of 10 pages