Misplaced Pages

This is an old revision of this page, as edited by Wisq (talk | contribs) at 03:30, 3 May 2005 (→Problem summary: Reordered, added 'always pick a goat'.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Monty Hall problem is a puzzle in probability that is loosely based on the American game show Let's Make a Deal; the name comes from the show's host Monty Hall. In this puzzle a contestant, say Jane, is shown three closed doors; behind one is a car, and behind each of the other two is a goat. Jane is allowed to open one door, and will win whatever is behind the door she opens; however, after Jane has selected a door but before she actually opens it, the host (who knows what is behind each door) opens one of the other doors to show that there is a goat behind it, and asks Jane whether she wants to change her mind and switch to the other closed door. Does Jane improve her chance of winning the car by switching or does it make no difference?

The question has generated heated debate. The difficulty arises when someone assumes that Monty is choosing elements at random - he is not in the majority of the cases. What most often occurs is that you pick a loser (2/3 chance). At this point, Monty must choose the only other losing door, and the only remaining door has the prize. There is no randomness in his choice. The other third of the cases, you have chosen the right door, and then Monty chooses a wrong door at random - but this is less likely. The whole issue is more intuitively obvious when dealing with larger numbers - say 100 or 1000. The key is to realize that two choices are being made; one by you which is probabilistic regardless, one by Monty, which is not probabilistic most of the time. (see Conditional probability).

The problem may be considered a paradox -- not in the sense of leading to a logical self-contradiction, but the sense that the mathematically verifiable answer contradicts what common intuition suggests the answer should be. The paradox is resolved once you realize that Monty is not acting as a free agent, but is constrained in his choice by yours. Two-thirds of the time, he is simply revealing the only remaining goat (as you have already chosen the first one).

Problem and solution

The problem

Here is a famous statement of the problem, from a letter from Craig F. Whitaker to Marilyn vos Savant's column in Parade Magazine in 1990 (as quoted by Bohl, Liberatore, and Nydick):

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 No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

This is a restatement of the problem as given by Steve Selvin in a letter to the American Statistician (February, 1975). As stated, the problem is an extrapolation from the game show; Monty Hall did open a wrong door to build excitement, but did not allow contestants to change their choice. As Monty Hall wrote to Selvin:

And if you ever get on my show, the rules hold fast for you -- no trading boxes after the selection.
—(letsmakeadeal.com)

Selvin's subsequent letter to the American Statistician (August, 1975) appears to be the first use of the term "Monty Hall problem".

An essentially identical problem appeared as the "three prisoners problem" in Martin Gardner's Mathematical Games column in 1959. Gardner's version makes the selection procedure explicit, avoiding the unstated assumptions in the version given here.

Problem summary

A concise statement of the problem:

• The contestant picks one of three doors. The contents are not revealed.
• Monty knows what is behind every door.
• Monty will always pick a goat.
  • If the contestant picks a goat, Monty picks the other goat.
  • If the contestant picks the car, Monty picks either of the two goats.
• The contestant is asked whether to stay with their first choice, or switch to the one remaining door.

Do the contestant's odds increase by switching?

The solution

The solution to the problem is yes; the chance of winning the car is doubled when the contestant switches to another door rather than sticking with the original choice.

There are three possible scenarios, all with equal probability (1/3):

• The contestant picks goat number one. Monty picks goat number two. Switching will win the car.
• The contestant picks goat number two. Monty picks goat number one. Switching will win the car.
• The contestant picks the car. Monty picks either of the two goats. Switching will lose.

In the first two scenarios, the contestant wins by switching. The third scenario is the only one where he wins by staying. Since two out of three scenarios win by switching, the odds of winning by switching are 2/3.

When the contestant chooses a door, there is a 1/3 chance of choosing the car; there is a 2/3 chance of not choosing the car. When the host opens a door to reveal a goat, there is still a probability of 2/3 that the contestant has not chosen the car. (Knowing where one of the goats is does not change the probability of the original decision.) Therefore, if the contestant switches to the only remaining choice, there is now a probability of 2/3 that he or she has chosen the door with the car.

The problem would be completely different if there was no initial choice. If Monty always had two goats to choose from, and the contestant was only asked for a choice once a goat was revealed (with two doors remaining), the odds would be 1/2. In the original problem, it is because the contestant has a 2/3 chance of eliminating one of Monty's goats that Monty's decision reveals the correct answer 2/3 of the time.

• See also Empirical solution of the Monty Hall problem

Aids to understanding

Venn diagram

The probability that the car is behind the remaining door can be calculated with the Venn diagrams below. Here, the contestant chooses door 3.

File:Monty2.gif

Increasing the number of doors

It may be easier for the reader to appreciate the result by considering a hundred doors instead of just three. In this case there are 99 doors with goats behind them and 1 door with a prize. The contestant picks a door; 99% of the time, the contestant will pick a door with a goat. So, there is almost no chance that he chose the right door! Monty then opens 98 of the other doors revealing 98 goats and offers the contestant the chance to switch to the other unopened door. On 99 out of 100 occasions the door the contestant can switch to will contain the prize as 99 out of 100 times the contestant first picked a door with a goat. At this point a rational contestant should always switch.

Probability that first choice is wrong

Another way of phrasing why the player should switch: By switching, the player is ensuring that he will win if he originally picked a goat. The probability of picking a goat was 2/3, so the player should switch.

Combining doors

Instead of one door being opened and thus eliminated from the game, it may equivalently be regarded as combining two doors into one, as a door containing a goat is essentially the same as a door with nothing behind it. In essence, this means the player has the choice of either sticking with their original choice of door, or choosing the sum of the contents of the two other doors. Clearly, the chances of the prize being in the other two doors is twice as high. Notice how the above assumptions play a role here: The reason switching is equivalent to taking the combined contents is that Monty Hall is required to open a door with a goat.

Bayes' theorem

For the least reliance on verbiage and the most on formal mathematics, an approach using Bayes' theorem may be best. It also makes explicit the effect of the assumptions given earlier. Consider the position when door 1 has been chosen and no door has been opened. The probability that the car is behind door 2, p(C2), is plainly 1/3, as it may equally well be in any of the three places. The probability that Monty will open door 3, p(O3), is 1/2; if there can be any doubt, enumeration of cases will confirm this. But when the car is behind door 2, Monty will certainly open door 3, by the assumptions; that is, p(O3|C2) = 1. Hence the probability that the car is behind door 2 given that Monty opens door 3 is

${\displaystyle P(C2|O3)={\frac {P(O3|C2)P(C2)}{P(O3)}}={\frac {1\times {\frac {1}{3}}}{\frac {1}{2}}}={\frac {2}{3}}}$

Opposing player

Consider the game as a two-player game in which Contestant A chooses a door. Monty then opens a goat door. And Contestant B opens the remaining door. Since the first contestant will choose the car door only 1 in 3 times, the second contestant will win the car 2 out of 3 times. Thus, the car is behind the remaining door 2 out of 3 times.

Effect of opening a door

This analysis of the problem considers the player's options in terms of Staying or Switching, and the probabilities of each strategy paying off. Here's what the probabilities would be if Monty didn't open a door after the player's initial choice:

• Staying: The player can only win by Staying if the car happens to be behind the door the player first picked. Since there's a ${\displaystyle {\begin{matrix}{\frac {1}{3}}\end{matrix}}}$ chance that the car is behind that door, the player's chance of winning by Staying is ${\displaystyle {\begin{matrix}{\frac {1}{3}}\end{matrix}}}$.
• Switching: The player can only win by Switching if the car isn't behind the door the player first picked, and if the player selects the correct door out of the two remaining when he/she decides to switch. There is a ${\displaystyle {\begin{matrix}{\frac {2}{3}}\end{matrix}}}$ chance that the car is behind one of those two doors, but only a ${\displaystyle {\begin{matrix}{\frac {1}{2}}\end{matrix}}}$ chance that the player will select the correct one; since both these conditions must be met, the chance of winning by Switching is ${\displaystyle \left({\begin{matrix}{\frac {2}{3}}\end{matrix}}\times {\begin{matrix}{\frac {1}{2}}\end{matrix}}\right)}$, or ${\displaystyle {\begin{matrix}{\frac {1}{3}}\end{matrix}}}$.

In this version, where Monty gives no additional information, the chances of winning by Staying or by Switching are the same. Here's what happens to the probabilities when Monty opens (and thus eliminates as a choice) a door that he knows contains a goat:

• Staying: The player still can only win by Staying if the car happens to be behind the door the player first picked. Since there's still a ${\displaystyle {\begin{matrix}{\frac {1}{3}}\end{matrix}}}$ chance that the car is behind that door, the player's chance of winning by Staying is still ${\displaystyle {\begin{matrix}{\frac {1}{3}}\end{matrix}}}$.
• Switching: The player still can only win by Switching is if the car isn't behind the door the player first picked. However, there are no longer two doors to pick from once the decision to switch is made; Monty has opened one of those two doors and eliminated it as a choice. The chance that the car was behind one of those two doors is now the chance that it is behind the only remaining one of those two doors, ${\displaystyle {\begin{matrix}{\frac {2}{3}}\end{matrix}}}$; now that Monty has eliminated the ${\displaystyle {\begin{matrix}{\frac {1}{2}}\end{matrix}}}$ chance of guessing wrongly after deciding to switch, ${\displaystyle {\begin{matrix}{\frac {2}{3}}\end{matrix}}}$ is the player's chance of winning by Switching.

Case analysis

Let's call one of the goats A and the other one B. The order of the doors is irrelevant. The player can choose:

 (1) the door with the goat A behind ;
 (2) the door with the goat B behind ; 
 (3) the door with the car  C behind ; 

Let's analyse these three cases:

 In case (1) the host will open the B door.        Staying with A: . Switching to C: .
 In case (2) the host will open the A door.        Staying with B: . Switching to C: .
 In case (3) the host will open the A (or B) door. Staying with C: . Switching to B (or A): .

Let's add it up:

 Staying strategy   = 1/3 *  + 1/3 *  + 1/3 *  = 1/3  = 33.33% of success
 Switching strategy = 1/3 *  + 1/3 *  + 1/3 *  = 2/3  = 66.66% of success

Simulation

Instead of attempting to calculate the exact probability of winning the car, we can execute a simulation of the game and count the fraction of times the contestant wins. By the law of large numbers, this is likely to approximate the probability of winning. The following Java program simulates a million games and compares the sucess rate of the switching strategy with that of the staying strategy.

import java.security.SecureRandom;
public class MontyHall {
    public static void main(String args) {
        SecureRandom rand = new SecureRandom();
        int games = 1000000, winsWithSwitch = 0, winsWithoutSwitch = 0;
        System.out.println("Playing " + games + " games...");
        for(int i = 0; i < games; i++) {
            // Place the prize behind a door, and then let the
            // contestant choose.
            int prizeDoor = rand.nextInt(3);
            int choice = rand.nextInt(3);
            // Open a door that does not have the prize behind it.
            int openedDoor;
            if(choice == prizeDoor)
                openedDoor = (prizeDoor + 1 + rand.nextInt(2)) % 3;
            else
                openedDoor = (0 + 1 + 2) - choice - prizeDoor;
            // Let the contestant switch to the door that was NOT opened.
            int switchDoor = (0 + 1 + 2) - choice - openedDoor;
            if(choice == prizeDoor)
                winsWithoutSwitch++;
            if(switchDoor == prizeDoor)
                winsWithSwitch++;
        }
        System.out.print("Win rate with a \"don't switch\" strategy: ");
        System.out.println((double) winsWithoutSwitch / games);
        System.out.print("Win rate with a \"switch\" strategy: ");
        System.out.println((double) winsWithSwitch / games);
    }
}

See empirical solution of the Monty Hall problem for a Perl program that implements a simulation.

Variants

With several minutes remaining in the game, Monty Hall chose two contestants for the "Big Deal". Behind one of three doors was the grand prize. Each contestant was allowed to choose a door (not the same one).

In this scenario, a variant of Selvin's problem can be stated. Monty eliminates a player with a goat behind their door (if both players had a goat, one is eliminated at random, without letting the players know about it), opens the door and then offers the remaining player a chance to switch. Should the remaining player switch?

The answer is no. The reason: a switcher in this game will lose if and only if either of two initial choices of the two contestants was correct. How likely is that? Two-thirds. A sticker will win in those 2/3 of the cases. So stickers will win twice as often as switchers.

Altenatively, by enumerating possibilities; again you (player 1) play 1 (i.e. choose door 1) and the other player (player 2) plays 2 (i.e. chooses door 2):

         Ejected Player  Probability    Switch Strategy     Stick Strategy
 1 2 3    
 C G G   2               1/3            Lose                Win
 G C G   1               1/3            x                   x   
 G G C   1               1/6            x                   x
         2               1/6            Win                 Lose

x: switch/stick strategy is irrelevant because you (player 1) are the ejected player.

Player 1 wins 1/3 of the time with the stick strategy, or 1/6 of the time with the switching strategy. Half the time he is eliminated. Given that he is not eliminated there is 2/3 probability of winning with the sticking strategy.

There is a generalization of the original problem to n doors: in the first step, you choose a door. Monty then opens some other door that's a loser. If you want, you may then switch your allegiance to another door. Monty will then open an as yet unopened losing door, different from your current preference. Then you may switch again, and so on. This continues until there are only two unopened doors left: your current choice and another one. How many times should you switch, and when, if at all?

The best strategy is: stick with your first choice all the way through but then switch at the very end. With this strategy, the probability of winning is (n-1)/n. This was proved by Bapeswara Rao and Rao.

Origins

The game used in the Monty Hall problem is similar to three card monte, a gambling game in which the player has to find a single winning card among three face-down cards. As in the Monty Hall problem, the dealer knows where the winning card is, but here the dealer always tries to trick the player into picking the wrong card. As the card is often a Queen court card, it is also known as Find the Lady.

An older puzzle in probability theory involves three prisoners, one of whom (already chosen at random but unknown to the prisoners) is to be executed in the morning. The first prisoner begs the guard to tell him which of the other two will go free, arguing that this reveals no information about whether he will be the victim; the guard responds by claiming that if the prisoner knows that a specific one of the other two prisoners will go free it will raise the first prisoner's subjective chance of being executed from 1/3 to 1/2. The question is whether the analysis of the prisoner or the guard is correct. In the version given by Martin Gardner, the guard then performs a particular randomizing procedure for selecting which name to give the prisoner; this gives the equivalent of the Monty Hall problem without the usual ambiguities in its presentation.

Anecdotes

After this problem's solution was discussed in Marilyn vos Savant's "Ask Marilyn" question-and-answer column of Parade magazine in 1990, many readers including several mathematics professors wrote in to declare that her solution was wrong. An equally contentious discussion of Marilyn's discussion took place in Cecil Adams's column The Straight Dope.

The Monty Hall problem is discussed, from the perspective of a boy with autism, in The Curious Incident of the Dog in the Night-time, a 2003 novel by Mark Haddon.

References

• Bapeswara Rao, V. V. and Rao, M. Bhaskara (1992). "A three-door game show and some of its variants". The Mathematical Scientist 17, no. 2, pp. 89–94
• Bohl, Alan H.; Liberatore, Matthew J.; and Nudick, Robert L. (1995). "A Tale of Two Goats ... and a Car, or The Importance of Assumptions in Problem Solutions". Journal of Recreational Mathematics 1995, pp. 1–9.
• Gardner, Martin (1959). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182.
• Selvin, Steve (1975a). "A problem in probability" (letter to the editor). American Statistician 29(1):67 (February 1975).
• Selvin, Steve (1975b). "On the Monty Hall problem" (letter to the editor). American Statistician 29(3):134 (August 1975).
• Tierney, John (1991). "Behind Monty Hall's Doors: Puzzle, Debate and Answer?", The New York Times July 21, 1991, Sunday, Section 1; Part 1; Page 1; Column 5
• vos Savant, Marilyn (1990). "Ask Marilyn" column, Parade Magazine p. 12 (Feb. 17, 1990).

External links

• THE MONTY HALL PROBLEM (at letsmakeadeal.com; quotes Monty's letter to Steve Selvin in full)
• Monty Hall Paradox (let's make a deal) (lengthy bibliography)
• Monty Hall Dilemma (Monty Hall simulation, discussions, and generalization)
• Grand Illusions Explanation and various simulators

• Mathematical recreations and puzzles
• Paradoxes