Monty Hall problem

File:Montyflip.png

In search of a new car, the player picks door 1. The game host then opens door 3 to reveal a goat and offers to let the player pick door 2 instead of door 1.

The Monty Hall problem is a puzzle involving probability loosely based on the American game show Let's Make a Deal. The name comes from the show's host, Monty Hall. A widely known statement of the problem is from Craig F. Whitaker of Columbia, Maryland in a letter to Marilyn vos Savant's September 9, 1990, column in Parade Magazine (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?

The problem is also called the Monty Hall paradox, in the sense that the solution is counterintuitive, although the problem does not yield a logical contradiction. Many people incorrectly assume since there are only two doors left after the host opens one, that the remaining doors must have equal probability. However, assuming the host knows what is behind each door, always opens a door revealing a goat, and always makes the offer to switch, the host's actions do not affect the probability of the player initially choosing the car (1/3). This means the answer is yes — switching results in the chances of winning the car improving from 1/3 to 2/3.

Problem and solution

The problem, with all constraints explicit

The version of the problem popularized by Parade unfortunately leaves room for possible misunderstandings, some of which may affect the correctness of the answer. An unambiguous statement of the problem, with explicit constraints on the host, was described by Mueser and Granberg:

A thoroughly honest game-show host has placed a car behind one of three doors. There is a goat behind each of the other doors. You have no prior knowledge that allows you to distinguish among the doors. "First you point toward a door," he says. "Then I'll open one of the other doors to reveal a goat. After I've shown you the goat, you make your final choice whether to stick with your initial choice of doors, or to switch to the remaining door. You win whatever is behind the door."

You begin by pointing to door number 1. The host shows you that door number 3 has a goat.

Do the player's odds of getting the car increase by switching?

The solution

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

The player initially has a 1 in 3 chance of winning; the host has a 2 in three chance of winning. The player who presumes that he has a 1 in 2 chance of winning has forgotten something: That the host chose to knew where the prize was and would have switched his choice of which door to choose had the car been behind a given door. Therefore, when the player is offered the chance to make a choice again, there remains a 1 in three chance that he chose correctly. The dealer kept a 2 in 3 chance that the car was behind either of the two doors that he could have chosen to show to the player. However, by now offering the player the chance to switch his choice now, he is offering the player the chance to trade chances of winning. In other words, the player can now choose to select the odds that the car was behind EITHER of the two doors.

The player than has a choice: the player can stick with the original choice, and have a 1 in 3 chance of winning. Or the player can recognize

At the point the player is asked whether to switch there are three possible situations corresponding to the player's initial choice, each with equal probability (1/3):

• The player originally picked the door hiding goat number 1. The game host has shown the other goat.
• The player originally picked the door hiding goat number 2. The game host has shown the other goat.
• The player originally picked the door hiding the car. The game host has shown either of the two goats.

If the player chooses to switch, the car is won in the first two cases. A player choosing to stay with the initial choice wins in only the third case. Since in two out of three equally likely cases switching wins, the odds of winning by switching are 2/3. In other words, a player who has a policy of always switching will win the car on average two times out of the three.

Another way of thinking about this explanation is by observing that the player begins the game with a 2/3 chance of picking a door with a goat behind it. In this case the host must show the other goat, so switching turns the initial 2/3 chance of picking a goat into an equivalent chance of winning the car. Switching loses only if the player picks the car first (1/3 chance). The total expected outcome for the player who always switches is therefore a 2/3 chance of winning the car.

The problem would be different if the game host were permitted to make the offer to switch more often (or only) depending on knowledge of the player's original choice or if the host does not know what is behind each door. Some statements of the problem, notably the one in Parade Magazine, do not explicitly exclude these possibilities. For example, if the game host only offers the opportunity to switch if the contestant originally chooses the car, the odds of winning by switching are 0%. In the problem as stated above, it is because the host must reveal a goat and must make the offer to switch that the player has a 2/3 chance of winning by switching.

Aids to understanding

