Monte Carlo method in Ruby
Geekery, Programming, Ruby & Rails 1 Comment »“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/.
