may 2016

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:

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

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 choose 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 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

We’re missing P(gl|~CI) and 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 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 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”.

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()