Saturday, March 3, 2007

Debugging Probablity: Car, Goats and Monty Hall

The Monty Hall puzzle is a famous probabity puzzle. In one of its various forms, there is a room with 3 closets. One of them has a car behind it, the other two has a goat each. When you enter the room, the doors were closed so you do not know which closet has what. The challenger asks you to guess which closet contains the car. If you guess correctly, you get the car. If incorrect bad things will happen, no guarantees here. So you think a lot, probably make phone calls to friends and make a guess, say X. Then you proceed to open the door to see what is in your fate. But the challenger stops you and opens one of the other closets Y that has a goat. Then he even gives you a chance to make a new guess Z. You have two options, stick with previous guess (X=Z), switch to the other unopened closet (X!=Z). What to do ?

The correct behaviour (by probability) is to change the guess to the closet that is still unopened, X!=Z. That will double your chance of winning. There are several ways to reason about this. But I am more interested in debugging other claims, mostly faulty. So, lets look at the different explanations.

We can make one assumption. To stop the challenger from getting the better of you, you should choose X uniformly at random from all three closets. So, P[X=car]=1/3 and P[X=goat]=2/3.

1. Repeat the experiment a million times. You would get the the car only one third of the time by sticking to your first door. People who always switch would therefore win the other two thirds. Therefore you should switch.
The only cases when you win by switching is when X=goat. So, P[winning | switching]=2/3 (probability taken over X).

2. Consider all possible cases:
  • X=goat1, Z=X (loose)
  • X=goat1, Z!=X (win)
  • X=goat2, Z=X (loose)
  • X=goat2, Z!=X (win)
  • X=car, Z=X (win)
  • X=car, Z!=X (loose)
3 cases you win by switching, 3 you dont. So, does not matter if you switch or not.
Actually, the complete table says that, if you randomly decide to switch or not switch, then you have a 50-50 chance of winning. Further, it even says that P[win | switch]=P[win | Z!=X]=2/3.

3. One argument is that revealing Y does not matter. The probability of finding the car in the remaining two doors was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having the car under it.
The explanation is a bit ambigous. Lets look at various cases and explanations. These are all different experiments.
[C1] At the beginning itself, the challenger opens one of the goat containing closets. P[car in one of the other two]=1/2 in this case.
[C2] The challenger opens a goat closet. The he randomly reshuffles the contents of the other two closets. Here,
P[X=car | switch]=P[X=car | not switch]=1/2
[C3] The challenger opens one door while your eyes are closed, showing a goat to the audience.
P[X=car] = 1/3
P[X=car | revealing] = 1/3
this is the same experiment. Just because he opened a door does not change your sample space.
[C4] The challenger reveals a goat closet to you.
But, P[X=car | revealing] != 1/2 because the challenger did not reshuffle the contents. In fact, knowing a closet contains a goat makes the probability of winning by switching 2/3. This is different from C1. The challenger has been forced to reveal some information not known before. If X=goat, Monty had to open the non-car closet. If X=car, he will not reveal any information. 2/3 of the cases X=goat, in which case he would leave the car closet closed. 1/3 of the cases X=car and he could choose any goat-door without saying anything. So, if you switch, you have a winning chance of 2/3. Note that, the analysis depends on your initial uniformity of choosing a closet but independent of challengers choice of Y.

4. The analysis sounds easier if you consider a related problem. Say there are 1000 closets, one car and 999 goats. Do the same experiment but here the challenger reveals 98 of the goat closets.
Initially P[X=car]=1/1000. When the challenger opens all but 2 doors, P[X=car] cannot possibly remain the same. In fact, by the argument in C4 above, 999/1000 times X=goat, so the challenger would be forced to leave the car closet open. Then, P[win | switch]=999/1000.

5. Another way of looking at it is, P[X=car]=1/3 which means that if you consider all possible items in the closet, in 1/3 of the cases it would be a car i.e. P[one of the other two has car]=2/3 Revealing a goat does not change this probability (it does change some conditional probabilities). So, even after revealing, P[one of the other two has car]=2/3. But now you know that one of the other two definitely has a goat. So, P[one of the other two that is unopened has a car]=2/3.

6. Consider a slight variant of the puzzle. There are 4 doors with 1 car and 3 goats. After you choose X, the challenger opens one door with goat. Now, with probability 3/4, you chose a goat closet. In which case, the challenger leaves a car closet and a goat closet open. Let us say you always switch to any of the them with probability 1/2. Then your probability of winning in this case is 3/8. With probability 1/4, you choose a car, in which case you always loose when you switch. So, switching gives you 3/8 probability of winning. On the other hand, if you do not switch, then you only win when you chose the car closet, which happens with probability 1/4=2/8. So, switching is better, but not by that much.

No comments:

Post a Comment