 Monty Hall problem

The Monty Hall problem is a probability puzzle loosely based on the American television game show Let's Make a Deal and named after the show's original host, Monty Hall. The problem, also called the Monty Hall paradox, is a veridical paradox because the result appears odd but is demonstrably true. The Monty Hall problem, in its usual interpretation, is mathematically equivalent to the earlier Three Prisoners problem, and both bear some similarity to the much older Bertrand's box paradox.
The problem was originally posed in a letter by Steve Selvin to the American Statistician in 1975. (Selvin 1975a) (Selvin 1975b) A wellknown statement of the problem was published in Marilyn vos Savant's "Ask Marilyn" column in Parade magazine in 1990 (vos Savant 1990):
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 [but the door is not opened], 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?Vos Savant's response was that the contestant should always switch to the other door. If the car is initially equally likely to be behind each door, a player who picks Door 1 and doesn't switch has a 1 in 3 chance of winning the car while a player who picks Door 1 and does switch has a 2 in 3 chance. The host has removed an incorrect option from the unchosen doors, so contestants who switch double their chances of winning the car.
Many readers refused to believe that switching is beneficial. After the Monty Hall problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming that vos Savant was wrong. (Tierney 1991) Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept that switching is the best strategy.
The Monty Hall problem has attracted academic interest because the result is surprising and the problem is interesting to formulate. Furthermore, variations of the Monty Hall problem are made by changing the implied assumptions, and the variations can have drastically different consequences. For example, if Monty only offered the contestant a chance to switch when the contestant had initially chosen the car, then the contestant should never switch. Variations of the Monty Hall problem are given below.
Contents
Extended problem description
Certain aspects of the host's behavior are not specified in Marilyn vos Savant's wording of the problem. For example, it is not clear if the host considers the position of the prize in deciding whether to open a particular door or is required to open a door under all circumstances (Mueser and Granberg 1999). Almost all sources make the additional assumptions that the car is initially equally likely to be behind each door, that the host must open a door showing a goat, and that he must make the offer to switch. Many sources add to this the assumption that the host chooses at random which door to open if both hide goats, often but not always meaning by that, at random with equal probabilities. The resulting set of assumptions gives what is called "the standard problem" by many sources (Barbeau 2000:87). According to Krauss and Wang (2003:10), even if these assumptions are not explicitly stated, people generally assume them to be the case. A fully unambiguous, mathematically explicit version of the standard problem is:
Suppose you're on a game show and you're given the choice of three doors [and will win what is behind the chosen door]. Behind one door is a car; behind the others, goats [unwanted booby prizes]. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one [uniformly] at random. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you "Do you want to switch to Door Number 2?" Is it to your advantage to change your choice?Solutions
Simulation
A simple way to demonstrate that a switching strategy really does win two out of three times on the average is to simulate the game with playing cards (Gardner 1959b; vos Savant 1996:8). Three cards from an ordinary deck are used to represent the three doors; one 'special' card such as the Ace of Spades should represent the door with the car, and ordinary cards, such as the two red twos, represent the goat doors.
The simulation, using the following procedure, can be repeated several times to simulate multiple rounds of the game. One card is dealt facedown at random to the 'player', to represent the door the player picks initially. Then, looking at the remaining two cards, at least one of which must be a red two, the 'host' discards a red two. If the card remaining in the host's hand is the Ace of Spades, this is recorded as a round where the player would have won by switching; if the host is holding a red two, the round is recorded as one where staying would have won.
This experiment is likely to approximate the probability of winning, and running the experiment over enough rounds should not only verify that the player does win by switching two times out of three, but show why. After one card has been dealt to the player, it is already determined whether switching will win the round for the player; and two times out of three the Ace of Spades is in the host's hand.
If this is not convincing, the simulation can be done with the entire deck, dealing one card to the player and keeping the other 51 (Gardner 1959b; Adams 1990). In this variant the Ace of Spades goes to the host 51 times out of 52, and stays with the host no matter how many nonAce cards are discarded.
Another simulation, suggested by vos Savant, employs the "host" hiding a penny, representing the car, under one of three cups, representing the doors; or hiding a pea under one of three shells.
Vos Savant's solution
The solution presented by vos Savant in Parade (vos Savant 1990b) shows the three possible arrangements of one car and two goats behind three doors and the result of switching or staying after initially picking Door 1 in each case:
Door 1 Door 2 Door 3 result if switching result if staying Car Goat Goat Goat Car Goat Car Goat Car Goat Goat Goat Car Car Goat A player who stays with the initial choice wins in only one out of three of these equally likely possibilities, while a player who switches wins in two out of three. The probability of winning by staying with the initial choice is therefore 1/3, while the probability of winning by switching is 2/3.
Other simple solutions
An even simpler solution is to reason that switching loses if and only if the player initially picks the car, which happens with probability 1/3, so switching must win with probability 2/3 (Carlton 2005).
Another way to understand the solution is to consider the two original unchosen doors together. Instead of one door being opened and shown to be a losing door, an equivalent action is to combine the two unchosen doors into one since the player cannot choose the opened door (Adams 1990; Devlin 2003; Williams 2004; Stibel et al., 2008).
As Cecil Adams puts it (Adams 1990), "Monty is saying in effect: you can keep your one door or you can have the other two doors." The player therefore has the choice of either sticking with the original choice of door, or choosing the sum of the contents of the two other doors, as the 2/3 chance of hiding the car has not been changed by the opening of one of these doors.
As Keith Devlin says (Devlin 2003), "By opening his door, Monty is saying to the contestant 'There are two doors you did not choose, and the probability that the prize is behind one of them is 2/3. I'll help you by using my knowledge of where the prize is to open one of those two doors to show you that it does not hide the prize. You can now take advantage of this additional information. Your choice of door A has a chance of 1 in 3 of being the winner. I have not changed that. But by eliminating door C, I have shown you that the probability that door B hides the prize is 2 in 3.'"
Increasing the number of doors
That switching has a probability of 2/3 of winning the car runs counter to many people's intuition. If there are two doors left, then why isn't each door 1/2? It may be easier to appreciate the solution by considering the same problem with 1,000,000 doors instead of just three (vos Savant 1990). In this case there are 999,999 doors with goats behind them and one door with a prize. The player picks a door. His initial probability of winning is 1 out of 1,000,000. The game host goes down the line of doors, opening each one to show 999,998 goats in total, skipping over only the player's door and one other door. The host then offers the player the chance to switch to the only other unopened door. On average, in 999,999 out of 1,000,000 times the other door will contain the prize, as 999,999 out of 1,000,000 times the player first picked a door with a goat — the chance that the player's door is correct hasn't changed. A rational player should switch.
Intuitively speaking, the player should ask how likely is it, that given a million doors, he or she managed to pick the right one. It's as if Monty gives you the chance to keep your one door, or open all 999,999 of the other doors, of which he kindly opens 999,998 for you, leaving, deliberately, the one with the prize. Clearly, one would choose to open the other 999,999 doors rather than keep the one.
Stibel et al. (2008) propose working memory demand is taxed during the Monty Hall problem and that this forces people to "collapse" their choices into two equally probable options. They report that when increasing the number of options to over 7 choices (7 doors) people tend to switch more often; however most still incorrectly judge the probability of success at 50/50.
Decision tree
The conditional probability of winning by switching given which door the host opens can be determined referring to the expanded figure below, or to an equivalent decision tree as shown to the right (Chun 1991; Grinstead and Snell 2006:137138), or formally derived as in the mathematical formulation section below.
For example, the player wins if the host opens Door 3 and the player switches and the car is behind Door 2, and this has probability 1/3. The player loses if the host opens Door 3 and the player switches and the car is behind Door 1, and this has probability 1/6. These are the only possibilities given host opens Door 3 and player switches. The overall probability that the host opens Door 3 is their sum, and we convert the two probabilities just found to conditional probabilities by dividing them by their sum. Therefore, the conditional probability of winning by switching given the player picks Door 1 and the host opens Door 3 is (1/3)/(1/3 + 1/6), which is 2/3.
As all the doors are initially equally likely to hide the car and the host is equally likely to open either door when he has a choice, the chance that the switching will give the car cannot depend on which door was chosen by the player and which door was opened by the host.(Morgan et al. 1991)
Bayes' theorem
Bayes' theorem relates the conditional and marginal probabilities of events A and B, provided that the probability of B does not equal zero:
where P(A  B) denotes the conditional probability of A given B.
Bayes' theorem can be applied to the Monty Hall Problem, following ]], [[#refGill2002Gill, 2002Henze, 1997. Consider the discrete random variables, all taking values in the set of door numbers {1,2,3}:
 C: the number of the door hiding the Car,
 S: the number of the door Selected by the player, and
 H: the number of the door opened by the Host.
