The Monty Hall Problem (Probability Debate)

[ballin4life]

Backward induction is the secret to many "tricky" interview questions, so you should thank me.

E.g.

To begin with you have 80 wolves and 1 sheep on an island. A wolf can eat a sheep, but then he turns into a sheep himself. A wolf would prefer to eat, but most of all just wants to stay alive (so the wolf's preferences are: eat and live > don't eat and live > eat and then die ).

What happens? How many sheep get eaten, and how many wolves are left at the end?

And yes, I actually was given the above problem in an interview.

 

[ciaza]

So...the first wolf eats the one sheep, and then effectively becomes that sheep, right? The second wolf does the same, etc until the last wolf eats the one remaining sheep to become a sheep meaning there are 0 wolves and 1 sheep.

That seems like a pretty poor outcome, so wouldn't it be better for no wolves to eat the sheep?

 

[Battlecow]

Wolves are incapable of complex rational thought.

And you just pwned that interview with OUTOFTHEBOX thinking.

 

[1048576]

Assuming the wolves are capable of rational thought...

If there is 1 wolf and 1 sheep left, the sheep gets eaten. If there are 2 wolves and 1 sheep left, the wolves go hungry, since if one of them ate, he'd become the sheep in the 1 wolf, 1 sheep scenario.

If there are 3 wolves and 1 sheep left, wouldn't it be beneficial for one wolf to eat a sheep, since he knows he'll never be eaten, since that would be a death sentence? 4 wolves nobody eats, since then the 3 wolves scenario occurs. 5 wolves, a wolf eats, since then the 4 wolves scenario occurs. So yeah, 80 wolves, nobody eats, but I'd prefer there to be 79 wolves at the start, since then (if I'm right,) it'd be a harder problem.

 

[ballin4life]

Assuming the wolves are capable of rational thought...

If there is 1 wolf and 1 sheep left, the sheep gets eaten. If there are 2 wolves and 1 sheep left, the wolves go hungry, since if one of them ate, he'd become the sheep in the 1 wolf, 1 sheep scenario.

If there are 3 wolves and 1 sheep left, wouldn't it be beneficial for one wolf to eat a sheep, since he knows he'll never be eaten, since that would be a death sentence? 4 wolves nobody eats, since then the 3 wolves scenario occurs. 5 wolves, a wolf eats, since then the 4 wolves scenario occurs. So yeah, 80 wolves, nobody eats, but I'd prefer there to be 79 wolves at the start, since then (if I'm right,) it'd be a harder problem.

You got this right, except that 79 isn't any harder than 80. It just comes down to even -> no wolf eats, odd -> one wolf eats, then you're in the even situation.

The key though is the backwards induction. You look at the end situation first, and working backwards from there gives the solution.

 

[AltF4]

In computer science parlance, you'd call it recursion. (As opposed to "backwards induction")

 

[ballin4life]

Backwards induction is standard terminology that refers to this method for finding the subgame perfect Nash equilibrium.

Sometimes there is more than one such subgame perfect Nash equilibrium though so I don't know if recursion will always work (depending on how you define the recursion).

 

[1048576]

You got this right, except that 79 isn't any harder than 80. It just comes down to even -> no wolf eats, odd -> one wolf eats, then you're in the even situation.

The key though is the backwards induction. You look at the end situation first, and working backwards from there gives the solution.

I meant that someone could guess right more easily if you start with 80 instead of 79

 

[ballin4life]

If they just guessed a random number then maybe I guess. But the point is the reasoning.

 

[#HBC | Mac]

Gawd I absolutely hated learning this. The correct answer makes absolutely no sense to me no matter how anyone explains it to me (even the mathematical explanation. [Which is even worse because I tend to look at things very mathematically]).

edit: lemme try to consider the 100 door example, maybe the problem will stop plaguing my mind
edit2: ooooo interesting. rethinking about the problem with many more doors sheds more light on the concept. I still find it interestingly odd but atleast I can wrap my head around it now

 

[rvkevin]

Hope this helps:

There are six arrangements of what could happen. If you choose door one, he could open door two or three, if you choose door two...so that you have:
[Door you chose, door opened] (Result assuming prize in door one)
Combination 1: [1,2] (Win if stay)
Combination 2: [1,3] (Win if stay)
Combination 3: [2,1] (Prize is opened)
Combination 4: [2,3] (Win if switch)
Combination 5: [3,1] (Prize is opened)
Combination 6: [3,2] (Win if switch)
If he opens a door that does not have a prize, and the prize is in door number one, this will eliminate combinations 3 and 5 since those options have him opening up the car and that didn't happen. This means that the options left remaining are 1, 2, 4, and 6. Half of them result in you winning if you stay and half of them result in winning if you switch, so switching does not benefit you. However this assumes that he will open the door randomly. If you draw the matrix such that he only opens the door with no prize, still assuming door one has the prize, you get this matrix:
[Door you chose, door opened] (Result assuming prize in door one)
Combination 1: [1,2] (Win if stay)
Combination 2: [1,3] (Win if stay)
Combination 3: [2,3] (Win if switch)
Combination 4: [2,3] (Win if switch)
Combination 5: [3,2] (Win if switch)
Combination 6: [3,2] (Win if switch)
Now, options 1 and 2 result in you winning if you stay, whereas options 3, 4, 5, and 6 result in you winning if you switch. Basically, if you switch, you win every time you initially didn't choose the winning door. Since you choose the winning door one third of the time, the chance of winning after the other door is opened is two thirds by switching.

 

[ballin4life]

Gawd I absolutely hated learning this. The correct answer makes absolutely no sense to me no matter how anyone explains it to me (even the mathematical explanation. [Which is even worse because I tend to look at things very mathematically]).

edit: lemme try to consider the 100 door example, maybe the problem will stop plaguing my mind
edit2: ooooo interesting. rethinking about the problem with many more doors sheds more light on the concept. I still find it interestingly odd but atleast I can wrap my head around it now

It's all because Monty knows where the car is.

Then, if you guess wrong at first (2/3 chance) he literally has NO choice which door to open. He can't open your door, and he knows where the car is, so he HAS to open the third door.

 

[Tyler Moncek]

An error has occured

 

[AfungusAmongus]

The probability is NOT 50/50 because of how Monty's pick depends on your pick. There is a 2/3 chance that you picked a goat, causing Monty to pick the other goat, in which case swapping guarantees that you win. There is a 1/3 chance that you picked a car, in which case swapping guarantees that you lose. Therefore P(win|swap) = 2/3. Since there are only 2 closed doors to pick, P(win|stay) = 1 - P(win|swap) = 1/3.