next up previous



As the performance in theoretical tests is no guarantee, but only an indicator of what we may expect in practice, empirical testing of pseudorandom number generator s is an absolute necessity. A popular misconception is to equate testing pseudorandom number s with testing ``randomness''. The latter term is undefined in statistics. No random number generator is ``more random'' than any other. We propose to forget about the misleading term ``randomness'' and to concentrate upon the original purpose of pseudorandom number generation. The objective is to get reliable results in stochastic simulation. No pseudorandom number generator is appropriate for all tasks. As a consequence, we shall try to identify statistical tests that are similar to our simulation problem. If a generator passes these tests, we may expect ``good'' simulation results from it. For our notion of ``goodness'', see Wegenkittl (1995). Certain statistical tests have proven their relevance for a large number of problems encountered in practice.

As a first example of such a test, we would like to check if the bits in the binary representation of pseudorandom number s tex2html_wrap_inline517, tex2html_wrap_inline525, simulate realizations of independent random variables, equidistributed on the set tex2html_wrap_inline685. The following test design is due to Leeb (1995), who has also contributed Figures 3 and 4. From the binary representation of every coordinate of the nonoverlapping s-tuple tex2html_wrap_inline689 tex2html_wrap_inline691 tex2html_wrap_inline693 tex2html_wrap_inline695 we take a block of l digits that starts at the k-th digit. We perform this operation on tex2html_wrap_inline701 s-tuples. This procedure will yield a quantity tex2html_wrap_inline705 that simulates the upper tail probability tex2html_wrap_inline707 of a tex2html_wrap_inline709distributed random variable. tex2html_wrap_inline707 is an equidistributed random variable on [0,1[. In a second step, we compute the value of tex2html_wrap_inline705 for 64 distinct consecutive samples of size N. We compare the empirical distribution of these 64 numbers to the distribution of tex2html_wrap_inline707 by means of a two-sided Kolmogorov-Smirnov test statistic. We denote its value by tex2html_wrap_inline721. The distribution of the KS-statistic is known. To a level of significance of 0.01, there corresponds the critical region tex2html_wrap_inline723. The following figures illustrate the results for the Ansi-C generator, see Figure 3, and ICG(tex2html_wrap_inline725, see Figure 4. The parameters are s=4, tex2html_wrap_inline729 and tex2html_wrap_inline731. Large values of tex2html_wrap_inline733 have been truncated to keep the graphics in scale. The ICG is clearly superior, the LCG performs poorly.


Many models in stochastic simulation have the form
where tex2html_wrap_inline737 is some given function and the tex2html_wrap_inline739 are independent, identically U([0,1[)-distributed random variables. As the M-tuples overlap, the usual tex2html_wrap_inline745-test cannot be applied. This approach leads to the important overlapping M-tuple test of Marsaglia (1985).

The M-tuple test is a stringent test. Wegenkittl (1995) gave a detailed proof of the distribution of this random variable that is missing in Marsaglia's paper. The following test design and Figures 5 and 6 stem from Wegenkittl (1995). It is an application of the M-tuple test. From every component of an overlapping 5-tuple tex2html_wrap_inline747 of pseudorandom number s tex2html_wrap_inline749 [0,1[, we take the first four bits in its binary representation. Then, for a given sample size N, we compute 32 values of the -theoretically equidistributed- upper tail probability of the M-tuple test. In the following figures, the sample size ranges between tex2html_wrap_inline755 and tex2html_wrap_inline757. In Figure 5, we plot the 32 values of this test statistic. The resulting patterns should be irregular. If, for a given sample size N, the corresponding box is either totally white or black, the generator has failed miserably. For example, the Fishman and Moore LCG begins to break down from tex2html_wrap_inline761 onwards. In Figure 6, we show the result of a two-side d KS-test applied to these 32 values. Values of the KS-test statistic greater than the critical value 1.59 that corresponds to the significance level of 1% are shown in dark grey. We compare the following PRN generators:

EICG(tex2html_wrap_inline763, short ``EICG1"

EICG(tex2html_wrap_inline765, short ``EICG7"

ICG(tex2html_wrap_inline725, short ``ICG"

LCG(tex2html_wrap_inline769, short ``FISH''

LCG(tex2html_wrap_inline771, short ``ANSIC''

LCG(tex2html_wrap_inline773, short ``MINSTND''

LCG(tex2html_wrap_inline775 short ``RANDU"

``FISH'' was recommended by Fishman and Moore (1986) because of its excellent lattice structure. ``ANSIC'' is the Ansi-C system generator. The call rand(0) is equivalent to our initialization. ``MINSTND'' is the ``minimal standard" generator of Park and Miller (1988) , where ``RANDU'' is also discussed. The latter is an unlucky product of IBM.


Figure 5: The Distribution of the Upper Tail Probabilities of the M-Tuple Test Statistic


Figure 6: The Values of the KS-Test Statistic

Our third example is the run test. Since Knuth (1981), the run test has proven to be a very reliable test to detect correlations within a sample tex2html_wrap_inline777 of pseudorandom number s. We refer to Fishman and Moore (1982) for empirical results concerning LCGs.

Entacher (1995a, 1995b) has studied the runs up statistic. For a given sample of size N, 100 values of this asymptotically tex2html_wrap_inline745-distributed quantity have been generated. In a second step, a two-sided KS-test was applied to these values to check the goodness-of-fit. The following figures show the results for the minimal standard generator and for EICG(tex2html_wrap_inline783). The two horizontal lines represent the critical values of the KS test statistic that correspond to the significance levels 0.05 and 0.01. The sample size ranges from tex2html_wrap_inline785 to tex2html_wrap_inline787 We have considered the subsequence tex2html_wrap_inline789. Similar results hold for other LCG and EICG, see Entacher (1995b). Apparently, large samples of the LCG have an increasing tendency to fall into the critical region.


As a final remark in this section, we would like to draw the reader's attention to the fact that all our tests are two-level tests in the sense of L'Ecuyer (1992) and that we have varied the sample size. This careful test design is not as common in the published literature on pseudorandom number generation as one would wish.

Overview * Team * Generators * Tests * News * Literature * Links

next up previous

Peter Hellekalek