Saturday, December 20, 2008

The Monty Hall Problem

The Monty Hall Problem is a probability puzzle based on a game that contestants played on the popular old TV game show Let's Make a Deal, hosted by Monty Hall. On the show, contestants were given a choice of three doors. Behind one door is a car, behind each of the other two, goats. The contestant got to choose a door, and won whatever was revealed to be behind that door. The twist was that after the contestant had selected a door, Monty would show them what was behind one of the two doors not selected, and give them the option of changing their mind.*

The game was deceptively simple, in that it seemed as though the contestant always had one chance in three of winning the car, whether they switched their choice or not. There was a strategy that would double the odds of winning though. It turns out that the winning strategy is as simple as the game.

All a contestant had to do to double their odds of winning was always switch their guess after Monty opened one of the doors. This simple strategy worked because the contestant had only one chance in three of guessing the right door initially. Once they had made their guess, Monty would open one of the other doors that did not conceal the car. Since the player's initial guess was wrong 2/3 of the time, Monty was opening the only other losing door 2/3 of the time (the car was behind one door, so he wouldn't open that).

This strategy isn't intuitive to a lot of people. In fact, when the strategy was first published in Parade magazine, thousands of people wrote in to claim the solution was wrong. It becomes more clear if you look at a bigger variation of the same problem.

Imagine you're on a game show where there are 100 doors. Behind one of them is a new car, while the other 99 conceal goats. Your odds of selecting the right door are 1 in 100. Now imagine that after you've made your selection, the host of the show opens 98 of the doors, revealing 98 of the goats. (Keep in mind that he doesn't randomly open doors. He knows where all the goats are.) Would you switch your original guess to the one remaining door? You only had a 1% chance of winning with your original guess, so does it seem advantageous to switch after the choices are narrowed down to only two?

With a bigger set of doors to choose from, it becomes much easier to see that you have a distinct advantage when you switch from your initial guess. The same holds true for the original problem. By always switching after one door was opened in the original game, the odds of winning were improved from 1/3 to 2/3. That's certainly not a sure thing, but it's not bad odds on a brand new car.

Additional Note: If you want to try out an online interactive version of the original game, you can play it here. Make sure you give yourself enough trials to confirm that the optimal strategy wins 2/3 of the time.

* It turns out, Monty Hall never offered to let contestants switch which door (or curtain) they picked on Let's Make a Deal. Instead, he would offer them cash to opt out of the game entirely. The problem that would be known as the Monty Hall Problem was originally published as the Game Show Problem by columnist Marilyn vos Savant in 1990.

Greg said...

Two questions:
1) Since the sample set has been changed, don't the odds on whether or not you've made the right choice the first time change? Thus, there would be no point to changing your choice, since the odds are 1 in 2 either way.
2) To go from the theoretical to the practical, has this solution been proven in practice to work? That's the kicker for me. If you can show me, over a large enough sampling, that it works, then I'll assume my intuition is completely wrong, and agree!

Bill the Lizard said...

Greg,
Good questions.

1) No, the odds of you making the right choice in the first place don't change. You always have three doors to choose from initially. Removing one door in the middle of the game changes the odds of the remaining door being the winner.

2) It would be easy enough to write a simulator that played the game thousands of times and reported the results. If instead you'd like to try it out a few times, you can play the game here As a matter of fact, I like that idea so much I'm going to add it to the main article.

Thanks,
-Bill

Greg said...

Just a comment on your post-script: the odds shouldn't change to 2/3s. They should increase from 1/3 to 1/2.

I'll play it to see what happens. Thanks for the link.

Greg said...

Let me see if I can frame this differently, and perhaps muddy my thinking even further!

One common probability problem is the coin-flip problem. If you have an evenly weighted coin, and you flip it, the odds of heads or tails are 50/50 each. If you ask someone ahead of time what the odds of flipping heads the first time, it is obviously .5. What, then are the odds of flipping heads 10 times in a row? 2^10.

However, if you proceed to flip 9 consecutive heads, and ask what the odds are of flipping heads again, the common mistake is too assume it is 2^10. That's wrong, because the odds of flipping heads on that flip are independent of the previous flips. Therefore, the odds are .5 that the next flip will be heads.

In the same way, I would argue that the odds of the door you chose, when 3 were available, being correct are, indeed, 1/3. When you chose. But as soon as you remove the bad door from the equation, what happened previously now no longer matters. The odds are now .5 of the door you have selected being the correct one.

I'm arguing this from a completely intuitive perspective, and make no claims to it being correct. Probability has always fascinated me, but I make no claims to expertise. I'd be glad to see why my reasoning is wrong. Now I'm off to play some games to see what reality holds for me! ;-)

Greg said...

Heh. It's a small sample set, but I played 25 times, and won 14 cars after switching. That's pretty amusing. I'm sure it will even out over a larger set, but it is pretty funny.

I think I'll throw together a simulator. Shouldn't be difficult. Clearly, intuition doesn't always offer the right answer, though.

Bill the Lizard said...

Greg,
It does seem intuitive that the odds of winning after one door is opened would increase only to 1/2. This is the trap, though! The odds would only be 1/2 if the two remaining doors had an equal likelihood of concealing the car. Remember, they don't.

At the beginning of the game you had 1 chance in 3 of choosing the right door, which means you had a 2/3 probability of choosing wrong. If you play the game many times, your first guess will be wrong 2/3 of the time. Opening one of the doors doesn't change the odds on your initial pick. It still has only a 1/3 chance of being the winner. With one door open, however, the remaining door now has a 2/3 chance of being the winner.

Tim Kington said...

I love it. To all the doubters - you have to try it out. If you don't trust the website, use dice :) You have to use them to randomly place the car, and to determine your initial choice.

Here's a variation that I really like. One day on the show, Monty forgets to find out where the car in advance. In the spirit of "the show must go on", he opens one of the doors and luckily, reveals a goat. Nobody else knows that he had any doubts. What are the odds now for staying vs switching?

Bill the Lizard said...

Tim,
That's an interesting variation that I hadn't heard before. I wonder if it really happened on the show?

I think I know the answer, but right now it's more intuition than anything else. I don't want to post a solution until I've proven to myself that it's right. I also don't want to spoil it for anyone else who might be trying to solve it.

Bill the Lizard said...

My initial guess to the variation posted by Tim Kington (who is a former instructor and good friend of mine, thanks for reading, Tim) was wrong. I originally thought that it didn't matter that Monty was guessing, and that the odds on switching were still 2/3 in favor of winning.

Don't read any further if you don't want to read a spoiler.

I had forgotten that in probability you should always use every piece of information you have available (if it has a possibility of changing the outcome). After a bit of analysis I came up with the correct answer. The odds of winning if you switch in the variation are 1/2.

Here's the breakdown:

-You pick a goat on your initial guess, then Monty reveals a goat and you win by switching to the car.

-You pick the car on your initial guess, then Monty reveals a goat and you lose by switching to the other goat.

These are the only two options. A third option, that you initially pick a goat and Monty reveals the car is eliminated in the premise, so you know from the setup of the problem that this option didn't happen.

Tricky. :)