[Curtis Rutland]

Wiki link: Monty Hall Problem

Quote

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Answer:

Spoiler

Quote

Vos Savant's response was that the contestant should always switch to the other door. If the car is initially equally likely to be behind each door, a player who picks door 1 and doesn't switch has a 1 in 3 chance of winning the car while a player who picks door 1 and does switch has a 2 in 3 chance, because the host has removed an incorrect option from the unchosen doors, so contestants who switch double their chances of winning the car.

Some of you yourselves may not believe the predicted result.

Here's the interesting bit from the article:

Quote

Many readers refused to believe...After the Monty Hall problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming that vos Savant was wrong (Tierney 1991). Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept...the best strategy. According to the French magazine Le Figaro Magazine, Paul Erdős, the most prolifically published mathematician of modern times, found it very hard to believe the result of his own calculations, and admitted he was not fully convinced until a simple computer simulation confirmed the predicted result.

So, let's write our own simulations and prove or disprove this! Your program can be as simple or complex as you feel necessary, as long as it proves your theory. It must incorporate these key points:

• There are three prizes, one good and two bad.
  
• After one prize is chosen by the player (at random, without knowing what they have), one bad prize is removed from the left-over choices.
  
• This is where the simulations must diverge. You must show what happens when the contestant keeps the prize they've already chosen, and what happens when they switch.
  
• Repetition is key. Small sample runs prove nothing. Write your program so that it proves your hypothesis, or at least strongly suggests it with data.

This is posted in the C# section, but I welcome any language submission.

Please post your answer code in spoilers. I'll post mine once we get a few entries.

Edit for clarity: our goal here is to actually write a program to perform the simulation. I know that this is a simple problem to prove with math, but the fun is in writing the code to prove that. I've updated the title to make this more clear.

[jon.kiparsky]

The proof has already been provided.

To look at it another way, imagine that there are 100 doors. Now, after you pick one, the host opens 98 doors, leaving one closed. What are the odds that you picked the right door the first time? 1/100. Therefore, what are the odds that the prize is behind the remaining closed door? 99/100.

The same logic holds when N = 3.

Another way to convince yourself is to imagine that you get to select two doors of four - if you have a winner, you keep it. Now the host opens one door each from the selected and the unselected doors. Does switching help you in this case?


The challenge, if you want to be particular about it, is not to prove, but to illustrate the provided proof.

This post has been edited by jon.kiparsky: 19 September 2012 - 01:02 PM

[Curtis Rutland]

Completely true. I suppose I should have made it more clear that this is a programming exercise to prove what math can and has already proven with an actual simulation.

[jon.kiparsky]

Just me being nitpicky, don't mind me. Expect a scala solution this evening, since that's what I'm learning now.

[modi123_1]

Heh.. I was going to post a link to Mythbusters and declare myself done. Now I gotta write up some code that links to, and plays, the mythbusters video to win!

[jon.kiparsky]

I'm going to deliver actual goats and cars to the user. You're going to have to beat that, buddy.

[modi123_1]

Pffssh.. what evs..

Who would want your Bostonian sourced gutter goats anyways with their broad-a bleats and reeking of Belichick's musk?

I, on the other hand, have organically grown petite lap goats that also dress up in AT-AT costumes, bleat with an accent neutral voice of an angel, and are hypoallergenic.

[CodeGrappler]

modi123_1, on 19 September 2012 - 01:21 PM, said:

Pffssh.. what evs..

Who would want your Bostonian sourced gutter goats anyways with their broad-a bleats and reeking of Belichick's musk?

I, on the other hand, have organically grown petite lap goats that also dress up in AT-AT costumes, bleat with an accent neutral voice of an angel, and are hypoallergenic.

But you don't have cars...

[modi123_1]

My petite lap goats believe in being green - that's why some dress up as AT-ATs - as a simulation of a car without the unneeded carbon foot print.

[jon.kiparsky]

Not much meat on one of them petite lap coats, is there?

[CTphpnwb]

Too soon?

Spoiler

C++ code:

