Qoding: Monte Carlo Simulation – as easy as pie!


With the previous installment of Qoding, and the introduction of ‘Ji’s Pies’, I started to think about the number Pi, and more specifically Monte Carlo Simulation...

With the previous installment of Qoding, and the introduction of ‘Ji’s Pies’, I started to think about the number Pi, and more specifically Monte Carlo Simulation, which can be used to estimate this number to a surprising degree of accuracy.

Monte Carlo methods comprise a wide range of powerful computational algorithms. They use random number generation to obtain results to problems which seemingly have nothing to do with randomness at all.

The fundamental characteristics of Monte Carlo methods are as follows:
1. Random sampling
2. A known input distribution 
3. A repeated numerical experiment

For example, say we have a unit square as below. Circumscribed within the square is a circle with a radius of 0.5. 

soph-blog-1.gif

We know the circle has an area of π/4 (given the area of a circle is πr²), and we use this to formulate our known input distribution. 

To demonstrate, we can implement the algorithm using the following JavaScript.

To begin, we set up a loop that will repeat our numerical experiment

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


We then generate a host of random co-ordinates (x, y) within our unit square.

We can then work out how far our point is from the origin (0.5, 0.5) using the Pythagorean Theorem  c=√(a² + b²)  and check against our given radius of 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 value of r is less than 0.5, we know the point lies within our unit circle, and we have a hit!

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


The greater the number of iterations, the more accurate the estimate becomes.

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

 

So what’s the point to all this number crunching? Well aside from the fun, the answer is that you can estimate the results of just about any numerical computation using randomness in much the same way. From the possibilities of analysing complicated linear equations to questions of probability; using random data to analyse real numerical results has a number of interesting applications. 

Just recently, Monte Carlo Methods have been developed into a technique known as Monte-Carlo tree search, which is a form of artificial intelligence most notably employed to make calculated decisions in game play. 

The primary example being its use in contemporary computer Go programs, but it has also been used in a number of board games, videos games and even poker.

This is the beginning of a wide range of applications that use random numbers to get at answers that would otherwise be too difficult to compute exactly. And with the 21st century being dubbed the Monte Carlo Age, who knows what’s next.

29 May

2015
Sophie Baxter
Listed in:  Development
Estimated read time:
 words,  minutes

Signup to receive these articles straight to your inbox.