More Point Sets

Based on the theory of uniform distribution, many different point sets and sequences have been developed or studied in detail. In this section, we show further examples and visualize the behavior of their local discrepancy with our graphics tools.

The Halton sequence in dimension two differs from the Hammersley sequence only in that the second coordinate in equation (1) uses the ternary expansion for instead of the binary expansion. The following graphics show a Halton sequence for and its visualization of local discrepancy.

Figure 8. Local discrepancy of a Halton sequence .

Lattices are essentially different from the nets shown in earlier sections. Special lattices are obtained if we produce all "overlapping" vectors () from a point set , where the numbers are generated with and via the recurrence . The parameters and , , and the starting value have to fulfill certain conditions in order to get the full period for the recurrence (see [3, 8]). The parameter is responsible for the distribution quality of the lattice. If is chosen well, the vector is called a good lattice point, because the corresponding lattice is generated from multiples of . In Figures 9 and 10 the modulus and the additive constant . In Figure 9 we use the bad parameter and in Figure 10 the good parameter .

Figure 9. Local discrepancy of bad lattice points with and .

Figure 10. Local discrepancy of good lattice points with and .

The weak distribution for is clearly seen in the visualization of local discrepancy. The good lattice is more dispersed, like Figure 5. The reader is asked to try to compute the three-dimensional visualization of the bad lattice.

There is another important application of such lattices. The modular generation method yields a classical method for the generation of (pseudo-) random numbers. If one uses only a small sample of numbers from the previous recurrence with large modulus (sample size lower than the square root of modulus recommended), then the numbers behave like "real" random numbers in many applications. The generation method is called the linear congruential generator (LCG). Figure 11 visualizes a sample of numbers from a widely used LCG called the "Minimal Standard" generator (, , ) [9] (for further references see [10]).

Figure 11. Local discrepancy of a sample from the Minimal Standard random number generator.

Linear congruential pseudorandom number generators have often been criticized for the underlying lattice structures they produce if all overlapping vectors are considered. Therefore, several other (nonlinear) generators have been proposed where overlapping vectors generated from such random numbers are not contained in lattices (or small unions of lattices). Thus, we consider a "baby" version and a more recent nonlinear generator, called the explicit inversive congruential generator (EICG), defined by Eichenauer-Herrmann [11]. The reader is asked to recover the modular generation method by means of the following Mathematica implementation. From the baby generator with modulus , we produce all possible overlapping vectors (Figure 12), and from a large EICG with modulus and the same multiplier 117, we generate a sample of numbers (Figure 13).

Figure 12. Local discrepancy of a baby EICG with and .

Figure 13. Local discrepancy of a small sample of an EICG with and .