Massachusetts Institute of Technology Handout 60 6.042J/18.062J: Mathematics for Computer Science May 7, 1999 Professor Albert R. Meyer

Notes for Tutorial 13 (5/7/99)

1 Review of Variance and Expectation

E [X] ::= ∑ ; sample points s X(s) Pr {s} = ∑_{x∈range(X)} x Pr {X = x}

Linearity of expection:

E [X + Y] = E [X] + E [Y]
E [aX] = aE [X]

for any a ∈ ℝ. More generally,

E [∑_{n=0}^{∞} R_{n}] = ∑_{n=0}^{∞} E [R_{n}]

for any series R_{0} +R_{1} +… of random variables which is absolutely convergent at all sample points.

For random variable X with mean μ,

Var [X] ::= E [(X − μ)^{2}] = E [X^{2}] − E^{2} [X] .

For any a, b ∈ ℝ,

Var [aX + b] = a^{2}Var [X] .

If X, Y are independent,

E [X · Y] = E [X] · E [Y] ,
Var [X + Y] = Var [X] + Var [Y] .

2 Markov and Chebyshev Bounds

2.1 Review

The theorems of Markov and Chebyshev give upper bounds on the probability that a random variable differs by a given amount from its mean. The Markov bound holds solely under the hypothesis that the variable is nonegative and the expectation exists, i.e., is finite. The Chebyshev bound holds solely under the hypothesis that the variance exists. (Remember that the variance can exist only if the expectation does.)

Theorem 2.1 (Markov’s Bound). If R is a non-negative random variable with finite expectation, then for all x > 0,

Pr \{R ≥ x\} ≤ \frac{E [R]}{x}

Setting x = c · E [R] allows Markov’s Theorem to be expressed in an alternate form:

Corollary 2.2. If R is a non-negative random variable with finite expectation, then for all c > 0

Pr \{R ≥ c · E [R]\} ≤ \frac{1}{c}

Theorem 2.3 (Chebyshev’s Bound). Let R be a random variable with finite variance, and let x be a positive real number. Then

Pr \{|R − E [R]| ≥ x\} ≤ \frac{Var [R]}{x^{2}}.

2.2 One-sided Chebyshev Bound

There is a version of the Chebyshev Bound which, like the Markov bound, bounds the probability that a variable exceeds its mean:

Lemma 2.4 (One-sided Chebyshev Bound). For any random variable X and real number c > 0,

Pr \{X − E [X] ≥ c\} ≤ \frac{Var [X]}{Var [X] + c^{2}} .

The proof is similar to the way the standard Chebyshev bound of Theorem 2.3 is proved from the Markov bound.

Proof. Let μ = E [X]. For any d > 0,

X − μ ≥ c iff X − μ + d ≥ c + d,

and since c + d > 0, this last inequality implies (X − μ + d)^{2} ≥ (c + d)^{2}. Hence,

Pr {X − μ ≥ c} ≤ Pr {(X − μ + d)^{2} ≥ (c + d)^{2}}
≤ \frac{E [(X − μ + d)^{2}]}{(c + d)^{2}}  [by Markov]
= \frac{E [(X − μ)^{2} + 2d(X − μ) + d^{2}]}{(c + d)^{2}}
= \frac{E [(X − μ)^{2}] + 2d(E [X] − μ) + d^{2}}{(c + d)^{2}}  [by linearity of E [·]]
= \frac{Var [X] + d^{2}}{(c + d)^{2}}  [since E [X] − μ = 0]

Letting d = Var [X] /c—the value which minimizes this last expression—gives

Pr \{X − μ ≥ c\} ≤ \frac{Var [X] + (Var [X] /c)^{2}}{(c + Var [X] /c)^{2}}
= \frac{Var [X]}{c^{2} + Var [X]}.

3 Team Problems

Problem 1. An urn contains red and blue colored balls. The fraction of red balls is r where 0 ≤ r ≤ 1. A gambler repeatedly pulls a ball at random from the urn. That is, at any point during succesive pulls, each ball in the urn is equally likely to be the next one pulled. The gambler puts the ball back into the urn before making the next pull. He keeps pulling balls until he pulls two red balls in a row.

The sequence of pulls by the Gambler can be regarded as a sequence of tries, where the first try begins with the first ball pulled. Each try consists of a sequence of pulled balls continuing until either a blue ball, or two red balls in a row, are pulled. For example, if the colors of pulled balls are RBBBRBRR, then there are five tries which we indicate with slashes: /RB/B/B/RB/RR/. Note that each try consists of one or two consecutive balls.

(a) What is the expected length of the ith try, assuming that there are at least i tries? Solution: Given that there is an ith try, it is of length 1 iff it starts with a blue ball. It is of length 2 iff it consists of 2 red balls. Hence,