As the host's placement of the car is random, all values c in {1,2,3} of C are equally likely. The initial (unconditional) probability distribution of C is then
 , for every value of c.
Further, as the initial choice of the player is independent of the placement of the car, variables C and S are independent. Hence the conditional probability of C = c given S = s is
 , for every value of c and s.
The host's behavior is reflected by the values of the conditional probability of H = h given C = c and S = s:

if h = s, (the host cannot open the door picked by the player), if h = c, (the host cannot open a door with a car behind it) if h s and s = c, (the two doors with no car are equally likely to be opened), if h c and h s and s c (there is only one door available to open).
The player can then use Bayes' theorem to compute the probability of finding the car behind any door, after the initial selection and the host's opening of one. This is the conditional probability of C = c given H = h and S = s:
where the denominator is computed using the law of total probability as the marginal probability
 .
Thus, if the player initially selects Door 1, and the host opens Door 3, the probability of winning by switching is
Strategic solution by dominance
Following Gill, 2011 a strategy of contestant involves two actions: the initial choice of a door and the decision to switch (or to stick) which may depend on both the door initially chosen and the door to which the host offers switching. For instance, one contestant's strategy is "choose door 1, then switch to door 2 when offered, and do not switch to door 3 when offered." There are twelve such deterministic strategies of the contestant.
Elementary comparison of contestant's strategies shows that for every strategy A there is another strategy B "pick a door then switch no matter what happens" which dominates it (Gnedin, 2011). No matter how the car is hidden and no matter which rule the host uses when he has a choice between two goats, if A wins the car then B also does. For example, strategy A "pick door 1 then always stick with it" is dominated by the strategy B "pick door 2 then always switch after the host reveals a door": A wins when door 1 conceals the car, while B wins when one of the doors 1 and 3 conceals the car.
The dominance is a strong reason to seek for a solution among alwaysswitching strategies under fairly general assumptions on the environment in which the contestant is making decisions. In particular, if the car is hidden by means of some randomization device  like tossing symmetric or asymmetric threesided die  the dominance implies that a strategy maximizing the probability of winning the car will be among three alwaysswitching strategies, namely it will be the strategy which initially picks the least likely door then switches no matter which door to switch is offered by the host.
Alternative derivations
Formal mathematical derivations can also be given which avoid explicit computations or formula manipulation, and which illustrate various insights into the Monty Hall problem.
 Proof using a simple solution and symmetry. The chance that the door chosen by the contestant, Door 1, hides the car, is 1/3. The conditional probabilities that Door 1 hides the car given that the host opens Door 2, and that he opens Door 3, must be equal to one another, by symmetry. This means that whether or not the host opens Door 3 is (statistically) independent of whether or not the car is behind Door 1 given the player initially chose Door 1. The conditional probability is equal to the unconditional probability, 2/3. (Gill, 2011a), (Bell (1992): "I will leave it to readers as to whether this equivalence of the conditional and unconditional problems is intuitively obvious.").
 Proof by total symmetry: irrelevance of door numbers. As before, let C, S, H stand for the numbers painted on the doors hiding the Car, Selected by the contestant, and opened by the Host, respectively. Let R stand for the Remaining closed door. The triple of door numbers (S,H,R) are the specific numbers observed by the player written on the doors chosen, opened, and left closed. They form a permutation of the numbers 1, 2, 3. Let I stand for the Indicator random variable which takes the value 1 if switching would give the car, and 0 if not: thus I = 1 if C = R, while I = 0 if C = S. Let's pretend for the moment that the door chosen by the player was actually chosen at random  it just happened to be Door 1. With this assumption, an arbitrary renumbering of the doors changes nothing in the probabilistic description of the problem. In mathematical terms, the problem is completely symmetric under permutations of the door numbers. Now, however we renumber the doors, whether or not switching gives the car does not change, I is Invariant. On the other hand, renumbering the doors in all six possible ways makes (S,H,R) take on all of its six possible values, the six different orders in which one can write down the numbers 1, 2, 3. By invariance, the six different orderings all have the same probability, 1/6, and I must be (statistically) Independent of (S,H,R): the probabilities that I = 0 and I = 1 can't depend on which permutation has been realised. The door numbers in a specific case are Irrelevant to deciding whether to switch or stay (and it was indeed totally harmless to pretend that the player's initial choice was random). This ties in with Marilyn Vos Savant's almost parenthetical wording "say, Door 1", and "say, Door 3", and her Insistence (vos Savant, 1991b) in response to Morgan et al. (1991) that conditional probability is absolutely not needed to solve the problem she had posed. In Tierney (1991), the mathemagician and Stanford professor Persi Diaconis stands up for vos Savant, see Diaconis (1988) for his work on symmetry in statistics.
Sources of confusion
When first presented with the Monty Hall problem an overwhelming majority of people assume that each door has an equal probability and conclude that switching does not matter (Mueser and Granberg, 1999). Out of 228 subjects in one study, only 13% chose to switch (Granberg and Brown, 1995:713). In her book The Power of Logical Thinking, vos Savant (1996:15) quotes cognitive psychologist Massimo PiattelliPalmarini as saying "... no other statistical puzzle comes so close to fooling all the people all the time" and "that even Nobel physicists systematically give the wrong answer, and that they insist on it, and they are ready to berate in print those who propose the right answer." Interestingly, pigeons make mistakes and learn from mistakes, and experiments, Herbranson and Schroeder, 2010, show that they rapidly learn to always switch, unlike humans.
Most statements of the problem, notably the one in Parade Magazine, do not match the rules of the actual game show (Krauss and Wang, 2003:9), and do not fully specify the host's behavior or that the car's location is randomly selected (Granberg and Brown, 1995:712). Krauss and Wang (2003:10) conjecture that people make the standard assumptions even if they are not explicitly stated. Although these issues are mathematically significant, even when controlling for these factors nearly all people still think each of the two unopened doors has an equal probability and conclude switching does not matter (Mueser and Granberg, 1999). This "equal probability" assumption is a deeply rooted intuition (Falk 1992:202). People strongly tend to think probability is evenly distributed across as many unknowns as are present, whether it is or not (Fox and Levav, 2004:637).
In addition to the "equal probability" intuition, a competing and deeply rooted intuition is that revealing information that is already known does not affect probabilities. Although this is a true statement, it is not true that just knowing the host can open one of the two unchosen doors to show a goat necessarily means that opening a specific door cannot affect the probability that the car is behind the initiallychosen door. If the car is initially placed behind the doors with equal probability and the host chooses uniformly at random between doors hiding a goat (as is the case in the standard interpretation) this probability indeed remains unchanged, but if the host can choose nonrandomly between such doors then the specific door that the host opens reveals additional information. The host can always open a door revealing a goat and (in the standard interpretation of the problem) the probability that the car is behind the initiallychosen door does not change, but it is not because of the former that the latter is true. Solutions based on the assertion that the host's actions cannot affect the probability that the car is behind the initiallychosen door are very persuasive, but lead to the correct answer only if the problem is completely symmetrical with respect to both the initial car placement and how the host chooses between two goats (Falk 1992:207,213).
The problem continues to attract the attention of cognitive psychologists. The typical behaviour of the majority, i.e., not switching, may be explained by phenomena known in the psychological literature as: 1) the endowment effect (Kahneman et al., 1991); people tend to overvalue the winning probability of the already chosen—already "owned"—door; 2) the status quo bias (Samuelson and Zeckhauser, 1988); people prefer to stick with the choice of door they have already made. Experimental evidence confirms that these are plausible explanations which do not depend on probability intuition (Morone and Fiore, 2007).
Variants
A common variant of the problem, assumed by several academic authors as the canonical problem, does not make the simplifying assumption that the host must uniformly choose the door to open, but instead that he uses some other strategy. The confusion as to which formalization is authoritative has led to considerable acrimony, particularly because this variant makes proofs more involved without altering the optimality of the alwaysswitch strategy for the player. In this variant, the player can have different probabilities of winning depending on the observed choice of the host, but in any case the probability of winning by switching is at least 1/2 (and can be as high as 1), while the overall probability of winning by switching is still exactly 2/3. The variants are sometimes presented in succession in textbooks and articles intended to teach the basics of probability theory and game theory. A considerable number of other generalizations have also been studied.
Criticism of the simple solutions
Some sources, in particular, Morgan et al. (1991) state that many popular solutions are incomplete because they do not explicitly address their interpretation of vos Savant's rewording of Whitaker's original question. The popular solutions correctly show that the probability of winning for a player who always switches is 2/3, but without additional reasoning this does not necessarily mean the probability of winning by switching is 2/3 given which door the player has chosen and which door the host opens.
The simple solutions show in various ways that a contestant who is determined to switch will win the car with probability 2/3, and hence that switching is a winning strategy. Some sources, however, state that although the simple solutions give a correct numerical answer, they are incomplete or solve the wrong problem. These sources consider the question: given that the contestant has chosen Door 1 and given that the host has opened Door 3, revealing a goat, what is now the probability that the car is behind Door 2?
To understand the difference, consider the following variation of the problem. Assume the contestant, Bryan Hall, knows that Monty does not pick the second door randomly; instead, when given an opportunity to pick between two losing doors, Monty will open the one on the left. Again, one may ask the same two questions:
 What is the probability of Bryan winning the car if he will abandon his initial pick?
 What is the probability of the car being behind the door 2 if Bryan first picked door 1 and Monty revealed a goat behind door 3?
