Skip to content

Monte Carlo Methods

Abstract

In 1946, mathematician Stanisław Ulam lay convalescing from a severe illness, playing solitaire, and asked himself: what are the odds this layout can be won? The combinatorics were hopeless, but he realized he could just deal a hundred hands and count. Shared with John von Neumann, the idea became the Monte Carlo method: solve intractable mathematics by random sampling. Named by Nicholas Metropolis after the casino where Ulam’s uncle gambled away borrowed money, first run on ENIAC in 1948 for nuclear weapons design, it became one of the defining algorithms of the computing age, behind reactor design, financial risk models, weather ensembles, computer graphics, and the sampling engines of modern AI.

Solitaire and the Bomb

Stanisław Ulam (Polish-born veteran of the Manhattan Project at Los Alamos) was recovering from a 1946 illness (a bout of encephalitis) when the solitaire question struck him. Exhaustive calculation of a Canfield solitaire’s success probability was combinatorially impossible; playing a large number of games and counting successes was easy, and answers the practical question just as well. He immediately saw what mattered: the same trick applied to the problem Los Alamos actually had, neutron diffusion, tracking how neutrons scatter, are absorbed, and multiply through fissile material, a chain of probabilistic events far too tangled for analytic solution.

Ulam described the idea to John von Neumann, who seized on it and worked out how a computer could execute it: simulate thousands of individual neutron histories, each decision (collision? absorption? fission?) made by drawing random numbers, and read the physics off the statistics. Nicholas Metropolis supplied the name (Monte Carlo) after the Monaco casino where Ulam’s uncle would borrow money from relatives to gamble.

In the spring of 1948, von Neumann, Metropolis, and colleagues ran the first fully automated Monte Carlo calculations (simulating a fission weapon core) on ENIAC. It was among the first serious scientific computations ever performed by an electronic computer, and it set the pattern for the hydrogen bomb work that followed: where the mathematics of the Teller–Ulam problem could not be solved, it was sampled.

Dead End: Von Neumann’s Random Numbers

A sampling method is only as good as its randomness, and the first source was a famous misstep. Von Neumann proposed the middle-square method: square a number, take its middle digits as the next “random” value, repeat.

Why It Died

Middle-square sequences collapse; they fall into short cycles or decay to zero, and the quality depends erratically on the seed. Von Neumann knew it was a hack; his own verdict became one of computing’s most quoted lines: “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.” He used it anyway because it was fast and its failures were at least visible, hardware noise generators of the day could not be debugged or replayed. The dead end was productive: it founded the study of pseudorandom number generation, from linear congruential generators through the Mersenne Twister to today’s cryptographic PRNGs, a whole discipline devoted to sinning well.

From Neutrons to Everything

The method’s generality was recognized almost immediately (a 1949 symposium already gathered applications), and it spread with cheap computing:

  • Physics and engineering, reactor shielding, particle transport at CERN, semiconductor device simulation.
  • The Metropolis algorithm (1953), developed by Metropolis, Arianna and Marshall Rosenbluth, and Augusta and Edward Teller on the Los Alamos MANIAC, sampled from complex probability distributions via random walks, founding Markov chain Monte Carlo (MCMC). Arianna Rosenbluth wrote the implementation, one of the earliest substantial scientific programs authored by a woman (see Women in Computing). Generalized by Hastings (1970) and turbo-charged by Gibbs sampling, MCMC later made Bayesian statistics practical, a quiet revolution across science.
  • Finance, derivative pricing and risk (Value-at-Risk) are Monte Carlo over simulated market paths; so are pension and insurance models.
  • Graphics, path tracing, the physically accurate rendering behind modern film CGI and GPU ray tracing, is Monte Carlo integration of light transport.
  • Weather and climate, ensemble forecasting runs the model many times with perturbed inputs; the forecast’s “70% chance of rain” is a Monte Carlo statistic.
  • AI and games: Monte Carlo tree search powered the Go breakthroughs of AlphaGo; sampling methods pervade probabilistic machine learning.

The Philosophical Trade

Monte Carlo embodies a bargain characteristic of the computing age: exchange certainty for tractability. An analytic answer is exact but often unobtainable; a sampled answer is approximate, but its error shrinks predictably (as 1/√N) with more computation, so accuracy becomes something you buy with cycles. Ulam’s solitaire insight was that this bargain is almost always worth taking, and cheap computation has been proving him right for eighty years.

📚 Sources