may 2016

# Monty Hall: the Complete and Definitive Solution

Monty Hall is a solved problem as far as I am concerned. The math is 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 chose 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 chose the
otherclosed 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 math 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 chose the car from the outset is one third. In math 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:

```
P(C|Ig)
```

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'
formula:

```
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
background information '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 `P(C|I)`

is
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
chosen). So:

```
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,
this probability `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
posterior probability `P(~C|Ig)`

that one of those doors holds the car
is unchanged:

```
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
probability `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 chose 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.

The event `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|Igl)`

or
`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(gl|I)`

and `P(gr|I)`

, but also `P(gl|CI)`

and
`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 chose the
rightmost door, period. Therefore:

```
P(gl|CI) = 0
P(gr|CI) = 1
```

Therefore:

```
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(gl|I)`

and `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 chose
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
```

We're missing `P(gl|~CI)`

and `P(gr|~CI)`

. If you have *not* chosen
the car, the helper chose whatever door holds the goat. With a little
bit of thinking (or yet another application of Bayes' formula), we can
deduce that:

```
P(gl|~CI) = 1/2
P(gr|~CI) = 1/2
```

Then,

```
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.

## Experimenting

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

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.

### The random

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 math. 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".

### The enemy

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.

### The communist

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.

### the helper

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.

### The lunatic

Again, exercise for the reader.

## Source code

```
-- 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[1] ~= nil then host = arg[1] end
if arg[2] ~= nil then player = arg[2] end
if arg[3] ~= nil then nb_games = arg[3] end
run_many_games(tonumber(nb_games), _G[player], _G[host])
end
main()
```