`
`Random Digits
`
`By John von Neumann
`
`Summary written by George E. Forsythe
`
` 13. Various Techniques Used in Connection With
`
`In manual computing methods today random
`numbers are probably being satisfactorily obtained
`from tables. When random numbers are to be
`used in fast machines, numbers will usually be
`needed faster. More significant is the fact that,
`because longer sequences will be used, one is
`likely to have more elaborate requirements about
`what constitutes a satisfactory sequence of random
`numbers.
`. There are two classes of questions
`connected with hi h-speed computation about
`which I should li e to make some remarks:
`(A) How can one produce a sequence of random
`decimal
`digits—~a
`se uence where
`each digit
`appears with probabiity one—tenth and where
`consecutive ones are independent of each other in
`all combinations?
`(B) How can one produce
`random real numbers according to an assigned
`probability distribution law?
`On problem (A), I shall add very little to what
`has been said earlier in this symposium. Two
`quantitatively different methods for the produc—
`tion of
`random digits have been discussed:
`physical processes and arithmetical processes.
`The main characteristics of physical
`recesses
`have been pointed out by Dr. Brown. There are
`nuclear accidents,
`for example, which are the
`ideal of randomness, and up to a certain accuracy
`you can count them. One difficulty is that one is
`never quite sure what is the probability of occur-
`rence of the nuclear accident. This difficulty has
`been overcome by taking larger counts than one
`in testing for either even or odd. To cite a human
`example,
`for simplicity,
`in tossing a coin it is
`probably easier to make two consecutive tosses
`independent than to toss heads with probability
`exactly onerhalf,
`If independence of successive
`tosses is assumed, we can reconstruct a 50—50
`chance out of even a badly biased coin by tossing
`twice.
`If we get heads—heads or tails—tails, we
`reject the tosses and try again.
`If we get heads-
`tails (or tails-heads), we accept the result as heads
`(or
`tails). The resulting process is rigorously
`unbiased, although the amended process is at
`most 25 percent as efiicient as ordinary coin—
`tossing.
`We see then that we could build a physical
`instrument to feed random digits directly into a
`high~speed computing machine and could have the
`
`control cell for these numbers as needed. The real
`objection to this procedure is the practical need
`for checking computations.
`If we suspect that a
`calculation is wrong, almost any reasonable check
`involves repeating something done before. At
`that point the introduction of new random num-
`bers would be intolerable.
`I think that the direct
`use of a physical supply of random digits is abso-
`lutely inacceptable for this reason and for this
`reason alone. The next best thing would be to
`produce random digits by some physical mecha-
`nism and record them, letting the machine read
`them as needed. At
`this point We have maneu—
`vered ourselves into using the weakest portion of
`presently designed machines—«the reading organ.
`Whether or not this difficulty is an absolute one
`will depend on how clumsy the competing processes
`turn out to be.
`Any one who considers arithmetical. methods of
`producing random digits is, of course, in a state of
`sin. For, as has been pointed out several times,
`there is no such thing as a random number—there
`are only methods to produce random numbers,
`and a strict arithmetic procedure of course is not
`such a method.
`(It is true that a problem that
`we suspect of being solvable by random methods
`may be solvable by some rigorously defined
`sequence, but this is a deeper mathematical ques-
`tion than we can now go into.) We are here
`dealing with mere “cooking recipes” for making
`digits; probably they can not be justified, but
`should merely be judged by their results.
`Some
`statistical study of the digits generated by a given
`recipe should be made. but exhaustive tests are
`impractical.
`If the digits work well on one prob—
`lem, they seem usually to be successful with others
`of the same type.
`.
`If one nevertheless considers certain arithmetic
`methods in detail,
`it is quickly found that the
`critical thing about them is the very obscure, very
`imperfectly understood behavior of round-off errors
`in mathematics.
`In obtaining y as the middle
`ten digits in the square of a ten—digit number x,
`we are really mapping 2: onto 3/ by a certain saw-
`toothed discontinuous curve y=f(:r), for 09.51,
`OSySl. When we take m,+,;f(x,) for i=1, 2,
`3,
`.
`.
`.
`,
`this curve will gradually scramble
`the digits of
`1‘; and produce something fairly
`
`|PR2018-00067
`
`Unified EX1027 Page 1
`
`36
`
`IPR2018-00067
`Unified EX1027 Page 1
`
`

`

`
`
`.
`
`pseudo—random. A simpler process suggested by
`Dr. Ulam is
`to use
`the mapping function
`If one produces a sequence {33,}
`f(is):4s(1——r).
`in this manner, mm is completely determined by
`art, so that independence is lacking.
`t is, however,
`quite instructive to analyze the nature of ran—
`domness that exists in this sequence. One can,
`by an incomplete argumentation,
`apparently
`establish one kind, and then see that in reality a
`very different kind holds. First, let the relations
`:r,:sin2 1ra1- define the sequence {at} (each modulo
`1). Since xi+1=4m,(1—m,-), one sees that (1,4.1320“
`(modulo 1). The sequence {at} is thus obtained
`in binary representation by shifting the binary
`number
`a1=-fi1;3263fl4
`.
`.
`.
`as
`follows: on:
`!
`'.32l33154
`-
`-
`a
`-
`-
`-
`at='5118i+113¢+2
`-
`-
`1
`.
`.
`.
`.
`It follows
`from the theorem of Borel
`about
`the randomness of
`the digits of
`real
`numbers that, for all numbers on except
`those
`in a set of Lebesgue measure zero, the numbers
`a, are uniformly distributed on the interval (0,1).
`Hence, the x,- are distributed like the numbers :17:
`sin21ry, with equidistributed y,
`i. e., with the
`probability distribution (2w)“{r(1—:r)]””dx.
`However, any physically existing machine has
`a certain limit of precision. Since the average
`value of lf’(x)l on (0, 1.)
`is 2, in each transforma-
`tion from as.- to as,“ any error will be amplified on
`the average by approximately two.
`In about 33
`steps the first round—off error will have grown to
`about 101”. No matter how random the sequence
`{15,-} is in theory, after about 33 steps one is really
`only testing the random properties of the round-off
`error. Then one might as well admit that one
`can prove nothing, because the amount of
`the—
`oretical information about the statistical proper—
`ties of the round—off mechanism is nil.
`As Dr. Hammer told us, sequences {33,} obtained
`from the squaring routine haVe been successfully
`used for various calculations. By the very as-
`sumption of randomness, however, one is exposed
`to the systematic danger of the appearance of self—
`perpetuating zeros at the ends of the numbers 23,.
`Dr. Forsythe’s remark that in some cases the zero
`mechanism is the major mechanism destroying
`the sequences is encouraging, because one always
`fears the appearance of undetected short cycles.
`I fear, however, that if we used one of Dr. Brown’s
`ingenious tricks to overcome the zero mechanism,
`we might just bring out the next most disastrous
`mechanism.
`In any case, I think nobody who is
`practically concerned will want to use a sequence
`produced by any method without
`testing it
`statistically, and it has been the uniform ex—
`perience With those sequences that
`it
`is more
`trouble to test them than to manufacture them.
`Hence the degree of complication of the method
`by which you make them is not
`terribly im—
`portant; what
`is important
`is to carry out a
`relatively quick and efficient
`test. Personally
`I suspect that it might be just as well to use some
`cooking recipe like squarin and taking the middle
`digits, perhaps with more digits than ten.
`
`
`
`Let me now consider questions of the class (B).
`If one wants to get random real numbers on
`(0,
`1)
`satisfying a uniform distribution,
`it
`is
`clearly sulficient
`to juxtapose enough random
`binary digits. To avoid any bias it is probably '
`advisable always to force the last digit to be a 1.
`If, however, the numbers are to satisfy some non—
`uniform probability distribution f(s)d:r. on (0, 1),
`some tricks are possible and advisable. Suppose
`one lets t:F(r)r—L1f(a)du, and lets r=tb(t)
`represent
`the transformation inverse to F.
`If
`the random variable T is uniformly distributed on
`(0, 1), then the random variable X:@ (T) obeys
`the distribution law F(3:). Now the human com—
`puter can obtain the inverse function reasonably
`efficiently by scanning, with or Without
`the aid
`of the rotating drum mentioned in Dr. Wilson’s
`paper earlier in this symposium. A machine scans
`poorly, but might be instructed to calculate each
`X from T. This calculation is, however,
`likely
`to be quite cumbersome in practice, and I should
`like to mention some other methods that are often
`more efficient when they are applicable.
`One trick is to pick a scaling factor a such
`that (#0051, and then to produce two random
`numbers, X and Y, from a uniform distribution on
`(0, 1).
`If Y>oj(X), we reject the pair and call
`for a new pair.
`If YSeflX), we accept X.
`Since the acceptance ratio is proportional
`to
`flX),
`the accepted numbers X will have the
`probability distribution f(a:)d:r. One can see that
`the efficiency of the method depends on the ratio
`of the average value of fins) to its maximum value;
`the smaller the ratio,
`the more difficult it Will
`be to use the method. One characteristic of this
`method is that one cancften make the test “is
`Y>aj(X) ?” implicitly, Without having to calculate
`j(X) explicitly. For example, if
`
`af(;r)=(1—:r?)“,
`
`one may make the test ”is X2+ Y2>1?” and
`only elementary operations are needed.
`Suppose one wants to produce random numbers
`9 in (—1, 1) according to the distribution
`
`1r”1(1—- 92)—%d9.
`
`The obvious procedure is to take a uniformly
`distributed random variable T in (—1, 1) and
`calcula to
`
`9 = sin 11' T.
`
`I have a feeling, however, that it is somehow silly
`to take a random number and put it elaborately
`into a power series, and in this case one can employ
`a trick related to the last one. Select two random
`numbers X, Y from a uniform distribution on
`(0, 1); the point (X, Y) lies in the unit square. To
`make sure that its angle,
`.
`
`¢=arc tan (X/Y),
`
`3
`|PR2018200067
`
`Unified EX1027 Page2
`
`
`
`IPR2018-00067
`Unified EX1027 Page2
`
`

