Introduction to Monte Carlo Methods

Share on FacebookTweet about this on TwitterShare on Google+Share on RedditShare on StumbleUpon

Generally Monte Carlo methods refer to:

Any method which solves a problem by generating suitable random numbers and observing that fraction of the numbers obeying some property or properties. [1]

In other words, a Monte Carlo method is any algorithm which obtain numerical results (an approximation) with random sampling. This is simple, straight forward, and is a very common practice. There are many real world examples, such as surveying a population, calculating the risk of an investment, physics simulations, approximating the value of an integral, and more!

A bit of history

The method was “invented” in the 1940’s by Stanislaw Ulam, while he was working on the Manhattan project. The method was named the Monte Carlo method because Stanislaw’s uncle had recently visited a Monte Carlo casino, to gamble and the method was useful for determining probabilistic outcomes.

Use Cases

Monte Carlo methods are often useful in applications where it is easier to generate an approximate answer via many iterations as opposed to solving the problem directly. Many problems are unsolvable and the best approach we have is using the Monte Carlo method (or a similar method) for approximation.

A common example where Monte Carlo algorithms are used  are in physics, where equations relating to fluids, thermodynamics, or nuclear fission have inputs which are “loosely” bound. Rather than attempting (if it is even possible) to bound the equation(s) we iterate with many different starting values and find and approximate answer after a period time.

One other area where Monte Carlo methods are used in an interesting are in business analysis [2]. They can be used to simulate the probably out come of game theory scenarios, risk assessments, etc. much more accurately than a human can and much more accurately than many other methods.

There are many more applications of the Monte Carlo method, the reason for this is they can in some cases be the only solution to a problem. When systems become so complex the use of Monte Carlo methods can often be a solution, by simply testing or iterating over a system ten thousand, a hundred thousand, a million, or more times you can begin to see a pattern and this pattern you can use. One famous (as well as one of the first) examples of a Monte Carlo method being used is in 1947 – 1950 by John von Neumann and his use of it in developing the Hydrogen Bomb.

Simple Example of a Monte Carlo Method

Pi_30K
via Wikipedia

Say for example we wished to find the approximate value of a double integral, which are reasonably tedious/difficult to solve, but with Monte Carlo methods are straight forward to approximate.

Take the following integral and solution using WolramAlpha:

Screen Shot 2014-04-30 at 5.17.13 PM

If we wished to solve this directly we would have to first take the integral in the dx and then in the dy, plug in the values and we will receive ~22.333. Similarly, if we take the following:

Screen Shot 2014-04-30 at 5.18.50 PM

We would again have to take the integral of the dy, then the dx, plugin all the values accordingly and receive 99/2 or ~49.5.

I really do not want to do this by hand, so rather than doing that, I wrote up the following:

(or view via Github)

My output being: (22.343587154427766, 49.379322128101656)

Even 10,000 iterations in over two separate functions took less than a second to run. Simple, straight forward and fairly accurate. The error in this case for the first function was 0.0004 or 0.04%, not bad for an approximation! The second function  .0024  or 0.24%, again not bad.

Unfortunately, these methods are just that approximations and they do require a large number of iterations to reduce the influence of outliers, but over all they are usually some of the most straight forward algorithms to program and can be very useful for analysis of complex systems.

It is also important to note that Monte Carlo methods (for the most part) can be parallelized and ran on supercomputers. This is why many complex physics models/calculations require supercomputers to run.

Related Articles

Share on FacebookTweet about this on TwitterShare on Google+Share on RedditShare on StumbleUpon