Monte Carlo methods involve the use of computers to make millions of guesses to the solution of a problem. As with the Wisdom of the Crowd the more guesses that are made the closer to the correct solution you get. A common example, when explaining Monte Carlo Methods, is the estimation of a value for Pi. And because Monte Carlo Methods use random numbers we also use in this example the random process of throwing darts blindfolded at a circular dartboard placed on a square backboard.
If we imagine a hypothetical dartboard of radius 1 unit (diameter is 2 units) then we can place this dartboard onto a square backboard of 2 units by 2 units. (see following image)
We know that the area of a square is Height * Width and in this case the area will equal 4 units. The area of a circle is Pi * radius^2 but because we know the radius to be 1 and 1^2 is 1 then the area of our circle is therefore Pi. If we can calculate the area of the circle then we will know the value of Pi. Because the circle touches the four sides of the square then it is seen that we can subtract the area of the square not covered by the circle from the area of the square to leave us with the area of the circle and thence a value for Pi. So how do we determine the area of the square not touched by the circle?
This is where the dartboard analogy is used. If we randomly throw darts in the direction of the backboard and dartboard then darts will hit the dartboard with a frequency of area of circle/area of square. In reality we know that Pi is approximately 3.14... so we would expect darts to hit the dartboard in the approximate ratio of 3.14/4 or about 0.785 times the number of darts thrown. If we multiply our experimentally determined ratio by 4 (the unit area of the square) then we will have a value for Pi.
All we now need to do is throw lots of darts randomly in the general direction of the backboard and work out the ratio of hits to the dartboard to the total number of darts thrown and multiply this answer by 4. We can either do this by buying a dartboard and a backboard (wouldn't that be a fun experiment for young school children!) or we can work it out using Excel (less fun for young school children).
In the next image (click to enlarge) we can see a spreadsheet to calculate Pi by Monte Carlo Methods. Column A is just a count of the number of trials, column B is the X co-ordinate of our dart given by =1-(2*RAND()) and column C is the Y co-ordinate of our dart also determined randomly by =1-(2*RAND()). We use that particular random number generator to give us a range of numbers from -1 to +1, our unit dimensions.
We can now drag these three columns down for as many iterations as we require. In this example I have done 10,000 iterations. (For a greater number we can always run the simulation multiple times by pressing F9 on your keyboard and noting each estimation.)
Next, we want to know if a dart has entered the dartboard rather than the backboard so Columns D and E determine if the co-ordinates in B and C are within the circle. We do this with the formula =IF(B3^2+C3^2<1,B3,0) (see end note) in column D and =IF(B3^2+C3^2<1,C3,0) in column E. Drag these down as far as you have gone in columns B and C. You will notice that sometimes the values in columns D and E are zero. This is because the dart has missed the dartboard.
We can also see scatter plots of the random numbers generated. The square is created by a scatter plot of the numbers in columns B and C and the circle by the numbers generated in columns D and E. These charts show that the numbers are correctly defining our square and our circle.
Columns F and G count the number of darts in the dartboard and the number of darts thrown. There are a variety of ways to do this but checking for X or Y not equal to 0 will count the number of darts in the dartboard for column F. Column G is superfluous as it always counts a dart thrown. In cell F2 we have a count of all darts in the dartboard and cell G2 is just a count of all darts thrown.
Finally, cell I2 is the ratio of darts in the dartboard to darts thrown and cell I3 is that ratio multiplied by 4. As you can see, even for many thousands of trials you will get wildly differing results. Of course, we will never get close to the value of Pi because it is of infinite length but the longer the trial continues the closer we get, within the limits of 32 or 64-bit computing.
The drawback of using Monte Carlo Methods for calculating Pi is that it is a computationally wasteful method. Mathematicians have come up with simple algorithms that calculate Pi to an adequate number of decimal places with just a few iterations. When we use Monte Carlo Methods we must be sure that there is not a simple method for performing our calculations first before we use something like Monte Carlo. For other problems, Monte Carlo Methods may be the only way and my next article will take us towards such problems.
For a book on sports specific Monte Carlo methods there is the excellent Calculated Bets: Computers, Gambling, and Mathematical Modeling to Win by Professor Steven Skiena. Steven constructed a simulation of the game of Jai Alai using Monte Carlo methods for an automated betting system. In chapter three of his book the professor simulated one million games of Jai Alai and was able to construct a model for win, place and show betting. He has also given a video seminar on his work too.
End note
This formula is derived from Pythagoras. Any line (radius) from the centre of this circle to its
edge is of length 1. This line is also the side opposite the right-angled
triangle formed by the centre of the circle and the X & Y co-ordinates thus, if the sum of the two
squares of the co-ordinates is less than 1 then the dart lies along a radius and is therefore on the
dartboard.
