The Progressive Monty Hall Problem, Again

Sorry for the sporadic blogging. For the past week I’ve been working on the Progressive Monty Hall problem, and it has proven to be considerably more complicated than I at first realized. I had expected to polish it off with a few hours work. Instead I have thought about little else for the past several days, and have grown very unhappy with my inability to prove certain statements that are obviously true. Adding to my frustration is the nagging feeling that I am overlooking something simple and conclusive. So, I figured, why not turn it over to my readers?

I blogged about this previously. But I will go into far more detail now.

Here’s the problem. You are a game show contestant confronted with n identical doors. Behind one of them is a car, the others conceal goats. You choose one of the doors, but do not open it. Monty (the host of the show) now opens a door other than the one you have chosen most recently, always choosing one he knows to conceal a goat. He now gives you the options of sticking with your original door or switching to some other door. After making your decision, Monty opens another goat-concealing door. Again you are given the options of sticking or switching. This continues until only two doors remain. At this point you make your final decision, and then you receive whatever is behind your door. Throughout we assume that Monty chooses randomly from among the goat concealing doors when there is more than one such door. What strategy should you follow to maximize your chances of winning the car?

So there it is. The optimal strategy is actually pretty obvious. You stick with your initial choice until only two doors remain. You will win with probability n-1/n by following this strategy. Basically, your initial choice is correct with probability 1/n This probability does not change when Monty opens goat-concealing doors. Therefore, it will still have probability 1/n when only two doors remain. It follows that the other door will have probability n-1/n, as claimed.

This can all be proven rigorously using Bayes’ Theorem, but I’ll spare you the annoying details.

The intuition behind this strategy is that every time Monty opens a door he is giving you information about the location of the car. The optimal strategy will be the one that forces Monty to give you the maximum amount of information at each step. You receive more information from learning that an improbable event occurred than from learning that a likely event occurred. If you switch from your initial choice, you are allowing Monty to open a door that you already knew was very unlikely to be correct. By sticking with that door, you force Monty to open one of the other doors, and these doors are far more likley to conceal the car. So you should stick with your initial choice for as long as possible.

I am trying to prove that this strategy is not only optimal, but that it is uniquely optimal. That is, any other strategy gives you a probability of winning that is strictly less than n-1/n.

Now for the complications. Let D_i denote the event that the car is behind door i. Let M_j denote the event that Monty opens door j. Every time Monty opens a door, we use our new information to update the probabilities. That is, we try to evaluate P(D_i|M_j), the probability that door i conceals the prize given that we just saw Monty open door j. This, as always, is accomplished via Bayes’ Theorem.

Let’s do a warm-up exercise. Suppose there are five doors. We choose door one, and then watch as Monty opens door two. If what I said earlier is correct, then this revelation should not alter the probability of door one. According to Bayes’ Theorem we have:

P(D_1|M_2) = P(D_1) P(M_2|D_1) / P(M_2).

We clearly have P(D_1) = 1/5. Since Monty chooses randomly from among the goat concealing doors, we have P(M_2|D_1 )= 1/4. (If the prize is behind door one then Monty will choose randomly from among the other four doors).

The term on the bottom is a bit more complicated. The probability that Monty opens door 2 depends on the location of the car. So we write:

P(M_2) = P(M_2|D_1) P(D_1) + P(M_2|D_2) P(D_2) + P(M_2|not (D_1,D_2)) P(not (D_1,D_2)).

Now, P(M_2|D_2) = 0. If the car is behind door 2 then Monty will not open that door. We also have P(M_2|not(D_1,D_2)) = 1/3 and P(not(D_1,D_2)) = 3/5. (Note that doors one and two each have a probability of 1/5. So the probability that the car is not behind either of those doors is given by 1-(2/5).)

If you now plug all this in you get:

P(D_1|M_2) = (1/5)(1/4) / (1/5)(1/4) + (1/3)(3/5) = 1/5,

precisely as expected.

So far so good. Let’s push this a little farther. Suppose at this point you switch to door 3. Since door 1 has probability 1/5, door 2 has been eliminated, and doors three, four and five are identical, they all must have probability 4/15. What happens if Monty now opens door 1?

Using the same Bayes’ Theorem argument as before, we would now evaluate: P(M_1|D_3) = 1/3, P(M_1| not (D_1,D_3)) = 1/2. Plugging in now gives

P(D_3|M_1) = (4/15)(1/3) / (4/15)(1/3) + (1/2)(8/15) = 1/4.

Did you catch that? Did you see what just happened? Initially we assigned a probability of 4/15 to D_3. But after Monty opened door 1 we assigned a probability of 1/4 to D_3. That means P(D_3) went from 4/15 to 1/4 as the result of Monty opening door one. So P(D_3) actually went down!

And that’s the first question. Can anyone provide a simple, intuitive reason for why this is so? Why is it unsurprising that door 3 seems less likely after Monty opened door 1 than it did before Monty opened that door?

The message of our calculation is clear. After door two is eliminated there are four doors remaining. If we pretend for the moment that all are equally likely , then we would assign a probabiltiy of 1/4 to each of them. It’s as if we were playing the game from scratch with only four doors instead of five, and then watched as Monty eliminated one of the doors. So the effect of eliminating door one from the game is to erase all traces of history. But it’s not clear to me why eliminating door 1 has that effect.

Let’s move on. The fact that it is actually possible for the probability of a door to go down as Monty opens doors makes it quite difficult to prove that the strategy of switching at the last minute really is optimal. Here’s the problem: Regardless of the strategy we follow, there comes a time when only two doors remain. We want one of those doors to have a very low probability, so that we can win with high probability by switching to the other door. Outperforming the switch at the last minute strategy requires that one of those doors have probability smaller than 1/n. Now, every door starts with that probability. But how do we know that we can not drive the probability down below that level with some clever sequence of switches during the game?

That’s the problem. Here’s an attempted solution. While it is true that the probability of a door can go down in the course of the game, I think there is a definite statement that can be made regarding how far it can go down. If you choose a door at a time when x doors have been eliminated, then no matter what happens in the future, regardless of how many times you switch or which doors Monty opens, that door will always have a probability of at least 1/(n-x) for as long as it remains in play.

In the example we worked out before, we first chose door 3 at a time when four doors remained in play. We saw that we could then drive the probability of this door down to 1/4. But if I’m right, then no subsequent events could possibly drive this probability down any lower.

The situation here is the reverse of the question I asked a moment ago. I regard this as intuitively obvious, but I lack a rigorous proof. I regard it as obvious for the following reason: Regardless of which doors you have chosen in the past, after x doors have been eliminated there are n-x doors still in play. If all of those doors were identical you would assign a probability of 1/(n-x) to each of them. That probability represents the most ignorant you can be about the location of the car when only n-x doors remain. The fact that you might have chosen other doors earlier in the game only drives up the probability of the never chosen doors. That is, knowing that some of the n-x doors have a lower probability because they were chosen at some earlier point in the game only makes the never chosen doors seem more likely to be correct.

No matter what happens, Monty can not take away from you the fact that you know the door was chosen from a selection of (n-x) ostensibly identical doors. If he dutifully eliminates all of the previously chosen doors then that is all you will know about the probability of that door, and you will assign it a probability of 1/(n-x). But you will never have a reason to think the door is less likely than that.

That seems convincing to me. But a proof would be nice.

Considerably more than this can be said, but if you grant me this then it is straightforward to show that the switch at the last minute strategy is uniquely optimal.

Among the other things that can be said is the fact that the only way to drive down the probability of a door is by having Monty open previously chosen doors. That is, no door has its probability go down as a result of Monty revealing there is a goat behind a door that you had never previously chosen at any point during the game.

The Bayes’ theorem arguments I gave above can be readily adapted to more general situations. Instead of five doors, we consider n doors at the start of the game, and we suppose that we are considering the moment when x doors have been eliminated. You can then work out all sorts of inequalities about what it would take for some probability to dip below 1/n as the result of Monty’s door opening. I have dozens of pages of scrap paper strewn about my office working out these sorts of calculations for different starting assumptions. And I have an awful lot of very suggestive stuff. But no slam dunk argument. Yet.

