U.C. Berkeley — CS70: Discrete Mathematics and Probability Problem Set 10Lecturers: Umesh Vazirani & Christos H. Papadimitriou Due November 13, 2006 at 4:00pmProblem Set 101. Independence(a) Show that, for independent random variables X, Y , we have E[XY ] = E[X]E[Y ] (Hint: Showfirst that, even if the r.v.’s are not independent, E[XY ] =PaPbab · Pr[X = a ∧ Y = b].)(b) Give a simple example to show that the conclusion of part (a) is not necessarily true when X andY are not independent.2. Pairwise IndependenceThis problem illustr ates that events may be pairwise independent but not mutually independent. Twofair dice are thrown. Consider the following three events: A = the fir st die is odd; B = the second die is odd;C = the sum of the dice is odd.(a) Show by directly counting s ample points that events A, B are independent; that B, C are inde-pendent; and that A, C are independent.(b) Show that the three events are not mutually independent.3. Variance(a) Let X and Y be independent r andom variables. Express V ar(X − Y ) in terms of V ar(X) andV ar(Y ).(b) Given a rando m varia ble X with E(X) = µ and V ar(X) = σ2, let the random variable Y = XZwhere Z is defined as follows: Flip a fair coin. If it comes up H, then Z = 1, otherwise Z = −1.Find V ar(Y ).4. ChebyshevEach pixel in a 32 × 8 display is turned on o r off with equal probability. The display shows a horizontalline if all 8 pixels in a given row are turned on. Let X denote the number of horizontal lines that thedisplay s hows.• What is E[X]?• What is V ar[X]?• how that P r[X ≥ 2] ≤ 1/25.5. RunsA biase d coin is tossed n times, and heads shows with probability p on e ach toss. A ru n is a maximalsequence of throws which result in the same outcome, so that, for example, the se quence HHT HT T Hcontains five runs.• Show that the expected number of runs is 1 + 2(n − 1)p(1 − p).1• What is the varia nce of the number of runs?6. Extra C reditI think of two dis tinct real numbers between 0 and 1 but do not reveal them to you. I now chooseone of the two numbers at random and give it to you. Can you give a procedure for guessing whetheryou were shown the smaller or the larger of the two numbers, such that your g uess is correct withprobability strictly gre ater than 0.5 (although exactly how much better than 0.5 may depend on theactual values of the two
View Full Document
Unlocking...