Description

CS 70 Discrete Mathematics and Probability Theory

1 Inequality Practice
(a) X is a random variable such that X >−5 and E[X] = −3. Find an upper bound for the probability of X being greater than or equal to −1.
(b) Y is a random variable such that Y < 10 and E[Y] = 1. Find an upper bound for the probability of Y being less than or equal to −1.
(c) You roll a die 100 times. Let Z be the sum of the numbers that appear on the die throughout the 100 rolls. Compute Var(Z). Then use Chebyshev’s inequality to bound the probability of the sum Z being greater than 400 or less than 300.
2 Vegas
On the planet Vegas, everyone carries a coin. Many people are honest and carry a fair coin (heads on one side and tails on the other), but a fraction p of them cheat and carry a trick coin with heads on both sides. You want to estimate p with the following experiment: you pick a random sample of n people and ask each one to flip his or her coin. Assume that each person is independently likely to carry a fair or a trick coin.
1. Given the results of your experiment, how should you estimate p?
(Hint: Construct an (unbiased) estimator for p such that E[pˆ] = p.)
2. How many people do you need to ask to be 95% sure that your answer is off by at most 0.05?
3 Working with the Law of Large Numbers
(a) A fair coin is tossed multiple times and you win a prize if there are more than 60% heads. Which number of tosses would you prefer: 10 tosses or 100 tosses? Explain.
(b) A fair coin is tossed multiple times and you win a prize if there are more than 40% heads. Which number of tosses would you prefer: 10 tosses or 100 tosses? Explain.
(c) A fair coin is tossed multiple times and you win a prize if there are between 40% and 60% heads. Which number of tosses would you prefer: 10 tosses or 100 tosses? Explain.
(d) A fair coin is tossed multiple times and you win a prize if there are exactly 50% heads. Which number of tosses would you prefer: 10 tosses or 100 tosses? Explain.