Monte Carlo simulation of the Monty Hall Problem in Ruby and Python | Hacker News Reader

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

antoniocangiano.com

22 pointsacangiano11 comments

Wow, that's a lot of code.

  def main(iter=100000):
	stay_win = 0.0
	switch_win = 0.0
	for i in xrange(iter):
		win_door = int(numpy.random.uniform()*3)
		pick_door = int(numpy.random.uniform()*3)
		if pick_door == win_door: 
			stay_win += 1.0
		else: 
			switch_win += 1.0
	print 'stay: ', stay_win/float(iter)
	print 'switch: ', switch_win/float(iter)
	return

Your code doesn't really provide "proof." You've completely omitted the host's door elimination. I know in the end it doesn't matter, but if you already knew the answer you would code the simulation in the first place, right?

Not that this really needs another implementation, but since I already wrote it before seeing this thread...

  (defun monty-hall (strategy &aux (winner (random 3)) (choice (random 3)))
    (let ((monty (if (= winner choice)
                     (do ((x (random 3) (random 3)))
                         ((/= x winner) x))
                     (- 3 (+ winner choice)))))
      (case strategy
        (:stay (= winner choice))
        (:change (= winner (- 3 (+ choice monty)))))))

(looping and reporting omitted)

Incidentally, I think the code in the original article provides a good example of how code can be so verbose as to detract from understanding. Good code clarifies a problem rather than obfuscating it under the weight of useless detail.

You make a good point, and there is definitely some value to including that step (although it would be only another 2 lines of code actually.) I considered putting it in, but didn't because of the following:

1. The only leap of logic required is to realize that the two options are mutually exclusive: either you win by staying or you win by switching. There is no alternative.

2. Writing the code in that concise form, I believe the inherent structure of the problem is much clearer than the mess of classes and function calls.

Question: why are stay_win and switch_win floats? Why not make them integers, and just do a conversion when you're printing the results out?

That way you can do increments with integers which should be cheaper.

Is that the case? I've never profiled it actually. I always just assumed that basic operations (float and int) were all single cycle since there is such a huge incentive to optimize those on the CPU.

Random tangent: a while ago I was working on a project where we used a big fancy MCMC algorithm to do some computer vision task. One issue we ran into was that double types didn't have enough precision to compute the partition function. We spent along while trying to figure out a way around having to compute it, and put in 10-20k lines of C++ code to make it happen. Really complicated. Took forever. One day I had the rather silly idea to just use an arbitrary precision floating point library. It was a silly idea because we profiled it and found that it was 20x slower for all floating point computations which seemed to be the bulk of the algorithm (and performance REALLY mattered here.) I decided to try it out on the theory that 90% of the CPU time was spent on memory access, looping, and program jumps, and that even though we had a ton of floating point operations, they were basically free. So I implemented it, and as it turned out we did indeed get a 20x slowdown on our floating point computations. But the overall algorithm only lost about 1% or so, because the floating points stuff only constituted a tiny fraction of the total cost. Since then I just ignore the cost of arithmetic and focus 100% on optimizing program flow. Almost seems obvious in retrospect, but I still see code where people jump through hoops to save a few multiplications, even though in the end it usually costs them more due to cache misses inherent in loops and program jumps.

Using floats without need adds noise to the code, e.g. the ".0"s in foo = 0.0; bar += 1.0, and makes the reader wonder why floats are being used. "What am I missing?"

Thanks, I meant that but got distracted by "oh! optimization opportunity!"

Yay you're smart. You get a gold star.

Did you even read the part where he said his code was intentionally simplistic and not optimized? Making a fast/efficient simulation was not the point at all.

No need to be so harsh. It's a natural reflex to rewrite code-- a way of understanding it.

You're right. That was unnecessary.

axiom, I apologize. I don't know what got into me.

Reply on news.ycombinator.com