The answer to the first question is again 2/3, since this is still the probability that his initial pick is wrong, but the answer to the second question is now different: Bryan may infer with complete certainty that the car is behind door 2. This is because Monty's preference for leftmost doors would otherwise had led him to open door 2 instead. For this variation, the two questions yield different answers. However, there is some disagreement in the literature regarding whether vos Savant's formulation of the problem, as it occurred in Parade magazine, is asking the first or second question, and whether this difference is significant (Rosenhouse 2009).
That probability is a conditional probability (Selvin (1975b); Morgan et al. 1991; Gillman 1992; Grinstead and Snell 2006:137). The difference is whether the analysis is of the average probability over all possible combinations of initial player choice and door the host opens, or of only one specific case—to be specific, the case where the player picks Door 1 and the host opens Door 3. Another way to express the difference is whether the player must decide to switch before the host opens a door, or is allowed to decide after seeing which door the host opens (Gillman 1992); either way, the player is interested in the probability of winning at the time they make their decision. Although the conditional and unconditional probabilities are both 2/3 for the problem statement with all details completely specified  in particular a completely random choice by the host of which door to open when he has a choice  the conditional probability may differ from the overall probability and the latter is not determined without a complete specification of the problem (Gill 2010). However as long as the initial choice has probability 1/3 of being correct, it is never to the contestants' disadvantage to switch, as the conditional probability of winning by switching is always at least 1/2.
According to Morgan et al. (1991) "The distinction between the conditional and unconditional situations here seems to confound many." That is, they, and some others, interpret the usual wording of the problem statement as asking about the conditional probability of winning given which door is opened by the host, as opposed to the overall or unconditional probability. These are mathematically different questions and can have different answers depending on how the host chooses which door to open when the player's initial choice is the car (Morgan et al., 1991; Gillman 1992). For example, if the host opens Door 3 whenever possible, then the probability of winning by switching for players initially choosing Door 1 is still 2/3 overall, but only 1/2 if such host opens Door 3, and in contrast 1 if he opens Door 2. In its usual form the problem statement does not specify this detail of the host's behavior, nor make clear whether a conditional or an unconditional answer is required, making the answer that switching wins the car with probability 2/3 equally vague. Many commonly presented solutions address the unconditional probability, ignoring which door was chosen by the player and which door opened by the host; Morgan et al. call these "false solutions" (1991). Others, such as Behrends (2008), conclude that "One must consider the matter with care to see that both analyses are correct."
Other host behaviors
The version of the Monty Hall problem published in Parade in 1990 did not specifically state that the host would always open another door, or always offer a choice to switch, or even never open the door revealing the car. However, vos Savant made it clear in her second followup column that the intended host's behavior could only be what led to the 2/3 probability she gave as her original answer. "Anything else is a different question" (vos Savant, 1991a). "Virtually all of my critics understood the intended scenario. I personally read nearly three thousand letters (out of the many additional thousands that arrived) and found nearly every one insisting simply that because two options remained (or an equivalent error), the chances were even. Very few raised questions about ambiguity, and the letters actually published in the column were not among those few." (vos Savant, 1996) The answer follows if the car is placed randomly behind any door, the host must open a door revealing a goat regardless of the player's initial choice and, if two doors are available, chooses which one to open randomly (Mueser and Granberg, 1999). The table below shows a variety of other possible host behaviors and the impact on the success of switching.
Determining the player's best strategy within a given set of other rules the host must follow is the type of problem studied in game theory. For example, if the host is not required to make the offer to switch the player may suspect the host is malicious and makes the offers more often if the player has initially selected the car. In general, the answer to this sort of question depends on the specific assumptions made about the host's behaviour, and might range from "ignore the host completely" to 'toss a coin and switch if it comes up heads', see the last row of the table below.
Morgan et al. (1991) and Gillman (1992) both show a more general solution where the car is (uniformly) randomly placed but the host is not constrained to pick uniformly randomly if the player has initially selected the car, which is how they both interpret the well known statement of the problem in Parade despite the author's disclaimers. Both changed the wording of the Parade version to emphasize that point when they restated the problem. They consider a scenario where the host chooses between revealing two goats with a preference expressed as a probability q, having a value between 0 and 1. If the host picks randomly q would be 1/2 and switching wins with probability 2/3 regardless of which door the host opens. If the player picks Door 1 and the host's preference for Door 3 is q, then in the case where the host opens Door 3 switching wins with probability 1/3 if the car is behind Door 2 and loses with probability (1/3)q if the car is behind Door 1. The conditional probability of winning by switching given the host opens Door 3 is therefore (1/3)/(1/3 + (1/3)q) which simplifies to 1/(1+q). Since q can vary between 0 and 1 this conditional probability can vary between 1/2 and 1. This means even without constraining the host to pick randomly if the player initially selects the car, the player is never worse off switching. However, it is important to note that neither source suggests the player knows what the value of q is, so the player cannot attribute a probability other than the 2/3 that vos Savant assumed was implicit.
Possible host behaviors in unspecified problem Host behavior Result "Monty from Hell": The host offers the option to switch only when the player's initial choice is the winning door. (Tierney 1991) Switching always yields a goat. "Angelic Monty": The host offers the option to switch only when the player has chosen incorrectly (Granberg 1996:185). Switching always wins the car. "Monty Fall" or "Ignorant Monty": The host does not know what lies behind the doors, and opens one at random that happens not to reveal the car (Granberg and Brown, 1995:712) (Rosenthal, 2005a) (Rosenthal, 2005b). Switching wins the car half of the time. The host knows what lies behind the doors, and (before the player's choice) chooses at random which goat to reveal. He offers the option to switch only when the player's choice happens to differ from his. Switching wins the car half of the time. The host always reveals a goat and always offers a switch. If he has a choice, he chooses the leftmost goat with probability p (which may depend on the player's initial choice) and the rightmost door with probability q=1−p. (Morgan et al. 1991) (Rosenthal, 2005a) (Rosenthal, 2005b). If the host opens the rightmost door, switching wins with probability 1/(1+q). The host acts as noted in the specific version of the problem. Switching wins the car twothirds of the time.
(Special case of the above with p=q=½)The host opens a door and makes the offer to switch 100% of the time if the contestant initially picked the car, and 50% the time if she didn't. (Mueser and Granberg 1999) Switching wins 1/2 the time at the Nash equilibrium. Fourstage twoplayer gametheoretic (Gill, 2010, Gill, 2011). The player is playing against the show organisers (TV station) which includes the host. First stage: organizers choose a door (choice kept secret from player). Second stage: player makes a preliminary choice of door. Third stage: host opens a door. Fourth stage: player makes a final choice. The player wants to win the car, the TV station wants to keep it. This is a zerosum twoperson game. By von Neumann's theorem from game theory, if we allow both parties fully randomized strategies there exists a minimax solution or Nash equilibrium (Mueser and Granberg 1999). Minimax solution (Nash equilibrium): car is first hidden uniformly at random and host later chooses uniform random door to open without revealing the car and different from player's door; player first chooses uniform random door and later always switches to other closed door. With his strategy, the player has a winchance of at least 2/3, however the TV station plays; with the TV station's strategy, the TV station will lose with probability at most 2/3, however the player plays. The fact that these two strategies match (at least 2/3, at most 2/3) proves that they form the minimax solution. As previous, but now host has option not to open a door at all. Minimax solution (Nash equilibrium): car is first hidden uniformly at random and host later never opens a door; player first chooses a door uniformly at random and later never switches. Player's strategy guarantees a winchance of at least 1/3. TV station's strategy guarantees a losechance of at most 1/3. N doors
D. L. Ferguson (1975 in a letter to Selvin cited in Selvin (1975b)) suggests an N door generalization of the original problem in which the host opens p losing doors and then offers the player the opportunity to switch; in this variant switching wins with probability (N−1)/[N(N−p−1)]. If the host opens even a single door the player is better off switching, but if the host opens only one door the advantage approaches zero as N grows large (Granberg 1996:188). At the other extreme, if the host opens all but one losing door the advantage increases as N grows large (the probability of winning by switching approaches 1 as N grows very large).
Bapeswara Rao and Rao (1992) suggest a different N door version where the host opens a losing door different from the player's current pick and gives the player an opportunity to switch after each door is opened until only two doors remain. With four doors the optimal strategy is to pick once and switch only when two doors remain. With N doors this strategy wins with probability (N−1)/N and is asserted to be optimal.
Quantum version
A quantum version of the paradox illustrates some points about the relation between classical or nonquantum information and quantum information, as encoded in the states of quantum mechanical systems. The formulation is loosely based on quantum game theory. The three doors are replaced by a quantum system allowing three alternatives; 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 with the initial 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 (Flitney and Abbott 2002, D'Ariano et al. 2002).
History
The earliest of several probability puzzles related to the Monty Hall problem is Bertrand's box paradox, posed by Joseph Bertrand in 1889 in his Calcul des probabilités (Barbeau 1993). In this puzzle there are three boxes: a box containing two gold coins, a box with two silver coins, and a box with one of each. After choosing a box at random and withdrawing one coin at random that happens to be a gold coin, the question is what is the probability that the other coin is gold. As in the Monty Hall problem the intuitive answer is 1/2, but the probability is actually 2/3.
The Three Prisoners problem, published in Martin Gardner's Mathematical Games column in Scientific American in 1959 (1959a, 1959b), is equivalent to the Monty Hall problem. This problem involves three condemned prisoners, a random one of whom has been secretly chosen to be pardoned. One of the prisoners begs the warden to tell him the name of one of the others who will be executed, arguing that this reveals no information about his own fate but increases his chances of being pardoned from 1/3 to 1/2. The warden obliges, (secretly) flipping a coin to decide which name to provide if the prisoner who is asking is the one being pardoned. The question is whether knowing the warden's answer changes the prisoner's chances of being pardoned. This problem is equivalent to the Monty Hall problem; the prisoner asking the question still has a 1/3 chance of being pardoned but his unnamed cohort has a 2/3 chance.
Steve Selvin posed the Monty Hall problem in a pair of letters to the American Statistician in 1975. (Selvin (1975a), Selvin (1975b)) The first letter presented the problem in a version close to its presentation in Parade 15 years later. The second 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 offered a known lesser prize—such as $100 cash—rather than a choice to switch doors. 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.A version of the problem very similar to the one that appeared three years later in Parade was published in 1987 in the Puzzles section of The Journal of Economic Perspectives (Nalebuff 1987). Nalebuff, as later writers in mathematical economics, sees the problem as a simple and amusing exercise in game theory.
Phillip Martin's article in a 1989 issue of Bridge Today magazine titled "The Monty Hall Trap" (Martin 1989) presented Selvin's problem as an example of what Martin calls the probability trap of treating nonrandom information as if it were random, and relates this to concepts in the game of bridge.
A restated version of Selvin's problem appeared in Marilyn vos Savant's Ask Marilyn questionandanswer column of Parade in September 1990 (vos Savant 1990). Though vos Savant gave the correct answer that switching would win twothirds of the time, she estimates the magazine received 10,000 letters including close to 1,000 signed by PhDs, many on letterheads of mathematics and science departments, declaring that her solution was wrong. (Tierney 1991) Due to the overwhelming response, Parade published an unprecedented four columns on the problem (vos Savant 1996:xv). 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 1990). 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 had 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 in which Monty Hall himself was interviewed. (Tierney 1991) Hall appeared to understand the problem, giving the reporter a demonstration 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 (Mueser and Granberg 1999). Barbeau 2000 contains a survey of the academic literature pertaining to the Monty Hall problem and other closely related problems.
The problem continues to appear in many venues:
 The syndicated NPR program Car Talk featured it as one of their weekly "Puzzlers," and the answer they featured was quite clearly explained as the correct one (Magliozzi and Magliozzi, 1998).
 An account of the Hungarian 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 problem is presented in fictional form in the first chapter of the novel Mr Mee (2000) by Andrew Crumey.
 The problem is discussed, from the perspective of a boy with Asperger syndrome, in The Curious Incident of the Dog in the Nighttime, a 2003 novel by Mark Haddon.
 The problem is also addressed in a lecture by the character Charlie Eppes in an episode of the CBS drama NUMB3RS (Episode 1.13).
 The problem is addressed in Derren Brown's 2006 book Tricks Of The Mind.
 Penn Jillette explained the Monty Hall Problem on the "Luck" episode of Bob Dylan's Theme Time Radio Hour radio series.
 The Monty Hall problem appears in the film 21 (Bloch 2008).
 Economist M. Keith Chen identified a potential flaw in hundreds of experiments related to cognitive dissonance that use an analysis with issues similar to those involved in the Monty Hall problem. (Tierney 2008)
 In 2009 a booklength discussion of the problem, its history, methods of solution, and variations, was published by Oxford University Press (Rosenhouse 2009).
