GOPHERSPACE.DE - P H O X Y
gophering on gopherpedia.com


======================================================================
=                        Monty Hall problem                        =
======================================================================

                             Introduction                             
======================================================================
The Monty Hall problem is a brain teaser, in the form of a probability
puzzle, loosely based on the American television game show 'Let's Make
a Deal' and named after its original host, Monty Hall. The problem was
originally posed (and solved) in a letter by Steve Selvin to the
'American Statistician' in 1975. It became famous as a question from
reader Craig F. Whitaker's letter quoted in Marilyn vos Savant's "Ask
Marilyn" column in 'Parade' magazine in 1990:



Vos Savant's response was that the contestant should switch to the
other door. Under the standard assumptions, contestants who switch
have a  chance of winning the car, while contestants who stick to
their initial choice have only a  chance.

The simplest explanation for the effectiveness of the strategy
concerns the placement of the goats: when the player first makes their
choice, there is a 66% chance that a goat is behind their chosen door.
This probability does not change after the host reveals the location
of the other goat. Since it is always more likely the player has
chosen a goat
to begin with, and the host will always give away the location of the
other one, there is a 66% chance that switching was within the
player's best interest all along (as opposed to the less likely 33%
chance the player had chosen the car).

The given probabilities depend on specific assumptions about how the
host and contestant choose their doors. A key insight is that, under
these standard conditions, there is more information about doors 2 and
3 than was available at the beginning of the game when door 1 was
chosen by the player: the host's deliberate action adds value to the
door he did not choose to eliminate, but not to the one chosen by the
contestant originally. Another insight is that switching doors is a
different action than choosing between the two remaining doors at
random, as the first action uses the previous information and the
latter does not. Other possible behaviors of the host than the one
described can reveal different additional information, or none at all,
and yield different probabilities.

Many readers of vos Savant's column refused to believe switching is
beneficial despite her explanation. After the problem appeared in
'Parade', approximately 10,000 readers, including nearly 1,000 with
PhDs, wrote to the magazine, most of them claiming vos Savant was
wrong. Even when given explanations, simulations, and formal
mathematical proofs, many people still do not accept that switching is
the best strategy. Paul Erdős, one of the most prolific mathematicians
in history, remained unconvinced until he was shown a computer
simulation demonstrating vos Savant's predicted result.

The problem is a paradox of the 'veridical' type, because the correct
choice (that one should switch doors) is so counterintuitive it can
seem absurd, but is nevertheless demonstrably true. The Monty Hall
problem is mathematically closely related to the earlier Three
Prisoners problem and to the much older Bertrand's box paradox.


                             The paradox                              
======================================================================
Steve Selvin wrote a letter to the 'American Statistician' in 1975
describing a problem based on the game show 'Let's Make a Deal',
dubbing it the "Monty Hall problem" in a subsequent letter. The
problem is mathematically equivalent to the Three Prisoners problem
described in Martin Gardner's "Mathematical Games" column in
'Scientific American' in 1959 and the Three Shells Problem described
in Gardner's book 'Aha Gotcha'.


 Standard assumptions 
======================
Under the standard assumptions, the probability of winning the car
after switching is .
The key to this solution is the behavior of the host. Ambiguities in
the 'Parade' version do not explicitly define the protocol of the
host. However, Marilyn vos Savant's solution printed alongside
Whitaker's question implies, and both Selven and Savant explicitly
define, the role of the host as follows:
# The host must always open a door that was not picked by the
contestant.
# The host must always open a door to reveal a goat and never the car.
# The host must always offer the chance to switch between the
originally chosen door and the remaining closed door.

When any of these assumptions is varied, it can change the probability
of winning by switching doors as detailed in the section below. It is
also typically presumed that the car is initially hidden randomly
behind the doors and that, if the player initially picks the car, then
the host's choice of which goat-hiding door to open is random. Some
authors, independently or inclusively, assume that the player's
initial choice is random as well.


 Simple solutions 
