Hacker News Reader

Comment by javajosh | Hacker News Reader

So this is at least in part about the "Monty Hall Problem" and why it's solution not intuitive. The article missed an important angle: when the host opens a door, he's giving you more information, which explains why it's better to switch. If you're the host, you need to know which door the car is behind to do your job 2/3 of the time, to avoid revealing it.

It's this quality of unexpected information exchange that I find most fascinating about this particular puzzle!

View on HN

When you choose the first door, you are partitioning the "board" into two parts: the door you chose, and "everything else".

By opening a door, Monty lets you cover 100% of the "everything else" partition using only one guess.

So now you get to choose between partition 1, which covers 1/3 of the board, and partition 2, which covers 2/3 of the board.

I have never heard this formulation, and I like it quite a lot. Thanks!

It is Bayes’ Rule essentially written out (sample spaces)

I think the confusing part for many people is the unstated fact that the host takes all prizes into account when revealing a door, and that the host is forbidden from revealing the car. If the host chooses randomly then his pick adds no information (other than the extra revealed prize)

I don't think people are confused by this in their initial solutions, but rather this after-the-fact problem modification happens to match the incorrect intuition people have.

The instinct is strong that "I am right" so "I must have just solved the wrong problem", thus "the problem was confusing".

Rather, I think you will find that most people don't expect the host will ever pick a door with a car until after you tell them that switching is better, and rationalization begins.

Additionally, it's on the solver to realize that a problem is under-constrained, and to ask for more constraints. That means that even if you were earnestly confused by the question, you presented a solution to an under-constrained problem. This is like answering "what is the square-root of four" with "it's negative two".

yeah, it’s reasonable to attribute those defects to the solver and not their situation and circumstances

I don't think this actually matters. Suppose Monty doesn't actually know which door has the prize, and just picks randomly between the two. Now the only difference is that Monty might accidentally pick a prize. Suppose he does. What are the options now?

1. The game goes on, and you can just switch your guess to the door he picked. (WIN)

2. The game resets due to Monty's error and you play again. (REDO)

3. Monty just decides that you lose since he picked the prize. (LOSE, NO CHOICE)

Options 1 and 2 don't deprive you of the car. But option 3 doesn't give you a choice, so there is no dilemma.

So conditional on having a game where no prize has been revealed yet and you get a choice to switch, I think it still pays to always switch.

Another way of putting it: you get to choose between partition 1 covering 1/3 of the board where you get 1 guess, or partition 2 covering 2/3 of the board where you get two guesses. It works even if all of the guesses are random.

>Now the only difference is that Monty might accidentally pick a prize.

This a mistaken conclusion, as actually there is a difference if a goat is revealed by devious Monty (who makes sure he doesn't reveal the car) and dumb Monty (who picks at random), because the rules of the game really are different. The apparent outcome (you pick door, Monty reveals a goat) is the same. But the process is different. In the latter version dumb Monty has all the same information as you, in the former version devious Monty gets more information that you do and changes his behavior based on that information.

In programming terms, devious Monty has an "if" statement in there. (Something like, `if (random_choice == prize_door) { swap_choice(); open_door(); } else { open_door(); }`.)

TL;DR: I was wrong (but I did understand the distinction you are drawing)

I'm aware that there is a difference between devious Monty and dumb Monty. The question I was trying to answer is whether this difference affects the actual outcome of the game, or the choice you should make.

I ran a Monte Carlo simulation to test my analysis, and this proved that my previous analysis was in error. If Monty doesn't know to avoid the door with the car, then it makes no difference statistically speaking whether the player switches or not after Monty reveals a goat.

If the rules are such that you win when (dumb) Monty picks the car, then your overall chances are now 2/3 instead of 1/3, since you effectively get two guesses (your guess and Monty's guess). But it makes no difference whether you switch after Monty picks a goat.

On the other hand, if (dumb) Monty choosing the car results in either (1) you losing or (2) a reshuffle and redo, then your overall chances are only 1/3. In this case, it also makes no difference whether you switch after Monty's guess.

if monty picks a prize the game is over

Interestingly, if the host picks randomly (and if he reveals the car, you... start over, or you get the car, or you get nothing, or ... it doesn't matter because it happens not to have happened in the time we're considering) then you are faced with a 50/50 chance.

I don't understand how this could be. If you start over when the host picks the car, then isn't that the same as the host picking the goat every time, i.e. the same as the host knowing.

Well, I don't know. Advantage moves to the contestant: they close the doors, but everything's gonna remain in the same place. Steathily repositioning an automobile on a soundstage might be possible (albeit difficult), but just you try moving the damn goat

Fair warning: I haven't rigorously verified the math on this, and tfa is all about the importance of vigorously verifying the math.

In the case where the host revealing the car means you restart, there are three equally likely situations after the host opens a door: - You picked the car, and the host revealed a goat - You picked a goat, and the host revealed the other goat - You picked a goat, and the host reveals the car (restart)

Of the two terminal cases, one gets you the car if you switch, and one gets you the car if you don't switch. In the non-terminal case, it doesn't matter what policy you have because you don't even get a chance to apply it.

One way to think about it is to imagine Monty picking randomly in either case, but then (internally and invisibly) correcting his pick.

Assuming, WLOG, that we choose door 1, that leaves us with 6 equally likely cases just before that final correction (or lack thereof):

    A) Car 1, Monty 2
    B) Car 1, Monty 3
    C) Car 2, Monty 2
    D) Car 2, Monty 3
    E) Car 3, Monty 2
    F) Car 3, Monty 3

