Richard Bucker

Monte Hall Paradox

Posted at — Jun 1, 2012

[Updated 2012-06-04] I added a Perl version of the same function.I was recently taking part in a technical interview when the interviewer provided me with the Monte Hall. This is nothing like The Full Monty. It is something completely different. I started to solve the problem using a random DSL of my choosing… which turned out to be something akin to pseudocode or maybe more like detailed comments that one might write for assembler code ‘cause most comments are getting a bad rap these days.My intuition told me that if we started with 3 doors, 1 car and 2 goats… that once Monte removed one of the goat/doors that if I did not change my guess that my odds were going to change from 33% to 50% regardless. Meaning that whether or not I did anything I was going to have the same odds. (spoiler alert: I was wrong)So on my flight home I decided to solve the problem or at least simulate it. (the solution is over my head)[sourcecode language=“python”]#!/usr/bin/env pythonimport random</pre>def monte_hall(change): car = random.randint(1,3) guess = random.randint(1,3) if change: return guess != car return guess == cardef monte_run(change, trials): wins = reduce(lambda acc, trial: acc+monte_hall(change), xrange(1, trials)) print "trials (%d), wins (%d) ratio (%f)" % (trials, wins, (wins / (trials1.0)))if name == "main": trials = 10000 monte_run(False, trials) monte_run(True, trials)[/sourcecode]The code has a few shortcuts in it but those were only implemented after the brute force version implemented it concisely. There may even be a way to reduce the code in the monte_hall() function but it’s small enough for me now. Using the reduce() and lambda were the fun parts thanks to erlang.As a result of the simulation here are a few things I learned:(1) if you do not change your selection after Monte discards one goat/door then your odds of winning are 33%(2) if you ALWAYS change your selection after Monte discards one goat/door then your odds of winning are 66%(3) and while I did not actually focus on this, but if you randomly (50:50) changed then for some strange reason your chances of winning were 50%. This choice has a few problems. Mainly that there aren’t enough trials on the actual show to give you a chance to win. So choosing (2) would always seem to be the best strategy.I decided to rewrite the code in Perl:[sourcecode language=“perl”]#!/usr/bin/env perluse List::Util qw(reduce);</pre>sub monte_hall($) { my ($change) = @; my $car = int(rand(3)); my $guess = int(rand(3)); return $guess != $car if $change; return $guess == $car;}sub monte_run($$) { my ($change, $trials) = @; my $wins = reduce { $a + monte_hall($change) } 0, 1 .. $trials; printf("trials (%d), wins (%d) ratio (%f)\n", $trials, $wins, ($wins / ($trials1.0)));}my $trials = 10000;monte_run(0, $trials);monte_run(1, $trials);[/sourcecode]