==================
The solution presented by vos Savant in 'Parade' shows the three
possible arrangements of one car and two goats behind three doors and
the result of staying or switching after initially picking door 1 in
each case:

:::: Behind door 1   Behind door 2   Behind door 3   Result if staying
at door #1   Result if switching to the door offered
| Goat || Goat || **Car** || Wins goat || **Wins car**
| Goat || **Car** || Goat || Wins goat || **Wins car**
| **Car** || Goat || Goat || **Wins car** || Wins 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.

An intuitive explanation is that, if the contestant initially picks a
goat (2 of 3 doors), the contestant 'will' win the car by switching
because the other goat can no longer be picked, whereas if the
contestant initially picks the car (1 of 3 doors), the contestant
'will not' win the car by switching. The fact that the host
subsequently reveals a goat in one of the unchosen doors changes
nothing about the initial probability.


Most people come to the conclusion that switching does not matter
because there are two unopened doors and one car and that it is a
50/50 choice. This would be true if the host opens a door randomly,
but that is not the case; the door opened depends on the player's
initial choice, so the assumption of independence does not hold.
Before the host opens a door there is a  probability the car is behind
each door. If the car is behind door 1 the host can open either door 2
or door 3, so the probability the car is behind door 1 AND the host
opens door 3 is  ×  = . If the car is behind door 2 (and the player
has picked door 1) the host must open door 3, so the probability the
car is behind door 2 AND the host opens door 3 is  × 1 = . These are
the only cases where the host opens door 3, so if the player has
picked door 1 and the host opens door 3 the car is twice as likely to
be behind door 2. The key is that if the car is behind door 2 the host
must open door 3, but if the car is behind door 1 the host can open
either door.

Another way to understand the solution is to consider the two original
unchosen doors together. As Cecil Adams puts it, "Monty is saying in
effect: you can keep your one door or you can have the other two
doors." The  chance of finding the car has not been changed by the
opening of one of these doors because Monty, knowing the location of
the car, is certain to reveal a goat. So the player's choice after the
host opens a door is no different than if the host offered the player
the option to switch from the original chosen door to the set of
'both' remaining doors. The switch in this case clearly gives the
player a  probability of choosing the car.



As Keith Devlin says, "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 . 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.

Vos Savant suggests that the solution will be more intuitive with
1,000,000 doors rather than 3. In this case, there are 999,999 doors
with goats behind them and one door with a prize. After the player
picks a door, the host opens 999,998 of the remaining doors. On
average, in 999,999 times out of 1,000,000, the remaining door will
contain the prize. Intuitively, the player should ask how likely it is
that, given a million doors, he or she managed to pick the right one
initially. Stibel 'et al' proposed that 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 the number of options is increased to more than 7
choices (7 doors), people tend to switch more often; however, most
contestants still incorrectly judge the probability of success at
50:50.


                    Vos Savant and the media furor                    
======================================================================
Vos Savant wrote in her first column on the Monty Hall problem that
the player should switch. She received thousands of letters from her
readers - the vast majority of which, including many from readers with
PhDs, disagreed with her answer. During 1990-1991, three more of her
columns in Parade were devoted to the paradox. Numerous examples of
letters from readers of Vos Savant's columns are presented and
discussed in 'The Monty Hall Dilemma: A Cognitive Illusion Par
Excellence'.

The discussion was replayed in other venues (e.g., in Cecil Adams'
"The Straight Dope" newspaper column) and reported in major newspapers
such as 'The New York Times'.

In an attempt to clarify her answer, she proposed a shell game to
illustrate: "You look away, and I put a pea under one of three shells.
Then I ask you to put your finger on a shell. The odds that your
choice contains a pea are , agreed? Then I simply lift up an empty
shell from the remaining other two. As I can (and will) do this
regardless of what you've chosen, we've learned nothing to allow us to
revise the odds on the shell under your finger." She also proposed a
similar simulation with three playing cards.