So I haven’t just been blowing you guys off frivolously. It’s just that it’s part of the mathematical temperment that when you latch on to an interesting problem it’s basically impossible to think about anything else, no matter how miserable the problem is making you. Over the past week I have tried at various times to pick up any of the four or five books I’m in the middle of, only to find my mind drifiting back to this problem after just a few paragraphs.

Whatever. The problem will yield. Oh yes. It will yield…

Comments

#1 Kurt
August 1, 2007

And that’s the first question. Can anyone provide a simple, intuitive reason for why this is so? Why is it unsurprising that door 3 seems less likely after Monty opened door 1 than it did before Monty opened that door?

Um, because you made a calculation error?

I’ve always felt that it’s a mistake to use Bayes’ theorem in the Monty Hall problems, not because it can’t be done, but because it’s unnecessary and just muddles up things (and makes it easy to make calculation errors). In fact, after you first made that series of posts on Monty Hall and related probability puzzles, I started writing a blog entry about this, but alas never finished it. Maybe I’ll be motivated to do that now.

Anyway, your problem is that you’ve convinced yourself that the probability of a given door can decrease during a step, and that’s simply not true. (Well, not quite: the probability of the door that’s revealed goes to zero.) The probability of the door that you’re currently sitting on stays the same, and the probabilities for all of the other doors go up proportionately to make up for the difference of the revealed door. Once you convince yourself of this fact, it is immediately obvious that your strategy is in fact uniquely optimal.
#2 schep
August 1, 2007

I think I just proved by induction on the number of remaining doors:

If n doors are remaining, with respective probabilities of hiding the prize p_1, … p_n, then the optimal player’s probability of winning is 1-min{p_i}.

If that’s not enough explanation, or it doesn’t seem to work out for others, I can copy my notes to LaTeX and post, maybe on the weekend.
#3 Kevin
August 1, 2007

“Behind one of them is a car, the others conceal goats”

are they good-looking goats?
#4 Kevin
August 1, 2007

“What strategy should you follow to maximize your chances of winning the car?”

what if I would rather have the goat?
#5 schep
August 1, 2007

No, Kurt, the probability of a given door really can go down, depending on what Monty does. For an even simpler example, let’s say that I started with 101 doors and am now down to 3. I’ve been sticking with the first one, so the probabilities are now 1/101, 50/101, 50/101. But now I (foolishly) switch to door #2.

There are four possibilities:
D1, M3: 1/101
D2, M3: 25/101
D2, M1: 25/101
D3, M1: 50/101

Now Monty opens door 1. The first two possibilities didn’t happen. And looking at the ratio of the latter two, P(D2) is now 1/3. It went *down* from 50/101 to 1/3.
#6 schep
August 1, 2007

Oh yeah, I forgot the goal of proving *uniquely* optimal. But the end result of the induction step does give an inequality if there’s a unique minimum probability (i.e. not the first irrelevant decision).
#7 Kurt
August 2, 2007

Sorry, schep, I’ll stick with my initial comment. In fact, I’ll go so far as to wager that about the time Jason reads the last sentence of my comment, he slaps his forehead and shouts, “D’oh!”

I honestly don’t quite understand where you got the probabilities in your example, so I can’t comment on where you might have gone wrong. But here’s the way I would describe the situation in your final step: You’ve just switched to door #2, which has a probability of 50/101 of holding the car; door #1 has probability 1/101, and door #3 has probability 50/101. We’re in agreement here. Now, Monty has control of the pool of doors consisting of doors 1 and 3. Collectively, this pool has a 51/101 chance of holding the car. Monty is going to reveal a door without a car behind it, which he can always do at will. This is the key point, and also why one needn’t bother with conditional probabilities at all. The pool of doors controlled by Monty and still concealed is going to have the same collective probability, 51/101 in this case, and it’s going to belong to whichever door he didn’t reveal. (The probability of the door he does reveal becomes, obviously, zero.) Door #2, which you control, plays no role in this process and its probability does not change from 50/101.

The key point is that except for the revealed door, the probabilities never decrease.
#8 Kurt
August 2, 2007

My apologies to the English composition gods for referring to two separate things as “the key point” in my above comment. Actually, make that an apology to the logic gods, since obviously at most one point can be “the key point”. The apology to the English composition gods should be for using clichéd expressions…
#9 FhnuZoag
August 2, 2007

Hmm, I think I have a more intuitively obvious proof.

The basic idea is to avoid direct application of Bayes, and instead work with odds – i.e. ratios of probabilities.

So, for N doors, we have a N-component vector which represents the ratio of probabilities for the car being behind each door – note that we can multiply the entire vector by any constant and get the same situation.

Why is this helpful? Because with odds, bayesian stats is just a matter of multiplication. When a door is opened, the new odds is the componentwise multiplication of the prior odds with another likelihood odds vector, which has components representing the relative likelihood of the given door being opened supposing that the car was actually behind the corresponding component’s door.

It’s easy to see, then, that if we choose a door j, and door i was opened to give a goat, it is possible to rescale the likelihood vector to give 0 in the i vector (since it’s impossible for i to be opened if the car was there), 1 in the j vector (because we multiply the whole lot by a scalar so that this is the case, without affecting the ratios), and a number greater than 1 in every other component (because if then, two doors cannot be opened instead of just 1, so the likelihood of that particular door is greater).

So, our final odds vector, which is reduced to 2 non-zero components, has the remaining two being the product of a bunch of numbers, and the optimal strategy is precisely the one that maximises the difference between them. For each trial, there is one 1, and one >1 left in the final product of numbers, so clearly the way to max the difference is to have all the 1 multiplied together, and all the >1s multiplied together – which corresponds to choosing the same door every time.

Does that make any sense?
#10 Johan
August 2, 2007

I am a total non-mathematician but it seems to me that no matter what you do, in the end you end up with 2 doors. One has a goat and one has a car. It seems to me that the chance is simply 50% of getting the car (being right).

Isn’t the mistake you’re making that you believe that any or all actions you take before you arrive at the two doors have any influence on the actual outcome?
#11 Joseph
August 2, 2007

Here’s my highly non-technical proof of optimal strategy.

Suppose your probability of going into the N+1 door game with N>=2 having picked a goat is x. If you don’t switch doors, you go into the N door game with a probability x of having picked a goat. If you do switch doors,

a fraction (N-1)/N of people with goats switch to goats;
a fraction 1/N of people with goats switch to cars;
all people with cars switch to goats;

so you have a probability 1-x+x*(N-1)/N = (N-x)/N of entering the N door game with a goat when you switch doors.

The key to winning the car is having a probability of having picked a goat as far from 1/2 as possible. Assume that one starts with x>1/2. Now:

(N-x)/N is further from 1/2 than x when N/(N+1) > x
(N-x)/N is just as close to 1/2 as x when N/(N+1) = x
(N-x)/N is closer to 1/2 than x when N/(N+1) < x
and (N-x)/N is always greater than 1/2 (unless N=2 and x=1, but then it's trivial to show that only switching in the 2 door game is an optimal strategy in this case)

So if x > N/(N+1) going into the N+1 game, making a switch hurts your chances of winning.

You start going into the M game for some M>=N+1. You start with x=(M-1)/M since you choose a door at the start and are forced to keep this x going into the M-1 game because Monty has to open at least 1 door before you get a chance to switch. Since (M-1)/M >= (N/N+1) > 1/2 for all M>=N+1 and N>=2 (since x isn’t 1 here), it follows that any switch made before reaching the 2 door game hurts your chances of winning. So the optimal strategy is never switching until making one single switch at the 2 door game with probability x > 1/2 of switching to a door with a car.
#12 Joseph
August 2, 2007

I can’t believe I put a major typo in my comment.

Amend my previous comment to read

“(N-x)/N is closer to 1/2 than x when N/(N+1) < x;”
#13 Joseph
August 2, 2007

There must be something wrong here at 1 am.

Make that read “(N-x)/N is closer to 1/2 than x when x is greater than N/(N+1);”
#14 FhnuZoag
August 2, 2007

Johan:

I’m afraid not. You’ve basically fallen into the classic Monty Hall trap.

The basic idea is that by using inference, the observations you have made – i.e. the doors opened, gives you information about the actual state of the world – i.e. where the car actually is.

A more intuitive example is: suppose you flip a coin and it comes up heads a whole bunch of times. Then you have a good reason to believe that the coin is loaded, and that it will come up heads more often than a fair one would.

The difference between this and the idea of a sort of reversed gambler’s fallacy – where past observations have no effect, is that at the start, you don’t actually know for sure that the coin is fair. Indeed, how willingly you conclude that from now on, the coin will always give heads – your so-called posterior probabilities – is based on your ‘prior’ beliefs – whether you believed the coin was loaded or not, and how strongly you thought so. In this way, the classic gambler’s situation corresponds to the case that you believe infinitely strongly that the coin is fair.
#15 AnInGe
August 2, 2007

Assume n = 10. 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.
#16 Ruth
August 2, 2007

I haven’t read all the comments, but I want to reinforce the point that has been made by several other commenters.

The probability that the car is behind the CURRENTLY SELECTED DOOR can NEVER change, regardless of what Monty Hall does.

This is because the probabilities only change because, as you say, Monty Hall’s opening of a particular door gives you new information about not only that door, but all other doors IN CONTENTION.

It’s that ‘in contention’ bit that you are missing. The door that is currently selected is NEVER included in Monty Hall’s choice of which door to open, regardless of what it has behind it. Monty Hall’s opening of a door can only give you information about the doors that he included in his decision making process. In other words, about every door EXCEPT the one that you have currently selected.

Just as in the original three-door version of the problem, the probability of your currently selected door being the right one cannot change. Since, after the first door-opening, every door except the one you first chose has a probability greater than 1/n, and since opening a door can only ever INCREASE the probability for any door apart from the one opened, which, by the rules of the game, will never be the one you have currently chosen, no door other than the door you first chose will ever have a probability of 1/n or lower.
#17 Sam the Centipede
August 2, 2007

In the N-door problem, the probability of choosing the right door is 1/N so the probability of the car being in the remaining pool is (N-1)/N and this is unchanged by doors opening IF AND ONLY IF the contestant does not change their choice. Hence it is best to swap at the end (with 2 doors remaining) because the probability remains at 1/N for the original choice and (N-1)/N for the other door, and (N-1)/N is almost 1 for big N and always bigger than 1/N for N>2. That’s the standard argument I think.

However, if the contestant elects to change their choice after some doors have been opened say when there are M doors (M < N) they have effectively restarted the entire problem; the opened doors are completely irrelevant. So now the probability at the end (2 door) stage is 1/M for the revised choice and (M-1)/M for the remaining unchosen door.

And (M-1)/M is always less than (N-1)/N for M < N (both positive).

No Bayesian stuff. Any problems with this argument?
#18 Brian Thompson
August 2, 2007

I’ve always wanted a goat. I have a car. Its old and smelly. I’ll take a young and smelly goat instead.
#19 divalent
August 2, 2007

I didn’t read too carefully the comments above (so this might have, and probably was, stated above). but its seems to me that if you get a jump in the probability of the door you “own” when something else happens, then you aren’t calculating it properly. You lock in the probability of door 3 (the door you now “own”) when you choose it. It was 4/15 at the time you switched, so it remains that way regardless of which door is opened.

When Monty opens any door, it releases the probability that was assigned to that door, and that should be distributed only to the remaining “un-owned” doors.

BTW, the goal of the “hold-to-the-end then switch” strategy is to ensure that each door that is opened along the way releases the maximum possible amount of probability, while you lock your initial door at its initial low probability. In the case where you switch, you lose because you release a low probability door in exchange for a higher probability door (which is bad for your strategy).
#20 jedipunk
August 2, 2007

When I first heard of the Monty Hall problem it seemed counter-intuitive.

Instead of turning one door over at a time I resolved my issues this way.

Imagine 100 doors.
You get to pick one door.
Monty opens 98 doors showing goats.
Two doors remains: Yours and one other.
Which one likely has the car?
#21 JimV
August 2, 2007

I got hung up on a different paradox (or maybe the same paradox under a different name), based on your 5-door example. We had (adjusting your notation slightly to save typing):

P(D1|M2) = P(M2|D1)*P(D1)/P(M2)

I’ll expand P(M2) differently but equivalently:

P(M2) = P(M2|D1)*P(D1)+P(M2|D2)*P(D2)+ … +P(M2|D5)*P(D5)

Now suppose P(D1)=P(D3)=P(D4)=P(D5)=p (so P(D2)=1-4*p). Then,

P(M2|D1) = 1/4 (Monty is equally likely to pick doors 2-5)
P(M2|D2)=0 (Monty won�t pick the door the car is behind)
P(M2|D3)=1/3 (since we guessed door 1, Monty won’t pick 1 or 3)
P(M2|D4)=1/3
P(M2|D5)=1/3

P(D1)=p

Substituting these values in the Bayes formula:

P(D1|M2) = (1/4)*p/{(1/4)*p+0*(1-4*p)+3*(1/3)*p} = 1/5 (regardless of the value of p!)

Say for example we had a mole in Monty’s organization who gave us the additional piece of information that the car was not behind door 2, but could be behind any one of the other four doors. So p =1/4. If Monty opens door 2 after our initial guess of door 1, we have no new information, yet by Bayes formula, the probability that the car is behind door 1 has changed from 1/4 to 1/5, and the probabilities for doors 3-5 have changed from 1/4 to 4/15!

To check my arithmetic and thinking, I did a thought experiment, simulating a bunch of random trials for the above case [P(D2)=0]. I guess door 1, then for each of the four possibilities, Monty does 12 random trials which are perfectly uniformly distributed.

D1: 3 M2′s, 3 M3′s, 3 M4′s, and 3 M5′s

D2: won’t happen, no trials

D3: 4 M2′s, 4 M4′s, and 4 M5′s

D4: 4 M2′s, 4 M3′s, and 4 M5′s

D5: 4 M2′s, 4 M3′s, and 4 M4′s

So there are a total of 15 M2′s among the 48 trials, and 3 of them occur under D1, so indeed the as-measured result is P(D1|M2) = 3/15 = 1/5.

This happens under the case that we have initially guessed door 1. Call this G1. If you extend the above series of trials to include G2 through G5, then the measured result for P(D1|M2) becomes 1/4.

So far, the best explanation I have is that there can be a difference between the result we can measure for a given initial guess (G1) and the “absolute” probability over all initial guesses (G1-G5).
#22 Justin
August 2, 2007

What is interesting, non-mathematically, is that Monty could easily figure out what your doing by choosing different doors at each step and not choose to reveal those previously chosen doors if they had a goat behind them.

If he did reveal each of your previously chosen doors in succession and skipped one, then you would either know that was the car or that he changed strategies.

I think that changing doors at each step might be more beneficial in the end. Your probability of choosing one of the final door would higher.

But in reality, if Monty’s goal is for you to have your door and a goat door left, mathematics go out the window and your stuck with a 50/50 shot. He can manipulate it that way. Your chances would never be better than 50/50.

Right?
#23 Fastlane
August 2, 2007

Several previous discussion about this at the Internet Infidels forums.

http://www.iidb.org/vbb/showthread.php?t=178640
http://www.iidb.org/vbb/showthread.php?t=163211
http://www.iidb.org/vbb/showthread.php?t=160845
http://www.iidb.org/vbb/showthread.php?t=160558

I had found a website that repeats the experiment by random choice, than showing the odds, but my google fu is failing me this morning.

Anyway, the way it works out you should always switch to increase your odds.

Cheers.
#24 David D.G.
August 2, 2007

Actually, the problem is that until the final door is opened, what is behind it is both a car and a goat (i.e., one object that has the condition of being both objects simultaneously), until the door is opened and we can observed the door’s actual contents.

The fallacy is to have categorized this as a Monty Hall problem in the first place; it is actually a Monty Schroedinger problem.

;^D

~David D.G.
#25 mark
August 2, 2007

It seems if we try to think in realistic terms, the case is hopeless. On a whim, Monty might not go through the entire process, but reveal the car with 4 doors remaining. Or offer a cash option to quit. Or break for a commercial while they replace the Ferrari with a Studebaker Lark.
#26 saul
August 2, 2007

1) It does seem reasonable to me that opening door 1 “erases history.” After door 2 is opened, our estimates of the likelihood of the car’s being door j have to take into account the possibility that we chose the correct door to begin with. After we switch to door 3 and door 1 is opened, we know that that possibility didn’t occur. Intuitively, the situation seems identical to the one where we start with doors 1,3,4, and 5 only, and we choose dooor 3 and Monty opens door 1. Suppose you walked in on the process at this point, and calculated the probabilities as P(D_3) = 1/4 P(D_4)=P(D_5)=3/8, and now someone tells you that actually, the contestant picked door 1 originally, etc. Would you say, “Oh, that’s different, now I think …”? What does the history have to do with it? (of course, if Monty opened door 4 instead, it would be important to know that it was the second door he opened, and that Monty was precluded from opening door 1 at the first stage.)

