《Mathematics for Computer》Introduction to Probability

6.042/18.] Mathematics for Computer Science April 14, 2005 Srini devadas and Eric Lehman Lecture notes Introduction to Probability Probability is the last topic in this course and perhaps the most important. Many Igorithms rely on randomization. Investigating their correctness and performance re- quires probability theory. Moreover, many aspects of computer systems, such as memory management, branch prediction, packet routing, and load balancing are designed around probabilistic assumptions and analyses. Probability also comes up in information theory cryptography, artificial intelligence, and game theory. Beyond these engineering applica- tions, an understanding of probability gives insight into many everyday issues, such as polling, DNA testing, risk assessment, investing, and gambling So probability is good stuff 1 Monty Hall In the September 9, 1990 issue of Parade magazine, the columnist Marilyn vos Savant responded to this letter Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say number 1, and the host, who knows what's behind the doors, opens another door, say number 3, which has a goat. He says to you, Do you want to pick door number 2?" Is it to your advantage to switch your choice of doors? Craig. F. Whitaker Columbia, MD The letter roughly describes a situation faced by contestants on the 1970s game show Let's Make a Deal, hosted by Monty Hall and Carol Merrill. Marilyn replied that the con testant should indeed switch. But she soon received a torrent of letters- many from mathematicians- telling her that she was wrong. The problem generated thousands of hours of heated debate Yet this isis an elementary problem with an elementary solution. Why was there much dispute? Apparently, most people believe they have an intuitive grasp of probability stark contrast to other branches of mathematics; few people believe they have n intuitive ability to compute integrals or factor large integers mately 100% of those people are wrong. In fact, everyone who has studied probability at

6.042/18.062J Mathematics for Computer Science April 14, 2005 Srini Devadas and Eric Lehman Lecture Notes Introduction to Probability Probability is the last topic in this course and perhaps the most important. Many algorithms rely on randomization. Investigating their correctness and performance re￾quires probability theory. Moreover, many aspects of computer systems, such as memory management, branch prediction, packet routing, and load balancing are designed around probabilistic assumptions and analyses. Probability also comes up in information theory, cryptography, artificial intelligence, and game theory. Beyond these engineering applica￾tions, an understanding of probability gives insight into many everyday issues, such as polling, DNA testing, risk assessment, investing, and gambling. So probability is good stuff. 1 Monty Hall In the September 9, 1990 issue of Parade magazine, the columnist Marilyn vos Savant responded to this letter: Suppose you’re on a game show, and you’re given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say number 1, and the host, who knows what’s behind the doors, opens another door, say number 3, which has a goat. He says to you, ”Do you want to pick door number 2?” Is it to your advantage to switch your choice of doors? Craig. F. Whitaker Columbia, MD The letter roughly describes a situation faced by contestants on the 1970’s game show Let’s Make a Deal, hosted by Monty Hall and Carol Merrill. Marilyn replied that the con￾testant should indeed switch. But she soon received a torrent of letters— many from mathematicians— telling her that she was wrong. The problem generated thousands of hours of heated debate. Yet this is is an elementary problem with an elementary solution. Why was there so much dispute? Apparently, most people believe they have an intuitive grasp of probability. (This is in stark contrast to other branches of mathematics; few people believe they have an intuitive ability to compute integrals or factor large integers!) Unfortunately, approxi￾mately 100% of those people are wrong. In fact, everyone who has studied probability at

2 Introduction to Probability length can name a half-dozen problems in which their intuition led them astray--often The way to avoid errors is to distrust informal arguments and rely instead on a rigor on intuition, then there are lots of compelling financial deals we'd love to offer you!8 ous, systematic approach. In short: intuition bad, formalism good. If you insist on relyin 1.1 The Four-Step method Every probability problem involves some sort of randomized experiment, process, or game And each such problem involves two distinct challenges 1. How do we model the situation mathematically? 2. How do we solve the resulting mathematical problem? In this section, we introduce a four-step approach to questions of the form, What is the In this approach, we build a probabilistic model step-by-step, formalizing the original question in terms of that model. Remarkably, the structured thinking that this approach imposes reduces many famously-confusing problems to near triviality. For example, as you'll see, the four-step method cuts through the confusion sur rounding the Monty Hall problem like a Ginsu knife. However, more complex probability questions may spin off challenging counting, summing, and approximation problems which, fortunately, you've already spent weeks learning how to solve 1.2 Clarifying the Problem Craig s original letter to Marilyn vos Savant is a bit vague, so we must make some as- sumptions in order to have any hope of modeling the game formally 1. The car is equally likely to be hidden behind each of the three doors 2. The player is equally likely to pick each of the three doors, regardless of the cars location 3. After the player picks a door, the host must open a different door with a goat behind it and offer the player the choice of staying with the original door or switch 4. If the host has a choice of which door to open, then he is equally likely to select each In making these assumptions, were reading a lot into Craig Whitaker's letter. Other nterpretations are at least as defensible, and some actually lead to different answers. But let's accept these assumptions for now and address the question, What is the probability that a player who switches wins the car

2 Introduction to Probability length can name a half­dozen problems in which their intuition led them astray— often embarassingly so. The way to avoid errors is to distrust informal arguments and rely instead on a rigor￾ous, systematic approach. In short: intuition bad, formalism good. If you insist on relying on intuition, then there are lots of compelling financial deals we’d love to offer you! 1.1 The Four­Step Method Every probability problem involves some sort of randomized experiment, process, or game. And each such problem involves two distinct challenges: 1. How do we model the situation mathematically? 2. How do we solve the resulting mathematical problem? In this section, we introduce a four­step approach to questions of the form, “What is the probability that —– ?” In this approach, we build a probabilistic model step­by­step, formalizing the original question in terms of that model. Remarkably, the structured thinking that this approach imposes reduces many famously­confusing problems to near triviality. For example, as you’ll see, the four­step method cuts through the confusion sur￾rounding the Monty Hall problem like a Ginsu knife. However, more complex probability questions may spin off challenging counting, summing, and approximation problems— which, fortunately, you’ve already spent weeks learning how to solve! 1.2 Clarifying the Problem Craig’s original letter to Marilyn vos Savant is a bit vague, so we must make some as￾sumptions in order to have any hope of modeling the game formally: 1. The car is equally likely to be hidden behind each of the three doors. 2. The player is equally likely to pick each of the three doors, regardless of the car’s location. 3. After the player picks a door, the host must open a different door with a goat behind it and offer the player the choice of staying with the original door or switching. 4. If the host has a choice of which door to open, then he is equally likely to select each of them. In making these assumptions, we’re reading a lot into Craig Whitaker’s letter. Other interpretations are at least as defensible, and some actually lead to different answers. But let’s accept these assumptions for now and address the question, “What is the probability that a player who switches wins the car?

Introduction to Probability 1.3 Step 1 Find the Sample Space Our first objective is to identify all the possible outcomes of the experiment. a typical experiment involves several randomly-determined quantities. For example, the Monty Hall ga olves three such quantities 1. The door concealing the car 2. The door initially chosen by the player 3. The door that the host opens to reveal a goat Every possible combination of these randomly-determined quantities is called an out come. The set of all possible outcomes is called the sample space for the experiment. a tree diagram is a graphical tool that can help us work through the four-step ap proach when the number of outcomes is not too large or the problem is nicely structured In particular, we can use a tree diagram to help understand the sample space of an exper- iment. The first randomly-determined quantity in our experiment is the door concealing the prize. We represent this as a tree with three branches location A B In this diagram, the doors are called A, B, and C instead of 1, 2, and 3 because well be adding a lot of other numbers to the picture later. Now, for each possible location of the rize, the player could initially chose any of the three doors. We represent this by adding a second layer to the tree

Introduction to Probability 3 1.3 Step 1: Find the Sample Space Our first objective is to identify all the possible outcomes of the experiment. A typical experiment involves several randomly­determined quantities. For example, the Monty Hall game involves three such quantities: 1. The door concealing the car. 2. The door initially chosen by the player. 3. The door that the host opens to reveal a goat. Every possible combination of these randomly­determined quantities is called an out￾come. The set of all possible outcomes is called the sample space for the experiment. A tree diagram is a graphical tool that can help us work through the four­step ap￾proach when the number of outcomes is not too large or the problem is nicely structured. In particular, we can use a tree diagram to help understand the sample space of an exper￾iment. The first randomly­determined quantity in our experiment is the door concealing the prize. We represent this as a tree with three branches: car location C A B In this diagram, the doors are called A, B, and C instead of 1, 2, and 3 because we’ll be adding a lot of other numbers to the picture later. Now, for each possible location of the prize, the player could initially chose any of the three doors. We represent this by adding a second layer to the tree:

Introduction to Probability guess location Finally, the host opens a door to reveal a goat. The host has either one choice or two, depending on the position of the car and the door initially selected by the player. For example, if the prize is behind door a and the player picks door B, then the host must open door C. However, if the prize is behind door A and the player picks door A, then the host could open either door B or door C. All of these possibilities are worked out in a hird layer of the tree

4 Introduction to Probability car location player’s initial guess C C A B A B C A B C A B Finally, the host opens a door to reveal a goat. The host has either one choice or two, depending on the position of the car and the door initially selected by the player. For example, if the prize is behind door A and the player picks door B, then the host must open door C. However, if the prize is behind door A and the player picks door A, then the host could open either door B or door C. All of these possibilities are worked out in a third layer of the tree:

Introduction to Probability door outcome car location (A, C, B) (B, B, A) Now let's relate this picture to the terms we introduced earlier: the leaves of the tree represent outcomes of the experiment, and the set of all leaves represents the sample space Thus, for this experiment, the sample space consists of 12 outcomes. For reference weve labeled each outcome with a triple of doors indicating door concealing prize, door initially chosen, door opened to reveal a goat) In these terms, the sample space is the set (A,A,B),(A,A,C),(A,B,C),(A,C,B),(B,A,C),(B,B,A), (B,B,C),(B,C,A),(C,A,B),(C,B,A),(C,C,A),(C,C,B) The tree diagram has a broader interpretation as well: we can regard the whole exper iment as"walk"from the root down to a leaf, where the branch taken at each stage randomly determined. Keep this interpretation in mind; we'll use it again later 1.4 Step 2: Define Events of Interest Our objective is to answer questions of the form What is the probability that where the horizontal line stands for some phrase such as"the player wins by switching the player initially picked the door concealing the prize, or"the prize is behind door C Almost any such phrase can be modeled mathematically as an event, which is defined to be a subset of the sample space

� � Introduction to Probability 5 car location player’s initial guess door revealed C C C A B A B A B C A B C A B A C A C C B A B outcome B (A,A,B) (A,A,C) (A,B,C) (B,A,C) (B,B,A) (B,B,C) (B,C,A) (C,A,B) (C,B,A) (C,C,A) (C,C,B) (A,C,B) Now let’s relate this picture to the terms we introduced earlier: the leaves of the tree represent outcomes of the experiment, and the set of all leaves represents the sample space. Thus, for this experiment, the sample space consists of 12 outcomes. For reference, we’ve labeled each outcome with a triple of doors indicating: (door concealing prize, door initially chosen, door opened to reveal a goat) In these terms, the sample space is the set: (A, A, B), (A, A, C), (A, B, C), (A, C, B), (B, A, C), (B, B, A), S = (B, B, C), (B, C, A), (C, A, B), (C, B, A), (C, C, A), (C, C, B) The tree diagram has a broader interpretation as well: we can regard the whole exper￾iment as “walk” from the root down to a leaf, where the branch taken at each stage is randomly determined. Keep this interpretation in mind; we’ll use it again later. 1.4 Step 2: Define Events of Interest Our objective is to answer questions of the form “What is the probability that —– ?”, where the horizontal line stands for some phrase such as “the player wins by switching”, “the player initially picked the door concealing the prize”, or “the prize is behind door C”. Almost any such phrase can be modeled mathematically as an event, which is defined to be a subset of the sample space

Introduction to Probability For example the event that the prize is behind door c is the set of outcomes: {(C,A,B),(C,B,A),(C,C,A),(C,C,B)} The event that the player initially picked the door concealing the prize is the set of out comes. {(A,A,B),(A,A,C),(B,B,A),(B,B,C),(C,C,A),(C,C,B)} And what were really after, the event that the player wins by switching, is the set of outcomes. {(A,B,C),(A,C,B),(B,A,C),(B,C,A),(C,A,B),(C,B,A)} Lets annonate our tree diagram to indicate the outcomes in this event door (A, A, B) (A, A, C) car (B, A, C) B (B, B, A) (B, B,c) (B,C, A) (C, A, B) (C, C, A) (C, C, B) Notice that exactly half of the outcomes are marked meaning that the player wins by switching in half of all outcomes. You might be tempted to conclude that a player who switches wins with probability This is wrong. The reason is that these outcomes are not all equally likely, as we'll see shortly 1.5 Step 3: Determine Outcome Probabilities So far weve enumerated all the possible outcomes of the experiment. Now we must start sessing the likelihood of those outcomes. In particular, the goal of this step is to assign

6 Introduction to Probability For example, the event that the prize is behind door C is the set of outcomes: {(C, A, B),(C, B, A),(C, C, A),(C, C, B)} The event that the player initially picked the door concealing the prize is the set of out￾comes: {(A, A, B),(A, A, C),(B, B, A),(B, B, C),(C, C, A),(C, C, B)} And what we’re really after, the event that the player wins by switching, is the set of outcomes: {(A, B, C),(A, C, B),(B, A, C),(B, C, A),(C, A, B),(C, B, A)} Let’s annonate our tree diagram to indicate the outcomes in this event. car location player’s initial guess door revealed switch wins? C C C A B A B A B C A B C A B A C A C C B A B outcome X X X X X X B (A,A,B) (A,A,C) (A,B,C) (B,A,C) (B,B,A) (B,B,C) (B,C,A) (C,A,B) (C,B,A) (C,C,A) (C,C,B) (A,C,B) Notice that exactly half of the outcomes are marked, meaning that the player wins by switching in half of all outcomes. You might be tempted to conclude that a player who switches wins with probability 1 2 . This is wrong. The reason is that these outcomes are not all equally likely, as we’ll see shortly. 1.5 Step 3: Determine Outcome Probabilities So far we’ve enumerated all the possible outcomes of the experiment. Now we must start assessing the likelihood of those outcomes. In particular, the goal of this step is to assign

Introduction to Probability each outcome a probability, which is a real number between 0 and 1. The sum of all outcome probabilities must be 1, reflecting the fact that exactly one outcome must occur Ultimately, outcome probabilities are determined by the phenomenon we re modeling and thus are not quantities that we can derive mathematically. However, mathematics can help us compute the probability of every outcome based on fewer and more elementary modeling decisions. In particular, we'll break the task of determining outcome probabilities to two stages 1.5.1 Step 3a: Assign Edge Probabilities First, we record a probability on each edge of the tree diagram. These edge-probabilities are determined by the assumptions we made at the outset: that the prize is equally likely to be behind each door, that the player is equally likely to pick each door, and that the host is equally likely to reveal each goat, if he has a choice. Notice that when the host has no choice regarding which door to open, the single branch is assigned probability 1 initial 12B (A, A, B) 12c 1/3B (A, B, c) (A, C, B) (B, A, c) 1/3 112A (B, B, A) 位2c (B, B,c) (C, A, B) (C, B, A) (C, C, A) (C, C, B) 1.5.2 Step 3b: Compute Outcome Probabilities Our next job is to convert edge probabilities into outcome probabilities. This is a purely mechanical process: the probability of an outcome is equal to the product of the edge-probabilities

Introduction to Probability 7 each outcome a probability, which is a real number between 0 and 1. The sum of all outcome probabilities must be 1, reflecting the fact that exactly one outcome must occur. Ultimately, outcome probabilities are determined by the phenomenon we’re modeling and thus are not quantities that we can derive mathematically. However, mathematics can help us compute the probability of every outcome based on fewer and more elementary modeling decisions. In particular, we’ll break the task of determining outcome probabilities into two stages. 1.5.1 Step 3a: Assign Edge Probabilities First, we record a probability on each edge of the tree diagram. These edge­probabilities are determined by the assumptions we made at the outset: that the prize is equally likely to be behind each door, that the player is equally likely to pick each door, and that the host is equally likely to reveal each goat, if he has a choice. Notice that when the host has no choice regarding which door to open, the single branch is assigned probability 1. car location player’s initial guess door revealed switch wins? C C C A B A B A B C A B C A B A C A C C 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1 1 1 1 1 1 1/2 B 1/2 1/2 1/2 A B 1/2 1/2 outcome X X X X X X B (A,A,B) (A,A,C) (A,B,C) (B,A,C) (B,B,A) (B,B,C) (B,C,A) (C,A,B) (C,B,A) (C,C,A) (C,C,B) (A,C,B) 1.5.2 Step 3b: Compute Outcome Probabilities Our next job is to convert edge probabilities into outcome probabilities. This is a purely mechanical process: the probability of an outcome is equal to the product of the edge­probabilities

