RUN TESTS

The analysis of runs within a sequence is applied in statistics in many ways (for examples see [7, Section II.5 (b),], [1]). The term run may in general be explained as a succession of items of the same class. Many concepts to analyze runs in a series of data have been studied. The main concepts are based on (i) the analysis of the total number of runs of a given class (see [9, 10]) and (ii) examinations about the appearance of long runs (see [7, Chapter XIII,], [8, 11] ).

For example, consider a sequence of bits. Binary runs are for example arbitrary repetitive patterns within the sequence. Let be a sequence of pairwise different numbers like an output of a pseudorandom number generator. A sequence of bits occurs if one considers the signs ( or ) of the differences , . For example X = (5,4,1,7,2,3,6) yields S = (0,0,1,0,1,1). This concept is used in [10, 11]. A subsequence of length l consisting of only 1 is called a "run up" of length l (this indicates a increasing subsequence of length l+1 within the sequence X). The opposite case, a subsequence consisting of only 0 is called a ``run down''. In the latter papers, several statistics based on this run definition are treated for both areas (i) and (ii). These considerations form the basis of a run-test proposed by Knuth [9] in order to test pseudorandom numbers. Knuth's run-test is one of the most common tests used for examining PRNs. An asymptotically chi-squared distributed test statistic based on the number of runs with length l = 1,2,3,4,5 and is given in Knuth [9, 6].

Consider a fixed sample size n. The run-test implemented in pLab calculates Knuth`s test statistic m times. To these "asymptotically chi-squared" values a Kolmogorov-Smirnov-test is applied (for details see [6]).

The graphics below show typically behavior of this test if "good" and "flawed" linear congruential generators with moduli are used. The lines in the graphics indicate the rejection area of the Kolmogorov-Smirnov statistic with level of significance 0.05 and 0.01 . The first graphics below shows the results obtained from Super-Duper = for sample sizes and m = 100. The afterimages are obtained from the subsequences with step sizes 99, 565 and 739 generated from Super-Duper. Note that these subsequences are produced by similar linear congruential generators with multiplier 1031357269, 3280877789 and 3028669781. Further results for linear and inversive congruential generators are given in [2, 6]. For subsequence behavior of well known linear congruential generators see [3, 4, 5].

References

1

A.J. Ducan. Quality Control and Industrial Statistics. Richard D. IRWIN, INC., 4 edition, 1974.

2

K. Entacher. Selected random number generators in run tests. Preprint, Mathematics Institute, University of Salzburg.

3

K. Entacher. A collection of selected pseudorandom number generators with linear structures. Technical report, Dep. of Mathematics University of Salzburg, 1997.

Abstract and postscript file available.

4

K. Entacher. The PLAB Picturebook: Part III, Bad Subsequences of LCGs - The Results. Report no. 06, PLAB - reports, University of Salzburg, 1997.

Abstract and postscript file available.

5

K. Entacher. Bad subsequences of well-known linear congruential pseudorandom number generators. ACM Tomacs, to appear.

6

K. Entacher and H. Leeb. Inversive pseudorandom number generators: empirical results. In Proceedings of the Conference Parallel Numerics 95, Sorrento, Italy, September 27-29, 1995, pages 15-27, 1995. available in postscript.

7

W. Feller. An Introduction to Probability Theory and its Applications, volume I. John Wiley & Sons, Inc., third edition, 1968.

8

L.J. Guibas and A.M. Odlyzko. Long Repetive Patterns in Random Sequences. Z. Wahrscheinlichkeitstheorie, 53 :241-262, 1980.

9

D.E. Knuth. The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 2nd edition, 1981.

10

H. Levene and J. Wolfowitz. The covariance matrix of runs up and down. Annals Math. Stat., 15 :59-69, 1944.

11

J. Wolfowitz. Asymptotic distribution of runs up and down. Annals Math. Stat., 15 :163-165, 1944.

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