Monty Hall problem

From Wikipedia, the free encyclopedia

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

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

Because there is no way for the player to know which of the two unopened doors is the winning door, many people assume that each door has an equal probability and conclude that switching does not matter. However, as long as the host knows what is behind each door, always opens a door revealing a goat, and always makes the offer to switch, opening a losing door does not change the probability of 1/3 that the car is behind the player's initially chosen door. As there is only one other unopened door, the probability that this door conceals the car must be 2/3. It is therefore to the contestant's advantage to switch to door 2.

The problem is also called the Monty Hall paradox; it is a veridical paradox in the sense that the solution is counterintuitive. For example, when the problem and the correct solution appeared in Parade, approximately 10,000 readers, including several hundred mathematics professors, wrote to the magazine claiming the published solution was wrong. Some of the controversy was because the Parade statement of the problem fails to fully specify the host's behavior and is thus technically ambiguous. However, even when given completely unambiguous problem statements, explanations, simulations, and formal mathematical proofs, many people still meet the correct answer with disbelief.

(1)首先，在游戏初始状态，设轿车在门X的后面，P(X)= 1/3

(2)设竞猜者选择了A门，然后Monty准备打开B门

(3)
如果轿车在A门后，则Monty打开B门的概率为:
P(Monty打开B门|A)= 1/2

如果轿车在B门后，则Monty打开B门的概率为:
P(Monty打开B门|B)= 0

如果轿车在C门后，则Monty打开B门的概率为:
P(Monty打开B门|C)= 1

则Monty打开B门的概率为：
P(Monty打开B门)=P(A)P(Monty打开B门|A)
+P(B)P(Monty打开B门|B)
+P(C)P(Monty打开B门|C)
=1/6 + 0 + 1/3
=1/2

(4)
据Bayes定理，
P(A|Monty打开B门)=P(A) * P(Monty打开B门|A)
/ P(Monty打开B门)
=(1/3 * 1/2) / (1/2)
=1/3

P(C|Monty打开B门)=P(C) * P(Monty打开B门|C)
/ P(Monty打开B门)
=(1/3 * 1) / (1/2)
=2/3

其实我刚看到这个问题的时候也很迷惑，直觉上也认为是1/2。在三思网站上和别人讨论了半天，有位老兄提醒我用贝叶斯公式，我又找到了一篇这一问题的运算过程，这才搞清楚。如果要笑话你的话，恐怕要先笑话我自己了。

我试着直观解释一下2/3的问题，也不知是否说的清楚（更糟糕的是也不知解释的对不对，还是用贝叶斯公式的那个算法更让人放心）：
1、参与者选A门，车在A门后的概率为1/3；车在B门与C门后的概率之和为2/3
2、MONTY打开B门，B门后没有车，即车在B门后的概率为零；由于车在B门与C门后的概率之和为2/3，而现在车在B门后的概率为零，则车在C门后的概率为2/3

注：这里还是用了一条概率论的定理----如果事件A与B为互斥事件（即事件A、B不会同时发生），设P(A)为事件A发生的概率，P(B)为事件B发生的概率,P(A+B)为事件A发生或事件B发生(且必有其一发生)的概率，则P(A+B)=P(A)+P(B)----不过这个定理相对容易懂多了

另外下面这个链接是我在三思科学论坛和别人讨论的帖子，看看对你是否有些帮助。呵呵，也看看我由错误走向正确的思维过程
http://128.104.179.104:8888/cgi-bin...de=1&jc=&page=2

Problem

The statement of the problem in the Ask Marilyn column in Parade leaves critical aspects of the host's behavior unstated, making the problem mathematically ambiguous. In a more precise statement of the problem (Mueser and Granberg 1999) the host is constrained to always open a door revealing a goat and to always make the offer to switch:

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

Do the player's chances of getting the car increase by switching to Door 2?

The problem as generally intended also assumes that the particular door the host opens conveys no special information about whether the player's initial choice is correct. The simplest way to make this explicit is to add a constraint that the host will open one of the remaining two doors randomly if the player initially picked the car.

[edit] Solution

Once the host has opened a door, the car must be behind one of the two remaining doors. The player has no way to know which of these doors is the winning door, leading many people to assume that each door has an equal probability and to conclude that switching does not matter (Mueser and Granberg, 1999). This "equal probability" assumption, while being intuitively seductive, is incorrect. The player's chances of winning the car actually double by switching to the door the host offers.

The chance of initially choosing the car is one in three, which is the chance of winning the car by sticking with this choice. By contrast, the chance of initially choosing a door with a goat is two in three, and a player originally choosing a door with a goat wins by switching. In both cases the host must reveal a goat. In the 2/3 case where the player initially chooses a goat, the host must reveal the other goat making the only remaining door the one with the car.

