The Progressive Monty Hall Problem

Empty or goats?

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?

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.

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.

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....

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.

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?

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.

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.

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 ...

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)

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.

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!

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.

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...

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...

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.

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.

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.

For a full discussion of this variation see

http://en.wikipedia.org/wiki/Monty_Hall_problem

Pascal Bercker

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.

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.

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.

The crucial information here is that Monty knows what is behind the doors and only opens empty doors.

The three extreme strategies are to:

1)stay with your first choice to the bitter end.
2)swap all the time.
3)stick with what you have and swap at your last opportunity.

In all these cases it comes down to at the end, just two doors.

I will analyse what information you gain from Monty with each of these three strategies.

STRATEGY 1) You stay with your choice to the bitter end.

Monty reveals a door with a goat. If you said to yourself that you are going to stick with the door you have chosen then you gain no extra information from Monty showing you the location of a door with a goat, as you already knew that a goat must be behind other doors you did not pick. You decided to stick with your original choice thereby depriving yourself of the freedom to make use of the knowledge of the location of the âdoor with a goatâ. So the location of the goat door is of no value to you. Hence your odds of winning the car remain the same â That is 1/10 or 10%.

STRATEGY 2.) You randomly pick a door every time you are given the opportunity.

However if you said to yourself before hand I will randomly select from the remaining boxes then you do make use of this information (of the location of the goat door Monty reveals).

The information you gain is that there is a goat behind that door. I do not know where the car is in the remaining doors so I will randomly pick from these. Using this strategy your chances of winning the car go from 1/10 to 1/9, to 1/8 â¦.. until the last two boxes remain when your chances reach ½ or 50%.

STRATEGY 3) You stick with your first choice and swap at your last opportunity.

Well if you said to yourself I know Monty knows what is behind these doors and I would like him to sort through door numbers 2 to 9 (say) and eliminate 8 of these doors of having the prize behind them, and then I would like to pick the remaining door that he does not reveal. That is, you would pick door 1 and swap to Montyâs remaining door at the last opportunity. Using this strategy you have maximise Montyâs knowledge of the location of the prize. By choosing one door and sticking with it, Monty is forced to sort the remaining 9 for you and the location of the remaining door that he does not reveal is of considerable information to you.

If the car is behind one of the remaining 9 doors from your original pick, you will win the car 100% of the time by switching to the door that Monty finally does not reveal.
Quite simply, the chances of the car being behind any group of 9 doors is 9/10. Montyâs elimination sort has forced the remaining door to these odds.

So using this strategy you have a 90% chance of winning the car.

PS

It is quite interesting to note that if Monty just happened to open doors with goats by chance (Monty was revealing doors you hadnât chosen and giving you successive choices to drum up the suspense). That is, he did not know what he was revealing or decided to open doors using some random procedure and only goats were revealed, then there is no way to gain information from Monty and your odds are 50/50 of wining the car in all the above scenarios.

Just by virtue that it was possible that Monty may have revealed the car during the session.

So in order to make use of these strategies you must be given all the information. That is; what Montyâs knowledge is and what he will do with this knowledge.

I donât think I made myself as clear as I could have in explaining what information is gained from Monty in Strategy 1 above.

If your rule is to stick with your original choice to the bitter end no matter what, then there is only two pieces of information that is of value to you (that will change your odds of winning).

1)Monty turns over all the remaining doors and each reveals a goat - in which case your have won the car. 100%
2)Monty turns over a car in one of the remaining boxes â in which case you do not win the car. 0%

As neither of these situations are part of the rules of the problem, Monty can do anything he likes with the remaining boxes (within the defined rules) and this will not effect the odds of you winning the car. Information of where the remaining goat doors are is useless to you with this strategy.

In the other strategies you make use of the information of the goat boxes Monty reveals. Strategy 3 you maximise this information by forcing the sort.

I retract my above comment and replace it with the following:

Yes as you may be aware I am having difficulty conceptualising the situation in Strategy 1 aboveâ¦..

Probably the easiest way to realise that your odds remain at 10% in strategy 1 is to consider the argument of strategy 3 and then take this probability away from one (1). There, easy, your chances of winning the car is 10% by sticking with what you choseâ¦.

Although it is always nice to see it from both perspectivesâ¦..

The key to realising the true odds in strategy 1 (remains at 10%) is to understand exactly how the problem you are given is defined.

The problem states that Monty knows what is behind all the doors, he opens all the doors bar one, and he only reveals doors that contain goats. This operation is done as a whole.

So I will rephrase the above for the problem. You are to pick a door. With the remaining doors - as a set - Monty will reveal either 8 goats of the 9 goats, or 8 goats of the 8 goats and 1 car, depending on the case. This is a SINGLE OPERATION performed on the SET OF REMAING DOORS AS A WHOLE and because either case is possible Monty must have complete knowledge of what is behind all the remaining doors in order to perform this single operation.

Note that this operation is performed on the set of nine. Because Montyâs sort operates on the nine doors as a set, the probabilities for the problem are divided into two. The door you picked and the set of nine remaining doors. That is, the chances of the car are 10% and 90% respectively.

So your odds do not change as Monty reveals eight of the set of nine doors as a goat. You were aware that there must be atleast 8 goats within this set of 9 doors anyway. This operation that Monty has performed on the set makes no difference to you.
If on the other hand Monty had a late night the previous night and became forgetful. He allows you to choose a door. Except this time Monty remembers only 8 doors of the remaining 9 doors and he remembers each of these doors having goats. So he is unsure of the whereabouts of the car exactly.

This is a different problem. Monty no longer has complete knowledge of what is behind the remaining doors and therefore is unable to perform the OPERATION stated above. Although he may be able to reveal 8 goats this time, this will only be coincidence. Many other times eight doors would reveal the car and the contestants would lose). As the problem is no longer divided into two sets, each time Monty reveals a goat your odds of winning the car increase â up until the point when 2 doors remain when your chances reach 50:50.

SO IT IS IMPORTANT THAT YOU KNOW WHAT MONTYâS KNOWLEDGE IS AND EXACTLY WHAT HE HAS PERFORMED BEFORE YOU CAN ASSESS A WINNING STRATEGY.

SO IN SUMMARY:

- If Monty invites you to make use of his information via a sort he performs then this is very good.

- If Monty reveals a door that is a goat but had the possibility of being the car then this increases your odds.

- If you refuse to make use of a sort procedure and instead Monty offers you worthless information that you already knew - then your odds will not increase.