The Monty Maul Problem
post by JGWeissman · 2009-06-24T05:30:16.760Z · LW · GW · Legacy · 5 commentsContents
5 comments
In his Coding Horror Blog, Jeff Atwood writes about the Monty Hall Problem and some variants. The classic problem presents the situation in which the game show host allows a contestant to choose one of three doors, one of which opens to reveal a prize while the other two reveals goats. The host then opens one of the other doors, reliably choosing one that has a goat, and invites the contestant to switch to the remaining unopened door. The problem is to determine the probability of winning the prize by switching and staying. The variants deal with cases in which the host does not reliably choose a door with a goat, but happens to do so.
Jeff cites Monty Hall, Monty Fall, Monty Crawl (PDF) by Jeff Rosenthal, which explains why the variants have different probabilities in terms of the "Proportionality Principle", which the appendix acknowledges to be a special case of Bayes' Theorem.
One of Jeff's anonymous commenters presented the Monty Maul Problem:
Hypothetical Situation:
The Monty Maul problem. There are 1 million doors. You pick one, and the shows host goes on a bloodrage fueled binge of insane violence, knocking open doors at random with no knowledge of which door has the car. He knocks open 999,998 doors, leaving your door and one unopened door. None of the opened doors contains the car.
Are your odds of winning if you switch still 50/50, as outlined by the linked Rosenthal paper? It seems counter-intuitive even for people who've wrapped their head around the original problem.
If you take as absolute the problem's statement the host is randomly knocking doors open, then yes, the fact that only goats were revealed is strong evidence that only goats were available because you picked the door with the prize, which, when combined with the low prior probability that you picked the door with the prize, gives equal probability to either of the unopened doors having the prize.
However, the fact that only goats were revealed is also strong evidence that the host deliberately avoided opening the door with the prize, and therefor switching is a winning strategy. After all, the probability of this happening if the host really is choosing doors randomly is 2 in a million, but it is guaranteed if the host deliberately opened only doors with goats.
Note that this principal still applies in variants with fewer doors. Unless there is an actual penalty for switching doors (which could happen if the host only sometimes offers the opportunity to switch, and is more likely to do so when the contestant chooses the winning door), any uncertainty about the host choosing doors randomly implies that it is a good strategy to switch.
5 comments
Comments sorted by top scores.
comment by Vladimir_Nesov · 2009-06-24T14:12:48.456Z · LW(p) · GW(p)
However, the fact that only goats were revealed is also strong evidence that the host deliberately avoided opening the door with the prize, and therefor switching is a winning strategy.
This is an important point for, say, thinking about what to do if a quantum random bit turned the same 1000 trials in a row. The theory doesn't promise "chaotic" random sequences, a sequence that repeats the same outcome is as normal as any other. On the other hand, the repetition sequence could happen for some other reason, and it's this alternative possible reason that makes the sequence special, not the default hypothesis where the "strange" sequence is ordinary.
comment by Annoyance · 2009-06-24T20:03:01.930Z · LW(p) · GW(p)
I'm told that game theorists often have arguments over a similar sort of situation:
In a competitive game with another person, it's often necessary to assume that they'll behave rationally in order to determine what your best strategy is. (If they'll choose randomly and erratically, the nature of the rules might make it impossible to determine which of the options is better.)
But what about the cases where there are, say, two strategies which are equally good if the opponent is rational but only one of which is better if they act irrationally? Is it consistent, some argue, to both assume that the opponent will be rational and to say that the one strategy is better?
I say that human beings can screw up, and the second option lets you hedge your bets without risking or losing anything. So there's potential benefit but no potential cost, so you should not view the two as equally good.
comment by Optimus · 2009-07-10T09:05:54.352Z · LW(p) · GW(p)
I have recently read another quiz that help me understand either the maul problem or what was the meaning of the description of the monty fall problem (that begged a lot of people because there was misunderstanding in the description).
There are 10000 people buying lotery tickets. Only one wins. You get your own. Of course all are getting randomly their ticket. You keep your ticket and wait for the others to reveal if they won. One after one scratches his ticket and looses. After 9998 it's you and another guy who happened to not have scratched his ticket yet. Nobody has revealed a winner yet.
You'd say based on the original Monty Hall problem that you have 1/10000 probability to stay and now you have 9999/10000 to switch. But it's the same for the other remaining person to switch with you. How can it be if the possibilities doesn't add to 1?
Because it's just 1/2. Of course the revealing of the tickets prize one by one is not done deliberately by choosing the loosing one (Monty Hall). It's done randomly (Monty Fall). But another way to understand it is this: From your side you have 1/10000 possibility to contain the ticket. What is the possibility that after randomly revealing one by one the other 9999 tickets, they won't find the winner in the middle, either in 2347th ticket or 4344th ticket or 8500th ticket, etc? It's damn small that someone of the 9999 people have the ticket and has not been choosen already after 9998 other tickets revealed. This possibility of this happen (that he still has the winning ticket and not being revealed) is as small as the posibility that you are the one who have the winning ticket. It comes down to 50% either I guess but if I am wrong you can correct. I only wanted to show how it's possible and why it explains the paradox of the monty maul problem.
Actually I had a problem with the definition of Monty Fall problem (that he chooses randomly yet he is too luck to get a goat and not reveal the car). It's incomplete. I think this is one of the reasons why there is confusion with this version of the problem on the internet.
What many people think: "There is randomness but somehow magically happens that always he gets lucky and get a goat" but I think what they meaned in the problem is "There is a possibility that monty selects randomly a car and then something happens (the show is cancelled, the players looses) and those are the rules. Let's say that with those rules you play once the show and monty randomly selects the goat and gives you the opportunity to switch".
So randomly selecting a goat is just one of the many runs. In other runs he can select the car. Most people discard those car reveal cases as not valid and say that it's like we arrive back at the old problem, all of our cases are only goat revealing, so it has to be 2/3. Some while having this collection of random incidents always revealing a goat in their mind, yet they accept the 1/2 sollution and then you know what they think? "WOW! Same exactly data, yet only because monty doesn't know or thinks different the probability changes. Wicked! Super Quantum Thought Manipulation!!! Crazy!". Which is not. The Monty Fall does not describe the same set of collected data as the original Monty Hall. It wants (but doesn't) say that the car can be selected, it's a valid case (and something happens but they don't tell us), but it happens that in the current run it has selected a goat but not all runs.
I believe the confusion in the Monty Fall is because it's misleading or not descriptive enough. It's not the same as the first problem which is straight forward imho.
comment by Cyan · 2009-06-25T17:48:09.898Z · LW(p) · GW(p)
The Monty Crawl variation is interesting. If you have to pick an unchanging strategy for a large number of trials, always switching wins two thirds of the time. But in any particular trial, after Monty opens a door you either know with certainty that switching wins (one third of the time), or switching and sticking are both 50:50 (two thirds of the time).
comment by SoullessAutomaton · 2009-06-24T10:48:13.182Z · LW(p) · GW(p)
One way to look at versions of this problem that involve the host "randomly" opening doors, none of which happen to contain the car, is that this is implicitly eliminating probability mass by discarding cases where one of the randomly opened doors does contain the car.
In the 3 door case, if you pick door 1, there are three possible locations for the car (C1, C2, C3). The host then randomly opens one of the two remaining doors (H2, H3). Each of the six possible combinations is equally likely, but C2+H2 and C3+H3 are implicitly eliminated because in those combinations, the car is revealed and the game ends.
The remaining four cases are C1+H2, C1+H3, C2+H3, and C3+H2. Obviously in this case your odds are 50/50 regardless. More significantly, your overall odds remain 1/3, because of the eliminated cases. The same logic applies to cases with more doors, where all combinations of C1+H? remain under consideration, while only one combination involving each other car position remains in play.
This differs from the classic statement of the problem because when the host never opens a door with the car, he does not eliminate any of the probability mass for "you picked the wrong door", thus concentrating the likelihood of "you picked the wrong door" onto a single door, which gives the usual counterintuitive result.
But yes, if you know that the host always opens a door and offers to let the player switch, switching will never make you do worse than not switching. If you don't know this, there is insufficient information to decide on a strategy.