Monte Carlo simulation of the Monty Hall Problem in Ruby and Python

Reading Jeff Atwood’s post The Problem of the Unfinished Game, reminded me of a similar problem. The Monty Hall Problem is a well known probability puzzle that has tricked many people. In fact, if you are not familiar with it already, chances are that you’ll get it wrong. And you would be in good company along with many mathematicians and physicists, including the great mathematician, Paul Erdos. This puzzle is loosely based on the television show Let’s Make a Deal, and is equivalent to some much older puzzles you may be familiar with (e.g. the three prisoners problem). In its simplest form, it asks the following question:

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?

This definition of the problem is admittedly ambiguous. Thankfully Wikipedia points us towards a more exact definition:

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 [that is, booby prizes]. 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?

The Monty Hall Problem

Think about it for a moment, then read on. To answer this question, most people will try to determine which of the two possible outcomes has a higher probability. Problems arise when trying to correctly calculate the probability of these two events though. There are two closed doors and the car could be behind either of them. Hence, most people’s “common sense” and psychology leads them to believe that there is a 50% chance that the car is behind the initially selected door, and 50% that it’s behind the other closed door that was offered up by Monty. Initially it would seem that switching or staying with the first choice doesn’t really make a difference.

Unfortunately that’s not the right answer. The correct answer is that there is a two out of three chance of winning by switching to the other door; so switching is always to your advantage. This result is considered to be a paradox because it’s very counterintuitive to the way that many people think. It is in fact so counterintuitive that most people will argue with you in an attempt to convince you otherwise. I invite you to check out the Wikipedia entry on the problem/paradox, to read a step-by-step explanation with figures about why switching gives you about 66.7% chance of winning the car and why staying with the initial choice gives you only a 33.3% success rate.

When you make your first choice your probability of winning the car is only 1/3. If you decide to switch, you will win only if the first choice you made was wrong. And since your first choice came with a 2 out of 3 chance of picking a goat, switching will then (logically) give you 2/3 chance of winning. Another easy way to come to intuitively accept this surprising result, is to wildly exaggerate the terms of the problem. If there were a billion doors, you picked one, and then Monty proceeded to open up all the remaining doors but one, we’d have a situation where it would be extremely unlikely that you picked the right door at the beginning, while it would be extremely likely that the remaining door was the one that was concealing the car.

Even after reading several explanations and aids to understand these results, there are still people who are skeptical or refuse to believe them. Let’s verify the outcome with a simulation.

What you find below is a quick Ruby script that I wrote to run a Monte Carlo Simulation of the Monty Hall problem/paradox. It runs the game a million times and then measures how many times the player won by sticking with their first choice, and how many times switching would have led to winning the car.

#!/usr/bin/env ruby -w

# Monte Carlo simulation for the Monty Hall Problem:
# https://en.wikipedia.org/wiki/Monty_Hall_problem

=begin
When using a Ruby version older than 1.8.7
define the following two methods:

  class Array
    def shuffle
      self.sort_by { rand }
    end
    
    def choice
      self.shuffle.first
    end
  end
=end

# Utility class for the simulation of a single Monty Hall game.
class MontyHall
  def initialize
    @doors = ['car', 'goat', 'goat'].shuffle
  end
  
  # Return a number representing the player's first choice.
  def pick_door
    return rand(3)
  end
  
  # Return the index of the door opened by the host.
  # This cannot represent a door hiding a car or the player's chosen door.
  def reveal_door(pick)
    available_doors = [0, 1, 2]
    available_doors.delete(pick)
    available_doors.delete(@doors.index('car'))
    return available_doors.choice
  end
  
  # Return true if the player won by staying
  # with their first choice, false otherwise.
  def staying_wins?(pick)
    won?(pick)
  end
  
  # Return true if the player won by switching, false otherwise.
  def switching_wins?(pick, open_door)
    switched_pick = ([0, 1, 2] - [open_door, pick]).first
    won?(switched_pick)
  end
  
  private
  
  # Return true if the player's final pick hides a car, false otherwise.
  def won?(pick)
    @doors[pick] == 'car'
  end
end

if __FILE__ == $0
  ITERATIONS = (ARGV.shift || 1_000_000).to_i
  staying = 0
  switching = 0
  
  ITERATIONS.times do
    mh = MontyHall.new
    picked = mh.pick_door
    revealed = mh.reveal_door(picked)
    staying += 1 if mh.staying_wins?(picked)
    switching += 1 if mh.switching_wins?(picked, revealed)
  end
  
  staying_rate = (staying.to_f / ITERATIONS) * 100
  switching_rate = (switching.to_f / ITERATIONS) * 100
  
  puts "Staying: #{staying_rate}%."
  puts "Switching: #{switching_rate}%."
