CS 70 Discrete Mathematics for CS Spring 2004 Papadimitriou/Vazirani HW 10

Due on Wed, April 7 at 11:59PM (283 Soda)

1. (20 pts.) Independent Random Variables Two random variables X and Y on the same probability space are said to be independent if the events “X = a” and “Y = b” are independent for all pairs of values a, b. (i.e., the value taken on by X has no effect on the distribution of Y, and vice versa).

(a) Show that, for independent random variables X and Y, we have

E[XY] = E[X]E[Y]

(Hint: Show first that even if the random variables are not independent, E[XY] = ∑_{a}∑_{b}ab · Pr[X = a ∧ Y = b].)

(b) Give a simple example to show that the conclusion of part (a) is not necessarily true when X and Y are not independent.

2. (20 pts.) Random Variables in GF_{p} Let the random variables X and Y be distributed independently and uniformly at random in the set {0,1,...,p − 1}, where p > 2 is a prime.

(a) What is the expectation E[X]?

(b) Let S = (X + Y) modp and T = XY modp. What are the distributions of S and T?

(c) What are the expectations E[S] and E[T]?

(d) By linearity of expectation, we might expect that E[S] = (E[X]+E[Y]) modp. Explain why this does not hold in the present context—i.e., why does the value for E[S] obtained in part (c) not contradict linearity of expectation?

(e) Since X and Y are independent, we might expect that E[T] = E[X]E[Y] modp. Does this hold in this case? Explain why or why not.

3. (20 pts.) The Martingale Consider a fair game in a casino: on each play, you may stake any amount $X; you win or lose with probability \frac{1}{2} each (all plays being independent); if you win you get your stake back plus $X; if you lose, you lose your stake.

(a) What is the expected number of plays before your first win (including the play on which you win)?

(b) The following gambling strategy, known as the “martingale,” was popular in European casinos in the 18th century: on the first play, stake $1; on the second play $2; on the third play $4; and in general, on the kth play $2^{k−1}. Stop (and leave the casino!) when you first win. Show that if you follow this strategy, and assuming you have unlimited funds available, then you will leave the casino $1 richer with probability 1. (Maybe this is why the strategy is banned in most modern casinos).

(c) To discover the catch in this seemingly infallible startegy, let X be the random variable that measures your maximum loss before winning (i.e., the amount of money you have lost before the play on which you win.) Show that E[X] = ∞. What does this imply about your ability to play the martingale strategy in practice?