The Monte Carlo Method
Written by Mike James   
Article Index
The Monte Carlo Method
Simulations
Finding Pi
Working out the matrix product

Monte Carlo methods are powerful ways of getting answers using random numbers to problems that really don't seem to have anything much to do with randomness. For example, you can find Pi and multiply two matrices together all by generating random numbers.

 

No this isn’t going to be about gambling, except in the broadest possible sense. Monte Carlo methods are a way of using the computer to solve difficult problems in a most unlikely way. They were invented to solve some of the problems of building the first atomic bomb.

 

Banner

 

When you think about using random numbers in a computer the most obvious application to come to mind is in computer games. Clearly it would be no fun at all if every time you play a game exactly the same set of things occur at exactly the same time. Random numbers are used to vary what happens in unpredictable ways.

A computer dice

Before we look in detail at more advanced ideas let’s look at some simpler ways that random numbers are used and at how to create events with a given set of probabilities.

Perhaps the archetypal use of random numbers is to program a computer dice. Usually the random number generator function, usually called RND or random or something similar, produces fractional numbers scaled into the range 0 to less than 1.

To create numbers in the range 1 to 6 all you need is a simple re-scaling and conversion to integer - using Javascript as an example language:

   Math.floor(Math.random()*6)+1

Most beginners miss the “+1” but of course the random function never produces 1 and so the result without the +1 is in the range 0 to 5 adding one gives you 1 to 6.

Notice that what is going on here is that we are “chopping” up the range of that the random numbers fall in into equal sized regions. Obviously if the regions are equal in size then they have the same probability of that the generated number will fall into one of them.

That is our dice is fair.

dice

Equal sections equals equal probability

By the same reasoning if we want to create a set of events with unequal probability all we have to do is divide the interval up into unequal lengths.

The random number falls into each interval with a probability proportional to the intervals length. In most cases you can’t program this as a simple function but you can use “If” statements to pick out the interval that the random function falls in.

 

dice2

Unequal sections equals unequal probability

 

This is all you need to know to make any set of discrete events happen.However there is the slightly more difficult problem of generating random values in a continuum of possible values.

The random function naturally returns values in the range 0 to 1 which are evenly spread in the interval - they are said to be “uniformly distributed”. Other distributions are often required and there is a whole armory of techniques waiting to come to your aid. For example, if you want a normal distribution all you have to do is add up a few random numbers and work out their average. That is, if you calculate:

n=(Math.random()+Math.random()+
Math.random()+Math.random()+
Math.random())/5

then n will have an approximately normal distribution with a mean of .5.

 

normal

From uniform to normal

This method is based on the central limit theory which says that if you take the average of enough reasonably distributed random values then the result tends to be normally distributed. The central limit theorem is the reason that the normal distribution occurs so often in practice. When ever you encounter some "noise" or randomness that is the average result of lots of other more basic random effects then in general the result tends to be normal because of the central limit theorem.

The central limit theorem works well for the normal distribution but what if you want to generate random numbers with a non-normal but known distribution. To do this you need the cumulative probability distribution. This is just a function that gives you the probability of getting a value less than or equal to x. That is:

F(x) is the probability of getting a result ≤x

cdf

 

For example if you have a fair dice then the cumulative probability function is:

F(1)=1/6
i.e the probabilityof throwing
a 1 or less is 1/6
F(2)=2/6 
i.e. the probability of throwing
a 2 or less is 2/6
F(3)=3/6
F(4)=4/6
F(5)=5/6
F(6)=1

Notice that a cumulative probability function cannot decrease as x increases and in this case it is constant between each of the possible integer values.

 

cdf2

 

You can use a cumulative probability function together with a uniform random number generator in the range 0 to 1 to generate values from the distribution that the function represents. The way that you do this is to use the inverse cumulative probability function F-1(p) which gives you a value x that satisfies F(x)=p i.e. the probability of getting x or less is p. 

What you do to generate random values with the distribution F(x) is generate a random number r in the range 0 to 1 and return F-1(r). If you think about this graphically then you can see that the areas that correspond to each value x generated are proportional to the probability of x.

For example, in the case of the dice example if the random number r generated is between 4/6 and 5/6 then F-1(r) is taken to be 5. You can see that the areas are divided up equally to generate values with a probability of 1/6th.

cdf3

 

In general the areas don't need to be divided equally and the cumulative probability function can be continuous. The algorithm works in a very regular way - find the cumulative probability function, find the inverse cumulative probability function, generate a random number in 0 to 1 and look it up the value in the inverse cumulative probability function. 

Usually the cumulative probability function is available as an approximate table and the inverse function can be created by simply using the table "the other way round".

Banner

 

 

<ASIN:038787836X>

<ASIN:0833030477>

<ASIN:1400063515>

 



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.