OVERLAPPING SERIAL TEST
Interested in the meaning of the following graphic ?
This is what we call a 'Load Test' for pseudorandom number generators: as the sample size increases, spectacular breakdowns (i.e. dark colored bars) of several generators can be observered. This page contains the basic definitions and procedures which are necessary to obtain such results.
The overlapping serial test
uses overlapping s-tuples of integers defined
by the first 4 leading bits of every pseudorandom number.
For a sample size n the test statistic is defined as follows:
let 
, 
and put
, where
means addition 
. Denote 
by 
.
For each 
let 
the number of occurences of the tuple t in the sample.
The overlapping serial test statistic [2, 5]
for these counters c is defined by
where 
denotes the expectation with respect to the null hypothesis
iid., that is 
. The second sum
is omitted in the case s=1.
This statistic is asymptotically distributed
with 
degrees of freedom.
Our 'Load Test' combines the overlapping serial test with a two-sided
Kolmogorov-Smirnov test.
We calculate K=32 samples of the test statistic
for 
,
where 
depends
on the pseudorandom numbers 
.
The resulting values are normalized by computing approximate
lower-tail probabilities
,
where 
,
see e.g. [4, p. 216,] for algorithmic details.
According to the null hypotheses, 
should approximately be uniform
on [0,1]. This is tested with the two-sided Kolmogorov-Smirnov test.
In
Stefan Wegenkittl's
master thesis
you can find
3-D bar plots
which summarize the behaviour of linear and
inversive
congruential generators
for sample sizes 
and dimensions
. Each bar reports the minimum between 2 and the
value of the KS test statistic 
.
The rejection area of the KS test with a level of significance of 0.01
is approximated by 
for
K =32, see e.g. [3, p. 183,].
Black bars indicate rejection. The grey level of the other bars varies
between white if the KS-test statistic is zero and deep grey near the
critical value.
The level-one test results 
are also reported there
in form of Grey-scale plots.
The 32 values are arranged in a rectangle containing 4 rows and 8 columns.
A black subrectangle denotes a high lower-tail probability indicating
that some differences 
are untypically large.
White subrectangles on the other hand denote almost equally filled
up counters, i.e., untypically small values of the overlapping
serial test statistic. The plots are organized in such a way
that again a single figure contains results in all analyzed dimensions and
sample sizes.
Further results of this kind for many linear and inversive congruential generators, a more detailed description of the 'Load Test' and an 'Ultimative Load Test' are given in the pLab-technical reports [6, 1].
The overlapping serial test has been implemented using 'C++'. The tests have been carried out using the pLab-package.
- 1
-
K. Entacher and S. Wegenkittl.
The PLAB Picturebook: Load Tests and Ultimate Load
Tests, Part II: Subsequences.
Report no. 2, PLAB - reports, University of Salzburg, 1997.
Abstract and postscript file available.
- 2
-
I. J. Good.
The serial test for sampling numbers and other tests for randomness.
Proc. Cambridge Philosophical Society, 49:276-284, 1953.
- 3
-
J. Hartung, B. Elpelt, and K. H. Klösener.
Statistik.
R. Oldenburg, Munich, 9th edition, 1993.
- 4
-
W. H. et al Press.
Numerical Recipes in C.
The Art of Scientific Computing. Press Syndicate of the University of
Cambridge, Cambridge, 1992.
- 5
-
S. Wegenkittl.
Empirical testing of pseudorandom number generators.
Master's thesis, University of Salzburg, Austria, 1995.
Abstract and html version available, postscript file on request.
- 6
-
S. Wegenkittl.
The PLAB Picturebook: Load Tests and Ultimate Load
Tests, Part I.
Report no. 1, PLAB - reports, University of Salzburg, 1997.
Abstract and postscript file available.