Better Than Fizz Buzz?

Last post I criticized Fizz Buzz. (Actually job interviewers that use Fizz Buzz.) It would be constructive for me to offer an alternative. My choice would be the Monte Hall Problem (MHP). Here is a quick description from the Wikipedia:

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, 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?

The MHP has been one of the first in-class assignments in the introduction to programming classes I have taught. (I believe the best way to learn programming is to read other peoples code and to program yourself. So I have students do both in class.)

Over 50 implementations in various languages are available here.

An interesting thing about the MHP is that an implementation of it can be either an analysis or a simulation. Consider these two versions written in Python.


'''Monte Hall Problem

This program "solves" the Monty Hall Problem.
However, it is not a simulation, it's an analysis!

So anybody unconvinced by this analysis of the problem will likely remain
unconvinced about what a contestant should do in real life!

'''

import random

# Initial conditions:
iterations = 10000000  # law of large numbers
win_if_switch = 0
win_if_dont = 0

# Perform the random experiments
for i in xrange(iterations):

    # Random (1 in 3) chance of car being behind doors 1, 2, or 3
    door_with_car = random.randint(1, 3)

    # Without loss of generality, contestant always picks door 1
    if door_with_car == 1:
        win_if_dont += 1
    else:
        # Only two doors left and Monty narrows that down to one door
        # by exposing a goat door to the contestant, so
        win_if_switch += 1


print "%d: %d to %d" % (iterations, win_if_switch, win_if_dont)

# Example output:
#    10000000: 6666110 to 3333890
#
# Thus, expect about 2 to 1 favorite odds if contestant switches doors.
# Versus 1 in 3 chance of winning a car if contestant doesn't switch.


'''Monte Hall Simulation

Based on the theory that the best way to understand a problem is to
simulate it! Repeatedly!

'''

import random

# Initial conditions:
iterations = 1000000  # law of large numbers
win_if_switch = 0
win_if_dont = 0

# Before the contestant makes her choice, the prizes are set up:
doors = {1: "goat", 2: "car", 3: "goat"}
# Note that Monty knows the car is behind door #2.
# The contestant does not.

# Perform the random experiments
for i in xrange(iterations):

    # First, the contestant picks a door
    # Since she doesn't know it's behind door #2,
    # she has to guess
    picked_door = random.randint(1, 3)

    # Monty offer a switch.
    # Show either door 1 or 3. Obviously, can't show door 2, that's the car!
    if picked_door == 3:
        shown_door = 1
    else:
        shown_door = 3

    # Next, contestant confirms her choice, or switches:
    # Suppose, in one universe, she switches
    if picked_door == 1:
        # Monty showed door 3:
        final_choice = 2
    elif picked_door == 2:
        # Monty showed door 3
        final_choice = 1
    else: # her pick was door 3
        # Monty forced to show door 1
        final_choice = 2

    # So the result if switching
    if final_choice == 2:
        win_if_switch += 1

    # Suppose, in another universe, she does not switch
    # Contestant collects her prize
    if picked_door == 2:
        win_if_dont += 1

print "%d: %d to %d" % (iterations, win_if_switch, win_if_dont)

# Example output:
#    1000000: 666693 to 333307
#
# Thus, expect about 2 to 1 odds if contestant switches doors.
# Versus 1 in 3 chance if don't switch.
# Totals sum to iterations, since in one universe or other,
# someone always wins the car.

The solution to the MHP, that it is doubly preferable to switch doors if given the chance, is unintuitive. Most people think it doesn't matter. So, for most programmers, the process of implementing a correct solution should force them to an unintuitive conclusion. Process over bias! So you would think this a perfect test for competency.

However, this has not been my classroom experience. Before programming the MHP, I would ask the students what they thought the answer should be. As expected, the majority got it wrong. The surprise was that even after implementing a solution (for those that could implement a solution) they implemented the wrong solution. It was the solution they expected.

I suppose there are a lot things that could be said about this.

No comments:

Post a Comment