#include <iostream>
#include <time.h>
#define NUM_TRIALS 10000 // Pick a number of trials to run. The larger the number, the closer to 1/3 and 2/3 wins for not switching and switching.
using namespace std;
#include <vector>
void initialize(bool d[]) {
	int num = rand() % 3;
	for (int i = 0; i < 3; i++) {
		d[i] = false;
	}
	d[num] = true;
}

int open_door(bool d[], int chc) {
	int gt;
	static vector<int> vec;
	for (int i = 0; i < 3; i++) {
		if (i != chc && ! d[i]) {
			vec.push_back(i);
		}
	}
	gt = vec[rand()%vec.size()];
	while (vec.size() > 0) {
		vec.erase(vec.begin());
	}
	
	return gt;
}

int other_door(bool d[], int chc, int gt) {
	for (int i = 0; i < 3; i++) {
		if (i != chc && i != gt) {
			return i;
		}
	}
	cout << "oops!" << endl;
	exit(1);
	return 9; // Error if we get here because there should always be a door to switch to.
}

int main (int argc, char * const argv[]) {
	srand(time(NULL));
	bool doors[3];
	int trial, choice, goat, cars, change;
	for (change = 0; change < 2; change++) {
		cars = 0;
		for (trial = 0; trial < NUM_TRIALS; trial++) {
			initialize(doors);
			choice = rand() % 3;
			goat = open_door(doors, choice);
			if (change) {
				choice = other_door(doors, choice, goat);
			}
			if (doors[choice]) {
				cars++;
			}
		}
		if (change) {
			cout << "When switching doors, we won: "<< cars << "/" << NUM_TRIALS << " trials." << endl;
		} else {
			cout << "When NOT switching doors, we won: "<< cars << "/" << NUM_TRIALS << " trials." << endl;
		}

	}

	return 0;
}

This post has been edited by CTphpnwb: 19 September 2012 - 02:29 PM

[Curtis Rutland]

Definitely not too soon.

Here was my solution:

Spoiler

internal class Program
{
    private enum Prize { Donkey, Car }
    private static readonly Random Random = new Random();

    private static void Main(string[] args)
    {
        RunSimulation(10000, true);
        RunSimulation(10000, false);
        Console.ReadKey();
    }

    private static void RunSimulation(int count, bool swap)
    {
        float wins = 0, losses = 0;
        for (var i = 0; i < count; i++)
        {
            if (PlayGame(swap)) wins++;
            else losses++;
        }
        Console.WriteLine("{0} runs. {1}. Wins {2} ({3:0.00%}), Losses {4} ({5:0.00%})",
            count, swap ? "Swapping" : "Not Swapping", 
            wins, (wins / count), losses, (losses / count));
    }

    private static bool PlayGame(bool swap)
    {
        //Create the prizes
        var doors = new List<Prize> { Prize.Car, Prize.Donkey, Prize.Donkey };

        //player chooses a door at random
        var index = Random.Next(0, doors.Count);
        var playerChoice = doors[index];
        doors.RemoveAt(index);

        //host removes one donkey-containing door:
        doors.Remove(Prize.Donkey);

        //if we're changing, take the last one left in the prize list
        if (swap) playerChoice = doors[0];

        return playerChoice == Prize.Car;
    }

}

[baavgai]

Sorry, been working in Python all day.

Spoiler

Plus, I rather liked the idea of a what's essentially a two liner.

from random import randint

def monty(sampleSize = 10000):
	winIfSwitchTotal = sum(1 
		for (firstChosenDoor, winningDoor) 
			in ((randint(0,2) for i in range(2)) for i in range(sampleSize))
			if not firstChosenDoor==winningDoor)
	print("Of {0} trails, {1} would be won if initial choice abandoned, or {2}%".format(
		sampleSize, winIfSwitchTotal, (winIfSwitchTotal/float(sampleSize)*100.0)
		))

Wondering if any clever LINQ person could make that happen in C#, since it looks rather LINQy.

[jon.kiparsky]

Here's a pretty straightforward python implementation. Too tired to try to do it in scala tonight.

Spoiler

#!/usr/bin/python

import random

num_doors = 3
iterations = 10000

def test_run(iterations, num_doors, switchp):
   result = 0
   for i in range(iterations):
      result += doTrial(num_doors)
iterations = 10000

