35
$\begingroup$

Is there a simulation method that is not Monte Carlo? All simulation methods involve substituting random numbers into the function to find a range of values for the function. So are all simulation methods in essence Monte Carlo methods?

$\endgroup$
  • 2
    $\begingroup$ I think "Stan" was just Ulam's first name, not the surname of anybody else. $\endgroup$ – Nick Cox Dec 6 '14 at 16:46
  • $\begingroup$ Stan is the abbreviation of Stanislas, indeed. Which is why Andrew Gelman chose STAN for his new simulation language. $\endgroup$ – Xi'an Dec 6 '14 at 17:16
  • $\begingroup$ Given a small, perhaps borderline-trivial, combinitorial problem, would an exhaustive search still be "Monte Carlo"? $\endgroup$ – Nick T Dec 6 '14 at 17:38
  • 3
    $\begingroup$ What I remember from my randomized algorithms lecture is that Monte Carlo methods have stochastic outcomes with known run times, in contrast to Las Vegas methods which have stochastic runtimes but correct outcomes. No reference for this except a five year old, handwritten script in my drawer. Edit: The wikipedia pages on monte carlo and las vegas seem to agree with this. $\endgroup$ – bayerj Dec 6 '14 at 19:34
  • $\begingroup$ An exhaustive search would probably be a brute force calculation. Monte Carlo methods pull from a sample space. This sample is usually a small subset of the universe of outcomes, which makes the statistical analysis tractable. $\endgroup$ – Alex Reynolds Dec 6 '14 at 19:42
41
$\begingroup$

There are simulations that are not Monte Carlo. Basically, all Monte Carlo methods use the (weak) law of large numbers: The mean converges to its expectation.

Then there are Quasi Monte Carlo methods. These are simulated with a compromise of random numbers and equally spaced grids to yield faster convergece.

Simulations that are not Monte Carlo are e.g. used in computational fluid dynamics. It is easy to model fluid dynamics on a "micro scale" of single portions of the fluid. These portions have an initial speed, pressure and size and are affected by forces from the neighbouring portions or by solid bodies. Simulations compute the whole behaviour of the fluid by calculating all the portions and their interaction. Doing this efficiently makes this a science. No random numbers are needed there.

In meteorology or climate research, things are done similarly. But now, the initial values are not exactly known: You only have the meteorological data at some points where they have been measured. A lot of data has to be guessed.

As these complicated problems are often not continuous in their input data, you run the simulations with different guesses. The final result will be chosen among the most frequent outcomes. This is actually how some weather forecasts are simulated in principle.

$\endgroup$
  • 5
    $\begingroup$ A slight correction: monte-carlo simulations can use non-random calculations. It is valid to call a simulation "monte-carlo" if it varies initial conditions, and then applies non-random calculations from there. A lot of CFD situations call for monte-carlo because the boundary-conditions are statistically defined. $\endgroup$ – Cort Ammon - Reinstate Monica Dec 6 '14 at 21:31
14
$\begingroup$

Monte Carlo method was the first approach to use computer simulation for statistical problems. It was developed by the John von Neumann, Stanisław Ulam, & Nicholas Metropolis team from Los Alamos laboratories that was working on the Manhattan project during the World War II. It was first described in 1949 by Metropolis & Ulam, and it was the first time the name appeared in print. It was possible because the scientists that discovered it were also able to use one of the first computers, that they were working on. In their work they used Monte Carlo methods for simulation physical problems, and the idea was that you could simulate a complicated problem with sampling some number of examples of this process. There are multiple interesting articles on history of Monte Carlo e.g. by Metropolis himself or some more recent, e.g. by Robert & Casella.

So "Monte Carlo" was a name of the first method described for a purpose of computer simulation to solve statistical problems. Then the name became a general name for a whole family of simulation methods and is commonly used in this fashion.

There are simulation methods considered non-Monte Carlo, however while Monte Carlo was the first use of computer simulation it is common that "computer simulation" and "Monte Carlo" are used interchangeably.

There are different definition of what "simulation" is, i.e.

Merriam-Webster dictionary:

3 a : the imitative representation of the functioning of one system or process by means of the functioning of another b : examination of a problem often not subject to direct experimentation by means of a simulating device

Cambridge dictionary:

to do or make something which behaves or looks like something real but which is not real

Wikipedia:

imitation of the operation of a real-world process or system over time

What simulation needs to work is an ability to imitate some system or process. This does not need any randomness involved (as with Monte Carlo), however if all the possibilities are tried, then the procedure is rather an exhaustive search or generally and optimization problem. If the random element is involved and a computer is used to run a simulation of some model, then this simulation resembles the spirit of the initial Monte Carlo method (e.g. Metropolis & Ulam, 1949). The random element as a crucial part of simulation is mentioned, for example, by Ross (2006, Simulation. Elsevier). However, the answer to the question depends heavily on the definition of simulation you assume. For example, if you assume that deterministic algorithms that use optimization or exhaustive search, are in fact simulations, then we need to consider a wide variety of algorithms to be simulations and this makes the definition of simulation per se very blurry.

