The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators
J. P. R. Tootill, Walter D. Robinson, A. G. Adams · Journal of the ACM · 1971
Any Tausworthe generator based upon a primitive trinomial over GF(2), xp + xq + 1, can be represented as a simple linear recurrence in GF(2P).For a generator producing a sequence of p-bit pseudo-random numbers, (p, 2p -1) = 1, which is guaranteed by Tausworthe's theory to be 1-distributed, the recurrence may reveal combinatorial relationships implying a poor runs up-and-down performance.This occurs when q is small, too near p/2, or nearly equal to p. Elementary but tedious combinatorics then enable the frequencies of runs of given length, either up or down, to be predicted quantitatively.Empirical studies strikingly confirm these predictions.A generator producing/-bit numbers, (1, 2p -1) = 1, according to Tausworthe's theory, yields a sequence of m-tuples uniformly distributed in m = [p/l] dimensions.We, however, additionally require that (m, 2 p -1) = 1.If m > 4, a simple argument shows that satisfactory runs up-and-down behavior is to be expected for runs of length not exceeding m -3.Empirical evidence confirms this expectation.Satisfactory performance in an m-dimensional simulation also reqi.liressatisfactory statistical properties along each dimension, i.e. it needs, among other things, good runs up-and-down performance for the subsequence obtained by taking every ruth number generated.Combinatorial argmnents similar to those used for the p-bit generators can be applied to this subsequence and, for the defective generators studied, lead to quantitative predictions of the frequencies of runs of any length.These predictions too • are in remarkable accord with empirical studies.A combinatorial argument shows that this problem can be overcome as m-dimensional uniformity of distribution can be imposed on the subsequence along dimensions by setting 1 = q.A recommended generator is based upon either x p + xq ~ 1 or xp -{-xp-~ ~ 1, q < p/2, m = [p/q], (qm,.2, -1) = 1, and is designed to produce a sequence of q-bit numbers.It has predictably good run properties, provided neither q nor m is too small.Empirical studies confirm greatly improved run properties for such a generator.