Today, at school, we considered the probability theory paradox called the Monty Hall problem:
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which he knows has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?
The world says that by seeing that goat, you learn that the probability of the car being behind door number 2 is 2/3 and Wikipedia has various explanations.
I claim it's 1/2. My first argument is that there is full symmetry between doors 1 and 2. How could you lower the probability of door 1 being the winning one by picking it? Nonsense.
For my second argument, let's treat it like the conditional probability that it is. All probabilities will be from your, the contestant 's, point of view.
At the start, we've got 3 equally probable situations: I'll denote them as CGG, GCG and GGC hoping it's clear enough.
Now the host opens a door. You see the goat: you gain information. Probabilities change. The probability of the door number 3 being the winning one falls down to 0.
So far, no difference from the "official" solutions. However, those maintain that while the probability of the car being behind the first door stays the same, the probability of it being behind the second one increases. Why the incoherence?
An important remark here: with the new information, we now have new events. We know that GGC didn't happen, so we have 3 events that assume ~GGC, namely:
- if the first door wins, it's CGG | ~GGC and P(CGG | ~GGC) is 1/2
- if the second door wins, it's GCG | ~GGC and P(GCG | ~GGC) is 1/2
- if the third door wins, it's GGC | ~GGC and P(GGC | ~GGC) is 0,
According to Wikipedia, "even Nobel physicists systematically give the wrong answer, and that they insist on it, and they are ready to berate in print those who propose the right answer". That's comforting: I may be wrong, but at least I have excellent company.
[UPDATE] After reading all the comments, I can see that I was wrong. Boy, is that problem counterintuitive! Thanks everyone for contributing! [/UPDATE]
Ok,
ReplyDeleteLet's scale up the problem. I present you with 52 playing cards, facing down, and you have to choose wich is the ace of hearts.
You choose, I pick up the remaining 51 cards.
No information is revealed, but i bet you think the ace is probably in my hands...)
Anyways, I show you 50 cards that are not the ace of hearts, and offer you to choose again between the one you were holding and the one facing down I'm left with.
Now tell me you are willing to always stick with your chosen card, do you want to play this game for money with me? :)
Your card's chances of being an ace of hearts didn't increase when I showed you some of the others.
I know you already read that, but again. Your argument would be valid I guess if the goat, or my 50 non-ace-of-hearts where revealed randomly, but their not. I'm deliberately showing you the loosing cards. This is not new information. You already knew 50 of my cards are not what you want just as you know the 2 doors you didn't choose contain only one prize.
Was I just trolled?
No, you weren't trolled, I genuinely took a strong interest in that problem yesterday. ;)
ReplyDeleteSo you're saying that if you're showing me a non-randomly chosen losing card, it's no new information. Yet, it increases the chance of one of the non-chosen non-shown cards being the winning one, so why doesn't it affect the chosen card?
no :)
ReplyDeleteit doesn't increase anything.
In the game with the playing cards (and I'm seriously asking if you want to play - say you put in $x i put in $10x and the ace of hearts holder takes everything*)
Now my final attempt at convincing you :)
So imagine we are playing the described card game. You know that within my 51 cards I can find 50 loosing cards, they're always there. You know that and I know that. So to cut the theatrics let's decide that will skip the part where I show you the loosing cards.
So now the game looks like this: you choose one card, then we agree that I'm holding 50 loosing cards and one that may or may not be the winning card, so despite the offer to change your mind you stick with your chosen card and think that you have 1/2 chance of holding the ace of hearts?
I thought it was trivial, but now I 'm not totally sure that it's always 2/3 vs 1/3 for _any_ "plausible" behaviour of the host.
ReplyDeleteIt depends on what the host does when you picked the door with a car first. If he opens a door with a goat, picked by a uniformly random choice independent of the door choice (the usual simplistic interpretation), then you forgot to "use" the information about the host's choice (and the probability space is larger), and I think everyone will agree that it's 2/3 vs 1/3.
Question (Rightmost-host): what if the host always opens the rightmost goat-door in the "you picked a car" case (and the player knows that)? Try answering that before going further :P
The answer: if I'm not wrong, it depends on the question. Wiki says 1/2 (Variants - the 5th, q=1). I think "change(i)" is still a better strategy than "stay(i)" (2/3 wins, proof below). In this case, a proof similar to yours fails when assuming that we can assume door #3 without loss of generality. The answer to the question "What is the probability we'll win, if we pick strategy X, and we know the host opened door #3?" is actually 1/2 for any strategy X in {stay(1),change(1),stay(2),change(2)} (strategies defined below). And that is my understanding of wikipedia's claim, that Righmost-Host gives 1/2. Note that X=stay(3) and X=change(3) make the answer undefined. Also note that Leftmost-Host limited to door #3 gives probability 1 for X=change(1), 0 for X=stay(1).
Strategy "stay(i)": pick the i-th door, then keep your choice.
Strategy "change(i)": pick the i-th door, then change your choice.
The proof I mentioned:
We fix a strategy, so our behaviour is deterministic. The host's behaviour is deterministic too.
So the outcome is determined by the uniformly random choice from (GGC,GCG,CGG). Fixing strategy "stay(1)" we get respectively (G,G,C). Fixing strategy "change(1)" gives outcomes (C,C,G). Same for stay(2), stay(3),... Q.E.D.
So if you agree that "choice(1)" is on of the best strategies for Rightmost-Host, the question arises - is it always one of the best, regardless of the host? We have to assume something - e.g. the host can't predict our behaviour by looking into our eyes.
My interpretation of the problem is "What strategy for a player with a random generator is best, if the host in the 'you picked a car' case chooses the goat-door to open by picking a random real r and applying a function f(r, player's first choice, car's position)->door. The player knows that function". We can say something unambiguous about the general case, i.e. when f is unknown to the player, if and only if there is a common best strategy for every function f (uniform-random, leftmost, or whatever). Conjecture: "change(1)" is such a strategy, giving 2/3 wins for any f. It's probably boring technical, but IMHO Wikipedia's statement is ambiguous about the host, so it's proofs are insufficient.
I think grzes explained it very well, but let me also make another note.
ReplyDeleteWhat *is* crucial for the whole problem and what *is not* present in your article is the *host algorithm*. The way host behaves in every situation. If he were opening random door, your argument would be valid. But he is not opening random door, as then he would sometimes show you the car.
Or, in yet another words. The sequence of events is not "1. start 2. host opens the door", but "1. start
2. the host learns where the car is. 3. the host learns the player choice 4. the host opens the door according to his algorithm"
Hi, I just popped in to say hello, great blog, congratulations!
ReplyDeleteYou can visit mine if you feel like.
Cheers from Argentina!
Humberto.
www.humbertodib.blogspot.com