Monty Hall problem analysis

From CodeCodex

These programs demonstrate that the solution to the Monty Hall problem is correct.

Implementations[edit]

C[edit]

This C program demonstrates that the solution to the Monty Hall problem is correct by playing several simulations. Half the time it switches and the other half it stays with the original choice.

/* Monty Hall Problem simulator */
/* Written by Elver Loho -- http://elver.cellosoft.com */
/* Released into public domain */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int main(int argc, const char* argv[]) {
	if(argc!=2) {
		printf("%s number_of_games\n", argv[0]);
		return 1;
	}
	int max = atoi(argv[1]);
	srand(time(0));
	int i, r, p, win_switch, win_stay;
	win_switch = win_stay = 0;
	int car[3] = {0};
	for(i = 0; i < max; i++) {
		car[r = rand()%3]++;
		// car is behind choice r.
		// let's choose at random one door. this is the player's choice.
		p = rand()%3;
		// the host eliminates the first goat.
		// we now make the choice between switching or staying.
		if(!(i%2)) {
			// we switch
			// when switching we win if our original choice is different
			// from that where the car is
			if(r != p)
				win_switch++;
		} else {
			// we stay
			// when we stay we win if our original choice is the
			// same as where the car is
			if(r == p)
				win_stay++;
		}
	}
	for(i = 0; i < 3; i++) {
		printf("%d: %d / %d (%d\%)\n", i, car[i], max, (car[i]*100)/max);
	}
	printf("wins by switching of all wins: %d / %d (%d\%)\n", win_switch, win_switch+win_stay, (win_switch*100)/(win_switch+win_stay));
	printf("wins by staying of all wins: %d / %d (%d\%)\n", win_stay, win_switch+win_stay, (win_stay*100)/(win_switch+win_stay));
	printf("total combined wins of all games %d / %d (%d\%)\n", win_switch+win_stay, max, ((win_switch+win_stay)*100)/max);
	printf("wins by switching of all related games %d / %d (%d\%)\n", win_switch, max/2, (win_switch*100)/(max/2));
	printf("wins by staying of all related games %d / %d (%d\%)\n", win_stay, max/2, (win_stay*100)/(max/2));
	return 0;
}

Compilation, usage and output look something like this:

$ gcc monty.c -o monty && ./monty 30000
0: 10073 / 30000 (33%)
1: 9942 / 30000 (33%)
2: 9985 / 30000 (33%)
wins by switching of all wins: 10006 / 14937 (66%)
wins by staying of all wins: 4931 / 14937 (33%)
total combined wins of all games 14937 / 30000 (49%)
wins by switching of all related games 10006 / 15000 (66%)
wins by staying of all related games 4931 / 15000 (32%)

C++[edit]

Following C++ program is simulation of Monty Hall problem. It performs simulation for given number of games (in capacity of long int type) and shows difference between 'switching' and 'staying' strategy.


	/* Approximate solution of the Monty Hall problem. */

#include<iostream>
#include<cstdlib>
using namespace std;

int doors[ 3] = { 0, 0, 0};
int r; // r - keeps choice of door

void clear_doors( void); // clears all doors
void draw( void); // places the car - at random - behind the doors; then 'contestant' picks, also at random, one door

