THE MONTY HALL THREE-DOOR PROBLEM FAQ
=====================================
Author: Mark N. Shaw <mshaw@notnetcom.com>
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 <stdio.h>
#include <stdlib.h>
#include <time.h>
/* 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 <num_trials> [-verbose]");
exit(0);
}
else
{
srand( (unsigned) time(&t) ); /* init. random-number engine */
for(trials=0; trials<num_trials; trials++)
{
for(i=0; i<NUM_DOORS; i++) /* initialize doors */
door[i] = BOOBY_PRIZE;
good_prize_door = random_door(); /* pick a door for good prize */
door[good_prize_door] = GOOD_PRIZE; /* put good prize behind door */
player_choice = random_door(); /* now the player picks a door */
if(verbose)
printf("\ntrial %9ld: ", trials+1);
if(player_choice == good_prize_door) /* if player chose correctly */
{ /* to begin with, */
++successes[STICK]; /* he wins if he sticks. */
if(verbose)
printf("STICK wins. ");
}
else /* otherwise, */
{
++successes[SWITCH]; /* he wins if he switches. */
if(verbose)
printf("SWITCH wins. ");
}
if(verbose)
printf(" SWITCH success %3.1f%%, STICK success %3.1f%%",
(float)successes[SWITCH] / (float)(trials+1) * 100.0,
(float)successes[STICK] / (float)(trials+1) * 100.0 );
}
if(verbose)
printf("\n");
printf("\nResults: After %ld trials,", trials);
printf("\n Success with stick strategy was %3.1f%%",
(float)successes[STICK] / (float)trials * 100.0 );
printf("\n Success with switch strategy was %3.1f%%\n",
(float)successes[SWITCH] / (float)trials * 100.0 );
}
}
--- cut here ---
---------------------------------------------------------------------------
THE CASINO DEMONSTRATION:
I will play the game with anyone who wishes to challenge me. We will play
with dollar bills and shoeboxes, each of us bringing to the table an equi-
valent number of dollar bills -- not less than 50 and not more than the
amount of cash I can scrounge up at the time. I will take the "switch"
strategy, and my opponent must take the "stick" strategy. We will take
turns being Monty and contestant, or choose a third party to be Monty, at
the challenger's option. The game will end when one of us is ahead by 50%
or more, unless the challenger wishes to continue.
---------------------------------------------------------------------------
FINAL NOTES:
If you still don't get it, don't feel too bad. Many people who work with
probability and statistics for a living have had a hard time getting it.
If you want clarification on anything, feel free to contact me. Please
refer to the particular method or methods above that are in question, and
I will attempt to explain them better. Flames and abuse will be cheerful-
ly ignored.
---
Mark Shaw
Dallas, Texas