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?

2. What is your favorite color?

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?

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

5. Why wouldn’t you try this strategy?

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?

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

(c) How many clues should Mulder expect to find 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.

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

Handout 49: Tutorial 13 Problems 3 (c) Use the binomial distribution to compute the probability of an erroneous decision after n trials, given that the patient is a sociopath.

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

(e) How many independent diagnoses would be needed to get less than 1% error?

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