2) While I haven’t tried to prove the theorem, I think the germ of a proof is something like this: Suppose, when we get down to two doors (that is, after n-2 rounds) that there where k rounds when I had selected a door other than the one I have now. Then the probability that the car is behind the door I have chosen is more than 1/n, because if it concealed a goat, Monty might have opened it on one of those k rounds.
(Compare the “rule of restricted choice” in card play.) So, I benefit less by switching in this case than I might.
#27 Jason Rosenhouse
August 2, 2007

First, let me thank everyone for the thought provoking comments. Here are a few thoughts in reply:

Kurt:

I’m afraid I’m sticking with my original story. It really is possible for Monty’s actions to drive down the probability of the door you are on by opening some other door. Now, if I could give a slam-dunk, intuitive argument for why that is so, I would have done so in the original post. All I can say is that I believe I have applied Bayes’ theorem correctly, and Bayes’ don’t lie!

schep-

As it stands, I don’t think your argument proves very much. At any stage of the game, we know the probability of each door. So if the game were to end at that moment, we would switch to the highest probability door. The problem, however, is in quantifying the probabilities of the doors. We have to show that regardless of how you play the game, none of those p_i’s has a value smaller than 1/n. Induction might be very useful in that regard, but I would need to see more details.

I like your illustration with the 100 doors. It’s another example of what I am talking about. In your example, we switch to door two at a time when three doors remain. If Monty now opens door one, the probability of door two goes from close to 1/2, down to 1/3. That is, 1 over the number of doors remaining when we picked it. But nothing can drive its probability lower than 1/3.

Kevin and Brian Thompson:

Of course, if you’re really keen on winning a goat, the correct strategy is obvious. You stick with your original door and never switch. Ever. Then you will win the goat with probability (n-1)/n. And if you can prove that really is the best way to win a goat I’d be really grateful, since that would effectively be equivalent to what I have been trying to prove!

Kurt, Again:

In schep’s scenario we are sitting on door two. Only doors one, two and three remain. Therefore, there are four scenarios. If the car is behind door one, Monty will have to open door three. This happens with probability 1/101. If the car is behind door two, then half the time Monty will open door one, and half the time he will open door three. Since the car is behind door two with probability 50/101, we find that each of these two scenarios will happen with probability 25/101. Finally, if the car is behind door three, then Monty will be forced to open door one. This happens with probability 50/101. This shows that in those cases where Monty opens door one, the car is twice aas likely to be behind door three as it is to be behind door two. That’s how we get probabilities of 1/3 and 2/3 for those doors.

I think the problem with your analysis of schep’s example is that you are not taking into consideration everything we know. Yes, we knew ahead of time that Monty would show a goat. But we do not know ahead of time which door Monty will open. If the doors have different probabilities of being correct, then there is a difference between, “Monty revealed a goat, just as we knew he would,” and “Monty has shown us that door X conceals a goat.”

FhnuZoag-

Your approach sounds interesting, but I’m afraid I found it hard to follow. I’m not accustomed to thinking in terms of odds and likelihoods. I’ll need a clearer explanation of what these vectors are meant to represent.

Johan-

Your analysis would be correct if we didn’t know that Monty only reveals goats. If Monty were just choosing randomly, and by sheer luck happened not to reveal the car, then it really would be 50-50 at the end. This is very similar to what happens in the game show Deal or No Deal. If only two cases remain and only one contains the million dollars, it is fifty-fifty which case contains the prize. The situation is very different when Monty is careful only to open goat doors, though you’re certainly not the first person to find that counterintuitive!

Joseph-

I’ll have to think about your argument a bit more before coming to a conclusion about it. The idea of approaching the problem recursively is certainly very interesting.

AnlnGe-

Your statement that you win with probability 1/2 if you switch every time is not correct, I believe. In fact, I can prove that if you switch every time your probability of winning will be very close to 1-(1/e) when the number of doors is very large. This is rather difficult to prove, however.

Unfortunatly, in casually dismissing the importance of Monty’s actions, I think you are making the same error a lot of people make in thinking about this problem. It is true that Monty is forced to open goat doors. But depending on how you play the game, you know something about the probability of each door before Monty opens it. Seeing Monty open a door you already knew was highly unlikely is not the same as seein him open a door that had a high probability.

Ruth-

Alas, my position hasn’t changed since responding to Kevin. Bayes’ theorem says that under the right circumstances the probability of your door can, indeed, change when Monty opens a door. I regret that I lack a more persuasive explanation than that.

Sam the Centipede-

There is a lot of Bayes’ stuff in your argument. Your assertions about when various probabilities can change have to be defended with something, and that something is Bayes’ theorem. Also, if you switch multiple times during the game, you will have a situation in which the remaining doors have many different probabilities of being correct. This seriously complicates the analysis as the game progresses.

divalent-

See previous responses.

jedipunk-

I think that’s a good way of thinking about the classical, three-door version of the problem. But since there is nothing in it that takes into account the effects of switching doors, I don’t think it is so useful here.

Jim V-

I don’t have a knee-jerk reply to your comment. I’ll have to think about it a bit.

Justin-

It’s built into the problem that Monty always chooses randomly from among the goat doors at each step. So as I presented the problem there is no danger that Monty will open his doors in a way designed to nullify your strategy.

David D.G.-

I love it! Actually, your comment reminded me of a magic trick I saw once. A magician had four large, opaque containers on the stage. He placed adorable bunny rabbits in three of them and a vicious cobra in the fourth. These containers were then mixed up so the magician, apparently, had no way of knowing which container contained the snake. He then had someone from the audeince draw balls numbered 1-4 from an urn. Whichever number came up, the magician would go to that container, thrust his hand inside, and pull out whatever animal was there. He did this three times, and each time, miraculously!, found there was a bunny in his container each time. He then went and poured out the contents of the fourth container, and sure enough, there was the cobra.

The way he did it (I think!) is that each container actually had both a bunny and a cobra, presumably in different, cordoned off sections inside (we were never allowed to look inside the containers). Not exactly quantum mechanics, but what can you do?

mark-

If I were interested in realism, I wouldn’t study pure mathematics. I leave realism to the applied guys!

saul-

I think you make some interestin gpoints. Let me mull it over for a while.

I have been working on this comment for a while, so I apologize to anyone who has posted since I started writing. I am not ignoring you! It’s just that our comments crossed in cyberspace.
#28 AnInGe
August 2, 2007

JR responds to my comment (the 15th comment in this thread):

“Unfortunatly, in casually dismissing the importance of Monty’s actions, I think you are making the same error a lot of people make in thinking about this problem. It is true that Monty is forced to open goat doors. But depending on how you play the game, you know something about the probability of each door before Monty opens it. Seeing Monty open a door you already knew was highly unlikely is not the same as seein him open a door that had a high probability.”

But there are no such things as ‘highly unlikely’ and ‘high probability’ doors! If, at any point in the game there are N doors left unopened, from your state of knowledge they all have exactly the same probability of hiding the car, which of course is 1/N. The doors that have been opened have (from your state of knowledge) exactly probability 1.0 of hiding a goat and 0.0 probability of hiding a car. This is totally independent of any actions of sticking, switch, and door opening that have gone before. You, and many other commenters in this thread, are making the same mistake as the gambler who is convinced that since he has had a run of bad luck, his luck must be ready to change. How strange that you reject mysticism in others, yet are convinced it pervades Monte Hall’s sound stage. If there are N unopened doors and Monte opens a (necessarily goat) door leaving (N-1) unopened doors, your state of knowledge for that door changed a probability of 1/N that that door hides a car and 1-1/N it hides a goat to probability 0 it hides a car and 1 that it hides (hid) a goat. Your state of knowledge for the remaining doors goes from probability 1/N each hides a car to 1/(N-1) each hides a car. Period. Simple. No Bayesian analysis called for.

