Python Monte Carlo

November 13, 2011 – 9:51 pm

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
>>>

EDIT 12/4/2011
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.

  1. 3 Responses to “Python Monte Carlo”

  2. What’s with using map and then reduce to count the nummber of true results, why not just use filter?

    For python 3 and list comprehension folks:
    len([hit for hit in range(1000000) if (random()**2+random()**2)**.5<1])/1000000*4

    Thought this twitching corpse of a blog had died off in shame but it appears the necro is strong in this one.

    That said, great conceptual intro to monte carlo, very original.

    By A curious reader on Nov 30, 2011

  3. A nice introduction to Monte Carlo simulations that easily extends to other interesting questions.

    For example: How many times do you need to throw the darts (on average) to calculate PI to 3 decimal places? How many times if you want to get it to 5 decimals places? Is it possible to calculate the expected accuracy of 100 million throws?

    Fun!

    By Scruffy Pete on Jan 16, 2012

  1. 1 Trackback(s)

  2. Nov 16, 2011: Rebrained! » Blog Archive » Black Scholes Monte Carlo in Python

Post a Comment