Problem 1(a)(b)Problem 2(a)(b)(c)Problem 3Problem 4(a)(b)(c)(d)� � 6.042/18.062J Mathematics for Computer Science April 29, 2005 Srini Devadas and Eric Lehman Notes for Recitation 20 Problem 1. The following two parts are not related. Try them, to make sure you un-derstand the jargon of random variables, distributions, probability density functions, etc. Ask your TA if you don’t understand/remember what some phrase means. (a) Suppose X1, X2, and X3 are three mutually independent random variables, each having the uniform distribution Pr (Xi = k) equal to 1/3 for each of k = 1, 2, 3. Let M be another random variable giving the maximum of these three random vari-ables. What is the density function of M? Solution. This can be easily hashed out by counting the possible outcomes: 1 M is 1 with probability 27 7 2 with probability 27 19 3 with probability 27 (b) Suppose X, Y are two independent binomial random variables with parameters (n, p) and (m, p), respectively. What is Pr (X + Y = k)? Solution. The pdf of X is the probability of tossing k Heads out of n independent flips of a coin with bias p. Likewise for Y and m flips. Since, X and Y are inde-pendent, the pdf of X + Y corresponds to n + m independent flips, i.e., X + Y is a Binomial variable with parameters (n + m, p). Hence, m + n kp (1 − p)m+n−k . k2 Recitation 20 Problem 2. I’m God. Seriously. So, I know everything that everybody thinks. In particu-lar, I know who each one of the 250,000,000 Americans want to vote for in the upcoming elections. I know that a fraction p = 0.52 of them want to vote for the current president. You are mortal. An insignificant dot in space-time. But a quite significant dot among dots. You work close to the president and, within a week, you must answer his agonizing question: “Am I winning?” Or, in math jargon (but with the same agony): “Is p > 1 2?” Your first idea is to ask me (I’m God). But you haven’t talked to me for a long time, so you know I won’t tell you. Your second idea is to call every American, ask them, then divide the yes’s by 250 million. But you soon realize there is not enough time (there is a reason for representative democracy). Your third idea. . . You have no third idea! In your panic as the week is almost over, you start picking Americans at random, call them, and ask! Amazingly, that’s the correct approach. But you should be careful what you are going to say to the president! Let’s see. (a) In you first phone call, you pick 1 American uniformly at random, call, and ask whether he/she will vote for the president. What is the probability that the answer is going to be “yes”. . . (i) from my perspective? (ii) from your perspective? How would you model this in terms of coin flips? Solution. From my perspective, it’s 0.52. From your perspective, it is also 0.52. The only problem is that you don’t know that, so you just call it p. Clearly, from your perspective, the first phone call is the same as flipping a coin with an unknown bias, which you call p (and I know is 0.52). (b) In your second phone call, you again pick 1 American uniformly at random, call, and ask whether he/she will vote for the president. But wait! When selecting the second voter, shouldn’t you exclude the guy that you asked in the first phone call? No. What’s bad if you exclude him/her? Solution. If you do this, you alter the coin that you are flipping. The bias will decrease or increase, depending on whether the first guy said “yes” or “no”, respec-tively. The analysis gets messy, so you don’t want to do this. (c) So, in each one of n phone calls, you pick 1 American uniformly at random and ask. Your plan is to eventually divide the number M of positive answers by n to get P = n M . An MIT friend tells you that, as the numerical outcome of a random experiment, this P is a random variable; and that, according to his calculations, Pr ( P − p ≤ 0.03) 0.95. (1)| | ≥ When you are done calling people, you divide to get P , and it’s 0.53. You call the president up and. . . what do you say? • Mr. President, p = 0.53! • Mr. President, with probability at least 95%, p is within 0.03 of 0.53!3 Recitation 20 • Mr. President, either p is within 0.03 of 0.53 or something very strange (less than 5-in-100) has happened. For each statement answer: (i) Are you justified to claim it? (ii) Is it true? Solution. The first statement is clearly off the mark. (i) Since you haven’t asked all Americans, you can only make probabilistic state-ments about p. (ii) The statement is also false, since p = 0.52. However, with a different choice of voters, it could have been true. Of course, even in that case, you wouldn’t be justified to claim it. The second statement is also wrong. (i) The unknown constant p is either within 0.03 of 0.53 or more than 0.03 away of 0.53. In the first case, the probability of it being as you claim is 1; in the second case, it is 0. The crucial point is that you don’t know which case holds. You could make the above claim, only if you knew you were in the first case. Sadly, you don’t. (ii) The claim is actually true in this case. Since p = 0.52, the unknown constant is indeed within 0.03 of 0.53. So the probability that you talk about is 1, and therefore at least 95%. But, as we said, it could be 0 and then the statement would be false. The third statement is the correct one. (i) You are justified to claim this statement. To see why, start with the statement either 0.53 − p ≤ 0.03 or 0.53 − p > 0.03.| | | | which is clearly true. Now read it as follows: Either p is within 0.03 of 0.53 or it is not and therefore my random random variable P took a value from a set that is hit only 5 times in 100. So, clearly either p is within 0.03 of 0.53 or something strange has happened. (ii) The statement is true. In the particular case, it is true because the first half of it is true.4 Recitation 20 Fact from lecture. Suppose a coin that comes up heads with probability p is flipped n times. Then for all α < p 2nH(α)1 − α Pr (# heads ≤ αn) ≤ 1 − α/p · � αn(1 − p)(1−α)n · p 2πα(1 − α)n where: 1 1 H(α) = α log2 + (1 − α) log2α 1 − α Problem 3. A coin that comes up heads with probability p is flipped n times. Find an upper bound on Pr (# heads ≥ βn)
View Full Document
Unlocking...