paul@oddjob.UChicago.UUCP (Paul Schinder) (01/05/85)
<> I am doing Monte Carlo integrations on several different machines, and I am using several different random number generators. I don't know how reliable these generators actually are. Does anyone out there have a test program which will take the output of a random number generator and check the numbers produced to see whether they are suitable for use as random numbers? What tests are usually used to test random number generators? Thanks. -- Paul Schinder Astronomy and Astrophysics Center University of Chicago uucp: ..!ihnp4!oddjob!paul
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (01/07/85)
> What tests are usually used to test random number generators?
Knuth volume 2 is mandatory reading for this subject.hes@ecsvax.UUCP (Henry Schaffer) (01/07/85)
In my opinion, testing the quality of a random number generator is a rotten job. Sometimes you can find something wrong, but you can seldom say enything more than, "So far, no obvious problems." If you still want to test, it is best to analyze how you are going to use them, and then test for the particular qualities you need. Common tests include: Equidistribution- divide your output interval (e.g. 0-1) into 10 or 20 subintervals, develop a frequency table of a LARGE number of random numbers, and use the Chi-Square Test. Lag Correlations-correlations between adjacent random numbers; correlations between random numbers i apart (i=1,2,3,...)- where you stop is determined by your use, statistically test for the significance of the correlation coefficient(s). The problem is that deviations from randomness can be very subtle, some years ago Marsaglia had an article on Random Numbers Fall Mainly in the Planes (CACM?) showing the crysalline behavior of n-tuples from congruential random number generators. Probably the best place to start reading is Knuth's Volume 2. --henry schaffer n. c. state univ. ...mcnc!ecsvax!hes
sher@rochester.UUCP (David Sher) (01/09/85)
I heard of a test for a random # generator developed at Xerox Park. The way they tested it was to use it to generate the bits controling whether the successive points on a graphics output were black or white (or some variant thereupon). If you could not perceive a pattern by looking at it then your random # generator probably generates fairly "white" noise. (The human eye is probably somewhat better than any easily written computer program at pattern detection). -David Sher
bates@uwstat.UUCP (01/09/85)
Another reference on random number generators and testing of them is
"Statistical Computing" by Kennedy and Gentle published by Marcel
Dekker. There are also more recent articles by Marsaglia which I could
look up if you were really interested.
A common problem with Monte Carlo runs, though, is the choice of seed
rather than the quality of the random number generator. The designers of
random number generators go to a great deal of trouble to get
non-repeating sequences of 2^30 or longer but methods of choosing seeds
usually only give you 10000 different seeds or so. One easy fix for this
is to store the state of the random number generator between program
runs and pick up on the same sequence at the next run. This is the
method used in the S statistical system.
--
Doug Bates @ wisconsin
ARPA: bates@wisc-stat.arpa
bates@uwisc (if you have the old host table)
UUCP: ...!{allegra,heurikon,ihnp4,seismo,sfwin,ucbvax,uwm-evax}!uwvax!batessesv@ihuxp.UUCP (Steve Sommars) (01/11/85)
On a related topic, here is one non-obvious programming bug which bit me in an old Monte Carlo. I was using a random number generator several places in the program. The format of the call (translated from FORTRAN) value = random(&x); If 0 < x < 1, use x as the seed in the random number generator, x is modified in the process. After testing the subroutines individually (successfully), I combined them & tested the entire Monte Carlo. Wow! I was finding new resonances, elementary particles, etc. The whole framework of particle physics was shaken. My elation was quenched when I realized that I was using the random number generator as: value1 = random(&x1); value2 = random(&x2); value3 = random(&x3); The calculated result depended upon value1, value2 and value3. Since the random number was based upon a linear congruence generator, I was marching along a single sequence of numbers three times with constant phase difference. The three values turned out to be strongly correlated, this caused the erroneous Monte Carlo Results. The moral is, "In addition to all other testing of random number generators, make sure that they are initialized exactly once." Steve Sommars AT&T Bell Labs ...!ihnp4!ihuxp!sesv