Log in

No account? Create an account
15 June 2009 @ 01:15 am
Monty Hall, meet Schrödinger's cat.  
Ladies and gentlemen...

I will now attempt the impossible -- to walk you through the most confusing problem in all of mathematics. This infamous problem has confused millions of students and professors, sparked thousands of hour-long debates and netted me at least $20 in bet winnings. The Monty Hall problem is a famous paradox of probability theory. The intuitive solution is incorrect, and the correct solution is completely counter-intuitive. Most people refuse to believe the correct solution, rejecting it as some sort of a trick of the mind. But what really makes this problem amazing is that, unlike most math problems, it is entirely grounded in the real world. Instead of giving you a proof, I will give you a simple tool that you will be able to use to prove it for yourself.

...and then when you get it, I will turn the problem upside down and confuse you forever. Ready?

Behold: the Monty Hall problem

You are a contestant on a game show. The grand prize is a car, hidden behind one of 3 identical doors. Behind the other two doors are goats. You are a vegan, living in a Manhattan studio apartment, so winning a goat would be a highly undesirable outcome for you -- you want the car. The game show host, Monty, asks you to choose one of the doors. You do so. He then opens one of the other two doors, revealing a goat, and asks you whether you want to take the prize behind the original door of your choice, or whether you want to change your mind and win the prize behind the other unopened door. What should you do?

Most people say that it doesn't matter -- the chances are 50/50 between the two remaining doors. In fact, the correct answer is to change your mind and pick the door you have not chosen originally. This strategy gives you a 2/3 chance of winning the car. Unconvinced? No worries. Let me show you a simple trick.

"Any lock can be picked with a big enough hammer"

Instead of trying to convince you, I will give you a tool you can use to solve this problem yourself. What do most people mean when they say, "The probability of getting heads in a coin toss is 50%"? They mean that if you toss that coin many, many times, about half of the time it will come up heads. One way to verify this is to take a coin, toss it a thousand times and count occurrences of heads and tails. It's boring, but it works. Fortunately, in the 21st century, we have machines that can do such boring tasks for us.

Open up Google Spreadsheets or a copy of Excel, if you have it. Make a new spreadsheet with 4 columns -- let's call them "Door with the prize", "Player's first choice", "Monty opens" and "Should switch". Put these column names into cells A1, B1, C1 and D1, respectively. Go ahead, do it, really; it will be worth your time. Next, set the values of cells A2 through D2 as follows:

A2: =randbetween(1,3)

A random number between 1 and 3, inclusive. This is the number of the door behind which the car is.

B2: =randbetween(1,3)

Another random door number. This is the player's first choice.

C2: =if(mod(B2,3)=A2-1,6-A2-B2,mod(B2,3)+1)

This is the door Monty will open. The formula says that, of the two doors not picked by the player, if the first one contains the prize, Monty will open the second one. Otherwise, he will open the first one.

D2: =if(B2=A2,false,true)

If the player has picked the door with the prize, then switching is a good idea; otherwise, not.

Cell D2 will contain your answer -- true if you should change your mind; false if you should keep the door you picked originally. We have successfully simulated the game once.

Now comes the cool part. Select cells A2 through D2 with your mouse and drag the little "+" sign that appears at the bottom-right corner of the selection all the way down to cell D100. The selected cells will fill up with numbers, giving us the results of 99 independent simulations of the game and for each one, the answer to the main question -- "Should the player switch or not." You will notice that the word "TRUE" appears about twice as often as the word "FALSE". To get a precise count, put the following formula into cell E3: "=sum(D2:D100)/count(C2:C100)".

Here is my spreadsheet for doing this. I got 65.66% TRUE, which is just under 2/3. If you add more rows and fill them, you should get closer and closer to 66.67%.

Note that we didn't even use the values of column C to compute column D. That is not a mistake. The outcome of the game does not depend on which door Monty opens! Whether the player wins or loses depends only on the player's initial door choice.

Forgetful Monty Hall

