Back-to-Basic Weekend Reading: Monte-Carlo Methods
I always enjoy looking for solutions to difficult challenges in non-obvious places. That is probably why I like using probabilistic techniques for problems that appear to be hard, or impossible to solve deterministically. The probabilistic approach may not result in the perfect result, but it may get you very close, and much faster than deterministic techniques (which may even be computationally impossible).
Some of the earliest approaches using probabilities in physics experiments resulted in the Monte Carlo methods. Their essential idea is using randomness to solve problems that might be deterministic in principle. These are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results.
The Monte Carlo methods can be traced back to Stanislaw Ulam, John van Neuman, and Nick Metropolis at the Los Alamos Scientific Laboratory in the late 40s. The Monte Carlo methods were crucial in the simulations of the Manhattan Project, given the limited computational power available in those days
The paper I will be reading this weekend is the original paper from 1949, by Metropolis and Ulam. For fun, I’ve also decided to add a second paper by Herbert Anderson, who was a member of the Manhattan project. Anderson’s paper describes the use of Monte Carlo methods, and the computers in the Manhattan project.
“The Monte Carlo Method”, Nicholas Metropolis, S. Ulam, Journal of the American Statistical Association, Vol. 44, No. 247. (Sep., 1949), pp. 335-341.
“Metropolis, Monte Carlo and the MANIAC”, Anderson, Herbert L., Los Alamos Science, (1986) 14: 96–108.