The Monte Carlo Method
Written by Mike James   
Friday, 01 November 2024
Article Index
The Monte Carlo Method
Simulations
Pi Program
Working out the matrix product
Page 3 of 4

Pi Program

The program is fairly easy. First we set up a loop that will repeat the random "shot" at the target:

var num = 1000;
var total = 0;
var hit = 0;
for (var i = 1; i <= num; i++) {

Next we generate two random numbers x and y and work out how for this point is from the center of the circle at 0.5,0.5:

 var x = Math.random();
 var y = Math.random();
 var r = Math.sqrt(Math.pow(x - 0.5, 2)
                  + Math.pow(y - 0.5, 2));

If the point is closer than 0.5 then we have a hit:

  total++;
  if (r < 0.5) hit++;
  Text1.value = hit / total * 4;
}

If you run the program (using Firefox in this case) for a range of values you get something like:

num     Pi
10      3.2
100     3.16
1000    3.1
10000   3.1512
100000  3.14
1000000 3.143372

As you can see convergence isn't fast but it generating random numbers is fairly cheap.

The complete program as an HTML page is:

<!DOCTYPE html>
<html lang="en">
 <head>
  <meta charset="utf-8" />
  <title>Random Pi</title>
 </head>
 <body>
  <input type="text" id="Text1"/>
  <script>
   var num = 1000000;
   var total = 0;
   var hit = 0;
   for (var i = 1; i <= num; i++) {
    var x = Math.random();
    var y = Math.random();
    var r = Math.sqrt(Math.pow(x - 0.5, 2)
                      + Math.pow(y - 0.5, 2));
    total++;
    if (r < 0.5) hit++;
    Text1.value = hit / total * 4;
   }
  </script>
 </body>
</html>  

More Than Just Areas

You might be convinced that you can work out areas, volumes and even Pi by random numbers but where next?

The answer is that you can estimate the results of just about any numerical computation using randomness in much the same way. The only problem is that explaining how it works would get us ever deeper into mathematics so a simple example will have to do.

You can use the Monte Carlo method to solve linear equations like

Ax=b

where b is a known vector and A is a known matrix.

Usually this problem is solved by inverting the matrix or a similar numerical method but when this is large finding the inverse is an expensive problem. Again randomness comes to the rescue and it is possible to estimate the x vector in much the same way as the needle dropping estimated Pi.

The actual steps to get to the solution are complicated but what about just working out the matrix product y=Ab, where A and b are known.

This isn’t such a big problem but it is a step on the way to solving Ax=b and at first it doesn't  seem to have anything at all to do with random numbers.

See if you can work out how to do it first.
Last Updated ( Friday, 01 November 2024 )