`

`is unifOrmly distributed on (O, 1/2), We first reject
`the pair if X2+Y2>L If 134—17251, we accept
`the pair and form :l:X/(X2+Y2)’i (irandom),
`which will have the desired distribution. The
`efficiency of the process is clearly 1r/4. The Only
`disagreeable feature is the square root, and even it
`may be eliminated by forming 8 not as
`
`but as
`
`isin e: iX/(XB-l—YZ)”,
`
`sin (2(13— 1r/2)=—cos 2¢=(X2—— Y2)/(X2+ Y2),
`
`which has the same distribution.
`Let me give one final example, the generation of
`nonnegative random numbers X with the distribu—
`tion 3“ d1. As you know, such numbers X repre‘
`sent free paths in the slab problems discussed in
`this symposium. The normal procedure is to pick
`T from a uniform distribution on (0, 1) and com-
`pute X:-—l0g T, but, as before, it seems objec—
`tiOnable to compute a transcendental function of a
`random number. Another method for getting X
`resembles a well known game of chance——Twenty—
`one, or Black Jack. We select numbers Y; from a
`uniform distribution on (0, 1) as follows. Pick Y1
`and Y2.
`If Kg Y2, we stop.
`If Y1>Y2, We select
`Y3.
`If Y2§Y3, we stop. Otherwise Y1>Y2> Y3,
`and we select Y4, etc. W'ith probability one there
`will be a least a for which
`
`YI>Y2> .
`
`.
`
`. >Yn, but: Ynslfrhpl.
`
`Now if n is odd, we accept Y1 as X, but if n is even,
`we reject all the Y1. To analyze this process, let
`Efl represent the event
`
`Y1>Y2> .
`
`.
`
`. >1”...
`
`It is easily shown by induction that
`
`Prob (En)=(n1)*1,
`
`
`
`
`
`While
`
`Prob {$<Y1<$+dr [ given En}:nxfl-ldx,
`Hence the probability that we simultaneously
`have
`
`is
`
`x<Y1<x+d$, En, and not-En“
`
`[35’1’1/(nfl l)lrr"/n!] (13'.
`
`Summing over all odd n, we see that
`
`Prob{;v< Y1<m+dx} :e‘rdz.
`
`We have therefore generated the portion 039531
`of the desired distribution; to get the complete
`distribution we must do something with the
`rejected fraction (3‘1) of the trials. Since
`e‘”(lm=e‘le’r+‘d:r,
`
`what we do is repeat the rejected trial but interpret
`the new Y1 differently.
`If Y1 from the retrial is
`accepted,
`take X:Y1+i.
`If the retrial
`is re-
`jected, but the Y1 from a second retrial is ac—
`cepted, we take X: Y;+2. Each time a trial is
`rejected, the range of values of X is increased by
`unity. A calculation shows that one may expect
`to choose about
`
`(1+?)(1—6“)"‘“5
`
`values of Y for each X,- selected; the process effi-
`ciency is thus about. one—sixth. The machine has
`in effect computed at logarithm by performing only
`diseriminations on the relative magnitude of
`numbers in (0, 1).
`It is a sad fact of life, however,
`that under the particular conditions of the Eniae
`it was slightly quicker to use a truncated power
`series for log (l—T) than to carry out all the dis-
`criminations.
`In conclusion,
`I
`should like to
`mention that the above method can be modified to
`yield a distribution satisfying any first—order
`differential equation.
`
`|PR2018-00067
`
`Unified EX1027 Page 3
`
`
`
`
`
`IPR2018-00067
`Unified EX1027 Page 3
`
`