def test_run(iterations, num_doors, switchp):
   result = 0
   for i in range(iterations):
      result += doTrial(num_doors)
   if switchp: 
      result = iterations-result
   return result
   
def doTrial(num_doors):
   return gen_doors(num_doors)[random.randrange(num_doors)]
   
 
def gen_doors(num_doors):
   doors = list([0]*num_doors)
   doors[random.randrange(num_doors)] = 1
   return doors



def run_simulation(iterations, num_doors):
   print "Results for", iterations, "trials"
   print "Wins under switch condition: ", test_run(iterations, num_doors, True)   print "Wins under no-switch condition: ", test_run(iterations, num_doors, False)

EDIT: Due to technical difficulties, this version does not deliver goats and cars. However, if my kickstarter comes through I'll be developing my e-goat delivery system and that little glitch will be addressed.

This post has been edited by jon.kiparsky: 20 September 2012 - 11:54 AM

[fromTheSprawl]

I'm not sure if what I did is correct, but here's something from Python:

Spoiler

def addDoors():
    picker =  randint(0,1)
    if picker == 1:
            door1,door2,door3 = "dragon","goat","goat"
    else:
            door1 = "goat"
            picker = randint(0,1)
            if picker == 1:
                    door2,door3 = "dragon","goat"
            else:
                    door2,door3 = "goat","dragon"
    return [door1,door2,door3]

 def openGoatDoor(doors):
     door = ""
     while door != "goat":
             doorNumber = randint(0,2)
             door = doors[doorNumber]
     return doorNumber


def montyhall(doorNumber,switchOk):
     doors = addDoors()
     goatDoor = openGoatDoor(doors)
     while goatDoor == doorNumber:
             goatDoor = openGoatDoor(doors)
     if switchOk == "yes":
             doorNumber = randint(0,2)
             while doorNumber == goatDoor:
                     doorNumber = randint(0,2)
     return doors[doorNumber]
	 
def testMontyHall(playTimes,switch):
    wondragon,wonGoat = 0,0
    for i in range(playTimes):
            prize = montyhall(randint(0,2),switch)
            if prize == "dragon":
                    wondragon += 1
            else:
                    wonGoat += 1
    print "Dragons:",wondragon
    print "Goat:",wonGoat

100 runs

Spoiler

---No Switch---
Dragons: 35
Goat: 65
---Switched---
Dragons: 51
Goat: 49
---No Switch---
Dragons: 38
Goat: 62
---Switched---
Dragons: 49
Goat: 51
---No Switch---
Dragons: 33
Goat: 67
---Switched---
Dragons: 49
Goat: 51
---No Switch---
Dragons: 31
Goat: 69
---Switched---
Dragons: 51
Goat: 49
---No Switch---
Dragons: 31
Goat: 69
---Switched---
Dragons: 51
Goat: 49

1000 runs

Spoiler

---No Switch--
Dragons: 347
Goat: 653
---Switched---
Dragons: 493
Goat: 507
---No Switch--
Dragons: 324
Goat: 676
---Switched---
Dragons: 516
Goat: 484
---No Switch--
Dragons: 339
Goat: 661
---Switched---
Dragons: 496
Goat: 504
---No Switch--
Dragons: 346
Goat: 654
---Switched---
Dragons: 494
Goat: 506
---No Switch--
Dragons: 333
Goat: 667
---Switched---
Dragons: 472
Goat: 528

A million ways

Spoiler

Whoops, wrong one.

Here it is:

Spoiler

---No Switch---
Dragons: 333266
Goat: 666734
---Switched---
Dragons: 499739
Goat: 500261
---No Switch---
Dragons: 332995
Goat: 667005
---Switched---
Dragons: 499654
Goat: 500346
---No Switch---
Dragons: 333703
Goat: 666297
---Switched---
Dragons: 499560
Goat: 500440
---No Switch---
Dragons: 333127
Goat: 666873
---Switched---
Dragons: 499563
Goat: 500437
---No Switch---
Dragons: 334095
Goat: 665905
---Switched---
Dragons: 500426
Goat: 499574

Yeah I know, the code needs improvement lots. I hope one day I can do something like baavgai's on Python.
From the figures, yeah I think the Monty Hall problem proves itself... unless if what I did is completely off. There there.