Spectral test

The spectral test is a method that can be used to check whether given random numbers are actually stochastically independent of one another , or whether the opposite is the case, i.e. H. Values ​​already "rolled" influence the following values ​​- and the latter thus become (more or less) predictable.

For the spectral test , the random numbers obtained are combined into tuples and it is checked how well these vectors are distributed in their value range of the -dimensional space and how well this distribution corresponds to the theoretically required. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$

The test is used to evaluate ( pseudo ) random number generators . Linear congruence generators (LKG), for example, are still frequently used , and depending on the choice of parameters, they have very different good or bad qualities. A much better generator is the Mersenne Twister . An alternative to generators would be to measure physical phenomena (radioactivity, real cube).

Basic idea

Figure 1: The random number triples generated with RANDU are not distributed randomly, but are all concentrated in a small number of areas.

Figure 1 visualizes the random numbers generated with the RANDU algorithm in a way that corresponds to the basic idea of ​​the spectral test: Three random numbers were combined into a 3-tuple (triple), which is interpreted as a point in three-dimensional space and displayed graphically. The algorithm should actually generate evenly distributed random numbers (in the sense of: evenly distributed). Since a triple of three equally distributed random variables is again equally distributed, one would expect a completely uniform distribution in the graph.

However, it is easy to see that these points are not evenly distributed at all, but rather follow a pattern. If you now know, for example, two consecutive numbers, the third is no longer random, but takes on one of a maximum of 15 different values, which gives you a seven percent chance of guessing the correct one.

For a good random number generator, however, it should not be just 15 values, but as many as possible. An upper limit is set here by the number of numbers that can be generated by the generator. If these numbers are evenly distributed over the entire space of possible tuples (a cube with edge length ), you get points along each spatial direction. For the illustrated three-dimensional test by RANDU, this results . The actual number of 15 therefore falls far short of what is theoretically possible. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle {\sqrt[{i}]{m}}}$ ${\displaystyle {\sqrt[{3}]{2^{31}}}\approx 1290}$

execution

For the mathematical or computational analysis one considers families of parallel, (hyper) planes, which all have the same distance and contain all tuples (for a certain one ). The family with the greatest distance is then selected. This distance is denoted by. The reciprocal value is called accuracy . Mathematically it is not exact, but you can roughly imagine the accuracy as the approximate "number of areas". ${\displaystyle i}$ ${\displaystyle 1/\nu _{i}}$ ${\displaystyle \nu _{i}}$

${\displaystyle i}$further denotes the length of the examined tuples or sequences. For the RANDU example, we have so far considered the case , vividly: points in a cube that are arranged in parallel surfaces. denotes the distance between these surfaces. 2-tuples, on the other hand, are points in the plane that can be arranged in parallel lines. denotes the distance between these lines. The geometric concepts used for and are no longer clear for 4 and more dimensions - the mathematics used can still be used without any problems. ${\displaystyle i=3}$ ${\displaystyle 1/\nu _{3}}$ ${\displaystyle 1/\nu _{2}}$ ${\displaystyle i=2}$ ${\displaystyle i=3}$

The greater the accuracy , i.e. the smaller , the better the vectors are distributed in their value range. To assess the quality of a random number generator, one calculates the for i from 2 to maybe 5 or 6 and compares the results with those of other available generators or the theoretical value of approx . ${\displaystyle \nu _{i}}$ ${\displaystyle 1/\nu _{i}}$ ${\displaystyle \nu _{i}}$ ${\displaystyle {\sqrt[{i}]{m}}}$

The practical difficulty is to find an algorithm that will find the closest family you need. For some generators (e.g. LKGs such as RANDU) there are algorithms that deliver the exact result with relatively little computing effort. A more general approach is to interpret the distribution of points in space as density. Periodic changes then correspond to (i-dimensional) waves, which suggests an analysis of the frequency spectrum in order to determine the main direction and amplitude of the wave fronts. Hence the name: Spectral test.

In the case of generators that only supply a finite number of different numbers (periodic generators), the test can be carried out over the entire period.

Examples

The following examples are linear congruence generators . To generate random numbers by means of the formula and fixed constants , , and the initial value x ₀ . For this, Knuth gives a specific algorithm for performing the spectral test. The values ​​in the tables are also from there. ${\displaystyle x_{n+1}=(a\cdot x_{n}+c)\,{\textrm {mod}}\,m}$ ${\displaystyle a}$ ${\displaystyle c}$ ${\displaystyle m}$

example 1

m = 10000000000 = 10 ¹⁰ ; a = 3141592621; c = 1; x ₀ = 0. The spectral test delivers

${\displaystyle \nu _{2}}$	${\displaystyle \nu _{3}}$	${\displaystyle \nu _{4}}$	${\displaystyle \nu _{5}}$	${\displaystyle \nu _{6}}$	${\displaystyle \nu _{7}}$
67654	1017	249	42	23	23

The generator was chosen here as an example because it delivers a result that is typical of many good generators.

The numbers say something directly about the accuracy of the random numbers obtained: If you always need two random numbers in a calculation, for example because you need random points in the plane, you can give the results with a maximum accuracy of . If you need three per invoice, that's it . With four per invoice the result is . ${\displaystyle 1/\nu _{2}=1/67654=0{,}0000148<10^{-4}\Rightarrow 4{\text{ Dezimalstellen}}}$ ${\displaystyle 1/\nu _{3}=1/1017=0{,}000938<10^{-3}\Rightarrow 3{\text{ Dezimalstellen}}}$ ${\displaystyle 1/\nu _{4}=1/249=0{,}00402<10^{-2}\Rightarrow 2{\text{ Dezimalstellen}}}$

The Box-Muller method for generating normally distributed random numbers requires two random numbers per evaluation. Your results are better than four digits with this random number generator. The generator used in the example is useful. There are better generators, but there are also much worse ones, as the next example shows.

Example 2 - RANDU

The horror example in this context is the RANDU generator that was popular in the past:

m = 2147483648 = 2 ³¹ ; a = 65539 = 2 ¹⁶ +3; c = 0; x ₀ = 1 and the spectral test result

${\displaystyle \nu _{2}}$	${\displaystyle \nu _{3}}$	${\displaystyle \nu _{4}}$	${\displaystyle \nu _{5}}$	${\displaystyle \nu _{6}}$	${\displaystyle \nu _{7}}$	${\displaystyle \nu _{8}}$	${\displaystyle \nu _{9}}$
23171	10	10

More precisely  . ${\displaystyle \nu _{3}={\sqrt {118}}\approx 10;\quad \nu _{4}=\ldots =\nu _{9}={\sqrt {116}}\approx 10}$

All i-tuples with i> 2 have a maximum of 1 decimal place accuracy!

literature

• Donald E. Knuth : The Art of Computer Programming. 3rd edition. 23. Printing. Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston MA et al. 2008, ISBN 978-0-201-89684-8 , pp. 93ff.

Individual evidence

1. ^ Donald E. Knuth : The Art of Computer Programming. 3rd edition. 23. Printing. Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston MA et al. 2008, ISBN 978-0-201-89684-8 , pp. 93ff.
2. ↑ RANDU on the English Wikipedia