The Mosteller Hall Puzzle | Hacker News Reader

The Mosteller Hall Puzzle

jonathanweisberg.org

36 pointsgpresot27 comments

I don't understand why the given solution doesn't fall prey to the same problem of "her logic would make it unnecessary to consult the guard".

By this solution, if the guard says "B" (as in the original story), the probably of A being condemned goes up. But if the guard says "C", the probably also goes up by the same amount, because the graph is symmetric!

Going by this logic, if the guard is not allowed to say "A", then their answer doesn't matter. So why isn't the final probability still 1/3?

The final probability of A being released is indeed 1/3.

The second part of the article just attempts to nail down the specific fallacy in A's reasoning, which is also helpful in explaining the Monty Hall problem (which makes the guard's orders implicit rather than explicit)

I think it's the author's fault for switching between probabilities and odds and the readers for not recognizing the switch.

"Thus A’s chance of being condemned remains twice that of being pardoned."

When he says this, he is talking of odds of 2:1 and therefore, the probability of not being condemned is 1/1+2 = 1/3

Also when he says "Because, unlike in Monty Hall, the intuitive judgment is the correct one in Mosteller’s puzzle." He means the intuitive judgment that 1/2 is incorrect.

I was extremely confused the first 2-3 times I read it and kept trying to understand the author's viewpoint because everything other than these two statement seemed to make sense. At least I wasn't the only one.

I think a correct analysis of this problem requires you to know the guard's exact policy for what to say in every possible situation. The author has assumed that in the case that A is pardoned, the guard randomly chooses whether to answer "B" or "C" with equal probability, but we have no evidence for this.

Consider, for example, how you would analyze the situation where the guard says to A, completely unsolicited, "Hey, just so you know, B is still condemned to die."

On the one hand, it seems that the author's exact same analysis could be used in this situation: the guard's policy here might be exactly the same as it was in the original situation (where A asks the guard to name one of the other prisoners). On the other hand, perhaps the guard's policy was to only offer this information to A if A were pardoned. Or maybe the guard would have only said this if C were pardoned. We just don't know, so we can't calculate the probability that A is pardoned.

Yeah, looking at it with Bayes rule makes it sound more convincing. Here's what's assumed:

* The guard can't express whether or not A was pardoned to A.

* The guard is telling the truth.

Then the named (named to prisoner A) executed person E must be either B or C if A is saved. Let the saved person be S. Then:

    P(S=A|E=B) = P(S=A) P(E=B|S=A) / sum_{S in {A, B, C}}(P(S) P(E=B|S))

           = P(E=B|S=A) / (P(E=B|S=A) + P(E=B|S=B) + P(E=B|S=C))

           = P(E=B|S=A) / (P(E=B|S=A) +      0     +      1   )

As mentioned in the OP, if S=B then E=C and if S=C then E=B necessarily: both these events happen with equal probability. Then, as you mention with your intuition, if, say, the guard prefers to name B in the case of S=A, then hearing that E=B really does give you some information, since there is more probability mass in situations where you're saved when looking at the subset of events where E=B. Put extremely, taking P(E=B|S=A) = 1, we find that indeed P(S=A|E=B) = 1/2!

> a correct analysis of this problem requires you to know the guard's exact policy for what to say in every possible situation.

Just as with Monty Hall, where one ought to specify that the host knows exactly what's where, and always opens a remaining door such that it contains a goat (choosing uniformly if there's more than one such choice).

The nice thing about the variant in the article is that it is fairly well and intuitively specified.

(By the way, if the guard chooses B with probability x (rather than 1/2) in case A is pardoned, then the probability that A is pardoned is x/(1+x), which is between 0 and 1/2, but indeed is 1/3 only for x = 1/2.).

        A = A is pardoned
	etc.
	
	P(A) = P(B) = P(C) = 1/3
	
	
	SA = guard says A still condemned
	etc.
	
	P(SB | A) = x
	P(SB | B) = 0
	P(SB | C) = 1
	
	P(SC | A) = 1-x
	P(SC | B) = 1
	P(SC | C) = 0
	
	P(SA) = 0
	P(SB) = (1+x)/3
	P(SC) = (2-x)/3
	
	
	P(A | SB) = P(SB | A) P(A) / P(SB)
	          = x * 1/3 / (1+x) * 3 = x/(1+x)

This seems identical to the Monty Hall problem, except that the typical telling of the Monty Hall problem elides an important detail: that Monty knows which door conceals the car and intentionally always picks one that conceals a goat.

With that omitted (on Wikipedia [0], it's omitted in both the introduction to the page and the "canonical" reader's letter it quotes), people correctly conclude that their chance of winning doesn't go up by switching doors.

[0] https://en.m.wikipedia.org/wiki/Monty_Hall_problem

From the letter quoted at your link:

> You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat.

[Emphasis added.]

Right, but it doesn't say that he always picks one with a goat.