1. Host reveals Goat A or Host reveals Goat B Player picks car Switching loses. 2. Host must reveal Goat B Player picks Goat A Switching wins. 3. Host must reveal Goat A Player picks Goat B Switching wins.

The player has an equal chance of initially selecting the car, Goat A, or Goat B. Switching results in a win 2/3 of the time.

More formally, when the player is asked whether to switch there are three possible situations corresponding to the player's initial choice, each with probability 1/3:

• The player originally picked the door hiding the car. The game host has shown one of the two goats.
• The player originally picked the door hiding Goat A. The game host has shown the other goat.
• The player originally picked the door hiding Goat B. The game host has shown the other goat.

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

The solution would be different if the host did not know what was behind each door, or if the host sometimes had the option of not offering the player the chance to switch. Some statements of the problem, notably the one in Parade Magazine, do not explicitly exclude these possibilities. For example, if the game host only offers the opportunity to switch if the contestant originally chooses the car, the probability of winning by switching is 0%. In the common understanding of the problem as stated by Mueser and Granberg, the host must reveal a goat and must make the offer to switch so the player has a 2/3 chance of winning by switching.

[edit] Aids to understanding

[edit] Why the probability is 2/3

The most commonly voiced objection to the solution is that the past can be ignored when assessing the probability — that it is irrelevant which doors the player initially picks and the host opens. However, in the problem as originally presented, the player's initial choice does influence the host's available choices.

This difference can be demonstrated by contrasting the original problem with a variation that appeared in vos Savant's column in November 2006. In this version, Monty Hall forgets which door hides the car. He opens one of the doors at random and is relieved when a goat is revealed. Asked whether the contestant should switch, vos Savant correctly replied, "If the host is clueless, it makes no difference whether you stay or switch. If he knows, switch" (vos Savant, 2006).

In this version of the puzzle, the player has an equal chance of winning whether switching or not. There are six possible sequences of events that can occur, each with probability 1/6:

In the first two cases above, the host reveals the car. What might happen in these cases is unknown — perhaps the contestant immediately wins or immediately loses. However, in the problem as stated, the host has revealed a goat, so only four of the six cases remain possible, and they are equally likely. In two of these four cases, switching results in a win, and in the other two, switching results in a goat. Staying with the original pick gives the same odds: a loss in two cases and a win in two others.

The player's probability of winning by switching increases to 2/3 in the problem as stated by Mueser and Granberg because in the two cases above where the host would reveal the car, he is forced to reveal the remaining goat instead. In the table below, the host's picks from the table above are highlighted. Because he cannot reveal the car, his behavior is altered in two cases:

This change in the host's behavior causes the car to be twice as likely to be behind the "third door", and is what causes switching to be twice as likely to win in the "host knows" variation of the problem.

[edit] Sources of confusion

One reason the Monty Hall problem may be so counterintuitive is that the host is expected to be deceitful (Mueser and Granberg 1999). If the host opens a door only when the player has chosen correctly, then when the host opens a door the player should never opt to switch.

Another possible reason for confusion is that the problem is often stated as though the host takes the player by surprise by opening the door and offering the choice. This tends to give the impression that the host is trying to confuse a player who has chosen correctly, and would mean the player did not know the rules in advance. If the player did not know the rules, that would not alter the probability in the particular case, but it would mean that the player could not definitively make the optimal choice. This confusion is dealt with in the unambiguous statement of the problem where the host explicitly relates the rules to the contestant in advance.

A third possible reason for confusion could come from how the problem is presented. If either the assumption that the host knows which door the car is behind or the assumption that the host always offers the choice to switch is omitted, then choosing to switch doors or to stay with the original decision yields an indeterminate probability for success.

[edit] Increasing the number of doors

It may be easier to appreciate the solution by considering the same problem with 100 doors instead of just three. In this case there are 99 doors with goats behind them and one door with a prize. The player picks a door. The game host then opens 98 of the other doors revealing 98 goats — imagine the host starting with the first door and going down a line of 100 doors, opening each one, 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 99 out of 100 times the other door will contain the prize, as 99 out of 100 times the player first picked a door with a goat. A rational player should switch.

The three-door game, by comparison, gives a misleading impression, because the player is always presented with 1/3 proportions. There is a 1/3 chance of winning, the host reveals 1/3 of the mystery, and the player is allowed to switch to the other 1/3 option. All options seem equal — yet they are not. This is an essential ingredient for the counter-intuitiveness of the original problem.

