The Halting ProblemSolution to the Halting ProblemWhy Tree Diagrams WorkA Posteriori ProbabilitiesA Coin ProblemA Variant of the Two Coins ProblemMedical TestingConditional Probability PitfallsCarnival DiceOther IdentitiesDiscrimination LawsuitOn-Time Airlines6.042/18.062J Mathematics for Computer Science April 21, 2005 Srini Devadas and Eric Lehman Lecture Notes Conditional Probability Suppose that we pick a random person in the world. Everyone has an equal chance of being selected. Let A be the event that the person is an MIT student, and let B be the event that the person lives in Cambridge. What are the probabilities of these events? Intuitively, we’re picking a random point in the big ellipse shown below and asking how likely that point is to fall into region A or B: ABset of all peoplein the worldset of people wholive in Cambridgeset of MITstudentsThe vast majority of people in the world neither live in Cambridge nor are MIT students, so events A and B both have low probability. But what is the probability that a person is an MIT student, given that the person lives in Cambridge? This should be much greater— but what it is exactly? What we’re asking for is called a conditional probability; that is, the probability that one event happens, given that some other event definitely happens. Questions about conditional probabilities come up all the time: • What is the probability that it will rain this afternoon, given that it is cloudy this morning? • What is the probability that two rolled dice sum to 10, given that both are odd? • What is the probability that I’ll get four-of-a-kind in Texas No Limit Hold ’Em Poker, given that I’m initially dealt two queens? There is a special notation for conditional probabilities. In general, Pr (A | B) denotes the probability of event A, given that event B happens. So, in our example, Pr (A | B) is the probability that a random person is an MIT student, given that he or she is a Cam-bridge resident.2 Conditional Probability How do we compute Pr (A | B)? Since we are given that the person lives in Cambridge, we can forget about everyone in the world who does not. Thus, all outcomes outside event B are irrelevant. So, intuitively, Pr (A | B) should be the fraction of Cambridge residents that are also MIT students; that is, the answer should be the probability that the person is in set A ∩ B (darkly shaded) divided by the probability that the person is in set B (lightly shaded). This motivates the definition of conditional probability: Pr (A | B) = Pr (A ∩ B) Pr (B) If Pr (B) = 0, then the conditional probability Pr (A | B) is undefined. Probability is generally counterintuitive, but conditional probability is the worst! Con-ditioning can subtly alter probabilities and produce unexpected results in randomized algorithms and computer systems as well as in betting games. Yet, the mathematical definition of conditional probability given above is very simple and should give you no trouble— provided you rely on formal reasoning and not intuition. 1 The Halting Problem The Halting Problem is the canonical undecidable problem in computation theory that was first introduced by Alan Turing in his seminal 1936 paper. The problem is to determine whether a Turing machine halts on a given blah, blah, blah. Anyway, much more impor-tantly, it is the name of the MIT EECS department’s famed C-league hockey team. In a best-of-three tournament, the Halting Problem wins the first game with probability 1 2. In subsequent games, their probability of winning is determined by the outcome of the previous game. If the Halting Problem won the previous game, then they are envigorated by victory and win the current game with probability 2 3. If they lost the previous game, then they are demoralized by defeat and win the current game with probablity only 1 3. What is the probability that the Halting Problem wins the tournament, given that they win the first game? 1.1 Solution to the Halting Problem This is a question about a conditional probability. Let A be the event that the Halting Problem wins the tournament, and let B be the event that they win the first game. Our goal is then to determine the conditional probability Pr (A | B). We can tackle conditional probability questions just like ordinary probability prob-lems: using a tree diagram and the four-step method. A complete tree diagram is shown below, followed by an explanation of its construction and use.3 Conditional Probability 2/3L1/2W1/2W1/3L2/3L1/3W2/3LL1/3W2/3W1/31st gameoutcome2nd gameoutcome3rd gameoutcomeprobabilityoutcome1/31/181/91/91/181/3event B:win the1st game?event A:win theseries?WWWLWWLLLWWLWLLLoutcomeStep 1: Find the Sample Space Each internal vertex in the tree diagram has two children, one corresponding to a win for the Halting Problem (labeled W) and one corresponding to a loss (labeled L). The complete sample space is: S = {W W, W LW, W LL, LW W, LW L, LL} Step 2: Define Events of Interest The event that the Halting Problem wins the whole tournament is: T = {W W, W LW, LW W }And the event that the Halting Problem wins the first game is: F = {W W, W LW, WLL}The outcomes in these events are indicated with checkmarks in the tree diagram. Step 3: Determine Outcome Probabilities Next, we must assign a probability to each outcome. We begin by labeling edges as spec-ified in the problem statement. Specifically, The Halting Problem has a 1/2 chance of winning the first game, so the two edges leaving the root are each assigned probability 1/2. Other edges are labeled 1/3 or 2/3 based on the outcome of the preceding game. We then find the probability of each outcome by multiplying all probabilities along the corresponding root-to-leaf path. For example, the probability of outcome W LL is: 1 1 2 1 = 2 · 3 · 3 94 Conditional Probability Step 4: Compute Event Probabilities We can now compute the probability that The Halting Problem wins the tournament, given that they win the first game: Pr (A | B) = Pr (A ∩ B) Pr (B) Pr ({W W, W LW }) = Pr ({W W, W LW, W LL}) 1/3 + 1/18 = 1/3 + 1/18 + 1/9 7 = 9 We’re done! If the Halting Problem wins the first game, then they win the whole tourna-ment with probability 7/9. 1.2 Why Tree Diagrams Work We’ve now settled into a routine of solving probability problems using tree diagrams. But we’ve left a big question unaddressed: what is the mathematical
View Full Document
Unlocking...