int main()
{
	long int n, w = 0, w_s = 0; // n - number of games, w - number of winning games without switching, w_s - number of winning games with switching
	double p, p_s, n_copy; // p - percent of winning games without switching, p_s - percent of winning games with switching

	cout << "Give number of games: ";
	cin >> n;
	n_copy = n;

	srandom( time( NULL));

	for( n; n > 0; n--) // this loop is for games without switching
	{
		draw();

		if( doors[ r] == 1) // if contestant chose winning door, increament winning games counter and clear all doors
		{
			w++;
			clear_doors();
		}
		else // if didn't, only clear all doors
		{
			clear_doors();
		}
	}

	n = n_copy; //reset counter of number of games to play, to previous value given by user
 
	for( n; n > 0; n--) // this loop if for games with switching
	{
		draw();

		/*
		How does it work:
		If contestant picked door with the car then switch to losing door.
		If contestant picked losing door then switch to winning door [because he chose the losing one at the first pick and second losing he saw when he could change his decision].
		[It shows that knowledge of the game host is essential!]
		*/

		if( doors[ r] == 0) // if contestant chose winning door, increament winning games counter and clear all doors
		{
			w_s++;
			clear_doors();
		}
		else // if didn't, only clear all doors
		{
			clear_doors();
		}
	}

	cout << endl;
	p = (w / n_copy)*100;
	p_s = (w_s / n_copy)*100;
	cout << "Number of winning games without switching: " << w << " [ " << p << "% ]" << endl;
	cout << "Number of winning games with switching: " << w_s << " [ " << p_s << "% ]" << endl;

	cout << endl;
	return 0;
}

void clear_doors( void)
{
	doors[ 0] = doors[ 1] = doors[ 2] = 0;
}

void draw( void)
{
	doors[ random() % 3] = 1; // places the car, at random, behind the doors
	r = random() % 3; // picks one door at random
}


Sample output for n = 1 000 000

Give number of games: 1000000

Number of winning games without switching: 332762 [ 33.2762% ]
Number of winning games with switching: 667494 [ 66.7494% ]

Java[edit]

The following Java program simulates a million games and compares the success rate of the switching strategy with that of the staying strategy.

import java.security.SecureRandom;
public class MontyHall {
    public static void main(String[] args) {
        SecureRandom rand = new SecureRandom();
        int games = 1000000, winsWithSwitch = 0, winsWithoutSwitch = 0;
        System.out.println("Playing " + games + " games...");
        for(int i = 0; i < games; i++) {
            // Place the prize behind a door, and then let the
            // contestant choose.
            int prizeDoor = rand.nextInt(3);
            int choice = rand.nextInt(3);
            // Open a door that does not have the prize behind it.
            int openedDoor;
            if(choice == prizeDoor)
                openedDoor = (prizeDoor + 1 + rand.nextInt(2)) % 3;
            else
                openedDoor = (0 + 1 + 2) - choice - prizeDoor;
            // Let the contestant switch to the door that was NOT opened.
            int switchDoor = (0 + 1 + 2) - choice - openedDoor;
            if(choice == prizeDoor)
                winsWithoutSwitch++;
            if(switchDoor == prizeDoor)
                winsWithSwitch++;
        }
        System.out.print("Win rate with a \"don't switch\" strategy: ");
        System.out.println((double) winsWithoutSwitch / games);
        System.out.print("Win rate with a \"switch\" strategy: ");
        System.out.println((double) winsWithSwitch / games);
    }
}

Here is the output of a sample run of this program:

Playing 1000000 games...
Win rate with a "don't switch" strategy: 0.332968
Win rate with a "switch" strategy: 0.667032

Perl[edit]

Alternative one[edit]

The following Perl program computes an approximate solution of the Monty Hall problem by simulation. Two strategies are simulated: stick with initial choice every time, or switch from initial choice every time. The program performs a number of games and counts how many times each strategy wins the game.

The result of the simulation almost always shows that the switch strategy wins about twice as many times as the stick strategy. This is empirical evidence that switching is a better strategy in this game.

#!/usr/bin/perl

# Approximate solution of the Monty Hall problem

# Use -v to see each game. (default: off)
# Use -i # to set number of iterations. (default: 3000)

use strict;

my $iterations = 3000;    # How many games to play
my $verbosity = 0;

while (@ARGV) {
    my $param = shift @ARGV;
    $verbosity = 1 if $param eq '-v';
    $iterations = int (shift @ARGV) if $param eq '-i';
}

sub verbose {
    print $_[0]."\n" if $verbosity;
}

my $stickers;
my $switchers;

print "Playing $iterations games...\n\n";

