Description

1 Linearity
Solve each of the following problems using linearity of expectation. Explain your methods clearly.
(a) In an arcade, you play game A 10 times and game B 20 times. Each time you play game A, you win with probability 1/3 (independently of the other times), and if you win you get 3 tickets (redeemable for prizes), and if you lose you get 0 tickets. Game B is similar, but you win with probability 1/5, and if you win you get 4 tickets. What is the expected total number of tickets you receive?
(b) A monkey types at a 26-letter keyboard with one key corresponding to each of the lower-case English letters. Each keystroke is chosen independently and uniformly at random from the 26 possibilities. If the monkey types 1 million letters, what is the expected number of times the sequence “book” appears?
2 Joint Distributions
(a) Give an example of discrete random variables X andY with the property that E[XY]6=E[X]E[Y]. You should specify the joint distribution of X and Y.
(b) Give an example of discrete random variables X and Y that (i) are not independent and (ii) have the property that E[XY] = 0, E[X] = 0, and E[Y] = 0. Again you should specify the joint distribution of X and Y.
3 Ball in Bins
You are throwing k balls into n bins. Let Xi be the number of balls thrown into bin i.
(a) What is E[Xi]?
(b) What is the expected number of empty bins?
(c) Define a collision to occur when two balls land in the same bin (if there are n balls in a bin, count that as n−1 collisions). What is the expected number of collisions?