I think people would have a different response to the problem if before the host opened the door, the contestant said "Monty, can you please open one of the doors with a goat behind it?"

It is obvious. Why would he show the winning door? If he shows the winning door then the game is over and there is no reason to switch.

If one doesn't know the show, it's not obvious. Imagine an alternative universe in which the policy of the host is to open a random door (of the two remaining ones). Then, if it's a car, the show is over. If it's a goat, well, you can switch or not, doesn't matter.

The precise statement of the host's policy is fundamental to the whole problem, and it's these annoying vague formulations that lead to the endless discussions.

And that, in turn, is the nice thing about the Mosteller Hall Puzzle variation in the article: it makes the host/guard's policy very clear, and in fact so clear that one intuitively understands the damn problem.

> If one doesn't know the show, it's not obvious. Imagine an alternative universe in which the policy of the host is to open a random door (of the two remaining ones)

Yes, exactly. The wikipedia description is consistent with this alternative show. And if you say "that would make no sense as a game show", perhaps the contestant had to get through many other puzzles to get this far.

If you skip the comment "say No. 3", the formulation literally says "opens another door which has a goat."

That's still a little bit ambiguous. The problem statement mixes together the policy and the problem statement, and it's hard to tell which is which. Perhaps the policy is to pick a random door, but the problem statement specifies that it happens to contain a goat. In fact, I think the phrase "another door which contains a goat" technically means that the goat is coincidental, because of the difference between "which" and "that":

http://www.quickanddirtytips.com/education/grammar/which-ver...

So a better phrasing might be "opens a different door that has a goat".

That said, I suspect that most readers understand that the door was picked because it contained a goat.

It's not the same as the Monty Hall problem because the prisoner is not given a choice. If you are sure you know the answer to the Monty Hall problem and are a programmer then I suggest writing a little simulator to test your answer.

As far as I can see, it's identical to the Monty Hall problem, except slightly more precisely phrased in that the guard definitely does not reveal the name of the free prisoner, which is often a contentious point in these discussions (as it alters the probabilities).

It is structurally the same. With the wrong conclusion that A now has 1/2 chance of being pardoned, he'd be indifferent between remaining himself or rather being C.

With the (correct) conclusion that A still has 1/3 chance of being pardoned, and given that B has 0 chance of being pardoned, A would now rather "switch" with C, who has 2/3 chance of being pardoned. (That he doesn't have that choice doesn't matter.)

I didn't mean it was mathematically different, but the framing is sufficiently different to cause most people to miss the most interesting part. I was leaving out the correct conclusion so as not to spoil it for anyone.

I have shared the Monty Hall problem with people many times, and have always made explicit that the host knows which door the prize is behind and thus always intentionally choses a 'losing' door.

It has not yet stopped anyone I have tried it with from making the error that it doesn't matter whether they stick or twist.

Bit of a tangent here, but I don't get the relevance of the goat animated gif at the bottom of the article. Perhaps it was just for fun, or is there some deeper metaphor I'm missing?

In the Monty Hall problem, the bad outcome is opening a door and finding a goat -- https://en.wikipedia.org/wiki/Monty_Hall_problem

This is a puzzle that everyone gets intuitively, but formulating the error exactly is still a good learning exercise.

Maybe a good interview question?

I found it!! The elusive source of it all! Here, ladies and gentleman, you can see the birth of the exact thought:

"Hey I just read this really obscure article on something I've never heard of in school or used in my professional life, and didn't have to figure out for myself.

I bet it would make a great interview question."

You don't deserve the downvotes because that seems to be the exact thought process here: an interview is not about what the candidate can do, but how [s]he responds to weird gotchas.

I think questions along these lines are good questions if they're explicitly told that they aren't expected to know the answer or get it right.

For a counter intuitive question, I'd ask what their gut answer was first, and then see how they react to being told that it's wrong. Do they question the premise? Try to work it out? Ask you to explain? Waste time trying to prove that their answer was the right one? All of those things will give you an idea of what their personality is like. Ideally I'd want them to clarify the question to make sure they understood it, start trying to work it out with half remembered math from school, ask for some hints, and maybe get it right eventually, or at least wave in the general direction of how they think it could be solved. I don't care if they end up being totally wrong in the end, as long as they demonstrate some ability to think methodically.

Of course you could get similar information by asking them to troubleshoot a broken script or something like that. You'd probably be better off asking if they'd prefer a logic puzzle or a troubleshooting task.

No, unless familiarity with these problems is assumed to be mandatory.

People who inherently 'get' the Monty Hall problem on their first try are of course superior beings with a better intuitive grasp of everything (I kid, I kid) but using these sort of questions gives an enormous advantage to those who have seen it before. Unless you're testing for 'exposure to geek culture', I would avoid.

This wasn't the Monty Hall problem, though. The hypothetical interview question would be about putting something simple into words.

Reply on news.ycombinator.com