Remember The Problem of the Unfinished Game? And the almost 2,500 comments those two posts generated? I know, I like to pretend it didn't happen, either. Some objected to the way I asked the question, but it was a simple question asked in simple language. I think what they're really objecting to is how unintuitive the answer is.
Which reminds me of another question that you've probably heard of:
Suppose the contestants on a game show are given the choice of three doors: behind one door is a car; behind the others, goats. After a contestant picks a door, the host, who knows what's behind all the doors, opens one of the unchosen doors, which reveals a goat. He then asks the contestant, "Do you want to switch doors?"
Should the contestant switch doors?
This is, of course, the Monty Hall problem. It's been covered to death, and quite well I might add, by dozens of writers who are far more talented than I.
What's interesting about this problem, to me at least, is not the solution, but the vehemence with which people react to the solution – as described in The Drunkard's Walk: How Randomness Rules Our Lives.
It appears to be a pretty silly question. Two doors are available – open one and you win; open the other and you lose – so it seems self-evident that whether you change your choice or not, your chances of winning are 50/50. What could be simpler? The thing is, Marilyn said in her column that it is better to switch.Despite the public's much-heralded lethargy when it comes to mathematical issues, Marilyn's readers reacted as if she'd advocated ceding California back to Mexico. Her denial of the obvious brought her an avalanche of mail, 10,000 letters by her estimate. If you ask the American people whether they agree that plants create the oxygen in the air, light travels faster than sound, or you cannot make radioactive milk by boiling it, you will get double-digit disagreement in each case (13 percent, 24 percent, and 35 percent, respectively). But on this issue, Americans were united: Ninety-two percent agreed Marilyn was wrong.
Perhaps the public can be forgiven their ignorance, but what of the experts? Surprisingly, the mathematicians fare little better.
Almost 1,000 Ph.D.s wrote in, many of them math professors, who seemed especially irate. "You blew it," wrote a mathematician from George Mason University. From Dickinson State University came this: "I am in shock that after being corrected by at least three mathematicians, you still do not see your mistake." From Georgetown: "How many irate mathematicians are needed to change your mind?" And someone from the U.S. Army Research Institute remarked, "If all those Ph.D.s are wrong the country would be in serious trouble." Responses continued in such great numbers and for such a long time that after devoting quite a bit of column space to the issue, Marilyn decided she whould no longer address it.The army PhD who wrote in may have been correct that if all those PhDs were wrong, it would be a sign of trouble. But Marilyn was correct. 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.
You may recognize Paul Erdos from a particularly obscure XKCD cartoon last week. So if you feel like an idiot because you couldn't figure out the Monty Hall problem, take heart. The problem is so unintuitive one of the most notable mathematicians of the last century couldn't wrap his head around it. That's ... well, that's amazing.
How can something that seems so obvious be so wrong? Apparently our brains are not wired to do these sorts of probability problems very well. Personally, I found the text of Jeffrey Rosenthal's Monty Hall, Monty Fall, Monty Crawl (pdf) to be the most illuminating, because it asks us to consider some related possibilities, and how they might affect the outcome:
Monty Fall Problem: In this variant, once you have selected one of the three doors, the host slips on a banana peel and accidentally pushes open another door, which just happens not to contain the car. Now what are the probabilities that you will win, either by sticking with your original door, or switching doors?Monty Crawl Problem: Once you have selected one of the three doors, the host then reveals one non-selected door which does not contain the car. However, the host is very tired, and crawls from his position (near Door #1) to the door he is to open. In particular, if he has a choice of doors to open, then he opens the smallest number available door. (For example, if you selected Door #1 and the car was indeed behind Door #1, then the host would always open Door #2, never Door #3.) Now what are the probabilities that you will win the car if you stick versus if you switch?
Paul Erdos was brilliant, but even he realized his own limits when presented with the highly unintuitive Monty Hall problem. For his epitaph, he suggested, in his native Hungarian, "Végre nem butulok tovább". This translates into English as "I've finally stopped getting dumber."
If only the rest of us could be so lucky.
@BA:
"By concluding that all combinations of of boy and girl are equally likely you are making a statistical fallacy in assuming that a randomly selected subset has the same properties as the superset."
Umm, no. By concluding that the PROBABILITY of an outcome in a small sample is equal to the outcome in a large sample you are assuming that there is no small-sample bias. This is not a statistical fallacy, but instead the underlying assumption in most statistic-based calculations.
The question was not, at all, "What is the gender of the other child?". It was: what is the probability that the other child is a boy.
To run into your issue, we'd have had to state that there are four families each with two kids. Family 1 has two girls; family 2 has a boy and a girl; family 3 has two boys; family 4 has what? And then answer "a boy and a girl"with no margin of error. THAT would be a subset-superset fallacy, or more precisely, a failure to keep account of statistical error.
More interestingly, though, you do have a point on family size. Consider the social impacts of a male-dominant society crossed with a small-family-size inclination. If the main goal of having children was to have a boy to "carry on the family name", a lot of families would stop after their first boy was born. Thus, a large portion (we'll say all just to deal in round numbers) of the families with 2 children had a girl first, which means that the likelihood of having two girls is 50%. This type of information completely changes the problem space by reducing the possible outcomes.
Tom Dibble on June 22, 2009 10:25 AMWell, it's pretty simple actually. You only lose if you initially chose the car, and that has a 1/3 chance of happening, so the other 2/3 chances are of you winning.
Ricardo on June 22, 2009 10:28 AMHere's a model of the situation in C. Over 100,000 iterations, it shows that by switching from the first choice to a new choice, the player wins in 2/3rds of the games.
#include
#include
int main (int argc, const char * argv[]) {
int doors[3];
int playerChoice;
int hostChoice;
int iterations;
int wins;
iterations = 0;
wins = 0;
for (int i = 0; i 100000; ++i) {
// Reset doors
doors[0] = 0;
doors[1] = 0;
doors[2] = 0;
// Place the car behind a random door
doors[rand() % 3] = 1;
// Choose a door for the player
playerChoice = rand() % 3;
// Choose a door for the host that is not the player's door and does
// not contain the car
hostChoice = playerChoice;
while ((hostChoice == playerChoice) || (doors[hostChoice] == 1)) {
hostChoice = rand() % 3;
}
// Switch player choice to new door
int choiceMask = 1 playerChoice;
choiceMask |= (1 hostChoice);
int newChoice = (7 - choiceMask) / 2;
// Did we get the right door?
if (doors[newChoice] == 1) {
wins++;
}
iterations++;
}
printf("Iterations: %d Wins: %d Ratio %f\n", iterations, wins, (double)wins / (double)iterations);
return 0;
}
I couldn't believe there was a sentence in my native language. It took me a second to switch back. :)
pestaa on June 22, 2009 10:43 AM@Practicality:
I don't even remember where we disagreed. Anyway....
There's a pretty big anti-vaccine movement which is believed to be causing a resurgence in diseases which were once thought to be all but eradicated in developed countries. The movement stems from a belief that components of the vaccines cause autism.
If you search Google for the two words (vaccines and autism), you'll see a bunch of links. What's most damning is http://www.time.com/time/health/article/0,8599,1888718,00.html -- since it's a celebrity claiming it, people identify with her. Because they identify with her, they believe her over people with whom they do not identify (faceless scientists.)
sadnessbowl on June 22, 2009 10:43 AM@Troy- One of the choices *was* the door that Monty opened. After he opens it, it's no longer a choice. It's just that the door Monty opens depends on the door you open. He can't open the door you opened, and he can't open the door with a car; 2/3 of the time, that accounts for two separate doors, and he can only open the one non-car non-chosen goat door, leaving the non-chosen non-Monty door the car door. 1/3 of the time, he has a choice of goats, because you have the car- and then it really doesn't matter which one he opens, because if you switch, you lose.
The only false part about a "choice" is assuming that Monty has a choice. If the reveal-and-switch is mandatory (as it wasn't in Let's Make A Deal), then Monty only has a choice 1/3 of the time- the situation in which his choice doesn't matter.
Windrider on June 22, 2009 10:47 AMIf you choose a goat on your first guess,
the host can't open your door,
so he has to pick the other wrong choice.
Therefore, the remaining door has a more likely chance
of being the car. (THE HOST ONLY HAS 1 CHOICE)
If you choose a car on your first guess,
the host can pick either of the two
wrong choices (THE HOST HAS 2 CHOICES)
"One more quiz:
There's a game called Chuck-a-Luck (aka Crown and Anchor) that's played on midways. The rules are simple. There are three dice kept in an hour glass cage. The cage is turned over and the three dice are rolled.
You bet on a number 1 to 6, and if that number comes up, you get paid even odds. That is, if you bet a dollar, you win a dollar. (You get two dollars back: The dollar you won, and your initial dollar you bet). That sounds very fair. The possibility of a number coming up on a die is 1:6 times. Since there are three numbers, the possibility must be 3 x 1/6 or 1/2 time. Even odds. Right?
However, the dealer gives a bit of a bonus: If two of the dice land on your number, you get double your money. If all three dice land on your number, you get triple your money! How can you lose?
But, lose you will. What is the actual odds of winning in this game?"
Interesting case. I'm not going to run down the full set of probabilities, but the trick of the game is in the double- and triple-roll dice.
Imagine a $1 bet on each of the sides. If all three come up differently, the banker pays back $6 and takes in $6. If all three come up on $1 the lucky sod who bet there gets $4 back (his original plus three payouts) while taking in $6 as always.
So, take the likelihoods of 2 dice coming up the same and the likelihood of all three dice coming up the same and compare those to the likelihood of all three being different and you have the deviation from "even".
You could look at the same game with 2 4-sided dice or 4 8-sided dice and plot the unfavorability of it ... Obviously 1 die/2-sides and you're at a coin toss (which is an even game), so I'd guess the favorability to house would steadily increase with the number of die and sides.
Tom Dibble on June 22, 2009 10:51 AM@Jon Skeet: +1
"Simple" questions are the ones that trouble the most by being ambiguous. IMO. YMMV.
@Anonymous - you should have posted your name. This comment did it for me...
>it's a 33/33/33 choice and you drop one -- how does that not make it a 50/50 choice?
There was a 0.33 chance you picked the right door in the first place. Probabilities have to add up to 1, so there's a 0.66 chance that you win if you switch.
Anonymous on June 22, 2009 8:01 AM
The way I usually explain this to others is like this: Instead of choosing one door, you choose two, but then *tell* Monty that you chose the other. If one of the two doors you chose contains the price (that is 66.666% of the time), Monty will now tell you which one of the two it is.
LKM on June 22, 2009 11:00 AMStop making it more enigmatic than it needs to be.
Try it again but considering one more thing.
Suppose the contestants on a game show are given the choice of three doors: behind one door is a car; behind the others, goats. After a contestant picks a door, the host, who knows what's behind all the doors, opens one of the unchosen doors, which reveals a goat. He then asks the contestant, "Do you want to switch doors?"
Solve it considering this :
The host know where is the car and will never reveal it. He will always open a door that he know contain a goat.
The original never said that the host knew what was behind the door, or if he had to open a door.
When the Monty Hall problem was updated to say that the host had to make a decision and that the host knew what was behind the doors, then we have a complete different proof.
Math and logic are not the same thing. We must be very careful on how we word our problems.
I have noticed (personal experience, not a scientific study)that most programmers fall into one of two categories: mathematicians or logicians. The two different types code very differently.
The point is that each type thinks that their code is self-documenting, while in fact it is only self documenting to that type of programmer.
We must be careful on how our code reads.
Actually, "Deal or No Deal" is not at all like the Monty Hall problem. If the host of DoND asks if you want to switch at the end when it's down to 2 cases (does he do that?) you're no better off switching or not switching.
Joe on June 22, 2009 11:10 AMAfter reading the pdf, it is clearer to me why math professors have this problem. It is about probabilities, not mathmatical equations. Probabilities involve equations, but probabilities are not representative of measurable things.
AC on June 22, 2009 11:12 AMI'm surprise no one has mentioned the agnostic mindset (there might be a better term for this but agnostic will have to do for the placeholder).
If the two sensibilities are switching doesn't hurt and switching helps I might as well switch even if I don't believe it will help as it will help if I'm wrong and will make me look better to those that believe if I'm right.
In other words the possibilities are:
A. I switch and am more likely to win
B. I switch and it doesn't change my odds but people think I'm smarter for taking the option that might increase my odds.
No matter the wording of the question if the choices boil down to switching helps or switching is dead even then my choice is simple.
Unless someone warns me of a wording where switching hurts my odds I'm not going to worry much about the different variations.
dhanson865 on June 22, 2009 11:16 AMAUTHOR: BG
DATE: 06/22/2009 10:17:00
?php
// The Monty Hall Simulator
// editable settings
$debug = 0;
$switchanswer = 1; // toggle 0 or 1 to enable answer switching
$iterations = 1000; // number of times to run the simulation
// begin uneditable settings and code
$wins = 0;
$loss = 0;
$numcorrect = 0;
$numincorrect = 0;
$choices = array(0, 1, 2);
$i = 1;
while ($i = $iterations) {
if ($debug) { print "--------\n"; }
$answer = mt_rand(0,2);
if ($debug) { print "A: ". $answer ."\n"; }
$guess = mt_rand(0,2);
if ($debug) { print "G: ". $guess ."\n"; }
if ($switchanswer) {
if ($guess == $answer) {
// If the contestant picks the right door, the host will open one of the other two doors, both of which are incorrect
// 1/3 chance of guessing correctly on first shot
// This leaves the correct door (chosen) and 1 remaining incorrect door. By always switching, the contestant will always lose.
// Remove the user's guess from the choices
$newchoices = array_diff($choices, array($guess));
//if ($debug) { print_r($newchoices); }
// Randomly select from the remaining choices
$newguess = array_rand($newchoices);
//if ($debug) { print_r($newguess); }
//if ($debug) { print "\n"; }
// Make this their guess
$guess = $newguess;
if ($debug) { print "NG: ". $guess ."\n"; }
$numcorrect++;
} else {
// If the contestant picks the incorrect door, the host will open the remaining incorrect door.
// 2/3 chance of guessing an incorrect door on first shot
// This leaves the incorrect door (chosen) and the correct door. By always switching, the contestant will always win.
// pick correct answer
$guess = $answer;
if ($debug) { print "NG: ". $guess ."\n"; }
$numincorrect++;
}
}
// Results check
if ($answer == $guess) {
$wins++;
if ($debug) { print "Correct!\n"; }
} else {
if ($debug) { print "Sorry, incorrect!\n"; }
$loss++;
}
$i++;
}
// Results Tally
if ($switchanswer) {
print "The contestant always chose to switch their answer\n";
} else {
print "The contestant always stayed with their original answer\n";
}
print "Out of ". $iterations ." iterations, there were ". $wins ." wins and ". $loss ." losses.\n";
printf("Win %%: %.2f\n", $wins/$iterations);
printf("Loss %%: %.2f\n", $loss/$iterations);
?
BG on June 22, 2009 11:18 AMOur full possibility set:
33% #1{Car, Goat, Goat}
33% #2{Goat, Car, Goat}
33% #3{Goat, Goat, Car}
For simplicity sake, we'll assume that the guesser always chooses the first door. As is hopefully obvious, the chance of winning on the first choice is 1/3
We'll also assume the host is not an interested agent in this -- He doesn't care if you win or lose, he's just following a script. There are three possible cases allowed by most phrasings of the question. One: He opens a door entirely at random. Two: He opens a door he knows contains a goat. Three: He always picks the same door. We will also assume that he will never open the picked door in this question. (If you need help deciding to switch when the host shows that you have already picked the car, then your needs are beyond my capabilities.)
- Case one: True Random Pick -
33% #1a{Car, *Goat, Goat}(16.7%) : #1b{Car, Goat, *Goat}(16.7%)
33% #2a{Goat, *Car, Goat}(16.7%) : #2b{Goat, Car, *Goat}(16.7%)
33% #3a{Goat, *Goat, Car}(16.7%) : #3b{Goat, Goat, *Car}(16.7%)
If the door is chosen entirely at random, you have an equal chance that he shows you the car, you HAVE the car already, or the last door (neither shown nor picked) is the car. He didn't show you the car (eliminating #2a and #3b) and that leaves an equal choice of whether or not you should switch.
- Case Two - Known Goat Pick -
33% #1a{Car, *Goat, Goat}(16.7%) : #1b{Car, Goat, *Goat}(16.7%)
33% #2{Goat, Car, *Goat}(33%)
33% #3{Goat, *Goat, Car}(33%)
In this case, we have removed the host's choice as a random factor in two of the three base scenarios. The key here is that the 33% split is still valid. #1(a+b)=#2=#3. You have a 33% chance that you picked right (and should not switch) and a 67% chance that you picked wrong (and should).
- Case Three - Always Opens Door Two -
33% 1a{Car, *Goat, Goat}
33% 2{Goat, *Car, Goat}
33% 3{Goat, *Goat, Car}
Same as a random pick, only with fewer options. If he shows you a car, you're lost either way. If he shows you a goat, it's 50:50.
--
In summary, you should always switch. If you are dealing with Case One or Three, it won't make a difference. If you are dealing with Case Two, you will be better off for it. There are no cases where switching lowers your odds of car ownership. (Assuming, of course, that the host is not acting maliciously by only giving you the option when you've already picked correctly)
Trevel on June 22, 2009 11:21 AMIt seems that about 1/3rd of the commentators here believe that it matters if Monty Hall picks the one he knows doesn't have the car, or picks at random, the fact is that it doesn't matter since the problem states that the door opened didn't have the car behind it, whether this is due to prior knowledge, or just chance, you are still better off switching.
Refer to the chart on http://www.marilynvossavant.com/articles/gameshow.html and realize that there are some possibilities that are not listed, i.e. the door revealed by the host has the car behind it. Why is it not listed? Because we are told that he opened the door and there was a goat behind it. Whether these original potential outcomes are no longer possible by the time the question is posed is due to the host's knowledge or his luck, it doesn't matter.
Kearns on June 22, 2009 11:21 AMSee, the Monty Hall problem was easy for me to get my head around. The Unfinished Game however took me a long time, I argued vehemently with my friend about it, and ultimately decided a computer simulation would prove him wrong.
Even while coding it up I realized my mistake in logic, but I finished it anyway and conceded defeat. If I can't manage to do it through mathematics, simulation seems to always fix my thoughts (and upon reading "finishing the game" computer simulation was your method too, I feel like I'm awesome now)
aterimperator on June 22, 2009 11:23 AM"Marilyn is wrong, and her logic is flawed."
People who argue this point have obviously never actually sat down and tried to simulate this problem at all. Take the time to simulate it using cards and you will quickly see the error of your ways.
I think what this post shows is that people will argue anything to death even when it has been previously announced that there is nothing worth arguing about.
Just let it go people. If you want to argue the Monty Hall problem go somewhere else. Proving/disproving the Monty Hall problem is not the point of this blog post.
Matt on June 22, 2009 11:30 AM@Kearns - Commentators believe that it matters whether or not the host reveals a door purposefully or accidentally because the paper Jeff links to explicitly states that this is so. Are you arguing that the paper is incorrect?
aux on June 22, 2009 11:31 AMSuppose there are three doors: A, B and C.
Without loss of generality, let us assume the contestant picks A.
Let us enumerate the possibilities:
The car is in A, the host opens B, the contestant sticks with A and wins.
The car is in A, the host opens B, the contestant changes to C and loses.
The car is in B, the host opens C, the contestant sticks with A and loses.
The car is in B, the host opens C, the contestant changes to B and wins.
The car is in C, the host opens B, the contestant sticks with A and loses.
The car is in C, the host opens B, the contestant changes to C and wins.
There are 3 win cases and 3 lose cases. In 2 of the three win cases, the contestant switched to the other door.
QED.
Elongar on June 22, 2009 11:35 AMOh Lord. Not again. Please! The last set ruined my January.
As before, I side with Marilyn, but now I refuse to be drawn into explaining why. It's a redundant exercise trying to persuade people, because either you get it or you don't:
http://www.codinghorror.com/blog/archives/000781.html
Tobermory on June 22, 2009 11:35 AMChoice Prize Reveal Should Switch?
1 1 2 No
1 1 3 No
1 2 3 Yes
1 3 2 Yes
2 1 3 Yes
2 2 1 No
2 2 3 No
2 3 1 Yes
3 1 2 Yes
3 2 1 Yes
3 3 1 No
3 3 2 No
I keep looking, and it still looks like 50-50 to me.
Ah, but suppose you pick a door, then Monty Hall falls down, and starts crawling. Meanwhile, one hidden goat gets bored, hops in the car, and takes it for a spin. He totals the car, but manages to drive it back, smoking and sputtering, and parks it behind a door. Not the same door it was behind before, the other door. The goat gets back behind the unoccupied door.
Finally Monty opens a door. It's the goat that didn't leave. You can win either a totalled car, or a goat smart enough to drive said car and bring it back. NOW should you switch doors?
Keep in mind that this is just what I came up with, and may be incorrect.
Monty Fall: Assuming that Monty will always open a door that is both unselected and does NOT contain the car, the probability distribution does not change. By ruling out the possibility of him opening the chosen door and/or revealing the car, the problem is reduced back to its original state.
Monty Crawl: For the game as a whole, switching doors still doubles the player's chances of winning. However, the player is *guaranteed* to win if they switch doors after Monty has opened the highest-numbered remaining door. Otherwise, the player's choice does not affect the outcome.
I'd like to propose a value, M, in a similar vein to the Erdos number.
M is the log(base 10) of the number of minutes it took you to be convinced that changing is the best tactic in the Monty Hall Problem.
I have an M of 2.08
Before Monty helps
1/3 picking right door
Monty helps:
Monty will open either door, since they're both wrong
Stay = Win
Switch = Lose
2/3 picking wrong door
Monty helps:
Monty has "2" choices - the 'right' door and wrong
Alas, Monty is forced into opening the 'wrong'
Stay = Lose
Switch = Win
1/3 of the time (initial scenario) switching WILL result in a loss
2/3 of the time switching WILL win.
@Stephen Oberholtzer + 1
@Robert B + 1
Switching the door increases the possibility, tested with a simulation code.
I like to think of it this way:
If you pick a goat, Monty will reveal the other goat. Switching will win you the car.
If you pick the car, then Monty will reveal one of the goats. Switching will get you the other goat.
You have 2/3rds chance of picking a goat.
Matt Brunell on June 22, 2009 11:55 AMI like the Monty Maul example. Mostly for entertainment value.
Practicality on June 22, 2009 11:56 AMThe best way to understand the Monty Fall Problem is to change it slightly.
Monty Fall Problem: In this variant, once you have selected one of 1,000,000 doors, the host slips on a banana peel and accidentally pushes open all remaining 999,998 doors except one, all of which just happen not to contain the car. Now what are the probabilities that you will win, either by sticking with your original door, or switching doors?
You can see if you stick with your originally door, you only have a million in one chance of winning. If you switch you have 99.9999% chance of winning.
After you get over your initial amazement at Monties luck of *randomly* opening 999,998 doors without accidently opening the one that contains the car, you wisely switch doors.
WhatAreTheOdds? on June 22, 2009 12:03 PMNote that this sort of error isn't completely behind us yet - or at least it isn't very far behind us. It was recently discovered that psychological researchers have been making the same mistake for years on a problem equivalent (isomorphic?) to the monty hall problem. See http://blog.noblemail.ca/2008/04/combinatorics-debunks-psychology.html
Steven H. Noble on June 22, 2009 12:12 PM@WhatAreTheOdds
>The best way to understand the Monty Fall Problem is to change it slightly.
No, this is the _worst_ way to understand the "Monty Fall" problem, because you're absolutely wrong. If the host slips on a banana and randomly pushes open all 999,998 doors except your door and one other, you're chances are _exactly the same_ whether you switch or not. In the original problem, it is the host's _knowledge of the what's behind the doors_ that renders switching the better option. It doesn't matter if the host randomly opens a million trillion doors randomly, your odds don't change if he doesn't happen to reveal the car. The reason is that by virtue of the terms of the question, you are discounting all scenarios where a car is revealed, whereas in the original question you didn't have to discount any scenarios, because the host will never reveal a car, as he knows where the car is.
I find it easier explaining to people with an example of 10 (or 100) doors.
Say you pick the first. 1/10 of the cases you are right, 9/10 you are wrong.
Now the host cancells doors 2-9. 1/10 you were right before, 9/10 - the car is behind door #10.
Much easier for people to grasp.
A D&D d10 or d20 can also help do the trick.
The interesting thing about this problem is not its solution but the reason why most people's intuition is wrong. In fact, I believe that it is due to the way that probability is taught in schools and universities.
There are two common interpretations of probability theory: the frequentist interpretation and the Bayesian interpretation. The former is usually taught in schools (though this may be changing), and starts with abstract axioms, e.g., a probability space is defined as "Given any set Omega, (also called sample space) and a sigma-algebra F}, on it, a measure P, defined on F, is called a probability measure if P(Omega)=1." - this is where you start building you intuition... (from wikipedia, but my old probability theory book is similar)
Edwin Jaynes was a firm believer in the Bayesian interpretation and his book "Probability theory: the logic of science" gives compelling arguments (a "beta" version is even available online). Most importantly his presentation of probability as an extension of classical Aristotelian logic is the most intuitive explanation of probability theory I have ever seen (i.e., no abstract concepts from measure theory). While the book requires a good amount of mathematical maturity in some of its arguments in the later chapters, reading just the basic chapters was very enlightening. Interestingly it turns out that the Bayesian methods are even more powerful than the classical frequentist methods. This comment is long enough, I'll post a more detailed explanation on my blog for those interested.
/Karl
Karl Krukow on June 22, 2009 12:16 PMFor more insight listen/view the TED talk by Dan Ariely "Are we in control of our own decisions", available on the TED website.
Tathagata on June 22, 2009 12:19 PMI think mostly these questions (and especially these comments) demonstrate that most programmers need to take a writing class.
Seriously. Omit needless words. These explanations are so unclear it is difficult to determine whether the commenter is saying he agrees, he disagrees or that he wants to bring out some other point entirely.
Captcha: mural PXTCHOGUE (Is this thing Russian?)
Practicality on June 22, 2009 12:21 PMThe Monty Fall Problem does make a difference! The odds are only 1:3. That's because, the host is not supplying you with any information. It's as if Monty doesn't know which door has the prize and simply opens a random door himself. For example, imagine the prize is behind Door #1. There are six EQUAL possibilities (the fact that all possibilities are equal is important):
1). I pick Door #1, Monty opens Door #2
2). I pick Door #1, Monty picks Door #3
3). I pick Door #2, Monty opens Door #1
4). I pick Door #2, Monty opens Door #3
5). I pick Door #3, Monty opens Door #1
6). I pick Door #3, Monty opens Door #2
Notice I would lose if I switched in either situation #1 or #2. Also, notice I would win in situation #4 or #6.
However, in situations #3 and #5, I would lose whether or not I switched simply because Monty already revealed the prize (and I assume I am not allowed to switch to Monty's door). Thus, out of the six possibilities, I can only win 1:3 times.
But, you say, that's not the problem. The problem states that Monty opened a RANDOM door, but that still didn't reveal the prize. Wouldn't switching help you there? Answer is no. What we have now are four out of six possibilities to contemplate:
1). I pick Door #1, Monty opens Door #2
2). I pick Door #1, Monty picks Door #3
4). I pick Door #2, Monty opens Door #3
6). I pick Door #3, Monty opens Door #2
We threw out situations #3 and #5 because in those two, Monty revealed the prize. As you can see, there are four situations. Switching would make me lose in situation #1 and #2, but win in situation #4 and #6. In otherwords, switching is even odds. Considering the original 1:3 choice, switching doesn't improve or harm my odds. The odds are still 1:3.
So, why was the original Monty Hall problem favorable when you switched? Because the host was giving you information. The hose knew which door had the prize and gave you that information. Here are the six possibilities:
1). I picked Door #1, Monty opens Door #2
2). I picked Door #1, Monty opens Door #2
3). I picked Door #2, Monty is thinking of picking Door #1, remembers the prize is behind it, so picks Door #3 instead.
4). I picked Door #2, Monty picks Door #3.
5). I picked Door #3, Monty is thinking of picking Door #1, remembers that the prize is behind it, so picks Door #2
6). I picked Door #3, Monty picks Door #2.
Notice that situation #3 and situation #4 look identical, but aren't. Monty didn't randomly open a door, he specifically opened the door without the prize. Now, thanks to this new information, I can improve my odds.
It's like the problem of the friend with two children.
Friend: One of my two children is a boy.
What are the odds of both kids being boys? 1:3
Friend: My oldest child is a boy.
What are the odds of both kids being boys: 1:2. By supplying me with extra information, I can eliminate the possibility that the youngest is a boy, but the oldest is a girl.
I have to work out the Monty Crawl problem, however, I believe the odds are still better if I do switch. What they are is impossible to say without some work. But, there are certain situations where switching guarentees me a prize. For example, if Monty opens Door #3, switching guarentees me the prize. (I pick Door#1, Monty picks Door #3 because the prize is behind Door#2. I pick Door #2, Monty picks Door #2 because the prize is behind Door #1).
David W. on June 22, 2009 12:21 PMWhatAreTheOdds?
Of the two doors remaining after Monty's crazy fall, each has a 50% chance of being the door with the car. I recommend switching anyways, but in the Randomly Opened Door scenario, the choices are equal.
For N doors, there is 1 possibility where your door is correct, N-1 where another door is. Each possibility is equally weighted.
If someone knocks open all the doors except for yours and one other, there are n-2 scenarios where one of the doors shown will hold a car, and 2 that they will not. There is 1 where your door holds a car, and 1 where the remaining door does. The n-2 scenarios are discarded as no car is found, leaving 1 where you have the car already, and 1 where you do not. It is an equal choice.
--
If someone knowingly opened all the doors except for yours and one other, then there is 1 scenario where your door holds a car, and n-1 where the other doors do not. You have an advantage in switching that increases with larger values of n.
Knowledge matters.
The n-2/n chance can be discarded, as no car is shown.
Trevel on June 22, 2009 12:22 PMIgnore the last line in my last post -- I thought I'd deleted it.
Trevel on June 22, 2009 12:23 PMSheesh.
Please stop posting nonsense unless you have a mathematical proof backed up by some rigorous computer modelling.
Go read some beginner statistical analysis and come back in a year.
http://mathforum.org/library/drmath/sets/select/dm_coin_tossing.html
Frogger on June 22, 2009 12:25 PMI didn't believe it either... until I coded it - here is my Java contribution:
import java.util.Random;
public class Test {
static Random r = new Random(System.currentTimeMillis());
int goodDoor = -1;
int guessDoor = -1;
int revealDoor = -1;
public Test() {
goodDoor = r.nextInt(3);
guessDoor = r.nextInt(3);
// This step is, technically, not required.
revealDoor = getRevealDoor();
}
// True if we guessed correctly at the start.
// Otherwise, false (which means we would have been right
// had we switched)
public boolean guess() {
return goodDoor == guessDoor;
}
// Identify a door that is neither the guess door, nor the correct door
public int getRevealDoor() {
while (true) {
int testDoor = r.nextInt(3);
if (testDoor != goodDoor && testDoor != guessDoor) {
return testDoor;
}
}
}
public static void main( String[] args ) {
int switchingWins = 0;
int notSwitchingWins = 0;
for( int i = 0; i 10000000; i++ ) {
Test t = new Test();
if( t.guess() ) {
notSwitchingWins++;
}
else {
switchingWins++;
}
}
System.out.println( "Switching Wins = " + switchingWins );
System.out.println( "Not Switching Wins = " + notSwitchingWins );
}
}
I can understand why people really believe it should 50% and why switching should not matter. This game is really about choosing between one of two options, switch or not, so it is pretty much 50-50.
However...
That is NOT what is being asked in this problem. The *question* is should you switch doors after your initial choice. The answer is YES. For heaven's sake people, computer simulations confirm these results. I'm very sorry most of you people have an inability to understand this.
By the way, I saw mention of Deal or No Deal (DoND). While DoND is not the same as the Monty Hall problem, they are similar in that if you make it to the end of the game you *should* switch suitcases.
Here's the reason, and maybe, JUST MAYBE, this will help illustrate the Monty Hall problem. The reason you should switch cases in DoND is that you have a 1 in 26 chance of choosing the million dollar suitcase. Does that sound like good odds? So, if you make it to the end of the game there is a 25 in 26 chance that the model's suitcase contains the million dollar prize.
Get it now? With the Monty Hall problem you have a 2 in 3 chance of being wrong. If you are wrong then Monty Hall is *actually* telling you the door with the car.
Nicholas on June 22, 2009 12:31 PMWow I can't believe this post is close to 100 comments already... I really recommend The Drunkard's Walk, it's excellent - and contains a nice variant to the Monty Problem.
"in a family with 2 children, what are the chances, if one of the children is a girl named Florida, that both children are girls?".
It's not as trivial as it seems...
The simplest way to understand this is to imagine there are two goats. These goats have been fed a diet primarily consisting of alfalfa. Alfalfa (Medicago sativa) is a flowering plant in the pea family Fabaceae cultivated as an important forage crop. In the UK, Australia, and New Zealand it is known as lucerne and as lucerne grass in south Asia.
Alfalfa is a cool season perennial legume living from three to twelve years, depending on variety and climate. It resembles clover with clusters of small purple flowers. The plant grows to a height of up to 1 metre (3 ft), and has a deep root system sometimes stretching to 4.5 metres (15 ft). This makes it very resilient, especially to droughts. It has a tetraploid genome. The plant exhibits autotoxicity, which means that it is difficult for alfalfa seed to grow in existing stands of alfalfa. Therefore, it is recommended that alfalfa fields be rotated with other species (for example, corn or wheat) before reseeding.
Like other legumes its root nodules contain bacteria, Sinorhizobium meliloti, with the ability to fix nitrogen, producing a high-protein feed regardless of available nitrogen in the soil. Its nitrogen-fixing abilities (which increases soil nitrogen) and its use as an animal feed greatly improved agricultural efficiency. (The nitrogen comes from the air, which is 78 percent molecular nitrogen.)
Alfalfa is widely grown throughout the world as forage for cattle, and is most often harvested as hay, but can also be made into silage, grazed, or fed as greenchop. Alfalfa has the highest feeding value of all common hay crops, being used less frequently as pasture. When grown on soils where it is well-adapted, alfalfa is the highest yielding forage plant.
Alfalfa is one of the most important legumes used in agriculture. The US is the largest alfalfa producer in the world, but considerable area is found in Argentina (primarily grazed), Australia, South Africa, and the Middle East. Known as Kuthirai Masal in Tamil, alfalfa is mostly grown in the Coimbatore district of Tamil Nadu, southern India.
Within the U.S.A. the leading alfalfa growing states are California, South Dakota, and Wisconsin. The upper Midwestern states account for about 50% of US production, the Northeastern states 10%, the Western states 40% and the Southeastern states almost none. Alfalfa has a wide range of adaptation and can be grown from very cold northern plains to high mountain valleys, from rich temperate agricultural regions to Mediterranean climates and searing hot deserts.
Its primary use is as feed for dairy cattle—because of its high protein content and highly digestible fiber—and secondarily for beef cattle, horses, sheep, and goats. Humans also eat alfalfa sprouts in salads and sandwiches. Tender shoots are eaten in some places as a leaf vegetable. Human consumption of fresh mature plant parts is rare and limited primarily by alfalfa's high fiber content. Dehydrated alfalfa leaf is commercially available as a dietary supplement in several forms, such as tablets, powders and tea. Alfalfa is believed by some to be a galactagogue, a substance that induces lactation.
Meanwhile the car was produced by the automotive industry. The automotive industry designs, develops, manufactures, markets, and sells the world's motor vehicles. In 2007, more than 73 million motor vehicles, including cars and commercial vehicles were produced worldwide.
In 2007, a total of 71.9 million new automobiles were sold worldwide: 22.9 million in Europe, 21.4 million in Asia-Pacific, 19.4 million in USA and Canada, 4.4 million in Latin America, 2.4 million in the Middle East and 1.4 million in Africa. The markets in North America and Japan were stagnant, while those in South America and Asia grew strongly. Of the major markets, Russia, Brazil, India and China saw the most rapid growth.
About 250 million vehicles are in the United States. Around the world, there were about 806 million cars and light trucks on the road in 2007; they burn over 260 billion gallons of gasoline and diesel fuel yearly. The numbers are increasing rapidly, especially in China and India. In the opinion of some, urban transport systems based around the car have proved unsustainable, consuming excessive energy, affecting the health of populations, and delivering a declining level of service despite increasing investments.[citation needed] Many of these negative impacts fall disproportionately on those social groups who are also least likely to own and drive cars. The sustainable transport movement focuses on solutions to these problems.
In 2008, with rapidly rising oil prices, industries such as the automotive industry, are experiencing a combination of pricing pressures from raw material costs and changes in consumer buying habits. The industry is also facing increasing external competition from the public transport sector, as consumers re-evaluate their private vehicle usage. Roughly half of the US's fifty one light vehicle plants are projected to permanently close in the coming years with the loss of another 200,000 jobs in the sector, on top of the 560,000 jobs lost this decade.
Monty Hall was the host of the game show Let's Make a Deal, which he developed and produced with partner Stefan Hatos. Let's Make a Deal aired on NBC daytime from December 30, 1963 to December 27, 1968 and on ABC daytime from December 30, 1968 to July 9, 1976, along with two primetime runs. It also aired in syndication from 1971 to 1977, from 1980 to 1981, from 1984 to 1986, and again on NBC briefly from 1990 to 1991. He was producer or executive producer of the show through most of its runs. During the show's initial run, Hall became well known alongside model Carol Merrill and announcer Jay Stewart.
Monty Hall started his career in Toronto in Radio. Early in his career, Hall hosted such game shows as Bingo At Home and guest-hosted more established game shows such as Strike It Rich before hosting the first show of his own, Keep Talking in 1958. He succeeded Jack Narz as host of a well-received and unique game show called Video Village, which ran in 1960-1962 on CBS. On Video Village, contestants played on a giant game board consisting of three sections: Money Street, Bridge Street and Magic Mile. Players advanced with the roll of a large die. The further contestants advanced along the board, the better the prizes that were offered. A spinoff called Video Village Junior, featuring youngsters, was hosted by Hall and ran during the 1961-1962 regular television season. The first show he ever hosted was Bingo At Home. In 1962, with co-producer Art Stark, Hall sold his first game show to NBC, Your First Impression, which ran for two years. Stefan Hatos was the Producer of that show, and eventually, he and Hall formed a production company which is still running. Hatos died in 1999. Besides Let's Make a Deal, the game show Split Second which originally ran on ABC from 1972-75, and again in syndication in 1987 (with Hall also hosting that version) was the only other successful program from Hatos-Hall Productions. Other game shows from their production company included Chain Letter in 1966; a revival of the venerable 1950s-era panel quiz, Masquerade Party in 1974; 3 For the Money in 1975; It's Anybody's Guess in 1977, which reunited Let's Make a Deal announcer Jay Stewart with Hall, who also hosted the show, and the Canadian-based The Joke's on Us in 1983. Hall filled in as guest host on several daytime game shows while Let's Make a Deal was on NBC, most notably What's This Song? and PDQ. In 1979, Hall hosted the only game show since Video Village which he did not produce — Goodson-Todman's All-New Beat the Clock.
Hall received a star on the Hollywood Walk of Fame on August 24, 1973, a star on the Palm Springs Walk of Fame in 2000, and in 2002, he was also inducted into Canada's Walk of Fame. Hall is one of only two game show hosts on both Hollywood's and Canada's Walks of Fame, the other being Alex Trebek. In May 1988, the Government of Canada bestowed on him the prestigious Order of Canada for his humanitarian work in Canada and other nations of the world. For many years, he has been associated with Variety, the Children's Charity, helping to raise millions of dollars through their telethons and other related fund-raisers.
Hall was the recipient of the 2005 Ralph Edwards Service Award from Game Show Congress, in recognition of all the work the emcee-producer has done for charity through the years.
Hall graduated from the University of Manitoba, where he majored in chemistry and zoology, receiving his Bachelor of Science degree.
He has been married for many years to his wife, Marilyn, and has two daughters — actress and Tony Award winner Joanna Gleason and Sharon Hall, a television executive — and one son, Richard Hall, a television producer.
In addition to his work on game shows, Hall was a radio analyst for the New York Rangers of the National Hockey League during the 1958-60 season. Between 1956 and 1960, Hall worked as a host of NBC Radio's "Monitor" weekend broadcast. At least one recording of Hall on "Monitor" is known to exist.
Although retired, Hall still makes occasional television appearances. He played the host of a beauty pageant who schemed to become "the world's most powerful game show host" in the Disney animated series American Dragon: Jake Long. Monty appeared on GSN Live on March 14, 2008, and hosted a game of Let's Make a Deal for Good Morning America on August 18, 2008 as part of Game Show Reunion week.
In "The Monty Hall Problem," the player, having chosen a door, has a 1/3 chance of having the car behind the chosen door and a 2/3 chance that it's behind one of the other doors. It is assumed that when the host opens a door to reveal a goat, this action does not give the player any new information about what is behind the door he has chosen, so the probability of there being a car behind a different door remains 2/3; therefore the probability of a car behind the remaining door must be 2/3. Switching doors thus wins the car with a probability of 2/3, so the player should always switch.
max on June 22, 2009 12:35 PM@Nicholas:
Sigh. You're completely wrong. In DoND, you're selecting suitcases at random, so the Monty Hall problem is completely inapplicable. In the Monty Hall problem, the extra information comes from the host *knowing* which door the car is behind, and acting accordingly. In DoND, no-one knows which suitcase contains the million bucks. If you're lucky enough to get to the end, you can switch or you can stick, your odds are identical either way (50/50). If you don't believe me, look at the "Monty Fall" problem, either in the paper Jeff linked to or on the wiki page for Monty Hall.
moya on June 22, 2009 12:37 PMAs a poker player I always like explaining this problem using a poker analogy.
Imagine I approach you and offer to play a special game. I've got three cards, two kings and one ace. I shuffle these cards, deal one randomly to you and I get the other two. You're not allowed you look at your card. But I look at my two, pick one and discard it. Now how much are you willing to bet that your card beats my card? Remember you can't look at your card before betting. If we played 100 hands of this game betting the same every time do you think you would come out even?
It hardly takes a professional poker player to understand this is a losing proposition.
I think part of the reason this problem is so hard is because our minds tend to not start at the 'beginning' of the problem. We need to consider the probability of the first choice.
My 'proof':
When you make your first choice, you have a 2/3 chance of being wrong.
If your first choice is wrong and you choose the second door, your SECOND AND FINAL choice will be right. So switching doors for your second choice means you will be right 2/3 of the time. Q.E.D.
Asa on June 22, 2009 12:39 PM@Gabriel I started to see the light
@Gareth made it all clear. So simple
I am going to call this thread "The Monty Hall Problem Problem".
@seth
Be careful, because Gabriel's assertion that it doesn't matter whether or not the host reveals a door randomly is completely false.
moya on June 22, 2009 1:00 PM@moya
I don't believe that analysis of the Monty Fall problem is correct. Consider writing a simulation. The only time the Monty Fall simulation results would be different from the normal Monty Hall case is when Monty randomly chooses the door with the car. However the problem explicitly states that we're excluding those cases; we're only calculating the probabilities of the two options given that we know he has selected a door with a goat. The results are identical to the Monty Hall problem.
Chris (ctcarton.at.gmail) on June 22, 2009 1:00 PM@moya
I don't believe that analysis of the Monty Fall problem is correct. Consider writing a simulation. The only time the Monty Fall simulation results would be different from the normal Monty Hall case is when Monty randomly chooses the door with the car. However the problem explicitly states that we're excluding those cases; we're only calculating the probabilities of the two options given that we know he has selected a door with a goat. The results are identical to the Monty Hall problem.
Chris (ctcarton.at.gmail) on June 22, 2009 1:01 PM"How many irate mathematicians are needed to change your mind?"
I am reminded of a quote where someone was asked a similar question (sadly, can't remember who) - "if I were wrong it would only take one".
This is very relevant to programming issues - the problem of not being able to see the obvious real world implications of your design (that the host must choose a door with a goat) and then trying to defend a bad result by saying the specification should have been mentioned it.
Paul Coddington on June 22, 2009 1:08 PMWhy the hell did you reopen this can of worms?
Here come a thousand posts complete with math and program examples to *prove* they are correct. I like you less.
Matt on June 22, 2009 1:09 PMOk, nevermind. I worked out the math and came up with the 50/50 probably if monty chooses randomly. Ignore my last post! :)
Chris (ctcarton.at.gmail) on June 22, 2009 1:13 PMHasn't the Monty Hall thing been beaten to death sufficiently by the billion other blog posts about it? Did you know how many E.T. cartridges were buried in a landfill...blah blah blah.
Anyone who feels the need to post a comment questioning this needs to just shut up, stop yapping, and just read up on it. And if it's new to you, you must be new to the web.
Dennis Forbes on June 22, 2009 1:14 PM@Chris
The fact that we discard the cases where Monty reveals a car is the crucial point.
If you try it yourself with a deck of cards, two kings and an ace, you'll see it makes no difference whether you switch or stick. When you pick randomly to "reveal" a second door, around 1/3 of the time you'll reveal the ace. When you discount these times, the ace will be the original card half the time and the last card half the time. i.e., of the 2/3s of the time you don't reveal the ace, half (1/3) of the time your original guess was correct, and half (1/3) of the time the last card it the ace.
The mistake in your logic comes from misunderstanding the terms of the question:
>The only time the Monty Fall simulation results would be different from the normal Monty Hall case is when Monty randomly chooses the door with the car. However the problem explicitly states that we're excluding those cases
"We will discard those times when he reveals the car" does not mean the same thing as "he will always reveal a goat" - if it did, he wouldn't be picking a door at random! Although we're only dealing with those cases where he doesn't reveal the car, we still have to *consider* the fact that he could have revealed a car - similar to "Finishing the Game"
moya on June 22, 2009 1:15 PMI found this video helpful on explaining the Monty Hall problem: http://www.youtube.com/watch?v=mhlc7peGlGg&NR=1
Lucas McCoy on June 22, 2009 1:19 PMThis is one of the many examples people should be shown over and over again until they learn to stop trusting their intuition! It is ALMOST ALWAYS WRONG! I would wager that almost all suffering in the world boils down to people refusing to ignore their intuition and deal with things rationally. We've got parents putting their children in mortal danger by not vaccinating them because of a stupid error of mistaking correlation for causation. We've got even more parents abusing their children savagely by sheltering them and preventing their maturation thanks to the parents following their "gut feelings" with regard to what information to teach their kids, what media to let them see, etc. The parents never stop to think where their children are going to learn how to handle adult situations, they just assume it comes with age (it doesn't, and if they go too long they may never be able to learn it). Billions of dollars are wasted every year trying to disprove the idiocy people come up with thanks to their "intuition" and even more money is wasted by being thrown at charlatans, homeopaths, and pseudoscientific con artists, all of that boils down to people refusing to defer to their rational abilities and relying on their massively unreliable intuition.
Intuition evolved in human beings to operate only on a very local, very personal level. Any time a situation involves more than 2 people, your intuition cannot be trusted. Intuition also tends to be very conservative, seeing patterns where none exist. This may not harm you if all you're doing is not eating from one bush that you feel might be poisonous (but actually isn't). But when it comes to things like vaccinations, parenting techniques, and things like that, "better safe than sorry" does not apply. By being conservative, you do tremendous damage for no good reason. Our culture is tremendously anti-intellectual and rabidly anti-rational. It's very difficult to even address many issues because people are so certain that their intuitions must be right and every corner of our culture teaches that reason and science are tricksters and liars.
"The Drunkard's Walk" is a fantastic book and I recommend it to everyone. It will include things you will likely refuse to believe, but are true (grading by teachers is random and significantly biased is one I find most people REALLY don't want to believe). Another book that has a couple counterintuitive things in it that are good to know is "Nine Crazy Ideas In Science." Its first chapter alone should end the gun control debate once and for all. It shows conclusively that the prevalence of gun ownership in a society has no correlation with violent crime, neither positive or negative. Counterintuitive, sure, but provable. How many lives are lost every year because people are wasting their energies in anti-gun movements when they could be doing something productive? Intuition costs our society an inestimable amount of money and lives.
We really should start teaching critical thinking skills around 5th or 6th grade. Teachers and parents would hate it because the kids would quickly be better at it than they are, but if we could convince people to once again at least TRY to be rational and have some intellectual integrity I think we would come out the other side a much happier world.
otakucode on June 22, 2009 1:28 PM# in pythonesque, version 3.x:
from random import choice
def pull(s):
k=choice(tuple(s))
s1=s.copy()
s1.remove(k)
return k,s1
def run(stay=True):
doors=set((1,2,3))
chosen,rest=pull(doors)
car,goats=pull(doors)
opened,closed=pull(goats)
while opened==chosen:
opened,closed=pull(goats)
if stay:
return chosen==car
else:
return choice(list(rest-set((opened,))))==car
n=0
cyc=10000
for i in range(cyc):
n+=run(True)
print("Frequency staying: "+str(n/cyc))
n=0
cyc=10000
for i in range(cyc):
n+=run(False)
print("Frequency switching: "+str(n/cyc))
# Output:
#Frequency staying: 0.3343
#Frequency switching: 0.6667
ooops!!!!
your site is not tabs friendly!
#last try
from random import choice
def pull(s):
k=choice(tuple(s))
s1=s.copy()
s1.remove(k)
return k,s1
def run(stay=True):
doors=set((1,2,3))
chosen,rest=pull(doors)
car,goats=pull(doors)
opened,closed=pull(goats)
while opened==chosen:
opened,closed=pull(goats)
if stay:
return chosen==car
else:
return choice(list(rest-set((opened,))))==car
n=0
cyc=10000
for i in range(cyc):
n+=run(True)
print("Frequency staying: "+str(n/cyc))
n=0
cyc=10000
for i in range(cyc):
n+=run(False)
print("Frequency switching: "+str(n/cyc))
# Output:
#Frequency staying: 0.3343
#Frequency switching: 0.6667
...and it also strips anything that starts with "less-than" and ends with "bigger-than", although it is obviously NOT html...
(I tried to simulate the indents with "less-than"intent"bigger-than")
For me, the solution to the Monty Hall problem "clicked" when I read the following variant:
Suppose there are 10,000 doors instead of 3. After you choose, Monty opens 9,998 doors, all of which do not have a car behind them, leaving only your door and one other door closed. Now it is immediately obvious that the chance you originally picked the right door is very small (1 in 10,000), while the chance the other door still closed is the right door is really high.
Jeroen
Jeroen on June 22, 2009 1:57 PMYour odds DO NOT IMPROVE.
Here is the proof along with a C# program. Source and exe.
http://picklepumpers.com/wordpress/?p=130
Pickle Pumpers on June 23, 2009 2:19 AMAnd please stop drawing that flawed chart.
When people use that chart they are saying, "When we get to state 3 the host gets into his time machine and changes his choice to door 3."
Sorry, no time machines are allowed. Once he picks door 3 it no long exists.
Pickle Pumpers on June 23, 2009 2:23 AM
When people use that chart they are saying, "When we get to state 3 the host gets into his time machine and changes his choice to door TWO from door 3."
One thing that's really annoying is that everyone insists that what Monty "meant" to do makes some kind of difference. It doesn't - if you find yourself in that situation - you picked a door, another is opened that doesn't contain the prize, do you want to change? - then the probability of you having picked the right door initially is no different whether Monty meant to open the door with no prize or not.
Hence, the "Monty Fall" problem has no change in outcome.
Zelda on June 23, 2009 2:43 AMTwo things:
One. Jeff's statement of the problem is fine: "the host, who knows what's behind all the doors, opens one of the unchosen doors, which reveals a goat". It's not relevant whether he opened it randomly or not. All that's important is that on this occasion, he reveals a goat.
Two. Monty's motivation - whether he wants to help or hinder - is not relevant either (unless he has the option to not offer you the switch!). He opens one of two doors. If he reveals a goat, you're better off switching. If he were to pick randomly, and revealed a car, then you're DEFINITELY better off switching!
John H on June 23, 2009 2:47 AMMonty motivation's could actually make a difference if, sometimes, he chooses NOT to open ANY door... Which means that he could then choose to open a door only when you chose the car or with some algorithm that can guarantee that whenever you pick the car, switching won't be for good.
philibert on June 23, 2009 2:56 AM@Logo,
A test for a disease is 99% accurate, 1/10,000 people have the disease. You are chosen randomly to be tested for the disease and you test positive. What's the probability that you have the disease?
From this example, it must be assumed that the test is 99% accurate whether you have the disease or not. If you have the disease, then the test will come back positive 99% of the time and 1% of the time it will come back with a false negative. So with 1 million people ~100 people will be expected to have the disease. Of those 100 who have the disease 99 will come back positive {and correctly} that they have the disease, 1 will come back negative {a false negative} indicating that they don't have the disease.
If you don't have the disease, then the test will come back negative 99% of the time and positive 1% of the time it will come back with a false positive. So with 1 million people ~999,900 will be expected to not have the disease. Of those 999,900 who don't have the disease 989,901 will come back negative {and correctly} that they don't have the disease, 9999 will come back positive {a false positive} indicating that they have the disease.
With these numbers, it is clear that if the test comes back positive you have less than a one percent chance that you have the disease, only a ~0.98% chance that you have the disease (99 / (9999 + 99) = (people who have disease / (people who test positive, both correctly and incorrectly). If the test comes back negative it is almost assured that you don't have it, ~99.9999%. Of course if you didn't take the test, your odds of not having it were already relatively low, 99.99%.
I believe a question similar to this was posed to breast cancer doctors in regard to mamograms that have a fairly high false positive rate compared to the rate of breast cancer. Unfortunately, almost all the doctors couldn't figure out that the rate of false positives greatly outnumbered the number of correctly identified postitives. This lead many of the doctors to scare their patients into believing that they might have cancer even though they most likely didn't have it {I believe this is also why tumor samples are taken which are much more accurate}.
MostGetItWrong on June 23, 2009 3:05 AM@philibert: Monty does not have a choice. In fact forget about Monty.
Monty HAS to open a door. It's a valid idea you have but it's really just a problem with the question. Take all human choice out of it.
I just had a discussion with one of those smart people that think changing improves the odds and he was making the mistake of multiplying odds from the previous state. That's fine if you are asking a different question but the question is, will changing your choice NOW make a difference?
Nope. The number of doors Monty reviles is irrelevant. The point is he ALWAYS comes down to two doors. One has a car, one doesn't.
@philibert: Monty does not have a choice. In fact forget about Monty.
Monty HAS to open a door. It's a valid idea you have but it's really just a problem with the question. Take all human choice out of it.
I just had a discussion with one of those smart people that think changing improves the odds and he was making the mistake of multiplying odds from the previous state. That's fine if you are asking a different question but the question is, will changing your choice NOW make a difference?
Nope. The number of doors Monty reviles is irrelevant. The point is he ALWAYS comes down to two doors. One has a car, one doesn't.
OK, forget my last comment. I just wrote myself a simulation and it proved me wrong. I'm surprised by this result - need to go away and think about it for a while!
Zelda on June 23, 2009 3:15 AM@MostGetItWrong
Yeah that is the correct solution and good job writing out the explanation.
Logo on June 23, 2009 3:33 AM@Pickle Pumpers
So basically what you're saying is that as long as you take out the part that makes the chances of a switch being better correct, it's not correct.
Interesting logic. I'd like to subscribe to your newsletter.
PR on June 23, 2009 3:37 AMWhen you make your initial choice, there is a 2/3 chance you are wrong. After the gameshow host shows you a wrong door, there is still a 2/3 chance you chose the wrong door, so switching gives you the 2/3 instead of the 1/3 chance you had with your original choice.
richyrich on June 23, 2009 4:21 AM@Pickle Pumpers
There is a huge gap between saying that something DID not occur (Monty Fall) and COULD not occur (Monty Hall). You talk of the host picking the door with the car and then, with a time machine, changing his choice. We say that could never have happened, because the host ALREADY knows what is behind each door. If the car is behind door #3 and we choose door #1, the host KNOWS and always opens door #2. ALWAYS. There's no time machine involved -- why would he need one? He already KNOWS what is behind that door.
Similarly, if the car is behind door #2, the host ALWAYS opens door #3. If the car is behind door #1, we don't care WHAT the host opens, because it's going to be the same scenario either way: He'll pick a goat and the remaining door also has a goat.
To put it another way -- the host is giving you the choice between what you initially picked and the best of all the other doors. Take the switch.
Trevel on June 23, 2009 4:27 AM
Trying to calculate probabilities directly for these sorts of problems is where pretty much all of us go wrong. The only way for (most of) us to be sure we have the right answer is to work through all the possible scenarios, then divide the number of desired results by the number of scenarios.
It's the one thing I do remember from all those probabilities subjects at uni.
Jim Cooper on June 23, 2009 4:50 AMI liked Benny Hill better. He was hilarious.
david on June 23, 2009 4:58 AM@Confuse-us on June 22, 2009 10:41 PM
The options you list are not all equally likely, which is why you appear to be getting 50%.
The two options listed when you pick the right door are each only half as likely as the option when you pick the wrong door.
If you collapse the options so that each row is equally likely, you get:
Choice Prize Reveal Should Switch?
1 1 (2 or 3) No
1 2 3 Yes
1 3 2 Yes
2 1 3 Yes
2 2 (1 or 3) No
2 3 1 Yes
3 1 2 Yes
3 2 1 Yes
3 3 (1 or 2) No
This gives you the correct odds of success.
Pete on June 23, 2009 4:59 AMEveryone here seems to be making a massive assumption - that the car is a better prize than a goat.
;-)
Given that the choice and prize doors are 100% random, the revealed door must have modified chances to prevent the invalid case of revealing the prize door. It seems all "proof" simulations chose this method. This all feels to me like a silly word puzzle where reality somehow has no practical use, anybody care to disagree?
Confuse-us on June 23, 2009 5:23 AMSorry, could not resist, another version, this time in C#:
(based on the c-version of ant in the comments before)
using System;
class Program
{
static void Main()
{
const int iterations = 1000000;
const int NumberOfDoors = 3;
TestLoop(iterations, NumberOfDoors, false);
TestLoop(iterations, NumberOfDoors, true);
Console.WriteLine("(press a key to exit)");
Console.ReadKey();
}
static void TestLoop(int iterations, int NumberOfDoors, bool DoChange)
{
int wins = 0;
for (int i = 0; i
/// Monty Hall Simulation
///
/// Shall the player change door or not?
/// Number of doors total (only one is shown as wrong/goat)
/// has the player chosen right?
static bool Play(bool DoChange, int NumberOfDoors)
{
// Reset doors (each row is automatically initialized to "false" in C#)
bool[] doors = new bool[NumberOfDoors];
// Place the car behind a random door
doors[rand() % NumberOfDoors] = true;
// Choose a door for the player
int playerChoice = rand() % NumberOfDoors;
// Choose a door for the host that is not the player's door
// and does not contain the car
int hostChoice = -1;
while (true)
{
hostChoice = rand() % NumberOfDoors;
if ((hostChoice != playerChoice)
&& (doors[hostChoice] == false))
{
break;
}
}
int newChoice = -1;
if (DoChange)
{
// Switch player choice to a new door
for (int j = 0; j doors.Length; j++)
{
if (j != playerChoice
&& j != hostChoice)
{
newChoice = j;
break;
}
}
}
else
{
newChoice = playerChoice; // do not change door
}
// just to be sure
if (newChoice == -1 || hostChoice == -1)
{
throw new ApplicationException("invalid choice, error!");
}
// Did we get the right door?
return doors[newChoice];
}
static Random moRand = new System.Random();
static int rand()
{
return moRand.Next();
}
}
What a dammned' comment-system:
It fails on less-than and greater-than-signs, what a pity and how unworthy.
Dear Steve, please update, that's so 2001 ...
C. Wissing on June 23, 2009 6:07 AM" I just wrote myself a simulation and it proved me wrong. I'm surprised by this result..."
That's what we've been saying all along. Just go simulate it people! Stop with the hypothesis and just go stinking simluate it! You don't have to write a program. Use coins, cards, your fingers or whatever. It takes two minutes, literally. It takes less time to run through a simple test than it does to keep rambling on and on here.
**********************************************************************
Listen people! Do us all a favor before posting: SIMULATE IT!
**********************************************************************
I didn't read all the comments, but has anyone tried it this way? What if you are allowed to pick two doors to start. Monty shows you a goat behind one of the doors you picked. If you switched to the other door, wouldn't your odd of picking the car go down? So, when you pick one door and he shows you one with the goat, by switching, you are now picking two doors.
Joseph on June 23, 2009 6:25 AM@LintMan, @Tom Dibble
Thanks for the clarifications on the Unfinished Game/Nosy Neighbour puzzles. Re-phrasing Jeff's question has cleared things up for me.
Ian.
Ian on June 23, 2009 6:43 AMTrying to explain this using only 3 doors is futile, it's utterly counterintuitive. The conceptual problem is that Monty isn't opening ONE door, he's opening ALL the doors that you didn't pick, minus 1. It's just that when there's only 3 doors, that means he only opens one door. If there's 1,000 doors, he opens 998 of them. In more detail:
Monty shows you 1,000 doors. You pick door 1. He opens doors 3 through 1000, revealing all goats. Now only doors 1 and 2 are closed.
What are the odds you happened to pick the car? (1 in 1000.) Since Monty knows where the car is, you have a 999/1000 chance of getting the car if you switch, and a 1 in 1000 chance if you stay.
Now extrapolate down to 1 in 100, 1 in 10, 1 in 5, 1 in 3, and it all makes sense.
dirtside on June 23, 2009 7:36 AM"Listen people! Do us all a favor before posting: SIMULATE IT!"
The thing I was simulating was the thing about "discarding cases" where the host picked the door. I already knew about (or "believed") the 66%, I just thought it wouldn't matter whether he knew what was behind the door or not.
I still can't reconcile the two. Putting myself in the game: I picked door 1. Monty opened door 2. It didn't have the prize. As far as I can see, there are two possible things that have happened:
1. I picked the right door, and Monty has shown me one of the wrong ones (66%)
2. I picked the wrong door, Monty has shown me the other wrong one. (33%)
But I'm missing something, aren't I? Because actually, there's something in point 1 to do with the fact that Monty *could* have shown me the car, by accident (if we're allowing that).
Can anyone help me understand it?
Zelda on June 23, 2009 7:41 AM@Zelda & Matt
Empiricism, best way to deal with illusion brought forth by language usage with which we unintentionally fool ourselves.
I think a better rephrase of the question should be: Assuming that one should switch if suppose there's higher chance of not guessing correctly which door the car is behind,and there are three doors in total while there's only a car,should u switch side once one of the doors which is not your 1st choice and does not have the car u sought for? In retrospect what's the possibility that one would choose the correct door in the 1st place?
The goat thingie IMO is just a strawman,goat or no goat the whole thing is that if the participant has chosen the wrong one from the start, the switch to the another door left unopened would certainly won him/her the car.
Or that the unadventurous ones could take the goat as consolation?;-b
@Confuse-us:
Why dont you try it out on your friends or relatives? Dont have to be computer simulation or do the whole Python Hall, but perhaps simple things like guessing which cup has the ball in it. Since the reason behind switching is that people are more likely to guess the wrong than right one the first time, all u need to do is to do statistics for one time guessing. Due to Law of Large number,remember to take huge amount of statistical records like hundreds of them.
This way it is much better than all those smack talks that all these arent "realistic". Heck, even those who have done computer simulations are above those who only talk the talk. Remember, empiricism.
liuzg150181 on June 23, 2009 7:51 AMBah!
You know what? There was a bug in my simulation - it was only playing a game with two doors! So it turns out it *doesn't* matter if Monty knows what's behind the door, so long as you throw away situations in which he accidentally reveals the car.
Thank heavens for that.
Zelda on June 23, 2009 8:03 AM@Zelda
Due to latency,I just posted before ur last post, actually think of it it is quite simple: You only need to change if ur first choice is wrong,but what's the chance u would get it right(1/3 I assume) vs wrong(2/3 I assume)?
Idon'tGetItIdon'tGetItIdon'tGetIt!
I'm not a crack probabilist, but I'm smart enough to mistrust my intuition and reasoning on these questions, so I actually ran some code (don't laugh, perl guys!):
Monty Hall:
#! /usr/bin/perl -w
use strict;
my ($i, $prize, $door, $open, $win_switch, $win_keep);
for ($i = 0; $i 500; $i++) {
$prize=int(rand(3));
$door=int(rand(3));
do {$open=int(rand(3))} while ($open == $door || $open == $prize);
($prize == $door) ? $win_keep++ : $win_switch++;
}
print "Keep:\t$win_keep\nSwitch:\t$win_switch\n";
This produces the correct results - 1:2
But for Monty Fall, I get exactly the same thing, as many posters here have argued, against many others and the Rosenthal paper Jeff links to!
#! /usr/bin/perl -w
use strict;
my ($i, $prize, $door, $open, $win_switch, $win_keep);
for ($i = 0; $i 10000; $i++) {
$prize=int(rand(3));
$door=int(rand(3));
$open=int(rand(3));
next if ($open == $door);
($prize == $door) ? $win_keep++ : $win_switch++;
}
print "Keep:\t$win_keep\nSwitch:\t$win_switch\n";
This yields exactly the same results, not unsurprisingly, since it's basically the same code, just that the first version makes Monty always choose between the two unpicked doors, while in the second we let him pick any one, but we abandon the cases where Monty slips against the door that we originally picked. Am I making some wrong assumption here? More to the point, has anyone who is defending Rosenthal's solution actually run a simulation confirming it - this is a programming blog, after all!
Celejar on June 23, 2009 8:07 AMThe comments to this entry are closed.
|
|
Traffic Stats |