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 tex2html_wrap_inline78 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 (tex2html_wrap_inline80 or tex2html_wrap_inline82) of the differences tex2html_wrap_inline84, tex2html_wrap_inline86. 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 tex2html_wrap_inline106 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 tex2html_wrap_inline112 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 = tex2html_wrap_inline118 for sample sizes tex2html_wrap_inline129 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].




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

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

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.

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.

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

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.

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

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

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

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

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

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

Karl Entacher
Fri Jun 13 15:46:39 MET DST 1997