See also
 Principle of restricted choice (bridge)
 Boy or Girl paradox
 Two envelopes problem
 Sleeping Beauty problem
References
 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). Retrieved July 25, 2005.
 Bapeswara Rao, V. V. and Rao, M. Bhaskara (1992). "A threedoor game show and some of its variants". The Mathematical Scientist 17(2): 89–94.
 Barbeau, Edward (1993). "Fallacies, Flaws, and Flimflam: The problem of the Car and Goats". The College Mathematics Journal 24(2): 149154.
 Barbeau, Edward (2000). Mathematical Fallacies, Flaws and Flimflam. The Mathematical Association of America. ISBN 0883855291.
 Behrends, Ehrhard (2008). FiveMinute Mathematics. AMS Bookstore. p. 57. ISBN 9780821843482. http://books.google.com/?id=EpkyE6JFmkwC&pg=PA48&dq=montyhall+doornumber.
 Bell, William (1992). "Comment on Let's make a deal by Morgan et al.", American Statistician 46(3): 247 (August 1992).
 Bloch, Andy (2008). "21  The Movie (my review)". http://www.andybloch.com/gl/pub/article.php?story=2008031308241327. Retrieved 20080505.
 Carlton, Matthew (2005). "Pedigrees, Prizes, and Prisoners: The Misuse of Conditional Probability". Journal of Statistics Education [online] 13 (2). http://www.amstat.org/publications/JSE/v13n2/carlton.html. Retrieved 20100529.
 Chun, Young H. (1991). "Game Show Problem," OR/MS Today 18(3): 9.
 D'Ariano, G.M et al. (2002). "The Quantum Monty Hall Problem" (PDF). Los Alamos National Laboratory, (February 21, 2002). Retrieved January 15, 2007.
 Devlin, Keith (July – August 2003). "Devlin's Angle: Monty Hall". The Mathematical Association of America. http://www.maa.org/devlin/devlin_07_03.html. Retrieved 20080425.
 "Getting the goat: When it comes to weighing risks and probabilities, keep in mind this golden rule: never trust your guesses". The Economist (The Economist Newspaper) 350: p. 110. 1999. http://www.economist.com/node/187166.
 Diaconis, Persi (1988). Group representations in probability and statistics, IMS Lecture Notes, Institute of Mathematical Statistics. ISBN 0940600145.
 Falk, Ruma (1992). "A closer look at the probabilities of the notorious three prisoners," Cognition 43: 197–223.
 Flitney, Adrian P. and Abbott, Derek (2002). "Quantum version of the Monty Hall problem," Physical Review A, 65, Art. No. 062318, 2002.
 Fox, Craig R. and Levav, Jonathan (2004). "PartitionEditCount: Naive Extensional Reasoning in Judgment of Conditional Probability," Journal of Experimental Psychology: General 133(4): 626642.
 Gardner, Martin (1959a). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182. Reprinted in The Second Scientific American Book of Mathematical Puzzles and Diversions.
 Gardner, Martin (1959b). "Mathematical Games" column, Scientific American, November 1959, p. 188.
 Gill, Jeff (2002). Bayesian Methods, pp. 8–10. CRC Press. ISBN 1584882883, (restricted online copy at Google Books)
 Gill, Richard (2010) Monty Hall problem. pp. 858–863, International Encyclopaedia of Statistical Science, Springer, 2010. Eprint [1]
 Gill, Richard (2011) The Monty Hall Problem is not a probability puzzle (it's a challenge in mathematical modelling). Statistica Neerlandica 65(1) 5871, February 2011. Eprint [2]
 Gill, Richard (2011) The Monty Hall Problem. Mathematical Institute, University of Leiden, Netherlands 1013, 17 March 2011. Eprint [3]
 Gill, Richard (2011b) Monty Hall Problem (version 5). StatProb: The Encyclopedia Sponsored by Statistics and Probability Societies 2011. [4]
 Gillman, Leonard (1992). "The Car and the Goats," American Mathematical Monthly 99: 3–7.
 Gnedin, Sasha (2011) "The Mondee Gills Game." The Mathematical Intelligencer http://www.springerlink.com/content/8402812734520774/fulltext.pdf
 Granberg, Donald (1996). "To Switch or Not to Switch". Appendix to vos Savant, Marilyn, The Power of Logical Thinking. St. Martin's Press. ISBN 0612304633, (restricted online copy at Google Books).
 Granberg, Donald and Brown, Thad A. (1995). "The Monty Hall Dilemma," Personality and Social Psychology Bulletin 21(7): 711729.
 Grinstead, Charles M. and Snell, J. Laurie (20060704) (PDF). Grinstead and Snell’s Introduction to Probability. http://www.math.dartmouth.edu/~prob/prob/prob.pdf. Retrieved 20080402. Online version of Introduction to Probability, 2nd edition, published by the American Mathematical Society, Copyright (C) 2003 Charles M. Grinstead and J. Laurie Snell.
 Gruber, Gary (2010). The World's 200 Hardest Brain Teasers. Sourcebooks, Inc.. p. 136. ISBN 13:9781402238574. http://books.google.com/books?id=sesXaPoWyb0C&printsec=frontcover&dq=The+World's+200+Hardest+Brainteasers&hl=en&ei=bXzbTaGMIeTUiALCq7kR&sa=X&oi=book_result&ct=result&resnum=1&ved=0CDgQ6AEwAA#v=onepage&q=The%20World's%20200%20Hardest%20Brainteasers&f=false.
 Hall, Monty (1975). The Monty Hall Problem. LetsMakeADeal.com. Includes May 12, 1975 letter to Steve Selvin. Retrieved January 15, 2007.
 Henze, Norbert (1997). Stochastik für Einsteiger: Eine Einführung in die faszinierende Welt des Zufalls, pp. 105, Vieweg Verlag, ISBN 3834800910, (restricted online copy at Google Books)
 Herbranson, W. T. and Schroeder, J. (2010). "Are birds smarter than mathematicians? Pigeons (Columba livia) perform optimally on a version of the Monty Hall Dilemma." J. Comp. Psychol. 124(1): 113. Retrieved from http://www.ncbi.nlm.nih.gov/pubmed/20175592 March 1, 2010. http://people.whitman.edu/~herbrawt/HS_JCP_2010.pdf
 Kahneman, D., J.L. Knetsch and R.H. Thaler, 1991. Anomalies: The endowment effect, loss aversion, and status quo bias. The Journal of Economic Perspectives.
 Krauss, Stefan and Wang, X. T. (2003). "The Psychology of the Monty Hall Problem: Discovering Psychological Mechanisms for Solving a Tenacious Brain Teaser," Journal of Experimental Psychology: General 132(1). Retrieved from http://www.usd.edu/~xtwang/Papers/MontyHallPaper.pdf March 30, 2008.
 Mack, Donald R. (1992). The Unofficial IEEE Brainbuster Gamebook. WileyIEEE. p. 76. ISBN 9780780304239. http://books.google.com/?id=hcy9mQp83dEC&pg=PA18&dq=%22monty+hall+problem%22.
 Magliozzi, Tom; Magliozzi, Ray (1998). Haircut in Horse Town: & Other Great Car Talk Puzzlers. Diane Pub Co.. ISBN 0756764238.
 Martin, Phillip (1989). "The Monty Hall Trap", Bridge Today, May–June 1989. Reprinted in Granovetter, Pamela and Matthew, ed. (1993), For Experts Only, Granovetter Books.
 Martin, Robert M. (2002). There are two errors in the the title of this book (2nd ed.). Broadview Press. pp. 57–59. ISBN 9781551114934. http://books.google.com/?id=d6w6Wyp5cyUC&pg=PA57&dq=montyhall+doornumber.
 Morgan, J. P., Chaganty, N. R., Dahiya, R. C., & Doviak, M. J. (1991). "Let's make a deal: The player's dilemma," American Statistician 45: 284287.
 Morone, A., and A. Fiore, 2007. Monty Hall's Three Doors for Dummies. Dipartimento di Scienze Economiche e Metodi Matematici  Università di Bari, Southern Europe Research in Economic Studies  S.E.R.I.E.S. Working Paper no. 0012, [5].
 Mueser, Peter R. and Granberg, Donald (May 1999). "The Monty Hall Dilemma Revisited: Understanding the Interaction of Problem Definition and Decision Making", University of Missouri Working Paper 9906. Retrieved June 10, 2010.
 Nalebuff, Barry (1987). "Puzzles: Choose a Curtain, Duelity, Two Point Conversions, and More," Journal of Economic Perspectives 1(2): 157163 (Autumn, 1987).
 Rosenhouse, Jason: The Monty Hall Problem. Oxford University Press 2009, ISBN 9780195367898 (online copy of the first chapter, preprint).
 Rosenthal, Jeffrey S. (2005a). "Monty Hall, Monty Fall, Monty Crawl". Math Horizons: September issue, 5–7. Online reprint, 2008.
 Rosenthal, Jeffrey S. (2005b): Struck by Lightening: the Curious World of Probabilities. Harper Collings 2005, ISBN 9780002007917.
 Samuelson, W. and R. Zeckhauser, 1988. Status quo bias in decision making. Journal of Risk and Uncertainty, 1, pp. 759.
 Selvin, Steve (February 1975), "A problem in probability (letter to the editor)", American Statistician 29 (1): 67
 Selvin, Steve (August 1975), "On the Monty Hall problem (letter to the editor)", American Statistician 29 (3): 134
 Seymann R. G. (1991). "Comment on Let's make a deal: The player's dilemma," American Statistician 45: 287288.
 Stibel, Jeffrey, Dror, Itiel, & BenZeev, Talia (2008). "The Collapsing Choice Theory: Dissociating Choice and Judgment in Decision Making," Theory and Decision. Full paper can be found at http://users.ecs.soton.ac.uk/id/TD%20choice%20and%20judgment.pdf.
 Tierney, John (July 21, 1991), "Behind Monty Hall's Doors: Puzzle, Debate and Answer?", The New York Times, http://query.nytimes.com/gst/fullpage.html?res=9D0CEFDD1E3FF932A15754C0A967958260
 Tierney, John (April 8, 2008), "And Behind Door No. 1, a Fatal Flaw", The New York Times, http://www.nytimes.com/2008/04/08/science/08tier.html
 vos Savant, Marilyn (1990). "Ask Marilyn" column, Parade Magazine p. 16 (9 September 1990).
 vos Savant, Marilyn (1990b). "Ask Marilyn" column, Parade Magazine p. 25 (2 December 1990).
 vos Savant, Marilyn (1991a). "Ask Marilyn" column, Parade Magazine p. 12 (17 February 1991).
 vos Savant, Marilyn (1991b). "Marilyn vos Savant's reply (letters to the editor)", American Statistician 45(4): 347 (November 1991).
 vos Savant, Marilyn (1996). The Power of Logical Thinking. St. Martin's Press. ISBN 0312156278. http://books.google.com/?id=pgQQv8W_IgIC&pg=PA5&dq=%22monty+hall+paradox%22+inauthor:savant.
 vos Savant, Marilyn (2006). "Ask Marilyn" column, Parade Magazine p. 6 (26 November 2006).
 Schwager, Jack D. (1994). The New Market Wizards. Harper Collins. p. 397. ISBN 9780887306679. http://books.google.com/?id=Ezz_gZbRzwC&pg=PA397&dq=threedoors+montyhall.
 Williams, Richard (2004). "Appendix D: The Monty Hall Controversy" (PDF). Course notes for Sociology Graduate Statistics I. http://www.nd.edu/~rwilliam/stats1/appendices/xappxd.pdf. Retrieved 20080425.
 Wheeler, Ward C. (1991). "Congruence Among Data Sets: A Bayesian Approach". In Michael M. Miyamoto and Joel Cracraft. Phylogenetic analysis of DNA sequences. Oxford University Press US. p. 335. ISBN 9780195066982. http://books.google.com/?id=1wqvNgz58JQC&pg=PA335&dq=%22monty+hall%22+unchanged+switch.
 Whitaker, Craig F. (1990). [Formulation by Marilyn vos Savant of question posed in a letter from Craig Whitaker]. "Ask Marilyn" column, Parade Magazine p. 16 (9 September 1990).
External links
 The Game Show Problem–the original question and responses on Marilyn vos Savant's web site
 Monty Hall at the Open Directory Project
 "Monty Hall Paradox" by Matthew R. McDougal, The Wolfram Demonstrations Project (simulation)
 The Monty Hall Problem at The New York Times (simulation)
Categories: Featured articles on Mathematics Portal
 Probability theory paradoxes
 Let's Make a Deal
 Mathematical problems
 Game theory
 Microeconomics
 Decision theory paradoxes
 Named probability problems
Wikimedia Foundation. 2010.