The most common objection to the solution is the idea that, for various reasons, the past can be ignored when assessing the probability. Thus, the first door choice and the host's forced response are ignored. Because there are two doors to choose from, many people jump to the conclusion that there must be a fifty-fifty chance of choosing the right one.

Although ignoring the past works fine for some games, like coin flipping, it doesn't work for all games. In this case what should be ignored is the opening of the door. The player's choice is between the originally picked door and the other two — opening one is simply a distraction. There's only one car. The original choice divides the possible locations of the car between the one door the player picks (1/3 chance) and the other two (2/3 chance). It is already known that at least one of the two doors contains a goat. The revealing of the goat therefore gives the player no additional information about his own door. It doesn't change the 2/3 probability that the car is still in the block of two doors.

Another possible reason for confusion is that the problem is often stated as though the host takes the player by surprise with his opening of the door. This tends to give the impression that the host is trying to confuse a player who has chosen correctly. This is why the rules are so strictly formulated in the previous section. The player may still not know these rules, but that does not alter the probability; it just means the player is discouraged from rationally considering the options and making the optimal choice.

Increasing the number of doors

It may be easier 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 player picks a door; 99% of the time, the player will pick a door with a goat. Thus, the chances of picking the winning door at first are very small: only 1%. The game host then opens 98 of the other doors revealing 98 goats and offers the player the chance to switch to the only other unopened door. On 99 out of 100 occasions the other door will contain the prize, as 99 out of 100 times the player first picked a door with a goat. At this point a rational player should always switch.

To drive the point home, one only has to imagine the host having to start with the first door and go down the line, opening the doors but skipping over only the player's door and one other door. The player can then more easily appreciate the randomness of his first choice and the large amount of information he has gained since he made that choice and then see the wisdom in switching.

There is a reasonable question to this logic: if we increase the number of doors, why does this explanation assume the host would open 98 doors to make the problem similar to the original? Why doesn't the host open 33 doors instead? That's actually an essential ingredient for the counter-intuitiveness of the original problem. It's correct to assume the host would open 98 doors in this alternate game because in the 3 door game the player has only one switching option — so the player in the 100 door game must also be presented with a single switching option. The 3 door game is misleading because the player is always presented with 1/3 proportions: he has a 1/3 chance of winning, the host reveals 1/3 of the mystery, and he is allowed to switch to the other 1/3 option — therefore all options seem equal.

Venn diagram

File:Monty4.png

The probability that the car is behind the remaining door can be calculated using Venn diagrams. After choosing door 1, for example, the player has a 1/3 chance of having selected the door with the car, leaving a 2/3 chance between the other two doors. Note that there is a 100% chance of finding a goat behind at least one of the two unchosen doors because there is only one car.

File:Monty3.png

The host now opens door 3. Since the host must always open a door revealing a goat, opening this door does not affect the chance that the car is behind the originally chosen door which remains 1/3. The car is not behind door 3, so the entire 2/3 probability of the two unchosen doors is now carried only by door 2, as shown below. Another way to state this is that if the car is behind either door 2 or 3, by opening door 3 the host has revealed it must be behind door 2.

Decision tree

Tree listing the probability of every possible outcome

More formally, the scenario can be depicted in a decision tree.

In the first two cases, wherein the player has first chosen a goat, switching will yield the car. In the third and fourth cases, since the player has chosen the car initially, a switch will lead to a goat.

The total probability that switching wins is equal to the sum of the first two events, ${1 \over 3}+{1 \over 3}={2 \over 3}$. Likewise, the probability that staying wins is ${1 \over 6}+{1 \over 6}={1 \over 3}$.

Combining doors

Instead of one losing door being opened (and thus eliminated from the possible array of choices), it may equivalently be regarded as combining two doors into one (i.e. reducing the two doors which were not chosen into a single option, since the player can't, and won't choose the opened, losing door anymore). In essence, this means the player has the choice of either sticking with the original choice of door (1/3 chances), or choosing the sum of the contents of the two other doors (2/3 chances). Notice how the game assumptions play a role here — the switching is equivalent to taking the combined contents because the game host is required to open a door with a goat.

