2010-01-24

Monty Hall Problem Simulator (ruby implementation)

Monty Hall problem is a probability problem based on an American TV show, Let's make a deal. The details are in the Wiki, http://en.wikipedia.org/wiki/Monty_Hall_problem. The point of this blog entry is a simulator of the problem, so, I only make a brief explain about that.

--- Rule ---
  1. There are three doors (A, B, C), and (cat, donkey, donkey) are behind randomly.
  2. The player choose a door.
  3. The host always open one of the door that is not chosen by the player, regardless which door was chosen by the player.
  4. The host knows the where is the car, and always open the donkey door. If both unchosen doors are donkey door, the host decide the door by flipping a coin.

(Cited from Wikipedia Japan's Monty Hall problem)


The question is 'Should the player switch the choice?', or it does not matter?

The answer is 'always switch is better.' The switch makes twice possibility to get a car.

At the end of this blog, you can find the Monty Hall Problem simulator. It is written by ruby. The logic is pretty simple and you can write any other languages. (By the way, I implemented the rule 2 as: the player choose the door equally distributed randomly. All the random generator implementation is ruby's build-in rand().)

The result of 10000 time trials is

Result: switch win ratio = 0.6689, switch lose ratio = 0.3311.

This means switch strategy wins 2/3 probability. (In my implementation, random number sequence is initialized as always the same, therefore, you can get the same answer on your machine. I have tried this ruby 1.8.7.)

When this problem is explained at a magazine, there are so many 'you are wrong' letters from the readers including professional mathematician. Maybe,

'Switching strategy is twice better'

is a bit odd as intuition. And if we properly define the problem,

'We can make the case switch doesn't matter.'

Some people find this suits for their intuition. In the magazine's article, some rules are implicitly assumed (though, they are reasonable, I presume.) These conditions makes it an flame article.

My intuition of 'independent events' is not so good. For example, if a right dice shows the 'one' eye five times sequentially, I don't feel to bet 'one' next time. But this is independent event and it should not matter. Since a dice never remembers the last number and never change the number according to the last number.

For this problem, conditional probability is not the same as the first possibility. My intuition also has the problem for that. For an extremely case, if we can get the information of car door instead of donkey, it doesn't matter the probability theory. Then it is obvious information changes the result. Here, the player got some kind of information.

Because of the doubt of my intuition to the probability theory, I wrote many small simulators like this. When I wrote a simulator, I could realize what kind of assumption is necessary to implement the simulator. Here whenever I wrote the 'rand' statement, I need some kind of assumption. Especially, around the line 82 of this problem needs a special care and also the logic around the line 82. If the assumption is changed, the simulator's behavior will change. There are a lot of interesting things related with this on the Wiki page.


#! /usr/bin/ruby
#
# $Id$
# Copyright (C) 2010 Hitoshi
#
# Monty Hall Problem simulator 2010-1-22(Fri)
#
# The following is the problem rule definition. It seems that Monty
# didn't clearly define the problem, so, we employ some
# assumptions. If this rule is changed, the probability will change.
#
# 1. There are three doors (A, B, C) that has (car, donkey, donkey) and
# the assign is chosen equally distributed randomness.
#
# 2. Player choose one of the door
#
# 3. Host open one of the door that is not chosen by the player
# regardless which door is chosen by the player.
#
# 4. Host knows which door has a car (Host know the information). Host
# only open the door which has a donkey. If the both doors that is not
# chosen by the Player have donkey, Host choose one of them according
# to equally distributed random number.
#
# Actually, the rule 3. and 4. are not clear (Monty didn't mention
# this definition.) The rule 1 seems satisfied, but, could be
# violated. For example, the host can move the car, or they can put
# the car after the Player choose the door. If you change these rules,
# the probability will be changed. This makes interesting
# confusion. See WikiPedia, Monty Hall Problem.
#
# http://en.wikipedia.org/wiki/Monty_Hall_problem
# http://www.youtube.com/watch?gl=US&v=mhlc7peGlGg
#
#
require "getoptlong.rb"

MONTYHALLSIM_VERSION = "0.1.0"

#------------------------------------------------------------
# help
#------------------------------------------------------------
def print_help()
$stderr.print <<"HELP"
usage: montyhallsim.rb [-h|--help] [-v|--version] number_of_trials
Monty Hall Problem simulation.
-h, --help output this help.
-V, --version show version.
number_of_trials simulation number
By Hitoshi.
HELP
end

#------------------------------------------------------------
# verbose output
#------------------------------------------------------------
def verboseprint(mes)
if $OPT_VERBOSE then
$stderr.print mes
end
end

#------------------------------------------------------------
# class montyhallsim
#------------------------------------------------------------
class MontyHallSim
# constructor
# FIXME
def initialize()
# @foo is instance variable

# winning count when switch the choise
@switch_win_count = 0
end

# one trials and keep the results in member
def one_try()
# generate the car, donkey, donkey
car_pos = rand(3)
player_choice = rand(3)

if car_pos == player_choice then
# if player's initial choise is the car, choose one of the rest
# with 1/2 possiblity
open_choise = rand(2)
open_pos = (player_choice + (open_choise + 1)) % 3
else
# if player's initial choise is not the car, choose the only one
# possible donkey
if (player_choice + 1) % 3 == car_pos then
open_pos = (player_choice + 2) % 3
else
open_pos = (player_choice + 1) % 3
end
end

# show the status
doors = ['*', '*', '*' ]
doors[player_choice] = "P"
doors[open_pos] = "H"

# player position 'P' and Host open position 'H'
print "Player-Host: ";
doors.each { |x| print x.to_s + ' ' }
print "\n";

# and the car 'C'
print "Car: ";
doors[car_pos] = "C"
doors.each { |x| print x.to_s + ' ' }

# keep the record
if player_choice != car_pos then
@switch_win_count = @switch_win_count + 1
print " ... switching win!";
end
print "\n";
end


# run simulation
# \param _number_of_trials simulation number of trials
def run(_number_of_trials)
begin
# check number of trials
raise "0 number of trials" if _number_of_trials <= 0

# init random sequence (but always the same sequence in this
# implementation)
srand(0)
i = 0;
while i < _number_of_trials do
one_try()
i = i + 1
end

# output the result
print "Result: switch win count = " + @switch_win_count.to_s + "\n"
switch_win_ratio = @switch_win_count.to_f / _number_of_trials.to_f

print "Result: switch win ratio = " + switch_win_ratio.to_s +
", non-switch win ratio = " + (1 - switch_win_ratio).to_s + "\n"

rescue
# `$!' has the last exception object
print "Error! " + $!.message + "\n"
end
end
end

#------------------------------
# command line option parsing
#------------------------------
args = GetoptLong.new();

# ['--output', '-o', GetoptLong::REQUIRED_ARGUMENT],
args.set_options(
['--help', '-h', GetoptLong::NO_ARGUMENT],
['--version', '-v', GetoptLong::NO_ARGUMENT]
);

begin
args.each_option do |name, arg|
# print(name + ", " + arg + ":\n")
eval "$OPT_#{name.sub(/^--/, '').gsub(/-/, '_').upcase} = '#{arg}'"
end
rescue
exit(1)
end

#--- help
if $OPT_HELP
print_help
exit(1)
end

#--- show version
if $OPT_VERSION
$stderr.print(MONTYHALLSIM_VERSION + "\n")
exit(1)
end

#--- dotfile only option
is_dotfileonly = false
if $OPT_DOTFILEONLY
dotfileonly = true
end

#--- get number of trials
if ARGV.length == 0 then
number_of_trials = 100
elsif ARGV.length == 1
number_of_trials = ARGV[0].to_i
else
$stderr.print("Error! illegal number of arguments.\n")
print_help
exit(1);
end

# --- backup
dback = MontyHallSim.new()
dback.run(number_of_trials)

# --- end of montyhallsim.rb