## Thursday, May 3, 2012

### Knowledge and Monty Hall

Sam Harris' book, The Moral Landscape, introduced me to the Monty Hall problem. People who love big words call this problem a veridical paradox, which basically means that the correct answer defies common sense.  Most people, even after having the answer explained to them, still have this unsettled feeling about it.  If you've never seen this before, you are almost guaranteed to think "but that can't be right!"

You can read about the problem on the Wikipedia page I linked above.  You can also read a description by Barbara Drescher here.  The purpose in bringing this up is to illustrate how our brains can fail us.  How common sense can be dead wrong.  How an assumption about the world can therefore be dead wrong, and how critical it is that we look deeply and think critically.

This applies to all sorts of things.  Evolution, for example, is not an intuitively obvious process, and I suspect that this is the source of much resistance to the idea.  Even after understanding evolution I sometimes think about the complexity of even a goldfish and think "wait, that isn't designed?"

So back to Monty Hall.  Here's the most popular version of it:

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 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which 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 answer is yes, it is to your advantage to switch, because if the odds of Door No. 1 winning are 1 in 3, and the odds of Door No.3 winning are 2 in 3.   Your brain might riot at this suggestion, but its true.  I will briefly describe why this works a little later, but the links to Wikipedia and Drescher above include pretty pictures, so you may prefer that.  The odds are not equal between these two doors.   The key thing that your brain probably does not intuitively recognize is that you have the ability to take advantage of someone else's knowledge.

Drescher's description of the problem and its solution included this phrase:
"The issue of knowledge is a factor in our processing of the problem, but it’s not what Monty knows that matters. It’s what you (the subject of the problem) know."

It is not clear to me whether Drescher has misunderstood the deeper nature of the problem, or if she has just been unclear with her wording.  In any case, the phrase "it's not what Monty knows that matters" is very misleading.  What Monty knows is crucial.  What Monty knows is what makes this whole thing work.  What Monty knows about which door is the winner is what makes these two options unequal.

To illustrate this, we can change the problem slightly.  This time, instead of Monty opening the other door, we will alter the problem so that you have an opponent:

Suppose you're on a game show, in the final round with your opponent.  Because you are ahead, you are allowed to reserve a door (but not open it) before your opponent picks.  Behind one door is a car; behind the others, goats.  You pick Door No. 1 but the door is not opened.  Your opponent picks Door No. 3 and this door is opened, revealing a goat.  Your host now gives you the opportunity to switch to Door No. 2 if you wish.  Is it to your advantage to switch?

In this case, the answer is no, it does not matter.  Door No.1 and Door No.2 in this version of the problem have equal chances to be correct, and the difference is that your opponent did not have any knowledge of which door was the winner when she picked Door No. 3.  It was not a revealing of information, it was a guess.  You do get more information, in the sense that you now know that Door No. 3 is a loser, but in this version that doesn't help you pick between 1 and 2.  Here's why:

I find this easier to explain in the multiple universes sense.  In the original problem, there are 3 possible universes that you could be living in:

Universe 1:
C G G   <- the prizes behind the doors
1  2  3   <- the door numbers
^  ?  ?    <- the various guesses and reveals
In this universe there is a car (C) behind door number 1, and you have picked this door as shown by the (^) symbol.  In this case Monty will reveal either door 2 or 3 and if you switch you will lose.  This is the 1 case out of 3 where switching is not to your advantage.

Universe 2:
G C G
1  2  3
^  ?  X

In this universe there is a car (C) behind door number 2.  You have picked door 1 as shown by the (^) symbol.  In this case Monty will always reveal door 3 (X), because Monty knows which door has the car.  This is a case where you win if you switch your guess.

Universe 3:
G G C
1  2  3
^  X  ?

In this universe the car is behind door 3, you have picked door 1, and Monty will always reveal door 2 (X) as a loser, because Monty knows.  This is a case where you win if you switch your guess.

So that's the original problem, and in 2 of the 3 possible scenarios you win if you switch your guess.

Here's the altered version.  In it, your opponent's guess is random, as was yours.  For clarity we will pre-assume that you have guessed door no 1, and your opponent has guessed door no 2 in all cases.  Since neither of you know anything about which doors is the winner, this configuration of guesses is essentially the same as any other.

Universe 1:
C G G
1  2  3
^  L  ?

In this universe the car is behind 1, and your opponent has lost by guessing door 2 (L).  If you switch you will lose.

Universe 2:
G C G
1  2  3
^ W ?

In this universe the car is behind 2, which your opponent has guessed (W).  You lose.  If you have a choice to make at all, you are not in this universe.  Critically, this is the condition that never happens in the version where Monty reveals a door that he knows to be a loser for you, and this is what makes the two versions different.  In the previous version this Universe is a winner for you, but in this one it is a loser.

Universe 3:
G G C
1  2  3
^  L  ?

In this universe the car is behind 3, and you will win if you switch.

Out of these 3 universes, you can only be in 2 of them if you have a choice to make at all, and of those 2 possibilities, in one of them you win if you switch and in the other you lose if you switch.  It's 50/50 this time.

So there's an extra layer of paradox.  You picked 1, and someone opened another door, revealing a goat.  Should you switch?  It depends on what the person who opened the door knows.  If Monty opened the door with the deliberate intent to reveal a loser to you, then you should switch because that makes your odds 2/3.  If an opponent selected a door randomly and just happened to reveal that same losing door, then your chances are not affected by switching.  One door is as good as the other.

This is so counter-intuitive that I built a computer simulation of the problem just to verify that I'm not crazy.  The car placement is random.  The contestant's guess is random.  In the Monty version, Monty's reveal is not random, it is based on Monty's knowledge.  In the Opponent version, the opponent's guess is random from the remaining choices.