Bayes' theorem

Analysis of the problem using Bayes' theorem has the least reliance on verbiage and the most on formal mathematics. It also makes explicit the effect of the assumptions given earlier. Consider the position when door 3 has been chosen and no door has been opened; the probabilities P(C1) that the car is behind door 1, P(C2) (car behind door 2), and P(C3) (car behind door 3), are all plainly 1/3. The probability that the game host will open door 1, P(O1), is 1/2:

$P(O1)=P(C1)\times P(O1|C1)+P(C2)\times P(O1|C2)+P(C3)\times P(O1|C3)$

$={\frac {1}{3}}\times 0+{\frac {1}{3}}\times 1+{\frac {1}{3}}\times {\frac {1}{2}}={\frac {1}{2}}$

(when the car is behind door 1, the game host will never open door 1; when the car is behind door 2, the game host will certainly open door 1; and, when the car is behind door 3, he will open door 1 or door 2 with probabilities 1/2). Hence the probability that the car is behind door 2 given that the game host opens door 1 is

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

(and, in the same way, you may find P(C1|O2) that is also 2/3).

Opposing player

Consider the game as a two-player game in which Player A chooses and opens a door. The game host then opens a goat door. Player B then gets what is behind the remaining door. Since the first player will choose the car door only 1 in 3 times, the second player will win the car 2 out of 3 times. Thus, the car is behind the remaining door 2 out of 3 times.

Simulation

Instead of attempting to calculate the exact probability of winning the car, we can execute a simulation of the game and find the fraction of times the player wins. By the law of large numbers, this is likely to approximate the probability of winning. This method has been shown to closely approximate the theoretical probabilities.

Card game experiment

There is a simple way for anyone to convince themselves that a switching strategy really does win two out of three times on the average, and that is to simulate the game with playing cards, playing Monty's role. The simulator takes three cards from an ordinary deck to represent the three doors; one 'special' card such as the Ace of Spades should be picked to represent the door with the car, and ordinary cards such as the two red twos picked to represent the goat doors.

The simulator then repeats the following procedure several times, to simulate multiple rounds of the game: One card is dealt at random to the 'player', to represent the door the player picks initially. The simulator, as Monty, then looks at the two cards in his hand and discards a red two (of which he will have at least one.) If the card remaining in the simulator's hand is the Ace of Spades, this is recorded as a round where the player would have won by switching; if the simulator is holding a red two, the round is recorded as one where staying would have won.

Running the experiment over enough rounds should not only verify that the player does win by switching two times out of three, but show the simulator why: two times out of three, after one card has been dealt to the player, the Ace of Spades is in Monty's hand -- and at that point, it is already determined whether staying or switching will win the round for the player. If this is not sufficiently convincing, the simulator can try the experiment with the entire deck, dealing one card to the player and keeping the other fifty-one: seeing that the Ace of Spades goes to Monty fifty-one times out of fifty-two, and stays with Monty no matter how many non-Ace cards he discards, should bring the point home.

The General Case

One common criticism of the Monty Hall problem is that the assumptions about the host’s behavior are not specified, such as when the original question was posed to Marilyn Vos Savant in 1990. In that instance, it was not specifically stated that the host would always open another door, or always offer a choice to switch, or even that the host must open a door containing a goat. The criticism is that without these behaviors specifically stated, the player does not have an assurance that switching is always the best option. Therefore, it has been argued that you can not conclude the best course of action unless these assumptions are explicitly stated in the problem.

In this general case, without all of the assumptions of the host behavior specified, you cannot verify that switching will be successful two-thirds of the time. Consider the various possible host behaviors: Perhaps the host only offers the option to switch when the player has chosen the door containing the car, which would mean that switching is wrong 100% of the time; or perhaps the host only offers the option to switch when the player has chosen incorrectly, meaning that switching is correct 100% of the time; or perhaps the host acts as noted in the specific version of the problem, where switching is correct two-thirds of the time. Without more-detailed information about which of these behaviors is the correct one, there is no reason to assume that any one is more or less likely.

Variants

Two players

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

