University of California, Berkeley - CS 70HW09 SOLN. CS 70 Discrete Mathematics and Probability Theory. Homework 9 Solutions.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2017 Kannan Ramchandran and Satish Rao HW 9 Sundry Before you start your homework, write down your team. Who else did you work with on this... homework? List names and email addresses. (In case of homework party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade. Please copy the following statement and sign next to it: I certify that all solutions are entirely in my words and that I have not looked at another student’s solutions. I have credited all external sources in this write up. I certify that all solutions are entirely in my words and that I have not looked at another student’s solutions. I have credited all external sources in this write up. (signature here) 1 Identity Theft A group of n friends go to the gym together, and while they are playing basketball, they leave their bags against the nearby wall. An evildoer comes, takes the student ID cards from the bags, randomly rearranges them, and places them back in the bags, one ID card per bag. What is the probability that no one receives his or her own ID card back? [Hint: Use the generalized inclusionexclusion principle.] Then, find an approximation for the probability as n ! ¥. You may, without proof, refer to the power series for ex: ex = ¥∑k=0 xk k 2 Mario’s Coins Mario owns three identical-looking coins. One coin shows heads with probability 1=4, another shows heads with probability 1=2, and the last shows heads with probability 3=4. CS 70, Fall 2017, HW 9 2 (a) Mario randomly picks a coin and flips it. He then picks one of the other two coins and flips it. Let X1 and X2 be indicators of the 1st and 2nd flips showing heads. Are X1 and X2 independent? If so, prove it; if not, provide a counterexample. (b) Mario randomly picks a single coin and flips it twice. Let Y1 and Y2 be indicators of the 1st and 2nd flips showing heads. Are Y1 and Y2 independent? If so, prove it; if not, provide a counterexample. (c) Mario arranges his three coins in a row. He flips the coin on the left, which shows heads. He then flips the coin in the middle, which shows heads. Finally, he flips the coin on the right. What is the probability that it also shows heads? 3 Combinatorial Coins Allen and Alvin are flipping coins for fun. Allen flips a fair coin k times and Alvin flips n - k times. In total there are n coin flips. (a) Use a combinatorial proof to show that k∑i=0 k -k i n-i k = nk : You may assume that n-k ≥ k. (b) Prove that the probability that Allen and Alvin flip the same number of heads is equal to the probability that there are a total of k heads. 4 Sinho’s Dice Sinho rolls three fair-sided dice. What is the PMF for the maximum of the three values rolled? [Hint: First find the CDF.] [Show More]

Last updated: 1 year ago

Preview 1 out of 6 pages