next up previous
Next: EMPIRICAL RESULTS Up: INVERSIVE PSEUDORANDOM NUMBER GENERATORS: Previous: INVERSIVE GENERATORS

THEORETICAL RESULTS

 

In the theoretical analysis of pseudorandom number generator s, we study the following questions:

(Q1) What is the maximal period length of the given type of generator?

(Q2) How to choose the parameters to obtain maximal period length?

(Q3) Which algorithms let us obtain such parameters?

(Q4) What can we say about correlations between pseudorandom number s and what results hold for the empirical distribution of samples?

(Q5) What are the regularities (i.e. lattice structures, tex2html_wrap_inline607) of this type of generator?

The answers for the ICG are as follows. We consider ICG(tex2html_wrap_inline609), with p a prime. As for (Q1), Eichenauer and Lehn (1986) have shown that the maximal period length is p. In the same paper, the have provided an answer to question (Q2): if tex2html_wrap_inline615 is a primitive polynomial over the finite field tex2html_wrap_inline543, then ICG(tex2html_wrap_inline609) has maximal period length. Flahive and Niederreiter (1992) have extended this result considerably. They have shown that IMP-polynomials induce maximal period length. This approach has allowed Chou (1994) to obtain a very effective algorithm for IMP-polynomials, thereby replying to (Q3). Our tables in Section 5 have been computed with an implementation of this algorithm.

Question (Q4) is the most difficult to answer. It is a generally accepted approach to study the empirical distribution of overlapping s-tuples
displaymath623
or nonoverlapping s-tuples
displaymath627
in the s-dimensional unit cube tex2html_wrap_inline631, either with tools from number theory and statistics, in other words, with discrepancy, or with geometrical test quantities like the spectral test. The behavior of the points tex2html_wrap_inline633 is used as an indicator of correlations within the sequence tex2html_wrap_inline591 of pseudorandom number s.

Uniform pseudorandom number s tex2html_wrap_inline517, tex2html_wrap_inline525, should simulate realizations of independent, identically U([0,1[)-distributed random variables. Hence the points tex2html_wrap_inline633 should be approximately tex2html_wrap_inline645-distributed. For a given sample tex2html_wrap_inline647 = tex2html_wrap_inline649 in tex2html_wrap_inline631, there are several concepts to assess its empirical distribution. From the statistical point of view, it is natural to compare the empirical distribution function of the points tex2html_wrap_inline633, tex2html_wrap_inline655, to the target distribution, which is uniform distribution on tex2html_wrap_inline631, by means of a classical goodness-of-fit test, the two-sided Kolmogorov-Smirnov test statistic (``KS-test''). In number theory, this test quantity is called the star discrepancy. Niederreiter has developed an impressive technique to obtain discrepancy estimates. It has allowed to determine the order of magnitude of discrepancy for most types of pseudorandom number generator s. Usually, these results hold for the whole period of a generator only and not for smaller samples, as they are relevant in practice. We refer to the monograph Niederreiter (1992) and the comprehensive survey Niederreiter (1995a).

The ICG excels in this respect. The discrepancy of full period sets tex2html_wrap_inline647 is of the same order of magnitude as the law of the iterated logarithm for the discrepancy suggests, see Niederreiter (1992) and Eichenauer-Hermann (1994b). An average-case analysis of the discrepancy of samples has been carried out by Eichenauer-Herrmann and Emmerich (1994, 1995), with interesting results. It has to be noted that the only condition on the parameters a and b is that they must imply maximal period length. Once this requirement is met, ICG(tex2html_wrap_inline609) will have those excellent correlation properties. This fact stands in sharp contrast to the sensibility of the LCG concerning the choice of parameters.

The spectral test of Coveyou and MacPherson (1967) is a completely different approach. In its original form, it is a figure of merit derived from certain exponential sums. In practice, this numerical quantity can only be computed if the set tex2html_wrap_inline647 in tex2html_wrap_inline631 has a lattice structure. In this special case there exists a nice geometric interpretation, see Knuth (1981) and Ripley (1987).

The spectral test does not apply to the ICG, nor the EICG, see the discussion of (Q5) below.

Concerning (Q5), the ICG differs strongly from linear methods in its geometrical structure. As Marsaglia (1968) has noted for the LCG, ``random numbers fall mainly in the planes''. Eichenauer-Herrmann (1991) has shown that ICG ``avoid'' the planes. Further, ICG pass the lattice test in dimensions that are out of reach for the LCG, see Niederreiter (1992, 1995a).

The simple definition of the EICG allows even stronger results. Questions (Q1), (Q2), and (Q3) are easy to answer. The maximal period of EICG(tex2html_wrap_inline557) is p. It will be obtained if we choose tex2html_wrap_inline675. As for (Q4), EICG behave like ICG with respect to discrepancy. Again, the spectral test is useless, due to the absence of any lattice structure.

There is a truly remarkable difference between the EICG and any other type of pseudorandom number generator , namely excellent splitting properties. As a consequence, the EICG qualifies as one of the most promising candidates for parallelization. Due to Eichenauer-Herrmann (1993a), Niederreiter (1994), and Eichenauer-Herrmann and Niederreiter (1994), a thorough theoretical assessment of the behavior of substreams and of general types of s-tuples tex2html_wrap_inline633 is known. These results ensure against long-range correlations, in sharp contrast to the LCG. We refer to De Matteis and Pagnutti (1990) for the latter.

Niederreiter (1994) has shown that the explicit-inversive method yields optimal behavior under the lattice test. There are no regularities with respect to hyperplanes. As with the ICG, explicit-inversive pseudorandom number s avoid the hyperplanes. This replies to (Q5).

The compound approach preserves the excellent properties of the ICG and EICG. The answers to (Q1), (Q2), and (Q3) follow directly from the above results for the components. Compound inversive generators have the same outstanding correlation properties as single inversive generators, see the survey of Eichenauer-Herrmann and Emmerich (1995). This answers (Q4). Question (Q5) is still open, but there is some empirical evidence. All scatterplots show the same nonlinear structures as single ICG and EICG.

An Important Remark

The theoretical assessment of pseudorandom number generator s is sometimes viewed as being ``esoteric''. This fact is partly due to the abstract language in which the results are presented.

Theoretical tests of a certain pseudorandom number generator cannot guarantee that samples from this generator will pass a given statistical test. In the first type of tests we are forced to consider very large samples, usually the full period of the generator. This limitation is due to the mathematical methods involved. In empirical tests, we consider much smaller samples, as they appear in the practice of simulation. Alas, from the behavior of very large samples we cannot reason on the performance of small samples. The missing mathematical link between theoretical and empirical tests has not yet been found. Nevertheless, almost three decades of practical experience have shown that certain theoretical measures, such as discrepancy or the spectral test, are reliable indicators. If a generator performs well with respect to these tests, its samples will pass a large class of stringent empirical tests.

Theoretical test quantities like discrepancy or the spectral test cannot be computed for samples as they appear in practice. Either the computational complexity is prohibitive, as in the case of discrepancy, or the test is not defined, as it happens to be the case for the spectral test. There is a definite lack of test quantities that are relevant in theory as well as in numerical practice.


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


next up previous
Next: EMPIRICAL RESULTS Up: INVERSIVE PSEUDORANDOM NUMBER GENERATORS: Previous: INVERSIVE GENERATORS

Peter Hellekalek