oscarbonilla.com

The Monty Hall problem

After all the positive feedback I got from Visualizing Bayes’ theorem, I thought I’d post my explanation of the Monty Hall problem. I was fascinated for a while with this problem because at first it doesn’t seem to make any sense. And most of the explanations I’ve seen have a magic feel to them. I’ve even seen people with math backgrounds argue against the result.

I think the problem has to do with most of the explanations mixing two very different probability classes. But I’m getting ahead of myself.

The Problem

The problem statement (from Wikipedia) is:

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (Schrock 1990) [1]

If you are like most people, your gut feeling is going to be “it does not matter. There is a 50-50 chance that the car will be in the door I have already selected”. Like most people, you would be wrong.

In order to solve this problem, you need to consider two very distinct pieces of information. One is “what state is the world in?”, the other is “what events have occurred?”. Let me elaborate.

The States of the world

When I deal with probabilities and get confused, I revert to counting. What are all the possible outcomes? What subset of those outcomes am I looking at? So let’s look at all the posible states.

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats.

Let’s translate that to a simple diagram. We have three doors, let’s label them A, B, and C. We also know that there is a car behind one of the doors, it can be behind door A, B, or C. So we have three possible configurations of the world:

picture-22The door with the car has been colored red. The possible states of the world are Sa (meaning the car is behind door A), Sb (car behind door B), and Sc (car behind door C).

Quick, what is the probability of the car being behind door A? Or to put it another way, what is the probability that the world is in state Sa? Note that these two questions are the same, but the latter reminds us of the possible states. It is easy then to see that

p-fig1Now I’m going to ask you a very different question. Assume that instead of playing, you are observing your friend play the game. What is the probability that he will pick door A? Did you say 1/3? Of course you did, there are three doors and he must pick one. However, and this is really important, these probabilities are completely independent of the probabilities above!

Think of it this way. If two doors had cars behind them instead of just one, would that change the number of states the world can be in? Would it change the probability of your friend choosing door A? What if all doors had cars? Now there is just a single state for the world, but your friend can still choose door A with 1/3 probability!

If we now say that A is the event of your friend opening door A, we can easily see that

p-fig2which is just saying each door has an equal probability of being opened.

The trick to solving this problem is that you are dealing with two different classes of probabilities. One is the probability that the world is in a given state (a priori), the other is that a participant (you or Monty) chooses any given door. If you can keep these two classes of probabilities separate, you will be able to easily solve this problem.

Let’s see what happens once you have made the choice. Let’s assume you chose the door labeled A.

What does Monty do?

Monty is, of course, the host of the game show. And he is trying to screw you. He doesn’t want you to get the car. He also happens to know where the car is, or in other words, he knows the state of the world. You on the other hand, are only guessing. You chose door A with probability 1/3, now he gets to choose a door. But there are only two doors left. He must choose either door B or door C.

So how does Monty choose? What is the probability that Monty will open the door labeled B? Here’s what the world looks like to Monty:

picture-23Door A has been chosen, he must choose between doors B and C. Were he to choose randomly, each door would be equally probable,

picture-10

The little m‘s are a reminder that this is Monty’s choice, not your original choice. If you wanted to be pedantic you could add P(Am) = 0 since Monty can never choose door A (you chose that one).

But he knows better than to choose randomly, he knows whether we’re in Sa, Sb, or Sc! How he chooses will depend on what the state of the world is. If we are in Sa, it doesn’t matter what he chooses, he’ll choose B or C with equal probability as neither has a car[2]. That is to say “given that we are in state Sa, Monty chooses door B with probability 1/2″, in other words:

picture-12If we are in state Sb, Monty will never choose door B, that would be giving away the prize.

picture-14And finally, if we are in state Sc, Monty will always choose door B.

picture-15Your turn

And now it’s your turn to make a decision. Do you stay with your original choice of door A? Or do you switch and choose door C?