It is time to make things weird. Let's change the game scenario a little bit. There are still three doors, one car and two goats, and you still get to choose the first door. But now, Monty has forgotten where the prize is! He knows he has to open one of the two remaining door, but he can't remember which one has the car. He is nervous; he is sweating. The show's producer is looking around the room in panic. Finally, Monty decides to take a wild guess and picks the door on the left. He opens it, and... whew! It's a goat. The show goes on. It's your turn to decide. Do you change your mind, or do you stick with your original decision?

You are probably thinking, "What's the difference?" What does it matter if Monty knows where the car is. The outcome is the same, right? He still opens a door with a goat behind it. Well, it turns out that in this case, it doesn't matter if the player switches or not -- the probability is 50/50. But you don't have to trust me. You have the tool to check it yourself -- simulation!

Let's start a new spreadsheet. This time, we will need 5 columns -- "Door with the prize", "Player's first choice", "Monty opens", "The show goes on" and "Should switch". Here are the formulae:

A2: =randbetween(1,3)

The prize is behind a random door.

B2: =randbetween(1,3)

The player picks the door at random initially.

C2: =mod(B2-1+randbetween(1,2),3)+1

Monty picks one of the other two doors at random.

D2: =if(A2=C2,false,true)

This is TRUE, unless Monty has opened the door that was hiding the prize. Since we know that this didn't happen, we ignore all rows that have value FALSE in this column.

E2: =if(A2=B2,false,true)

Same as before -- if the player has picked the door with the prize, then switching is a good idea.

Select cells A2 through E2 and drag the bottom-right corner of the selection down to cell E100.

Note that about 1/3 of the values in column D are FALSE. In my spreadsheet, I have marked them in gray. They correspond to scenarios where Monty has accidentally opened the prize door. The problem states that this is not the case, so we ignore all such rows. From the rows that remain, we count the fraction that have TRUE in column E. An easy way to do that is to type the following formula into cell D3: "=sum(filter(E2:E100, D2:D100))/sum(D2:D100)". Mine shows 45.16%. If we added more rows, that value would get closer and closer to 50%.

If Monty doesn't remember which door hides the car, then changing your mind and not changing your mind give you the same chances of winning the prize.

So where does Schrödinger's cat come into this?

Schrödinger's Cat is a famous paradox of quantum mechanics, where a cat can be simultaneously alive and dead, until an observer opens a box and looks inside. The act of observation seems to have a measurable effect on the physical world. I claim that the case of forgetful Monty Hall is similarly weird, if not more so.

Imagine you are a contestant on Monty's game show. You pick your door, and Monty opens one of the other ones, revealing a goat. He then offers you a chance to change your mind. You may open one of the two remaining doors and claim the prize behind it. To make things a little bit more interesting, Monty offers you an extra $100 if you do not change your mind and stick with your original choice of door.

At this point, you have to ask yourself -- did Monty know where the prize was, or did he just get lucky by opening the right door at random? How certain was he? Is he tired today and thus prone to forgetfulness? If Monty is perfectly lucid, then your door has the prize 33% of the time. If he is completely out of it, then your door has the prize 50% of the time. In reality, Monty is probably somewhere in the middle, depending on his age, how much sleep he got last night and how distracted he is by the cute girl playing against you. None of this is in your control, or has anything at all to do with you! I'm calling it "spooky probabilistic action at a distance".

If you think this is weird, look at it from Monty's point of view. If he knows where the prize is, he wins with probability 33%. If he doesn't, he wins half the time. Knowledge works against him! To be fair, that's not exactly true. It depends on what happens if he opens the door with the car behind it. If the punishment is getting fired from the show and ridiculed by all the TV viewers, then Monty definitely wants to know where the prize is. If instead the director simply yells "Cut!", closes the doors, shuffles the car and the goats, and we replay the round, then Monty would rather not know where the prize is. (Well, technically, he does want to know, and he would always intentionally open the door with the prize, unless you, the player, are holding that door, but then if you knew that that was Monty's strategy, you would never switch, unless... it gets complicated.)

