Wednesday, April 05, 2006

Beating Monty Hall

Prof. of mathematics Jason Rosenhouse recently put my brain through an ordeal with the Monty Hall problem:
You are presented with three identical doors. Behind one of them is a car and behind the other two are goats. You want the car. Monty Hall tells you to choose one of the doors. Regardless of which door you choose, at least one of the two remaining doors will have a goat behind it. Monty Hall, who knows where the car is, then opens one of the doors that has a goat behind it. He then gives you the option of either sticking with the first door you chose, or switching your choice to the other unopened door.

Question: What should you do? Should you stay where you are? Swtich? Does it make a difference?
Because we're left with only two doors to choose from the odds are 50-50 that the car is behind the door we originally picked. Hence, switching is irrelevant, right? Well, that's what I thought.

After making sure I was well aware that my line of reasoning was completely off the mark, Rosenhouse explained in various ways how to understand the correct probabilities of switching and not switching. But guess what? None of them got through to me. I think my brain must be due for a 100,000-kilometer overhaul or something. So I googled and visited Alexander Bogomolny's Cut the Knot site where there were even more explanations. Amongst them the one that finally switched on the bulb was the explanation by Michael Gerard Wilson:
Let's say that you choose your door (out of 3, of course). Then, without showing what's behind any of the doors, Monty says you can stick with your first choice or you can have both of the two other doors. I think most everyone would then take the two doors collectively.
And it made even more sense when I coupled that with Ashutosh Joshi's take on the problem:
The main thing that confuses in the problem is that there are only 3 doors. Lets generalize the problem as follows:

There are n number of doors. One of them has a prize behind it and n-1 are empty. After I select one door the host opens n-2 empty doors and gives me the option to switch doors. Should I switch?

When n is 3 as in the original problem, things get confusing but now let n be a large number say 1000. So there are 999 empty doors.I select one of them and the host shows me 998 empty doors. Now it is clear that it is definitely advantageous for me to switch. There was only a 0.001 chance of me picking the correct door immediately so obviously one can't say that it is now a 50-50 chance. It is still 0.001 that I had picked the right door initially. So the chance of me winning if I now switch is 0.999 or (n-1)/n. Since this is the solution for the general problem of n doors, the answer for n=3 is (3-1)/2 or there is a 2/3 chance of winning if I switch my choice of doors.

Now that I think I get it let me make a stab at explaining it the way it makes sense to me.

Instead of just three doors let's say I'm presented with 100. I'm asked to choose one. The probability that the door I choose actually is the correct one is of course 1/100 or 1%. Monty then gives me a choice whether to stick with my choice or to trade it for the 99 other doors. In other words I being given the chance to bet that the car is behind the 99 other doors instead of the one I initially picked. Furthermore, I am not being asked to pick one among those 99, I'm just being asked to choose between two groups: 1 door or the 99 other doors. Given that the probability of finding the car in the latter group is 99% I'd be crazy not to avail of the option. Continuing with the game, whichever group I choose Monty proceeds to open 98 doors of the latter group.

Choosing the latter group--the 99 other doors--is equivalent to switching to the one door that Monty doesn't open among the 99. In the case of 100 doors, switching when we're down to just two doors gives us a 99% chance of winning the car! Incredible, isn't it?

The same reasoning applies given any number of doors. Likewise, the above explanation also in part addresses (at least I think it does) Rosenhouse's Variation 2 of the problem:
This time there are five doors, concealing one car and four goats. You choose one of the doors. Monty Hall, who knows where the car is, opens one of the remaining goat-bearing doors. He then gives you the option of switching. You make your choice, after which Monty Hall again opens a goat-bearing door. Again you have the option of switching. This process continues until there are only two doors remaining. What is your best strategy?
The best strategy he says is to defer until there are only two doors left and then switch. Alex Bogomolny has probability figures for a 4-door version of this multi-stage Monty Hall problem. I think the general rule is the same as for the single stage version: The probability of getting it right if we switch only at the last moment--when there are only two doors left--is (n-1)/n.

1 comment:

KipEsquire said...

Ashutosh Joshi's "extension" is merely a mundane example of failing to incorporate Bayesian posteriors.

I think what probably confuses people here is the false assumption that Monty Hall is somehow a random actor in the spirit of a roulette wheel. He is not.

Regardless of whether there are three doors, 1000, or n, and regardless of which door you initially choose, he will consciously collapse the game in such a way as to present you with a 50-50 chance at the end. QED.