THE MONTY HALL THREE-DOOR PROBLEM FAQ ===================================== Author: Mark N. Shaw Date: 941006 Last Revised: 981111 Version: 1.4 Copyright (C) 1994, 1998 by Mark N. Shaw. Permission to distribute this document freely, in whole or in part, is hereby granted, with the under- standing that no fee may be charged and proper attribution is given. PGP Public Key: -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.6 mQBNAy5mIRsAAAECAMyOFih+Tr91c0O10TJVaczzzmAakwLKGkD1WTC5/G9OeGCv PfLyl/Hbl+6NH276CR1yPdYSpCsmzV3Bfvb30UkABRG0JU1hcmsgU2hhdyA8bW5z MUBkYWxzb2wucnRjLnNjLnRpLmNvbT4= =npQS -----END PGP PUBLIC KEY BLOCK----- Preamble: ======== The Monty Hall three-door problem is a very sticky puzzle. It's probabi- lity-based, which throws most people for a loop immediately, and in addition the solution is counterintuitive. As such, it is the subject of endless controversy. This file is an attempt to eliminate some of the controversy by explaining the solution in as many ways as possible. Question/Answers ================ Q1: What is the Monty Hall three-door problem? ----------------------------------------------- The problem is defined as follows: On the "Let's Make a Deal" game show, Monty Hall gives a contestant his choice of three closed doors. One of the doors has a fabulous prize behind it; the other two have worthless prizes. Only Monty knows which door has the good prize. The contestant chooses a door. Before the chosen door is opened, Monty opens one of the other doors, showing that it has a booby prize behind it. At this point he tells the contestant that he may, if he wishes, change his choice to the remaining closed door. Is it better for the contestant to switch his choice to the remaining door or to stick with his original choice? Q2: So what's the answer? -------------------------- It's better to switch. The contestant has a 2/3 chance of winning the good prize if he switches, but only a 1/3 chance of winning the good prize if he sticks with his original choice. Q3: Huh? He's choosing between two doors! He's got a 50-50 chance! --------------------------------------------------------------------- Nope. Seems reasonable, but no. It's better to switch. Q4: But what if Monty DOESN'T open one of the unchosen doors? -------------------------------------------------------------- For the purposes of this puzzle, we assume that Monty planned to open a valueless door regardless of what the contestant's original choice was. Otherwise, we're reduced to speculating about Monty's motivations and how he might act on those motivations, and that's more of an exercise in game- show-host psychology than anything else. Q5: Can you prove that it's better to switch? ---------------------------------------------- Maybe. Depends on what you mean by "proof." I'm not a mathematician, so I don't know if you'll accept any of the following as anything like a formal proof. I can make some pretty convincing arguments, though. Q6: Okay, smart guy, let's see 'em! ------------------------------------ Here you go: --------------------------------------------------------------------------- THE MATHEMATICAL (well, sort of) PROOF: At the beginning of the game, the probability of the contestant's choosing the correct door is 1/3, since there are three doors and they're all the same. In other words, for X = {1,2,3}, the probability that Door X contains the good prize is P(Door X) = 1/3 (1) or, writing the expression in terms of the probability of each door's having the good prize: P(omega) = P(Door A) + P(Door B) + P(Door C) (2) = 1/3 + 1/3 + 1/3 = 1 Where omega is the summation of possible events, and P(omega) is always equal to unity (from probability theory). Note that "P(omega)" can be thought of as "The probability that the good prize lies somewhere within the system of doors." After Monty opens one of the unchosen doors (assume he opened Door C), equations (1) and (2) no longer hold. We know for certain that the good prize still lies behind one of the remaining doors, so we can write P(omega) = P'(Door A) + P'(Door B) = 1 (3) but 1/3 + 1/3 != 1 so either P(Door A) != P'(Door A) (4) and/or P(Door B) != P'(Door B) (5) are true. Now, when Monty opens one of the unchosen doors, he conveys no new infor- mation about the chosen door. This is true because for any particular door chosen by the contestant, Monty can open at least one other door, effec- tively removing it from the game. Therefore, the probability that the good prize lies behind the chosen door is constant. If we assume that Door A was chosen, we can write P(Door A) = P'(Door A) = 1/3 (6) and P(omega) = 1/3 + P'(Door B) (7) (If it is difficult to accept equation (6), remember that the contestant chose the door from a field of three. If he decides to stick with his choice, it doesn't matter if Monty opens a door or not -- he's going to stick with his choice, and that's that, so his chances of winning are the same as if Monty does *not* open a door -- that is, 1/3.) Now we can rearrange equation (7) to express the probability that the prize lies behind Door B: P'(Door B) = P(omega) - 1/3 (8) Since the value of P(omega) is always, by definition, unity, this becomes P'(Door B) = 1 - 1/3 (9) = 2/3 Now, since the probability that the prize lies behind Door B is 2/3, and the probability that the prize lies behind Door A is 1/3, and the contest- ant chose Door A, it's in his best interest to switch. --------------------------------------------------------------------------- SET THEORY: Partition the set of doors as follows: A = {1}, which the contestant has chosen, and B = {2,3} which the contestant has NOT chosen. Clearly, the probability that the money can be found in A is 1/3, and the probability that it can be found in B is 2/3. When Monty opens one of the doors in the B partition, he is in effect removing that door from the game, reducing the cardinality of B from 2 to 1. He cannot, however, affect the likelihood that the money is con- tained within that partition simply by reducing its cardinality. At this point, Monty is giving the contestant the option of trading A for ALL the doors in B. And since the probability that the money is in B is still 2/3, it's a good trade. --------------------------------------------------------------------------- THE STEP-BY-STEP EXPLANATION IN PLAIN ENGLISH: Please read through, understand and accept the conclusions of each step before proceeding to the next. If you cannot accept the conclusions of any particular step, STOP. Do NOT proceed. Instead, contact me and I will endeavor to better explain the step you are confused about. STEP ONE: In the initial phase of the exercise (before Monty opens a door and reveals a booby prize), the contestant has a 1/3 chance of having chosen the door with the good prize behind it, and a 2/3 chance of having chosen one of the doors with a booby prize. STEP TWO: After Monty opens a door, revealing a booby prize, the following situation exists: There are two doors, one of which has been chosen by the contestant. Behind one of the doors is a good prize; behind the other is a booby prize. In other words, the door that Monty has opened has been, in effect, removed from the game. STEP THREE: There are now only four possibilities: 1. The contestant has chosen the good door and will stick with his original choice. 2. The contestant has chosen the good door and will switch his choice to the other door. 3. The contestant has chosen one of the bad doors and will stick with his original choice. 4. The contestant has chosen one of the bad doors and will switch his choice to the other door. STEP FOUR: In STEP THREE, possibilities number 1 and 4 result in favorable outcomes. Possibilities number 2 and 3 result in unfavorable outcomes. However (as has been shown in STEP ONE), there is a 2/3 probability that either possi- bility 3 or 4 will occur, and a 1/3 probability that either possibility 1 or 2 will occur. STEP FIVE: If the contestant sticks with his original choice, possi- bilities 2 and 4 are eliminated. A favorable outcome is now only possible if the contestant chose correctly to begin with (possibility number 1). In STEP ONE, it was shown that this will occur with probability 1/3. STEP SIX: If the contestant switches to the remaining door, possibi- lities 1 and 3 are eliminated. A favorable outcome is now only possible if the contestant chose INcorrectly to begin with (possibility number 4). In STEP ONE, it was shown that this will occur with probability 2/3. CONCLUSION: It has been shown in STEP FIVE that the stick-with-the- original-door strategy has a probability of success of 1/3, and in STEP SIX that the switch-to-the-other-door strategy has a probability of success of 2/3. Therefore, the better strategy is to switch. --------------------------------------------------------------------------- THE EMPIRICAL MODEL: Assume the goodies are behind Door A. Now there are only three ways the game can proceed: The contestant picks Door A. Monty opens either Door B or Door C (it doesn't matter which). If the contestant switches to the remaining door, he loses. If he doesn't switch, he wins. The contestant picks Door B. Monty opens Door C. If the contestant switches to the remaining door (Door A), he wins. If he doesn't switch, he loses. The contestant picks Door C. Monty opens Door B. If the contestant switches to the remaining door (Door A), he wins. If he doesn't switch, he loses. All other possibilities are permutations of the above, the only difference being that the goodies are behind Door B or Door C instead of Door A. Now, since the contestant's first choice is random among the three doors, each of the above three scenarios are equally likely. Two of them result in wins if the contestant pursues a "switch" policy, though. Therefore, the better choice is to switch. --------------------------------------------------------------------------- THE REDUCTIO AD ABSURDUM ARGUMENT: Change the problem to one of 100 doors, but otherwise the same. The proba- bility that the correct door will be chosen by the contestant is now only 1%. Now, Monty opens 98 doors, removing them from the game. Hmm, now that remaining door is starting to look awfully attractive.... --------------------------------------------------------------------------- THE REVERSE ARGUMENT: Assume the contestant decides beforehand that he's going to switch to the remaining unopened door, no matter what. Now, when Monty gives the contes- tant his choice between the three original doors, his question can be re- phrased as "Choose one of these doors to remove from the game. After you have done so, I will remove a valueless door from the remaining two. You can have whatever's behind the last door." Another way of looking at this is that a contestant pursuing a "switch" strategy is, when he makes the initial choice, actually defining the one door he does *not* want. He gets to keep all the goodies that lie behind the other two doors. --------------------------------------------------------------------------- THE COMPUTER SIMULATION: --- cut here --- /* doors.c version 1.1 This is a simulation of the Monty Hall three-door problem. The problem is defined as follows: A contestant on a game show is given the choice of three doors to choose from. Behind each door is a prize. One of the prizes is quite valuable, and the other two are booby prizes. The contestant will be awarded whatever prize is behind the door he chooses. After the contestant chooses a door, the game show host reveals a booby prize behind one of the unchosen doors (he always does this, no matter which door was chosen by the contestant). At this point, the contestant is given a choice: he may switch his choice to the third door, or he may stick with his first choice. The question to be answered is whether the better strategy is to stick or to switch. This simulation tests each strategy empirically. The user specifies the number of trials on the command line, and whether or not a verbose output is desired. History: 94xxxx created. 941226 added initialization for random-number engine. */ /* includes: */ #include #include #include /* defines: */ #define NUM_DOORS 3 #define BOOBY_PRIZE 0 #define GOOD_PRIZE 1 #define STICK 0 #define SWITCH 1 #ifndef RAND_MAX #define RAND_MAX 32766 #endif /* function prototypes: */ int random_door(void); int interpret_command_line(int num_args, char *arg[]); void main(int argc, char *argv[]); /* globals: */ int verbose = 0; long num_trials; /* function definitions: */ int random_door() { return( (int) ( (float)rand() / (float)RAND_MAX * (float)NUM_DOORS ) ); } int interpret_command_line(int num_args, char *arg[]) { int arg_num = 0, ret_value = 0; if( !( (num_args == 3) || (num_args == 4) ) ) return(ret_value); while(1) { if(++arg_num == num_args) return(ret_value); if( !strcmp(arg[arg_num], "-verbose") ) { verbose = 1; continue; } else if( !strcmp(arg[arg_num], "-trials") ) { ret_value = 1; num_trials = atol(arg[++arg_num]); continue; } } } void main(int argc, char *argv[]) { char door[NUM_DOORS]; int good_prize_door, player_choice; long successes[2]={0,0}, trials, i; time_t t; if ( !interpret_command_line(argc, argv) ) { printf("\nusage: doors -trials [-verbose]"); exit(0); } else { srand( (unsigned) time(&t) ); /* init. random-number engine */ for(trials=0; trials