The point is -- whether or not Monty knows something determines your optimal playing strategy.

How bad can this get?

Is there a situation where the mere fact of me knowing something would mean the differce between a 99%-good and a 99%-bad outcome for you? For starters, if you simply increase the number of doors to 100, (keeping the one car, but now requiring a sizeable herd of goats), then the 66.67% probability in the "Monty knows" case turns into a 99% probability. The "forgetful Monty" case remains at 50%. See, for example, my previous post about a 30-door version of the Monty Hall problem. Or else, you can make a tiny change to the spreadsheet and easily simulate the 100-door case yourself.

The homework question is -- can you devise a game where you win 99% of the time if I know something, and lose 99% of the time if I do not? It is tricky to understand what I mean here! Both scenarios must be exactly the same, up until the point where you have to make a critical decision. At that instant in time, your probability of winning must heavily depend on whether I know some particular fact. In the case of the 100-door Monty Hall problem, this difference in probabilities is 99%-50%. Can you make it 99%-1%?
(Anonymous) on June 15th, 2009 09:36 pm (UTC)
Hmm... Mind-boggling. But, I don't agree with the conclusion that the knowledge works against Monty.

If Monty doesn't know which door hides the car, there is one possible outcome whose value is undefined - Monty breaking the format of the game by revealing the car himself. If we define this outcome (e.g., Monty would 10x rather give away the car than break the rules), the "paradox" disappears.

Also, regarding this comment: 'If instead the director simply yells "Cut!", closes the doors, shuffles the car and the goats, and we replay the round, then Monty would rather not know where the prize is.'

I would think that repeating until Monty "gets it" is essentially the same as if he "knew". If the contestant knows that the game is going to repeat until Monty finds the right door, they still have a 2/3 chance of winning.

On the other hand, if the contestant does not know what is going to happen if Monty accidentally reveals the car, then the game is poorly undefined, and talking about probabilities doesn't make sense.
(Anonymous) on June 15th, 2009 09:37 pm (UTC)
Forgot to sign... This is IgorO :-)
igor_navigor_nav on June 15th, 2009 09:44 pm (UTC)
I agree. Thinking along these lines quickly turns into a game of figuring out who knew what at which time. I wasn't really trying to make a precise point in that part.
(Anonymous) on June 15th, 2009 10:13 pm (UTC)
I think I was wrong with one point, though.

It looks like there actually is difference between the case when Monty knows which door hides the car, and the case where the directory yells "Cut!" repeatedly until Monty happens to find a goat.

I found it confusing... but then I realized the reason. If the contestant happens to choose the door with the car on the first try, the other two doors contain goats, so the game will not restart regardless of which door Monty chooses. So, given that the game was not restarted, the likelihood the contestant has the right door goes up to 50%.

This problem really is confusing. :-)

(Anonymous) on June 23rd, 2009 11:08 pm (UTC)
Monty knowing leads to 50%
I suspect you'd find that Monty acting intelligently, combined with the contestant doing the same, would yield a Nash equilibrium at a 50% chance of user victory. Probably-insufficent proof:

- Monty can force 50% by acting as though he knows nothing.
- The contestant can force 50% by picking randomly.

