Equation of State Calculations by Fast Computing Machines
Can't check every possibility? Wander among them at random — cleverly — and a plain average becomes the right answer.
When a problem has too many possibilities to ever check them all, you can still get the right answer — by wandering through them at random, but cleverly.
The big idea
Many questions in science come down to an average over a staggering number of arrangements — for instance, the average pressure of a gas, taken over every possible arrangement of its molecules. There are far too many to add up, and almost all of them barely matter.
In 1953 a team at Los Alamos got a computer to explore the arrangements that do matter, by taking a guided random walk. From wherever you are, try a small random change. If it leads somewhere more likely, go there. If it leads somewhere less likely, go anyway — but only with a chance that shrinks the worse it is. Wander this way and you visit each arrangement just as often as it deserves, so a simple average of what you see along the way is the answer.
How it came about
It was born in the weapons labs and their first electronic computers. At Los Alamos, Nicholas Metropolis, the husband-and-wife physicists Marshall and Arianna Rosenbluth, and Edward and Augusta Teller put the idea to work on the MANIAC, one of the earliest stored-program machines. The name “Monte Carlo,” after the casino, had been coined a few years earlier by Stanislaw Ulam and John von Neumann for the broader notion of solving problems by chance.
Who did what on the 1953 paper is still disputed. Marshall Rosenbluth said late in life that he and Arianna did the real work — she wrote the program — while the algorithm carries Metropolis's name, and that Edward Teller supplied an early, crucial idea. Arianna Rosenbluth, who actually coded it, is the one history has remembered least.
Why it mattered
It turned “too many possibilities to count” from a dead end into a routine calculation, and helped make computer simulation a third way of doing science, beside theory and experiment. The same trick now sits inside the statistics behind clinical trials and election forecasts, the simulations behind weather and new materials, and a great deal of modern machine learning.
A way to picture it
Imagine mapping the busiest spots in a huge city, in the dark, on foot. You can't visit every street. So you stroll: step somewhere nearby; if it feels busier, keep going; if quieter, sometimes turn back and sometimes not. Each minute, mark where you stand. Walk long enough and your tally of marks traces the city's crowds — though you never saw the whole map. That is exactly how the algorithm samples the “crowded,” most-likely arrangements of a physical system.
Where it sits
The idea rests on Markov chains — sequences where the next step depends only on where you are now, studied by Andrey Markov in 1913 — and on the probability foundations laid by Kolmogorov in 1933. It grew out of the Monte Carlo method of Ulam and von Neumann in the 1940s, was generalized by Hastings in 1970, and now underlies the Bayesian statistics and large-scale simulation woven through modern science. (See the Library's document on Markov.)