If Monty doesn't correct in cases C and F, then when he shows us a goat behind (say) 2 then we learn we are in either A or E - it's 50/50. If Monty does correct himself, then we might have been in A or E or F.

Ah, yep, that’s right. Another way to see it is that we’re interested in the probability that your door has a goat behind it, given that you didn’t need to start over:

P(you chose goat | host didn’t choose car) = P(you chose goat, host didn’t choose car) / P(host didn’t choose car).

The numerator is 2/3 * 1/2, and the denominator is 2/3, so the ratio is indeed 1/2.

(A rejection sampling loop, where you repeatedly simulate a process until a condition holds, has the same distribution over final outcomes as the conditional distribution—so repeatedly restarting the game if the host chooses the car induces the same distribution on final results as simply conditioning on the host not choosing the car.)

This is a small enough situation that we can do complete enumeration of the states.

Let's say you pick door 1. Let's go through all the possibilities: the states of the 3 doors, which one monty reveals, and what do we do, and what is the result?

  1 | 2 | 3 || Monty Reveals | You switch | Result
  ---------------------------------------------------
  G | G | C ||      2        | Yes        |  Win
  G | G | C ||      2        | No         |  Lose
  G | G | C ||      3        | N/A        |  Start Over
  
  G | C | G ||      2        | N/A        |  Start Over
  G | C | G ||      3        | Yes        |  Win
  G | C | G ||      3        | No         |  Lose
  
  C | G | G ||      2        | Yes        |  Lose
  C | G | G ||      2        | No         |  Win
  C | G | G ||      3        | Yes        |  Lose
  C | G | G ||      3        | No         |  Win

Count 'em up: When you switch, 2 wins and 2 losses. When you don't, 2 wins and 2 losses. Of course, the situation is symmetrical for any starting guess you make.

What would this table look like if Monty always revealed a goat? Would any win or lose row be added or removed?

I know the result is right, but I don't think this table illustrates the reason.

You are not enumerating the options correctly. You have 3 rows for the GGC and GCG options but 4 for the CGG option, which is assigning the CGG option higher probability. In reality, they have equal weight.

Agh, you are right. There should be two “start over” rows in each of GGC and GCG. I can’t write “N/A;” we must say “yes/no” in those.

Doesn’t change the result though.

No, because the probability of a do-over depends on whether the contestant initially picked the door with a car.

At first I agreed with you, but then I thought about the variation with 100 doors (this is what originally helped me grasp the correct answer): you choose a door out of 100 (with very slim chance of choosing the correct one), the host opens 98 of the remaining 99 doors and there are goats behind all of them. Now it's obvious that the car is in the remaining door.

If the host is opening random doors, then: * If you chose a door with a goat, in 98/99 cases we would start the game over because the host opened the door with the car. * If you chose the door with the car, the game cannot start over because the host can only open doors with goats.

This means that when you choose a goat, the randomness gives you another chance to choose the correct door.

"Now it's obvious that the car is in the remaining door."

No. It could be behind the one you chose, surely.

I understand the explanations, or at least some of them; but I still don't get it. I thought I was intelligent and numerate, and this is making me sad.

I don't see why, after Monty reveals a goat and invites you to switch, you can't re-assess the probabilities from scratch. There are two closed doors, car behind one, goat behind the other, and you have no evidence which is which; therefore 50:50.

Yeah - and at least for me this was part of the confusion. The problem is often stated incorrectly.

Critically the host always removes a goat.

If the person presenting the problem just says “the host opens one of the doors”, but doesn’t specify he’s always revealing a bad door then it’s not clear why that matters.

