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

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

1. (15 pts.) Geometric Distribution James Bond is imprisoned in a cell from which there are three possible ways to escape: an airconditioning duct, a sewer pipe and the door (which is unlocked). The air-conditioning duct leads him on a two-hour trip whereupon he falls through a trap door onto his head, much to the amusement of his captors. The sewer pipe is similar but takes five hours to traverse. Each fall produces temporary amnesia and he is returned to the cell immediately after each fall. Assume that he always immediately chooses one of the three exits from the cell with probability \frac{1}{3}. On the average, how long does it take before he realizes that the door is unlocked and escapes?

2. (15 pts.) Another distribution A super power has 2620 missiles stored in well separated silos. An enemy is considering a sneak attack. However, for the attack to succeed every one of the missiles must be destroyed. Assume that each attacking warhead hits one of the enemy missiles with each enemy missile being equally likely to be the one that is hit. How many warheads on the average will be needed to ensure the complete destruction of every enemy missile?

3. (20 pts.) Coupon Collecting

(a) Let X be the number of tosses of a biased coin with Heads probability p until the first Head appears (i.e., X is a geometric r.v. with parameter p). We have seen in lecture that E[X] = \frac{1}{p}. Show that Var[X] = \frac{1−p}{p^{2}} .

(b) Now let X be the r.v. in the coupon collecting problem, i.e., X is the number of cereal boxes we need to buy before we have collected one copy of each of n baseball cards. Recall from lecture that μ = E[X] = n∑ _{i=1}^{n} \frac{1}{i} ≈ n(lnn+γ). Use the result of part (a) to compute the variance Var[X]. (Note: your answer should contain a sum of the form ∑ _{i=1}^{n} \frac{1}{i^{2}}.)

(c) It turns out that the series ∑ _{i=1}^{∞} \frac{1}{i^{2}} converges to a constant value C = \frac{π^{2}}{6} ≈ 1.645. Deduce that Var[X] ≤ Cn^{2}. Hence deduce the smallest value of β for which you can say that the probability we need to buy more than μ + βn boxes is less than \frac{1}{100}.

4. (20 pts.) Random bit strings Consider a random bit string S of length n.

(a) For a given position j in S, what is the probability that it is a starting point of a run of at least l ones?

(b) What is the expected number of places j at which runs of at least l ones start?

(c) Use Markov’s inequality to show that the probability that there exists a run of at least clogn ones is less than \frac{1}{n^{c−1}} .

(d) Call a bit string of length l “alternating of length l” if it has length l, its odd-position bits are 1, and its even-position bits are 0. For instance, 10101 is alternating of length 5, 1010 is alternating of length 4, etc. What is the expected number of places at which an alternating string of length at least l starts?

5. (20 pts.) More on Independent Random Variables This problem is a continuation of last week’s problem on independent random variables.

(a) Recall from lecture that when X and Y are independent, VarX + Y = VarX + VarY. Give a simple example to show that this is not necessarily true when X and Y are not independent.

(b) Show that, for any random variables X and Y (not necessarily independent), we have

VarX + Y = VarX + VarY + 2(𝔼[XY] − 𝔼[X]𝔼[Y]).

(c) The quantity 𝔼[XY] − 𝔼[X]𝔼[Y] is called the covariance of X and Y, written Cov(X,Y). When X and Y are independent, Cov(X,Y) = 0. Is the converse true? I.e., does Cov(X,Y) = 0 imply that X and Y are independent? If so, prove it; if not, give a simple counterexample.