Monty Hall problem

From Freepedia

Image:Monty-hall.png

The Monty Hall problem is a puzzle in game theory involving 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 player is shown three closed doors; behind one is a car, and behind each of the other two is a goat. The player is allowed to open one door, and will win whatever is behind the door. However, after the player selects a door but before opening it, the game host (who knows what's behind the doors) must open another door, revealing a goat. The host then must offer the player an option to switch to the other closed door. Does switching improve the player's chance of winning the car? The answer is yes — switching results in the chances of winning the car improving from 1/3 to 2/3.

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.

Contents

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 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.
—(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 Parade Magazine version.

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

An unambiguous statement of the problem, with explicit constraints on the host as described by Mueser and Granberg:

  • Behind each of three doors is either a goat or a car (two goats, one car), with the car behind each door with equal probability.
  • The player picks one of the three doors. The contents are not revealed.
  • The game host knows what is behind each door.
  • The game host must open one of the remaining doors and must make the offer to switch.
  • The game host will always open a door with a goat.
    • That is, if the player picks a door with a goat, the game host picks the other door with a goat.
    • And if the player picks the door with a car, the game host randomly picks either of the two doors with a goat.
  • The host offers the player the chance to either claim what is behind the originally-chosen door, or to switch, claiming what is behind the one remaining door.

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.

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

  • The player picks goat number 1. The game host picks the other goat. Switching will win the car.
  • The player picks goat number 2. The game host picks the other goat. Switching will win the car.
  • The player picks the car. The game host picks either of the two goats. Switching will lose.

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

The problem would be different if there were no initial choice, or if the game host picked a door to open at random, or 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. 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 make the offer to switch and must reveal a goat that the player has a 2/3 chance of winning by switching.

Another way of getting the solution is that assuming you will switch, the only way of losing would be by originally picking the winning door (i.e. you inititially bet that you'll find the prize; if you did pick the winning door, switching will make you lose). By switching, you essentially invert your chances from 1/3 to 2/3 (i.e. by switching you actually bet on not having chosen the winning door in the first pick).

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 reasoning about which door he opens are ignored. Because there are two doors to choose from, there is then 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. The most notable counterexample is card counting in some card games, which allows players to use information on past events to their advantage. Past information helps also in the Monty Hall problem, as shown below.

Venn diagrams

The probability that the car is behind the remaining door can be calculated with the Venn diagrams below. After choosing door 3, 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.

Image:Monty4.png

The host now opens door 1. Since the host must always open a door revealing a goat, and does not open a door at random, 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 1, 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 1 or 2, by opening door 1 the host has revealed it must be behind door 2.

Image:Monty3.png

A more formal probability diagram is shown below.

Image:Monty.GIF

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 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.

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: people are so used to judge probability problems using ratios that they don't notice uniqueness any more. 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.

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 their 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's theorem

Analysis of the problem using Bayes's 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 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 the game host will open door 1, p(O1), is 1/2 since there is equal probability the car is behind door 1 (forcing the host to open door 2) or door 2 (forcing the host to open door 1) and if the car is behind neither door by the given assumptions the host opens one of them randomly. But when the car is behind door 2, the game host will certainly open door 1, by the assumptions; that is, p(O1|C2) = 1. Hence the probability that the car is behind door 2 given that the game host opens door 1 is

<math>

P(C2|O1) = \frac{P(O1|C2) P(C2)}{P(O1)} 

= \frac{1 \times \frac{1}{3}}{\frac{1}{2}}
= \frac{2}{3}

</math>

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. Here is the output of a sample run of the Perl language simulation for the default 3000 iterations (alternative implementations are also available):

Wikisource has original text related to this article:
Playing 3000 games...
Grand totals:
Sticker has won 1013 times
Switcher has won 1987 times

The win rates, 33.8% vs. 66.2% (with about 2% margin of error), closely approximate the theoretical probabilities.

Card game experiment

Consider the problem as a card game where the goal is to end up with the ace of spades. Doing this may make the answer easier to understand and provides a way anyone can run a simple experiment. Take three cards including the ace of spades. Shuffle them and deal one to the "player" while you (the "host") keep two. Looking at the two, discard one so long as it is not the ace of spades. Should the player switch? To amplify the effect, do this again using the entire deck. Deal one card to the player while you keep 51 and (looking at the 51) discard 50 so long as none of them are the ace of spades. By switching, the player will nearly always win (51 out of 52 times).

For a more thorough walkthrough of this experiment, consider two players. Player A and Player B take the 13 diamond cards out of a standard deck of cards. The cards are shuffled, and then Player A receives one card face-down and is not permitted to see the card's face. Player B receives the other 12 cards, and he may look at them. Both players are trying to wind up with the ace of diamonds in their hand.

Question: Player A received one card. Player B received twelve cards. What are the chances that the ace is currently in Player B's hand? Answer: Twelve out of thirteen.

Player B has twelve cards and can examine the card faces. At least eleven of them are not the ace. Player B takes out eleven non-ace cards from his hand and lays them down face-up.

Question: Player B did not discard the ace (which he may not even have). No cards have moved from one hand to the other. Therefore, if the ace was in Player B's hand at the beginning, it is still there now. What are the chances that the ace is currently in Player B's hand? Answer: Since the chances depend only on whether or not he originally received the ace, the chances are still twelve out of thirteen.

Player A now has an option: he can stay with the one card he was originally dealt (which he hasn't looked at), or he can switch his hand with Player B's hand, which was originally dealt twelve of the thirteen cards.

Question: If the ace is currently in Player B's hand, Player A will win by switching hands. What are the chances that Player A will win by switching hands? Answer: Since the chances depend only on whether or not Player B originally got the ace, the chances are twelve out of thirteen.

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 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 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.

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.

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.

Origins

Despite similarity in their name, the game used in the Monty Hall problem is not related to three card monte, a gambling game in which the player has to find a single winning card among three face-down cards. The Monty Hall problem is essentially a reasoning problem and involves no deception or tricks, whereas in three card monte the dealer 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 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.

Anecdotes

After this problem's (correct) solution was discussed in Marilyn vos Savant's "Ask Marilyn" question-and-answer column of Parade magazine in 1990, vos Savant estimates 10,000 readers including several hundred mathematics professors wrote in to declare that her solution was wrong. An equally contentious discussion of vos Savant's article took place in Cecil Adams's column The Straight Dope. The version of the problem published in the magazine leaves critical assumptions about the host's behavior unstated. This version does not say that the host must always make the offer to switch or that the host must always open a door to reveal a goat. Without these constraints other solutions are possible, although nearly all the criticism was not based on the lack of these assumptions. Even with these assumptions explicitly stated many people insistently argue the correct answer must be wrong. Over 40 papers have been published about this problem in academic journals and the popular press.

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 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 got it wrong.

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.
  • 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).

External links

Retrieved from "http://en.freepedia.org/Monty_Hall_problem.html"


Views
Personal tools
In other languages
Similar Links