I get the impression that you have access to cheap slave labor (grad students). Why not have one program this game, run a statistically significant set of trials for some N and all variations of sticks&switches, and see what probabilities you converge to? (Note that if your results do not agree with my analysis in the 15th comment, there is something wrong with your program.)

Ironically, Thomas Bayes himself would never have applied Bayesian analysis to this problem. Being a devout Presbyterian minister, he would have fallen to his knees and prayed for divine guidance. Having lived from 1702 to 1761, he would have had little need for the car (no gas stations) he would have prayed for one of the goats.
#29 Brendan S
August 2, 2007

100 doors. You hang on to A until it’s down to 4. Thusly the probs. are like this:

a: 1/100
b,c,d (99/3)/100 or 33/100 Each.

Now, you switch to B. YOU have no info about the system, so B is locked at 33/100.

The REST OF THE SYSTEM consists of 67% distributed among 3 doors. Any of them opened makes the other two 33.5% probable.
#30 schep
August 2, 2007

I’ll write up my proof better for closer analysis when I have time for it.

For now, a response to the repeated claim that “the probability of the door you choose cannot change”: What if the a-priori probabilities are 0, 1/2, 1/2? Alice selects door #2. Monty opens door #3. The probability the car is behind door #2 is now, I hope you’ll agree, 1, not 1/2. This doesn’t change much if the initial probability for #1 is one in a billion rather than exactly zero.

That claim happens to be true for the classic 1/3, 1/3, 1/3 example, and also for the optimal strategy for the progressive version, but is not the way things work when starting with different probabilities. It’s a bit of a surprise to me too, since it’s so often used as the quick explanation for the Monty Hall problem, but we can’t use it as a law of probability.
#31 divalent
August 2, 2007

Once again, I’ll state emphatically that the probability of the door you own having a car does not change when Monty displays a goat behind another (unless its the penultimate door he opens). It is locked in at whatever it is at the time you choose it.

Think about it: in the situation you describe, you *know* that monty can and *will* open a door that is *not the door you own* and show a goat. It is 100% certain. So, if it is 100% certain that he can do this *before he actually does it*, it should not affect that probability of any door that has no possibility of being a part of his action. And the only door that can’t possibly be a part of his action is the door you own (all other doors are possible candidates for being opened).

Before he opens that door, there is some probability that your door has the car (which can be determined) and some probability that it is somewhere else. That “somewhere else” probablility is 1-(your door’s probability).

By opening a door, you only redistribute the “somewhere else” probability to the remaining (non-owned) doors.
#32 divalent
August 2, 2007

I should have added the conclusion, which is:

therefore, if your model has the probability of the door you own changing when monty opens that door at that time, then the model is invalid.
#33 JimV
August 2, 2007

(Why do I only start thinking about this problem again when my head hits the pillow?) Okay, carry on, I understand why that paradox that puzzled me in my first post isn’t actually a paradox (the one where P(D1|M2) is 1/5 regardless of the value of p).

When I first heard of the Monty Hall Problem, it reminded me the “Theory of Resticted Choice”, from bridge. I.e., if you and dummy have nine cards of a suit missing the jack, queen, and two small cards; you lead the suit and your left-hand opponent plays the jack; then he could either have the singleton jack or the doubleton jack-queen, but the odds are about 2:1 that the jack was a singleton, because if he had the jack-queen, half the time he would have played the queen instead of the jack, whereas if he only had the jack he had no choice.

The same kind of thing happens in my problem. First considering the case where p=1/4, the fact that Monty opens door 2 actually does tell you a little bit more than you already knew. If the car were behind door 1, he could have chosen any of doors 2-5, but if the car is behind one of doors 3-5, he has less of a choice.

For the case where 1-4*p was not zero, opening door 2 converts that case retroactively to the p=1/4 case – so all roads should lead to Rome, where Rome is P(D1|M1)=1/5.

I think that is basically the same issue as your first request. Having switched from door 1 to door 3 in your example, seeing door 1 opened slightly ups the chances that the car is behind door 4 or 5, and slightly lowers the chance that it is behind door 3, because there would be slightly less of a chance for Monty to open door 1 (more choices) if the the car were behind door 3.

I’m going back to bed now. Maybe tomorrow night I’ll think about your second issue, if you or somebody else hasn’t already resolved it.
#34 fredk
August 3, 2007

JimV pretty much said the same thing I had to say, but I took a bit less mathematical approach to things. I think the first observation to make is that your choosing a door places no restriction on the probabilities in the problem. All choosing does is prevent Monty from opening that door. After Monty opens another door, the probability of your door may go up, down, or stay the same. The three door problem with unequal probabilities is a good example. Door 1 has 0 probability of having the car, and Doors 2 and 3 each have 1/2 probability. If you choose Door 3 your probability of winning is 1/2. If Monty opens Door 2 revealing a goat, then you have a 100% chance of winning by sticking with Door 3. However, if Monty opens Door 1, then Door 3 only has a 25% chance of winning. That’s because Monty has increased the chance of Door 2 being the winning door by NOT choosing it. Basically, if Door 3 were the winner, Monty would be equally likely to choose either Doors 1 or 2, but if Door 2 is the winner, then he will always choose Door 1. The fact that he chose Door 1 makes the second scenario more likely. You can write out the possibilities to get the exact numbers:

You choose Door 3:

If Door 3 is the winner (50% probability)
Then 50% Probability Monty opens Door 1: Total P=25%
Then 50% Probability Monty opens Door 2: Total P=25%

If Door 2 is the winner (50% probability)
Then 100% Probability Monty opens Door 1: Total P=50%

So, the probability that the chosen Door 3 is the winner and that Monty opens Door 1 is 25%.

The unequal-probability 3 door problem was easier for me to puzzle through than the unequal-probability 4 door problem Jason posted on, so I hope that that clarifies things for others as well.
#35 fredk
August 3, 2007

Hmmm, I think I may have screwed up my analysis a bit. Monty will choose Door 1 25% of the time when Door 3 is the winner and 50% of the time when Door 2 is the winner, so Monty choosing Door 1 will make Door 2 twice as likely as Door 3 to be the winner, not 3 times more likely as I said in my previous post.
#36 FhnuZoag
August 3, 2007

Jason:

The idea of working with odds is to do away with the neccessity of rescaling probabilities so that they add up to 1.

For example, an odds vector of 1,1,1 represents 3 possibilities, each with equal probability. Meanwhile, 0,1,2 represents 3 with the first impossible, and the third having twice the probability of the second. In probabilities, we have then 0,0.33..,0.66…

Why work with odds? Because if we consider the ratio of any two conditional probabilities we get by application of Bayes’ rule:

P(A|C)/P(B|C)=[P(C|A)/P(C|B)]*[P(A)/P(B)]

Since P(C) in the nominator and denominator cancels out. Looking at this expression, we have that the ratio between any two probabilities A and B after we observe C is just the original ratios, multiplied by the ratio of the probability of observing C, supposing that A, or B were true. So, updating the odds, and so the probabilities, after an observation is transformed into a straightforward matter of multiplication.

The application of this to your problem is then to use a vector to represent the ratio between all the probabilities of the car being in each door, starting with 1,1…1 when no doors have been opened. (since it’s equally likely that the car is behind each door)

And then, after each new door is opened, we update this odds vector by a ‘likelihood’ vector where the i-th component is proportion to the probability of the observed door having been opened if the truth was that the car was actually hidden behind door number i.

Suppose k doors are unopened before the latest door was opened. For the door which was opened, the probability is 0 – since if the car was there, the door would not have been opened. For the door which was chosen, the probability is 1/(k-1) – since there would be k-1 candidates for goat-filled doors being opened, if the car was hidden behind the chosen door. For the remaining unopened doors, the probability is 1/(k-2) – since now TWO doors are exempt from being opened, so the actual observation is a random choice from k-2 possibilities.

Since the odds vector is just a representation of ratios, we can multiply the whole likelihood vector by k-1 for an updating vector of the form

