Solution to Gameshow Problem

/* gameshow.c */

/* KLuGe */


/* Solution by  The Fallible Fiend, aka The Fiend */

/*
  Cross Reference: Three Door Monty, Three Door Problem.

  File CONTENTS:
	A. Description of problem and program.
	B. Commented program listing.
	C. Alternative (analytic) solutions:
		i.   reduction argument mentioned by MVS.
		ii.  probability tree.
		iii. conditional probabilities.

  COMPILATION:
  Make the program like this on Unix:  cc -o gameshow gameshow.c
  Execute as: gameshow
  Then look at the file "results.dat" for the answer.

  The default is 10,000 trials.  If you want to try more trials, you
  can type "gameshow 100000", e.g., to see if the answer changes.

  I think this is ansi C, so I don't think there should be any
  trouble to compile under Borland or Microsoft.  (Come to think
  of it, though, the rand() function may not be standard. I'm not
  sure. Whatever, if you're really interested, and have basic
  familiarity, you should be able to figure it out.)

  GENERAL INFORMATION:
  Program to test the Game Show problem posed by Marylin Vos Savant
  (in, I think 'Parade' magazine, which I never read)  and described
  in the Summer '91 issue of Skeptical Inquirer.  The problem, I think,
  goes back a lot farther than MVS.

  PROBLEM DEFINITION:
  You are in a game show in which you are asked to choose between three
  doors.  Each door has a single prize behind it.  Behind one door is a new
  car.  Behind each of the other two is a goat.  You select a door, say
  door three.  The host then opens one of the doors which you did not
  select, say door number one.  He then asks you if you would like to
  keep the door you have chosen OR switch to the remaining door (door number
  two in this case).  An important point to make here is that the choice
  that the host makes of turning over a door in the game is NOT random -
  the host has perfect knowledge of what is behind each door.  He turns
  over one of the doors you did not pick, but ALWAYS turns over a goat -
  his choice is not random.

  The question which this program resolves is this:
    "Is it to your advantage to switch doors?"

  The unequivocal answer: "Yes!"  There is a two thirds probability that
  the other door (door two) is the correct door and only a one third
  probability that the door you originally selected is the correct door.


  One interesting thing to note about writing a program to solve this
  problem is that you never REALLY have to run it! You make a realization
  while you're writing the program about what the probability MUST be.
  It's really pretty funny!

 */


#include 
#include 

/* #include "kluge.h" */

#define TRUE  1
#define FALSE 0

#define MAXRANDOM 32767
#define NUMDOORS 3


typedef
  enum {
       goat,
       car
       } PRIZE;

typedef PRIZE DOOR[NUMDOORS];

int RandomIntegerInRange(int, int);
int SelectDoor(DOOR, int *, int);


int main(int ac, char **av)
  {
  DOOR door;
  int  dn;
  int game_count;
  int keep_wins  =0;
  int switch_wins=0;
  int random_door;
  int choose_list[2];
  int choose_idx;
  int opened_door;
  int chosen_door;
  int trials;
  FILE *result_file;

  if (ac==1)
    trials=10000;
  else
    sscanf(av[1],"%d",&trials);

  for (game_count=0;game_count < trials;++game_count)
    {
  /* Step 1 - Set up a game */
    random_door = RandomIntegerInRange(0,NUMDOORS-1);
    for (dn=0;dn < NUMDOORS;++dn)
      if (random_door=dn) door[dn] = car;
      else door[dn] = goat;

  /* Step 2 - Start the play of a game */
    chosen_door = RandomIntegerInRange(0,NUMDOORS-1);

  /* Step 3 - The host interrupts */
    /* Find doors available for host to turn over - store in choose_list[] */
    for (choose_idx=0,dn=0;dn < NUMDOORS;++dn)
      if (dn != chosen_door) choose_list[choose_idx++]=dn;
    opened_door = SelectDoor(door,choose_list,chosen_door);

  /* Step 4 - Tally wins */
    if (random_door == chosen_door)  ++keep_wins;
    else ++switch_wins;

  /* NOTE: That whatever happens in Step 3 has NO BEARING on step 4! */
    }

  /* Print results */
  result_file = fopen("results.dat","w");
  if (result_file == NULL)
    {
    printf("Unable to open results.dat\n");
    exit(0);
    }

  fprintf(result_file,"\n\n    Results of Game Show Program.\n");
  fprintf(result_file,    "    _____________________________\n");
  fprintf(result_file,"\nAfter %6d trials, we find that:\n\n",trials);
  fprintf(result_file,"Switching would win %5.2f percent of the time.\n",
	 (float) switch_wins / (float) game_count);
  fprintf(result_file,"Keeping   would win %5.2f percent of the time.\n",
	 (float) keep_wins / (float) game_count);

  close(result_file);
  }



