Structural properties of PRNGs

  In order to describe properties of PRNs that are relevant for an actual application we have to develop numerical measures of sequences of PRNs that allow us to distinguish between the different generation methods. Such measures can be divided into two classes, depending on the kind of arguments involved.

So-called statistical tests characterize a sequence of PRNs in comparison to all possible sequences of RNs by rating the region into which the results fall. They will be discussed in the next chapter. In this section, we shall concentrate on structural properties of PRNs.

For certain algorithms we are able to describe in a detailed way the subset of or , in which the PRNs fall.

Let us look at a trivial example for such a characterization: if a PRNG first produces integers in the range and divides each number by per, the PRNs will lie in the finite subset

of [0,1[. The maximal possible resolution of these numbers is a known property of the generator and can be used to distinguish it from other generators. It is clear that a finer resolution of the generator will be regarded an advantage in most simulation problems. This is one explanation for the importance of theoretical results that guarantee maximal period length.

All the generators in our test battery have a period that is long enough to put the resolution of the random numbers in the region of the resolution of the typical 'float' types on most computers; apart from using 'double' types or special computing packages a longer period would not contribute any more to the resolution of the values that can be used in common programming languages. However, a long period is still a reasonable criterion for choosing a generator even when the resulting numbers do not gain in resolution. As we will see in Chapters 3 and 4, this is especially the case when many calls to the generators are made.

A generalization of the concept of resolution to more dimensions is the term ``lattice". A lattice is a set of the form

where the denote s linearly independent vectors in . This definition can be found in [16, Section 1.3, Definition 1,].

If we now take nonoverlapping s-tuples of PRNs and form s-dimensional vectors, the same argument as above holds: the pseudorandom numbers of a generator with period length per will lie on the lattice

where is the i'th unit vector. Actually, a widely used type of generator, the LCG, produces numbers that lie on a much coarser lattice! The following plot of overlapping 3-tuples generated by the famous RANDU needs no accompanying words:

 

Randu, overlapping 3-tuples.

Pay attention to the fact that RANDU has a period length of ! In order to illustrate the sensibility of the LCG with respect to the choice of parameters, we consider two ``toy" LCGs.

LCG(1024,1021,21), overlapping 2-tuples.

We will not give the proof for this coarse lattice structure of the LCG and refer the reader to Niederreiter [36] and Ripley [42]. However, differently parametrized LCGs produce totally different lattice structures as the following plot of a LCG with the same period shows.

LCG(1024,997,21), overlapping 2-tuples.

Using a computer-simulated magnifying glass, we even can reveal the lattice structure of a very 'good' LCG of our test battery. Look at the following plot, which contains all overlapping tuples that fall into the square :

LCG, overlapping 2-tuples, whole period. This is what is produced by an ICG: no lattice seems to be recognizable.

ICG, overlapping 2-tuples, whole period.

The same is true for an EICG:

EICG, overlapping 2-tuples, whole period.

Summing up, we have the following very important difference between linear congruential generators and inversive methods:

For a mathematical proof of the statement, we again refer the reader to Niederreiter [36]. A measurement for the 'coarseness' of a lattice is the so called spectral test which can be found in Knuth [26, p.89,]. Recently, a new approach has been introduced by Hellekalek [19]. The weighted spectral test allows a similar theoretical analysis as is possible for the discrepancy. Further, empirical computations for samples are possible.

Well, all this lattice theory is certainly of interest for mathematicians. But what are the consequences for practical stochastic simulation? In our opinion, the following arguments can be built upon the theoretical results:

1. A coarse lattice contains large regions which will never be hit by a point of the generator. There exist simulation problems which will only give reasonable results when these regions are hit by the expected number of points. If somebody expects their simulation problem to be sensitive in this respect, the results should at least be controlled by a second simulation using an inversive generator or a LCG with a fine lattice structure.
2. A lattice expresses strong regularities. We expect certain 'natural' simulation problems to be sensitive to such regularities. Unexpected results can for example result from the superposition of a regular partition of the sample space by the simulation on the lattice which results in aliasing effects or interference. We will meet this argument again in Chapter 4.
3. In the following chapters we will introduce empirical statistical tests that show considerable differences between linear and inversive generators. Many of the results can be explained with the lattice structure of the LCGs.

We have included these remarks in the thesis to make the reader aware of the differences present behind the generation methods for PRNs. These differences are a big advantage! Different types of generators can and should be used to verify simulation results. From the mathematical viewpoint it is clear that the inversive generators will cause certain simulations to yield bad results, too. Whether these simulations have a structure that appears among 'natural' problems within the field of stochastic simulation cannot be told without further analysis. For the moment all we can do is to increase our confidence in a simulation by evaluating it with strongly different random numbers and comparing the results.