Here's 1 million runs of the Monty version (Monty reveals, information added):
Opportunities for you to switch: 1,000,000
Wins: 667,103

As we claimed, you win 2/3 of the time in this version by switching, and you always have the chance to switch.

Here's 1 million runs of Opponent version (Opponent guesses, no information added):
Opponent guesses correctly: 333,246 times. (no chance for you to guess)
Opportunities for you to switch: 666,754 times.
Wins by switching: 333,417 times.

As you can see, in this version you win about 1/2 the time that you are given the opportunity to switch, or 1/3 of the time overall.  In the Monty version all of those times when the Opponent guessed correctly would have instead been converted to a condition where you win if you switch.

We might as well call your opponent Scotty, because Scotty doesn't know.  (NSFW, sexual humor, language.  Also, Matt Damon!)  Monty does know, and knowing is half the battle... or 2/3rds... or something.

Failures of human reasoning fascinate me.

1. I'm gonna have to do that simulation myself before I'll accept it.

Just when I thought I finally understand a thing.

3. So I've been thinking about this some more, and I have an additional explanation that I hope will make the difference between the Monty version and the Opponent version clearer.

Imagine an alternate Monty version. Initial setup is the same as the standard version. You pick Door 1. Monty says "I'm going to give you the option to, instead of picking Door 1, pick Doors 2 AND 3, and if the prize is behind either of them, you win it."
Should you switch? Obviously, yes. You've been given a 2-for-1 guess. Essentially, the probabilities of each of Door 2 and Door 3 winning have been stacked up into a single choice that you can make. It's an obvious 2/3 chance to win, because you get 2 guesses in 1.

Now imagine yet another alternate version. Same setup. You guess Door 1. Monty says "Now, we're going to do a possible switch of the prize. IF the prize is behind Door 2, we're going to move it to Door 3. If it is not behind Door 2, we will not move the prize. You may then guess Door 3 if you wish." Should you switch? Of course, the probabilities have b een added again. If the prize was originally behind 2, then it is now behind 3. By guessing 3 you can get a 2-for-1 guess again. You'll win 2/3 of the time by switching.

This is exactly what is going on in the original Monty version, it's just less obvious because of the way the question is framed. Instead of "you pick Door 1, Monty reveals Door 3, should you switch to Door 2?", we can rephrase the question so that it is the same thing but more obvious. Monty says "We're going to treat Doors 2 and 3 as a pair, but instead of opening both of them, I'm going to open one that isn't a winner and give you the option to open the one that is left." The original problem is confusing because you feel like you're choosing between Door 1 and Door 2, when you are in fact choosing between Door 1 and the remaining door from a Door2-Door3 pair with stacked odds. You are again getting a 2-for-1 guess, it just isn't as obvious.

In the case of the Opponent version, your opponent, Scotty, is not doing anything that creates a 2-for-1 guess for you. He is not adding the probabilities of Doors 2 and 3 in any way. He is not in any way making a pair of them, or making them equivalent. He is actually guessing to win. When Scotty reveals Door 2 it does not add its probability to Door 3, because if Door 2 was a winner, Scotty would have won. In this case your choice is not between Door 1 and the remaining door of a Door2-Door3 pair, it is literally between Door 1 and Door 2 only. In this case their chances are still equal.

4. Yet another way of seeing the "random Monty" version is this: Randomly selecting a door to open is isomorphic to randomly selecting one to keep closed.

So what happened is that you randomly chose a closed door, then Monty randomly chose a closed door from the other two, then the remaining door was opened. It should be clear that the only difference between you and Random Monty is that you picked "first", but that doesn't mean you are any less likely to have picked the car than Monty is. You could have both picked at the same time (barring the situation where you pick the door) and it would fundamentally be the same game.

A mistaken way to perceive it would be: "When I picked, I had a 1 in 3 chance, but when Monty picked, he had a 1 in 2 chance, so if I switch, my odds improve from 1/3 to 1/2." (Of course, since the car didn't move, Monty's choice wasn't somehow a fifty-fifty situation.)

Interestingly, a lot of people mistakenly say that "1/3 vs 1/2" is the answer to the classical version! For example, I just introduced the problem to a retired physics professor. After he initially thought it made no difference, I clarified that Monty's choice wasn't random. Because I don't like people thinking too long about it with the wrong intuitions (they tend to get attached to their mistakes and dig in their heels), I emphasized that there's no way that Monty opening a second door can make you likelier to have picked the prize to begin with, since you already knew it would happen. He understood this but still thought that switching was only 50% likely to win, even as staying was 33%. Perhaps the idea that switching is such a drastic improvement feels highly counterintuitive, for some reason.

Finally, here's yet another way to think about Random Monty. In the original puzzle, prior to Monty opening a door, you can predict with 100% confidence that he will reveal a goat. Therefore, you don't have to wait until that happens to calculate your probability of currently having a goat, and you know that probability won't change immediately after a fully-predictable event. On the other hand, if you know Monty is random, then his opening a goat door actually tells you something about your door. He's twice as able to show a goat if you've helpfully sequestered the car from his two doors (which will happen 1/3 of the time) than if you unhelpfully sequestered a goat (which will happen 2/3 of the time). So we simply multiply it all out: one-half of two-thirds (the probability that you pick a goat and Monty picks the other goat) equals one-third, while one times one-third (the probability that you pick a car and Monty picks a goat) equals one-third. Our final situation is 1/3 of games where switching and only switching will win, 1/3 of games where staying and only staying will win, and 1/3 of games where a car was revealed and the audience wants their money back.