/*
  Have the host select a door that does not have the prize behind it
  to turn over during the game interruption.
 */

int SelectDoor(door,choose_list,chosen_door)
  DOOR door;
  int *choose_list;
  int chosen_door;
  {
  if (door[chosen_door] == car)
    return choose_list[RandomIntegerInRange(0,1)];
  else if (door[choose_list[0]] == car)
    return choose_list[1];
  else
    return choose_list[0];
  }



/* Return a random integer, j, such that low <= j <= high */

int RandomIntegerInRange(low,high)
  int low, high;
  {
  return (int) ((high-low+1)* ((float) rand()/(float) MAXRANDOM)) + low;
  }

/*
   A sample output from this program:

    Results of Game Show Program.
    _____________________________

After  10000 trials, we find that:

Switching would win  0.66 percent of the time.
Keeping   would win  0.34 percent of the time.

*/

/*
Another way to think of the problem.
(Marylin apparently listed this in her column.)

The problem that most people have with this is that they intuitively
think that because they end up with two doors that the probability
must be 50%.

Imagine you are faced with a million doors. Behind one is a million
dollars.  Behind the other 999,999 doors are goats.  You pick one
door at random.  Your host then picks 999,998 of the remaining
999,999 doors and turns over goats.  Do you still think the probability
that the goat is behind the remaining door is only 50%?  The key is
that we know the host has perfect knowledge of what is behind every door.
You do not have perfect knowledge of what is behind any door until the
door gets opened!  When you picked your door, you had a 1 in a million
chance of being right.  When the host turned over his 999,998 doors,
there was a 100% chance that they would all be goats! Did the fact
that the host opened the other doors, change the probability of the
door you initially selected?  No! Not at all.  What he did was give
you information about the set of doors that you did not select!  He
gave you no information at all concerning the single door that you
did select!  And therefore the probably concerning that single door
could not have changed!

It's a strange and counter-intuitive problem.  What this means is
that our intuition is not perfect, even though, in many cases, it's
all we have to go on!  One of the things we learn in probability is
that our intuition is not perfectly reliable!

FWIW, I don't think being able to solve this problem makes
a person smart, or failing to be able to solve the problem makes a
person not smart.  It's mainly a matter of being familiar with non-
intuitive concepts.

*/

/*  Yet ANOTHER way to think of this problem is the probability tree.

Say X marks the door with the nice price behind it , while g and G mark
the doors with goats behind them.  In the following diagram a State is the
known existing universe of the problem set at a moment in time.  Each
branch of the tree has a probability beside it denoting the probability
of taking that branch (following that event) given the previous state.

State A is when the doors are presented to the contestant.

Event 1 is the contestant's 1st choice of a door.

States B1-B3 are the possible states which could result from Event 1.

Event 2 is when the host turns over a door with a goat behind it.

States C1-C4 are the possible states which could result from all of the
possible States B1-B3, given all possible event 2s.

[q = unknown probability that host will show 1st goat given that
contestant chose the prize door.]

                               X g G                         State A.
                                 |
            +--------------------+--------------------+
            |                    |                    |
        1/3 |                1/3 |                1/3 |      Event 1.
            |                    |                    |
            v                    v                    v
          X  gG                g  XG                G  Xg    State B1 - B3.
            |                    |                    |
            +                    |                    |
      +-----+-----+              |                    |
      |           |              |                    |      Event 2.
    q |       1-q |            1 |                  1 |
      |           |              |                    |
      v           v              v                    v
    X  g        X  G          g   X                 G  X     State C1 - C4.


     1           1             1                    1 
     -*q    +    -*(1-q)       -*1                  -*1     Probabilities.
     3           3             3                    3
           \\                   \\                   \\     Evaluating to....
            \\                   \\                   \\
            1/3                 1/3                  1/3


Finally, examining the probability tree, makes it pretty clear how
we would write the equations in terms of conditional probabilities.

P(C1 U C4) = P(C1|B1)P(B1) + P(C2|B1)P(B1) = 1/3,  whereas
  _______
P(C1 U C4) = P(C3 U C4) = P(C3|B2)P(B2) + P(C4|B3)P(B3) = 2/3.

You can move the X around to the other two spots and you get the
same kinda tree (but it's not necessary to do that, if you think
about it).

*/