1, 0, (k-1)/(k-2), (k-1)/(k-2)…

And we just update by multiplying componentwise.

The important insight is that (k-1)/(k-2), the factor by which unchosen, and unopened doors grow in probability relative to the chosen door is based only on k – that is, how far into the game you are – and not on things like which door opened or which door was chosen. Because our final objective is to maximise the ratio of probabilities between the doors that remain, the idea of stacking the not-enbiggening multiplier on the same door by choosing the same door again and again provides the proof required.
#37 divalent
August 3, 2007

Further thoughts, not intended to make your head explode:

Another thing to point out is that these probabilities are observer dependent. Imagine a 100-door game played simultaneously by two contestants (C1 and C2); C1 initially chose door 1 (D1), C2 chose D2. Neither is aware of the other (or the other’s choices), but Monty and the audience can observe all (but only Monty knows where the car is). Both C1 and C2 play the “hold-em” strategy down to four doors remaining, and we consider the probabilities for each remaining door from the perspective of C1, C2, and the audience.

C1 and C2 each evaluate their own door as having a 0.01 probability, and the remaining 3 each at 0.33. the audience would say D1+D2 each have a probability of .01, with the other two at 0.49 each. C1 has no reason to believe D2 is any different from the other doors he doesn’t own, so he distributes the “somewhere else” probability over 3 other doors. (That is, all the surviving other doors get credit for surviving the 1st to the 96th round of cuts: doing so makes it more likely they have the car). OTOH, the audience knows Monty would not (at this point) have opened either D1 or D2, and thus gives no credit to those doors for surviving the initial rounds; their probability of having the car remains locked, and so they distribute the “somewhere else” probability to fewer remainders.

If on the next round both C1 and C2 hold and D4 is shown to be a goat, C1 and C2 both would correctly estimate they have (at this point), a 0.495 probability of getting a car by chosing another door and holding to the end. However, C3 (who Monty just pulled out the audience and allowed to chose any door he wants) would have a 0.98 probability of getting a car if he chose D3 and held to the end.
#38 Kurt
August 3, 2007

I’ve been sitting here trying to formulate a rebuttal and… I realized I was wrong. Jason (and schep), I concede the point that the probabilities can indeed decrease. I’m an idiot (crawls under rock).

Damn you, Jason!

On the other hand, I did score a 32 on this!
#39 JimV
August 3, 2007

For brevity’s sake, I’ll just say that I like and agree with all the comments after my last one (up until now, 9 AM EDT; can’t predict future ones), particularly the vector of odds-ratios bit.

When my head hit the pillow again, I realized that that the restricted-choice viewpoint also answers your second issue, at least intuitively. Since every time Monty opens a door, the odds of the door you’ve chosen go down and the odds of the remaining doors go up, it makes sense that you should stick to the same door until there are only two left, so its odds are as small as possible and the remaining door’s odds are as high as possible. I didn’t feel like getting up again, though.
#40 divalent
August 3, 2007

JImV: “Since every time Monty opens a door, the odds of the door you’ve chosen go down …”

That’s not true.
#41 Jim
August 3, 2007

Jason:
It’s too bad that you couldn’t make it to the Yearly KOS convention this year, but it looks like Science Blogs (Sb) was represented well. I hope Bill O’Reilly didn’t scare you off.
http://www.dailykos.com/storyonly/2007/8/3/6333/14786
#42 Saul
August 3, 2007

Ruth,

I think that you’re tacitly assuming that the unselected doors must be identical. In that case, you’re right; we learn nothing about the selected door when Monty open one of the others, since we already knew he could do that. However, if the doors aren’t identical, this isn’t so.

Suppose you are a loyal fan of the show and have noticed that there’s an 80% chance that the car is behind door 3, and that the chances for doors 1 and 2 are both 10%. Now you get to be on the show, and you choose door 1, expecting that Monty will open door 2 and you will switch. But no! Monty opens door 3. Now, if your estimate of the probability of the car’s being behind door 1 doesn’t change, you must conclude that there’s a 90% chance that it’s behind door 2. I think you’ll agree that that seems unreasonably large.

You can use Bayes Rule to work out the probability, or you can imagine that the experiment is run 100 times. 80 times the car is behind door 3, 10 times it’s behind door 2, and 10 ten times it’s behind door 1. Now, we know it wasn’t behind door 3, and in the 10 cases where it’s behind door 2, Monty has no choice but to open door 3. In 5 of the 10 cases where it’s behind door 1, Monty opens door 2, (didn’t happen), and in the other 5, he opens door 3. Thus, there are 10 cases where he opens door 3 and it’s behind door 2, but only 5 where it’s behind door 1 and he opens door 3. A priori, these cases are equally likely, so the probability that it’s behind door 1 is 5/15 = 1/3.

The thing is, once you start switching, the unselected doors are no longer identical, because they have been “in contention” as you put it so appositely, at different times.

Note that we get the most information when Monty opens a door we thought was highly likely to conceal the car. When he shows us a goat behind an unlikely door, we don’t learn much, because we didn’t think the car was there anyway. It’s dumb to switch the first time because the door we select the first round has the lowest probability after Monty opens the first door. By switching, we lay ourselves open to the possibility that Monty will open that door, so we will learn less than we could have.

Let me say that I’m only using the term “information” in an intuitive sense. I am not suggesting that the constestant’s best strategy in general, is to minimize entropy (although I am not suggesting the contrary, either).
#43 anon
August 3, 2007

I’ll write up schep’s proof. It’s easier to think of it as you wanting to choose a goat, since then you don’t switch at the last step. In this case, the claim is that if the probabilities are p_1, p_2, …, p_n, then the probability of winning is 1 – p_i for an i with p_i = min p_j and this can be achieved only by staying on door i the entire time. Proof goes by induction with the n=2 case being clear.

Suppose we choose door i. Then straightforward calculations show that for j != i,

P(D_k | M_j) = p_k/(n-2) / ( sum_l{ p_l/(n-2) } + p_i/(n-1) ) for k != i,j, and
P(D_i | M_j) = p_i/(n-1) / ( sum_l{ p_l/(n-2) } + p_i/(n-1) )

where the sums are over l != i,j. We need to analyze our probability of winning, which is given by

sum_j{ P(M_j) * probability of winning with probabilities P(D_k | M_j) }
= sum_j{ P(M_j) * ( 1 – min_k P(D_k | M_j ) }

according to the induction hypothesis. Continuing, we get:

= sum_j{ sum_l{ p_l/(n-2) } + p_i/(n-1) – min{ p_i/(n-1) or p_k/(n-2)’s } }
= sum_j{ ( 1 – p_i – p_j )/(n-2) + p_i/(n-1) – min{ p_i/(n-1) or p_k/(n-2)’s } }
= 1 – sum_j min{ p_i/(n-1) or p_k/(n-2)’s } }

after skipping some algebra. We want to choose i such that this value is maximized, which means that we want to subtract as little as we can–meaning that we want to take i such that p_i is a minimum, since it’s divided by a larger number. Thus we get

= 1 – p_i

and the strategy is optimal (up to there being more than one minimum p_i), since after the first step P(D_i | M_j) is the unique minimal P(D_k | M_j).
#44 FhnuZoag
August 3, 2007

divalent:

The trick with odds is that only *relative* odds matter. Multiplication by a non-zero scalar at any step does not change what is being encoded in the system. i.e. 0,0.5,1 is the same as 0,1,2, since both show a situation with 3 possibilities with the third twice as likely as the second.

It is possible (and perhaps more intuitive than my example), to set the P(C|x_i) vector by multiplying with k-2 so that all the unchosen, unopened doors have their components stay the same while the chosen door’s odds decrease.

We can manipulate things in this way because unlike with probabilities, we are ommitting the final step where we divide the vector by the sum of all its components. This, as people have found, can lead to the chosen door increasing in probability because the removal of one door leads to a proportionate increase in probability of all the remaining possibilities.
#45 divalent
August 3, 2007

FhnuZoag,

Sorry, but for this problem, you are not correct.

At any time, you can calculate the probability of the door you own, and a “somewhere else” probability that is distributed among the other remaining doors. When Monty opens one of those other doors, it reduces the number of doors that are included in that pool, so the probability of having a car for the doors in that (now 1 smaller) pool goes up (because that probability is distributed over fewer doors). Monty will never open the door you currently own, so the fact that he did not open your door does not reveal any information to you about whether or not your door has a car. So the probability for that door does not change.
#46 JimV
August 4, 2007

