Monty Hall: the Complete and Definitive Solution
Monty Hall is a solved problem as far as I am concerned. The maths are simple and the experimental results unambiguous. Yet many otherwise reasonable people dispute those results. This article is my attempt end this once and for all. First, I'll solve Monty Hall with modern probability theory. Then I'm going to demonstrate those results experimentally.
Without further ado, the problem:
You are at a TV show. The host shows you three doors. The prize (a car) lie behind one of those doors —you have no idea which. Now the game proceeds as follows (this procedure is know to you):
- You choose a door.
- The host opens a door you have not chosen.
- You are offered a chance to switch. You can either stick to your guns, or choose the other closed door.
Now the door the host just opened happens to reveal a goat (no prize). Should you switch?
Note that whether the host always reveals a goat is carefully left unspecified. I did state you've just seen a goat, but I did not say whether you knew you'd see a goat. This is very important.
Applying Probability Theory
The easiest way to get the answer is simply to apply probability theory. Just compute your probability that the prize is behind your door —if it's lower than 50%, you want to switch.
So we have three doors, (1), (2), and (3). At the beginning of the game, you don't know where the car is. That is, given your background information I, your probability of the prize lying behind any given door is one third. In maths speak:
P(1|I) = 1/3 P(2|I) = 1/3 P(3|I) = 1/3
(Make sure you understand the notation, I'll be using it quite a bit.)
Choosing a door gives you no information, so the your probability that
you choose the car from the outset is one third. In maths speak (the
'C' stands for "you have chosen the car":
P(C|I) = 1/3
That's your prior probability. But we're not quite finished yet. The host opens a door, and what do you know, there's a goat behind it! Now what you want to know is this:
That is, the probability that your door has a car behind it, given
your background information, and the fact that the host just revealed
a goat (that's what the lower case
'g' means). That's your
posterior probability. Computing it is as easy as applying Bayes'
P(g|CI) P(C|I) P(C|Ig) = ──────────────── P(g|I)
(It's probably a little different from what you're used to. The
'I' is omitted from most textbooks. Modern
probability theory however never ignores it, so, like
E. T. Jaynes, I make it explicit.)
Now let's compute that formulae: your prior probability
1/3. Then, the probability that the host reveals a goat if you have
chosen the car,
P(g|CI), is 1 (he can't open the very door you have
1 × 1/3 1/3 P(C|Ig) = ───────── = ──────── P(g|I) P(g|I)
Now remember I haven't specified
P(g|I) (that is, whether you knew
or suspected that the host would reveal a goat). So we're stuck. I
have seen people disagreeing about the answer to the Monty Hall
problem because they did not share the same background assumptions.
For this problem, I am going to consider a number of scenarios.
Scenario 1: the goat
You know the host is going to reveal a goat. Whatever the reason
(he's done it before, you have insider intel…), your probability
P(g|I) is equal to 1. Therefore,
1/3 1/3 1 P(C|Ig) = ──────── = ───── = ─── P(g|I) 1 3
Your door is not a good choice. You should switch.
Really, this is not surprising at all: you knew the host was going to reveal a goat, and he did. No wonder your posterior probability is the same as your prior probability: you've learned nothing about your door. It was 1/3 before, it stays 1/3 after.
Another way to look at it is to look at the probability that a door
you have not chosen holds the car. At the beginning of the game,
P(~C|I) is 2/3. (The
'~' stands for
"complement": if you haven't chosen the car, it's on the other
doors). Now the hosts opens one of those two doors, revealing a goat
(as expected, like before). You have learned nothing, so your
P(~C|Ig) that one of those doors holds the car
P(g|~CI) P(~C|I) 1 × 2/3 2 P(~C|Ig) = ────────────────── = ───────── = ─── P(g|I) 1 3
Except now you know which one.
Scenario 2: the random
You are positive the host have no idea where the car is. Whatever
he's doing, he'll do no better and no worse than random. His odds of
revealing the car are 1/3, just like you. In this case, your
P(g|I) is 2/3. Therefore,
1/3 1/3 1 P(C|Ig) = ──────── = ───── = ─── P(g|I) 2/3 2
This time the goat revelation wasn't entirely expected. So when you see the goat, you do learn something about what lies behind your door. Too bad that new information only served to make you more confused than you were at the outset (there are only 2 doors left, so a probability of 1/2 means you're back to maximum ignorance).
Scenario 3: the enemy
The host knows where the prize is, and he'll make his best to snatch
it from you. You just know it. If you didn't choose the car the
first time around, you can bet your ass he'll reveal it. Since your
odds where one third to begin with, his odds are the remaining two
thirds. Your probability
P(g|I) is therefore 1/3. Therefore,
1/3 1/3 P(C|Ig) = ──────── = ───── = 1 P(g|I) 1/3
In plain speak, seeing the goat makes you certain the door you picked first was the right one. Obviously. If you haven't chosen the car, the host would have picked it. You don't even need probability theory to deduce that. Do not switch!
Scenario 4: the communist
For whatever reason, you know this host will open the leftmost door
—that you haven't chosen. You still don't know where the car is, so
as far as you know, your probability
P(g|I) that' he'll reveal a
goat is 2/3. Therefore:
1/3 1/3 1 P(C|Ig) = ──────── = ───── = ─── P(g|I) 2/3 2
That is, the same result as the random scenario.
Scenario 5: the helper
Some of you may have noticed that I omitted a potentially crucial piece of information in the goat scenario: which door exactly the host has opened. Sometimes, this information is irrelevant. Not always, though.
The helper uses a weird strategy: he behaves exactly like the goat, with a twist: if you have chosen the car, he'll pick the rightmost door (that you haven't picked, as always).
As in the goat scenario, your probability
P(C|Ig) is still 1/3.
But that's not what we're interested in this time. You've not just
seen a goat, you've seen whether the host opened the rightmost door
or the leftmost one.
g can be partitioned into 2 sub-events:
gl, where the
host opened the leftmost door, and
gr, where the host opened the
rightmost door. Your actual posterior probability is
P(C|Igr), depending on which door the host actually opened. Let's
consider the two scenarios (Bayes' formula again):
P(gl|CI) P(C|I) P(gl|CI) 1/3 P(C|Igl) = ─────────────────── = ────────────── P(gl|I) P(gl|I) P(gr|CI) P(C|I) P(gr|CI) 1/3 P(C|Igr) = ─────────────────── = ────────────── P(gr|I) P(gr|I)
We need to assess
P(gr|I), but also
P(gr|CI). The last two are easy: the helper chooses the rightmost
door that holds a goat. If you have chosen the car, he'll choose the
rightmost door, period. Therefore:
P(gl|CI) = 0 P(gr|CI) = 1
P(gl|CI) P(C|I) 0 × 1/3 0 P(C|Igl) = ─────────────────── = ───────── = ───────── P(gl|I) P(gl|I) P(gl|I) P(gr|CI) P(C|I) 1 × 1/3 1/3 P(C|Igr) = ─────────────────── = ───────── = ───────── P(gr|I) P(gr|I) P(gr|I)
P(gr|I) are a bit more complicated. To compute them,
you'll need the sum rule. For any event A and B, the sum rule says:
P(A|I) = P(A|BI)×P(B|I) + P(A|~BI)×P(~B|I)
In this case, the event
B we're interested in is whether we choose
the car or not. that is,
C. Applying the sum rule gives:
P(gl|I) = P(gl|CI)×P(C|I) + P(gl|~CI)×P(~C|I) P(gr|I) = P(gr|CI)×P(C|I) + P(gr|~CI)×P(~C|I)
Now let's review the quantities we already know:
P(gl|CI) = 0 P(gr|CI) = 1 P( C|I) = 1/3 P(~C|I) = 2/3
P(gr|~CI). If you have not chosen
the car, the helper choose whatever door holds the goat. With a little
bit of thinking (or yet another application of Bayes' formula), we can
P(gl|~CI) = 1/2 P(gr|~CI) = 1/2
P(gl|I) = 0×(1/3) + (1/2)×(2/3) = 1/3 P(gr|I) = 1×(1/3) + (1/2)×(2/3) = 2/3
Now we can go back to our original formula:
P(gl|CI) P(C|I) 0 × 1/3 P(C|Igl) = ─────────────────── = ───────── = 0 P(gl|I) 1/3 P(gr|CI) P(C|I) 1 × 1/3 P(C|Igr) = ─────────────────── = ───────── = 1/2 P(gr|I) 2/3
Meaning, if the host have chosen the leftmost door, there's no way you have chosen the car. You must switch. On the other hand, if he has chosen the rightmost door, you're back to maximum ignorance: switching won't change your odds.
Always mind your surroundings. You never know when you might get a relevant piece of information.
Scenario 6: the lunatic
The lunatic will adopt one of the above strategy. You don't know
which. This time,
P(g|I) depends on what kind of host you might
have, and that depends on your background information.
I'll leave that as an exercise for the reader. Just remember that if
you can assign a prior probability for each kind of host (such that
they sum up to 1),
P(g|I) will follow from a straightforward
application of Bayes' theorem.
Some of you may feel highly sceptical about these results. After all, I've only proven them right. Now we're going to test them. I've made a little program for that purpose (you need Lua to run it):
$ lua monty-hall.lua the_random choose_random_door 10 Door 2 has the car. You picked door 1. Host opened door 3 (right). Please switch. Door 1 has the car. You picked door 2. Host opened door 1 (left). You lose. Door 1 has the car. You picked door 1. Host opened door 2 (left). Do not switch. Door 3 has the car. You picked door 3. Host opened door 1 (left). Do not switch. Door 2 has the car. You picked door 3. Host opened door 1 (left). Please switch. Door 1 has the car. You picked door 3. Host opened door 1 (left). You lose. Door 1 has the car. You picked door 1. Host opened door 3 (right). Do not switch. Door 2 has the car. You picked door 1. Host opened door 3 (right). Please switch. Door 1 has the car. You picked door 3. Host opened door 1 (left). You lose. Door 2 has the car. You picked door 3. Host opened door 2 (right). You lose.
So we ran the game 10 times. Each line represents one game. It tells you which door had the car, which door you picked, which door the host picked, and whether you should switch (if you haven't lost already). We're going to run many such games, and count the lines where you should switch.
By default, we run 1000 games, and the player chooses the door randomly. I'm mostly interested in the host's strategy anyway. Now, we'll record 1000 games per host. Here:
$ lua monty-hall.lua the_goat > goat.txt $ lua monty-hall.lua the_random > random.txt $ lua monty-hall.lua the_enemy > enemy.txt $ lua monty-hall.lua the_communist > communist.txt $ lua monty-hall.lua the_helper > helper.txt
Now let's count.
The goat always opens a goat door. you never lose right away.
$ grep "You lose" < goat.txt | wc -l 0
When playing with the goat, you should switch 2 times out of 3:
$ grep "Please switch" < goat.txt | wc -l 670 $ grep "Do not switch" < goat.txt | wc -l 330
Of, course, you can't know in advance when to switch.
This one is a bit trickier, since we only want to consider the cases where the host opened a goat door. Because obviously…
$ grep "You lose" < random.txt | wc -l 322
Sometimes, the random actually opens a car door, and you're just screwed. But if you only consider the cases where you still have a chance:
$ grep "Please switch" < random.txt | wc -l 346 $ grep "Do not switch" < random.txt | wc -l 332
About half the time, you should switch. About half the time, you shouldn't. As expected from the maths. Some people deny the math, but they can't deny the data. And the data says: "when the random shows you a goat, your chances at winning the car are fifty fifty".
This one is simpler: if he can snatch open the car from you, he will. The effects are quite marked:
$ grep "You lose" < enemy.txt | wc -l 670
Then again, the problem only considers the cases where you don't lose right away:
$ grep "Please switch" < enemy.txt | wc -l 0 $ grep "Do not switch" < enemy.txt | wc -l 330
Never switch when the enemy's in charge. Obviously.
I've predicted the same outcome from the communist and the random. As for the actual results:
$ grep "You lose" < communist.txt | wc -l 353 $ grep "Please switch" < communist.txt | wc -l 323 $ grep "Do not switch" < communist.txt | wc -l 324
Same as the random.
Now this one is interesting. At a first approximation, he could as well be the goat:
$ grep "You lose" < helper.txt | wc -l 0 $ grep "Please switch" < helper.txt | wc -l 676 $ grep "Do not switch" < helper.txt | wc -l 324
That is, you never lose right away, and you should switch 2 times out of 3 (as always, never knowing when exactly).
But when you look at which door he opened however, you get a very different picture. With the goat, it doesn't matter. Consider only the cases where he opened the left door
$ grep "(left).*Please switch" < goat.txt | wc -l 337 $ grep "(left).*Do not switch" < goat.txt | wc -l 168
Same 2 to 1 ratio. As for the right:
$ grep "(right).*Please switch" < goat.txt | wc -l 333 $ grep "(right).*Do not switch" < goat.txt | wc -l 162
2 to 1 again.
The helper however only opens the leftmost door when the rightmost door has the car:
$ grep "(left).*Please switch" < helper.txt | wc -l 323 $ grep "(left).*Do not switch" < helper.txt | wc -l 0
Always switch when the helper opens the leftmost door. If he opens the right door however…
$ grep "(right).*Do not switch" < helper.txt | wc -l 324 $ grep "(right).*Please switch" < helper.txt | wc -l 353
That's right, you're left in the dark. 50/50 just like with the Random. Well, at least switching doesn't hurt.
Again, exercise for the reader.
-- returns a "random" number between 1 and n (included) -- feel free to replace this with crypto secure stuff function random(n) if math.random() < 1/n then return n else return random(n-1) end end -- Possible strategies for choosing the first door -- (Applicable for either the prize or the player) function choose_door_1() return 1 end function choose_door_2() return 2 end function choose_door_3() return 3 end function choose_random_door() return random(3) end -- From now on: -- * The car parameter says where the car is. -- * The choice parameter says which door the candidate has picked -- opens the leftmost door the candidate has not chosen function open_leftmost_door(choice) if choice == 1 then return 2 else return 1 end end -- opens the rightmost door the candidate has not chosen function open_rightmost_door(choice) if choice == 3 then return 2 else return 3 end end -- opens one of the doors the candidate has not chosen, at random function open_random_door(choice) if random(2) == 1 then return open_leftmost_door(choice) else return open_rightmost_door(choice) end end -- opens the goat door when there is only one possibility function open_goat(car, choice) if car == choice then error("2 possible choices") else if car ~= 1 and choice ~= 1 then return 1 else if car ~= 2 and choice ~= 2 then return 2 else return 3 end end end end -- Possible strategies for the host, (once the doors have been chosen) -- always opens a goat function the_goat(car, choice) if car == choice then return open_random_door(choice) else return open_goat(car, choice) end end -- opens a door at random function the_random(car, choice) return open_random_door(choice) end -- opens the car (if possible) function the_enemy(car, choice) if car == choice then return open_random_door(choice) else return car end end -- opens the leftmost door function the_communist(car, choice) return open_leftmost_door(choice) end -- opens the rightmost door iff it holds a goat function the_helper(car, choice) if car == choice then return open_rightmost_door(choice) else return open_goat(car, choice) end end -- So we can print like a *real* programmer local printf = function(s, ...) return io.write(s:format(...)) end -- Runs the game once function run_game(player, host) local car = random(3) local choice = player() -- player knows nothing local opened = host(car, choice) -- host knows where the car is if opened == choice then error("the host can't open the door you picked!!!") end printf("Door %d has the car. ", car) printf("You picked door %d. " , choice) printf("Host opened door %d " , opened) if opened == open_leftmost_door(choice) then printf("(left). ") else printf("(right). ") end if opened == car then printf("You lose.\n") else if choice == car then printf("Do not switch.\n") else printf("Please switch.\n") end end end function run_many_games(nb_games, player, host) for i = 1, nb_games do run_game(player, host) end end -- main program. Possible usages: -- Usage: lua monty-hall.lua [[[host] player] nb_games] -- -- Examples: -- lua monty-hall.lua -- lua monty-hall.lua the_goat -- lua monty-hall.lua the_random choose_door_2 -- lua monty-hall.lua the_enemy choose_door_1 50 -- lua monty-hall.lua the_communist -- lua monty-hall.lua the_helper -- -- Possible hosts: -- the_goat (by default) -- the_random -- the_enemy -- the_communist -- the_helper -- -- Possible players: -- choose_random_door (by default) -- choose_door_1 -- choose_door_2 -- choose_door_3 -- -- nb_games is a positive integer. 1000 by default function main() -- default settings local host = "the_goat" local player = "choose_random_door" local nb_games = 1000 if arg ~= nil then host = arg end if arg ~= nil then player = arg end if arg ~= nil then nb_games = arg end run_many_games(tonumber(nb_games), _G[player], _G[host]) end main()