for(1..$iterations) {
    my @items = qw(goat goat prize);     # two goats, one prize
    my @door;

    while (@items) {  # put the @items into the @door array in random order
        push (@door, splice (@items, int rand @items, 1));
    }

    verbose ("Door 0: $door[0];  Door 1: $door[1];  Door 2: $door[2]");

    my $contestant = int rand 3, my $monty, my $alternate;

    # If the contestant picked the prize, Monty picks another door at random.
    if ($door[$contestant] eq 'prize') {
        $monty = ($contestant + (int rand 2) + 1) % 3;
    }

    # Otherwise, he picks the other goat.
    else {
        $monty = $door [ ($contestant+1) % 3 ] eq 'goat' ? ($contestant+1) % 3 : ($contestant+2) % 3;
    }

    $alternate = ($contestant + 1) % 3 == $monty ? ($contestant + 2) % 3 : ($contestant + 1) % 3;

    verbose ("Contestant opens door $contestant, Monty opens door $monty; alternate is $alternate.");

    if ($door[$contestant] eq 'prize') {
        verbose ("Sticker wins.");
        $stickers++;
    }

    if ($door[$alternate] eq 'prize') {
        verbose ("Switcher wins.");
        $switchers++;
    }
}

print "Grand totals:
Sticker  has won  $stickers  times
Switcher has won  $switchers  times
";

Here is the output of a sample run of this program for the default 3000 iterations:

Playing 3000 games...

Grand totals:
Sticker  has won  1013  times
Switcher has won  1987  times

Alternative two[edit]

There is another empirical solution of the Monty Hall problem, but it looks like the coder tried to save lines of code rather than make the code obvious to casual passerby. Just to give you an idea, I've been coding Perl for about 7 years and the algorithms weren't immediately obvious to me. I had to ponder what was being done.

So I re-coded the empirical solution as my own Perl script, trying to be far more verbose and clear. I also coded this script because I couldn't believe the truth either, and needed my own reinforcement. It's amazing how strongly my brain refused to believe the answer to the problem. It is so similar to an optical illusion, that I'm dubbing it a "conceptual illusion."

#!/usr/bin/perl -w

# Empirical evidence that the Monty Hall "conceptual illusion" aka "problem"
# aka "paradox" actually has the answer the experts say it has.
#
# Written by Philo Vivero in July 2005 (because he couldn't believe the answer
# was correct unless he implemented a checker himself)
#
# The algorithms for determining which doors have what, which doors are picked,
# which doors are switched to, etc are all rather stupidly implemented as far
# as efficiency, *BUT* should be very clear how they work, even to an amateur.
#
# Released under the terms of the GNU Public License v.2 (GPL). If any of the
# terms of that license are unknown or ambiguous to you, you are granted no
# license to copy or use this script.
#
# Re-releasing under terms of GFDL, because it looks like Wikisource prefers
# that license. In any case,
#
# THIS SCRIPT COMES WITH NO WARRANTY, EXPRESS OR IMPLIED, EVEN THE IMPLIED
# WARRANTY OF FITNESS. THIS SCRIPT MAY NOT WORK. IT MAY BREAK. IT MAY HURT
# YOUR PETS. YOU BEAR ALL RESPONSIBILITY AND LIABILITY FOR ANY FAILURE.

$switchWins=0;
$switchLoses=0;
$stickWins=0;
$stickLoses=0;

# only output results of every Nth game
$showEveryNthGame = 50;
$numGamesToPlay = 2000;