First of all, does it matter? Is there any difference whether we switch or not? The answer is a resounding YES! Monty gave away information about the state of the world by choosing door B. We can use that information.

What we are really trying to figure out is this: “what configuration is the world in?” Monty knows, he used that information to choose door B. Now we have to ask ourselves, “given that Monty chose door B, what is the probability that the world is in state Sa versus the probability of the world being in state Sc?” Note that we have eliminated Sb because Monty has already opened door B and there was no car!

Here is where we can apply Bayes’ formula to get an answer:

picture-16and plugging in the values we have already computed:

picture-17Which means we have a 1/3 chance the car is behind our original choice of door A. Note that this 1/3 probability is different than the original P(A) = 1/3 we had computed. It ends up being the same number, but it is really a different probability!

What about the car being behind door C? What is the probability that we are in state Sc, given that Monty chose door B?

picture-18and plugging in the values we get:

picture-21Which means we have a 2/3 chance the car is behind the other door (door C). Therefore we should switch.

Does it matter if Monty knows?

The only reason we managed to gain any information from Monty’s choice of door B is that he knows the state of the world and acts differently depending on what state is the correct one. If Monty didn’t know, he would have been choosing randomly between doors B and C and we would not have gained any information (except that Sb is not possible since there was no car behind door B).

If Monty always chooses door B when neither B nor C have the car, we would not have gained any information when he opens door B, but we would gain information if he opens door C (do you see why?).

Note that it is still to our advantage to switch doors, since in this case the probabilities for the states Sa and Sc are the same (1/2). And if we don’t know whether Monty knows or not, we might get an advantage from switching.

  1. If you are really pedantic, the mathematically correct definition of the problem is: “Suppose you’re on a game show and you’re given the choice of three doors. Behind one door is a car; behind the others, goats. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door,the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you “Do you want to switch to Door Number 2?” Is it to your advantage to change your choice? (Krauss and Wang 2003:10)” []
  2. This is important, if he doesn’t choose either door randomly, you gain information asymmetrically. Keep reading. []

Written by ob

May 5th, 2009 at 7:27 am

Posted in Math

Tagged with

25 Responses to 'The Monty Hall problem'

