THE GENERATION OF
RANDOM VARIATES

THOMAS G. NEWMAN
Associate Professor of Mathematics
Texas Tech University
and
PATRICK L. ODELL
Professor of Mathematics and Statistics
Texas Tech University

BEING NUMBER TWENTY-NINE OF
GRIFFIN'S STATISTICAL
MONOGRAPHS & COURSES
EDITED BY
ALAN STUART, D.Sc.(Econ.)

In this chapter we discuss briefly the history of the use of sampling techniques as an aid to solving various classes of mathematical and statistical problems. There are certain mathematical problems whose solutions are extremely difficult to obtain by the usual numerical methods, but which are relatively easily solved by sampling techniques. Sampling techniques to estimate distributions of complicated functions of random variables, such as test statistics and estimators, are important in applied statistical methodology. With the advent of operations research and systems analysis, sampling techniques have become important in performing parametric studies on conjectured models of a complicated physical system to determine performance indices over a wide range of environments.

During the early years of this century, sampling experiments were being performed to estimate the frequency distribution of various statistics, but, apart from the well-known “needle problem” [44]  [  1  2 ] used to estimate the value of  Pi, apparently very little was being done toward solving non-probabilistic problems by means of sampling techniques. However, in the 1940’s sampling techniques were applied to non-probabilistic problems to gain answers to very difficult problems primarily arising in nuclear physics. The mathematicians John von Neumann and Stanley Ulam were influential in developing and applying these techniques, which became known as the Monte Carlo method. The term has survived, and common usage now includes sampling techniques used to study probabilistic and systems simulation problems, as well as deterministic problems.

The interested reader is directed to three references where the history of pertinent topics relating to the Monte Carlo method is briefly summarized, namely [100, 95, 75]. Three topics which appear fundamental to numerical simulation using sampling techniques are:

• (1) modelling the problem in probabilistic form;
  
• (2) methods to reduce the variance of the estimate of the solution; and
  
• (3) the generation of the random variables used in the simulation
  

The first topic is highly problem-related, and therefore little in general will be said in our monograph concerning this.Purpose and aim is to investigate thoroughly the third topic, and to describe briefly the basics of the second topic insofar as they affect the third. The problem of how to generate random numbers efficiently and accurately is central to all applications of numerical simulation or of Monte Carlo techniques.

1 Early use of sampling techniques