for ($i=0; $i<$numGamesToPlay; $i++) {
       $carDoor = int(rand(3))+1;
       $guessDoor = int(rand(3))+1;

       # here we see what door monty will open
       if ($guessDoor == $carDoor) {
               # we guessed the car -- so monty chooses a random goat
               $montyRandom = int(rand(2))+1;
               $montyDoor = (($carDoor + $montyRandom - 1) % 3) + 1;
       } elsif ($guessDoor != $carDoor) {
               # we guessed the goat -- so monty chooses the other goat
               if (($guessDoor == 2 || $guessDoor == 3) && ($carDoor == 2 || $carDoor == 3)) { $montyDoor = 1; }
               elsif (($guessDoor == 1 || $guessDoor == 3) && ($carDoor == 1 || $carDoor == 3)) { $montyDoor = 2; }
               elsif (($guessDoor == 1 || $guessDoor == 2) && ($carDoor == 1 || $carDoor == 2)) { $montyDoor = 3; }
       }

       # only print every Nth game
       if ($i % $showEveryNthGame == 0) { print "carDoor is: $carDoor guessDoor is: $guessDoor montyDoor is: $montyDoor... "; }

       # o the humanity! should i switch, or not? let's flip a coin...
       $switchDecision = int(rand(2))+1;
       # uncomment one of the following if you want to always switch or always stick
       ## # no, let's always switch.
       ## $switchDecision = 1;
       ## # actually, let's always stick.
       ## $switchDecision = 2;

       if ($switchDecision == 1) {
               # heads, we switch
               if (($guessDoor == 2 || $guessDoor == 3) && ($montyDoor == 2 || $montyDoor == 3)) { $guessDoor = 1; }
               elsif (($guessDoor == 1 || $guessDoor == 3) && ($montyDoor == 1 || $montyDoor == 3)) { $guessDoor = 2; }
               elsif (($guessDoor == 1 || $guessDoor == 2) && ($montyDoor == 1 || $montyDoor == 2)) { $guessDoor = 3; }

               if ($i % $showEveryNthGame == 0) { print "switched to $guessDoor... "; }
       } else {
               # tails, we stick with our original choice
               if ($i % $showEveryNthGame == 0) { print "stuck with $guessDoor... "; }
       }

       # the moment of truth! is the guess door same as the car door?
       if ($carDoor == $guessDoor) {
               if ($i % $showEveryNthGame == 0) { print "we won! w00t.\n"; }
               if ($switchDecision == 1) { $switchWins++; } else { $stickWins++; }
       } else {
               if ($i % $showEveryNthGame == 0) { print "darn. we lost.\n"; }
               if ($switchDecision == 1) { $switchLoses++; } else { $stickLoses++; }
       }
}

print "switch win/lose: $switchWins / $switchLoses\n";
print "stick  win/lose: $stickWins / $stickLoses\n";

print "Note: I only output the result 1 out of every ${showEveryNthGame} games (but played a total of $numGamesToPlay games).\n";

PHP[edit]

<?PHP

/* Notes for the casual passerby: 
/ - change the number after $num_games =  to choose how many games to play
/
/ - array_splice, with the parameters it's given here, takes a single element out of an array
/	which is treated here as the equivalent of opening that door, because it's removed
/	from the possible choices at the same time that we find out its value....
/ - all lines of the forum $variable = $varible[0] are array to string conversion
/ - mt_rand() chosen over rand() for speed. (not aware that there is a differences in randomness of numbers between them)
/ - yet, array functions used for readability
/ - added calculation of how long it took and games simulated per second. The user will probably play around with the number
/	of games played, so this is will help them determine how long it will take as they adjust it
*/


$wins_sticking = 0;
$wins_switching = 0;
	
$num_games = 1000000;
	
