Monday, October 26, 2009

Monty Hall and John Von Neumann walk into a bar ...

I recently read The Monty Hall Problem: The Remarkable Story of Math's Most Contentious Brain Teaser .
Here's my version of the Monty Hall Problem.
The Basic Situation is as follows. There are two individuals: Monty Hall and Alice. There is a car; there are three closed curtains; and the car is behind one of the curtains, which hides it completely. There is nothing behind the other two curtains. The action proceeds as follows:
1. Monty hides the car behind one of the curtains (H); Alice has no idea which one.
2. Alice chooses a curtain (C), but it is left closed. Alice doesn't know yet whether she chose the car or not.
3. Monty opens one of the curtains (S) showing Alice what's behind it.
3a. Monty is not permitted to open curtain Alice's curtain C; S cannot equal C.
4. Alice finally chooses another curtain (F) which can be different than C or the same. Alice gets what's behind the curtain she finally chose. If F=H, Alice wins the car, otherwise Alice gets nothing.

We can nail this down so that it is an exercise in pure logic and probability for Alice by further specifying what Monty does at steps 1 and 3. Here are the Additional Stipulations.
1a. Monty chooses where to hide the car (H) by randomly picking one of the three curtains: each of the three curtains is equally likely.
3b. Monty will only show Alice an empty curtain in step 3. Monty never opens the curtain with the car. S cannot equal H.

Given these Additional Stipulations. the consequences of the Alice's choice in step 4 are completely unambiguous - however the results surprise many people. Alice's two main strategies are Stay (F=C) and Switch (F≠C≠S) Many people guess that Stay and Switch are equivalent and that Alice wins 1/2 the time either way. Surprisingly Stay only wins 1/3 of the time while Switch wins 2/3's of the time.

Suppose Alice elects to follow the following strategy: always choose curtain #1 in step 2 and always Stay with curtain #1 in step 4.
In step 1. Monty hides the car behind curtain #1 1/3 of the time.
In step 2. Alice always chooses curtain #1.
In step 3. Monty will open either curtain #2 or curtain #3. Note that this does not change the actual location of the car, it's still behind curtain #1.
In step 4. Alice will always choose curtain #1 again. Alice wins the car.

In step 1. Monty hides the car behind curtain #2 or curtain #3 2/3's of the time.
In step 2. Alice always chooses curtain #1, which is empty.
In step 3. Monty will open either curtain #2 or curtain #3. Note that this does not change the location of the car, curtain #1 is still empty.
In step 4. Alice will always choose curtain #1 again, which is empty. Alice gets nothing.

So we see that by following the strategy of always chosing curtain #1 both times, Alice only wins the car 1/3 of the time.

Suppose on the other hand Alice uses another strategy: in step 2. she always chooses curtain #1; in step 4. shes always Switches to the only other curtain which is still closed.

In step 1. Monty hides the car behind curtain #1 1/3 of the time.
In step 2. Alice always chooses curtain #1.
In step 3. Monty will always open curtain #2 or curtain #3. Note that this does not change the actual location of the car, it's still behind curtain #1.
In step 4. because Alice always switches she will choose either curtain #2 or curtain #3. But the car is still behind curtain #1 and Alice gets nothing.

In step 1. Monty hides the car behind curtain #2 1/3 of the time.
In step 2. Alice always chooses curtain #1, which is empty.
In step 3. Monty must open curtain #3 - because it is the only door which is empty and is not Alice's. That of course does not change the location of the car - which is still behind curtain #2.
In step 4. Alice always switches to curtain #2 - because it is still closed. Alice wins.

In step 1. Monty hides the car behind curtain #3 1/3 of the time.
In step 2. Alice always chooses curtain #1, which is empty.
In step 3. Monty must open curtain #2 - because it is the only door which is empty and is not Alice's. That of course does not change the location of the car - which is still behind curtain #3.
In step 4. Alice always switches to curtain #3 - because it is still closed. Alice wins.

So Alice always wins if Monty hid the car behind curtain #2 or curtain #3 and Alice always loses if Monty hid the car behind curtain #1. Perhaps suprisingly Alice wins 2/3's the time when she always switches.

There's another formulation of the problem which only uses the facts in the Basic Situation. The Additional Stipulations are not included. Surprisingly Alice can guarentee the same favorable outcome in the Basic Situation that was achievable with the Additional Stipulations! Monty is permitted to choose where to hide the car (H) in step 1. any way he likes. In step 3. he is permitted to choose which curtain to open (S) by any method, as long as he doesn't open curtain C (still forbidden by 3a). It doesn't matter how Monty makes his choices (as long as he obeys 3a), Alice can still win the car surprisingly often.

Here's a paper (in pdf) which explains the Game Theory approach to the Monty Hall Problem: Probabilistic and Game Theoretic solutions to The Three Doors Problem