I’ve started looking at Monte Carlo methods recently, just for fun. Monte Carlo is a method that attempts to give a probabilistic solution to complex problems. Its premise is that by using random numbers, you can get an idea of how the solution looks like.

The most basic example that I’ve tried is to calculate the value of PI. The story goes like this…

You take a circle circumscribed by a square. Something like a darts board. Imagine now that you throw darts at it randomly. Some of the darts will land within the circle, some others will land in the square but outside the circle. The probabilities of these 2 events are proportional to the areas of the respective areas.

Here’s a good explanation of the theory and the formula:

http://www.chem.unl.edu/zeng/joy/mclab/mcintro.html

A quick an dirty implementation that I came up with in 10 minutes in Python:

import random from math import sqrt radius = 100 hits_total = 0 hits_within = 0 decimals = 4 good_enough_pi = 3.1415926535897932384 approximate_pi = 0 def calculate(): x = random.randint(0, radius) y = random.randint(0, radius) global hits_total, hits_within hits_total += 1 if sqrt(x*x + y*y) <= radius: hits_within += 1 while(int((approximate_pi - good_enough_pi) * (10 ** decimals)) != 0): calculate() approximate_pi = 4 * ( float(hits_within) / float(hits_total) ) print "Calculating PI with 2 decimals took %d tries" % hits_total print "PI~=%s" % str(approximate_pi)

When running this algo, I’ve seen that perhaps 3 out 4 times it runs it completes really quickly for 3/4 decimals. The other one time it takes ages and it doesn’t converge. So in that sense is not reliable. It does converge but it can take millions of tries.

Not to mention trying to get more decimals.

Here I’m just comparing the approximate PI with a pre-calculated PI, but imagine applying Monte Carlo to problems when you can’t pre-calculate (real problems in other words). Well, the problem is that it is difficult to know when your result is good enough and you can stop.

Maybe you can use another Monte Carlo method to determine the probability of a Monte Carlo method to be reliable and converge quickly. Applying Monte Carlo methods recursively…

As I said, basic stuff…