The many door example makes it easy to intuit as well.

I think when stating the problem, some people assume the listener has actually watched Lets Make A Deal. You can under-specify the problem for people who have watched it, as the fact that Monty shows the worthless prize is already known.

That’s obvious. If he reveals the car, he isn’t going to ask you if you want to switch. A goat is a goat. It doesn’t matter to you which goat you get.

It’s not obvious if you think revealing the car ends the game (and you lose).

I think when I was first told it the person said “takes a door away” which is even less clear.

Years ago I challenged you on this and you suggested I write a simulation to check. I did just that and my understanding of the problem improved dramatically. That exchange made a pretty big impact on me and is something I think about fairly often, so thanks. :)

https://news.ycombinator.com/item?id=9079260

This made my week :)

I also wrote a simulation, in PHP, when I first encountered this problem.

  <?php
  $wins = 0;
  for ($i = 0; $i < 1000; $i ++)
   {
   $car = mt_rand(0, 2);
   $choose = mt_rand(0, 2);
   if ($choose == $car) $wins ++;
   }
  echo "stay: " . ($wins / 1000 * 100) . "%<br />";
  // switch
  $wins = 0;
  for ($i = 0; $i < 1000; $i ++)
   {
   $car = mt_rand(0, 2);
   $choose = mt_rand(0, 2);
   if ($choose != $car) $wins ++;
   }
  echo "switch: " . ($wins / 1000 * 100) . "%";

This is exactly why the Monty Hall problem doesn’t apply to Deal or No Deal. Intuitively, it disappears when doors are opened randomly because, by Bayes, the likelihood you picked the good prize goes up every time you reveal a bad prize.

This is always how I thought about it. The host is giving you more information about the 2/3 doors you did not choose, while the amount of information stays the same about the 1/3 door you did choose. It's this asymmetry that makes switching make sense.

I'll suggest we encountered the same class of inadvertent information sharing via a recent post to this forum, The Case of the 50ms request:

https://news.ycombinator.com/item?id=27053941

Having recognised (from crystallized experience) the nature of the problem from the very first hint, I went straight for the jugular at the first opportunity; any residual uncertainty about the diagnosis was extinguished by the wording of the answer prompt, which to my mild disappointment took all the drama out of the reveal.

Sadly, there was no automobile prize on offer. No, not even a goat.

The explanation that best helped me 'intuitively' understand things is to rephrase the game as being two separate games: choosing one of three doors, and after that having the option to go for a coin toss instead. Obviously you'd go for the coin toss.

Now I understand that the reason why that worked for me is precisely because it becomes much more clear that it's really about new information, and what tripped me up was trying to maintain a kind of 'narrative', I suppose?

I still don't think I really "get" it, but this explanation makes the most sense to me. Thanks!

Like of course I would switch and go for the coin toss, but I don't know how to convert that certainty into actually probabilities, tho I'm sure that the odds of my choices are not 1/3 versus 1/2, because there's probably some interplay.

If I think about it more I start to get confused again, along the lines of: does the first choice even matter then? and what if I reverse my first and second choices (as in I pick 1, then switch to 3, but what if I picked 3 then switched to 1), how can I still have better odds by switching, since there's only 1 right answer? But sticking with the coin toss, I feel, "OK this makes sense."

the first choice matters insofar that you can choose to stick with it, so while the coin toss in isolation is 50/50, for the game as a whole you need to consider the option of sticking with that initial 1 in 3 chance along side the 1 in 2 chance.

I like to think about this slightly differently: at first, you bet based on no information, and you know you’re probably wrong. In advance of the host helping out, though, you have no way to put money on your initial bet being wrong. (It’s like playing roulette — the casino is not going to give you even odds betting on two dozens, which would have almost 2/3 chance of being right.)

After the host helpfully takes a door out of play, though, you can bet that you were wrong, and the payout doesn’t change. You already knew you were probably wrong, and now you can bet on this. Of course it’s a good deal. A player can probably avoid the cognitive dissonance by thinking of their initial bet as being their best guess at finding a door that doesn’t have a car behind it.

This was one of the explanations that I find elucidating as well, but just now I realize that the change from 1/3 as an estimate to 1/2 is exactly the result of absorbing new information, which makes this explanation unsatisfactory.

Isn't he also removing relevant information as well? The third door is no longer part of the game so the information he gives you ceases to be relevant.

I don't think you can "remove" information from A probability problem in this way. And even if you could there's no reason to assume it would zero-sum with the later information gain.

Happy to be wrong though, been a long time since i dabbled in probably.

Reply on news.ycombinator.com