Massachusetts Institute of Technology Handout 49 6.042J/18.062J: Mathematics for Computer Science May 5, 2000 Professors David Karger and Nancy Lynch

Mini-Quiz 13

1. What is your name?

Solution. Sir Galahad of Camelot.

□

2. What is your favorite color?

Solution. Blue. No yel– Auuuuuuuugh!

□

3. Suppose you gamble at a roulette wheel with an equal number of red and black slots. If you bet $1000 on red the first spin and double your bet on each successive spin. What is your expected winnings after any finite number of spins? Solution. $0.

□

4. If you bet on red until the first time you win, how much do you expect to win? Solution. $1000.

□

5. Why wouldn’t you try this strategy?

Solution. You expect to spend an infinite stake before you win.

□

Tutorial 13 Problems

Problem 1 Kyle is playing his favorite computer game: X-Files Adventures. The game begins with Mulder in the main hallway of a space ship searching for clues to the Truth. The hallway has 5 doors. One door exits the space ship. Another door leads back to the main hallway after a journey that passes through one intermediate room. A third door leads back to the main hallway after a journey that passes through two intermediate rooms. A fourth door leads back to the main hallway after a journey that passes through three intermediate rooms. The fifth door leads directly back to the main hallway. What is behind each door is permuted at random using a uniform distribution each time Mulder returns to the main hallway.

(a) How many times can Mulder expect to be in the main hallway before he leaves the ship?

Solution.

Let the random variable R be the number of times Mulder selects a door before he selects the exit. We need to find Ex(R). This is just a mean-time-to-failure style calculation. Ex(R) = ∑_{i=0}^{∞} Pr(R > i) = \frac{1}{p} = 5 Since Mulder expects to be in the main hallway each time he selects a door, the desired value is 5.

□

(b) Any time Mulder enters a room (not the hallway), there is an even chance that he will find a new clue (independent of whether he found a clue in any previous time he may have entered this room).

Let J be the number of journeys Mulder takes before leaving the ship. Let the random variable C_{i} be the number of clues Mulder finds on his ith journey around the ship. If i > J, we define C_{i} = 0.

Let the random variable C the number of clues Mulder would find on any trip through a uniformly chosen, non-exit door. Argue that

Pr(C_{i} = x | J ≥ i) = Pr(C = x)

for all i ≥ 1 and all x in the range of C.

Solution.

If J ≥ i then Mulder selects a nonexit door on the ith try. In that case, C_{i} and C have the same distribution. Thus, Pr(C_{i} = x) = Pr(C = x).

□

(c) How many clues should Mulder expect to find before he exits the ship?

Solution.

We want to compute Ex(C_{1} + C_{2} + ⋯ + C_{J}). In the previous part we have shown that the variables C, C_{i}, and J have the properties necessary for the application of Wald’s Theorem. Therefore we know that

Ex(C_{1} + C_{2} + ⋯ + C_{J}) = Ex(C_{1}) · Ex(J).

Since the last door Mulder selects is always the exit, J = R−1 (where R is as in the previous part). Thus, the expected number of journeys, Ex(J) = 4.

To find Ex(C_{1}), the expected number of clues in the first journey, consider four equally likely cases. Case i, 0 <= i <= 3 corresponds to a journey with i intermediate rooms.

By linearity of expectation, the expected number of clues found during the journey is

Ex(C_{1}) = ∑_{i=0}^{3} Ex(C_{1i})

where C_{1i} is the expected number of clues found during a journey through i intermediate rooms.

Again we can use linearity of expectations again to decompose C_{1i} into i individual rooms where Mulder can expect to find 1/2 a clue. So on any journey Mulder expects to find ∑_{i=0}^{3} i/2 · 1/4 = 3/4 clues. Therefore, Mulder expects to find 3 clues before he exits the ship.

□

Problem 2 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 somewhat less likely to correctly diagnose a real sociopath than not—sociopaths are really good liars. Suppose the probability of an errant diagnosis by a random psychologist is known.

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 judgments independently.

(a) Given a set of independent diagnoses of a patient by n randomly chosen psychologists, give a reliable function to decide if a patient is a sociopath.

Solution.

