Basic Monte Carlo

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…

Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: