2003-11-24

The Full Monty (Hall Problem)

It is very easy to get the wrong answer to The Monty Hall Problem. I'll quote an excerpt of the above referenced page at MathWorld without spoilers so you can have the fun of trying to spot the error as you follow along:

The Monty Hall problem is named for its similarity to the Let's Make a Deal television game show hosted by Monty Hall. The problem is stated as follows. Assume that a room is equipped with three doors. Behind two are goats, and behind the third is a shiny new car. You are asked to pick a door, and will win whatever is behind it. Let's say you pick door 1. Before the door is opened, however, someone who knows what's behind the doors (Monty Hall) opens one of the other two doors, revealing a goat, and asks you if you wish to change your selection to the third door (i.e., the door which neither you picked nor he opened). The Monty Hall problem is deciding whether you do.

Here is my exploration of why it is so easy to get wrong.

Naiive Case Exhaustion Analysis

When presented with a small enough problem (or one that can be reduced to a small enough problem), exhaustion of cases is a great way to search for a solution. Lets apply this technique to the Monty Hall Problem...

Suppose the three doors are A, B and C. Suppose further (without loss of generality) that door A is the winning door, even though we don't know that going in. Now, lets show all possible cases (accounting for the fact that the host will not open our chosen door, nor will he open the winning door) for each strategy and see how each strategy fares.

We'll model our analysis directly after the statement of the problem.

In the tables below, "Choose" is the door we choose, "Opens" is the door the host shows us, and "Switch" is whether or not we switch after the host opens a non-winning door. "Win" is whether or not we win.

First, the "Sticker" (non-switcher):

  Choose  Opens  Switch  Win
  _____________________________
    A       B      N      Y
    A       C      N      Y
    B       C      N      N
    C       B      N      N
  _____________________________

So the "Sticker" wins 2/4 cases = 50% of the time.

Now, the "Switcher":

  Choose  Opens  Switch  Win
  _____________________________
    A       B      Y      N
    A       C      Y      N
    B       C      Y      Y
    C       B      Y      Y
  _____________________________

So the "Switcher" wins 2/4 cases = 50% of the time.

This seems pretty reasonable, but most certainly does not match the results indicated in the above reference.

More Exhaustive Analysis

Under the assumption that we left something out of the above analysis, lets be a bit more explicit about the cases that can't happen and see if it helps:

First, the "Sticker" (non switcher):

  Choose  Opens  Switch  Win
  _____________________________
    A       A      CAN'T HAPPEN
    A       B      N      Y
    A       C      N      Y
          .....................
    B       A      CAN'T HAPPEN
    B       B      CAN'T HAPPEN
    B       C      N      N
          .....................
    C       A      CAN'T HAPPEN
    C       B      N      N
    C       C      CAN'T HAPPEN
  _____________________________

So, the "Sticker" still wins 2/4 cases = 50% of the time.

Now, the "Switcher":

  Choose  Opens  Switch  Win
  _____________________________
    A       A      CAN'T HAPPEN
    A       B      Y      N
    A       C      Y      N
          .....................
    B       A      CAN'T HAPPEN
    B       B      CAN'T HAPPEN
    B       C      Y      Y
          .....................
    C       A      CAN'T HAPPEN
    C       B      Y      Y
    C       C      CAN'T HAPPEN
  _____________________________

So, the "Switcher" still wins 2/4 cases = 50% of the time.

This analysis still shows that neither strategy is superior. We'll have to look elsewhere to figure out where we are going wrong.

Proper Case Exhaustion Analysis

So, where else could the analysis go wrong? Its not our "without loss of generality" assumption (you can enumerate cases further, including the different possibilities for the winning door to see it)...

The tip off is that these sorts of puzzles tend to revolve around identifying and finding a way to exploit an asymmetry. The key is realizing that the analyses above make an implicit assumption that the cases as identified are equiprobable when they are not.

There is a clear asymmetry in that the "CAN'T HAPPEN" cases are not evenly distributed. There are five "CAN'T HAPPEN" cases out of nine total cases, and among the three clearly equiprobable pairs of the independant "Chooses" variable, two of them lead to certain loses for "Sticker".

Lets simplify our tables from above, since the naiive way of doing our exhaustion of cases has encouraged a flaw in our reasoning. We included non-essential information in both earlier analyses, obscuring the true situation. Here's the right way to look at the problem...

First, the "Sticker" (non switcher):

  Choose  Switch  Win
  ___________________
    A       N      Y
    B       N      N
    C       N      N
  ___________________

So, the "Sticker" is now seen to actually win 1/3 cases = 33% of the time.

That is, if the "Sticker" starts out choosing the right door, he'll win, otherwise he'll lose.

Now, the "Switcher":

  Choose  Switch  Win  Comment
  ________________________________________________________________________
    A       Y      N   B or C can be opened, the other can be switched to.
    B       Y      Y   Only C can be opened, only A can be switched to.
    C       Y      Y   Only B can be opened, only A can be switched to.
  ________________________________________________________________________

So, the "Switcher" is now seen to actually win 2/3 cases = 67% of the time.

That is, if the "Switcher" starts out choosing the right door, he'll lose, but otherwise (most of the time) he'll win. The key is that whenever the initial choice is wrong (most of the time), the remaining door after one is opened is the winning door because two of the three doors can't be opened (the chosen door and the winning door).

No comments: