“The Monte Carlo method uses random numbers to solve mathematical & statistical problems.” While it’s not a great definition, it’s all I need to say as the “Wikipedia entry for it”:http://en.wikipedia.org/wiki/Monte_Carlo_method explains almost everything you could want to know.

In place of a general explanation I’m going to write briefly about the way in which it can be used to estimate Pi.
[_Explanatory note_: Yesterday I was asked to use an overly complex VB program to analyze estimations Pi using the Monte Carlo Method and, as I’m on a mac, I needed to rewrite it in a language I can understand.]

If we take a square with sides of length _r_, and fill it with a circle (diameter _r_), the probability that a random point on the square will be in the circle is the area of the circle divided by that of the square:

P(In Circle) = Area of Circle / Area of Square

Thus

P(In Circle) = πr^2^ / r^2^ = π

Thus we can estimate Pi by finding the Probability that a Point will land in the circle.

Now, If we take one Quadrant of the circle/square mashup with a radius _r_:


!http://thescri.be/wp-content/uploads/2007/03/monte-carlo.png (Monte Carlo)!


π = P(In Circle) = 4(CircleArea / TotalArea)

If we let _r_=5 and pick a random point on the above square, say (2,3) and work out the distance from (0,0), we can compare this with _r_ to see if the point (2,3) is inside or outside the circle. We can easily find the distance between the two points thanks to “Pythagoras”:http://en.wikipedia.org/wiki/Pythagoras. If we take the root of the summed squares of the point, we’re there. In english:

Point: (2,3)
Length = √(2^2^ + 3^2^)

If this Length is greater than _r_ (in this case _r_=5) then the point is *outside* the circle, if it is less than _r_ it must be *inside*. By repeating this process a number of times we can estimate the value of Pi using our formula.

Here’s a ruby function to do the work for you:

The function myPi(_repetitions_) returns an estimated value of Pi based on the supplied number of repetitions.

There’s a good article similar to this on “datastructures”:http://www.datastructures.info/the-monte-carlo-algorithmmethod/.