Monte Carlo is a simulation method that can be useful in solving problems that are difficult to solve analytically.
Here’s an interesting application of the technique to estimate the value of pi.
Consider a circular dartboard placed against a square backing, with the sides of the square perfectly touching the circle tangentially at the top, bottom, left and right.
If you throw a dart blindly inside of the square, what are the chances the dart will actually land inside the circle?
Assuming the radius of the circle is r, it is:
= area of circle / area of square
= (pi * r ^ 2) / (4 * r ^ 2)
= pi / 4
So the chances of hitting the circle are pi / 4. In other words:
pi = 4 * the chances of hitting the circle.
So let’s set up a Monte Carlo simulation to work out the probability of getting the dart inside of the circle.
To do this, let’s think of the quarter circle below:
Note that the chances of hitting the quarter circle inside of its square is the same as hitting the larger circle inside of the bigger square. How can we easily simulate hitting the quarter circle? We can obtain two random numbers between 0 and 1, representing the x and y coordinates of a point with the origin at the circle’s center. If the distance between this point and the origin is less than 1, then we’re inside the quarter circle. Otherwise we’re outside it. If we simulate this enough times, and multiply the percentage of times we’re inside the circle by 4, we should converge on the value of pi.
Here’s a short python script that simulates this:
>>> from random import random >>> reduce(lambda x,y:x+y,map(lambda x:(random()**2+random()**2)**.5<1,range(100 0000)))/1000000.0*4 3.1411799999999999 >>>
Thanks curious reader, I guess you’re right, a filter is a little simpler:
>>> from random import random >>> len(filter(lambda x:(random()**2+random()**2)**.5<1,range(1000000)))/1000000.0*4 3.14064 >>>
Not to be picky, but don’t forget the “.0″ at the end of the last 1000000 in your list comprehension solution.