Introduction to Probability on the path from the root to that outcome. For example, the probability of the topmost out- come,(A,A,B)is3.3.2=is We'll justify this process formally next time. In the meanwhile, here is a nice informal tification to tide you over. Remember that the whole experiment can be regarded walk from the root of the tree diagram down to a leaf, where the branch taken at each step is randomly determined. In particular, the probabilities on the edges indicate ho ikely the walk is to proceed along each path. For example, a walk starting at the root in our example is equally likely to go down each of the three top-level branches Now, how likely is such a walk to arrive at the topmost outcome,(A, A, B)? Well, there is a 1-in-3 chance that a walk would follow the A-branch at the top level, a l-in-3 chance it would continue along the a-branch at the second level, and 1-in-2 chance it would follow the B-branch at the third level. Thus it seems that about 1 walk in 18 should arrive at the (A, A, B)leaf, which is precisely the probability we assign it anyway, let's record all the outcome probabilities in our tree diagram pla door revealed outcome wins? probability car location (A, B,c) (B, A,c) 1/3B 1/3 1/2c (B, B, c) (B, C, A) (C, A, B) (C, B, A) Specifying the probability of each outcome amounts to defining a function that maps each outcome to a probability. This function is usually called Pr In these terms, weve

8 Introduction to Probability on the path from the root to that outcome. For example, the probability of the topmost out￾come, (A, A, B) is 111 3 · 3 · 2 = 1 18 . We’ll justify this process formally next time. In the meanwhile, here is a nice informal justification to tide you over. Remember that the whole experiment can be regarded as a walk from the root of the tree diagram down to a leaf, where the branch taken at each step is randomly determined. In particular, the probabilities on the edges indicate how likely the walk is to proceed along each path. For example, a walk starting at the root in our example is equally likely to go down each of the three top­level branches. Now, how likely is such a walk to arrive at the topmost outcome, (A, A, B)? Well, there is a 1­in­3 chance that a walk would follow the A­branch at the top level, a 1­in­3 chance it would continue along the A­branch at the second level, and 1­in­2 chance it would follow the B­branch at the third level. Thus, it seems that about 1 walk in 18 should arrive at the (A, A, B) leaf, which is precisely the probability we assign it. Anyway, let’s record all the outcome probabilities in our tree diagram. car location player’s initial guess door revealed switch wins? C C C A B A B A B C A B C A B A C A C C 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1 1 1 1 1 1 1/2 B 1/2 1/2 1/2 A B 1/2 1/2 outcome X X X X X X probability 1/18 1/18 1/9 1/9 1/9 1/18 1/18 1/9 1/9 1/9 1/18 1/18 B (A,A,B) (A,A,C) (A,B,C) (B,A,C) (B,B,A) (B,B,C) (B,C,A) (C,A,B) (C,B,A) (C,C,A) (C,C,B) (A,C,B) Specifying the probability of each outcome amounts to defining a function that maps each outcome to a probability. This function is usually called Pr. In these terms, we’ve