Subscribe to comments with RSS or TrackBack to 'The Monty Hall problem'.

  1. The New York Times published a nice explanation of this – check out http://www.nytimes.com/2008/04/08/science/08monty.html

    Rick Regan

    5 May 09 at 2:16 pm

  2. The problem is simple once you think about it a bit…

    There are 3 doors, behind one of which is a car.

    Would you like to look behind 2 doors to find the car, or only one?

    Its amazing how this one can consistently fool the smartest people.

    blackpage

    5 May 09 at 3:28 pm

  3. Well, if you don’t need proof but your audience simply doesn’t believe you, pretend the problem had 1000 doors, and you picked one. Monty opened all the rest but one, and they all had goats. Do you really think that you picked the right door?

    Lance

    5 May 09 at 4:44 pm

  4. In summary:
    There is a 1/3 chance the car is behind the door you pick.
    There is a 2/3 chance it’s somewhere else.

    These odds remain true both before and after Monty opens another door.

    So there’s still a 2/3 chance the car is somewhere else: namely behind that other door.

    Dman

    5 May 09 at 7:30 pm

  5. Actually, no. If Monty chooses randomly (he doesn’t know where the car is), then there is a 1/2 chance the car is somewhere else.

    ob

    5 May 09 at 8:05 pm

  6. [...] hidden prizes. There’s all kinds of high end mathematics involved in many of these analysis (see here for [...]

  7. Oscar, thank you again for your explanation skills!

    Though the math is logical (no surprise there ..), my “gut” doesn’t believe you.
    To align stomach and mind, I wrote up a small “Monty Hall”-Simulator. As I am probably not the only reader with “gut feelings”, I put the source on github.

    Jens

    Jens

    5 May 09 at 10:35 pm

  8. Fantastic! It took me a second to realize the github URL was linked from the post ;)

    ob

    6 May 09 at 12:11 am

  9. If this assumption:
    “Monty is, of course, the host of the game show. And he is trying to screw you. He doesn’t want you to get the car. ”
    is correct, then Monty would only ever give you a chance to switch in the case you chose correctly the first time. If you didn’t choose correctly, he’d just say nope, wrong, get off my stage. So, you would never switch.

    Consider the other states of Monty. He can want you to win, or not care if you win. The odds change. What are the odds that Monty is in any particular state? Cannot be calculated. Thus the actual answer to this problem is “not enough information to determine”

    Simonsays

    6 May 09 at 2:31 am

  10. Monty removes one of the other two doors from consideration, and in effect we have to re-allocate the probability we had formally accorded to that door before Monty revealed it was not the correct one.

    Your solution appears to always reallocate 100% of its probability to the other as-yet-unselected door. That does not seem correct to my layman’s appreciation of math.

    Look at it from Monty’s point of view. When we arrive at his decision of which door to reveal, there is a 1/3 probability that our door choice makes his reveal meaningless and effectively random (because we chose the door with the car). There’s a 2/3 chance that our door choice forces his hand, and he really has no choice in what to do (because one of the reamining doors holds the car, and he will never choose that door).

    Do we not reallocate the probabilities based on that? So, 1/3 * 1/3 is reallocated to the door I chose, and 2/3 * 1/3 is reallocated to the as-yet-untouched door.

    Final probabilties:

    My original door: 1/3 + (1/3 * 1/3) = approx. 44%
    The other door: 1/3 + (2/3 * 1/3) = approx 56%
    Monty’s chosen door: 0% (revealed as a goat)

    Can someone help me understand if/why my solution is not correct?

    Layperson

    6 May 09 at 5:18 am

  11. From the problem statement:

    …and the host, who knows what’s behind the doors…

    Steve

    6 May 09 at 6:20 am

  12. > Consider the other states of Monty. He can want you to win, or not care if you win. The
    > odds change.

    Actually, the odds don’t change. Assume Monty cannot open the door with the car and win himself, and let’s consider just the case where you picked door A (Sa) and Monty is deciding whether to open door B (B_m), since door C is equivalent.

    If Monty wants you to win, he chooses P(B_m|Sa) = 1/2, P(B_m|Sb) = 0, and P(B_m|Sc) = 1. Exactly as if he wants you to lose! What if he doesn’t care? Again, the only time he has a choice about which door to open is when you chose the winning door (in other words, Sa).

    As for giving you a chance to switch, we’re assuming that is part of the problem statement. They do it to build up some suspense ;)

    ob

    6 May 09 at 7:42 am

  13. Thanks. I actually forgot to paste the link to github. Here it is: http://github.com/Jens-n/Monty-Hall-Problem

    Jens

    6 May 09 at 10:52 am

  14. A simpler way to look at this is to consider the result of two strategies, sticking with your original choice, and switching, for each of the three possibilities for what is behind the originally chosen door;

    The following table shows what you will get for each strategy;

    Car Goat Goat

    Stick Car Goat Goat
    Switch Goat Car Car

    Since each column is equally likely (your first choice being truly random), the ‘Stick’ strategy has a 1/3 chance of winning the care, and the ‘Switch’ strategy 2/3rds

    Bill Aylward

    7 May 09 at 9:37 am

  15. On the pedantic footnote 1: its REALLY important. If your were playing the game and Monty really was trying to screw you. He would only open another door if you had chosen the one with the car. Otherwise, he would just stop the game. And the smarter you are about probability theory, the more easily he will screw you.

    Of course Monty wasn’t trying to screw the contestants. He wanted them to succeed so that he could launch into a paean about that great new Pontiac. That may amount to screwing the viewers, but we were rapt.

    Dr. Decay

    11 May 09 at 4:15 am

  16. The puzzle is tricky because it looks like there is a 50/50 chance that the money (or whatever prize is being offered) can be behind either door. And this is true. If you randomly choose a door you will win half the time. BUT if you do NOT randomly choose but always switch you will win two out of three times. So
    ALWAYS SWITCH and you will win two out of three time. If you stick with your original choice you will win one out of three times.
    Here are the options:
    Always switch:; you will 2 out of 3 times.
    Randomly choose: you win half the time.
    Stick with original choice: you win 1 out of 3 times.

    Richard Hammerud

    7 Jun 09 at 11:05 am

  17. When you first choose a door you have a 1:3 chance of winning.
    Monty has a 2:3 chance of winning – he has 2 doors.
    If you could swap with him your chances obviously are now 2:3.
    When one of his doors is opened to reveal a goat his chances are now the same as yours 1:3.
    it’s now 50/50 – swapping makes no difference. One door has gone and the 2:3 odds go with it.
    Imagine if Monty had opened the door with the car behind it instead of one with a goat behind it, if it was your door you now have 100% chance of winning so long as you don’t swap.
    If it’s one of his doors you have 100% chance of losing if you don’t swap.
    Maths is simple and puzzles like this confuse people into thinking they don’t understand it so playing into the hands of those who try to use maths as a mystery language that can only be understood by them. Don’t be fooled.

    Paul Tiemens

    20 Jul 09 at 4:17 pm

  18. You would be correct if Monty was opening a door randomly. The difference occurs when he acts based on information that he possesses. If you don’t believe it, run a little experiment and convince yourself. Or download this program and run the experiment.

    ob

    20 Jul 09 at 4:31 pm

  19. Sorry – Yes you are right. Monty is in fact swapping his two doors for your one door because in effect he is telling you which door of either of his two is a loser and is now giving you the option of opening the other one as well. So you do now have a 2:3 chance of winning.
    If Monty has two doors (1 & 2) and you have door 3 ;-
    With all doors closed. After opening one of Monty’s losing doors.
    (1 & 2) 3 (1 & 2) 3
    possible Win L L W – L W
    or Lose L W L – W L
    combinations W L L W – L

    Paul Tiemens

    21 Jul 09 at 11:33 am

  20. Unfortunately the spacing in the last five lines above did not transmit as a table and looks like the ramblings of a mad scientist – how apt you might say?
    There are three possible combinations for the three doors 1,2&3 ;- Lose,Lose,Win. Lose,Win,Lose, and Win,Lose,Lose.
    What it is meant to show is that each door has the possibility of one Win and two Loses as for example your chosen door – say door 3. But two doors together as Monty has – say doors (1 & 2) have a total possibility of two wins and four loses. If as you say he always opens a losing door then he is left with two wins and only one lose between the two doors.

    Paul Tiemens

    21 Jul 09 at 12:06 pm

  21. Heh, yeah. I read the previous one and couldn’t understand a word. This one makes sense.

    ob

    21 Jul 09 at 1:00 pm

  22. Here’s a good video explaining the problem in plain English:

    http://www.youtube.com/watch?v=koPBkK_Ra-k

    Philip Brocoum

    7 Oct 09 at 5:57 am

  23. The original statement is that there are three unknown doors. When you “open” one door the original statement is false. There are two unknowns. In this case door a and c.
    question should be
    which statement is true
    a=1
    or
    b=1
    or
    c=1
    a+b+c=1
    if
    b = 0
    then
    a or b =1
    Your chances are 50%

    Therefore door and and c are equal.

    With the common system if you choose a and they open door a and it is found to be correct you should still change because you odds are higher with two incorrect choices than the correct.
    It goes back to the opening statement. If we have three unknowns. The moment you only have two unknowns this becomes false and you have an entirely new equation.

    KK

    30 Oct 09 at 3:50 pm

  24. [...] an example, in the Monty Hall problem, if you second cousin thrice removed is part of the staff and he lets you in that the car is not in [...]

  25. [...] I've written about the Monty Hall Problem here. [...]

Leave a Reply