Discrete Mathematics and Probability Theory HW 9

CS 70 Discrete Mathematics and Probability Theory

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.
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 e
x
:
e
x =
∞
∑
0
x
k
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 1
(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−k
i
?
=
?
n
k
?
.
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.]
CS 70, Fall 2017, HW 9 2