end

And here is an “equivalent” version I wrote in Python:

#!/usr/bin/env python
"""
Monte Carlo simulation for the Monty Hall Problem:
https://en.wikipedia.org/wiki/Monty_Hall_problem.
"""
import sys
from random import randrange, shuffle, choice

DOORS = ['car', 'goat', 'goat']

def pick_door():
"""Return a number representing the player's first choice."""
return randrange(3)

def reveal_door(pick):
"""Return the index of the door opened by the host.
    This cannot be a door hiding a car or the player's chosen door.
    """
all_doors = set([0, 1, 2])
unavailable_doors = set([DOORS.index('car'), pick])
available_doors = list(all_doors - unavailable_doors)
return choice(available_doors)

def staying_wins(pick):
"""Return True if the player won by staying
    with their first choice, False otherwise.
    """
return won(pick)

def switching_wins(pick, open_door):
"""Return True if the player won by switching,
    False otherwise.
    """
other_doors = set([pick, open_door])
switched_pick = (set([0, 1, 2]) - other_doors).pop()
return won(switched_pick)

def won(pick):
"""Return True if the player's final pick hides a car,
    False otherwise.
    """
return (DOORS[pick] == 'car')

def main(iterations=1000000):
"""Run the main simulation as many
    times as specified by the function argument.
    """
shuffle(DOORS)

switching = 0
staying = 0

for dummy in xrange(iterations):
picked = pick_door()
revealed = reveal_door(picked)
if staying_wins(picked):
staying += 1    
if switching_wins(picked, revealed):
switching += 1

staying_rate = (float(staying) / iterations) * 100
switching_rate = (float(switching) / iterations) * 100

print "Staying: %f%%" % staying_rate
print "Switching: %f%%" % switching_rate

if __name__ == "__main__":
if len(sys.argv) == 2:
main(int(sys.argv[1]))
else:
main()

Even if you are not familiar with Ruby or Python, you may be able to understand what’s going on here. The main body of the program emulates the game and keeps track of the number of victories when the player sticks with their initial choice, and when they switch. Notice that this code intentionally tries not to be clever, in order not to annoy “skeptical” people.

There are many points in the code where correct assumptions about the problem would lead us to code that is faster and much more compact. For example, if the player wins a given game by sticking with his first answer, it’s obvious that switching would have made him lose. We could just calculate the difference between 100 and the success rate of staying with the first choice, and we’d obtain the success rate for switching. But here we are trying to simulate the problem as faithfully as possible and abstract as little as necessary.

As always with Monte Carlo Simulations, the outcome is slightly variable during each run since it depends on random input; but by the law of large numbers, it will very slowly converge to the expected values (despite the pseudo-randomness used here). For example, when I executed the code above for the first time on my machine, I obtained the following:


Staying: 33.382%.
Switching: 66.618%.

The results of this simulation should be enough to convince you that the theoretical results are actually true; we are easily fooled, and the mathematicians who got it right were not making stuff up. 😉

Happy New Year to my readers, I wish you all the best for a happy, successful 2009!

Get more stuff like this

Subscribe to my mailing list to receive similar updates about programming.

Thank you for subscribing. Please check your email to confirm your subscription.

Something went wrong.

27 Comments

  1. Niels January 2, 2009
  2. Lucas Sallovitz January 2, 2009
  3. Antonio Cangiano January 2, 2009
  4. Peter Bengtsson January 2, 2009
  5. Tetsuo January 2, 2009
  6. Antonio Cangiano January 2, 2009
  7. Raja S January 2, 2009
  8. Pancho January 3, 2009
  9. Kent January 3, 2009
  10. Raja S January 3, 2009
  11. OtengiM January 4, 2009
  12. Kent January 4, 2009
  13. John January 4, 2009
  14. Tim Kington January 5, 2009
  15. Jonathan January 5, 2009
  16. Antonio Cangiano January 5, 2009
  17. Chad January 5, 2009
  18. Tim Kington January 6, 2009
  19. Bradley Grzesiak January 7, 2009
  20. Daniel January 7, 2009
  21. Kent January 7, 2009
  22. Ryan February 2, 2009
  23. Jérôme February 6, 2009
  24. Francesco March 5, 2009
  25. Gustav Isaac October 2, 2009
  26. Blinkozo November 18, 2009
  27. Al December 10, 2009
  28. Pingback: Using Programming to Teach Mathematics July 29, 2016

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.