Hitting the Jackpot: The Birth of the Monte Carlo Method
November 1, 2023
A game of solitaire, a case of insomnia, a chance meeting at a train station, and a penchant for gambling all contributed to the creation of one of the most influential computing tools in the world: the Monte Carlo method. First conceived in 1946 by Stanislaw Ulam at Los Alamos† and subsequently developed by John von Neumann, Robert Richtmyer, and Nick Metropolis, the method was first used to calculate neutron diffusion paths for the hydrogen bomb. Since then, its use has exploded into an uncountable number of applications in science and technology, artificial intelligence, finance, transport, health, and manufacturing, along with virtually every profession that must measure risks.
The method is particularly useful for modeling situations with a large number of random variables, for instance, in applications ranging from predicting stock market volatility to modeling the post-detonation nuclear forensics of an electromagnetic pulse (EMP) attack. Modern Monte Carlo codes also underpin the criticality calculations in the article Calculating Criticality. The original calculations are historically significant as the first programs written in the modern stored-program paradigm to be run on an electronic computer, now the cornerstone of modern computing.
The virtuoso
Like many European intellectuals of the time, the Polish mathematician Stanislaw Ulam emigrated to the US in 1939 to escape racial persecution from the Nazis. Ulam resented being labeled an intellectual, however. His friend Gian-Carlo Rota said, “He would not even agree to being classified as a mathematician. He referred to the published volume of his scientific papers as ‘a slim collection of poems’.”
Perhaps, as Rota suggests in his reminiscences of Ulam, “virtuoso” would be the best descriptor.
As the war intensified, Ulam began to look beyond his teaching position at the University of Wisconsin for ways he could contribute to the war effort. His first thought was to turn to his friend and fellow Jewish emigre John von Neumann, who he suspected was involved in secret military research. Von Neumann’s uncharacteristic silence on scientific matters spoke volumes to Ulam. His suspicions proved to be correct, and before long Ulam joined the Manhattan Project.
At Los Alamos, Ulam discovered a natural talent for applying his esoteric mathematical skills to solve problems in physics. The divide he was attempting to bridge was real—he would joke that “the mathematicians know a great deal about very little and the physicists very little about a great deal.” After watching Enrico Fermi and Richard Feynman at the blackboard, he was inspired to emulate their approach by solving real-world problems with the minimum amount of math. Ulam went on to make major contributions to the design of the hydrogen bomb, solving the problem of how to initiate fusion, although he clashed with its other main designer, Edward Teller.
“I am thinking about something much more important than bombs; I am thinking about computers.” — John von Neumann, 1945.
Misfortune in the cards
After the war, Ulam had found himself in a pedestrian teaching job in California when he abruptly began to experience discombobulating headaches. He said that he “remembered suddenly Plato’s description of Socrates after he was given the hemlock in prison; the jailor made him walk and told him that when the feeling of numbness starting in the legs reached his head he would die.”
Within 24 hours he was rushed to face the surgeon’s knife for emergency brain surgery. He lost the ability to speak during the crisis and became desperately concerned about the state of his mental faculties—his whole career rested on the delicate machinery of his grey matter. Nevertheless, during his convalescence he made one of the most consequential intellectual breakthroughs of his life.
A solitaire-y epiphany
During the following months as Ulam began to recover, his fears of permanent effects from the illness slowly lessened. He was further encouraged when a telegram arrived offering him a position back at Los Alamos, signed by physicists Robert Richtmyer and Nick Metropolis. Ulam recalls in his memoir Adventures of a Mathematician, “this offer to return to Los Alamos to work among physicists and live once again in the exhilarating climate of New Mexico was a great relief for me.”
Having returned to Los Alamos, he was nevertheless still experiencing bouts of fatigue. While playing solitaire to while away the time during rest, Ulam asked himself a straightforward question: what are the chances that a hand laid out with 52 cards will come out successfully? It is a deceptively challenging problem—there are around 8 × 1067 ways to sort a deck of cards (a number approaching the estimated number of atoms in the observable universe). He wondered if instead of applying pure combinatorial calculations, which would be monstrously difficult, he could simply lay out the cards one hundred times and count the number of successful plays. Implicit was the assumption that each play started with randomized conditions.
“This was already possible to envisage with the beginning of the new era of fast computers,” he said, “and I immediately thought of problems of neutron diffusion and other questions of mathematical physics.” Now that Ulam had returned to Los Alamos, this meant questions posed by the development of the hydrogen bomb.
ENIAC: The dawning of digital computing
The “new era of fast computers” that Ulam was thinking of was led at the time by the ENIAC (Electronic Numerical Integrator And Computer), the world’s first programmable, electronic digital computer, completed in 1945 at the University of Pennsylvania. It was built during World War II to calculate ballistic trajectories at a rate 10 times faster than the differential analyzers then in use. (The differential analyzer was a mechanical analog computer that used a wheel-and-disc mechanism, built in 1927 by Manhattan Project administrator Vannevar Bush and worked on by his young student Claude Shannon in 1936; aspects of ENIAC’s design were modelled on the differential analyzer).
Although construction of ENIAC was not finished until after the war, its computational speed—more than 1,000 times faster than its closest electromechanical competitor—ensured it would be in demand for years. It was initially programmed by rewiring cables and setting switches on an enormous set of plugboard panels (Fig. 3), but in 1948 it was converted to be a stored-program machine. ENIAC ran in the new stored-program configuration for the remainder of its service life. By the end of its
operation in 1956, it comprised a sprawling network of 18,000 vacuum tubes, 7,200 crystal diodes, 1,500 relays, 70,000 resistors, 10,000 capacitors, and approximately five million hand-soldered joints.
Von Neumann and the stored program paradigm
The link between ENIAC and Los Alamos was John von Neumann, a brilliant mathematician and polymath—now recognized as one of the greatest minds of the twentieth century. Von Neumann had made pivotal contributions to the Manhattan Project, particularly to the implosion dynamics of the plutonium weapon, and was trying to conceive of a better way to perform the exponentially complex equations associated with rapid nuclear processes. Even before the war ended, he wrote to a colleague, “I am thinking about something much more important than bombs; I am thinking about computers.”
Von Neumann’s involvement with ENIAC seems to have arisen by pure chance. In 1944, while at a railway station he started chatting with a stranger who turned out to be an engineer who worked on ENIAC. Prior to this chance meeting, von Neumann had not heard of the project. After the war, von Neumann became involved with the development of the hydrogen bomb while also working as a consultant for the Ballistic Research Laboratory—sponsor of ENIAC—and saw the potential in Ulam’s statistical approach, which they had discussed during “an especially long conversation in a government car” while driving from Los Alamos to Lamy in 1946.
Ulam and von Neumann were professional colleagues but also good friends and eventually became neighbors on Bathtub Row in Los Alamos. Mathematician Gian-Carlo Rota said that “Stan was probably the only close friend von Neumann ever had. A similar background and a common culture shock brought them together. They would spend hours on end gossiping and giggling, swapping Jewish jokes, and drifting in and out of mathematical talk.”
Rolling the dice with Monte Carlo
In 1947, von Neumann wrote a letter to Robert Richtmyer (Los Alamos Theoretical division leader) that contained the first formulation of a Monte Carlo computation for an electronic computer, a concept that was years ahead of its time. Shortly after, fellow colleague on the project Nick Metropolis coined the name for the method from its probabilistic nature. The name also referred to Ulam’s Polish uncle who would borrow money from relatives because he “just had to go to Monte Carlo” (the Las Vegas of Europe). The code was finalized later that year with input from Richtmyer, and the first calculations were run on ENIAC in April–May, 1948 for the computer's first trial after it was upgraded to a stored-program machine.
Coincidentally, von Neumann had first met his wife Klára in Monte Carlo in 1936. Klára contributed significantly to the coding efforts of the Monte Carlo method, accompanying Metropolis to Maryland where they worked on ENIAC for 32 days without a break to modify the machine. “The method is clearly a 100% success,” von Neumann wrote at the time.
Von Neumann’s historical calculations were the first-ever programs written in the modern stored-program paradigm to be run on an electronic computer. Using his method, it was no longer necessary to physically unplug and reconnect wires every time a problem was changed. Ulam explained that “it was his feeling for and knowledge of the details of mathematical logic systems and the theoretical structure of formal systems that enabled him to conceive of flexible programming. This was
his great achievement.” This work had its immediate precursors in the work of Alan Turing and Konrad Zuse, among others, as well as collaborative work von Neumann had participated in with the design of EDVAC (Electronic Discrete Variable Automatic Computer), the successor to ENIAC based on the stored-program design that would become operational a few years later.
Laboratory historian Nic Lewis says that von Neumann’s work on EDVAC laid pivotal groundwork for development of the stored program paradigm: “Von Neumann’s major contribution, it seems, was his remarkable ability to translate the EDVAC collaboration’s work around a specific architecture into a generalizable, logical representation that others could emulate, without having to copy the EDVAC design.”
Ulam later remarked, “It is still an unending source of surprise for me to see how a few scribbles on a blackboard or on a sheet of paper could change the course of human affairs.” The calculations remained classified until the late 1950s, however, the method itself was not. Ulam was quick to promote the idea on a national lecture tour before it had even been published, helping it spread beyond the Laboratory. It found rapid success in the fields of physics, physical chemistry, and operations research.
FERMIAC and the insomniac
Remarkably, the ingenious physicist Enrico Fermi independently invented the fundamentals of Ulam’s random sampling method back in the 1930s while studying neutron moderation in Italy, but he had chosen to keep this part of his work secret and unpublished. Indeed, his colleagues often wondered how Fermi arrived at his answers so much faster than they did. Fermi was an insomniac who was always calculating equations with his pocket slide rule. This habit of Fermi’s prompted Robert Oppenheimer to quip, “He was simply unable to let things be foggy. Since they always are, this kept him pretty active.”
During a short hiatus in the ENIAC operation as it was moved between locations, Fermi dreamt up an analogue device to continue studies into neutron transport. At the time, this device was known as the Monte Carlo Trolley, but it was renamed the FERMIAC when Los Alamos scientists rediscovered it after Fermi’s death in the 1960s. Built as a brass and acrylic device by colleague L.D.P. “Perc” King in 1947, it employed a series of rotating drums that moved a stylus over a sheet of paper (Fig. 9). The action of the drums was dictated by a Monte Carlo process with pseudorandom numbers, giving a two-dimensional drawing of the resultant neutron genealogies. It was used by Fermi for approximately two years and remains a curiosity from this era of computing.
Statistical sampling methods had been around for a long time. For instance, Buffon's needle problem dates from the eighteenth century and uses a similar concept to the Monte Carlo method. Nevertheless, it was Ulam’s idea to combine statistical sampling methods with the emerging computing technology of the time that ensured the success of the method—a simple concept that can solve complex problems.
The seeds of the future
The enormous impact of the Monte Carlo method can be thought of itself as a genealogical network of influences, all leading back to Ulam’s epiphany and his friendship with von Neumann. Along with the Monte Carlo method, many other great advances in applied mathematics arose from their conversations, such as cellular automata, stimulated growth patterns, and other pioneering computer-based mathematical experiments.
As Ulam says in his memoir, “Little did we know in 1946 that computing would become a fifty-billion-dollar industry annually by 1970.” Von Neumann died in 1957 and did not see the true blossoming of his life’s work. “Too bad he did not live to see how computers have revolutionized everything and what influence they will have on science in general and even on pure mathematics,” Ulam said. “His role in their development was tremendous.” Ulam, a man of great understatement, added, “If I may say so… I too played a modest role in showing how to use computers!”
Acknowledgments
Many thanks to Nic Lewis, Jill Gibson, Avneet Sood, Joel Kulesza, Linda Deck, and Omar Juveland for their assistance in writing this article.
Further reading:
1. “From Cardinals to Chaos: Reflections on the Life and Legacy of Stanislaw Ulam,” Los Alamos Science, 15, 1987.
2. S.M. Ulam, “Adventures of a Mathematician,” Scribner’s, New York, 1976.
3. N. Lewis, W. Spivey, “Computing on the mesa,” National Security Science, Winter 2020.
4. A. Sood, R.A. Forster, B.J. Archer, R.C. Little “Neutronics Calculation Advances at Los Alamos: Manhattan Project to Monte Carlo,” Nucl. Technol., 2021, 207:sup1, S100-S133.
5. K. Kleiman, “Proving Ground: The Untold Story of the Six Women Who Programmed the World’s First Modern Computer,” Grand Central Publishing, New York, 2022.