Call (+1) 650-212-1212

Blog

How Monte Carlo Simulation Fights the Curse of Dimensionality

Sean Salleh 04 Oct 2013 Risk and uncertainty

The Curse of the Mummy? Already tackled with Lon Chaney in 1944. The Curse of Monkey Island? Thousands of PC gamers have beaten you to it. The Curse of Fatal Death? Doctor Who has it under control. But the Curse of Dimensionality…? Sounds like a case for superhero Monte Carlo simulation. In helping to overcome this threat to modelers all over the world, Monte Carlo simulation makes it possible to analyze complex situations in ways that would defeat deterministic methods.

One of the simplest Monte Carlo simulations to estimate Pi/4 Image source: Wikimedia.org

 

So What Is the Curse of Dimensionality?

The effort to resolve problems expressed in many dimensions (many variables) tends to grow exponentially with the number of dimensions when using a purely mathematical approach. This is the Curse of Dimensionality. Take an example of a model with ten variables to be mathematically evaluated for 20 values of each variable. The total number of evaluation points is 20 10 or about 10 13. A Monte Carlo simulation may give the same accuracy with only 10 6 points, which is ten million times less work (!).

Laying Down the Law (of Large Numbers)

Superheroes stand for law and order. The law of large numbers states that as the number of experiments or simulations increases, the actual results will converge on the theoretical or expected results. Thankfully, a Monte Carlo simulation can often make do with a few hundred thousand simulations for the law of large numbers to apply. This is an important aspect in combating the curse of dimensionality, because it means that such methods are often relatively fast. As a computing solution, speed depends on the processing power of the hardware) and application design; Analytica is designed for blazing speed for Monte Carlo simulation and more.

Lone Rangers Must Also Look to the Horizon

Monte Carlo simulation still needs a certain minimum number of runs. As an exaggerated counter-example, just running such a simulation three times would not be realistic. You can see this in simple coin-flipping experiments, where the coin falls as either heads (H) or tails (T). In the long run, a standard coin will tend to fall both ways (50 – 50) in an equal proportion. That’s what probability theory predicts, and that’s what the law of large numbers says too. However, just three runs will automatically lead to distorted results as the most balanced result can only be 66.666... – 33.333... (HTH or TTH, for example). Making unjustified assumptions by failing to look beyond a subset of results sometimes adversely affects expert elicitation, when independent experts are brought in to help in situations where data are only available in small quantities.

Superheroes Can Also Make Errors

Like the coin-flipping example above, the result of a Monte Carlo simulation may be inaccurate. However, it turns out that the degree of error is roughly proportional to 1/√N (reciprocal of the square root of N), where N is the number of simulation runs. While absolute errors can still vary in size, it can be forced downwards as N increases – down towards zero if N increases without limit.

If you’d like to know how Analytica, the modeling software from Lumina, can help you apply Monte Carlo simulation with ease, power and speed, then try a thirty day free evaluation of Analytica to see what it can do for you.

» Back

Sean Salleh

Sean Salleh is a data scientist with experience in guiding marketing strategy from building marketing mix models, forecasting models, scenario planning models, and algorithms. He is passionate about consumer technologies and resource management. He has master's degrees in Operations Research from University of California Irvine and Mathematics from Northeastern University.

Leave a Comment