In this scenario, a variant of Selvin's problem can be stated. The game host eliminates a player with a goat behind his 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 win if and only if both players originally pick goats. How likely is that? 1/3. A sticker will win in the remaining 2/3 of the cases. So stickers will win twice as often as switchers.

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

• Player 1 picks the door with the car. The host must eliminate player 2. Switching loses.
• Player 2 picks the door with the car. The host must eliminate player 1. Switching loses.
• Neither player picks the car. The host eliminates one of the players randomly. Switching wins.

Player 1 is the remaining player in the first case and half the time in the third case and switching loses (1/3 chance) twice as often as it wins (1/6 chance). Similarly, player 2 is the remaining player in the second case and half the time in the third, and loses twice as often by switching. Regardless of which player remains, there is 2/3 probability of winning with the sticking strategy.

The two player game, from the final player's point of view, sounds a lot like the single player game: the player chooses a door, a goat is revealved behind another door, and the player is given the opportunity to switch. However, the significant difference is that one player is eliminated. The process of surviving the initial elimination improves the remaining player's chances of having chosen the car initially from 1/3 to 2/3. Another way to look at this is that the chances of the remaining player having chosen the car initially is a combined probability: it is the chance that s/he chose the car initially and was not the eliminated player.

n doors

There is a generalization of the original problem to n doors: in the first step, you choose a door. The game host then opens some other door that's a loser. If you want, you may then switch your allegiance to another door. The game host 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 proven by Bapeswara Rao and Rao.

This problem is very similar to the television show Deal or No Deal, which begins with 26 cases (typically — it depends on the version of the show). The player selects one to keep, then carries on to peek at random from amongst the remaining cases. Even until the end, the player's keeper is equally likely to be the winner as any of the others that are left unrevealed. The distinction is that the player's peek might at any point reveal the grand prize, thereby eliminating it from contention. Monty on the other hand, knows the contents and is forbidden from selecting the winner. Because the player is just as likely to expose the winning case as another losing case, the Monty Hall advantage is lost at the end when the player is given the option to switch the last two cases.

Bridge principle

A common variant has been understood by bridge players for many years prior to the Vos Savant article. It is known as the principle of restricted choice. Another explanation is available at http://www.acbl-district13.org/artic003.htm

Quantum version

There is a quantum version of the paradox, which illustrates some points about the relation between classical (non-quantum) information and quantum information, as encoded in the states of quantum mechanical systems. The three doors are replaced by a quantum system allowing three alternatives, and opening a door and looking behind it is translated as making a particular measurement. The rules can be stated in this language, and once again the choice for the player is to stick by her first choice, or change to another ("orthogonal") option. The latter strategy turns out to double the chances, just as in the classical case. However, if the show host has not randomized the position of the prize in a fully quantum mechanical way, the player can do even better, and can sometimes even win the prize with certainty. There is an article explaining it and an applet demonstrating the effects.

Similar problems

• Three cards problem
• Boy or Girl
• Three Prisoners Problem

Despite similarity in their names, the game used in the Monty Hall problem is not related to three card monte.

History of the problem

The first appearance of the same general class of problem was probably the one presented in Joseph Bertrand's Calcul des probabilités (1889), known as Bertrand's Box Paradox.

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 Parade Magazine version. This 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 the prisoner 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.

