Monte Carlo Simulation

• Download source code - 2.76 KB

Introduction

A class of computational algorithms that rely on repeated random sampling to compute their results are called the Monte Carlo methods. Monte Carlo methods are often used when simulating physical and mathematical systems. Because of their reliance on repeated computation and random or pseudo-random numbers, Monte Carlo methods are most suited to calculation by a computer. Monte Carlo methods tend to be used when it is infeasible or impossible to compute an exact result with a deterministic algorithm.

Monte Carlo algorithms work based on the Law of Large Numbers. It says that if you generate a large number of samples, eventually, you will get the approximate desired distribution.

Monte Carlo methods have three characteristics:

1. Random sample generation
2. The input distribution is known
3. Numerical experiments

The direct output of the Monte Carlo simulation method is the generation of random sampling. Other performance or statistical outputs are indirect methods which depend on the applications.

There are many different numerical experiments that can be done, probability distribution is one of them.

Probability distribution identifies either the probability of each value of an unidentified random variable (when the variable is discrete), or the probability of the value falling within a particular interval (when the variable is continuous).

That is equivalent to saying that for random variables X with the distribution in question, Pr[X = a] = 0 for all real numbers a. That is, the probability that X attains the value a is zero, for any number a. If the distribution of X is continuous, then X is called a continuous random variable.

Normal distribution, continuous uniform distribution, beta distribution, and Gamma distribution are well known absolutely continuous distributions.

In the sample program, I will be using a Triangular distribution, which is is a continuous probability distribution with a lower limit a, mode c, and upper limit b.

Triangular distribution is therefore often used in business decision making, particularly in simulations. Generally, when not much is known about the distribution of an outcome (say, only its smallest and largest values), it is possible to use uniform distribution. But, if the most likely outcome is also known, then the outcome can be simulated by a Triangular distribution.

Whilst Monte Carlo methods can be a valuable aid to decision making, they should not be used without an understanding of the process being modeled. Typically, in any activity, there are a few critical inputs, and it is these which should be the focus of the analysis, not trying to attribute complex distributions to minor variables. So, a Monte Carlo analysis should be preceded by a sensitivity analysis to determine what the important parameters are.

Background

There are many ways of approaching a Monte Carlo analysis, but a good starting point is a flow chart of the processing being modeled.

For the purposes of this simulation, I will be focus on a tennis tournament simulation based on game winnings.

The flow chart of the process goes like this:

Using the code

Here is an example where we have two players, each with varying skills and talent. Assume they each have played 10 tournaments and we have gotten the minimum and maximum number of wins (assuming winning the tournament has the same number of wins as all the other tournaments). We can also compute the mean win for all the 10 tournaments they have played.

double[] VarWins = new double[]{player1,player2}];
double[] minWins = new double[]{11,12};
double[] meanWins = new double[]{12.5,13};
double[] maxWins = new double[]{17,15};
double[] results = MonteCarlo.simulate(2, new double[] { 11, 12 }, 
                   new double[] { 12.5, 13 }, new double[] { 17, 15 });

The main simulation is done using the following triangular distribution:

public static double triangular(double  Min,double  Mode,double  Max)
{ 
    //   Declarations
     double  R=0.0;
    //   Initialise
    Random r = new Random();
     R = r.NextDouble();       //between 0.0 and 1.0 gaussian
    //    Triangular
    if ( R == (( Mode -  Min) / ( Max -  Min)))
    {
        return  Mode;
    }
    else if ( R < (( Mode -  Min) / ( Max -  Min)))
    {
        return  Min + Math.Sqrt( R * ( Max -  Min) * ( Mode -  Min));
    else
    {
        return  Max - Math.Sqrt((1 -  R) * ( Max -  Min) * ( Max -  Mode));
    }
}

As seen in the output, player 1 is the most likely to win. However, player 2 is not far behind. So, with a little more practice and training, player 2 manages to reduce the mean number of wins on the next 10 tournaments. Simulating this again will show that he has greatly improved his performance and is most likely to win over player 1.

Output:

Simulation Results
Wins5251
Wins4749
Player1 win probability 52.51
- Player2 win probability47.49

Output after training:

Simulation Results
Wins4119 
Wins5881
Player1 win probability 41.19
- Player2 win probability58.81:

There are some instances where it is the other way around. As I have mentioned ealier, by the Law of Large Numbers, if you increase the number of simulated tournaments, you will notice that either player will always be the winner because the expected result will always come closer because of the large number of simulations.

More examples on the Monte Carlo algorithm can be found here.

Application

Monte Carlo methods are often used in Physics to determine neutron trajectories or to simulate atomic clusters. In the 1950s, Monte Carlo methods were used to study nuclear cascades. When a particle collides with a nucleus, a nuclear cascade is produced.

The particle’s path after the collision determines whether or not a new particle, a pion, is created. Monte Carlo methods keep track of the colliding particle’s path after the collision and determine the probability of the production of pions. Monte Carlo algorithms are useful here because it is difficult and time-consuming to simulate the collisions. By running the algorithm enough times, the results are usually statistically significant, and we are able to successfully calculate the probability of the production of nuclear cascades. Chemistry is another field where Monte Carlo methods come in handy.

Monte Carlo methods are often used to evaluate integrals. While integrals can be evaluated by many other mathematical methods, it is, sometimes too complex for other methods to evaluate an integral as its dimensionality grows. Not being able to evaluate an integral with growing dimensions is known as the ‘curse of dimensionality’. However, Monte Carlo methods outdo this curse because they work increasingly better with more complex integrals that contain high dimensions. Evaluation of multidimensional integrals is useful in calculating the volume of molecules. Since molecules do not have defined boundaries, volume calculations involve multidimensional integration. It is difficult to calculate the volume without the use of Monte Carlo methods because of the complexity involved and also because definite boundaries of the molecules are undefined. Volumes of molecules are often defined by a range of electron densities, so Monte Carlo methods use random number generation and a probability distribution function to evaluate the volumes of molecules.

One of the most popular applications of the Monte Carlo algorithms is in the field of finance. Monte Carlo methods aid the analysis of financial instruments, portfolios, and assets. When a financial instrument or asset is being analyzed to label its value, many complex equations, the values of which may be uncertain, are used to reach a final answer. Since Monte Carlo methods work well with highly complex equations, their use becomes vital in the calculation of uncertain values, which then in turn help analyze the final value of the instrument or asset in question. A specific ‘Monte Carlo Option Model’ is used to evaluate future prices of options. Many uncertain values affect the final value of these financial options; Monte Carlo methods use random number generation to lay the various price paths and then calculate a final option value.

Sources

• Monte Carlo simulation tutorials

History

• Draft - Jan 18, 2009