This page describes the solution to the MontyHallProblem
. Do not read further if you don't want the puzzle spoiled.
Keep in mind that Monty knows
behind which door the prize is, and will always
open an empty door. He will not cheat by moving the prize, and he will always offer you the opportunity to switch.
Note the denouement of "Slumdog Millionaire" featured the MHS in action.
The short answer, from http://www.faqs.org/faqs/puzzles/faq/:
- The probability that your first guess is right is only 1/3, and sticking to the same door will win you the prize if and only if your first guess was right (probability 1/3).
- After Monty opens the empty door, you know which door to pick if the prize was behind one of the two other doors (probability 2/3).
So switching changes your probability of winning from 1/3 to 2/3.
How about this.
- There are 3 doors, behind one is the prize.
- Monty lets you choose one door.
- You choose a door.
- Monty tells you this: You can keep what's behind the door you chose, or you can have what's behind both of the other doors.
What do you do?
But note that there is a fundamental difference from the original MontyHallProblem: Here, you do not gain any information from Monty's offer. In the original problem, Monty tells you something which you didn't know before. This new information helps you to make a better choice, as strange as it might sound.
Aha! This might be the sticking point that is confusing people. The benefit here is not the information, but the opportunity to act
on the information. You knew when you chose a door that one of the two other doors was empty. Only when he gives you the chance to have the prize if it's behind either
of the other two doors do you get better odds. This is the same choice that you are given in the original problem. (Just close your eyes when he opens the door!)
Under the usual set of assumptions about this problem, the concise solution is as follows:
The a priori probability that the prize is behind door X,
p(X) = 1/3
The probability that Monty Hall opens door B if the prize were behind A, B or C [m(X) meaning Monty opens door X]:
p(m(B)|A) = 1/2
p(m(B)|B) = 0
p(m(B)|C) = 1
The probability that Monty Hall opens door B is then
p(m(B)) = p(A)*p(m(B)|A) + p(B)*p(m(B)|B) + p(C)*p(m(B)|C)
= 1/6 + 0 + 1/3 = 1/2.
Then, by BayesTheorem?
, the chance that the prize is behind door A if Monty opens door B is:
p(A|m(B)) = p(A)*p(m(B)|A)/p(m(B))
= (1/3)*(1/2) / (1/2)
and the chance that the prize is behind door C if Monty opens door B is:
p(C|m(B)) = p(C)*p(m(B)|C)/p(m(B))
= (1/3)*(1) / (1/2)
Here's a different expression of the same solution, which may make more sense to some people. (It did to me.)
Intuitively, we'd think there'd be a probability of 1/2 success, whether we stay or switch. But in order to compute the odds correctly, we must take into account the fact that Monty tailors his behavior depending on what door we choose
. We don't know what Monty's behavior is, but we do know the probability distribution of that behavior, and we can use Bayes Theorem then to determine our probability of success under each scenario.
- Let P(D=d) be the probability that the prize is behind door d, 1 <= d <= 3. We'll abbreviate this as P(d).
- Let d1 be the door we choose initially, where dn != dm for any n and m between 1 and 3, n != m.
- We know that P(d1) = 1/3.
- Let P(M=m) be the probability that Monty opens door m. We'll abbreviate this as P(m).
- Let m2 be the door Monty opens, where mn = dn for all n.
- After Monty reveals m2, we need to evaluate whether to stay with d1 or switch to d3. We need to find P(d1|m2) and P(d3|m2):
- We know that P(m2|d1) = 1/2 (because we chose d1 the door with the prize, and Monty could then open either m2 or m3).
- We know that P(m2|d2) = 0 (because Monty will never open m2 if it contains the prize).
- We know that P(m2|d3) = 1 (because we chose d1 and the prize is behind d3, leaving only m2 for Monty to open).
- By Bayes Theorem (http://en.wikipedia.org/wiki/Bayes_theorem), P(di|m2) = P(m2|di)*P(di) / sum(P(m2|dj)*P(dj)), where j=1 to 3. Since P(di) = 1/3 for all i, and since we know P(m2|di) for all i, we plug in the values and get:
P(di|m2) = P(m2|di) * 2/3.
Therefore, if we stay, P(d1|m2) = P(m2|d1) * 2/3 = 1/3.
If we switch, P(d3|m2) = P(m2|d3) * 2/3 = 2/3.
The long, and correct, explanation:
Assume there are n doors. There are two strategies, to switch A and not to switch B. Let's analyse strategy A.
- If you choose the right door the first time (probability 1/n), you have a (probability 1) chance of losing by following strategy A.
- If you choose the wrong door the first time (probability n-1/n), you have a (probability n-3/n-2) of losing by following strategy A.
n-2 comes from the fact that the door you initially picked is excluded and the door Monty throws away is excluded. n-3 comes from the fact that the right door (which you fail to pick) is also excluded.
So the Total probability that you lose by following strategy A is
= (n-1/n)(n-3/n-2) + 1/n
= (n-1)(n-3)/n(n-2) + n-2/n(n-2)
= (n-1)(n-3) + (n-2) / n(n-2)
= n^2 - 3n + 1 / (n^2 - 2n) <eq 1>
This is a horrendous equation and it's not clear how to solve it or how it behaves. The good news is you don't have to! You just have to compare it with the Total probability that you lose by following strategy B (not switching), which is just
n-1/n <eq 2>
If strategy A is better than strategy B then it follows that
<eq 1> <= <eq 2>
n^2 - 3n + 1 / (n^2 - 2n) <= (n - 1) / n
(n^2 - 3n + 1) n <= (n^2 - 2n) (n - 1) # re-arranging
n^3 - 3n^2 + n <= n^3 - 3n^2 + 2n # ain't math beautiful?
...which is true for n = 0, 1, 2 and obviously true for all greater n too.
What's interesting is that in the case of n = 0, this final inequation seems to give the correct result. If there is no game to play, both strategies have equal payoff. In the case of n = 1, the switching strategy is ill-defined...
But anyways, there you have it!
At the start of the game, the prize is behind one of the doors. Let's assume that they neither move the prize into position after the game begins, nor move the prize during the game. Sheer physics says that the prize's position at the beginning of the game sets the stage.
Also, let's explore all permutations. If you choose an one of the incorrect doors, Monty can choice is reduced to only one (two scenarios). However, if you choose the correct door, he has two choices (another two scenarios).
Also, the choices you have are either to switch or not. Running through the possible permutations under a no-switch scenario should give you a ratio of wins to losses.
Let's assume for the sake of simplicity that the prize is behind door #3. Chances are given in brackets.
- [1/3] You choose #1
-  Monty eliminates #2
- stay with #1 loses; switch to #3 wins
- [1/3] You choose #2
-  Monty eliminates #1
- stay with #1 loses; switch to #3 wins
- [1/3] You choose #3
- [1/2] Monty eliminates #1
- stay with #3 wins (A); switch to #2 loses
- [1/2] Monty eliminates #2
- stay with #3 wins (B); switch to #1 loses
To find the probability of winning by staying, we add the probabilities of A and B to get:
1/3 * 1/2 + 1/3 * 1/2 = 1/3
Therefore the probability of winning by switching is 2/3.
(The previous inconclusive analysis here assumed a probability 1/2 of switching, and then calculated the probability of winning in that case as 1/2. That's right; it's just not what you needed to know.)
How about this
- There are 3 boxes, one has the prize. No-one knows which (and you know that no-one knows).
- Monty lets you choose one box.
- You choose a box.
- Monty opens one of the other boxes - it's empty.
- Monty tells you: keep the box you chose, or keep the other box.
- What do you do?
Answer (a): It doesn't matter.
Answer (b): You should change your choice.
For the answer see MontyHallVariationSolution
Comments from our readers:
I didn't believe the correct solution (change box) so I tried it at home and found it works. I made good money betting people :-) -- NissimHadar
The Car Guys on Car Talk got this wrong about 15 years ago. I once had a guy I worked with go ballistic when I mentioned this because his professor
had told him it didn't matter and that settled the issue. So I never discussed anything technical with him ever afterward.
[It]'s been said before and I understand that part. It's totally intuitive to me that the answer should be to switch, now. I'd like it to be totally LOGICAL to me as well. The question above about why it should be different if Monty doesn't know which box is what continues to bug me...
The best way of thinking about this problem I've found is to imagine that you've got a million doors instead of three.
- You pick a door at random (#1)
- Monty opens doors #2 through #425,849, passes door #425,850 and opens the doors #425,451 through 1,000,000 revealing that they're all empty.
- Do you switch doors?
Your original door has a 1/N probability of being right, no matter what information you have - if you can do better than that, you're a magician. Monty opens all doors apart from your door and one other. The prize is therefore behind one of those two doors. Therefore, the other door has a probability of 1 - 1/N.
[I find this explanation totally unconvincing, because it's only a coincidence of there being 3 doors that Monty is opening all but 1 of your other choices. Assume you have a million doors, you choose one, Monty opens *one* door, there's still 999,998 doors left. Do you switch?]
I still don't buy all this math. Imagine I select door A (and tell Monty), and then have a major case of amnesia. The next thing I remember is Monty saying "It's not behind door C". Being embarrassed about my amnesia, I try not to let anyone know that I forgot which door I previously choose. I mentally flip a coin (50-50 chance) and say: "In that case, I pick door B". Monty: "So you're changing your mind?". Me: "Yes".
When Monty opens door B to show me, I have a 50% chance of winning the prize. The only decision I remember making is the coin flip for A Vs B. My previous actions had no affect on this choice. But everyone else thinks that I changed my mind. If the math on this page is to be believed, then an external observer thinks I made a decision that gave me a 2/3 chance of winning. If this were quantum mechanics, I might believe that both probabilities are correct. But this is a simple classical problem. I made a 50-50 decision, so my probability of winning is 50%.
Groan groan groan. People, if you don't believe the math, you have an easy solution open to you, that works even if you don't know math. Run a damn test a few dozen times. When you still don't believe what you see, run it a few thousand times. But anyway... :)
You're right, you made a coin flip. If you flip a coin, you will win the prize 50% of the time. But that's only because you fail to take advantage of the weighting. Here's the setup: ("X" is the prize, "< >" is your pick)
[ ][ ][X]
You have three choices:
< >[ ][X]
[ ]< >[X]
[ ][ ]<X>
In which case, Monty will remove one box:
Now, consider the effects of flipping a coin:
< >[X] or [ ]<X> = 50/50
< >[X] or [ ]<X> = 50/50
[ ]<X> or < >[X] = 50/50
Six outcomes, with three winning and three losing. On the other hand, consider blindly switching:
[ ]<X> = you win
[ ]<X> = you win
< >[X] = you lose
The important bit is that there are now only three possibilities, and that they are weighting towards winning!
Here's another way to look at the same thing:
There's one-third a chance you initially chose the door with the prize. In this case, Monty reveals one of the losing doors. The remaining door, the one not chosen and not revealed, is also a losing door. In this case, if you switch, you lose.
There's a two-thirds chance you initially chose one of the losing doors. In this case, Monty reveals the other
losing door. The remaining door, by process of elimination, is the door with the prize. In this case, if you switch, you win.
Therefore, in general, there's a 1/3 chance that if you switch, you lose; and a 2/3 chance that if you switch, you win.
It's kind of a fuzzy-logic version of "Where did you hide the prize?"
"It's not in the closet! Here, let's look under the sofa!"
Hmm. Maybe I should look in the closet.
Monty knows which door has the prize, and he'll never reveal that door to you, nor the door that you chose. By selecting the door Monty did not
reveal, you're using his knowledge of where the prize is.
If you suffer a bout of amnesia, you lose the information that Monty may have avoided a certain door, and your chances drop to 1 in 2 instead of 2 in 3. This is why it's important to remember which door you chose and which Monty revealed, and to pick the remaining door as your final answer.
Indeed, there's no need for complex math, but the solution is unintuitive enough that it confounds a lot of people, including me. (That is, it used to.) Working through the complex math helped me sort it out. In the table above, you forgot to assign probabilities to the four outcomes. They are not equally likely. Note that the probability of the first pick being A, B, or C is each 1/3. Therefore, the probability of first picking B is 1/3, and the probability of picking C is 1/3, and the probabilities of picking A must total 1/3, as follows:
1st Monty Stay Switch Probability
Pick Opens of scenario
A B Win Lose 1/6
A C Win Lose 1/6
B C Lose Win 1/3
C B Lose Win 1/3
You'll note that the probabilities total 1. As you can see, there is a bias toward switching. The probability of winning if you switch is 2/3; whereas the probability of losing if you switch is only 1/3.
Aaughhh! Of course. The short form of the solution is that a switch wins if and only if your first pick is not the door with the prize. That's true 2/3 of the time. -- MarcThibault
While I understand the math, the probabilities and tables just fine (and have for decades), a part of my head always has always said "but... but..." until I read MarcThibault
's 2-line 'short form' above. -- MichaelWilson