| |
|
|
| |
| |
| |
We have so far discussed the desired features of random number generators and described some of the popular generators used in Monte Carlo applications. Now the question arises: How good are the random number generators? While most generators are quite good for a variety of applications, there have been a few applications in which popular generators have been found to be inadequate [3, 4, 5, 6].
Sophisticated Monte Carlo applications often spend only a small
fraction of their time in the actual random number generation. Most
of the time is taken up by other operations. It is therefore
preferable if we can test the random number generator fast, without
actually using it in the application, to determine if it is good.
For example in the runs test we divide the random number
sequence into blocks that are monotonically increasing, and
determine the distribution of the lengths of each block. This is a
good test of randomness because it is fast and looks at correlations
between longer and longer groups of random numbers. (Using a
sequence of length 
we expect to see runs as long as 15.)
However, a single statistical test is not adequate to verify the randomness of a sequence, because typical MCMC applications can be sensitive to various types of correlations. However, if the generator passes a wide variety of tests, then our confidence in its randomness increases. The tests suggested by Knuth [7] and those implemented in the DIEHARD package by Marsaglia [36] are a standard. Since there are many generators which pass these tests there is no reason to consider one that is known to fail. Of course, any generator will eventually fail most tests, so we always must state how many numbers were used in the test. level of accuracy).
The second type of test is to run an application that uses random numbers in a similar manner to your applications, but for which the exact answer is known. For statistical mechanical applications, the two-dimensional Ising model (a simple lattice spin model) is often used since the exact answer is known and it has a phase transition so one expects sensitivity to long range correlations. There are several different MCMC algorithms that can be used to simulate the Ising model and the random numbers enter quite differently in each algorithm. Thus this application is very popular in testing random number generators and has often detected defects in generators. We can test parallel generators on the Ising model application by assigning distinct random number sequences to subsets of lattice sites [37].
How good are the popular generators on the Ising model? Ferrenberg, et al [3] found that certain generators such as the particular shift register generator they used (R250) failed with the Wolff algorithm, while the simple and much maligned 32 bit LCG called CONG did well. Similar defects in popular generators have also been observed by others [4, 5, 6]. However, with the Metropolis algorithm, CONG performed much worse than R250. Thus it appears that it is the combination of problem and generator that must be considered in choosing a suitable generator. Thus statistical tests are not adequate; we must also test the generators in our actual application.
Of course in almost all cases we do not know the exact answer. How then can we trust a given generator on our problem? The only general approach is to run our application with several different types of generators that are known to have good statistical properties. Hopefully at least two will agree within the error bars and they can be used on further similar runs with that algorithm. A word of caution: the test runs must be at least as long as the production runs because subtle correlations in the PRNG may not show up until long runs are made. This approach is quite computationally expensive and if done seriously would increase the cost of all MC simulations by a factor of two. (If you decide at the end that all generators are good, you can recover the time by averaging the results together.)
The National Center for Supercomputing Applications
University of Illinois at Urbana-Champaign
ashoks@ncsa.uiuc.edu
Last modified: September 16, 1997