Literally every statistical procedure employs some model or approximation of the reality, that is "tried" and assessed. This is consistent with dictionary definitions of simulation. We do not however consider all the statistics to be simulation based. The question and the discussion seems to emerge from the lack of the precise definition of "simulation". Monte Carlo seems to be archetypical (and first) example of simulation, however if we consider very general definition of simulation then many non-Monte Carlo methods fall into the definition. So there are non-Monte Carlo simulations, but all the clearly simulation-based methods resemble the spirit of Monte Carlo, relate to it in some way, or were inspired by it. That is the reason why "Monte Carlo" is often used as a synonym for "simulation".

$\endgroup$
  • 3
    $\begingroup$ I think "Stan" was just Ulam's first name, not the surname of anybody else. $\endgroup$ – Nick Cox Dec 6 '14 at 16:46
  • 1
    $\begingroup$ Stan is the abbreviation of Stanislas, indeed. Which is why Andrew Gelman chose STAN for his new simulation language. $\endgroup$ – Xi'an Dec 6 '14 at 17:16
  • $\begingroup$ Given a small, perhaps borderline-trivial, combinitorial problem, would an exhaustive search still be "Monte Carlo"? $\endgroup$ – Nick T Dec 6 '14 at 17:38
  • 6
    $\begingroup$ I don't get it: how does this answer the question? $\endgroup$ – o0'. Dec 7 '14 at 21:00
  • 1
    $\begingroup$ @Xi'an it's Stanisław written with "Ł" (read as "woo" in English). $\endgroup$ – Tim Feb 18 '17 at 15:35
13
$\begingroup$

All simulation methods involve substituting random numbers into the function to find a range of values for the function.

I have never heard of that definition of simulation. For example, Wikipedia’s articles on simulation and computer simulations mention terms like random and stochastic only briefly.

A simple example of a simulation that does not involve any randomness and thus clearly is not a Monte Carlo simulation would be the following:

I want to simulate the behaviour of a simple pendulum and make some simplifying assumptions (massless cord, punctual mass, no friction, no external forces like the Coriolis force). Then I obtain a mathematical pendulum and can write down differential equations describing its motion. I can then use some solver for differential equations like a Runge–Kutta method to simulate its trajectory for given initial conditions. (I can also theoretically argue that I do not need to regard further initial conditions.)

This way I obtain a rather good simulation of a real pendulum without ever using a random number. Therefore, this is not a Monte–Carlo simulation.

In another example, consider the logistic map, which is a simple population model without any randomness.

$\endgroup$
7
$\begingroup$

No. The simulation of a particle under a force can be done using Runge-Kutta or other deterministic algorithm, which is not Monte Carlo.

Monte Carlo is used to compute integrals (you can call it a simulation, but in the end it just computes a numerical approximation of an estimator). Again, you could use a deterministic method to do that (e.g. trapezoidal rule).

Broadly speaking, you can separate algorithms to compute integrals in deterministic and non-deterministic. Monte Carlo is a non-deterministic method. Quasi-Monte Carlo is another. Trapezoidal rule is a deterministic algorithm.

$\endgroup$
4
$\begingroup$

Let me take a stab at a simplified explanation. A "what-if" model is a (deterministic) simulation. Say you have a complex system, like a widget processing plant. You want to be able to estimate some performance parameter, say cost. You build a mathematical model of the plant and then select various assumptions for specific factors in the model, like how fast widgets move through different operations, or what percentages flow in various directions, or how many widgets you will process. The model is a simulation of the plant and each set of assumptions gives you an estimate of that performance parameter.

Now introduce uncertainty. You don't know what the demand for widgets will be next month but you need to estimate cost. So instead of saying demand will be 1,000 widgets, you estimate a probability distribution for demand. Then you randomly sample demand values from that distribution and use those for your assumption. While you're at it, you can use probability distributions for other assumptions, also. You use the model over and over, plugging in assumptions sampled from the various probability distributions. The result will be a distribution of cost estimates. That's the Monte Carlo aspect.

Monte Carlo is a "feature" or "engine" that is layered on top of a simulation model. Instead of simulating with a single set of assumptions for a single estimate, it performs a collection of simulations using randomly selected assumptions.

$\endgroup$
2
$\begingroup$

In game theory, especially, approaches that use randomness in the simulations are called monte carlo techniques. It is typically used as part of Monte Carlo Tree Search (MCTS) in modern programs.

(The original question did not make a distinction between "monte carlo algorithm" and "monte carlo method", which may explain disagreement over some of the answers here.)

For instance in the game of go (and all other games I am aware of that use MCTS), the simulations are called playouts. Random playouts use the barest set of rules. Light playouts are either a synonym for random playouts or filter out a few easily detected bad moves. Heavy playouts use more heuristics to filter out a lot more moves. (By the way the playout always goes to the end of the game, so each playout takes roughly the same amount of time.) But all are referred to as being "monte carlo" simulations.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.