« PreviousContinue »
which is what we wanted to show.
We have also shown that, with probability 1, a random homeomorphism has a derivative of O almost everywhere, that is, everywhere except for a subset of [0,1] with Lebesgue measure 0. Consequently, with probability 1, a random homeomorphism is not smooth. Therefore this approach will not yield answers to questions concerning the transition from smooth to turbulent, or chaotic, behavior. As often happened with Stan's problems, the original question, which was motivated by physics, would eventually become a purely mathematical problem.
By the way, our original studies on an Apple computer illustrate the pitfalls of working with numerical results. From looking at the graphs we guessed that the set of fixed points for these homeomorphisms is a Cantor set. When we were unable to prove this conjecture, Tony Warnock conducted more highly resolved computer studies on a Cray. The results suggested not that the fixed points are a Cantor set but rather that a high proportion of the random homeomorphisms have an odd number of fixed points (see the accompanying table). This time we guessed that, with probability 1, a random homeomorphism has a finite odd number of fixed points. Indeed we were able to prove this; however, the proof is too complicated to outline here.
A few closing comments on this problem. First, the procedure for generating a random homeomorphism can also be viewed as a procedure for generating a distribution function at random. Thus, we have a probability measure on the space of probability measures! This viewpoint was thought of and developed earlier by Dubins and Freedman. Second, Stan and I did consider the generation of random homeomorphisms on other spaces. For example, the algorithm for generating homeomorphisms of the circle reads almost exactly like that for generating homeomorphisms of the interval. (However, in that case we don't know whether there is a positive probability of generating homeomorphisms with no periodic points. This is an interesting possibility.) Third, it is possible to bootstrap oneself up from generating homeomorphisms of the interval to generating homeomorphisms of the square, the cube, and so on. These possibilities are described in Graf, Williams, and Mauldin 1986. Finally Stan had some wild ideas about "crossing" random homeomorphisms with something like Brownian motion to produce flows at random.
That wildness was the joy of being with Stan Ulam. His boundless imagination opened up one's mind to the endless possibilities of creating. It was my good fortune to have known Stan for some ten years as a deep personal friend, a most stimulating collaborator, and an endless source of inspiration. ■
FIXED POINTS OF RANDOM
Listed here are computer-generated sets of data on the number of fixed points possessed by each of (a) 5000 and (b) 10,000 of the random homeomorphisms (h's) defined in the text. Note the predominance of homeomorphisms with odd numbers of fixed points. That observation led us to conjecture, and to prove, that, with probability 1, any such random homeomorphism has a finite odd number of fixed points.
Number k of
Number of h's with k Fixed Points (a) (b)
The first five works are general; the remainder are those cited in reference to specific topics.
A. I. Khinchin. 1949. Mathematical Foundations of Statistical Mechanics. New York: Dover Publications, Inc.
Mark Kac. 1959. Probability and Related Topics in Physical Sciences. New York: Interscience Publishers, Inc.
Mark Kac and Stanislaw M. Ulam. 1968. Mathematics and Logic: Retrospect and Prospects. New York: Frederick A. Praeger, Inc. Also in Volume 1 of Britannica Perspectives. Chicago: Encyclopedia Britannica, Inc.
R. Daniel Mauldin, editor. 1981. The Scottish Book: Mathematics from the Scottish Café. Boston: Birkhäuser Boston.
R. D. Mauldin and S. M. Ulam. 1987. Problems and games in mathematics. Advances in Applied Mathematics 8:281-344.
Richard P. Feynman. 1951. The concept of probability in quantum mechanics. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, edited by Jerzy Neyman. Berkeley and Los Angeles: University of California Press.
David Blackwell and R. Daniel Mauldin. 1985. Ulam's redistribution of energy problem. Letters in Mathematical Physics 60: 149. (This entire issue is devoted to Stan Ulam.)
S. Ulam. 1980. On the operations of pair production, transmutations, and generalized random walk. Advances in Applied Mathematics 1:7-21.
R. D. Mauldin and S. C. Williams. 1986. Random recursive constructions. Transactions of the American Mathematical Society 295: 325-346.
S. Graf, R. Daniel Mauldin, and S. C. Williams. 1986. Random homeomorphisms. Advances in Mathematics 60: 239.
R. Daniel Mauldin received his Ph.D. in mathematics from the University of Texas in 1969. In 1977, after eight years at the University of Florida, he joined the faculty at North Texas State University, where he is currently the Decker Science Fellow. He is a frequent visitor to the Laboratory. Some of his current research interests involve deterministic and random recursions and the asymptotic geometrical and measure-theoretic properties of objects defined by these processes. He is a member of the American Mathematical Society and an editor of its Proceedings.
AN ULAMIAN POTPOURRI
by Paul R. Stein
first met Stan Ulam during the war, when I was at Los Alamos as a GI, working in Hans Bethe's Theoretical Division. Our friendship was social rather than professional, for at that time I had little to contribute. I returned to Los Alamos in 1950 and was immediately caught up in the weapons program, spending much of my time in the East helping to run problems on computers in Washington, Philadelphia, and Aberdeen. What time remained was spent in Santa Monica consulting with the Rand Corporation and courting my future wife. Fortunately, in 1953 I managed to get married, and that, of course, settled me down. The next six years witnessed my gradual conversion, under Stan's tutelage, from physicist to mathematician.
Our collaboration started in a low key. At first it was limited to discussions-rather one-sided, as I recall. I listened as Stan aired his prejudices concerning mathematical biology as it then was (circa 1955): "It is all foolishness, don't you think?" I was in no position to counter these remarks, and soon he had me more or less believing them. One argument he advanced more than once (and which I no longer believe) was about the human eye. Stan could not imagine that something so complex could have evolved by random processes in the time available, even granting the effect of natural selection. Neither of us, however, could think of a practicable calculation to settle the question, so we turned to simpler matters.
The first mathematical problem we undertook together, with the aid of an IBM 704 computer, concerned the evolution of large populations under the assumption of random
mating, to which we added the effect of mutation. (This description of the problem may tempt the reader to interpret what follows in terms of Mendelian genetics. That topic, however, had already been treated mathematically in great detail, and our interest lay rather in investigating mathematical and computational approaches to other examples of evolutionary processes.) Stan made it very clear that he wanted nothing to do with the customary approach via differential equations (à la Sewall Wright); instead, everything was to be based on point-wise iteration. I heartily agreed.
We characterized the "type" of an individual in the population by a pair of integer indices (i,j), with i,j = 1,2,..., N. The number of males of type (i,j) was assumed to equal the number of females of that type; in fact, males and females were not distinguished, so, despite the use of the word "mating," the problem involved no sex (and none of the mathematical complications that go with it). The fraction of individuals of type (i,j) in the nth generation of the population was denoted by x) = x). Random mating then changes the population fractions from generation to generation according to the equation
prqs (n) (n)
The summation in Eq. 1 was carried out under the restrictions of a "mating rule," namely, that progeny of type (i,j) result from mating between individuals of type (p,q) and (r, s) only if
min(q,s) ≤ j ≤ max(q,s).
(Here min(u, v) and max(u, v) mean, respectively, the smaller and the larger of the two integers u and v.) In other words, the indices of an offspring fall within the ranges defined by those of its parents.
For technical reasons that I will not pursue here, we imposed simplifying conditions on the coefficients as follows:
min(p, r) ≤ i ≤ max(p,r)
by requiring that
Unfortunately, the detailed results of these experiments have disappeared over the thirty or so years since the computations were done. I seem to recall, however, that all the systems we looked at "converged"; in fact, after a sufficiently large number of generations, only a single type remained (survival of the fittest?). I also remember that the convergence was not usually monotone.
Although nothing of a detailed theoretical nature was discovered about the systems including mutation, the simpler systems without mutation (Eq. 1) could be analyzed exactly by elementary methods, even when individuals were distinguished by many indices rather than only two. In brief, each system, as defined by a set of initial population fractions, converged to a state determined entirely by that set. (Details of the analysis are given in Menzel, Stein, and Ulam 1959 and in Stein and Ulam 1964.) Our next joint project was undertaken with more mathematical aims in view, although Stan never lost his strong interest in biology. (A good summary of Stan's contributions to that field can be found in a 1985 article by Beyer, Sellers, and Waterman. The reader should take note of the 1967 paper by Schrandt and Ulam. The study of growth patterns contained therein bears a close resemblance to some recent work on cellular automata.) After extensive discussion, we decided to study the behavior under iteration of a restricted class of quadratic transformations, or maps, of the plane. The idea was mainly Stan's, but I managed to contribute some practical suggestions.
At this point is seems appropriate to explain what it meant to collaborate with Stan. At some stage in his mathematical career, he apparently lost his taste for detailed mathematical work. Of course, his mind was always brimmming with ideas, most