The monty hall problem Afra Zomorodian January 20, 1998 Introduction This is a short report about the infamous"Monty Hall Problem. The report contains two solutions to the problem: an analytic and a numerical one. The analytic solution will use probability theory and corresponds to a mathematician's point of view in solving problems. The numerical solution simulates the problem on a large scale to arrive at the solution and therefore corresponds to computer scientist's point of view The monty hall Problem The Monty Hall Problem's origin is from the TV show, "Lets Make A Deal"hosted by Monty Hall. The statement of the problem is as follows [LR94 You are a contestant in a game show in which a prize is hidden behind one of three curtains you will win the prize if you select the correct curtain. After you have picked one curtain but before the curtain is lifted, the emcee lifts one of the other curtains, revealing an empty stage, and asks if you would like to switch from your current selection to the remaining curtain. How will your chances change if you switch? The question was originally proposed by a reader of"Ask Marilyn, a column by Marilyn vos Savant in Parade Magazine in 1990 and her solution caused an uproar among Mathematicians, as the answer to the problem is unintuitive: while most people would respond that switching should not matter, the contestant's chances for winning in fact double if she switches curtains. Part of the controversy, however, was caused by the lack of agreement on the statement of the problem itself We will use the above version. For accounts of the controversy as well as solutions and interactive applets, see Don98 Proof by Probability Theory without loss of generality, let us call the curtain picked by the contestant curtain a, the curtain opened by Monty Hall curtain b, and the third curtain c. We will define the following events A, B, and C are the events that the prize is behind curtains a, b, and c respectively .O is the event that Monty Hall opens curtain b The Monty Hall Problem can be restated as follows: Is Pr()= Prclo?
The Monty Hall Problem Afra Zomorodian January 20, 1998 Introduction This is a short report about the infamous “Monty Hall Problem.” The report contains two solutions to the problem: an analytic and a numerical one. The analytic solution will use probability theory and corresponds to a mathematician’s point of view in solving problems. The numerical solution simulates the problem on a large scale to arrive at the solution and therefore corresponds to a computer scientist’s point of view. The Monty Hall Problem The Monty Hall Problem’s origin is from the TV show, “Let’s Make A Deal” hosted by Monty Hall. The statement of the problem is as follows [LR94]: “You are a contestant in a game show in which a prize is hidden behind one of three curtains. you will win the prize if you select the correct curtain. After you have picked one curtain but before the curtain is lifted, the emcee lifts one of the other curtains, revealing an empty stage, and asks if you would like to switch from your current selection to the remaining curtain. How will your chances change if you switch?” The question was originally proposed by a reader of “Ask Marilyn”, a column by Marilyn vos Savant in Parade Magazine in 1990 and her solution caused an uproar among Mathematicians, as the answer to the problem is unintuitive: while most people would respond that switching should not matter, the contestant’s chances for winning in fact double if she switches curtains. Part of the controversy, however, was caused by the lack of agreement on the statement of the problem itself. We will use the above version. For accounts of the controversy as well as solutions and interactive applets, see [Don98]. Proof by Probability Theory Without loss of generality, let us call the curtain picked by the contestant curtain a, the curtain opened by Monty Hall curtain b, and the third curtain c. We will define the following events: • A, B, and C are the events that the prize is behind curtains a, b, and c respectively. • O is the event that Monty Hall opens curtain b. The Monty Hall Problem can be restated as follows: Is P r{A | O} = P r{C | O}? 1
By Bayes's Theorem, we have PrOoF APRon Proy PrOOF rICProl cy PrOf We assume that the prize is randomly placed behind the curtains We compute all of the conditional probabilities for event O, as we'll need them to compute PrO PrO A)= 1/2, if the prize is behind a, Monty Hall can open either b or c PrOB 0, if the prize is behind b, Monty Hall cannot open curtain b Prole) 1, if the prize is behind c, Monty Hall can only open curtain b To compute Prof, we note that O=On A)U(On B)U(OnC) and A,OnB, and OnC are mutually exclusive events as the prize can be behind one curtain only. So, Prof= PronA+PronBPrloncy PrlAPr(| A)+ Pr( B+PrICPrlolCy /3)·(1/2)+(1/3)·0+(1/3)·1 Therefore. we have Pr(AJO- PriA)PrIoJA 1/3)·(1/2) /2 Furthermore, we have. PrIolo)= Pr PrICProlcy PrOf (1/3)·1 In other words, if we switch we double our chances of winning. We could have also arrived at this answer by noting PrBlo)=0 and therefore PrCO=1-Pr(Alof=1-1/3=2/3 Generalized Monty Hall Problem With the same analysis, we can show that if there are n curtains and the emcee opens n-2 of them after the contestant's initial choice, the contestant's chances of winning will be 1/n if she decides to stay with the initial choice and(n-1)/n if she switches. In other words, the contestant's chance of winning goes up by a factor of n-1 in case of switchin
By Bayes’s Theorem, we have: P r{A | O} = P r{A}P r{O | A} P r{O} P r{C | O} = P r{C}P r{O | C} P r{O} We assume that the prize is randomly placed behind the curtains: P r{A} = P r{B} = P r{C} = 1/3 We compute all of the conditional probabilities for event O, as we’ll need them to compute P r{O}: P r{O | A} = 1/2, if the prize is behind a, Monty Hall can open either b or c P r{O | B} = 0, if the prize is behind b, Monty Hall cannot open curtain b P r{O | C} = 1, if the prize is behind c, Monty Hall can only open curtain b To compute P r{O}, we note that O = (O ∩ A) ∪ (O ∩ B) ∪ (O ∩ C) and O ∩ A, O ∩ B, and O ∩ C are mutually exclusive events as the prize can be behind one curtain only. So, P r{O} = P r{O ∩ A} + P r{O ∩ B}P r{O ∩ C} = P r{A}P r{O | A} + P r{B}P r{O | B} + P r{C}P r{O | C} = (1/3) · (1/2) + (1/3) · 0 + (1/3) · 1 = 1/2. Therefore, we have: P r{A | O} = P r{A}P r{O | A} P r{O} = (1/3) · (1/2) 1/2 = 1/3. Furthermore, we have: P r{C | O} = P r{C}P r{O | C} P r{O} = (1/3) · 1 1/2 = 2/3. In other words, if we switch we double our chances of winning. We could have also arrived at this answer by noting P r{B | O} = 0 and therefore P r{C | O} = 1 − P r{A | O} = 1 − 1/3 = 2/3. Generalized Monty Hall Problem With the same analysis, we can show that if there are n curtains and the emcee opens n−2 of them after the contestant’s initial choice, the contestant’s chances of winning will be 1/n if she decides to stay with the initial choice and (n−1)/n if she switches. In other words, the contestant’s chance of winning goes up by a factor of n − 1 in case of switching. 2
Solution by simulatio The Monty Hall Problem Theoretical for Staying 33 1/30%-- Theoretical for Switching 66.7 时中M lumber of ga A program monty. c for simulating the generalized Monty Hall Problem was implemented in ANSI-C and is included. Using the program, data was generated for the two following graphs The graph above shows the convergence of the probabilities to the theoretical values for 3 curtains(each set of game was independently run. The graph plots the percentage of winning if the contestant always chooses to stay with the original door versus if the contestant chooses to switch. The graph clearly reaffirms the theoretical result The graph on the next page shows what happens when we increase the number of curtains from 3 to 100. For each value of curtains, 100,000 games were played. The graph also plots the theoretical values as above. The numerical and theoretical values match extremely well Conclusion In conclusion, I'd like to note that the Monty Hall Problem is unintuitive because it is hard to see when information is brought into the problem, i.e. Monty Hall's opening of the curtain causes the conditional probabilities to change. A related problem, the Prisoner's Problem, has the same structure but asks a different question and may be found in [LR94
Solution by Simulation 0 20 40 60 80 100 0 100 200 300 400 500 600 700 800 900 1000 Percentage Won Number of Games The Monty Hall Problem Staying Switching Theoretical for Staying 33 1/3% Theoretical for Switching 66.7 % A program monty.c for simulating the generalized Monty Hall Problem was implemented in ANSI-C and is included. Using the program, data was generated for the two following graphs. The graph above shows the convergence of the probabilities to the theoretical values for 3 curtains (each set of game was independently run.) The graph plots the percentage of winning if the contestant always chooses to stay with the original door versus if the contestant chooses to switch. The graph clearly reaffirms the theoretical result. The graph on the next page shows what happens when we increase the number of curtains from 3 to 100. For each value of curtains, 100,000 games were played. The graph also plots the theoretical values as above. The numerical and theoretical values match extremely well. Conclusion In conclusion, I’d like to note that the Monty Hall Problem is unintuitive because it is hard to see when information is brought into the problem, i.e. Monty Hall’s opening of the curtain causes the conditional probabilities to change. A related problem, the Prisoner’s Problem, has the same structure but asks a different question and may be found in [LR94]. 3
Generalized Monty Hall Problem(100,000 Games) 100 Theoretical for Staying(1/n)--. Theoretical for Switching(n-1Vn 50 Number of doors References Don98 Dennis Donovan. The Www Tackles The Monty Hall Problem, 1998 http://math.rice.edu/ddonovan/montyurl.html. LR94 Thomas H. Cormen, Charles E Leiserson, and Ronald L. Rivest. Introduction to Algo- rithms. The MIT Press, Cambridge, Massachusetts, 1994
0 20 40 60 80 100 10 20 30 40 50 60 70 80 90 100 Percentage Won Number of Doors Generalized Monty Hall Problem (100,000 Games) Staying Switching Theoretical for Staying (1/n) Theoretical for Switching (n-1)/n References [Don98] Dennis Donovan. The WWW Tackles The Monty Hall Problem, 1998. http://math.rice.edu/˜ddonovan/montyurl.html. [LR94] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 1994. 4