Polish Contributions to Computing
Stanislaw Marcin Ulam [pron. sta-NEE-suav MAR-chin OO-lahm] was born on April 13, 1909, in Lwów, Poland (Lemberg, Austro-Hungary), now Lviv, Ukraine, and died on May 13, 1984, in Santa Fe, New Mexico, USA. He obtained his master and doctorate degrees (1933) from the Polytechnic Institute in Lwów, and did post-doctoral studies in Vienna, Zürich and Cambridge (England), in 1934. He came to the U.S. in 1935, to the Institute for Advanced Studies, in Princeton, upon the invitation from John von Neumann. Then, he spent four years (1936-40) at Harvard, first at Harvard Society of Fellows and then as lecturer in mathematics. Next he moved to the University of Wisconsin, at Madison (1940-43), and in 1943 received an invitation to join the Manhattan Project at Los Alamos Scientific Laboratory, where he stayed until 1967. Between 1965-77, he was involved with the Mathematics Department at the University of Colorado, Boulder, where he eventually became a Chairman. Among his multiple visiting positions, he spent Winter trimesters between 1974-84 at the University of Florida, in Gainesville.

Major Contribution: Invention of the Monte Carlo method in 1947 [1-3] (with Nicholas Metropolis and John von Neumann). It is, of course, widely known that Stan Ulam’s greatest accomplishment of any kind was his contribution to the development of an H-bomb, by the so-called Teller-Ulam configuration for the bomb ignition [4]. His other contributions include work in mathematics (set theory, topology, group theory, dynamical systems, number theory), physics and astronomy, biology, and computing [5].

Basic Questions
What is a Monte Carlo method? The Monte Carlo method is a statistical trial and error technique for solving complex problems that are otherwise intractable using analytical deterministic techniques. Its essence is in generating random samples of data of known distribution to collect statistically valid results that would provide insight into the phenomenon or process being investigated. In other words, the method is using statistics to find approximate solutions to problems where exact mathematical treatment is too complex or time consuming, therefore, it's more general name: statistical testing. The idea for the method occurred to Stan Ulam during a game of solitaire. As he says in his biography [6]: “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.”

There are many books (for example [7]) and materials on the Internet explaining the idea of the Monte Carlo method, some of them with simulators, such as the one on this webpage under the Resources button. Most of them, including ours, show the simplest application of this method by calculating the value of an integral. One particularly interesting illustration that goes back to the first known application of this technique, predating the Ulam’s formulation by around two centuries, is the Needle Problem used by the French mathematician Count of Buffon to determine the approximate value of the number pi [8]. Count Buffon noticed that by casting a needle on a ruled grid, after many trials one can obtain the value of pi with good accuracy, by calculating a simple formula: a doubled ratio of needle’s total drops to the number of hits on the grid. An applet demonstrating this experiment has been written by Michael J. Hurben [9].

Where, then, did the name Monte Carlo method come from? C.C. Hurd [17] states that he “found no documentation concerning the first use of the name Monte Carlo.” Metropolis, however, states the following: “I suggested an obvious name for the statistical method – a suggestion not unrelated to the fact that Stan had an uncle who would borrow money from relatives because he just had to go to Monte Carlo [as a center of gambling].” [21]

Significance
The power of Monte Carlo method stems from the fact that it is suitable for solving problems otherwise intractable. In preface to the Proceedings of the first official symposium on the Monte Carlo method, held in Los Angeles, at the end of June 1949 [10], the editor, Alston S. Householder, wrote: “The Monte Carlo method may briefly be described as the device of studying an artificial stochastic model of a physical or mathematical process. The device is certainly not new. Moreover, the theory of stochastic processes has been subject of study for quite some time, and the novelty in the Monte Carlo method does not lie here. The novelty lies rather in the suggestion that where an equation arising in 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.” Since then, due to the use of electronic computers, the Monte Carlo method has been applied in hundreds of problems for simulating the behavior of various physical and mathematical systems, including such diverse areas as nuclear physics, VLSI design, ecology, econometrics and many others.

Beyond the Monte Carlo method and an H-Bomb, as Gian-Carlo Rota writes in his essay on Ulam [19]: “As a mathematician, his name is most likely to survive for his two problem books, which remain bedside books for young mathematicians eager to make their mark by solving at least one of them.” The latest edition of the problems appeared in 2004 [23].

Findings
Stan Ulam has been a celebrity figure of scientific research and plenty of material is available on his life and work, including books [11-14], a special issue of Los Alamos Science [15], and his personal archive stored by the American Philosophical Society [16]. So it is hard, for a student project, to find some unusually rare result of his work and present it on the website. However, we were able to track down his very first publication on the Monte Carlo method, predating his 1949 papers by two years, an initially classified report written with John von Neumann [1], originally printed in eight copies only. Two instances of this report were found: one is the electronic version of this report published in [14], and the other is an appendix to an article on early Monte Carlo computations [17], the latter republished here courtesy of the IEEE Computer Society Press. As reported in [22], also in 1947 an early abstract of this work has been published [24]. We also found that the first Monte Carlo application by different authors is likely to be [25].