$time_start = microtime_float();

	for ($i=0; $i < $num_games; $i++) {
		// put the possiblities behind the doors...
		$doors = array("goat","goat","prize");
		// randomize them....
		shuffle($doors);
		// the contestant choose ones, and it is removed from the remaining choices
		$contestant = array_splice($doors, mt_rand(0,2), 1);
		$contestant = $contestant[0];
		// If the contestant picked the prize, Monty opens another door at random.
		if ($contestant === "prize") {
		
			$monty = array_splice($doors, mt_rand(0,1), 1);
			$monty = $monty[0];
			
		} else {
		
			//Otherwise, monty intentionally opens the door with the other goat
			// there's only 2 choices,
			// one or other must be goat, this figures out which one
			if ($doors[0] === "goat") {
				$monty = array_splice($doors, 0, 1);
				$monty = $monty[0];
			} else {
				$monty = array_splice($doors, 1, 1);
				$monty = $monty[0];
			}
			
		}
		
		//now, the contestant has picked something, and monty has reacted. Time to switch or stay
		if ($contestant === "prize") {
			$wins_sticking++;
		}
		if (array_pop($doors) === "prize") {
			$wins_switching++;
		}
	}

	// calculate some helpful infomation on time it took and percentage of wins
	$time_end = microtime_float();
	$time_took = $time_end - $time_start;
	
	$percent_sticking = $wins_sticking / $num_games;
	$percent_switching = $wins_switching / $num_games;

	echo " Wins sticking: $wins_sticking ($percent_sticking%)\n Wins switching: $wins_switching ($percent_switching%)\n";
	echo " Calculation took $time_took seconds for $num_games games\n";
	echo " that's a rate of " . ($num_games / $time_took) . " games per second";
	
	function microtime_float()
	{
		list($usec, $sec) = explode(" ", microtime());
		return ((float)$usec + (float)$sec);
	}
?>

Sample output for 1,000,000 games (speed will vary; output shown from PC with p4 2.4ghz)

 Wins sticking: 333124 (0.333124%)
 Wins switching: 666876 (0.666876%)
 Calculation took 19.505182981491 seconds for 1000000 games
 that's a rate of 51268.424446411 games per second

Python[edit]

The following Python program computes an approximate solution of the Monty Hall problem by simulation. Two strategies are simulated: stick with initial choice every time, or switch from initial choice every time. The program performs a number of games and counts how many times each strategy wins the game.

The result of the simulation almost always shows that the switch strategy wins about twice as many times as the stick strategy. This is empirical evidence that switching is a better strategy in this game.

from __future__ import division
from random import choice

def monty(games=100000):
    switch_wins = 0
    stay_wins = 0
    doors = [1, 2, 3]
    for game in xrange(games):
        prize_door = choice(doors) # randomly choose prize_door
        chosen_door = choice(doors) # randomly choose initial door guessed
        opened_door = choice(list(set(doors) - set([prize_door, chosen_door]))) # door opened by monty
        switch_door = (set(doors) - set([chosen_door, opened_door])).pop() # door chosen if switching
        if chosen_door == prize_door:
            stay_wins += 1
        if switch_door == prize_door:
            switch_wins += 1
    print 'Win rate with a "don\'t switch" strategy:', stay_wins / games
    print 'Win rate with a "switch" strategy:', switch_wins / games

if __name__ == '__main__':
    monty()

Example output:

Win rate with a "don't switch" strategy: 0.33274
Win rate with a "switch" strategy: 0.66726

Ruby[edit]

Following Ruby program is simulation of Monty Hall problem.

# Empirical solution of the Monty Hall problem (Ruby)
GAMES = 100000
DOORS = [1, 2, 3]
stay_win = switch_win = 0

def choice(arr)
  arr[rand(arr.length)]
end

puts "Playing #{GAMES} games..."
GAMES.times {
  prize_door  = choice(DOORS)
  chosen_door = choice(DOORS)
  opened_door = choice(DOORS - [prize_door, chosen_door])
  switch_door = choice(DOORS - [chosen_door, opened_door])
  stay_win   += 1 if chosen_door == prize_door
  switch_win += 1 if switch_door == prize_door
}

puts "Win rate with a \"don't switch\" strategy: #{stay_win.to_f / GAMES}"
puts "Win rate with a \"switch\" strategy: #{switch_win.to_f / GAMES}"

Example output:

Playing 100000 games...
Win rate with a "don't switch" strategy: 0.33294
Win rate with a "switch" strategy: 0.66706