Observations of games of chance and fitting probability density functions came much earlier than 1900 and, in fact, gave the initial stimulus to the development of probability theory. In 1906 two papers appeared, one by Weldon [1081 and the second by Durbishire 11241, in which dice were used for sampling purposes.

"Student" in two papers in 1908 empirically found the distribution of the standard deviation and the ratio of the mean to the standard deviation of a sample. For his random numbers he used a series of 3,000 pairs of measurements that appeared in the journal Biometrika. These papers are apparently the first use of sampling for estimating distribution functions.

Greenwood and White [411 used '20,000 counts" in their study of estimating a distribution from actual data. Brownlee [811 and Yule [1141 used physical devices to obtain their random numbers; Brownlee tossed coins, while Yule used a circular tray with partitions into which beans were tossed while it was spinning. These simulations were performed in the 1920's.
Bispham, as reported in references [3] and [4] in 1920 and 1923, respectively, was apparently the first to sample from an arbitrary theoretical population.

Bispham used a population of thirty counters, each of which had one of the integers 15 to + 15 on it (zero excluded). A sample was obtained in order, as all thirty counters were drawn from an urn one at a time, without replacement.

Craig [16], in 1928, investigated the distribution of sample moments using punched cards. Randomness was accomplished by shuffling the cards by hand. Sheppard [93], in 1928, generated random numbers using a desk calculator. Other experiments are recorded as using physical means.

It should be noted that random numbers are still being generated using mechanical and electronic machines. The interesting electronic random number generator called "ERNIE" (Electronic Radom Number Generator Indicator Equipment) was described and its properties discussed in a paper by Thomson [101] in 1959 A mechanical system using precisely manufactured rubber balls which roll about at a specified rate of speed was reported by West [109] as a means to a lottery held in the 1950's in Southern Rhodesia. The statistical properties of this apparatus are described in West's paper.

It is important to note that with the arrival of the high-speed digital computer these techniques for generating random numbers became outdated. Von Neumann [105] is said to have divided the techniques for generating random numbers into two classes: (a) physical, and (b) arithmetical. Our monograph is primarily concerned with the arithmetical technique. The physical technique involves installing a physical device as part of a computer to produce the random numbers, and this technique is not considered desirable. Interesting references on this latter topic include Brown [7] and Hamaker [46 - 49].

For a detailed summary of the history of distribution sampling prior to the era of the computer and its relevance to simulation and for some early references, the interested reader is referred again to Teichroew's paper [1001. For more history and a good general bibliography see the book by Tocher [103].

2 The development of Monte Carlo techniques

Dr A. S. Householder has described the Monte Carlo technique as follows: "The Monte Carlo method may briefly be described as the device of studying an artificial stochastic model of a physic. or mathematical process." He goes on to state that the apparent: "novelty" in the technique "lies in the suggestion that where an equation arising in a non-probabilistic context demands a numerical solution not easily obtainable by standard numerical methods, there may exist a stochastic process with distributions or parameters which satisfy the equation, and it may actually be more efficient to construct such a process and compute the statistics than to attempt to use those standard methods."

It is important to note that one must construct a stochastic process, that is to say, one must generate a sequence of random numbers whose stochastic properties are the desirable ones. It is the methods that yield these random numbers that interest us in this monograph.

In applying the Monte Carlo method to his problem, the nuclear physicist has established the method as a modern tool in nuclear physics [961. Many references to work before 1954 are listed at the end of Meyer [75]. These references include several industrial and United States government publications, many of which are not included in our selected list of references (but see [18]).

3 Tests of random numbers

Basic to almost every use of random numbers is the capability to generate variates distributed independently uniformly on the interval [0, 1]. Once these numbers are available, one can use specified mathematical expressions which are functions of the uniform variates to obtain variates from other distributions; these latter variates can even possess specified correlation properties.

A question that arises naturally in generating uniform random numbers by any technique is: how does one become convinced that the numbers generated possess the properties desired and necessary for them to be useful in the context of a pertinent application? One usually desires that the uniform numbers in a set generated by using some technique should be

• (1) equidistributed,that is, evenly distributed over the interval [0, 1] (a precise definition of "equidistributed" can be found in Chapter 2);
• (2) uncorrelated. One can minimize correlation by judiciously selecting various parameters in the mathematical expression used for generating the variates so as to minimize the absolute value of the correlation.

When someone asks, "Are the numbers generated truly random?", he is referring to (2) above. The question in (1) is essentially a check on whether or not one has reproduced numerically what one desires to have been generated.

Many people concern themselves with the obvious inconsistency that the user may claim certain sets of numbers to be random when in truth they were generated using deterministic techniques. Furthermore, the numbers can be exactly duplicated by repeating the procedure. These people prefer terms like 'pseudo-random numbers" to denote these sets, especially those generated by digital computers. Certainly there is little and in most instances nothing random in the process of generating random numbers using high-speed digital computing equipment. The most that can be said about these numbers is that statistically the numbers generate can pass several valid statistical tests such as the frequency test, the serial test, the gap test, and the "poker" test 162].

Several of the more popular and perhaps more useful tests are discussed in Chapter 9 of this monograph.

4 Concluding remarks

The need for easy access to sets of random numbers became evident by 1920. Tippett [102] published the first set of tables in the Tracts for Computers series. Kendall and Smith [64], in 1939, published a table of 100,000 random digits. Tippett drew cards, while Kendall and Smith observed numbers from a spinning disc. Peatman and Shafer [89], in 1942, published 1,600 digits obtained from Selective Service Lists. There were others; the longest was the 1,000,000 random digits produced by a physical device at the Rand Corporation [91].

The tedious business of using tables is slow. Hence, technique for generating pseudo-random numbers especially adaptive to high-speed digital computers have been devised and tested. These techniques are the central theme of this monograph.

There is general agreement among statisticians that sampling techniques to establish a distribution are better than nothing but are less desirable than analytical techniques. The same conclusion is, in general, true when applying sampling techniques to numerical analysis, that is, Monte Carlo techniques are inferior to direct numerical techniques. However, one can obtain reasonable solution to extremely complicated problems using a sampling technique. It is this reason, combined with the existence of a great number of complicated problems, that has established these techniques as truly important tools in modern scientific investigations.

THE ART OF
SIMULATION

K. D. TOCHER
B.Sc., Ph.D., D.Sc.

1963

THE ENGLISH UNIVERSITIES PRESS LTD
102 NEWGATE STREET
LONDON ECI

CHAPTER 1
INTRODUCTION

 The subject-matter of this book stems from three origins and contains matters of interest to three groups of scientific workers.

The first and most respectable origin lies in the theory of mathematical statistics. Before and for some time after the founding of the Royal Statistical Society in 1834, the subject of statistics consisted of the collection and display in numerical and graphical form of facts and figures from the fields of economics, actuarial science and allied descriptive sciences. One of the most useful forms of display was the histogram or frequency chart and the transformation of statistics began when it was realised that the occurrence of such diagrams could be explained by invoking the theory of probability.

The idea of a probability distribution had been established as a useful concept by mathematicians and has been studied by Laplace and Gauss, to name two of the most celebrated mathematicians interested. The idea that frequency charts could be explained as a practical consequence of the laws of probability applied to everyday matters seized the imagination of the pioneers of mathematical statistics. Since a probability distribution is by its nature, in most instances, composed of an infinite number of items, and frequency charts by their nature are composed of a finite number of items, these latter had to be thought of as samples from an underlying theoretical probability distribution. The problem then raised itself at how to describe a probability distribution given only a sample from it. The mathematical difficulties of this seemed immense and such steps as were taken needed experimental verification to give the early workers confidence. Thus was born the sampling experiment. A close approximation to a probability distribution was created, samples were taken, combined and transformed in suitable ways and the resulting frequency chart of sampled values compared with the predictions of theory.

Although mathematical techniques have developed to levels of sophistication that would astonish the early workers, the value of sampling experiments in mathematical statistics still remains. The advent of automatic digital computers to perform the laborious calculaculation necessary has revitalised this as a possible approach to the solution of problems still beyond the reach of analysis.

The second origin lay in the demands of applied mathematicians for methods of solving problems involving partial differential equations. These equations constantly arise in the mathematical formulation of numerous physical processes. Analytical solutions were found for a wide range of formal problems but practical problems involving complex or irregular boundary conditions could not yield to theoretical attack. The corresponding situations had arisen in ordinary differential equations and had been overcome by developing numerical techniques for solving such equations. The nature of the problem for partial differential equations made an attack on these lines far more difficult.

A typical problem was the solution of the so-called diffusion equation, which arises, as its name implies, in the diffusion of gases as well as in the conduction of heat in a medium and many other physical systems. The characteristic of many of these systems was that the actual mechan ism for the movement of the gas (or heat) involved a large number of particles behaving in a partly regular and partly irregular manner. Averaging over the particles enabled the random element to be elimi nated and a deterministic description to be given.

Now the theory of probability had studied formal models closely allied to a system of particles moving in this partly regular, partly random manner and had developed mathematical techniques for deal ing with these problems which were studied under the name of random walks. The mathematical analysis of these problems gave rise to partial differential equations of the same type as the diffusion problem. Thus was born the idea of solving experimentally the diffusion and allied equations by random walks. The idea lay dormant for many years and was resurrected by Von Neumann and Ulam under the stress of the technological demands of the Second World War.

These men conceived of the extension of the principle to seek solu tions to difficult mathematical problems arising from deterministic problems by finding analogous problems in probability leading in theii analysis to formally identical mathematical equations and then solving the probability problems practically by sampling experiments. By this time, the ultimate stochastic nature of the physical phenomena often present in the original problem was often forgotten or completely ignored.

One of the simplest and most powerful applications of this idea. which they christened 'Monte Carlo', was the evaluation of a multi-dimensional integral. Consider the simplest case of evaluating the area of a bounded region. Surround the region with a square, scaling to make its side of unit length. Take a point in the area at random. The probability that this lies in the region of area A is simply A. Take a large number of points at random; the proportion of these lying in the area is an estimate of A.

The whole idea can be generalised to higher dimensions and the result remains true. The great advantage of this method lies in the fact that for higher dimensions, conventional numerical techniques will require an enormous number of points to get any answer at all. The Monte Carlo method can get an answer with any number of points although of course the accuracy falls off as the number decreases.

In fact, the accuracy is proportional to n^1/2, n being the number of points. Conventional methods give an accuracy proportional to n ^1/d where d is the number of dimensions.

The third origin lay in the new science of Operational Research. This set itself the tasks of applying scientific method in everyday life - to military problems during the last war and to problems of industry after it. In common with most sciences, it developed by building models of the systems it studied and using these models to give insight and some times quantitative information about these systems.

The outstanding difference between the subject-matter of conventional science and operational research lay in the greater variability of the phenomena studied. It was vital to bring regularity back into the description of these phenomena - to find a usable description of the variability. This was achieved, as had been done for economics and actuarial science in the previous century, by using probability theory.

The models studied were primarily probabilistic and the theoretical difficulties of these models were immense. A special branch of prob ability theory arose under the title of Queue Theory to deal with some of these problems, but the irregular nature of the boundary conditions and restrictions in the real problems could rarely be incorporated into the models that mathematical methods could solve.

Once again the scientist turned to an experimental technique. Now the problem was phrased in a language description of the real world involving queues, stocks, machines and operating instructions. The subject of simulation, as it was called, took on an identity of its own.

Yet this was nothing new. To a statistician the problem was nothing more than to find the sampling distribution of an intricately and irregularly defined statistic and because of the intricate nature of the definition, to do this by a sampling procedure.

The common element in all these approaches to our subject is probability theory. In these circumstances, it is hardly necessary to stress that an understanding of at least the elements of the theory are essential to an understanding of the principles and practice of sampling.

Any attempt to give a self-contained account of the theory necessary as part of the book would be self-defeating. It could be nothing more than a few formal definitions and readers ignorant of the subject might be tempted to read further with only such a brief introduction. There fore it is assumed that the reader has the necessary grounding in ele mentary probability theory.

Likewise, the elements of the theory of statistics are assumed. The commonest distributions such as Normal, Student's, X² binomial, exponential, are all discussed without a long introduction and the X²-test of goodness of fit is not explained, as this must surely be well known to all scientific workers.

Since the basic process involved is the drawing of samples from different distributions, this receives first study. The problem is reduced to drawing a sample from a uniform distribution (or drawing an integer from a range) 'at random'.

The methods of solving this problem by both machinery and mathematical methods are discussed.

This is followed by an account of the problems in determining a frequency distribution by sampling.

The possibility of using sampling methods as practical methods of acquiring knowledge rests on the possibility of taking really large samples to reduce the effect of the inherent variability. This in turn is possible only because of the existence of automatic digital computers.

It is assumed that one of these powerful devices is available and this raises the problem of describing how to use these machines for sampling. Again, this book is not the place to attempt to give details of the problems of instructing any particular machine to perform the required calculation.

However, the idea of a flow diagram as a means of describing the calculating procedure in a form suitable for transcription into a machine code is explained and forms a powerful means of reducing the volume of description of computing procedures.

Probability distributions are described by means of a set of para meters and the central problem of sampling is to specify the value of such parameters given a sample from the distribution. This is the prob lem of estimation, which receives full treatment. An estimate must be as accurate as possible, and methods of sampling and estimation that increase the accuracy of the estimate without a corresponding increase in the volume of computing are described.

We are then ready to tackle the problems of simulation. First simple queues are dealt with, gradually increasing in difficulty until a general case is dealt with.

More complex systems are then treated and a general technique evolved for dealing with any system.

Finally the question of the design of such large-scale experiments is considered.

S. M. ULAM
Adventures
of a
Mathematician

Charles Scribner's Sons
1976

Prologue

At dusk the plane from Washington to Albuquerque approached the Sandia Mountain range at the foot of which nestles the city of Albuquerque. Some ten minutes before the landing, the lights of the city of Santa Fe became visible in the distance. On the Western horizon loomed the mysteri ous mass of the volcanic Jemez Mountains. It was perhaps the hundredth time I was returning from Washington, New York, or California, where Los Alamos affairs or some other government or academic business took me almost every month.

My thoughts traveled back to my first arrival in New Mexico in January of 1944. I was a young professor at the University of Wisconsin and had been called to participate in a project, the exact nature of which could not be divulged at the time. All I was told was how to get to the Los Alamos area - a train station named Lamy near Santa Fe.

If someone had prophesied some forty-five years ago that I, a young "pure" mathematician from Lwow, Poland, would spend a good part of my adult life in New Mexico - a state whose name and existence I was not even aware of when I lived in Europe - I would have dismissed the idea as inconceivable.

I found myself recollecting my childhood in Poland, my studies, my preoccupation with mathematics even at an early age, and how my interest in physics led me to enlarge my scientific curiosity, which in turn - by a series of accidents and chance - led to a call to join the Los Alamos Project. The nature of the work there I only vaguely guessed when my friend John von Neumann asked me to join him and other physicists at a strange place. "West of the Rio Grande," was all he could tell me when I met him between trains at Union Station in Chicago.

The plane landed at Albuquerque. I took my bags, walked a hundred yards across a parking area, and climbed into the small plane that commuted several times a day be tween Albuquerque and a single runway at an altitude of 7300 feet on the Los Alamos mesa.

Von Neumann, one of the greatest mathematicians of the first half of the twentieth century, was the person who had been responsible for my coming to this country in 1936. We had corresponded since 1934 about some abstruse questions of pure mathematics. It was in this field that I early made a name for myseW von Neumann, working in similar areas, in vited me to visit the newly established Institute for Advanced Studies in Princeton - a place well known to the general public because one of its first professors was Albert Einstein. Von Neumann himself was one of the youngest professors at Princeton. He was already famous for his work in the foundations of mathematics and logic. Years later, he was to become one of the pioneers in the development of electronic computers.

von Neumann and 11-year-old daughter Marina on Santa Fe plaza circa 1949

At one time I had undertaken to write a book on von Neumann's scientific life. In trying to plan it, I thought of how I, along with many others, had been influenced by him; and how this man, and some others I knew, working in the purely abstract realm of mathematics and theoretical physics had changed aspects of the world as we now know it.

Memories of my own work in science, of my studies and early research, of the endless hours spent in caffes in my home town discussing mathematics with fellow mathematicians, of my coming to the United States, lecturing at Princeton and Harvard, became interwoven in an inextricable way with recollections of von Neumann's life and later events.

When I started to organize my thoughts, 1 realized that up to that time - it was about 1966, I think - there existed few descriptions of the unusual climate in which the birth of the atomic age took place. Official histories do not give the real motivations or go into the inner feelings, doubts, con victions, determination, and hopes of the individuals who for over two years lived under unusual conditions. A set of flat pictures, they give at best only the essential facts.

Thinking of all this in the little plane from Albuquerque to Los Alamos, I remembered how Jules Verne and H. C. Wells had influenced me in my childhood in the books I read in Polish translation. Even in my boyish dreams, I did not imagine that some day I would take part in equally fantastic undertakings.

The result of all these reflections was that instead of writing a life of von Neumann, I have undertaken to de scribe my personal history, as well as what I know of a number of other scientists who also became involved in the great technological achievements of this age.

As I have already mentioned, I began as a pure mathe matician. In Los Alamos I met physicists and other "natural" scientists, and consorted mainly, if not exclusively, with theoreticians. 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.

I became involved in the work on the atomic bomb, then in the work on the hydrogen bomb, but most of my life hasbeen spent in more theoretical realms. My friend Otto Frisch, the discoverer of the possibility of chain reactionl from fission, in an article in The Bulletin of the Atomic Scientists describing his first impressions of Los Alamos upon arriving there from embattled Britain, wrote:

"Certainly I have never found such a concentration of interesting people in one place. In the evening I felt I could: walk into any house at random and would find congenial people engaged in music making or in stimulating debate.

...I also met Stan Ulam early on, a brilliant. Polish topologist with a charming French wife. At once he told me that he was a pure mathematician who had sunk so low that his latest paper actually contained numbers with decimal points!"

Little has been written about the lives of the people responsible for so much in science and in the birth of the nuclear age and the space age: von Neumann, Fermi, and numerous other mathematicians and physicists. But here I want to recount also the more abstract and philosophically decisive influences which came from mathematics itself. Names like Stefan Banach, G. D. Birkhoff, and David Hil bert are virtually unknown to the general public, and yet it is these men, along with Einstein, Fermi and a few others equally famous, who were indispensable to what twentieth century science has accomplished. ...

Page 137

Wiener wrote in his autobiography that he had ideas similar to the ones I later proposed as the Monte Carlo method. He says vaguely that he found no response when he talked to someone and so dropped the matter, in the same way that he lost interest in the idea of geometry of vector spaces and function spaces a la Banach. In fact, in one of his books he called these vector spaces (which are associated with Banach's name alone) Banach-Wiener spaces. This nomenclature did not "take" at all.

In the first World 'War mathematicians had done much work in classical mechanics, calculations of trajectories, and external and internal ballistics. This work was resumed at the beginning of the second World War, although it soon turned out not to be the main thrust of the scientific applications. Hydrodynamic and aerodynamic questions became more detailed and urgent, particularly because they were di rectly connected with special war problems. Early in 1940 I took from the library a German textbook on ballistics and studied it, but noticed that there was not much in it of importance to the military technology of the forties. At the beginning of the war electronic computing machines did not exist. There were only the beginnings of the mechanical relay machines constructed at Harvard, at IBM, and one or two other places.  ...

Page 196

Two seminar talks I gave shortly after my return turned out to have good or lucky ideas and led to successful further developments. One was on what was later called the Monte Carlo method, and the other was about some new possible methods of hydrodynamical calculations. Both talks laid the groundwork for very substantial activity in the applications of probability theory and in the mechanics of continua.

The hydrodynamical calculations were for problems in which there was no hope for closed formulae or explicit classical analysis solutions. They could be described as a sort of "brute force" calculations using fictitious "particles" that were really not the fluid elements but abstract points. Instead of considering individual material points of the fluid, it was a matter of using the coefficients of an infinite series into which the continuum was developed as abstract particles for a global description of the fluid. The whole notion is described by some infinite series whose terms are successively less important. Considering only the first few of them, one changed the partial differential equations of several variables (or the integral equations in several vari ables) into ordinary or totally different equations for a finite number of abstract "particles." Some years later, the work of Francis Harlow in Los Alamos deepened, enlarged, and multiplied the scope of this approach to the calculations of motions of fluids or of compressible gases. These are now widely used. The possibilities of such methods have not yet been exhausted; they could play a great role in the calcula tions of air movements, weather prediction, astrophysical problems, problems of plasma physics, and others.

The second talk was on probabilistic calculations for a class of physical problems. The idea for what was later called the Monte Carlo method occurred to me when I was playing solitaire during my illness. I noticed that it may be much more practical to get an idea of the probability of the successful outcome of a solitaire game (like Ganfield or some other where the skill of the player is not important) by laying down the cards, or experimenting with the process and merely noticing what proportion comes out successfully, rather than to try to compute all the combinatorial possibilities which are an exponentially increasing number so great that, except in very elementary cases, there is no way to estimate it. This is intellectually surprising, and if not exactly humiliating, it gives one a feeling of modesty about the limits of rational or traditional thinking. In a sufficiently complicated problem, actual sampling is better than an examination of all the chains of possibilities.

It occurred to me then that this could be equally true of all processes involving branching of events, as in the production and further multiplication of neutrons in some kind of material containing uranium or other fissile elements. At each stage of the process, there are many possibilities deter mining the fate of the neutron. It can scatter at one angle, change its velocity, be absorbed, or produce more neutrons by a fission of the target nucleus, and so on. The elementary probabilities for each of these possibilities are individually known, to some extent, from the knowledge of the cross sections. But the problem is to know what a succession and branching of perhaps hundreds of thousands or millions will do. One can write differential equations or integral differen tial equations for the "expected values," but to solve them or even to get an approximative idea of the properties of the. solution, is an entirely different matter.

The idea was to try out thousands of such possibilities and, at each stage, to select by chance, by means of a random number" with suitable probability, the fate or kind of event, to follow it in a line, so to speak, instead of consider ing all branches. After examining the possible histories of only a few thousand, one will have a good sample and an approximate answer to the problem. All one needed was to have the means of producing such sample histories. It so happened that computing machines were coming into existence, and here was something suitable for machine calculation.

Computing machines came about through the confluence of scientific and technological developments. On one side was the work in mathematical logic, in the foundations of mathematics, in the detailed study of formal systems, in which von Neumann played such an important role; on the other was the rapid progress of technological discoveries in electronics which made it possible to construct electronic computers. They, in turn, provided such a quantitative in crease in the speed of operation so much greater than the mechanical relay machines that it produced a qualitative change and vastly improved and enlarged the use of the tool. The results are now known to everyone: computers in troduced a new age in heuristic research, in communication, and in making the space age possible.

The number of applications in exact science, in the natu ral sciences, and in everyday life is so great that one can talk of "the age of computers and automata" as having begun.

At that time the computers were merely in statu nascendi. As a joke I proposed to make Monte Carlo calculations by hiring several hundred Chinese from Taiwan, gather them on a boat, have each one sit with an abacus, or even just pencil and paper, and make them produce the random numbers by some actual physical process like throwing dice. Then someone would collect the results, and total the statistics into single answers.

Von Neumann played a leading role in the launching of electronic computers. His unique combination of gifts, his interests, and traits of character suited him for that role. I am thinking of his ability, and inclination to go through all the tedious details of program planning, of executing the minu tiae of putting very large problems in a form treatable by a computer. 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. By suitable flow diagramming and programming, an enormous variety of problems became calculable on one machine with all connections fixed. Before his invention one had to pull out wires and reconnect plug boards each time a problem was changed.

The Monte Carlo method came into concrete form with its attendant rudiments of a theory after I proposed the possibilities of such probabilistic schemes to Johnny in 1946 during one of our conversations. It was an especially long discussion in a government car while we were driving from Los Alamos to Lamy.

We talked throughout the trip, and I remember to this day what I said at various turns in the road or near certain rocks. (I mention this because it illustrates what may be multiple storing in the memory in the brain, just as one often remembers the place on the page where certain passages have been read, whether it is on the left- or right-hand page, up or down, and so on.) After this conversation we developed together the mathematics of the method. It seems to me that the name Monte Carlo contributed very much to the popularization of this procedure. It was named Monte Carlo because of the element of chance, the production of random numbers with which to play the suitable games.

Johnny saw at once its great scope even though in the first hour of our discussion he evinced a certain skepticism. But when I became more persuasive, quoting statistical es timates of how many computations were needed to obtain rough results with this or that probability, he agreed, eventually becoming quite inventive in finding marvelous technical tricks to facilitate or speed up these techniques.

The one thing about Monte Carlo is that it never gives an exact answer; rather its conclusions indicate that the answer is so and so, within such and such an error, with such and such probability - that is, with probability differing from one by such and such a small amount. In other words, it provides an estimate of the value of the numbers sought in a - given problem.  I gave a lot of "propaganda" talks for this method all over the United States. Interest and improvements in the theory came rapidly. Here is an easy example of this procedure which I often selected: One may choose a computation of a volume of a region defined by a number of equations or inequalities in spaces of a high number of dimensions. In stead of the classical method of approximating everything by a network of points or "cells," which would involve billions of individual elements, one may merely select a few thousand points at random and obtain by sampling an idea of the value one seeks.

The first questions concerned the production of the random or pseudo-random numbers. Tricks were quickly devised to produce them internally in the machine itself with out relying on any outside physical mechanism. (Clicks from a radioactive source or from cosmic rays would have been very good but too slow.)  Beyond the literal or "true" imitation of a physical process on electronic computers, a whole technique began to develop on how to study mathematical equations which on their face seem to have nothing to do with probability processes, diffusion of particles, or chain processes. The question was how to change such operator equations or differential equations into a form that would allow the possibility of a probabilistic interpretation. This is one of the main theses behind the Monte Carlo method, and its possibilities are not yet exhausted. I felt that in a way one could invert a statement by Laplace. He asserts that the theory of probability is nothing but calculus applied to com mon sense. Monte Carlo is common sense applied to mathematical formulations of physical laws and processes.

Much more generally, electronic computers were to change the face of technology. We discussed the many possibilities endlessly. But not even von Neumann could fore see their full economic or technological impact. These aspects of their development were still in their infancy so far as industrial applications were concerned when he died in 1957. Little did we know in 1946 that computing would become a fifty-billion-dollar industry annually by 1970.

Almost immediately after the war Johnny and I also began to discuss the possibilities of using computers heuristically to try to obtain insights into questions of pure mathematics. By producing examples and by observing the properties of special mathematical objects one could hope to obtain clues as to the behavior of general statements which have been tested on examples. I remember proposing in 1946 a calculation of a very great number of primitive roots of integers so that by observing the distributions one obtained enough statistical material on their appearance and on the combinatorial behavior to perhaps get some ideas of how to state and prove some possible general regularities. I do not think that this particular program has been advanced much until now. (In mathematical exploratory work on computers my collaborators were especially Myron Stein and Robert Schrandt.) In the following years in a number of pub lished papers, I have suggested - and in some cases solved - a variety of problems in pure mathematics by such experimenting or even merely "observing." The Gedanken Experimente, or Thought Experiments, of Einstein are pos sible and often useful in the purest part of mathematics. One of the papers outlining a field of exploration in "non-linear problems" was written in collaboration with Paul Stein. By now, a whole literature exists in this field.

Ulam 'demonstrating' MANIAC in 1955

Quite early, in fact only some months after the electronic computer called MANIAC became available in Los Alamos, I tried with a number of associates (Paul Stein, Mark Wells, James Kister, and William Walden) to code the machine to play chess. It was not so terribly difficult to code it to play correctly according to the rules. The real problem is that, even today, nobody knows how to put in its memory experiences of previous games and a general recognition of the quality of patterns and positions. ...

Page 232

I had seen very many wonderful and eminent scientists and artists in my life before, but the sight of this man who was a billionaire and wielded enormous power really awed me. But to go back to Johnny's fascination with the military, I believe it was due more generally to his admiration for people who had power. This is not uncommon with those whose life is spent in contemplation. At any rate, it was clear that he admired people who could influence events. In addition, being softhearted, I think he had a hidden admiration for people organizations that could be tough and ruthless. He appreciated or even envied those who at meetings could act or present their views in a way to influence not only others' thoughts, but concrete decision- making. He himself was not a very strong or active debater in committee meetings, yielding to those who insisted more forcefully. On the whole he preferred to avoid controversy.

These were the days of defense research contracts. Even mathematicians frequently were recipients. Johnny and I commented on how in some of their proposals scientists sometimes described how useful their intended research was for the national interest, whereas in reality they were motivated by bonafide scientific curiosity and an urge to write a few papers. Sometimes the utilitarian goal was mainly a pretext. This reminded us of the story of the Jew who wanted to enter a synagogue on Yom Kippur. In order to sit in a pew he had to pay for his seat, so he tried to sneak in by telling the guard he only wanted to tell Mr. Blum inside that his grandfather was very ill. But the guard refused, telling him: "Ganev, Sie wollen beten" ["You thief! You really want to pray"]. This, we liked to think, was a nice abstract illustration of the point.

Gamow, who lived in Washington, was a consultant at the Naval Research Laboratory. One of my early so-called business trips to Washington involved a consultation with him. He asked me to talk about Monte Carlo and we discussed modeling land:battle situations. He was interested in and did a lot of work on tank battles. He used Monte Carlo, for example, to simulate landscapes, which he dubbed Stan scapes. ...

Los Alamos

and the development of the atomic bomb

Robert W. Seidel

Otowi Crossing Press, 1995

 -22-
From calculators to computers

Computational models and methods are a vita part of the scientific and technological revolution.

Computers were people running desk calculators when Los Alamos began. By the end of the war, Los Alamos scientists were using the first electronic computer John von Neumann was the primary agent of this change. Automatic computing led to the Laboratory's strong program in computer science and technology, as well as making it possible to calculate the behavior of nuclear explosives.

Early calculations relating to the diffusion of neutrons in a critical assembly of uranium were made in 1942 by Eldred Nelson and Stanley Frankel, both of whom were members of Robert Serber's group in the Radiation Laboratory at the University of California-Berkeley. When they came to Los Alamos in the spring of 1943, they ordered the same sorts of machines that they had used in California, Marchant and Friden desk calculators, to make the calculations required in the design of nuclear weapons.

To perform some of these repetitive calculations, a group of scientists' wives were recruited to form a central computing pool. These 'computers" included Mary Frankel, Josephine Elliott, Beatrice Langer, Mici Teller, Jean Bacher, and Betty Inglis. They became group T-5 under New York University mathematician Donald (Moll) Flanders when he arrived in the late summer of 1943.

The mechanical calculators tended to break down under heavy use by physicists and had to be shipped back to the manufacturer until Richard Feynman of Princeton University and Nicholas Metropolis of the University of Chicago learned to repair them. Although Theoretical (T) Division leader Hans Bethe at first objected that in-house repair was a waste of time, he relented when the number of working calculators diminished.

Dana Mitchell, whom Oppenheimer had recruited from Columbia University to oversee procurement for Los Alamos, recognized that the calculators were not adequate for the heavy computational chores and suggested the use of IBM punched-card machines. Mitchell had seen them used successfully by Wallace Eckert at Columbia to calculate the orbits of planets, arid he persuaded Frankel and Nelson to order a complement of them.

John von Neumann developed Neddermeyer's one-dimensional theory of implosion with Teller. When von Neumann had difficulty with the pure high-density incompressible phase of implosion, he suggested a test implosion to determine physical quantities that could not be calculated analytically. He subsequently formulated another model for computation, and Teller setup a group in T Division devoted to the theory of implosion. The new IBM punched-card machines were devoted to calculations to simulate implosion. Metropolis and Feynman organized a race between them and the hand-computing group. "We set up a room with girls in it," recalled Feynman. "Each one had a Marchant. But one was the multiplier, and another was the adder, and this one cubed and all she did was cube this number and send it to the next one? For one day, the hand computers kept up; "The only difference was that the IBM machines didn't get tired and could work three shifts. But the girls got tired after a while."

Feynman worked out a technique to run several calculations in parallel on the punched-card machines, which reduced the time required. "The problems consisted of a bunch of cards that had to go through a cycle. First add, then multiply  - and so it went through the cycle of machines in this room, slowly, as it went around and around. So we figured a way to put a different colored set of cards through a cycle too, but out of phase. We'd do two or three problems at a time." Three months were required for the first calculation; Feynman's technique reduced the time to two or three weeks.

The first implosion calculation showed that the fissile material would be strongly compressed and that a high yield would result from assembling a relatively small amount of fissile material if a spherically symmetrical implosion was produced. Although about a dozen other calculations of implosion were done to refine it, the Trinity device test on July 16, 1945, would show that the basic calculation was correct.

Von Neumann brought news of computer developments else where, such as Bell Laboratory's relay computer and Howard Aiken's Mark I electromechanical calculator at Harvard. The Mark I was even used to run an unclassified version of one of the Los Alamos problems. Although t took several times as long as the Los Alamos machines, the Mark I computed to far greater precision.

Von Neumann saw that problems like those encountered at Los Alamos could be solved by electronic computers similar to the Electronic Numerical Integrator And Computer (ENIAC) being developed at the University of Pennsylvania. In 1944 and 1945, he formulated ways to translate mathematical procedures into a language of instructions for such a machine. And he recommended to Edward Teller, who had conceived of a thermonuclear, or "super," bomb that one of the computational problems associated with its design be used to test the ENIAC, since that would be much more demanding than the ballistic trajectories the Army had designed it to calculate.

Metropolis and Frankel traveled to the University of Pennsylvania early in 1945 to discuss the problem with the developers of ENIAC, John W Mauchly and J. Presper Eckert. (The calculations were run in December of 1945 and January of 1946 after the conclusion of the war. A half-million punched cards of data were transferred from Los Alamos to Philadelphia to run it, and mathematician Stan Ulam, whom von Neumann had recruited to come to Los Alamos from Princeton, recalled "the spirit of exploration and of belief in the possibility of getting trustworthy answers in the future. This was partly because of the existence of computing machines which could perform much more detailed analysis and modeling of physical problems."

The wartime work of the Laboratory created a need for computing that stimulated von Neumann, Metropolis. Ulam, and others to reduce previously insoluble physical problems to a form in which they could be calculated automatically. The use of these techniques not only made possible the design of nuclear and thermonuclear weapons, but also the solution ofmany other scientific problems, ranging from aerodynamics to molecular biology.