The second historical contribution of this website is to make available Ulam’s introductory chapter from the Scottish Book [18], not available electronically before (courtesy of Birkhäuser). This short reading reveals Ulam’s personality, fully confirmed later by his close friend, Gian-Carlo Rota [19], how it was shaped in meetings and discussions with prominent figures of the Polish school of mathematics: Banach, Kac, Kuratowski, Mazur, Sierpinski, Steinhaus and others, in an incredible atmosphere of a coffee shop in the 1930’s. It also shows an unusual gratitude Stan Ulam had towards his countrymen who indirectly helped him launch his world career, which he acknowledged by single-handedly putting together the collection of problems recorded at these meetings, translating them and publishing, first privately on a mimeograph (1957), and then officially as a Los Alamos Report LA-6832 (1967), and finally, as a regular hard-cover book [20].

References [hide]

[1] S. Ulam, R. D. Richtmyer, J. von Neumann, Statistical Methods in Neutron Diffusion,Report LAMS-551, Los Alamos Scientific Laboratory, Los Alamos, New Mexico, April 9, 1947
[2] N. Metropolis, S. Ulam, The Monte Carlo Method, Journal of the American Statistical Association, Vol. 44, pp. 335-341, 1949
[3] S. Ulam, On the Monte Carlo Method, Proc. Second Symposium on Large-Scale Digital Calculating Machinery, Cambridge, Mass., Sept. 13-16, 1949, Harvard University Press, 1951, pp. 207-212
[4] G.A. Goncharov, American and Soviet H-bomb Development Programmes: Historical Background, Physics – Uspekhi, Vol. 39, No. 10, pp. 1033-1044, 1996
[5] Publications of Stanislaw M. Ulam, pp. 313-317, in [15]
[6] S. Ulam, Adventures of a Mathematician, Charles Scribners & Son, New York, 1976
[7] N. Madras (Ed.), Lectures on Monte Carlo Methods, The Fields Institute Research in Mathematical Sciences, Communications Vol. 26, American Mathematical Society, 2000
[8] G. Buffon (George-Louis Leclerc, Comte de Buffon), Essai d'arithmétique morale, Histoire naturelle, générale er particulière, Supplément, Vol. 4, pp. 46-123, 1777 http://gallica.bnf.fr/ark:/12148/bpt6k97517m/f51.table
[9] M.J. Hurben, Buffon Needle, http://www.angelfire.com/wa/hurben/buff.html
[10] A.S. Householder et al. (Eds.), Monte Carlo Method, National Bureau of Standards, Applied Mathematics Series, Vol. 12, US Government Printing office, Washington, DC, 1951
[11] W.A. Beyer, J. Mycielski, G.-C. Rota (Eds.), Stanislaw Ulam: Sets, Numbers, and Universes, MIT Press, Cambridge, Mass., 1974
[12] M.C. Reynolds, G.-C. Rota, Science, Computers, and People: From the Tree of Mathematics – Stanislaw M. Ulam, Birkhäser, Boston, 1986
[13] N.G. Cooper, R. Eckhardt, N. Shera (Eds.), From Cardinals to Chaos: Reflections on the Life and Legacy of Stanislaw Ulam - A Los Alamos Profile, Cambridge University Press, New York, 1989
[14] S.M.. Ulam, Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and his Los Alamos Collaborators. University of California Press, Berkeley, 1990 http://ark.cdlib.org/ark:/13030/ft9g50091s/
[15] Special Issue: Stanislaw Ulam, Los Alamos Science, No. 15, Report LA-UR-87-3600, Los Alamos Scientific Laboratory, Los Alamos, New Mexico, 1987 http://www.fas.org/sgp/othergov/doe/lanl/pubs/number15.htm
[16] Stanislaw M. Ulam Papers (1916-1984), American Philosophical Society, Philadelphia, Penn., http://www.amphilsoc.org/library/mole/u/ulam.htm
[17] C.C. Hurd, A Note on Early Monte Carlo Computations and Scientific Meetings, IEEE Annals of the History of Computing, Vol. 7, No. 2, pp. 141-155, 1985
[18] S. Ulam, An Anecdotal History of the Scottish Book, pp. 3-16 in [20]
[19] G.-C. Rota, The Lost Café, pp. 23-32 in [15]
[20] R.D. Mauldin (Ed.), The Scottish Book: Mathematics from the Scottish Café, Birkhäuser, Boston, 1981
[21] N. Metropolis, The Beginning of the Monte Carlo Method, pp. 125-130, in [15]
[22] S.I. Gass, A.A. Assad, Model World: Tales from the Time Line—The Definition of OR and the Origins of Monte Carlo Simulation, Interfaces, Vol. 35, No. 5, pp. 429-435, September-October 2005
[23] S. Ulam, A Collection of Mathematical Problems, Wiley Interscience, New York, 1960 (latest edition published by Dover Publications in 2004)
[24] S.M. Ulam, J. von Neumann, On the Combination of Stochastic and Deterministic Processes. Preliminary Report (Abstract 53-11-403), Bull. Amer. Math. Soc., Vol. 53, p. 1120, 1947
[25] M.L. Goldberger, The Interaction of High-Energy Neutrons and Heavy Nuclei, Physics Review, Vol. 74, pp. 1269-1277, 1948

Copyright 2006. All rights reserved. W3C XHTML Compliant Valid XHTML 1.0 Transitional