E [length of ith try | there is an ith try] = 1 · (1 − r) + 2 · r = 1 + r.

(b) What is the expected number of tries? Solution: A series of tries ends iff only the last try consists of two reds. We know from lecture that the “mean time to failure” is the reciprocal of the probability of failure, so E [num tries] is the 1/Pr(2 reds) = 1/r^{2}.

(c) Write a simple expression in terms of your answers to the previous parts of this problem for the expected number of balls pulled by the Gambler. Briefly justify your reasoning. Solution: Wald’s Thm applies because E [length of ith try | there is an ith try] is the same expression from part (a) for all i. Hence,

E [num pulls] = E [pulls per try] · E [num tries] = (1 + r)\frac{1}{r^{2}} .

Problem 2. Let R_{1}, R_{2}, R_{3} be pairwise independent random variables. Prove that

Var [R_{1} + R_{2} + R_{3}] = Var [R_{1}] + Var [R_{2}] + Var [R_{3}] .

Solution: Let m_{i} = E [R_{i}] and R = R_{1} + R_{2} + R_{3}, so E [R] = m_{1} + m_{2} + m_{3} by linearity of expectation. Now

Var [R_{1} + R_{2} + R_{3}]
= E [R^{2}] − E^{2} [R] [by formula for Var [R]]
= E [R_{1}^{2} + R_{2}^{2} + R_{3}^{2} + 2(R_{1}R_{2} + R_{1}R_{3} + R_{2}R_{3})] − (m_{1} + m_{2} + m_{3})^{2}
= E [R_{1}^{2}] + E [R_{2}^{2}] + E [R_{3}^{2}] + 2(E [R_{1}R_{2}] + E [R_{1}R_{3}] + E [R_{2}R_{3}]) − (m_{1} + m_{2} + m_{3})^{2}

[by linearity of E [·]]

= E [R_{1}^{2}] + E [R_{2}^{2}] + E [R_{3}^{2}] + 2(m_{1}m_{2} + m_{1}m_{3} + m_{2}m_{3}) − (m_{1} + m_{2} + m_{3})^{2}

[because E [XY] = E [X] E [Y] for independent X, Y]

= E [R_{1}^{2}] − m_{1}^{2} + E [R_{2}^{2}] − m_{2}^{2} + E [R_{3}^{2}] − m_{3}^{2} [by algebra]
= Var [R_{1}] + Var [R_{2}] + Var [R_{3}] [by formula for Var [R_{i}]].

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 actors.

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.

(a) 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. Solution: Get a reliable test by repeatedly asking randomly chosen psychologists to do the diagnosis and computing the fraction, f, of “normal” diagnoses. Let s > 1/2 be the probability of a “normal” diagnosis on a sociopathic patient. Diagnose normal if f is closer to 1/2 than to s. By diagnosing independently enough times, there is small probability that f differs from the expected value of a diagnosis by very much (the expected value is either 1/2 or s depending on whether or not the patient is normal—we don’t know which). By the Law of Large Numbers, by Chebyshev’s bound, or by the estimation of the binomial distribution as used in the Gallup Poll example from the lecture notes, if we diagnose enough times, we can make this probability as small as desired, so the probability of a correct diagnosis can be as close to 1 as desired.

(b) Is the independence assumption reasonable? Solution: No. Some sociopaths may be bad liars and be detected by most psychologists, and others may be such good liars, they are diagnosed as normal by most psychologists. Also, there may be several expert psychologists whose diagnoses are more reliable than average; this implies if one expert diagnoses “normal,” the diagnosis is likely to be correct, making it more likely that another expert will also correctly diagnose “normal,” so their diagnoses will not be independent of each other.

Problem 4. Suppose you have learned that the average graduating MIT student’s total number of credits is 200.

(a) Knowing only this average, find a best possible 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 a century—that is, assume that there is no theoretical upper bound on the possible number of credits a student may earn.) Solution: Use Markov’s inequality Pr {X ≥ c} ≤ E [X] /c, with c = 235, to obtain the upper bound 200/235 ≈ 0.85.

(b) (Added 5/7/99 10pm) Suppose you are also told that no student can graduate with fewer than 170 units. How does this allow you to improve your previous answer? Solution: We can now apply Markov’s inequality to the nonnegative variable X − 170, obtaining Pr {X ≥ 235} = Pr {X − 170 ≥ 235 − 170} ≤ E [X − 170] /(235−170) = 30/65 ≈ 0.46.

(c) Now suppose you further learn that the standard deviation of the total credits per graduating student is 7. Give a best possible bound on the fraction of students who can graduate with at least 235 credits. Solution: Use the one-way Chebyshev inequality Pr \{X ≥ E [X] + cσ_{X}\} ≤ \frac{1}{1+c^{2}} with c = 5 to get an upper bound of 1/26.