Massachusetts Institute of Technology Handout 54 6.042J/18.062J: Mathematics for Computer Science December 7, 2000 Professors Nancy Lynch and Srinivas Devadas

Problem Set 11.5

You do not have to turn in the solutions to this Problem Set. It is designed to help you study for the final.

—————————————————————————–

Self-study: All about variance, from Section 2 of Lecture Notes 25.

Reading: Lecture notes 25 and 26; Rosen, Sections 4.4, 4.5,; (Optional) Ross Sections 4.6, 8.2, 8.5.

Final Exam: Covers the entire course, with more emphasis on the last 8 lectures. The final will be held Thursday, December 21, 1:30 p.m. to 4:30 p.m. in Rockwell.

Problem 1

(a) Let X be a random variable whose value is an observation drawn uniformly at random from the {i ∈ ℤ | −n ≤ i ≤ n}. Let Y = X^{2}. Show that Ex[XY] = Ex[X]Ex[Y]. Are X and Y independent?

(b) Show that in general for any two random variables X and Y that if Ex[XY] = Ex[X]Ex[Y] then var(X+Y) = var(X)+var(Y). In particular, this shows that it is possible for nonindependent variables to have variances that exhibit linearity.

Problem 2 Suppose you are playing the game “Hearts” with three of your friends. In Hearts, all the cards are dealt to the players, in this case the four of you will each have 13 cards.

(a) What is the expectation and variance of the number of hearts that you will have in your hand?

(b) What is the expectation and variance of the number of suits in your hand?

Problem 3 Psychological diagnosis of sociopaths is notoriously unreliable. For example, a random psychologist is as likely to diagnose a normal patient as sociopathic as he is to recognize that the patient is normal. A random psychologist is actually slightly less likely to correctly diagnose a real sociopath than not—sociopaths are really good liars.

(a) In these circumstances it might seem there was no reliable way to diagnose sociopaths, but in theory there is a way—if we have a large enough population of psychologists who reach their judgements independently. Explain how to obtain a reliable diagnosis in this case. Briefly explain why your method will be reliable, citing appropriate results from class. A qualitative answer is all that’s required—you need not come up with any numerical estimates or growth rates.

(b) Is it plausible to assume that psychologists will make their diagnoses independently? Briefly explain.

Problem 4 Three hundred students take the 6.042 final exam. The mean on the exam is 90 and the lowest score was 30. You have no other information about the students and the exam, e.g., you should not assume that the final is worth 100 points.

(a) State the best possible upper bound on the number of students who scored at least 180.

(b) Give an example set of scores which achieve your bound.

Problem 5 Suppose that n people have their hats returned at random. Let X_{i} = 1 if the ith person gets his or her own hat back and 0 otherwise. Let S_{n} = ∑_{i=1}^{n} X_{i}, so S_{n} is the total number of people who get their own hat back. Show that

(a) E [X_{i}^{2}] = 1/n.

(b) E [X_{i}X_{j}] = 1/n(n − 1) for i ≠ j.

(c) E [S_{n}^{2}] = 2. Hint: Use (a) and (b).

(d) Var [S_{n}] = 1.

(e) Using Chebyshev’s Inequality, show that Pr(S_{n} ≥ 11) ≤ .01 for any n ≥ 11.

Problem 6

(a) Knowing only that the average graduating MIT student’s total number of credits is 200, find a tight upper bound for the fraction of MIT students graduating with at least 235 credits. (Ignore the fact that students who graduate do so after at most 700 years; that is, assume that there is no theoretical upper bound on the possible number of credits a student may earn.)

(b) Assuming in addition only that the standard deviation of the total credits per graduating student is 7, give a tight bound on the fraction of students who can graduate with at least 235 credits.

(c) Different information about MIT credits is now provided by the Registrar. The standard deviation is not 7 after all. Instead, the registrar reports that 30% of past graduates are EECS majors and half of them had 235 or more credits. Only 1/7th of the non-EECS students graduated with that many credits. Use this information and the Chernoff bound to give a tight upper bound on the probability that among 1000 randomly chosen graduating students, at least 300 have 235 or more credits. (You may leave ln and e in your answer).

Problem 7 The latest recount of the Florida votes has yielded exactly 3 million votes for each. The Florida Supreme Court has decided to allow repeated recounts of all the votes in Florida, until the difference between the two is at least 1000 votes.

It turns out that recounting of votes has the odd property that it can be modeled by a random walk. Specifically, each recount has probability .4 of yielding exactly 100 more votes for Bush than the previous count, and exactly .6 of giving 100 more votes for Gore. (Unlike the current election, in this scenario, the total number of votes after each recount is constant.)

(a) What is the probability of Bush eventually winning? Of Gore eventually winning? Of neither eventually winning (that is, recounts go on forever)?

(b) What is the expected duration of the election (assume one recount per day)?