Let's Make a Deal

[Nev]

Righty. Those of you who already know the answer to this one (I'm willing to bet $200 Kup knows about it), please keep quiet until Monday. I'm going to keep this poll running for a few days - the main benefit I found for me when I was first exposed to this in high school was in thinking about it, not just being told the answer.

So. There used to be a game show on TV called Let's Make a Deal. In the final round, you'd be shown three doors, behind one of which was a fantabulomatic new car, and behind two of which were arguably less fantabulomatic things that were not new cars. (Usually these would be animals of the goat variety).

First, Monty Hall, the host, would tell you to pick a door, and you would.

Here's the tricky part. He would then open one of the doors that you did not choose and reveal a goat. You were then offered the chance to switch to the remaining door that you did not originally choose. You would end up being given whatever object was behind your final choice.

Assuming that you want the car (I don't think anyone who won the car was ever hoping for a goat instead, but one never knows), is it better to stick with your original choice or switch to the new door - or does it matter?

If you know the answer, PLEASE do not blather it all over the thread, at least not until Monday when the poll will expire. At that point I (or someone else) can give the correct answer. I absolutely loved this problem when I was told about it in school. This problem has a proper name, but I'd rather no one give that until Monday either because then people would be able to look up the answer more easily.

[Kupek]

I am familiar with this, and oddly enough, we discussed it last night on the way to a movie. I'm not going to give it away, but I will ask a clarification question which changes things considerabley.

Does the host <i>have</i> to open a door?

[Flip]

I dont KNOW the answer, so i assume i can post my logic in my decision without you having a hissy fit:

If your only conclusions are car or goat and 2 out of the 3 doors have goats then by only picking one door the host will always have the opportunity to show you a goat; leaving left hidden a car and a goat. It seems switching or sticking would make no difference as now it is a 50/50 shot.

This seems too easy so i think i am wrong. Kupeks question doesnt really add another layer since no matter what you picked he could show you a goat. If the host decided to now show you anything you would still have no idea if your original pick was correct. He isnt opening a door because there are 2 cars left, for instance.

[Tortolia]

Ah, yes. The Let's Make a Deal question.

I forget the answer, but there were some long discussions on The Straight Dope about it.

[Nev]

I am familiar with this, and oddly enough, we discussed it last night on the way to a movie. I'm not going to give it away, but I will ask a clarification question which changes things considerabley.

Does the host <i>have</i> to open a door?

You mean, once you've made your initial choice? I'm not sure I understand.

For now, yes, the host has to open the door with the goat before you decide whether or not to switch. I may see what you're getting at, though.

[SineSwiper]

We discussed this last year, I believe. I'll find the thread Monday. Honestly, I still do not understand the logic and mathematics of the solution, and I still dispute it.

[Nev]

If you doubt it, write a program to simulate it. Come on, you're a decent enough programmer to do that at least.

[Flip]

I yahoo'ed the answer and i guess it makes sense, interesting.

[Kupek]

You mean, once you've made your initial choice? I'm not sure I understand.

For now, yes, the host has to open the door with the goat before you decide whether or not to switch. I may see what you're getting at, though.

Yes, that's what I'm getting at. If the host is allowed to not show you a door, the probablitiies change.

I actually plan on writing a simulation, because I want to explore the various possibilities of host behavior.

[Nev]

Now THAT is going to be an interesting explanation. But I'll wait until Monday.

[Don]

If the host doesn't open a door no additional information is revealed and the probability does not change from 1/3.

If you just write out all the possible combinations of prize/goats the answer is actually pretty obvious.

[Garford]

Bleh, I actually made a sim for this since I was bored:

Possible combinations are:

C, G, G
G, C, G
G, G, C

Rest = Monday

[Blotus]

I'm guessing the big shocker is that altering your choice does make a difference, despite the obvious one-out-of-two chance that remains. Don't mind-fuck me!

[Nev]

Bleh, I actually made a sim for this since I was bored:

Possible combinations are:

C, G, G
G, C, G
G, G, C

Rest = Monday

You don't really need to order the combinations like that. But I'll explain on Monday.

[Don]

1 out of 2 is wrong too.

[SineSwiper]

Maybe I'm jumping in a bit early, but I think everybody already remembers this problem from last year anyway. Taking Garford's method, you could do it this way:

G = revealed goat
c = prize
g = locked goat

At first, you have one of these combinations:

cgg
gcg
ggc

So, that's a 33% chance. After something is revealed, you have these choices:

cGg
cgG
Gcg
gcG
Ggc
gGc

Okay, it still appears to be a 33% chance, but we can break it down. Now, let's say that you picked door number #2 on the first try and he reveals that door #1 is a goat; that leaves you with these choices:

Gcg
Ggc

Now, it's a 50% chance. HOWEVER, changing your answer does NOT increase your odds! When the host revealed one of the doors, it increased your odds automatically, whether you stayed with the one or not. Just look at the two possibilities: if you stay with the choice, you have a 50% chance of winning. If you don't stay with the choice, you have a 50% chance of winning.

Now, of course, host behavior has an impact on the choices. We are assuming that the host is not going to change his behavior, depending on if the first choice was right or not. What if he revealed the first choice that the person picked if it was right or wrong?

Let's assume that the game show is trying to make money, and he would reveal the choice if it was wrong. In that case, it would be basically a 100% chance that your choice is right if you STAYED with your choice, and he revealed one of the doors. (Of course, the first choice is 33%, but if he reveals a door, stay with your choice, and you know you've got it.) The opposite is true if he reveals the prize on the first try. (IOW, switch if he reveals.)

However, those kind of behaviors are dangerous to a game show. The pattern is so easy that most people will figure it out. (Obviously, if you have a 100% chance of something, it's not a good way to play it.) Therefore, my answer still stands: it doesn't matter if you change or not.

[Don]

If the door is revealed and you do not change your mind, nothing is gained. There is always at least 1 door that contains a goat regardless of your first choice.

The easier way to think is this:

If your initial choice was right, then switching definitely result in choosing the wrong door.

If your initial choice was wrong, there is only one other wrong choice possible and by the rules we are given, the host has to reveal the other wrong choice. Therefore switching will always lead you to getting the right choice if your initial choice was wrong.

The chance that your initial choice is right is 1/3.

So switching increases the odd of being right to 2/3.

[SineSwiper]

If your initial choice was wrong, there is only one other wrong choice possible and by the rules we are given, the host has to reveal the other wrong choice. Therefore switching will always lead you to getting the right choice if your initial choice was wrong.

What? That doesn't even make sense. Because you're down to two doors, the host is going to reveal the choices no matter what you choose. Next time, I demand logical and mathematical PROOF with any counterarguments. Everything you said was totally illogical.

[Don]

There are 3 possible distribution for the 3 doors, P = prize, G = goat

PGG
GPG
GGP

The PGG case:

If you pick P then changing leads to the wrong result regardless of which door is revealed.

If you picked G1, by defintiion G2 has to be revealed because he can't open the P door. So the only other door left is the P door and switching is beneficial.

If you picked G2, by definition G1 has to be revealed because P cannot be revealed. Switching is beneficial.

The GPG and GGP case are isomorphic to the first case. It should be readily obvious that had you picked the wrong door to start, the only door that can be revealed the other wrong door and the only remaining door is the correct one.

Switching leads to 2/3 chance of success.

[Kupek]

I wrote a simulation last night: http://www.cs.wm.edu/~scotts/monty_hall.cpp

I have comments in the code. If you understand the simulation, then you'll understand why it works out the way it does. Notice that my simulation scales to any number of doors greater than 3. Running the simulation with more doors skews the probability even higher that switching is better.

The easiest way to think about it is with a large number of doors, say 1000. Let's say you pick door <i>x</i> at random. There is a 1/1000 chance of the car being behind door <i>x</i>. Monty then eliminates all doors but yours and one other - that is, he opens 998 doors and they all have goats.

What does this do to the probablility that the car is behind door <i>x</i>? Nothing. When you chose it, you had 1000 choices, so it's still 1/1000. Hence the remaining door must have a 999/1000 chance of having the car, and you're better off picking it.

Why isn't it 50/50? Because when you chose the door, you chose it <i>randomly out of 1000</i>. The fact that other doors are now open doesn't change that the fact it is is a 1 out of 1000 door. Remember that Monty does not open doors at random; he has to open doors that are not your door and are not where the car is. He's systematically eliminating most of the other choices.

This all changes if the host can choose not to open doors because he can adopt a policy of only offering a choice when the contestant picks correctly the first time. In that case, the best thing to do would be to see if there's a pattern of behavior between past contestant guesses and whether or not the host gives the choice.

[Don]

If the host can choose to open doors selectively based on what you choose, the optimal strategy would be to randomly pick a door out of what's left because random is provably uncounterable, and if he opens any door at all it increases the chance of selecting correctly (from 1/X to 1/X-# of doors open). This of course assumes the host can't move the car after you choose a door, but in that case you will never be able to win regardless of what strategy you have.

[SineSwiper]

You assume that it's a three choice game throughout. By revealing one of the wrong choices, the rules change, and it's now a two-choice game. Saying that the odds are anything out of 3 are invalid. The first choice you made didn't matter, because there are TWO goats. If you picked one goat, he would reveal the other one. If you picked the prize, he could reveal any of the goats.

Let's take your PGG case. We can easily map out all of the possible combinations:

pGg - P is picked, G1 is revealed, 50/50 chance on either
pgG - P is picked, G2 is revealed, 50/50 chance on either
pgG - G1 is picked, G2 is revealed, 50/50 chance on either
pGg - G2 is picked, G1 is revealed, 50/50 chance on either

No matter what, you are left with ONE prize and ONE goat to choose from. The first choice DOES NOT MATTER! The first choice does not give you a prize. It does not affect what the second stage is going to be, because you will ALWAYS end up with ONE prize and ONE goat as your final choice.

The example logic you showed is erroneous statistical analysis. You are taking the first choice and trying to pair it up with the second choice, without even factoring in the chances on the second choice.

It should be readily obvious that had you picked the wrong door to start, the only door that can be revealed the other wrong door and the only remaining door is the correct one.

Again, this is wrong. Both doors are revealed after the second choice, or they are revealed one at a time. It doesn't matter, because it's not like you get a third choice after revealing the second door. Choicing one door or the other doesn't affect this behavior in any way.

[Kupek]

If the host can choose to open doors selectively based on what you choose, the optimal strategy would be to randomly pick a door out of what's left because random is provably uncounterable, and if he opens any door at all it increases the chance of selecting correctly (from 1/X to 1/X-# of doors open).

Not necessarily. If we had a large data set, and we found, say, that when Monty offered the choice in the past, 95% of the time it was when the contestant made the right choice, then you're probably best off sticking with your original door. This is leveraging past behavior to predict future behavior.

If you can't look at past behavior, then your rationale applies.

[Don]

pGg - P is picked, G1 is revealed, 50/50 chance on either
pgG - P is picked, G2 is revealed, 50/50 chance on either
pgG - G1 is picked, G2 is revealed, 50/50 chance on either
pGg - G2 is picked, G1 is revealed, 50/50 chance on either

Choice 1 & 2 represnts 1/3rd of all possibilities despite how you write it out like. Only 1/3rd of the time will you pick P.

If G1 or G2 is picked, the only door that can be revealed is G2 or G1 (depending on which you pick) and the only remaining door has to be P.

[Don]

If the host can choose to open doors selectively based on what you choose, the optimal strategy would be to randomly pick a door out of what's left because random is provably uncounterable, and if he opens any door at all it increases the chance of selecting correctly (from 1/X to 1/X-# of doors open).

Not necessarily. If we had a large data set, and we found, say, that when Monty offered the choice in the past, 95% of the time it was when the contestant made the right choice, then you're probably best off sticking with your original door. This is leveraging past behavior to predict future behavior.

If you can't look at past behavior, then your rationale applies.

If you consider the existence of an adverserial strategy that opens the door then it is never possible to predict the host's action regardless of how far you look back.

If the host is not adverserial, then past history applies. However, the only reason I can think of to selectively open doors would be to try to make you win less, so I think that's not a good assumption.

[SineSwiper]

The easiest way to think about it is with a large number of doors, say 1000. Let's say you pick door <i>x</i> at random. There is a 1/1000 chance of the car being behind door <i>x</i>. Monty then eliminates all doors but yours and one other - that is, he opens 998 doors and they all have goats.

What does this do to the probablility that the car is behind door <i>x</i>? Nothing. When you chose it, you had 1000 choices, so it's still 1/1000. Hence the remaining door must have a 999/1000 chance of having the car, and you're better off picking it.

Why isn't it 50/50? Because when you chose the door, you chose it <i>randomly out of 1000</i>. The fact that other doors are now open doesn't change that the fact it is is a 1 out of 1000 door. Remember that Monty does not open doors at random; he has to open doors that are not your door and are not where the car is. He's systematically eliminating most of the other choices.

Hmmm...for some reason, that actually makes sense. I was about to write my own program, but you beat me to it.

EDIT: There is also the idea that the host doesn't know what is behind the doors, either. He could pick a door at random that isn't yours. He basically has a 33% chance of picking the prize (based on if you picked the prize or not), and then you would automatically lose, because you didn't pick the prize.

[Kupek]

No matter what, you are left with ONE prize and ONE goat to choose from. The first choice DOES NOT MATTER!

The first choice does matter because the doors that were opened are a function of the door you chose. Put another way, you chosing a door and Monty leaving one of the doors open are <i>dependent</i> events.

The only way they could be independent is if Monty also chose a door at random, which would allow him to open the door you chose and the door with the car (if they are different doors). If he opens your door and there's a goat, then you should obviously switch. If he opens any door and it has the car, then you should obviously switch to that door. But if he opens a door that's not yours and reveals a goat, only then is each door equally likely to have the car.

[Don]

If the host opens door at random it's even more advantageous. 1/2 of the time he'll open a door with the goat. From this discussion, switching gives you 2/3 chance of winning. If he opens the door with the car, obviously you switch to that door instead awith a 100% chance of winning. The total chance of winnign is 1/2*(2/3) + 1/2 = 5/6.

Edit2: Saw what Kupek said and it make sense, so the final chance would be:

Host opens a door with a car (1/3), 100% chance to win (1/3)
Host opens a door with a goat (2/3). If it's your door (1/3rd) then you need to switch for (1/2). If it's any other door the chance is also (1/2).

So the chance is 1/3 + (2/3)*(1/2) = 2/3... which is same as the first scenario.

[SineSwiper]

No no no. If he picks the car, then you LOSE. You can't just switch to the car with it being opened. Here's some of the scernarios:

1. You pick the prize on the first choice, he picks a goat (he has to), then you stick with the prize, you win.
2. You pick the goat on the first choice, he picks the prize, you automatically lose.
3. You pick the goat, he picks the other goat, you stick with your goat, you lose
4. You pick the goat, he picks the other goat, you switch, you win.

[Nev]

Breaking from your game-show R&D session and returning to the classic Monty Hall problem for a bit...

I usually think of it as the "probability field" of the door you picked, and the "probability field" of the doors you didn't pick. In the classic example, the "pf" of the door you picked is one-third, and the "pf" of what you didn't pick is two-thirds. If you go up from there to the variable case, the "pf" of your initial choice is 1 divided by the total number of doors, and the "pf" of the rest is (number of doors - 1)/(number of doors). Shrodinger's Game Show!

In the classic case, you could also think of it as Monty giving you a choice between picking one door or picking the other two.

"Pick a door." "OK." "Now do you want what's behind the door you picked, or do you want the best choice out of what's behind the other two?" Wonder how many more people would have won the car if they'd put it that way? I bet they saved a bundle on cars through the years.

[Don]

No no no. If he picks the car, then you LOSE. You can't just switch to the car with it being opened. Here's some of the scernarios:

1. You pick the prize on the first choice, he picks a goat (he has to), then you stick with the prize, you win.
2. You pick the goat on the first choice, he picks the prize, you automatically lose.
3. You pick the goat, he picks the other goat, you stick with your goat, you lose
4. You pick the goat, he picks the other goat, you switch, you win.

So you mean the host can open a door contains the car, and you automatically lose because you can't switch to that one?

In that case you'd always lose if he opens the door with the car and it'd be advantageous for him to always open the door with the car (assuming you didn't pick right). You'd never have higher than a 1/3rd chance of winning, possibly lower if we consider mind games.

[Flip]

The easiest to understand explanation i've read is this...

There are ultimtaely two outcomes if you always switch:

1) You picked the right door first and switched to the wrong one
2) You picked the wrong door first and switched to the right one.

Since there is a 2/3 chance that you will pick the wrong door first, always switching will win 2/3 of the time.

Remember, when you pick the wrong door first (which will happen 2/3 of the time) Monty will reveal the other wrong door, which means switching will win it for you.

[Garford]

My sim data for 3 doors, should make it very obvious:

Possible results:

C, G, G
G, C, G
G, G, C

Door 1 selected first:

C(s), G, G
G(s), C, G
G(s), G, C

Host reaction:

C(s), G(h), G - Stay Win
G(s), C, G(h) - Switch Win
G(s), G(h), C - Switch Win

Stay 1/3, Switch 2/3

Door 2 selected first:

C, G(s), G
G, C(s), G
G, G(s), C

Host reaction:

C, G(s), G(h) - Switch Win
G(h), C(s), G - Stay Win
G(h), G(s), C - Switch Win

Stay 1/3, Switch 2/3

Door 3 selected first:

C, G, G(s)
G, C, G(s)
G, G, C(s)

Host reaction:

C, G(h), G(s) -Switch Win
G(h), C, G(s) - Swith Win
G(h), G, C(s) - Stay Win

Stay 1/3, Switch 2/3

Total: Stay 3/9, Switch 6/9