Let p_{fn} > 1/2 be the probability of a random psychologist diagnosing a sociopath as normal (false negative). Let p_{fp} = 1/2 be the probability of a random psychologist diagnosing normal patient as a sociopath (false positive). (Similarly, define the probability of a true negative diagnosis to be p_{tn} = 1 − p_{fp} = 1/2 and the probability of a true positive diagnosis to be p_{tp} = 1 − p_{fn} < 1/2.)

After n independent trials, we will have s “sociopath” diagnoses. Compute the fraction s/n such diagnoses. Decide 1 (the patient is a sociopath) if s/n is closer to p_{tp} than to p_{fp}. Decide 0 otherwise. In other words, let the “decision value” d = \frac{p_{tp}+p_{fp}}{2} . Decide 1 iff s/n < d. Note that p_{tp} < d < 1/2 = p_{fp} so we decide the patient is a sociopath only if substantially fewer than 1/2 our chosen psychologists say so!

□

(b) Use the binomial distribution to compute the probability of an erroneous decision after n trials, given that the patient is not a sociopath.

Solution.

We can compute the probability of a wrong decision given that the patient is not a sociopath as follows:

δ_{norm} = Pr(s/n < d) (The probability we decided the patient was a sociopath.)
= Pr(s < nd)
= F_{n,p_{fp}}(nd) (Cumulative binomial distribution for the random variable s.)
= F_{n,1/2}(d) (Note: d < 1/2.)
= \frac{1 − d}{1 − 2d}f_{n,1/2}(nd) (Theorem 4.1, Lecture 22.)

□

(c) Use the binomial distribution to compute the probability of an erroneous decision after n trials, given that the patient is a sociopath.

Solution.

We can compute the probability of a wrong decision given that the patient is a sociopath as 4 Handout 49: Tutorial 13 Problems

follows:

δ_{soc} = Pr(s/n > d) (The probability we decided the patient was not a sociopath.)
= Pr(\frac{n − s}{n} < 1 − d) (n − s = number of “normal” diagnoses)
= Pr(n − s < n(1 − d))
= F_{n,1−p_{tp}}(n(1 − d)) (Note: d > p_{tp} ⇒ 1 − d < 1 − p_{tp})
= F_{n,p_{fn}}(n(1 − d)) (Pr(“normal”diagnosis) = 1 − Pr(“sociopath” diagnosis))
= \frac{1 − (1 − d)}{1 − (1 − d)/p_{fn}} f_{n,p_{fn}}(n(1 − d)) (Theorem 4.1, Lecture 22.)
= \frac{dp_{fn}}{p_{fn} − 1 + d}f_{n,p_{fn}}(n(1 − d))

□

(d) Bound the error of this decision method with a closed-form formula. Solution.

δ ≤ max (δ_{norm}, δ_{soc})
= max (\frac{1 − d}{1 − 2d}f_{n,1/2}(nd), \frac{dp_{fn}}{p_{fn} − 1 + d}f_{n,p_{fn}}(n(1 − d)))

= max ((\frac{1 − d}{1 − 2d}) \frac{2^{(d log_{2}(2d)+(1−d) log_{2}(\frac{1}{2(1−d)}))·n} \overbrace{e^{a_{n}−a_{dn}−a_{n−dn}}}^{∼1}}{\sqrt{2πd(1 − d)n}},

(\frac{dp_{fn}}{p_{fn} − 1 + d}) \frac{2^{((1−d) log_{2}(\frac{p_{fn}}{1−d})+d log_{2}( \frac{1−p_{fn}}{d} ))·n} \overbrace{e^{a_{n}−a_{(1−d)n}−a_{n−(1−d)n}}}^{∼1}}{\sqrt{2π(1 − d)dn}})

□

(e) How many independent diagnoses would be needed to get less than 1% error? Solution. The question is under specified. The number of diagnoses depends on p_{fn}. In the worst case, p_{fn} = 1/2 and sociopaths are completely indistinguishable from normal patients. Notice that in this case, d = 0 and δ is undefined.

If p_{fn} is known and greater than 1/2 we can find n by trial and error.

□

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

Solution.

Not really. The psychologists decisions are not independently random. They are based on observations of the patients behavior. A psychologist diagnoses sociopathy if the patients exhibits certain behavior that the psychologist believes differentiates a sociopath from a normal patient. If the patient’s behavior is consistent from one trial to the next and a group of psychologists agree on the behavior typical of sociopaths, then the diagnoses will not be independent of each other.

□