In 1975, Steve Selvin wrote a pair of letters to the American Statistician (February and April issues) regarding the Monty Hall problem. The first letter presented the problem in a version close to its most popular form (the version presented by Parade Magazine is a restatement of Selvin's version.) The second letter appears to be the first use of the term "Monty Hall problem". The problem is actually an extrapolation from the game show; Monty Hall did open a wrong door to build excitement, but did not allow players 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.
—From the Let's Make a Deal website

A restated version of Selvin's problem statement appeared in Marilyn vos Savant's "Ask Marilyn" question-and-answer column of Parade magazine in September 1990. Though vos Savant gave the correct answer that switching would win 2/3rds of the time, vos Savant estimates 10,000 readers including several hundred mathematics professors wrote in to declare that her solution was wrong. As a result of the publicity the problem earned the alternative name Marilyn and the Goats.

In November 1990, an equally contentious discussion of vos Savant's article took place in Cecil Adams's column The Straight Dope. Adams initially answered, incorrectly, that the chances for the two remaining doors must each be one in two. After a reader wrote in to correct the mathematics of Adams' analysis, Adams agreed that mathematically, he'd been wrong, but said that the Parade version left critical constraints unstated, and without those constraints, the chances of winning by switching were not necessarily 2/3. Numerous readers, however, wrote in to claim that Adams had been "right the first time" and that the correct chances were one in two.

The Parade column and its response received considerable attention in the press, including a front page story in the New York Times (July 21, 1991) in which Monty Hall himself was interviewed. He appeared to understand the problem quite well, giving the reporter a demo with car keys and explaining how actual game play on Let's Make a Deal differed from the rules of the puzzle.

Over 40 papers have been published about this problem in academic journals and the popular press.

Anecdotes

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.

This situation is also addressed in a lecture by the character Charlie Eppes in an episode of the CBS drama NUMB3RS (Episode 1.13).

An account of mathematician Paul Erdős's first encounter of the problem can be found in The Man Who Loved Only Numbers. Like many others, he initially got it wrong.

The syndicated NPR program, Car Talk, featured this as one of their weekly "Puzzlers," and the answer they featured was quite clearly explained as the correct one. Transcript here. Also available in their book, "Haircut in Horse Town" (Magliozzi, Tom; Magliozzi, Ray (1998). Haircut in Horse Town: & Other Great Car Talk Puzzlers. Diane Pub Co. ISBN 0756764238.{{cite book}}: CS1 maint: multiple names: authors list (link))

See also

• Monty Hall - TV Game Show Host
• Let's Make a Deal - TV Game Show

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 Nydick, 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.
• Joseph Bertrand (1889) Calcul des probabilites
• Gardner, Martin (1959). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182. Reprinted in The Second Scientific American Book of Mathematical Puzzles and Diversions.
• Mueser, Peter R. and Granberg, Donald (1999), "The Monty Hall Dilemma Revisited: Understanding the Interaction of Problem Definition and Decision Making" (University of Missouri Working Paper 99-06). http://econwpa.wustl.edu:80/eps/exp/papers/9906/9906001.html (retrieved July 5, 2005).
• Nahin, Paul J. Duelling idiots and other probability puzzlers. Princeton University Press, Princeton, NJ: 2000, pp. 192-193. (ISBN 0-691-00979-1).
• 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 21 July 1991, Sunday, Section 1; Part 1; Page 1; Column 5
• vos Savant, Marilyn (1990). "Ask Marilyn" column, Parade Magazine p. 12 (17 February 1990). [cited in Bohl et al., 1995]
• Adams, Cecil (1990). "On 'Let's Make a Deal,' you pick Door #1. Monty opens Door #2--no prize. Do you stay with Door #1 or switch to #3?", The Straight Dope November 2 1990. http://www.straightdope.com/classics/a3_189.html (retrieved July 25, 2005).
• Tijms, Henk (2004). Understanding Probability, Chance Rules in Everyday Life. Cambridge University Press, New York, pp. 213-215.

External links

• Monty Hall Problem
• 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 at cut-the-knot
• The Monty Hall Problem - A game simulation (illustration by a demonstrative, user-friendly and versatile game simulation)
• Grand Illusions Explanation and various simulators
• Secret of Monty Hall (explanation from the bad-door side)
• Monty Hall Simulator (Simulators for the keep and change strategy in Perl, with data files representing the results of playing the game one million times with each strategy)
• A Monty Hall Simulator in Javascript (A Simulator that you can run in your web browser. )
• 'Monty Hall' over easy A short proof using a table of outcomes
• Realtime global simulation A simulation which tallies up the results from every user who has ever played.
• The Monty Hall Problem Web Page A simple presentation of the problem and its solution.
• A tree-diagram of the Monty Hall problem under the Marilyn vos Savant assumptions