Vos Savant commented that, though some confusion was caused by 'some'
readers' not realizing they were supposed to assume that the host must
always reveal a goat, almost all her numerous correspondents had
correctly understood the problem assumptions, and were still initially
convinced that vos Savant's answer ("switch") was wrong.


 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. Out of 228 subjects in one
study, only 13% chose to switch. In her book 'The Power of Logical
Thinking', quotes cognitive psychologist : "No other statistical
puzzle comes so close to fooling all the people all the time [and]
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." Pigeons repeatedly exposed to the problem
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  and do not fully
specify the host's behavior or that the car's location is randomly
selected. Krauss and Wang 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 that
switching does not matter. This "equal probability" assumption is a
deeply rooted intuition. People strongly tend to think probability is
evenly distributed across as many unknowns as are present, whether it
is or not.

The problem continues to attract the attention of cognitive
psychologists. The typical behavior of the majority, i.e., not
switching, may be explained by phenomena known in the psychological
literature as:

# The endowment effect, in which people tend to overvalue the winning
probability of the already chosen - already "owned" - door.
# The status quo bias, in which people prefer to stick with the choice
of door they have already made.
# The errors of omission vs. errors of commission effect, in which,
all other things being equal, people prefer to make errors through
inaction (Stay) as opposed to action (Switch).

Experimental evidence confirms that these are plausible explanations
that do not depend on probability intuition. Another possibility is
that people's intuition simply does not deal with the textbook version
of the problem, but with a real game show setting. There, the
possibility exists that the show master plays deceitfully by opening
other doors only if a door with the car was initially chosen. A show
master playing deceitfully half of the times modifies the winning
chances in case one is offered to switch to "equal probability".


 Criticism of the simple solutions 
===================================
As already remarked, most sources in the field of probability,
including many introductory probability textbooks, solve the problem
by showing the conditional probabilities that the car is behind door 1
and door 2 are  and  (not  and ) given that the contestant initially
picks door 1 and the host opens door 3; various ways to derive and
understand this result were given in the previous subsections.

Among these sources are several that explicitly criticize the
popularly presented "simple" solutions, saying these solutions are
"correct but ... shaky", or do not "address the problem posed", or are
"incomplete", or are "unconvincing and misleading", or are (most
bluntly) "false".

Sasha  wrote that "any explanation that says something like 'the
probability of door 1 was 1/3, and nothing can change that...' is
automatically fishy: probabilities are expressions of our ignorance
about the world, and new information can change the extent of our
ignorance."

Some say that these solutions answer a slightly different question -
one phrasing is "you have to announce 'before a door has been opened'
whether you plan to switch".

The simple solutions show in various ways that a contestant who is
determined to switch will win the car with probability , and hence
that switching is the winning strategy, if the player has to choose in
advance between "always switching", and "always staying". However, the
probability of winning by 'always' switching is a logically distinct
concept from the probability of winning by switching 'given that the
player has picked door 1 and the host has opened door 3'. As one
source says, "the distinction between [these questions] seems to
confound many". The fact that these are different can be shown by
varying the problem so that these two probabilities have different
numeric values. For example, assume the contestant knows that Monty
does not pick the second door randomly among all legal alternatives
but instead, when given an opportunity to pick between two losing
doors, Monty will open the one on the right. In this situation, the
following two questions have different answers:
# What is the probability of winning the car by 'always' switching?
# What is the probability of winning the car 'given the player has
picked door 1 and the host has opened door 3'?
The answer to the first question is , as is correctly shown by the
"simple" solutions. But the answer to the second question is now
different: the conditional probability the car is behind door 1 or
door 2 given the host has opened door 3 (the door on the right) is .
This is because Monty's preference for rightmost doors means that he
opens door 3 if the car is behind door 1 (which it is originally with
probability ) or if the car is behind door 2 (also originally with
probability ). For this variation, the two questions yield different
answers. However, as long as the initial probability the car is behind
each door is , it is never to the contestant's disadvantage to switch,
as the conditional probability of winning by switching is always at
least .

