Let’s Make A Deal!

July 24, 2009

Since the host always reveals a goat, the only thing that matters is whether the contestant’s initial pick was an auto or a goat; if the initial pick was an auto, staying wins, and if the initial pick was a goat, switching wins. The monty function (named after the original host, Monty Hall), plays n games and reports the number of wins when switching and the number of wins when staying:

(define (monty n)
  (let monty ((n n) (switch 0) (stay 0))
    (let ((auto (randint 3)) (pick (randint 3)))
      (cond ((zero? n) (values switch stay))
            ((= auto pick) (monty (- n 1) switch (+ stay 1)))
            (else (monty (- n 1) (+ switch 1) stay))))))

The variables switch and stay count the number of wins for each strategy. (randint n) returns a non-negative integer less than n; variable auto records the location of the automobile, and variable pick records the location of the contestant’s initial pick.

Running monty for 100,000 contests shows a clear winner:

> (monty 100000)
66824
33176

You can run the program at http://programmingpraxis.codepad.org/54PDMDSv, including rand and randint, which are taken from the Standard Prelude.

When the contestant first makes a choice, he wins the automobile one-third of the time. The other two doors hide the automobile the other two-thirds of the time. When the host reveals a goat, the probabilities don’t change: the door first chosen by the contestant wins the automobile one-third of the time, and wins a goat two-thirds of the time. But since the other two doors hid the automobile two-thirds of the time, and we now know that one of the doors certainly does not hide the automobile, the other door must hide the automobile two-thirds of the time. It is better to switch than stay.

When this puzzle appeared in Marilyn vos Savant’s column in Parade Magazine in 1990, it generated more mail than any previous column; over a thousand people with Ph.D.s thought she was wrong.

About these ads

Pages: 1 2

