The Monty Hall Problem
The Monty Hall Problem gets its name from the TV game show, Let's Make A Deal, hosted by Monty Hall 1. The scenario is such: you are given the opportunity to select one closed door of three, behind one of which there is a prize. The other two doors hide “goats” (or some other such “non-prize”), or nothing at all. Once you have made your selection, Monty Hall will open one of the remaining doors, revealing that it does not contain the prize 2. He then asks you if you would like to switch your selection to the other unopened door, or stay with your original choice. Here is the problem:
Does it matter if you switch?
This problem is quite interesting, because the answer is felt by most people — including mathematicians — to be counter-intuitive. For most, the “solution” is immediately obvious (they believe), and that is the end of it. But it's not. Because most of the time, this “obvious” solution is incorrect. The correct solution is quite counterintuitive. Further, I've found that many persons have difficulty grasping the validity of the correct solution even after several explanations. Thus, this web page.
Before I continue, you may wish to attempt to solve this problem by yourself. You've a good chance to do so, because you now know not to trust your instincts in this and that you should consider the problem very carefully. Try it.
First of all, I should say that this is not a rigorous mathematical analysis of this problem.This is a pretty simple problem, and doesn't require any advanced techniques. However, I've included a link to Steve Selvin's workup of this problem.My webpage is intended to present the solution in as clear and detailed terms as I believe are necessary.
Let's begin with a simple diagram:
There are three doors. One of these doors contains a prize. The other two do not. Therefore, the probability that any one of the doors contains the prize is 1/3. If the Monty Hall problem ended with the selection of the first door (and that would be a very dull problem, indeed), we could safely predict that one time out of three, the door picked will contain a prize; and that the contestant will go home with a brand-new Kenmore washer and dryer (well, I'd prefer Maytag, I think).
These are the probabilities we face when we are confronted by these three doors: the probability of one door being the door which hides a prize is 1/3, and the probability that it is not the prize-hiding door is 2/3. Look at represented in a modified diagram, and think about it for a moment:
The sum of the probabilities of the individual doors hiding the prize must equal one: we know that there is a prize (and exactly one indivisible prize) behind a door. Therefore, if we look at the three doors in aggregate, we know that there is a prize there. We are certain: the probability is one. And we can divide up the probabilities in this manner as we like. With only three doors, this is simple enough: we can look at one of the doors, and determine a probability (1/3), look at all three (1, of course), or look at two of the three (2/3). I'm going to repeat that last part, and harp on this because it's central to understanding the solution:
Behind any two doors considered together, the probability of there being a prize is 2/3.Here I have said something very different (but closely related to) what I said in the last paragraph. What is common is the 2/3 probability, and it should be obvious why. But I'll state it explicitly:
The probability that any two doors do hide a prize is two-thirds, and the probability that any one door does not hide a prize is two-thirds. They are the same because the sum of the probabilities for individual doors containing a prize must be one.
Now that you understand this thoroughly, let's continue.
When you are given a choice of one door to choose, and you choose a door; you have divided up the probabilities in the manner described above. It's bivalent: you have either chosen correctly, or you have not. The probability that you are correct is 1/3, and that you are not is 2/3. But here is where it gets interesting.
Monty Hall then opens one of the two remaining doors, and reveals to you that it does not contain a prize. Once he has done this, we can modify our diagram a bit:
Here you can see that he has eliminated one of the three doors from consideration. Note that he has not just eliminated any random door, but has eliminated one of the doors which does not hide a prize.
I believe that there is enough analysis presented so far, to make the solution to the Monty Hall problem obvious. Should you switch? In case you don't know, let's look at this in a bit more detail.Remember that we said that, once you made your initial choice, the situation is bivalent: you get the prize, or you didn't. Let's look at both in turn.
Okay, say you did select the correct door initially
How often will this happen? One time out of three: 1/3In that case, both of the two remaining doors will be “losers”, and Monty Hall will open one of them (at random, presumably — but it doesn't matter 3, leaving your correct door and the remaining incorrect door. So, if you switch, you'll switch to the wrong door (of course, since you picked the right one to begin with).
Since you will be right one-third of the time, that means that if you stay with your first choice, you'll get the prize one-third of the time.
That's what happens when your initial choice is correct.
So we know that the best you can do by staying is to get the prize 1/3 of the time.
See figure four:
Now let's look at the other possibility: that your initial choice is incorrect.
Only one time out of three is your first choice going to be correct. That means that the remaining times, your initial choice is going to be the wrong door. As we said earlier:
You're going to choose the wrong door 2/3 of the time.
And, as we said earlier, that means that 2/3 of the time, the other two doors (taken together) hide the prize.
Now look at the next diagram:
In the diagram, you can see that your initial choice is wrong: there is no prize there. And you can see that the prize is hidden by one of the remaining doors (in this figure, the central one). In this case, Monty Hall has no choice in what door to open for you — he has to open the rightmost door, because that's the only one of the two that does not hide the prize 4.
This leaves your initial choice, which is incorrect; and the remaining door, which hides the prize. We've already determined that your initial choice will be incorrect 2/3 of the time (it is those times we are looking at here). We've shown how that means (if it needed to be explained at all) that 2/3 of the time, the prize will be behind one of those two other doors. But in showing you which of those two doors does not hide the prize, Monty Hall has told you which does: the only one left. Keep thinking of the two doors, in aggregate, as having a 2/3 probability of hiding the prize. Now imagine that you know (and you do) which of the two doesn't. You can still think of the probabilities in aggregate — 2/3 — but now eliminate one possible choice. You might say that the remaining door “inherits” the probability of the eliminated door — so now for that one door, the probability of it being the door which hides the prize is 2/3.
Your initial choice has only one chance in three of being right — this remaining door has two chances in three.
Should you switch? Yep.
The Wrong “Solution”, and a More Concise Explanation of the Correct Solution.
I didn't discuss what the general, incorrect, intuitive “solution” to this problem is: I didn't want to mislead, or confuse you. It was, in fact, my own initial response to this problem. In short, I felt that after Monty showed me a losing door, that left two: one is right, the other wrong. It seemed to me, and to most people, that it's a 50:50 proposition: it doesn't matter if you switch, or not. Further, just to test my instinct, I asked myself “Well, did Monty Hall reveal any information in opening the losing door?” And it seemed to me that he did not. But he did.
He did, because he always has to open a losing door: one losing door is always eliminated. The probabilities of your initial choice being correct, and the remaining choices have to sum to equal one. Therefore, the probability of the remaining choices have to sum to equal one minus the probability of your initial choice. In this case (with three doors), they have to sum to equal 2/3. Say a door isn't opened. Then, you would have two to switch to (if you choose to switch — this would be like “changing your mind”), and your chance of picking the correct door would be 1/2 × 2/3. Well, that's 1/3, just like your initial choice. But if Monty has to open a door, then you'll only have one door to switch to. In this case (which is the Monty Hall problem), you'll pick the remaining door — so that'd be 1 × 2/3. And that's a probability of 2/3.
If there were four doors, then your chance of being correct with your initial choice would be 1/4. The remaining doors would have the remaining probabilities: 3/4. Again, if no door were opened (“changing your mind”), you'd have to pick one of the three, and that'd be 1/3 × 3/4. That's 1/4, of course. But if an incorrect door were opened, you'd have only 2 to choose from. So that'd be 1/2 × 3/4. That's 3/8, which is better than 1/4. (1/4, which is the best you're going to do by “staying.”) So it's best to switch. Always.
If you are disheartened that your intuition led you astray, rest assured that you're in good company. I've noticed that the general tone in rec.puzzles is that only ignorant or stupid people fall for the incorrect solution to this puzzle. Don't you believe it. I have argued about this puzzle with several people that one might not expect to get the answer wrong: physicists, and generally very smart people. And, I've heard of many Mathematicians being confused by this problem.
Finally, you may be interested to know how I approached the problem, and solved it. I was presented the problem, and also told that the obvious solution is wrong. I was aware of the controversy. What did I do? Well, normally I'm pretty much a theorist, but in this case it occurred to me that discovering the correct solution by experiment would save me some time. So I wrote a short program. Then I figured out why switching works. It baffles me that there are people who will insist that it's 50:50, and never make the effort to verify their claim.
An exaggerated modification of the problem, to make it really obvious...
Imagine that there were a million doors. After you have chosen your door, Monty opens all but one of the remaining doors, showing you that they are “losers.” It's obvious that your first choice is wildly unlikely to have been right. And isn't it obvious that of the other 999,999 doors that you didn't choose, the one door he avoided opening is wildly likely to be the one with the prize?
So you are still unconvinced? Check the citations and references.
About Obstinacy, Comprehension, and the Monty Hall Problem: An Exchange with a Skeptical Reader.
1 This isn't really how the actual game show worked. This problem gets its name from the show, because it inspired the problem — not that it truly reflects how contestants and Monty acted on TV. The actual behavior of Monty was more complex — making a math problem that truly reflected the show would be more simulation than puzzle. It's the puzzle that's interesting.
2 The standard annunciation of the MH problem, does not make explicit what I am assuming here: namely, that Monty will always open a door which does not contain a prize. Other possible assumptions could be that he only opens another door when you have selected the prize-hiding door (if that were true, you should never switch when he opens a door!); or that he randomly opens any remaining door (then it doesn't matter, see footnote 3); or any combination of the above actions (here we would have to begin to assign probabilities to Monty's actions).At any rate, I think the obvious assumption is that he will open a remaining losing door. This is what makes the problem interesting.
3 Actually, it only makes no difference as long as you are not aware of what his non-random reasoning is (if it is non-random). If you do happen to know what “rule” he uses for choosing between the two doors, and if that rule is dependent upon your choice (for example, he starts from your choice and moves “rightward”), then you could use that information to further increase your odds of winning over the standard version of the problem. Understand? If not, don't worry, stick with the basic, standard form of the problem. Just assume that Monty randomly chooses a losing door when you've chosen the winner, or that you don't know how he chooses a losing door when you've chosen the winner. But always remember that he always offers you a choice, and he always opens a losing door.
4 Here is an important fact of the statement of the problem: Monty Hall will not open the door that you initially selected to reveal that it was the wrong choice. If he could do so, this would be a very different problem, and the intuitive solution would be correct. Also, it would be a silly problem, because we wouldn't be asking if you should switch generally, because of course in the cases where he shows you that your first choice was incorrect, you'd switch. Unless you were very, very stupid. Still, you might want to work out the probabilities fully; because although you can't do better than 1/x, and it doesn't matter if you switch between (x - 1) unopened doors, it is amusing to calculate.
Citations and References
Some additions were made to this document as a result of my discovering the rec.puzzles USENET group. They keep an archive of puzzles and their solutions; in perusing it, I discovered the fact that inspired footnote 2. Also, I am stealing the references directly from them...
Copyright: 1995, Keith M Ellis