In Morgan 'et al.', four university professors published an article in
'The American Statistician' claiming that vos Savant gave the correct
advice but the wrong argument. They believed the question asked for
the chance of the car behind door 2 'given' the player's initial pick
for door 1 and the opened door 3, and they showed this chance was
anything between  and 1 depending on the host's decision process given
the choice. Only when the decision is completely randomized is the
chance .

In an invited comment and in subsequent letters to the editor, Morgan
'et al' were supported by some writers, criticized by others; in each
case a response by Morgan 'et al' is published alongside the letter or
comment in 'The American Statistician'. In particular, vos Savant
defended herself vigorously. Morgan 'et al' complained in their
response to vos Savant that vos Savant still had not actually
responded to their own main point. Later in their response to Hogbin
and Nijdam, they did agree that it was natural to suppose that the
host chooses a door to open completely at random, when he does have a
choice, and hence that the conditional probability of winning by
switching (i.e., conditional given the situation the player is in when
he has to make his choice) has the same value, , as the unconditional
probability of winning by switching (i.e., averaged over all possible
situations). This equality was already emphasized by Bell (1992), who
suggested that Morgan 'et als mathematically involved solution would
appeal only to statisticians, whereas the equivalence of the
conditional and unconditional solutions in the case of symmetry was
intuitively obvious.

There is disagreement in the literature regarding whether vos Savant's
formulation of the problem, as presented in 'Parade' magazine, is
asking the first or second question, and whether this difference is
significant. Behrends concludes that "One must consider the matter
with care to see that both analyses are correct"; which is not to say
that they are the same. Several critics of the paper by Morgan 'et
al.', whose contributions were published alongside the original paper,
criticized the authors for altering vos Savant's wording and
misinterpreting her intention. One discussant (William Bell)
considered it a matter of taste whether one explicitly mentions that
(under the standard conditions), 'which' door is opened by the host is
independent of whether one should want to switch.

Among the simple solutions, the "combined doors solution" comes
closest to a conditional solution, as we saw in the discussion of
approaches using the concept of odds and Bayes theorem. It is based on
the deeply rooted intuition that 'revealing information that is
already known does not affect probabilities'. But, knowing that the
host can open one of the two unchosen doors to show a goat does not
mean that opening a specific door would not affect the probability
that the car is behind the initially chosen door. The point is, though
we know in advance that the host will open a door and reveal a goat,
we do not know 'which' door he will open. If 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 non-randomly 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 initially chosen 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 initially chosen appear persuasive, but the assertion is
simply untrue unless each of the host's two choices are equally
likely, if he has a choice. The assertion therefore needs to be
justified; without justification being given, the solution is at best
incomplete. The answer can be correct but the reasoning used to
justify it is defective.


     Solutions using conditional probability and other solutions      
======================================================================
The simple solutions above show that a player with a strategy of
switching wins the car with overall probability , i.e., without taking
account of which door was opened by the host. In contrast most sources
in the field of probability calculate the conditional probabilities
that the car is behind door 1 and door 2 are  and  given the
contestant initially picks door 1 and the host opens door 3. The
solutions in this section consider just those cases in which the
player picked door 1 and the host opened door 3.


 Refining the simple solution 