9 Responses to “Let’s Make A Deal!”

  1. cwbowron said
    #lang scheme
    
    (define DOOR-COUNT 3)
    
    (define (car? n lst) (eq? (list-ref lst n) 'car))
    
    (define (get-door-layout n)
      (let loop ([n n] [doors (list)])
        (cond
          [(= 0 n) doors]
          [(or (member 'car doors)
               (not (= 0 (random n))))
           (loop (sub1 n) (cons 'goat doors))]
          [else 
           (loop (sub1 n) (cons 'car doors))])))
    
    (define (get-random-door door-count criteria-function)
      (let ([door (random door-count)])
        (if (criteria-function door) 
            door 
            (get-random-door door-count criteria-function))))
    
    (define (get-revealed-door doors contestant-selection)
      (get-random-door (length doors) 
                       (lambda (n)
                         (and (not (= n contestant-selection))
                              (eq? (list-ref doors n) 'goat)))))
    
    (define (get-switch-door door-count unavailable-doors)
      (get-random-door door-count (lambda (n) (not (member n unavailable-doors)))))
    
    (define (make-a-deal n (show-debug-info #f))
      (let ([success-count-stick 0]
            [success-count-switch 0])
        (for ((trial (in-range n)))
          (let ([doors (get-door-layout DOOR-COUNT)]
                [selected-door (random DOOR-COUNT)])
            (let ([revealed-door (get-revealed-door doors selected-door)])
              (let ([selected-door-switch (get-switch-door DOOR-COUNT (list selected-door revealed-door))])
                (when show-debug-info
                  (printf "DOORS: ~A~%" doors)
                  (printf "SELECTED DOOR: ~A~%" selected-door)
                  (printf "REVEALED DOOR: ~A~%" revealed-door)
                  (printf "SWITCH DOOR: ~A~%" selected-door-switch))
                (cond [(car? selected-door doors)
                       (set! success-count-stick (add1 success-count-stick))]
                      [(car? selected-door-switch doors)
                       (set! success-count-switch (add1 success-count-switch))])))))
        (printf "Success Rate of Sticking:  ~A%~%" (exact->inexact (* 100 (/ success-count-stick n))))
        (printf "Success Rate of Switching: ~A%~%" (exact->inexact (* 100 (/ success-count-switch n))))
        (if (> success-count-switch success-count-stick)
            (printf "Better off Switching~%")
            (printf "Better off Sticking~%"))))
    
    (make-a-deal 100000)
    
  2. Jamie Hope said

    I already knew that the correct answer is the probability of winning by switching is 2/3, but:

    #!r6rs
    
    (import (rnrs)
            (srfi :27))
    
    (define (create-game) ; false = goat, true = car
      (let ((v (make-vector 3 #f)))
        (vector-set! v (random-integer 3) #t)
        v))
    
    (define (player-choice) (random-integer 3))
    
    (define (host-choice g p) ; host always chooses a goat
      (case p
        ((0) (if (vector-ref g 1) 2 1))
        ((1) (if (vector-ref g 0) 2 0))
        ((2) (if (vector-ref g 0) 1 0))))
    
    (define (switch p h)
      (case (+ p h)
        ((1) 2)
        ((2) 1)
        ((3) 0)))
    
    (define (run-test n)
      (let loop ((wins 0) (total 0))
        (if (= total n) (/ wins total)
            (let* ((g (create-game))
                   (p (player-choice))
                   (h (host-choice g p))
                   (s (switch p h)))
              (if (vector-ref g s)
                  (loop (+ wins 1) (+ total 1))
                  (loop wins (+ total 1)))))))
    
    (display (inexact (run-test 1000000)))
    

    => 0.66756

  3. Mark VandeWettering KF6KYI said

    Ugly, but it works.

    #!/usr/bin/env python
    
    # code for the monty hall problem
    # written by Mark VandeWettering as a challenge on
    # the programming praxis website.
    
    import random
    
    NTRIALS=10000
    
    def trial(switch=False):
            # pick a random door...
            door = random.randint(1, 3)
            guess = random.randint(1, 3)
            if not switch:
                return door == guess
            else:
                # slightly clever, but the only way that you
                # lose is if you were lucky enough (or unlucky
                # enough) to guess the right door in the first
                # place.   This gives away the entire problem.
                return door != guess
    
    cnt_noswitch = 0
    cnt_switch = 0
    
    for x in range(NTRIALS):
        if trial():
            cnt_noswitch = cnt_noswitch + 1
        if trial(switch=True):
            cnt_switch = cnt_switch + 1
    
    print "By not switching, you won %d/%d rounds." % (cnt_noswitch, NTRIALS)
    print "By switching, you won %d/%d rounds." % (cnt_switch, NTRIALS)
    if cnt_switch > cnt_noswitch:
            print "It appears you should switch."
    else:
            print "It appears you should not switch."
    
  4. I suggest also reading a nice treatment of this exact problem in “The man who loved only numbers” by Paul Hoffman.

  5. Brian Everett said

    I’m just now learning Python and figured I’d play around with its list capabilities for this one…

    Originally I was using list comprehension to generate a list of random numbers (to indicate which door the car is behind) and keeping the contestant’s choice constant (always picking door number 1), but I realized it might be slightly faster to randomize the contestant’s choice and assume the car is always located behind door number 1 – simply using the list as a looping mechanism.

    import random
    trials = 100000
    print "Switching will win: %2.2f%% of the time" % (len(filter(lambda trial: random.randint(1, 3) != 1, xrange(trials))) / float(trials) * 100)
    
  6. [...] Let’s Make A Deal! « Programming Praxis. [...]

  7. Greg R said

    I made an attempt in PL/SQL (Oracle). I made the number of doors configurable (assuming that the host opens all doors except yours or the prize, or a random single door if you have chosen the prize door initially).

    declare
      Runs  integer := 10000;
      Doors integer := 3;
    
      function RunMonteHaul
      (
      Runs    in  integer,
      MaxDoor in  integer,
      Swap    in  boolean
      )
      return integer
      is
        Prize     integer;
        OtherDoor integer;
        MyDoor    integer;
        Wins      integer := 0;
        i integer;
        j integer;
      begin
      
        for i in 1 .. Runs loop
          Prize := dbms_random.value(1,MaxDoor);
          MyDoor := dbms_random.value(1,MaxDoor);
          if Prize = MyDoor then
            if Prize = MaxDoor then
              OtherDoor := 1;
            else
              OtherDoor := MaxDoor;
            end if;
          else
            OtherDoor := Prize;
          end if;
          if Swap then
            MyDoor := OtherDoor;
          end if;
          if MyDoor = Prize then
            Wins := Wins + 1;
          end if;
        end loop;
        return Wins;
      end RunMonteHaul;
    begin        
        dbms_output.put_line('Runs  ' || Runs);
        dbms_output.put_line('Doors ' || Doors);
        dbms_output.put_line('Swap Wins    ' || RunMonteHaul(Runs,Doors,true));
        dbms_output.put_line('No Swap Wins ' || RunMonteHaul(Runs,Doors,false));
    end;
    
    

    This produces the output

    Runs  10000
    Doors 3
    Swap Wins    6290
    No Swap Wins 3725
    
    Runs  10000
    Doors 10000
    Swap Wins    9999
    No Swap Wins 1
    
  8. Diego Giuliani said
    # Monty Hall Paradox simulation / Let's make a deal
    # Simulates a number of games and output the total number of wins and looses,
    # and the percentage of each, to determine if switching doors after the host has opened one
    # is a better option.
    
    from random import random,randint
    
    def scrambleDoors(doors):
        """
        Simulates the scramble of doors by choosing one to contain a Car instead of a Goat
        """
        doors[randint(1,3)] = "Car"
        return doors
        
    def pick():
        """
        Choose a door between 1 and 3
        """
        return int(random() * 100) % 3 + 1
            
    def openDoor(door_list,door):
        """
        The host opens a door, wich must not reveal the price, and also is not the one the player has choosen    
        """
        return [i for i in door_list.keys() if (door_list[i] != "Car") & (i != door)][0]
        
    def switchDoor(door_list,door):
        return [i for i in door_list.keys() if i != door]
    
    
    def play():   
       # 1 - Scramble doors   
       doors = scrambleDoors({1:"Goat",2:"Goat",3:"Goat"})
       
       # 2 - Pick a door
       door = pick()
       
       # 3 - Open a door, and remove it from door list 
       od = openDoor(doors,door)
       del doors[od]
    
       # 4 - Switch door
       newDoor = switchDoor(doors,door)
       
       # 5 - Won?
       return doors[newDoor[0]] == "Car"
       
    def game(n = 100):    
        """ 
        n: Number of games to simulate
        """
        
        win = 0
        loose = 0
        for i in range(0,n):
            if (play()):
                win +=1
            else:
                loose += 1
        porcWin = (float(win) / n) *  100
        porcLoose = (float(loose) / n) *  100
        print """
            Runs  : % s
            Win   : %s  Percentage win  : %s
            Loose : %s  Percentage Loose: %s
            """ % (n,win,porcWin, loose,porcLoose)
    

    Which produces the following output

    Runs  : 1000
    Win   : 680  Percentage win  : 68.0
    Loose : 320  Percentage Loose: 32.0
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 574 other followers

%d bloggers like this: