Coding Horror: Monty Hall, Monty Fall, Monty Crawl(codinghorror.com)
codinghorror.com
Coding Horror: Monty Hall, Monty Fall, Monty Crawl
http://www.codinghorror.com/blog/archives/001278.html
36 comments
I interpreted it the "wrong" way too. I thought about it like this: Instead of telling me that there is a girl or a boy tell me only that "1 + 1 = 2" and then ask me what the odds of the mothers child are for being a boy. I'll say 50%. I don't care what the state of some other child, I just care what the state of the unknown is. Now, if he had said, "you ask a woman that has a random assortment of children if she has at least 1 girl and she answers 'yes', what are the odds that the other is a boy" THEN I would be fine with the problem.
Paul's second algorithm, as stated, is exactly equivalent to the following:
1) Choose a random parent with exactly two children
2) If that parent has two boys, announce that they do not have two girls. If that parent has two girls, announce that they do not have two boys.
3) If that parent has a boy and a girl, randomly announce one of the above results.
It's easy to see that this has the same results as the first option. Counterintuitively, if that last step is nonrandom, you get the more intuitive result. Say, for example, that we did this:
1) Choose a random parent with exactly two children
2) Announce the gender of the eldest child.
This way, you get even odds that the other child is male or female. It's really counterintuitive, but that's how it works out.
1) Choose a random parent with exactly two children
2) If that parent has two boys, announce that they do not have two girls. If that parent has two girls, announce that they do not have two boys.
3) If that parent has a boy and a girl, randomly announce one of the above results.
It's easy to see that this has the same results as the first option. Counterintuitively, if that last step is nonrandom, you get the more intuitive result. Say, for example, that we did this:
1) Choose a random parent with exactly two children
2) Announce the gender of the eldest child.
This way, you get even odds that the other child is male or female. It's really counterintuitive, but that's how it works out.
Yudkowsky wrote a note about the same problem that cleared everything up for me: http://lesswrong.com/lw/ul/my_bayesian_enlightenment/
I'm always surprised by how the Monty Hall problem (and other similar problems, like the Bellhop and the missing dollar) messes people up. It's really terribly simple when you consider that Monty is adding information by acting non-randomly. The 3-door problem seems counter-intuitive to most people, so it is easier to imagine 10 doors-- after you choose, Monty opens 8 other empty doors, leaving one. It should be evident in this case that your choices are either a) to keep the original door, with a 1-in-10 chance of winning, or b) take the other 9 doors (8 of which are open) with a 9-in-10 chance of winning. Clearly, the winning move is to switch, and there's nothing counter-intuitive about it. People tend to let the details of the set-up get in the way of their seeing the structure of the problem. It's a cute puzzle, but it really shouldn't have confused Erdős.
I doubt Erdős was really confused. The Monty Hall problem is complicated because usually the person explaining it tries to make it complicated by leaving out necessary information. Specifically, they often leave out that Monty always opens an empty door and his choice of which empty door to open is done at random. Without those facts (which some but not all people take for granted) there is not enough information to solve the puzzle.
Why is Monty's choice of which empty door being random important? Isn't the fact that he always opens an empty door alone sufficient?
If you select the correct door, switching will yield an empty door.
If you select an empty door, switching will yield a prize.
You have a 2/3 chance of selecting an empty door, thus, 2/3 of the time, switching will grant you the prize.
If you select the correct door, switching will yield an empty door.
If you select an empty door, switching will yield a prize.
You have a 2/3 chance of selecting an empty door, thus, 2/3 of the time, switching will grant you the prize.
The reason it's important is that the problem, as usually phrased, is a conditional probability problem. Say you picked door number 1. Given that Monty opened door number 3 and it's empty, what's the probability you'll win by switching?
Now suppose that Monty will always open the empty door as advertised, but he will also always prefer to open a door with the smaller number, if he has a choice of two empty doors to open. If that is how Monty always acts, then given that he's opened door number 3, your probability to win by switching is 100%, and not the usual 2/3. If he's opened door number 2, then your probability to win by switching is 1/2, not the usual 2/3.
If Monty will always choose which of the two empty door to open by random, then the probability to win by switching is indeed 2/3.
There is a way to phrase the problem differently, so that it becomes an unconditional probability problem, and then it doesn't matter how Monty chooses the empty door to open. One way to enforce this interpretation is to phrase it as follows: Suppose some player always chooses to switch. Over many attempts, what will be the approximate proportion of his wins? The answer will be 2/3. But that's not how the problem is usually phrased.
Now suppose that Monty will always open the empty door as advertised, but he will also always prefer to open a door with the smaller number, if he has a choice of two empty doors to open. If that is how Monty always acts, then given that he's opened door number 3, your probability to win by switching is 100%, and not the usual 2/3. If he's opened door number 2, then your probability to win by switching is 1/2, not the usual 2/3.
If Monty will always choose which of the two empty door to open by random, then the probability to win by switching is indeed 2/3.
There is a way to phrase the problem differently, so that it becomes an unconditional probability problem, and then it doesn't matter how Monty chooses the empty door to open. One way to enforce this interpretation is to phrase it as follows: Suppose some player always chooses to switch. Over many attempts, what will be the approximate proportion of his wins? The answer will be 2/3. But that's not how the problem is usually phrased.
Oh, wow, you're completely right. That connection eluded me; thank you!
Why has no one phrased the answer like that before? That makes way more sense then talking about "adding information". I never grokked the solution until you described it that way.
Your logic is correct but you are a making a different assumption, that Monty treats each door symmetrically. For example let's say Monty's strategy is to always open door #3 if he has a choice. Then if your choice is to switch to door #3 or to stay, you should choose "stay".
When told of this, Paul Erdos, one of the leading mathematicians of the 20th century, said, "That's impossible." Then, when presented with a formal mathematical proof of the correct answer, he still didn't believe it and grew angry. Only after a colleague arranged for a computer simulation in which Erdos watched hundreds of trials that came out 2-to-1 in favor of switching did Erdos concede that he was wrong.
Can somebody please verify this from source, seriously !!
Can somebody please verify this from source, seriously !!
Sure.
It's the main subject of Chapter 6 of "The Man Who Loved Numbers: The Story of Paul Erdős and the Search for Mathematical Truth", by Paul Hoffman. He quotes Andrew Vázsonyi (who introduced the problem to Erdős) and Ronald Graham (who provided the proof that finally convinced Erdős).
It's the main subject of Chapter 6 of "The Man Who Loved Numbers: The Story of Paul Erdős and the Search for Mathematical Truth", by Paul Hoffman. He quotes Andrew Vázsonyi (who introduced the problem to Erdős) and Ronald Graham (who provided the proof that finally convinced Erdős).
Hey doesn't the Monty Fall problem also have the same answer as the Monty Hall problem - since the host falls and opens that door which always contains the goat, its same as saying that he knows which door contains the goat and opens that only.
Please correct me if I am wrong !
EDIT: Saw the soln in the pdf and not able to digest it though. Well if Erdos wasn't able to see it...
Please correct me if I am wrong !
EDIT: Saw the soln in the pdf and not able to digest it though. Well if Erdos wasn't able to see it...
Well, I think most of the confusion comes from the way that Rosenthal ignores a key part of the Monty Fall problem.
In the monty fall problem, you first choose a random door. Assuming a random placement of the car and a random guess, you should have a 1/3 chance of choosing the correct door on your first guess, and therefore a 1/3 chance of winning no matter what else happens.
I believe what's really happening in this example is that the Rosenthal is allowing for a possibility that he doesn't explicitly mention: the chance that the host opens the wrong door, nullifying the game and ruining the show.
Since there is a 1/3 chance that you picked the right door, it's a probability of 2/3 that it is in one of the other two doors. The host accidentally opens one of the two remaining doors. Since the host randomly chooses one of the remaining doors, the chance that he picks the door with the car is 1/3. If he does that, the game is invalidated, so Rosenthal ignores that result.
Therefore, the chance that you picked the correct door is 1/3, and the chance that the remaining door is the correct one is 1/3 (the remaining third is the chance that the host ruined the game). Since those are equal probabilities, you end up with an even chance whether or not you switch.
In the monty fall problem, you first choose a random door. Assuming a random placement of the car and a random guess, you should have a 1/3 chance of choosing the correct door on your first guess, and therefore a 1/3 chance of winning no matter what else happens.
I believe what's really happening in this example is that the Rosenthal is allowing for a possibility that he doesn't explicitly mention: the chance that the host opens the wrong door, nullifying the game and ruining the show.
Since there is a 1/3 chance that you picked the right door, it's a probability of 2/3 that it is in one of the other two doors. The host accidentally opens one of the two remaining doors. Since the host randomly chooses one of the remaining doors, the chance that he picks the door with the car is 1/3. If he does that, the game is invalidated, so Rosenthal ignores that result.
Therefore, the chance that you picked the correct door is 1/3, and the chance that the remaining door is the correct one is 1/3 (the remaining third is the chance that the host ruined the game). Since those are equal probabilities, you end up with an even chance whether or not you switch.
What's actually interesting is linking this result back to Deal or No Deal.
This implies that if you got down to two briefcases on the show, with both the $1,000,000 and $1 left, it's a 50/50 chance of picking the million dollar case whether you switch or not.
This implies that if you got down to two briefcases on the show, with both the $1,000,000 and $1 left, it's a 50/50 chance of picking the million dollar case whether you switch or not.
I'm confused about why people argue that it is not necessarily 2/3.
I assume that the sample space is: [(b,b),(b,g),(g,b),(g,g)] where the four possible birth sequences are [(younger child is boy, older child is boy), (younger child is boy, older child is girl), (younger child is girl, older child is boy), (younger child is girl, older child is girl)] and the sequences are all equally likely.
So now if you ask, what is the probability that the person has a girl and a boy given that at least one of them is a girl, you can discard (b,b) from your sample space because you know that there is at least one girl.
Now your sample space is [(b,g),(g,b),(g,g)] and the odds that the person has a girl and a boy are 2/3.
I assume that the sample space is: [(b,b),(b,g),(g,b),(g,g)] where the four possible birth sequences are [(younger child is boy, older child is boy), (younger child is boy, older child is girl), (younger child is girl, older child is boy), (younger child is girl, older child is girl)] and the sequences are all equally likely.
So now if you ask, what is the probability that the person has a girl and a boy given that at least one of them is a girl, you can discard (b,b) from your sample space because you know that there is at least one girl.
Now your sample space is [(b,g),(g,b),(g,g)] and the odds that the person has a girl and a boy are 2/3.
The way you phrase it - "given that one of them is a girl" - the answer is 2/3.
The people who argue that it is not 2/3 and yet aren't confused are choosing a different interpretation of the problem. When your acquaintance tells you "one of my children is a girl", they interpret it not as pure information, so to speak, but as an event to condition on.
It's reasonable to suppose, for example, that your acquaintance could have said "one of my children is a girl" or "one of my children is a boy", and used the actual knowledge of his children's gender to pick one of the two possibilities to say (choosing randomly if it's a boy or a girl). In that case, the question becomes: given that he/she said "... a girl" rather than "... a boy", what is the probability that it's a girl and a boy?
In that case, the sample space becomes larger: to (b,b) etc. add also B or G, which is whether the acquaintance said "one of my children is a boy" or "... a girl". The possibilities are:
b,b,B: 1/4 (b,b,G is impossible) g,g,G: 1/4 (g,g,B is impossible) b,g,B: 1/8 b,g,G: 1/8 g,b,B: 1/8 g,b,G: 1/8
Now if you condition this sample space on the event "G", you rule out exactly half the possibilities, and the answer is 1/2.
The people who argue that it is not 2/3 and yet aren't confused are choosing a different interpretation of the problem. When your acquaintance tells you "one of my children is a girl", they interpret it not as pure information, so to speak, but as an event to condition on.
It's reasonable to suppose, for example, that your acquaintance could have said "one of my children is a girl" or "one of my children is a boy", and used the actual knowledge of his children's gender to pick one of the two possibilities to say (choosing randomly if it's a boy or a girl). In that case, the question becomes: given that he/she said "... a girl" rather than "... a boy", what is the probability that it's a girl and a boy?
In that case, the sample space becomes larger: to (b,b) etc. add also B or G, which is whether the acquaintance said "one of my children is a boy" or "... a girl". The possibilities are:
b,b,B: 1/4 (b,b,G is impossible) g,g,G: 1/4 (g,g,B is impossible) b,g,B: 1/8 b,g,G: 1/8 g,b,B: 1/8 g,b,G: 1/8
Now if you condition this sample space on the event "G", you rule out exactly half the possibilities, and the answer is 1/2.
A reframing which makes intuitive sense (to me):
There are two bucket containing a number of balls. A third of the balls contain iPhones inside, two-thirds contain only navel-fluff. The balls are mixed at random. You have to chose a single ball from one of the buckets.
Obviously the chance of any ball you pick to contain an iPhone is 1/3 regardless of which bucket you choose from - even if the buckets does not contain the same number of balls.
But when you decide on one bucket to pick from, the host takes the other bucket, and removes half of the balls. However, he doesn't remove balls at random - he primarily removes balls containing fluff.
After this you are allowed to reconsider your choice of bucket. I think it is pretty obvious now that there is a better chance of finding an iPhone if you chose from the other bucket, where the host have removed some of the fluff-balls.
The critical point in the Monty Hall problem is that the host eliminates a bad choice, but he always eliminates it from the set of doors you didn't chose. However, this is a subtle detail in how the store is told. If for example the host randomly choose between opening any door containing a goat - including potentially the one the protagonist chose if he happens to choose a door with a goat behind - then it doesn't improve the odds to choose a different door.
There are two bucket containing a number of balls. A third of the balls contain iPhones inside, two-thirds contain only navel-fluff. The balls are mixed at random. You have to chose a single ball from one of the buckets.
Obviously the chance of any ball you pick to contain an iPhone is 1/3 regardless of which bucket you choose from - even if the buckets does not contain the same number of balls.
But when you decide on one bucket to pick from, the host takes the other bucket, and removes half of the balls. However, he doesn't remove balls at random - he primarily removes balls containing fluff.
After this you are allowed to reconsider your choice of bucket. I think it is pretty obvious now that there is a better chance of finding an iPhone if you chose from the other bucket, where the host have removed some of the fluff-balls.
The critical point in the Monty Hall problem is that the host eliminates a bad choice, but he always eliminates it from the set of doors you didn't chose. However, this is a subtle detail in how the store is told. If for example the host randomly choose between opening any door containing a goat - including potentially the one the protagonist chose if he happens to choose a door with a goat behind - then it doesn't improve the odds to choose a different door.
In fact, it is immensely important that the problem states that Monty Hall always reveals a losing door. If the problem merely states a particular series of events without specifying the rules -- as both Jeff's problem statement and Marilyn's problem statement do -- you can't know the probabilities.
Suppose, for example, that Monty has the policy of only revealing a losing door if the player has chosen the winning door; if, on the other hand, the player initially chooses a losing door, then Monty reveals no door and makes no offer to switch, sticking the player with the loss. In that case, if you encounter the same sequence of events in Jeff's problem description, then switching always has zero chance of winning. With the opposite assumption -- that Monty only reveals a losing door if the player has initially chosen a losing door -- switching always has a 100% chance of winning.
Both Jeff and Marilyn nevertheless press forward with the unstated assumption that Monty has no choice in the matter. It turns out that this assumption is not only faulty, but it's also unrealistic: on the actual game show, Monty was under no such obligation.
I'm a little surprised that Jeff, who apparently has read up a little on the topic, didn't bother to grab the much better problem specification from the Wikipedia article.
Suppose, for example, that Monty has the policy of only revealing a losing door if the player has chosen the winning door; if, on the other hand, the player initially chooses a losing door, then Monty reveals no door and makes no offer to switch, sticking the player with the loss. In that case, if you encounter the same sequence of events in Jeff's problem description, then switching always has zero chance of winning. With the opposite assumption -- that Monty only reveals a losing door if the player has initially chosen a losing door -- switching always has a 100% chance of winning.
Both Jeff and Marilyn nevertheless press forward with the unstated assumption that Monty has no choice in the matter. It turns out that this assumption is not only faulty, but it's also unrealistic: on the actual game show, Monty was under no such obligation.
I'm a little surprised that Jeff, who apparently has read up a little on the topic, didn't bother to grab the much better problem specification from the Wikipedia article.
Good point. The paradox is not the math per se, but rather that the rules the host follows are unintuitive not to mention unrealistic. When these rules furthermore is not stated explicitly, it is not surprising that even seasoned mathematicians gets tricked.
Everyone agrees that your odds get better. Most people intuitively guess that the odds go from 1/3 to 1/2. It's getting them to understand how you got to 2/3 that's the problem.
[deleted]
I found the easiest way was this:
You pick door A, the host opens door B or C and offers to let you switch to door C or B. He is effectively letting you choose between either A alone (by sticking) or B & C together (by switching) - i.e. by switching you open two doors instead of one, hence twice the probability.
I've found that the most enlightening explanation is to increase the number of doors. What if the game is played with 100 doors, and the host opens 98 of them after you've chosen yours? At the start you only have a 1% chance of winning. Most people see right away that the host can't be increasing the odds to just 50% by opening so many doors. They don't always see the logic immediately, but at least they begin to question their intuition. Getting people to admit that they might be wrong is often the first step toward getting them to accept the correct answer. (That last sentence is a general observation that applies to a much wider range of problems.)
From the Jeffrey Rosenthal paper that Jeff Atwood suggests
(http://www.probability.ca/jeff/writing/montyfall.pdf):
<Quote>
Nebulous Neighbours:
Your new neighbours have two children of unknown gender. From older to younger, they are equally likely to be girl-girl, girl-boy, boy-girl, or boy- boy. One day you catch a glimpse of a child through their window, and you see that it is a girl. What is the probability that their other child is also a girl?
Solution.
The probabilities that a glimpsed child will be a girl for each of the four possi- bilities (girl-girl, girl-boy, boy-girl, and boy-boy) are respectively 1, 1/2, 1/2, and 0. Since the probabilities must add to 1, the probabilities of these four possibilities are respectively 1/2, 1/4, 1/4, and 0. Hence, the probability is 1/2 that the other child is also a girl.
</Quote>
Can someone explain how glimpsing to one child and seeing that is a girl is different from hearing the parent saying that one child is a girl? How come and getting the same information from your eyes instead of your ears changes the probabilities? (1/2 for the other child to be a boy when seeing, 2/3 when hearing).
<Quote>
Nebulous Neighbours:
Your new neighbours have two children of unknown gender. From older to younger, they are equally likely to be girl-girl, girl-boy, boy-girl, or boy- boy. One day you catch a glimpse of a child through their window, and you see that it is a girl. What is the probability that their other child is also a girl?
Solution.
The probabilities that a glimpsed child will be a girl for each of the four possi- bilities (girl-girl, girl-boy, boy-girl, and boy-boy) are respectively 1, 1/2, 1/2, and 0. Since the probabilities must add to 1, the probabilities of these four possibilities are respectively 1/2, 1/4, 1/4, and 0. Hence, the probability is 1/2 that the other child is also a girl.
</Quote>
Can someone explain how glimpsing to one child and seeing that is a girl is different from hearing the parent saying that one child is a girl? How come and getting the same information from your eyes instead of your ears changes the probabilities? (1/2 for the other child to be a boy when seeing, 2/3 when hearing).
Seeing vs hearing is a red herring.
What really matters is whether information about one child being a girl fixes a particular child. It doesn't matter how the child is fixed (a popular variation is "I have two chilren and the older one is a girl"), but it does matter that out of the two children, it is now known about a specific one of them that it is a girl. In that case, out of 4 possibilities, 2 are ruled out, and the answer is 1/2.
If all that is known is that one of the children is a girl, only one possibility out of 4 is ruled out, and the answer is 2/3.
What really matters is whether information about one child being a girl fixes a particular child. It doesn't matter how the child is fixed (a popular variation is "I have two chilren and the older one is a girl"), but it does matter that out of the two children, it is now known about a specific one of them that it is a girl. In that case, out of 4 possibilities, 2 are ruled out, and the answer is 1/2.
If all that is known is that one of the children is a girl, only one possibility out of 4 is ruled out, and the answer is 2/3.
"If all that is known is that one of the children is a girl, only one possibility out of 4 is ruled out, and the answer is 2/3."
Well, that's the case when you glimpse from the window. Probably I'm wrong but I don't see why there is a fix, you still don't know if you see a G in GB or in BG or in GG
Well, that's the case when you glimpse from the window. Probably I'm wrong but I don't see why there is a fix, you still don't know if you see a G in GB or in BG or in GG
The difference is in how the information got revealed (whether it was seen or heard is irrelevant). In the case where you saw the girl, it completely specifies the gender of the child you saw and unspecifies the gender of the unseen child. (Intuitively: suppose you know the family has four children, and you peek in the window and see that three of them are girls. What's the probability of the fourth being a girl? 1/2.)
The case where you are told the family has at least one girl is potentially different... It depends on how you get this information. If you ask the parent, "Do you have at least one girl?" and they say yes, then the probability of the other child being a girl is 1/3. On the other hand, if you ask the parent, "What can you tell me about your children?" and they say "I have at least one girl", then the probability of the other child being a girl is 1/2. The difference is that in the second case, the parent chooses which child to reveal information about, while in the first case, they are forced to make a combined statement about both children. In the second case, the parent completely reveals the gender of the chosen child while unspecifying the gender of the other, just as good as seeing the chosen child in the window.
Obviously, most people who describe the boy-girl problem are interested in describing the non-intuitive 1/3 result. But in their rush to reveal the "paradox", many state the problem poorly, leaving open the possibility of the 1/2 case (as Jeff did when he presented the problem).
(I added a similar response with more details in the Wikipedia article discussion several months ago: http://en.wikipedia.org/w/index.php?title=Talk:Boy_or_Girl_p... I must warn, however, that the concluding paragraph there is incorrect: Jeff's problem is fundamentally undecidable as stated.)
The case where you are told the family has at least one girl is potentially different... It depends on how you get this information. If you ask the parent, "Do you have at least one girl?" and they say yes, then the probability of the other child being a girl is 1/3. On the other hand, if you ask the parent, "What can you tell me about your children?" and they say "I have at least one girl", then the probability of the other child being a girl is 1/2. The difference is that in the second case, the parent chooses which child to reveal information about, while in the first case, they are forced to make a combined statement about both children. In the second case, the parent completely reveals the gender of the chosen child while unspecifying the gender of the other, just as good as seeing the chosen child in the window.
Obviously, most people who describe the boy-girl problem are interested in describing the non-intuitive 1/3 result. But in their rush to reveal the "paradox", many state the problem poorly, leaving open the possibility of the 1/2 case (as Jeff did when he presented the problem).
(I added a similar response with more details in the Wikipedia article discussion several months ago: http://en.wikipedia.org/w/index.php?title=Talk:Boy_or_Girl_p... I must warn, however, that the concluding paragraph there is incorrect: Jeff's problem is fundamentally undecidable as stated.)
"If all those Ph.D.s are wrong the country would be in serious trouble."
Yes. And yes.
Yes. And yes.
[deleted]
Monty Crawl: if you pick the 1st door and the host opens the 3rd door, you have 100% chance to win if you switch.
Yes. But if picks the second door, it no longer matters whether you switch or not.
Your final probability in Monty Crawl is still only winning 2/3, because you can't do better than an always switch strategy, and you will pick the winning door initially 1/3 of the time.
Your final probability in Monty Crawl is still only winning 2/3, because you can't do better than an always switch strategy, and you will pick the winning door initially 1/3 of the time.
Can anyone confirm this article by Atwood is worth looking at?
Here Atwood links to a very insightful blog post by Paul Buchheit: http://paulbuchheit.blogspot.com/2009/01/question-is-wrong.h...
To continue the quote:
"...but it was a simple question asked in simple language."
Yes, a simple question, with two perfectly valid interpretations, as described by Buchheit. When I first read the question, I interpreted it the "wrong" way. The simple language that is used to ask the question is too simple, to the point of not being specific.
"I think what they're really objecting to is how unintuitive the answer is."
No sir. I am in fact objecting to the wording.