==============================
If we assume that the host opens a door at random, when given a
choice, then which door the host opens gives us no information at all
as to whether or not the car is behind door 1. In the simple
solutions, we have already observed that the probability that the car
is behind door 1, the door initially chosen by the player, is
initially . Moreover, the host is certainly going to open 'a'
(different) door, so opening 'a' door ('which' door unspecified) does
not change this.  must be the average probability that the car is
behind door 1 given the host picked door 2 and given the host picked
door 3 because these are the only two possibilities. But, these two
probabilities are the same. Therefore, they are both equal to . This
shows that the chance that the car is behind door 1, given that the
player initially chose this door and given that the host opened door
3, is , and it follows that the chance that the car is behind door 2,
given that the player initially chose door 1 and the host opened door
3, is . The analysis also shows that the overall success rate of ,
achieved by 'always switching', cannot be improved, and underlines
what already may well have been intuitively obvious: the choice facing
the player is that between the door initially chosen, and the other
door left closed by the host, the specific numbers on these doors are
irrelevant.


 Conditional probability by direct calculation 
===============================================
By definition, the conditional probability of winning by switching
given the contestant initially picks door 1 and the host opens door 3
is the probability for the event "car is behind door 2 and host opens
door 3" divided by the probability for "host opens door 3". These
probabilities can be determined referring to the conditional
probability table below, or to an equivalent decision tree as shown to
the right. The conditional probability of winning by switching is ,
which is .

The conditional probability table below shows how 300 cases, in all of
which the player initially chooses door 1, would be split up, on
average, according to the location of the car and the choice of door
to open by the host.

width="33%" | Car hidden behind Door 3 (on average, 100 cases out of
300) colspan=2 width="33%" | Car hidden behind Door 1 (on average, 100
cases out of 300) width="33%" | Car hidden behind Door 2 (on average,
100 cases out of 300)
colspan=4 | Player initially picks Door 1, 300 repetitions
Player has picked Door 1 and the car is behind Door 3 colspan=2 |
Player has picked Door 1 and the car is behind it Player has picked
Door 1 and the car is behind Door 2
bgcolor=#cccccc | Host must open Door 2 (100 cases) bgcolor=#cccccc |
Host randomly opens Door 2 (on average, 50 cases) Host randomly opens
Door 3 (on average, 50 cases) Host must open Door 3 (100 cases)
bgcolor=#cccccc | Host must open Door 2 if the player picks Door 1
and the car is behind Door 3 bgcolor=#cccccc width=16% | Host opens
Door 2 half the time if the player picks Door 1 and the car is behind
it width=16% | Host opens Door 3 half the time if the player picks
Door 1 and the car is behind it Host must open Door 3 if the player
picks Door 1 and the car is behind Door 2
bgcolor=#cccccc | Probability  (100 out of 300) bgcolor=#cccccc |
Probability  (50 out of 300) Probability  (50 out of 300) Probability
(100 out of 300)
bgcolor=#cccccc | Switching wins bgcolor=#cccccc | Switching loses
Switching loses Switching wins
colspan=2 bgcolor=#cccccc | On those occasions when the host opens
Door 2, switching wins twice as often as staying (100 cases versus 50)
colspan=2 | On those occasions when the host opens Door 3, switching
wins twice as often as staying (100 cases versus 50)


 Bayes' theorem 
================
Many probability text books and articles in the field of probability
theory derive the conditional probability solution through a formal
application of Bayes' theorem; among them books by Gill and Henze. Use
of the odds form of Bayes' theorem, often called Bayes' rule, makes
such a derivation more transparent.

Initially, the car is equally likely to be behind any of the three
doors: the odds on door 1, door 2, and door 3 are . This remains the
case after the player has chosen door 1, by independence. According to
Bayes' rule, the posterior odds on the location of the car, given that
the host opens door 3, are equal to the prior odds multiplied by the
Bayes factor or likelihood, which is, by definition, the probability
of the new piece of information (host opens door 3) under each of the
hypotheses considered (location of the car). Now, since the player
initially chose door 1, the chance that the host opens door 3 is 50%
if the car is behind door 1, 100% if the car is behind door 2, 0% if
the car is behind door 3. Thus the Bayes factor consists of the ratios
or equivalently , while the prior odds were . Thus, the posterior odds
become equal to the Bayes factor . Given that the host opened door 3,
the probability that the car is behind door 3 is zero, and it is twice
as likely to be behind door 2 than door 1.

Richard Gill analyzes the likelihood for the host to open door 3 as
follows. Given that the car is 'not' behind door 1, it is equally
likely that it is behind door 2 or 3. Therefore, the chance that the
host opens door 3 is 50%. Given that the car 'is' behind door 1, the
chance that the host opens door 3 is also 50%, because, when the host
has a choice, either choice is equally likely. Therefore, whether or
not the car is behind door 1, the chance that the host opens door 3 is
50%. The information "host opens door 3" contributes a Bayes factor or
likelihood ratio of , on whether or not the car is behind door 1.
Initially, the odds against door 1 hiding the car were . Therefore,
the posterior odds against door 1 hiding the car remain the same as
the prior odds, .

In words, the information 'which' door is opened by the host (door 2
or door 3?) reveals no information at all about whether or not the car
is behind door 1, and this is precisely what is alleged to be
intuitively obvious by supporters of simple solutions, or using the
idioms of mathematical proofs, "obviously true, by symmetry".


 Direct calculation 
====================
Consider the event 'Ci', indicating that the car is behind door number
'i', takes value 'Xi', for the choosing of the player, and value 'Hi',
the opening the door. The player initially chooses door i = 1, C = X1
and the host opens door i = 3, C = H3.

In this case, we have:
:

'P(H3|X1) = 1/2' because this expression only depends on 'X1', not on
any 'Ci'. So, in this particular expression, the choosing of the host
doesn't depend on where the car is, and there's only two remaining
doors once 'X1' is chosen (for instance, 'P(H1|X1) = 0'); and
'P(Ci,Xi) = P(Ci)P(Xi)' because 'Ci' and 'Xi' are independent events
(the player doesn't know where is the car in order to make a choice).

Then, if the player initially selects door 1, and the host opens door
3, we prove that the conditional probability of winning by switching
is:

:

From the Bayes' rule, we know that 'P(A,B) = P(A|B)P(B) = P(B|A)P(A)'.
Extending this logic to multiple events, for example 'A', 'B' and 'C',
we get that we can play with the different subsets of '{A, B, C}' to
calculate the probability of the intersection, as a tool to simplify
the calculation of our conditional probability:

:

In our case, since we know that 'P(H3|C2,X1) = 1', we are in luck:

:


 Strategic dominance solution 
==============================
Going back to Nalebuff, the Monty Hall problem is also much studied in
the literature on game theory and decision theory, and also some
popular solutions correspond to this point of view. Vos Savant asks
for a decision, not a chance. And the chance aspects of how the car is
hidden and how an unchosen door is opened are unknown. From this point
of view, one has to remember that the player has two opportunities to
make choices: first of all, which door to choose initially; and
secondly, whether or not to switch. Since he does not know how the car
is hidden nor how the host makes choices, he may be able to make use
of his first choice opportunity, as it were to neutralize the actions
of the team running the quiz show, including the host.

Following Gill, 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". Twelve such deterministic
strategies of the contestant exist.

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" that dominates it. 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 1 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 2 and 3 conceals the car.
Similarly, strategy A "pick door 1 then switch to door 2 (if offered),
but do not switch to door 3 (if offered)" is dominated by strategy B
"pick door 3 then always switch".

Dominance is a strong reason to seek for a solution among
always-switching 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 three-sided die - the dominance
implies that a strategy maximizing the probability of winning the car
will be among three always-switching strategies, namely it will be the
strategy that initially picks the least likely door then switches no
matter which door to switch is offered by the host.

Strategic dominance links the Monty Hall problem to the game theory.
In the zero-sum game setting of Gill, discarding the non-switching
strategies reduces the game to the following simple variant: the host
(or the TV-team) decides on the door to hide the car, and the
contestant chooses two doors (i.e., the two doors remaining after the
player's first, nominal, choice). The contestant wins (and her
opponent loses) if the car is behind one of the two doors she chose.


 Solutions by simulation 
=========================
A simple way to demonstrate that a switching strategy really does win
two out of three times with the standard assumptions is to simulate
the game with playing cards. Three cards from an ordinary deck are
used to represent the three doors; one 'special' card represents the
door with the car and two other cards represent the goat doors.

The simulation can be repeated several times to simulate multiple
rounds of the game. The player picks one of the three cards, then,
looking at the remaining two cards the 'host' discards a goat card. If
the card remaining in the host's hand is the car card, this is
recorded as a switching win; if the host is holding a goat card, the
round is recorded as a staying win. As this experiment is repeated
over several rounds, the observed win rate for each strategy is likely
to approximate its theoretical win probability, in line with the law
of large numbers.

Repeated plays also make it clearer why switching is the better
strategy. After the player picks his card, it is 'already determined'
whether switching will win the round for the player. If this is not
convincing, the simulation can be done with the entire deck. In this
variant, the car card goes to the host 51 times out of 52, and stays
with the host no matter how many 'non'-car cards are discarded.


                               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 always-switch 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  (and can be as high
as 1), while the overall probability of winning by switching is still
exactly . 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.


 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
follow-up column that the intended host's behavior could only be what
led to the  probability she gave as her original answer. "Anything
else is a different question." "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." 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. 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 behavior, 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' and Gillman 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 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  and switching wins with probability  regardless of which door the
host opens. If the player picks door 1 and the host's preference for
door 3 is 'q', then the probability the host opens door 3 and the car
is behind door 2 is  while the probability the host opens door 3 and
the car is behind door 1 is . These are the only cases where the host
opens door 3, so the conditional probability of winning by switching
'given the host opens door 3' is  which simplifies to . Since 'q' can
vary between 0 and 1 this conditional probability can vary between
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 neither source suggests the player knows what the
value of 'q' is so the player cannot attribute a probability other
than the  that vos Savant assumed was implicit.


!colspan=2|Possible host behaviors in unspecified problem
!Host behavior !Result
|The host acts as noted in the specific version of the problem.
|Switching wins the car two-thirds of the time. (Specific case of the
generalized form below with 'p' = 'q' = )
|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'. |If the host opens the rightmost door,
switching wins with probability 1/(1+'q').
|"Monty from Hell": The host offers the option to switch only when
the player's initial choice is the winning door. |Switching always
yields a goat.
|"Mind-reading Monty": The host offers the option to switch in case
the guest is determined to stay anyway or in case the guest will
switch to a goat. |Switching always yields a goat.
|"Angelic Monty": The host offers the option to switch only when the
player has chosen incorrectly. |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. |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 opens a door and makes the offer to switch 100% of the time
if the contestant initially picked the car, and 50% the time
otherwise. Switching wins  the time at the Nash equilibrium.
|Four-stage two-player game-theoretic. The player is playing against
the show organizers (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
zero-sum two-person 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. |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 win-chance of at least , however the TV station plays;
with the TV station's strategy, the TV station will lose with
probability at most , however the player plays. The fact that these
two strategies match (at least , at most ) 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 win-chance of at least . TV station's strategy guarantees
a lose-chance of at most .
|'Deal or No Deal' case: the host asks the player to open a door,
then offers a switch in case the car hasn't been revealed. |Switching
wins the car half of the time.


 ''N'' doors 
=============
D. L. Ferguson (1975 in a letter to Selvin) 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 . This probability is
always greater than , therefore switching always brings an advantage.

Even if the host opens only a single door (), the player is better off
switching in every case. As 'N' grows larger, the advantage decreases
and approaches zero.
At the other extreme, if the host opens all losing doors but one ('p'
= 'N' − 2) the advantage increases as 'N' grows large (the probability
of winning by switching is , which approaches 1 as 'N' grows very
large).


 Quantum version 
=================
A quantum version of the paradox illustrates some points about the
relation between classical or non-quantum 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.


                               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'. 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 , but the probability is
actually .

The Three Prisoners problem, published in Martin Gardner's
'Mathematical Games' column in 'Scientific American' in 1959  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 to be executed, arguing that this reveals no
information about his own fate but increases his chances of being
pardoned from  to . 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  chance of being pardoned but his unnamed colleague has a
chance.

Steve Selvin posed the Monty Hall problem in a pair of letters to the
'American Statistician' in 1975. 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:



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, as later writers
in mathematical economics, sees the problem as a simple and amusing
exercise in game theory.

"The Monty Hall Trap", Phillip Martin's 1989 article in 'Bridge
Today', presented Selvin's problem as an example of what Martin calls
the probability trap of treating non-random 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' question-and-answer column of 'Parade' in
September 1990. Though vos Savant gave the correct answer that
switching would win two-thirds 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. Due to the overwhelming response, 'Parade'
published an unprecedented four columns on the problem. 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's analysis, Adams agreed that
mathematically he had been wrong. "You pick door #1. Now you're
offered this choice: open door #1, or open door #2 and door #3. In the
latter case you keep the prize if it's behind either door. You'd
rather have a two-in-three shot at the prize than one-in-three,
wouldn't you? If you think about it, the original problem offers you
basically the same choice. Monty is saying in effect: you can keep
your one door or you can have the other two doors, one of which (a
non-prize door) I'll open for you." Adams did say the 'Parade' version
left critical constraints unstated, and without those constraints, the
chances of winning by switching were not necessarily two out of three
(e.g., it was not reasonable to assume the host always opens a door).
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. Hall understood 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. In the article, Hall pointed out that because he had control
over the way the game progressed, playing on the psychology of the
contestant, the theoretical solution did not apply to the show's
actual gameplay. He said he was not surprised at the experts'
insistence that the probability was 1 out of 2. "That's the same
assumption contestants would make on the show after I showed them
there was nothing behind one door," he said. "They'd think the odds on
their door had now gone up to 1 in 2, so they hated to give up the
door no matter how much money I offered. By opening that door we were
applying pressure. We called it the Henry James treatment. It was 'The
Turn of the Screw.'" Hall clarified that as a game show host he did
not have to follow the rules of the puzzle in the vos Savant column
and did not always have to allow a person the opportunity to switch
(e.g., he might open their door immediately if it was a losing door,
might offer them money to not switch from a losing door to a winning
door, or might allow them the opportunity to switch only if they had a
winning door). "If the host is required to open a door all the time
and offer you a switch, then you should take the switch," he said.
"But if he has the choice whether to allow a switch or not, beware.
Caveat emptor. It all depends on his mood."


                               See also                               
======================================================================
* 'MythBusters' Episode 177 "Wheel of Mythfortune" - Pick a Door
* Principle of restricted choice - similar application of Bayesian
updating in contract bridge


 Similar puzzles in probability and decision theory 
====================================================
* Boy or Girl paradox
* Sleeping Beauty problem
* Two envelopes problem


                            External links                            
======================================================================
*
[https://web.archive.org/web/20130121183432/http://marilynvossavant.com/game-show-problem/
The Game Show Problem] - the original question and responses on
Marilyn vos Savant's web site
* [http://math.ucsd.edu/~crypto/Monty/Montytitle.html University of
California San Diego, Monty Knows Version and Monty Does Not Know
Version, An Explanation of the Game]
*
* [https://www.bbc.co.uk/news/magazine-24047377 "Stick or switch?
Probability and the Monty Hall problem"], 'BBC News Magazine', 11
September 2013 (video). Mathematician Marcus du Sautoy explains the
Monty Hall paradox.


 License 
=========
All content on Gopherpedia comes from Wikipedia, and is licensed under CC-BY-SA
License URL: http://creativecommons.org/licenses/by-sa/3.0/
Original Article: http://en.wikipedia.org/wiki/Monty Hall problem


.