If either can force 50%, then changing away from that strategy can only give the opponent a chance to do better than 50% (since you can't change to a strategy that forces the opponent to do worse than 50%).

(Anonymous) on June 23rd, 2009 12:16 am (UTC)
Here's my solution. You are faced with 100 doors and told that each door has a 50% chance of having a car or a goat behind it. You don't make an initial choice; the game show host simply opens 90 doors that all have goats behind them. (If this isn't possible, or he accidentally shows a car, the game is canceled.) You need to place a bet on whether the final 10 doors have AT LEAST 9 cars behind them.

If the host knew what he was doing, then this will happen (100C10 + 100C9) / (100C10 + 100C9 + ... + 100C0) of the time, or very close to 99%. If the host just got lucky, this will happen (10C10 + 10C9) / 2^10 of the time, or very close to 1%. So your choice is 99% one way or the other, depending on whether he was lucky or acting with knowledge.

Mind you, there are a pretty ridiculous number of canceled games under this model. :) You could probably tweak the numbers to reduce it in the "host was smart" case. But I suspect there's some high lower bound on canceled games in the "host was lucky" case, since those canceled games are the key to changing the probability distribution. Wonder what that lower bound is? (99.99%?)

- Derek
(Anonymous) on June 24th, 2009 12:03 am (UTC)
Here's an alternate solution, using way more doors than is needed. Perhaps the new challenge should be to find the minimum expected number of cancelled games with at least a 99%-1% split.

There are 1,000,000 doors. With probability 1e-6, there is 1 car; else there are 100 cars. You pick a door, and Monty opens up another 999,899 doors -- all but 100 of the doors you didn't pick.

If he knows what he's doing, you're probably in the more probable number of cars -- 100 -- and the chance your current door contains a car is just 1e-4, and you have very good odds of scoring a car by switching doors.

If he doesn't know what he's doing, in the majority case his chances of picking the correct set of doors is miniscule [shut up spell checker, I'm not American], on the order of 1/(1e6!). But in the minority case, 1e-6 of the time -- which is actually seeming like a lot at this point -- his chances of picking the right doors are something like 1e-4. So in that scenario you're very likely to end up with 101 equally-likely doors and 1 car behind them.

(Anonymous) on June 26th, 2009 12:38 am (UTC)
Hmm. There's a key difference between your solution and mine, though. In your solution, you always want to switch, regardless of whether the host was acting with knowledge. The odds of success just change from 99% to 1%. In my solution, your "correct" move is actually different depending on the host's knowledge.

I think you could tweak your solution to cause this situation by saying "if you stick with the original door and the car's behind it, you actually get 100 cars." It's not enough to entice you to switch if the host is acting with knowledge; but if he's not, you should definitely stay with your first choice.

Of course, in both our solutions, the odds that the host got lucky without knowledge are vanishingly small (1e-10 in yours, 1e-zomgwtfbbq in mine). Based on the fact that the game wasn't canceled, Bayesian reasoning really should lead you to the conclusion that the host knew what he was doing, regardless of the prior probabilities you choose and any outside evidence. :)

- Derek
Ashiashi_starshade on February 7th, 2010 11:22 am (UTC)
Initially, when I had seen this problem a couple of years ago, I had dismissed it as sleight of hand and bad mathematics, but since you actually posted about it I took it seriously. When I thought about it, eventually it became clear. The question is phrased deceivingly. The correct question is: What are the odds the player was right to begin with? 1/3. That means 2/3 of the time the player should switch regardless of what Monty does -- since Monty gives no clue as to whether the player was right or not. [You did make a statement which subtly said this implicitly, in the end.]

Now, the 2nd and more tricky part, is why does the 2/3 factor carry over directly into the odds of winning by switching? Without actually looking into it, I think it's because exactly half the remaining choices are winning and exactly half are losing. If you make it 4 doors, I don't think the "3/4 " (rather than 2/3) will carry over -- I think there'll be a coefficient to it. But I have already satisfied myself and think I'm correct, so I'm not going to check :)

I didn't realize you were at google already. I knew it, and then didn't think about it later when I guy I know (who's worth knowing) started working there recently. I'll email you his contact info.
Ashiashi_starshade on February 7th, 2010 11:24 am (UTC)
Oh, I forgot to mention, I don't believe in Shroedinger's cat. It's not a scientifically accepted theory, just a postulated one. That should be noted.
Ashiashi_starshade on February 8th, 2010 08:54 pm (UTC)
Bah, I'm an idiot. You mentioned the 100 doors problem at the end. You must have taken it as an affront that I didn't even bother reading that far. Oh well, I guess you'll have to take the affront even though that was unintended. I thought the last section was going to be more schroedinger nonsense.