Even if only one of the 100 doors is opened, switching still increases the player's chances of finding a car. The 99/100 chance that the car is not behind the door the player picked is spread evenly over 98 doors after the host reveals one goat. Each of those 98 doors, that is all doors other than the one the player picked and the one the host reveals, has a 99/9800 chance of having the car, so by switching the player slightly improves the chances of winning the car — from a 0.0100 (1/100) chance to just over 0.0101 (99/9800). This is an improvement by a factor of 99/98, or slightly more than 1% better odds.

The same algorithm can be followed for any number of doors, N. The algorithm is "Choose a door, eliminate some number (0 < x < N-1) of the remaining, losing doors, decide to switch or not." This algorithm can be followed for N = 3 or N = 100. The higher N values demonstrate the same mathematical principle in a more obvious way.

[edit] Venn diagram

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

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

[edit] Decision tree

Tree listing the probability of every possible outcome

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

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

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

[edit] Combining doors

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, and will not, choose the opened door. The player therefore has the choice of either sticking with the original choice of door with a 1/3 chance of winning the car, or choosing the sum of the contents of the two other doors with a 2/3 chance. The game assumptions play a role here — switching is equivalent to taking the combined contents because the game host is required to open a door with a goat.

In this case what should be ignored is the opening of the door. The player actually chooses between the originally picked door and the other two — opening one is simply a distraction. There is only one car and it does not move. The original choice divides the possible locations of the car between the one door the player picks with a 1/3 chance and the other two with a 2/3 chance. It is already known that at least one of the two unpicked doors contains a goat. Revealing the goat therefore gives the player no additional information about the originally chosen door; it does not change the 2/3 probability that the car is still in the block of two doors.

[edit] Bayes' theorem

An analysis of the problem using the formalism of Bayesian probability theory (Gill 2002) makes explicit the role of the assumptions underlying the problem. In Bayesian terms, probabilities are associated to propositions, and express a degree of belief in their truth, subject to whatever background information happens to be known. For this problem the background is the set of game rules, and the propositions of interest are:

 : The car is behind Door i, for i equal to 1, 2 or 3.

 : The host opens Door j after the player has picked Door i, for i and j equal to 1, 2 or 3.

For example, denotes the proposition the car is behind Door 1, and denotes the proposition the host opens Door 2 after the player has picked Door 1. Indicating the background information with , the assumptions are formally stated as follows.

First, the car can be behind any door, and all doors are a priori equally likely to hide the car. In this context a priori means before the game is played, or before seeing the goat. Hence, the prior probability of a proposition is:

.

Second, the host will always open a door that has no car behind, chosen among the two not picked by the player. If two such doors are available, each one is equally likely to be opened. This rule determines the conditional probability of a proposition subject to where the car is, i.e. conditioned on a proposition . Specifically, it is:

			if i = j, (the host cannot open the door picked by the player)
			if j = k, (the host cannot open a door with a car behind it)
			if i = k, (the two doors with no car are equally likely to be opened)
			if i ≠k and j ≠ k, (there is only one door available to open)

The problem can now be solved by scoring each strategy with its associated posterior probability of winning, that is with its probability subject to the host's opening of one of the doors. Without loss of generality assume, by re-numbering the doors if necessary, that the player picks Door 1, and the host then opens Door 3, showing him or her a goat. In other words, the host makes proposition true.

The posterior probability of winning by not switching doors, subject to the game rules and , is then . Using Bayes' theorem this is expressed as:

.

By the assumptions stated above, the numerator of the right-hand side is:

.

The normalizing constant at the denominator can be evaluated by expanding it using the definitions of marginal probability and conditional probability:

Dividing the numerator by the normalizing constant yields:

.

Note that this is equal to the prior probability for the car to be behind the initially chosen door, meaning that the host's action has not contributed any novel information with regard to this eventuality. In fact, the following argument shows that the effect of the host's action consists entirely of redistributing the probabilities for the car to be behind any of the other two doors.

The probability of winning by switching the selection to Door 2, , can be evaluated by requiring that the posterior probabilities of all the propositions add to 1. That is:

.

There is no car behind Door 3 since the host opened it, so the last term must be zero. This can be proven using Bayes' theorem and the previous results:

Hence:

.

This shows that the winning strategy is to switch the selection to Door 2. It also makes clear the host's showing of the goat at Door 3 has the effect of transferring the 1/3 of winning probability a-priori associated to that door to the remaining unselected and unopened one, thus making it the most likely winning choice.

zz http://www.itpub.net/130524,2.html

http://en.wikipedia.org/wiki/Monty_Hall_problem

无情的赞美维基百科～