Having just spent three hours explaining the value of trigonometric substitutions and partial fraction expansions to not very enthusiastic calculus students, I'm not really in the mood for a lengthy post today. So how about yet another variation on the Monty Hall problem.
In this version the contestant is shown 10 identical doors. One contains a valuable prize, the other nine contain goats. The contestant chooses one door. The host then opens a door he knows to be empty and gives the contestant the choice of switching to one of the remaining eight unopened doors. After the contestant makes her decision, the host opens another door he knows to be empty. Again the contestant is given the option of switching. This continues until only two doors remain. The contestant makes her final decision, and the door she has now chosen is opened. The question is: What strategy should the contestant follow to maximize her chances of winning?
Be sure to justify your answer. Enjoy!
Comments
Empty or goats?
Posted by: bleat | February 6, 2007 8:20 PM
Until only 2 doors remain, you do not switch doors. Then you switch (and win!)
If I recall correctly from the original Monty Hall problem, the first door you pick would have a 1/n change of being the prize(in this case 1/10), therefore the last one remaining has a 9/10 chance of being the correct door. Even better odds than the original!
I think this makes sense, no?
Posted by: Ramekin | February 6, 2007 8:23 PM
Lets work this through folks, based on what we know.
Choose a door. Your door has a 1/10 chance of being correct. The chance of the prize being in the other group is 9/10. Monty takes one away. The chance is now 8/9. Each door has a 1/9 chance of being correct. Your door is still has a 1/10 chance. So, since any other door besides yours has a better chance, you switch.
Now you have a door that has a 1/9 chance. The other group has a 8/9 chance. Monty takes one away. Well, now that group has a 7/8 chance of having the prize and any one door has a 1/8 chance. Your door had a 1/9 chance. Switch again.
Keep switching all the way down. Good luck. You still might lose, but at least you maximized your odds.
Posted by: cephyn | February 6, 2007 10:36 PM
I think either of the two approaches listed above would work, though the former is less of a hassle. The key is switching at the end.
Posted by: Kevin W. Parker | February 6, 2007 11:13 PM
As I ponder it more and more, I think you have the key Kevin W. Parker. Doesn't matter what you do, just be sure to switch at the end....
...i think....
Posted by: cephyn | February 6, 2007 11:23 PM
I'm in agreement with Ramekin. Switching only at the end will either give better or equal odds as switching each time.
If cephyn is right about the odds changing each time you switch, then switching each time will increase the odds that it is behind your current door. Conversely, it reduces the chances the prize is not behind your door, which leaves you back at the original Monty Hall problem.
If the odds for each door remain constant, then there should be no difference between any strategy that has you switch at the end.
Switching only at the end should give you 90% successes.
Depending on whether odds change, constant switching can give you from 67% to 90%.
The answer is to switch only at the end. It is safer and less confusing.
Posted by: Jokermage | February 7, 2007 1:29 AM
If monty is smart, and you start switching, he'll never eliminate the first door you choose. even if it's empty. That way when it gets to the final two, you sit there thinking - should i go back to my original choice? or stick with this final new door?
Posted by: cephyn | February 7, 2007 1:44 AM
Stick with your door until you have two left and then switch. 0.9 probability that you were wrong on your original choice so switching at the end gives you the best odds.
Posted by: Nihar Pasala | February 7, 2007 4:19 AM
Wait after reading cephyn's solution, I think switching every time is optimal but with one caveat. You switch to a door you have never chosen before and if that is not possible then you dont switch. Dont ask me why.
Posted by: Nihar Pasala | February 7, 2007 4:29 AM
This one is complicated from straight probability by the fact that Monty *knows* where the prize is. But I can't justify my answer that you might as well stick with your original door down to the end, since as the problem is set up, Monty can't open it. You'll always be down to your door and one other by the end - switching around will only show you if your original door was *not* the prize if Monty opens it, but it doesn't seem like that would influence the last choice, which will always be between two doors you know nothing about and Monty knows all about, regardless of whether you switched before or not. But something tells me that those who say switch now are right ...
Posted by: The Ridger | February 7, 2007 6:54 AM
Stick with the original choice until it's down to the last two doors, and then switch. This would give a 90% chance of winning.
There is 1 chance in 10 that the prize is behind the door the contestant first chose (door A), and 9 chances in 10 that it is behind one of the other 9 doors. The probability of the prize being behind door A remains 1 in 10, but as each of the other doors is revealed to be wrong, the original 9 in 10 chance is redistributed among the remaining non-A doors. Once there is only one of these non-A doors left, the probability that the prize is behind THAT door is 9 in 10.
(It feels wierd posting before reading the other comments, but there wouldn't be much point otherwise)
Posted by: Ruth | February 7, 2007 8:09 AM
nihar and ruth are right about the probabilities. p=.1 that you are right the first time and .9 that you are wrong. that means that 9/10 of the time, the prize will be "somewhere else". if you wait until there's only one other door available, that "somewhere else" has to be that door.
and i suspect that this is optimal. but i can't prove it.
Posted by: Polymath | February 7, 2007 8:28 AM
According to Wikipedia, the optimal strategy is to stick with your original door until there are only two doors remaining, and then switch. Polymath and others are right that under that scenario you will win 9/10 of the time (or (n-1)/n in the general case). Wikipedia also asserts that this is the optimal strategy.
They do not provide a proof to show that this is the optimal strategy. Instead they merely refer to a paper, “A Three-Door Game and Some of Its Variants,” by Bapeswara and Rao. Well, I've read that paper. The authors prove that in the four door case the strategy of only switching at the very end is optimal. They do this by listing every possible scenario. They then merely assert that their result holds true for the n-door case.
Analyzing the probabilities for switching multiple times gets a bit trickier than some comments have suggested. Let's change the rules just slightly. Let's say you pick door one. Monty then opens the empty door two. He gives you the option of switching, after which the game will end. What should you do?
Your door is correct 1/10 of the time. That means that 9/10 of the time the prize is behind one of the doors numbered two through ten.
So in 9/10 of the times the game is played the prize is behind one of the eight, equally likely remaining doors. (That is, doors 3-10). If you switch you will choose correctly from among these doors 1/8 of the time. So the probability that you will win by switching is 9/10 times 1/8 which is 9/80. This is slightly better than 1/9.
After Monty opens door two, the updated probabilities for where the prize is are as follows: Door #1 - 1/10. Door #2 - 0. Door #3-#10 - 9/80. Yes, that does all add up to one.
But if you keep going things get more complicated still. By switching doors you give Monty the option of opening the door you chose initially. So if Monty opens that door he is eliminating an option that was correct only 1/10 of the time. If he opens one of the remaining doors he is eliminating an option that was correct 9/80 of the time. So it seems like you would want to force Monty to open one of the doors from 3 to 10.
Perhaps the way to express this is in information theoretic terms. Your optimal strategy will be the one that forces Monty to give you the maximum amount of information at each step. The previous argument seems to suggest that the maximum amount of information is extracted when you stick with your initial choice until the bitter end. But I don't have a simple slam-dunk proof of that fact.
So what I would like is a good argument to show that (1) You can't improve on the strategy of sitcking with your initial door until the end and (2) No other strategy does equally well. The simpler the argument the better!
Posted by: Jason Rosenhouse | February 7, 2007 3:21 PM
Let's say you've played this game following some strategy to the point where there are three doors remaining (1, 2, 3), and you know the probability that each door holds the prize (p1, p2, p3). It's clear that you want to pick the door with the lowest probability (let's say 1), as then Monty Hall will have to open one of the others (2), making the probability that the prize behind door 3 p2+p3, giving the highest possible probability difference between the remaining doors.
The general strategy should be to preserve the door with the lowest probability. If you don't pick the lowest door, one of two things may happen: it gets eliminated, or its probability is increased relative to the door you picked.
With four or more doors there is an added difficulty: Monty Hall has a choice of which door to open. The question then becomes can he avoid inadvertantly signalling the contents of the doors while he's choosing.
Posted by: Lars | February 7, 2007 4:28 PM
I worked through the four-door case and found that if you switch after the first door is opened, if Monty is playing to win he can hold you to 5/8 chance (as opposed to the 3/4 with the hold strategy). If he's feeling nice, and you know he's helping you to win, he can bring you back up to 3/4.
If Monty Hall selects a door at random (from the set of available doors that contain goats)the probabilities are updated in a predictable fashion: if he opens door 1, and you claim door 2, then the probability that door n contains the prize is pn*(1-p2)/(1-p2-p1). This, coupled with the realization that your goal is to retain one door with the lowest possible probability, should be enough to determine your strategy.
This seems close to a proof...
Posted by: Lars | February 7, 2007 4:48 PM
I'm a bit confused. In the original post, it's suggested that at each turn, the contestant can either stick of switch: the game is only over when all but one door has been opened. However, in Jason's comment, he suggests that it's game open as soon as the contestant switches for the first time. I'm not sure if this changes the optimal strategy though...
Posted by: Doormat | February 7, 2007 7:27 PM
Whenever a door is eliminated, the probabilityof that door being correct changes to zero. Since the total probability of must add up to one, the prior probability of the eliminated door must be redistributed among the remaining doors. The currently selected door and any eliminated doors cannot change their current probabilties, so the redistribution must take place among the surviving doors that were not chosen for the current round. The redistribution depends upon the strategy Monty Hall uses in eliminating the various doors, but no matter what strategy he uses (because there is always a chance that any given door can't or must be chosen, thereby defeating his strategy), every surviving door (that is not the currently chosen door) gains a positive, non-zero probability. Therefore, if you switch before there are only two doors remaining, the probability of your original choice either increases the round you switch, or it gets eliminated. In either case, the smallest probability has now increased (because the new door has a higher prbability of being correct than the initial distribution and the original door either has a higher probability or has been eliminated).
Thus, the best strategy is to stick with the original choice to prevent its probability from increasing.
BTW, if the doors are eliminated randomly, the prior probability of the eliminated door is evenly distributed between the remaining non-chosen doors, regardless of whether they were chosen in previous rounds. The redistribution is added to the prior probability of the individual doors.
Posted by: W. Kevin Vicklund | February 8, 2007 9:21 AM
For the case of n doors: Consider the following:
The door chosen first has a winning probability of: P(X=1)=1/n
All the other doors have winning probabilities of P(n>=X>=2)=(n-1)/n added together
After opening one door every other door except for the one chosen first has a probability of P(X=3,4,5...,n)=(n-1)/(n*(n-2))
Now if you change your choice, the remaining group of doors has a probability of P(X=1,4,5,...,n)=((n-1)*(n-2))/(n*(n-2)) - (n-1)/(n*(n-2)) + 1/n = (n^2-3n+1)/(n*(n-2))
If you stick with your choice, the remaining group of doors has a probability of P(X=3,4,...,n)=((n-1)*(n-2))/(n*(n-2))=(n^2-3n+2)/(n*(n-2))
So the question is:
Does n^2-3n+2 >= n^2-3n+1 always hold true? Yes, it does.
Posted by: Peter | February 8, 2007 4:29 PM
Doormat-
In my previous comment I explicitly changed the rules of the game to only allow one switch. I did that just to illustrate what is involved in calculating the probabilities of winning by switching vs. sticking. Things get far more complicated when you try to work out the conditional probabilities for multiple switches.
W. Kevin Vicklund-
That's a very interesting argument! I'll have to give it some thought, but it sounds pretty good.
Posted by: Jason Rosenhouse | February 8, 2007 5:31 PM
For a full discussion of this variation see
http://en.wikipedia.org/wiki/Monty_Hall_problem
Pascal Bercker
Posted by: pascal bercker | February 10, 2007 11:35 AM
Probability of it being in the final box is 1-p where p is probability when of getting it right when you last picked.
You minimize p on your first selection so you maximize 1-p on first selection.
Q.E.D.
Posted by: jg fellow | February 11, 2007 11:15 AM
Quite right jg fellow;
An easy way to visualise this type of problem:
Imagine you have a ten litre aquarium with one goldfish. You randomly scoop out one litre of water which may (or may not) contain the goldfish. Now, you drain the tank, one litre at a time. Obviously, the position of the goldfish (scoop vs aquarium) cannot change, so, neither can the probabilities.
That's the first choice best choice scenario.
Now suppose that, having drained five litres out of the tank, you pour your litre back in and scoop out another. You have simply restarted the problem using five litres instead of ten and halved your odds.
Now, for the information provided by Monty's choices, assuming you pick a different door at every opportunity.
After your eighth pick:
1. You have an 80% chance of having selected the prize door at some point;
2. The values for the remaining boxes are;
A. CS (current selection), and
B. either Sx (previous selection), or
U (unselected).
If the final configuration is CS/U there is an 4/5s chance that CS contains the prize. If the final configuration is CS/Sx, then there is a 2/3s chance Sx is the prize door. In all cases this is less than the 9/10s chance afforded by first choice.
Posted by: DTIS | February 11, 2007 1:41 PM
If you pick one door (any door) and stick with it until the final choice and then switch to the remaining door, your chances of getting the prize is 0.9. If you switch at each choice, your chances of getting the prize is 0.5. This is actually very easy to see if the puzzle is looked at in the right way. First, consider a different contest - we'll call the stated problem contest A and this slightly different problem contest B. In contest B you first are allowed to decide if you want to open one of the ten doors and you get the prize if it's behind that door, giving you a probability of winning of 0.1; or you can decide that you want to open 9 of the 10 doors, giving you a win probability of 0.9. You, of course, pick the second option with the much higher probability of winning. (Notice that Monte has no involvement in this contest B - you first decide whether you want to open one or nine doors, and then you pick the one or the nine doors you wish to open.)
Now apply this to the stated problem: contest A. Decide which 9 doors you wish to open - doors one through nine for example - and when Monte asks you to pick a door, you actually pick the door you don't want to open - door 10 - and stick with it until the final choice. So for the first eight trials, Monte opens eight doors that you wanted to be opened for you. In the ninth trial, you switch and pick the ninth of the nine doors that you wanted to be opened. Its really irrelevant that Monte opened eight of the doors for you as long as they got opened. So this is really the same as contest B with you choosing to open nine doors.
Compare this to what happens if you switch each time. For the first eight trials, it makes no difference what you do, which of the doors you pick as long as you keep changing. What is happening is that Monte is opening eight doors that are empty (or goats) and eliminating them from the game until you are down to two doors. All the probability analysis up to the point is totally irrelevant, since Monte is simply opening doors that he knows are empty and eliminating them from consideration. In the ninth (final) trial you are left with two doors - one with the prize and one empty, giving you a 0.5 probability of getting the prize. The key point is that for any trial in which you switch, all the previous trials only served to reduce the number of doors to be considered and the game in effect is restarting with fewer doors.
Suppose in your nine trials you switch in the first four, stick in the second four and then switch in the final one. The above logic applies: in the first four trials you are just reducing the game from one involving 10 doors to one involving six doors; in the final five trials you are effectively choosing which five of the six doors you want opened giving you a 5/6ths probability (=0.8333) of winning. I'll leave it to others to sort out the win chances for other patterns of sticks and switches.
The reason this problem seems so much more difficult than it really is is because it uses the magicians favorite trick of distraction. Monte's actions are really not relevant since he is not a free agent: He must always pick from a pool of empty doors, and since those doors are equivalent in effect, it is really not a choice. You have total control of the game (within the rules). I hope my explanation makes the answer as transparent as it really is.
Posted by: AnInGe | August 2, 2007 3:35 AM