Introduction to Probability just determined that Pr(A, A, B) 1 Pr(A,A, C)=18 (A, B, C) etc Earlier, we noted that the sum of all outcome probabilties must be 1 since exactly one outcome must occur. We can now express this symbolically ∑P(n)=1 In this equation, S denotes the sample space Though Pr is an ordinary function, just like your old friends f and g from calculi we will subject it to all sorts of horrible notational abuses that f and g were mercifully spared. Just for starters, all of the following are common notations for the probability of n outcome r Pr(a) Pr(a) Pr[zl p(a) A sample space S and a probability function Pr: S-0, 1 together form a probability space. Thus, a probability space describes all possible outcomes of an experiment and the probability of each outcome. a probability space is a complete mathematical model of an experiment 1.6 Step 4: Compute Event Probabilities We now have a probability for each outcome, but we want to determine the probability of an event. We can bridge this gap with a definition: the probability of an event is the sum of the probabilities of the outcomes it contains. As a notational matter, the probability of an event E CSis written Pr(E). Thus, our definition of the probability of an event can be written P(E)=∑Pr(x) For example, the probability of the event that the player wins by switching is Pr(switching wins)=Pr(A, B, C)+Pr(A,C, B)+ Pr(B, A, C) Pr(B, C, A)+ Pr(C, A, B)+Pr(C, B, A ×9 1111 9+9

� � Introduction to Probability 9 just determined that: 1 Pr (A, A, B) = 18 1 Pr (A, A, C) = 18 1 Pr (A, B, C) = 9 etc. Earlier, we noted that the sum of all outcome probabilties must be 1 since exactly one outcome must occur. We can now express this symbolically: Pr (x) = 1 x∈S In this equation, S denotes the sample space. Though Pr is an ordinary function, just like your old friends f and g from calculus, we will subject it to all sorts of horrible notational abuses that f and g were mercifully spared. Just for starters, all of the following are common notations for the probability of an outcome x: Pr (x) Pr(x) Pr[x] Pr x p(x) A sample space S and a probability function Pr : S → [0, 1] together form a probability space. Thus, a probability space describes all possible outcomes of an experiment and the probability of each outcome. A probability space is a complete mathematical model of an experiment. 1.6 Step 4: Compute Event Probabilities We now have a probability for each outcome, but we want to determine the probability of an event. We can bridge this gap with a definition: the probability of an event is the sum of the probabilities of the outcomes it contains. As a notational matter, the probability of an event E ⊆ S is written Pr (E). Thus, our definition of the probability of an event can be written: Pr (E) = Pr (x) x∈E For example, the probability of the event that the player wins by switching is: Pr (switching wins) = Pr (A, B, C) + Pr (A, C, B) + Pr (B, A, C) + Pr (B, C, A) + Pr (C, A, B) + Pr (C, B, A) 1 1 1 1 1 1 = + + + + + 9 9 9 9 9 9 2 = 3

duction to Probability It seems Marilyns answer is correct; a player who switches doors wins the car with prob- ability 2/3! In contrast, a player who stays with his or her original door wins with proba bility 1/3, since staying wins if and only if switching loses Were done with the problem! We didn't need any appeals to intuition or ingenious analogies. In fact, no mathematics more difficult than adding and multiplying fractions was required. The only hard part was resisting the temptation to leap to an"intuitively obvious" answer 1.7 An Alternative Interpretation of the monty hall problem Was Marilyn really right? A more accurate conclusion is that her answer is correct pro- vided we accept her interpretation of the question. There is an equally plausible interpretation in which Marilyns answer is wrong. Notice that Craig Whitaker's original letter does not say that the host is required to reveal a goat and offer the player the option to switch, merely that he did these things. In fact, on the Let's make a Deal show, Monty Hall some- times simply opened the door that the contestant picked initially. Therefore, if he wanted to, Monty could give the option of switching only to contestants who picked the correct door initially. If this case, switching never works! 2 Strange Dice Let's play Strange Dice! The rules are simple. There are three dice, A, B, and C. Not surprisingly, the dice are numbered strangely, as shown below B C The number on each concealed face is the same as the number on the opposite, exposed face. The rules are simple. You pick one of the three dice, and then I pick one of the two remainders We both roll and the player with the higher number wins

10 Introduction to Probability It seems Marilyn’s answer is correct; a player who switches doors wins the car with prob￾ability 2/3! In contrast, a player who stays with his or her original door wins with proba￾bility 1/3, since staying wins if and only if switching loses. We’re done with the problem! We didn’t need any appeals to intuition or ingenious analogies. In fact, no mathematics more difficult than adding and multiplying fractions was required. The only hard part was resisting the temptation to leap to an “intuitively obvious” answer. 1.7 An Alternative Interpretation of the Monty Hall Problem Was Marilyn really right? A more accurate conclusion is that her answer is correct pro￾vided we accept her interpretation of the question. There is an equally plausible interpretation in which Marilyn’s answer is wrong. Notice that Craig Whitaker’s original letter does not say that the host is required to reveal a goat and offer the player the option to switch, merely that he did these things. In fact, on the Let’s Make a Deal show, Monty Hall some￾times simply opened the door that the contestant picked initially. Therefore, if he wanted to, Monty could give the option of switching only to contestants who picked the correct door initially. If this case, switching never works! 2 Strange Dice Let’s play Strange Dice! The rules are simple. There are three dice, A, B, and C. Not surprisingly, the dice are numbered strangely, as shown below: A B C 2 1 3 6 7 5 9 4 8 The number on each concealed face is the same as the number on the opposite, exposed face. The rules are simple. You pick one of the three dice, and then I pick one of the two remainders. We both roll and the player with the higher number wins