(I really have to start doing my thinking on this thread earlier in the day – but there is so much else to do then, so here are some more late night thoughts.)

In my first comment, way above, I showed that for five doors, guessing door 1 and having door 2 opened, that if we start with an initial distibution of probabilities (p,1-4p,p,p,p) (for P(D1),P(2),…,P(D5), then as a result of opening door 2, P(D1|M2) becomes 1/5. That result can be generalized to N doors, i.e., P(D1|M2) = 1/N – regardless of the inital value of p = P(D1)=P(3)=P(D4)=…=P(DN). So if p was greater than 1/N to begin with, it decreases, if it was less it increases, and if it was 1/N to begin with, it stays the same.

(I mistakenly implied it always decreases absolutely in my last comment, having just done the case where p=1/4 goes to p=1/5. I should have said it decreases relative to the remaining doors.)

If I rearrange the door numbers in Jason’s step 2 caluculation, I get a four-door case of the same sort, where p=4/15 (using Jason’s doors 3,1,4,5 as my door’s 1,2,3,4). So after opening door “2″, the 4/15 reduces to 1/N = 1/4.

I haven’t thought about the general case (p1,p2,p3,…), but I’ll make the general claim that due to restricted choice, opening any door always reduces the relative odds of the door which was guessed versus the other remaining doors.
#47 FhnuZoag
August 4, 2007

divalent:

Again, I am working with odds, not probability. We are not arguing about absolute changes in probability, but relative changes in probability of the chosen door compared to everything else.

The rescaling issue causes weirdness with probability – and your assertion that the probability of the chosen door does not change is not correct. The problem with your argument is that there may be cases where the probability of the car is not evenly distributed amongst the unchosen doors. In this case, the opening of an unusually likely door will also increase the probability that the car is in the chosen door, and not in any of the doors up for contention at all.

In terms of odds, consider 2,2,1 which in probability is 0.4,0.4,0.2. Now, choose the first door. If the second door is opened, our new odds are 2,0,2. (Check this if you wish) This leads to probabilities of 0.5,0,0.5.
#48 FhnuZoag
August 4, 2007

It might be intuitive to think about it in a concrete example.

I flip a coin, and say that you win on heads, or side. Now, I tell you that the coin didn’t land on heads. Would it really be fair to suppose that the probability of it landing on heads is now redistributed entirely to the side-possibility, and that we now have the case that the coin is more likely to land on side than it is on tails?
#49 AJS
August 4, 2007

The point is, the probability that the door you originally picked is the winning one is 1/N. It’s N-1 times more probable that that door conceals a goat than a car. (If you change doors, it’s actually quite likely that Monty will open the door you first chose at some later stage during the game.)

If you keep changing your mind in the meantime, the maths becomes horrendously complicated. You can’t just consider each successive round as a new game with fewer doors, each with an equal probability of winning, because there is some memory effect going on: the fact of a door having been opened redistributed the winning-probabilities of the remaining doors unequally. {The probability of your door being the winner is still 1/N. The probability of each of the N-2 remaining doors being the winner is now (1 – 1/N) / (N – 2)
= (N – 1) / N (N – 2). This obviously > 1/N, for all N > 2.}

If you stick with your first choice of door until the very last minute, Monty keeps eliminating doors one at a time until there are just two doors remaining — one of which has a car behind it. And since there were more goats than cars in the first place when you chose your door, the greater probability is that the door you originally chose is concealing a goat.

The probability that your door leads to the car is 1/N. The probability that the only remaining door leads to the car is therefore 1 – 1/N. The more doors, the better the chances.

To put it another way; the only way you can win the car by sticking with your choice right to the bitter end is if you got it right in the first place. But in fact, you’re more likely to have got it wrong on the first guess. In the limiting case, when there are just two doors left, then the probability of the other door being the winner is equal to the probability of your door being the loser. If you change your mind mid-game and pick the winning door, then the only way you can win is to stick with that door (or switch away and back). And the probability of you switching to the winning door actually increases as more losing doors are eliminated.

Therefore, the absolute best winning strategy must be to switch doors at the very last opportunity.
#50 JimV
August 4, 2007

I worked through the general case in bed (to the great detriment of my going to sleep), and verified that for the general case of (p1,p2,…,pn) (being the prior-determined probabilities that door 1 through n is the correct door), that after you guess door 1 and Monty opens door 2, the ratio of probabilities p1/pi (where i = 3 to n) changes to [(N-2)/(N-1)]*(p1/pi). As a check, this occurs in FhunZoag’s example just above (posted at 3:12 AM – couldn’t get to sleep either, or different time zone?)

The reason for the (N-2)/(N-1) factor is “restricted choice”, i.e., Monty can choose any of N-1 doors in the D1 case, but only N-2 doors for the Di case. For those who don’t like Bayesian analysis, it is easy to run a “Monty” Carlo simulation in your head. Do pj*M trials for each possibility Dj, where j = 1, 3, 4, …,n. For D1, the results (which door Monty opens) are distributed uniformly over N-1 possible choices, so door 2 gets picked p1*M/(N-1). For Di, door 2 gets picked pi*M/(N-2) times. Divide the door-2 results for each Dj by the total p1*M/(N-1)+p3*M/(N-2)+…+pn*M/(N-2) to get the new estimate for P(Dj|M2). The denominator is the same in all cases, and the M’s in the numerators also cancel, so the ratio P(D1|M2)/P(Di|M2) is [p1/(N-1)]/[pi/(N-2)].

(I think a bunch of us are saying the same thing – this is just my way of saying it.)
#51 Joseph
August 4, 2007

I put a very verbose version of my corrected proof of optimal strategy on my blog here:

http://vacuumenergy.blogspot.com/2007/08/n-door-monty-hall-problem.html
#52 schep
August 4, 2007

Okay, here we go.
http://www.msu.edu/~schepler/monty.pdf
If you prefer, you can substitue .ps for the suffix (or even .tex if you want to do some editing).
#53 schep
August 4, 2007

Joseph, your proof assumes that the probability the chosen door conceals the car remains the same during each round. Unfortunately, that’s not justified if the other doors don’t all have equal probability.

I meant to note that there are plenty of similarities between what I’ve done and some of the stuff FhnuZoag posted about vectors and ratios of probabilities. I suspect his (her?) proof is also correct, though I haven’t looked hard at the details.
#54 divalent
August 4, 2007

Major mea culpa on my part. Turns out the mathematician is correct, and I was wrong.

I spent about 2 hours working out all scenarios, and, gosh dang it, the probability does drop, from 4/15 (0.26666) to 1/4 (0.25) when Monty shows a goat behind door #1 on round 2.

I worked it out by determining all possible ways the game could flow in round 1 and 2 that are consistent with the actual outcome, and then determining how likely that outcome is if the car was behind either door 3, 4 or 5.

The probability that the actual events in round 1 and 2 (show goat in #2, then show goat in #1) would occur if the car was behind door #3 was only 1/9. If the car was behind either doors 4 or 5, the probability is 1/6 for each.

So (1/9) / (1/9 + 1/6 + 1/6) = 1/4 ! Exactly as Jason calculated.

From an intuitive sense, why? I think it is because learning that door 1 had a goat gives you information that you didn’t have in calculating the probabilities after round 1, information you would never have if the player used the hold-em strategy. Consider the significance of Monty opening door 2 in the first round in terms of the probability that door 3 had the car: if Door 1 had the car, then Monty had a choice of 4 goat containing doors, so Door 3 survived a 25% chance of being eliminated, but if door 1 had a goat, Monty only had 3 doors to select from and so door 3 survived a 33% chance of being eliminated (if it had a goat). Surviving a more selective cut enhances the likelihood that a door actually survived because it had the car. The specific knowledge that door 1 had a goat tells us that door 3 (and 4 and 5) survived a more selective cut in round 1.

The fact that the probability drop to 1/4 suggests a possibility that I am unable to evaluate at this time (I’m visiting relatives), but perhaps makes the game appear (at least for one round) like one where the player’s choice is at risk for being exposed as having a goat along with all the others (presumably, monty won’t let you switch if your door is opened revealing a goat). In that game, I think a hold-em strategy does not lock in the probability on your chosen door, and increases along with the others. If my guess is correct (and, sheeze, I seemed to have been way off the mark recently in this game, so i can’t be sure!), it would suggest a lower limit to how much the probability can drop when your initial choice (abandoned at the first opportunity) is shown to be a goat: only to the equivalent probability when to starting with N-1 doors. And that probability will be higher than your initial choice in the N-door game. (Abandoning later in the game probably won’t do as well as this).

Finally, I will apologize in advance if this explanation is has been presented by others above. I didn’t read them too closely since I’m out of town.
#55 JimV
August 5, 2007

I think we are all on the same page now, so it may be an appropriate place to cite my favorite Einstein quote: “All mathematicians make mistakes; good mathematicians find them.” (I like to apply it to all other fields as well.) (And the fact that he doesn’t give a time limit means there is always hope for me.)

If anyone doesn’t know and cares, here is the condition under which the probability of the door you have chosen doesn’t change after Monty opens another door. Let p be the initial probability of the door you hae selected, and q be the initial probability of the door Monty opens. Then if and only if q = (1-p)/(N-1), p stays the same (where N is the number of doors).

In other words, q must be exactly equal to the average probability of all the doors except the one you have selected. At the default starting assumption for which all probabilities are 1/N, any door Monty opens meets the condition, and p is unchanged at the start of round 2. As long as you stick with the same door, all the possible q’s stay equal, and p stays the same. However, if you switch doors at any round, there is no door which Monty could open which will meet the condition and leave your new p unchanged.
#56 JimV
August 6, 2007

It ocurred to me (late last night again), that I never really answered Jason’s second question:

Outperforming the switch at the last minute strategy requires that one of those doors have probability smaller than 1/n. Now, every door starts with that probability. But how do we know that we can not drive the probability down below that level with some clever sequence of switches during the game?

Nor have I offered a proof of the optimal strategy, as others have done. Here is a brief outline of how I would do both.

To prove general cases of N doors, induction is the standard method – but schep has already given an induction proof, so I can’t use that without being a copy-cat. The odds-vector concept sounds like a neat method, but FhnuZoag has copyrighted it, so that’s out. The remaining method I could think of was to prove directly that once all prior probabilities (which I’ll call pi’s) are greater than 1/N, at some round where the remaining number of doors is M, then the resulting post-door-opening probabilities (which I’ll call qi’s) must also be greater than 1/N, no matter which door Monty opens.

Let’s say there are N doors at the start of the game, with pi = 1/N for all i = 1 to N. We proceed to the round with M remaining doors (for N>M>2) following the strategy of always chosing door 1, so p1 = 1/N, and pi = (1-1/N)/(M-1) for i=2 to M. Now we screw up, by selecting door 2 instead of 1.

If Monty opens door 1, as seen before we get q2=1/M (>1/N) and the remaining qi’s > q2 (by the factor (M-1)/(M-2)).

If Monty opens one of doors 3 through N, then:

q1 = [(M-1)^2]/[(M-1)^2 + (N-1)*(M^2 -3*M +1)]

q2 = (M-2)*(N-1)/[same denominator]

and all the other qi’s = q2*(M-1)/(M-2)

All these numbers are > 1/N, for N>M>2 – so departing from the alleged optimal strategy will put us in the condition that all the remaining door probabilities are >1/N

Now we look at the general case for M doors, starting with min{pi} > 1/N

To try to improve the situation, our best choice for the next round is to chose the door with the minimum probability; any other choice will produce a larger minimum probability at that next round (proof skipped unless challenged). Let p1 be the minimum (repainting the door numbers if necessary). Monty opens door 2 (again repainting the door numbers if he picked a different door). Door 1 now has probability:

q1 = [1/(M-1)]*p1/P(M2), where

P(M2) = [1/(M-1)]*p1 + [1/(M-2)]*(p3 + p4 + … + pM)

One can show that

[1/(M-1)]*(1/N) + (N-1)/[N*(M-1)] > P(M2)

Very briefly, note that p3+..+pM = 1-p1-p2, and the maximum case is for p1 minimum and p2 second-smallest, since shifting probability to the term with the larger factor increases the result; then if p2 = min(p2 through pM), the average of p3 through pM is less than (1 – 1/N)/(M-1).

Therefore,

P(D1|M2) > [1/(M-1)]*(1/N) / [1/(M-1)]*(1/N) + (N-1)/[N*(M-1)] = 1/N

(Hope I didn’t mix up any M’s and N’s – I originally did this for M doors at the start and N doors at the current round.)
#57 Bunjo
August 6, 2007

It took me a couple of sessions to understand the Monty Hall problem and why the best strategy is to hold one door until the final choice, then swap. I coded a bit of rough and ready BASIC to check this by a Monte Carlo method.

Although my code could do with a thorough validation, it did confirm the n-1/n probability for the ‘hold and swap’ strategy. I tried it for various numbers of doors and iterations. A hundred doors in a million games took a few minutes but the outcome was 989994 cars and 10006 goats.

Changing the ‘held’ door halfway through the game, or holding a different random door at each choice point, progressively degraded the success of the hold and swap strategy. This struck me as reasonable, although I didn’t try to calculate the results mathmatically.

It also struck me that the strategy was not about learning as much info as possible from Monty, but minimising the liklihood of your held door concealing the car (so you can finally swap). In a 10 door game the first held door has a 1 in 10 chance of concealing the car. If you hold another door next time, this has a 1 in 9 chance of concealing the car as 1 goat has been revealed, and so on. I am not certain how these liklihoods combine, I’ll have to give this some more thought.

Still, quite nice to break out the BASIC once again.
#58 Spike
August 6, 2007

OK. But what about the variation used on that Howie Mandel show, where your goal is to find the $1 million and they have actuaries offering you money to quit looking?

Is there a mental shortcut one could develop to optimize one’s chances in that situation?
#59 JimV
August 7, 2007

Whew, looks like nobody has yet read my August 6, 10:51 AM comment all the way through (don’t blame you it’s long). Good, because it ends in a mistake. I got confused about which way the inequality points. All I can show is that

P(D1|M2) &lt p1 for p2 &lt [average of p3 through pM]

P(D1|M2) = p1 for p2 = [average of p3 through pM]

P(D1,M2) > p1 for p2 > [average of p3 through pM]

This doesn’t prove the general proposition that P(D1|M2) > 1/N; p1 can still get smaller even when all pi’s > 1/N, and how much smaller it can get depends on the distribution of the rest of the pi’s, which depend on prior decisions. It looks like induction is the best way to go.
#60 AJS
August 9, 2007
There’s not a lot of point putting any numbers in.

There are two ways you can win this game. Either you can pick the winning door and stick with it; or you can pick a non-winning door and change your mind to the winning door.

Now,
1. The more doors there are for you to choose between, the less likely you are to pick the winning one.
2. You are always more likely to choose a non-winning door than the winning door at the beginning of the game.
3. The later in the game you change your mind, the more likely you are to pick the winning door.
Given which, it’s reasonable to suppose that the optimum strategy is always to stick with your first choice, right till there is only one other door remaining ….. because if the winner isn’t the door you picked to begin with, there’s only one door it can possibly be. If you switch doors in mid-game, then your new door is always more likely than your original door to be the winning one ….. but if there are still many doors remaining, then it’s not likely enough to be the winner.
#61 Uri Kalish
August 16, 2007

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

National Geographic SocietyIn partnership with

Advertisement

Science Blogs

Search National Geographic

The Progressive Monty Hall Problem, Again

Comments

Search This Blog

Recent Posts

This is Forty

Good Theology?

It Has Always Been Thus…

Brief Blog Break

The Evolution of the the Chess Set

Recent Comments

Archives

Blogroll

Meta

National Geographic SocietyIn partnership with

Advertisement

Science Blogs

Search National Geographic

The Progressive Monty Hall Problem, Again

Comments

Search This Blog

Subscribe

Recent Posts

This is Forty

Good Theology?

It Has Always Been Thus…

Brief Blog Break

The Evolution of the the Chess Set

Recent Comments

Archives

Blogroll

Meta