The Multi-Stage Monty Hall Problem
Some time back, Sids had a post on the Monty Hall problem/game, which is as follows (Source: Wikipedia).
Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?
In this case, there are three doors. So, the game is played in two stages — Stage 1: Choose a door; Stage 2: Switch or stick with your choice. Here, the probability that you win the car is 2/3 if you switch your choice. So, yes. It is to your advantage to switch. See this page for details.
Let us now generalize this game to N doors. That means, the game is played in (N - 1) stages.
Stage 1: Choose a door
For stages X = 2 through (N – 1):
Monty Hall shows you one of the “goat doors”. Then, you either switch to one of the remaining (N - X) doors or stick with your choice
Questions:
- What strategy has the highest probability of winning in this scenario?
- Why is this the best strategy?
- What is the probability of winning with this strategy?
For simplicity, let us consider N = 4. You get to choose a door at the first stage, and for the next two stages, you can either switch or stick. So the various permutations are:
- Choose, Stick, Stick
- Choose, Stick, Switch
- Choose, Switch, Stick
- Choose, Switch, Switch
Which of these four strategies wins most probably? And why? Once this is figured out, try looking at the generalized problem with N doors.
PS: If you already know the answer (or have found a link to it), kindly procrastinate on writing a comment about it. 
Interesting variation of the problem.
I think the strategy of switching at every possible point would win with the greatest probability. But I’m in no mood to write down the explanation of how I arrived at this answer.
(I actually did start writing the answer but when I read it back, it just did not make much sense. I guess it is just too late to be writing on probabilities, let alone working them out!)
sids
May 20, 2008 at 2:04 am
@Sids
Umm.. No. The strategy of switching at every stage intuitively seems to be the most profitable of all. However, the best strategy is to stick to your choice till the end and switch only at the last stage. Strange, but true!
I’ve just worked out the proof for this. Will put it up as another post.
Briefly, the results I got for the generalized N-door problem (N > 3) are as follows:
1. Stick with your initial choice till the very end without switching: Probability of winning is 1/N. This is trivially true.
2. Stick with your initial choice till the end and switch only at the last stage: Probability of winning is (N – 1) / N
3. Switch your choice at the very beginning and stick with this new door till the very end without switching again: Probability of winning is (N – 1) / (N (N – 2))
4. Switch at every possible stage: Probability of winning is (2N – 3) / (N (N – 2))
Of course, there could be many other scenarios as well. But intuitively, we can say that strategy 2 is the best of all.
Ha ha! It would have been highly risky for Monty Hall to play the N-door game for some large N. The minimum number of doors required to play this game is 3. And they rightly stuck to this minimum number in “Deal or No Deal”. By doing so, they minimized their risks as much as it was physically possible. As N increases, the probability of winning with strategy 2 also increases! Imagine what would happen if it was a 4-door or 5-door game and the participants figured out all the probability gymnastics involved in it.
As far as the 4-door problem is concerned, the answer obviously is that “choose stick switch” is the best strategy. The probability of winning for each of the four strategies mentioned in the post are as follows:
Choose, Stick, Stick — 0.25
Choose, Stick, Switch — 0.75
Choose, Switch, Stick — 0.375
Choose, Switch, Switch — 0.625
Mandar
May 20, 2008 at 1:56 pm
A comprehensive treatment of the N-door problem is said to have been given in the following paper:
V. V. Bapeswara Rao and M. Bhaskara Rao, A Three-Door Game Show and Some of its Variants, The Mathematical Scientist, 17(2):89–94, 1992.
But I could not find the paper online.
Mandar
May 20, 2008 at 2:23 pm
Actually, I had come to the conclusion of chose, stick, switch based on intuition. Of course, I had not worked it out and no solid basis. What I had thought was that, one should switch only after one gets all the information that can be got. In the case of 3 doors, there is only one more door left. This is the state with the least uncertainly (entropy, one could say) as far as this problem is concerned. What I thought was, when there are N doors, opening a door is adding new knowledge to the player. But (s)he does not know whether to stick or switch. So, the player waits till the problem reduces to the 3 door problem for which (s)he knows what to do.
Just an early morning off hand comment. Not sure if it is valid.
sanket
May 20, 2008 at 5:01 pm
>> [W]hen there are N doors, opening a door is adding new knowledge to the player. But (s)he does not know whether to stick or switch. So, the player waits till the problem reduces to the 3 door problem for which (s)he knows what to do
Precisely. The player waits till the last stage and maximizes his/her own information content. The host will unveil all but 1 goat door, while the player simply waits. At the last stage, the player wins if he/she had chosen a goat door at the first stage [the probability of which is rather high -- (N - 1)/N].
Mandar
May 20, 2008 at 6:49 pm
>> Switch at every possible stage: Probability of winning is (2N – 3) / (N (N – 2))
Oops! This is not correct.
Work is in progress.
Mandar
May 20, 2008 at 9:43 pm
[...] for the n-Door Monty Hall Problem Posted in Mathematics by Mandar on May 21st, 2008 In an earlier post (see comments also), I had put forth a question about the winning strategy for the famous n-Door [...]
Analysis of Strategies for the n-Door Monty Hall Problem « Someone and Anyone
May 21, 2008 at 1:42 am