Monty Hall problem
You are encouraged to solve this task according to the task description, using any language you may know.
Run random simulations of the Monty Hall game. Show the effects of a strategy of the contestant always keeping his first guess so it can be contrasted with the strategy of the contestant always switching his guess.
- 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. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you "Do you want to switch to Door Number 2?" Is it to your advantage to change your choice? (Krauss and Wang 2003:10)}}
Note that the player may initially choose any of the three doors (not just Door 1), that the host opens a different door revealing a goat (not necessarily Door 3), and that he gives the player a second choice between the two remaining unopened doors.
Simulate at least a thousand games using three doors for each strategy and show the results in such a way as to make it easy to compare the effects of each strategy.
Ada
<Ada> -- Monty Hall Game
with Ada.Text_Io; use Ada.Text_Io; with Ada.Float_Text_Io; use Ada.Float_Text_Io; with ada.Numerics.Discrete_Random;
procedure Monty_Stats is
Num_Iterations : Positive := 1000; type Action_Type is (Stay, Switch); type Prize_Type is (Goat, Pig, Car); type Door_Index is range 1..3; package Random_Prize is new Ada.Numerics.Discrete_Random(Door_Index); use Random_Prize; Seed : Generator; Doors : array(Door_Index) of Prize_Type; procedure Set_Prizes is Prize_Index : Door_Index; Booby_Prize : Prize_Type := Goat; begin Reset(Seed); Prize_Index := Random(Seed); Doors(Prize_Index) := Car; for I in Doors'range loop if I /= Prize_Index then Doors(I) := Booby_Prize; Booby_Prize := Prize_Type'Succ(Booby_Prize); end if; end loop; end Set_Prizes; function Play(Action : Action_Type) return Prize_Type is Chosen : Door_Index := Random(Seed); Monty : Door_Index; begin Set_Prizes; for I in Doors'range loop if I /= Chosen and Doors(I) /= Car then Monty := I; end if; end loop; if Action = Switch then for I in Doors'range loop if I /= Monty and I /= Chosen then Chosen := I; exit; end if; end loop; end if; return Doors(Chosen); end Play; Winners : Natural; Pct : Float;
begin
Winners := 0; for I in 1..Num_Iterations loop if Play(Stay) = Car then Winners := Winners + 1; end if; end loop; Put("Stay : count" & Natural'Image(Winners) & " = "); Pct := Float(Winners * 100) / Float(Num_Iterations); Put(Item => Pct, Aft => 2, Exp => 0); Put_Line("%"); Winners := 0; for I in 1..Num_Iterations loop if Play(Switch) = Car then Winners := Winners + 1; end if; end loop; Put("Switch : count" & Natural'Image(Winners) & " = "); Pct := Float(Winners * 100) / Float(Num_Iterations); Put(Item => Pct, Aft => 2, Exp => 0); Put_Line("%");
end Monty_Stats; </Ada> Results
Stay : count 507 = 50.70% Switch : count 669 = 66.90%
AWK
#!/bin/gawk -f # Monty Hall problem BEGIN { srand() doors = 3 iterations = 10000 # Behind a door: EMPTY = "empty"; PRIZE = "prize" # Algorithm used KEEP = "keep"; SWITCH="switch"; RAND="random"; # } function monty_hall( choice, algorithm ) { # Set up doors for ( i=0; i<doors; i++ ) { door[i] = EMPTY } # One door with prize door[int(rand()*doors)] = PRIZE chosen = door[choice] del door[choice] #if you didn't choose the prize first time around then # that will be the alternative alternative = (chosen == PRIZE) ? EMPTY : PRIZE if( algorithm == KEEP) { return chosen } if( algorithm == SWITCH) { return alternative } return rand() <0.5 ? chosen : alternative } function simulate(algo){ prizecount = 0 for(j=0; j< iterations; j++){ if( monty_hall( int(rand()*doors), algo) == PRIZE) { prizecount ++ } } printf " Algorithm %7s: prize count = %i, = %6.2f%%\n", \ algo, prizecount,prizecount*100/iterations } BEGIN { print "\nMonty Hall problem simulation:" print doors, "doors,", iterations, "iterations.\n" simulate(KEEP) simulate(SWITCH) simulate(RAND) }
Sample output:
bash$ ./monty_hall.awk Monty Hall problem simulation: 3 doors, 10000 iterations. Algorithm keep: prize count = 3411, = 34.11% Algorithm switch: prize count = 6655, = 66.55% Algorithm random: prize count = 4991, = 49.91% bash$
Haskell
import Random (StdGen, getStdGen, randomR) trials :: Int trials = 10000 data Door = Car | Goat play :: Bool -> StdGen -> (Door, StdGen) play switch g = (prize, new_g) where (n, new_g) = randomR (0, 2) g d1 = [Car, Goat, Goat] !! n prize = case switch of False -> d1 True -> case d1 of Car -> Goat Goat -> Car cars :: Int -> Bool -> StdGen -> (Int, StdGen) cars n switch g = f n (0, g) where f 0 (cs, g) = (cs, g) f n (cs, g) = f (n - 1) (cs + result, new_g) where result = case prize of Car -> 1; Goat -> 0 (prize, new_g) = play switch g main = do g <- getStdGen let (switch, g2) = cars trials True g (stay, _) = cars trials False g2 putStrLn $ msg "switch" switch putStrLn $ msg "stay" stay where msg strat n = "The " ++ strat ++ " strategy succeeds " ++ percent n ++ "% of the time." percent n = show $ round $ 100 * (fromIntegral n) / (fromIntegral trials)
Sample output:
The switch strategy succeeds 67% of the time. The stay strategy succeeds 34% of the time.
Java
<java>import java.util.Random; public class Monty{ public static void main(String[] args){ int[] doors = {0,0,0};//0 is a goat, 1 is a car int switchWins = 0; int stayWins = 0; Random gen = new Random(); for(int plays = 0;plays < 32768;plays++ ){ doors[gen.nextInt(3)] = 1;//put a winner in a random door int choice = gen.nextInt(3); //pick a door, any door int shown; //the shown door do{ shown = gen.nextInt(3); //don't show the winner or the choice }while(doors[shown] != 1 && shown != choice);
stayWins += doors[choice];//if you wonby staying, count it
//could have switched to win switchWins += (doors[choice] == 0)? 1: 0; doors = new int[3];//clear the doors for the next test } System.out.println("Switching wins " + switchWins + " times."); System.out.println("Staying wins " + stayWins + " times."); } }</java> Output:
Switching wins 21924 times. Staying wins 10844 times.
Perl
<perl>my $trials = 10_000;
sub play
- Takes a boolean saying whether to swtich doors; returns
- a boolean saying whether the result was a car.
{my $door1 = !int(rand 3); $_[0] ? !$door1 : $door1;}
sub msg
{print "The $_[0] strategy succeeds ", 100 * $_[1]/$trials, "% of the time.\n";}
sub count {scalar @_}
msg 'switch', count grep({$_} map {play 1} (1 .. $trials)); msg 'stay', count grep({$_} map {play 0} (1 .. $trials));</perl>
Sample output:
The switch strategy succeeds 66.44% of the time. The stay strategy succeeds 32.13% of the time.
Python
<python> I could understand the explanation of the Monty Hall problem but needed some more evidence
References:
http://www.bbc.co.uk/dna/h2g2/A1054306 http://en.wikipedia.org/wiki/Monty_Hall_problem especially: http://en.wikipedia.org/wiki/Monty_Hall_problem#Increasing_the_number_of_doors
from random import randrange, shuffle
doors, iterations = 3,100000 # could try 100,1000
def monty_hall(choice, switch=False, doorCount=doors):
# Set up doors door = [False]*doorCount # One door with prize door[randrange(0, doorCount)] = True
chosen = door[choice]
unpicked = door del unpicked[choice]
# Out of those unpicked, the alterantive is either: # the prize door, or # an empty door if the initial choice is actually the prize. alternative = True in unpicked
if switch: return alternative else: return chosen
print "\nMonty Hall problem simulation:" print doors, "doors,", iterations, "iterations.\n"
print "Not switching allows you to win", print [monty_hall(randrange(3), switch=False)
for x in range(iterations)].count(True),
print "out of", iterations, "times." print "Switching allows you to win", print [monty_hall(randrange(3), switch=True)
for x in range(iterations)].count(True),
print "out of", iterations, "times.\n" </python> Sample output:
Monty Hall problem simulation: 3 doors, 100000 iterations. Not switching allows you to win 33337 out of 100000 times. Switching allows you to win 66529 out of 100000 times.
Scheme
(define (random-from-list list) (list-ref list (random (length list)))) (define (random-permutation list) (if (null? list) '() (let* ((car (random-from-list list)) (cdr (random-permutation (remove car list)))) (cons car cdr)))) (define (random-configuration) (random-permutation '(goat goat car))) (define (random-door) (random-from-list '(0 1 2))) (define (trial strategy) (define (door-with-goat-other-than door strategy) (cond ((and (not (= 0 door)) (equal? (list-ref strategy 0) 'goat)) 0) ((and (not (= 1 door)) (equal? (list-ref strategy 1) 'goat)) 1) ((and (not (= 2 door)) (equal? (list-ref strategy 2) 'goat)) 2))) (let* ((configuration (random-configuration)) (players-first-guess (strategy `(would-you-please-pick-a-door?))) (door-to-show-player (door-with-goat-other-than players-first-guess configuration)) (players-final-guess (strategy `(there-is-a-goat-at/would-you-like-to-move? ,door-to-show-player)))) (if (equal? (list-ref configuration players-final-guess) 'car) 'you-win! 'you-lost))) (define (stay-strategy message) (let ((first-choice (random-door))) (case (car message) ((would-you-please-pick-a-door?) first-choice) ((there-is-a-goat-at/would-you-like-to-move?) first-choice)))) (define (switch-strategy message) (let ((first-choice (random-door))) (case (car message) ((would-you-please-pick-a-door?) first-choice) ((there-is-a-goat-at/would-you-like-to-move?) (car (remove first-choice (remove (cadr message) '(0 1 2)))))))) (define-syntax repeat (syntax-rules () ((repeat <n> <body> ...) (let loop ((i <n>)) (if (zero? i) '() (cons ((lambda () <body> ...)) (loop (- i 1)))))))) (define (count element list) (if (null? list) 0 (if (equal? element (car list)) (+ 1 (count element (cdr list))) (count element (cdr list))))) (define (prepare-result strategy results) `(,strategy won with probability ,(exact->inexact (* 100 (/ (count 'you-win! results) (length results)))) %)) (define (compare-strategies times) (append (prepare-result 'stay-strategy (repeat times (trial stay-strategy))) '(and) (prepare-result 'switch-strategy (repeat times (trial switch-strategy))))) ;; > (compare-strategies 1000000) ;; (stay-strategy won with probability 33.3638 % ;; and switch-strategy won with probability 51.8763 %)