Friday, August 03, 2007

The M-Door Monty Hall Problem

The M-Door Monty Hall problem assumes that you are a contestant in a game show trying to win a new car. You start off with M doors, one of which has a car behind it and all of the others have goats. After you pick a door, host Monty Hall opens a door to show the goat behind it (other than the one you picked, of course). He then gives you the choice of keeping your picked door or switching your pick to one of the other doors. After you make your choice, Monty and you continue alternating between opening doors to reveal the goats behind them and choosing whether or not to switch which door has been picked until the game is down to only two doors. Monty then gives you one final chance to switch your picked door before revealing your prize.

The problem is to determine the optimal strategy of either switching doors or not switching doors in each round starting from the initial pick from one of the original M doors. Also note that Monty is not allowed to switch which door has the new car behind it.

The key here is to have a probability that the door one has picked has the car behind it is a far from 1/2 as possible going into the two-door round. The further this probability is from 1/2, the more confident one can be in either switching one's pick or keeping one's pick as appropriate to win the car.

My proof of optimal strategy is as follows. Suppose that you go into round N+1 (here N>=2) with a probability x of having picked a door with a goat behind it.

  • If you don't switch your door, Monty opens a door with a goat behind it and you go into round N with a probability x of having picked a door with a goat behind it.


  • If you switch your door, a fraction
    • (N-1)/N of people who picked doors with goats behind them switch to another door with a goat behind it;

    • 1/N of people who picked doors with goats behind them switch to the door with the car behind it;

    • all people who picked the door with the car behind it switch to a door with a goat behind it.

    If you switch doors, you go into round N with a probability x*((N-1)/N)+1-x = (N-x)/N of having picked a door with a goat behind it.

Now (N-x)/N can equal 1/2 if N=2 and x=1. That is, if you were absolutely guarenteed that you picked the goat going into the 3 door game, then switching doors would reduce your chance of winning the goat to 1/2. In this case, the optimal strategy is to not switch doors, let Monty open one of the two remaining doors with goats behind them, and then switch doors to win the car with absolute certainty. In any other case other than N=2 and x=1, since x is at most 1, it follows that (N-x)/N is larger than 1/2.

Under what conditions is (N-x)/N closer to 1/2 than x? Start with the inequality

x - 1/2 > ((N-x)/N) - 1/2

This inequality is satisifed if

x > N/(N+1)

In other words, if x > N/(N+1), then switching doors in the N+1 round and then never switching doors again until a final switch in the 2-door final round will lead to a reduced probability of winning the car.

Notice also that if one switches in the N+1 round, thus altering the probability that one has picked a door with a goat behind it from x to (N-x)/N, it is also the case that for 1 > x,

(N-x)/N > (N-1)/N > (N-2)/(N-1) > ... > 2/3

Of course, if x=1 going into the N+1 round, then the optimal strategy is to never switch doors until the 2-door final round, thus winning the car with absolute certainty. What this means is that, if you go into the N+1 round with a probability 1 > x > N/(N+1) of having picked a door with a goat behind it, then switch doors in the N+1 round, then no matter how many rounds you refuse to switch doors before the two door finale, the next switch of doors still further hurts your chance of winning the car. This same argument can be repeated as many times as necessary to show that, as long as one starts with 1 > x > N/(N+1) going into the N+1 round, every time you switch doors before the 2-door final round, no matter when, you hurt your chance of winning the car.

So the conclusion is that, if you go into the N+1 round with N>=2 with x > N/(N+1), every switch of the doors before the 2-door final round, no matter when, will always hurt your chance of winning the car. Notice that your probability of having picked a goat is always going to be at least 2/3, so you will always want to switch doors in the final 2-door round.

Now, one starts the game by picking from M doors with M>=3, then allowing Monty to open a door to reveal the goat behind it. The probability of picking a door with a goat out of a selection of M doors with M-1 doors having goats behind them is x = (M-1)/M. You're forced to allow Monty to open at at least one door before your first switch. So you go into the M-1 round with a probability x = (M-1)/M of having picked a door with a goat behind it. Since

(M-1)/M > (M-2)/(M-1)

it follows that switching doors in the M-1 round or any subsequent round hurts your chances of winning, no matter how many rounds you wait and refuse to switch doors. So the optimal strategy must be to never switch any doors until reaching the two round finale, and then and only then switching doors. This is consistent with all of the special cases above as well, so this is the optimal strategy.

2 Comments:

Anonymous Anonymous said...

You say:

If you don't switch your door, Monty opens a door with a goat behind it and you go into round N with a probability x of having picked a door with a goat behind it.

This is not true in general. It is only true if all the unselected doors have the same a priori probability, which in turn is true only if you never switch doors.

9:20 AM  
Blogger Uri Kalish said...

Got my own version:
http://urikalish.blogspot.com/2007/02/vertigo-and-lion-intuition-can-be.html

8:36 AM  

Post a Comment

Links to this post:

Create a Link

<< Home