An Asymptotically Random Tausworthe Sequence

ABSTRACT

The theoretical limitations on the orders of equidistribution attainable by Tausworthe sequences are derived from first principles and are stated in the form of a criterion to be achieved. A second criterion, extending these limitations to multidimensional uniformity, is also defined. A sequence possessing both properties is said to be asymptotically random as no other sequence of the same period could be more random in these respects. An algorithm is presented which, for any Tausworthe sequence based on a primitive trinomial over GF(2), establishes how closely or otherwise the conditions necessary for the criteria are achieved. Given that the necessary conditions are achieved, the conditions sufficient for the first criterion are derived from Galois theory and always apply. For the second criterion, however, the period must be prime. An asymptotically random 23-bit number sequence of astronomic period, 2607 - 1, is presented. An initialization program is required to provide 607 starting values, after which the sequence can be generated with a three-term recurrence of the Fibonacci type. In addition to possessing the theoretically demonstrable randomness properties associated with Tausworthe sequences, the sequence possesses equidistribution and multidimensional uniformity properties vastly in excess of anything that has yet been shown for conventional congruentially generated sequences. It is shown that, for samples of a size it is practicable to generate, there can exist no purely empirical test of the sequence as it stands capable of distinguishing between it and an ∞-distributed sequence. Bounds for local nonrandomness in respect of runs above (below) the mean and runs of equal numbers are established theoretically.The claimed randomness properties do not necessarily extend to subsequences, though it is not yet known which particular subsequences are at fault. Accordingly, the sequence is at present suggested only for simulations with no fixed dimensionality requirements.

REFERENCES

• 1: TAUSWORTHE, R. C Random numbers generated by hnear recurrence modulo two Math. Comput. 19, 90 (1965), 201-209
• 2: J. P. R. Tootill , W. D. Robinson , A. G. Adams, The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators, Journal of the ACM (JACM), v.18 n.3, p.381-399, July 1971 [doi>10.1145/321650.321655]
• 3: R. R. Coveyou , R. D. Macpherson, Fourier Analysis of Uniform Random Number Generators, Journal of the ACM (JACM), v.14 n.1, p.100-119, Jan. 1967 [doi>10.1145/321371.321379]
• 4: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 5: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 6: ZIERLER, N.Pmmltlve trlnomlals whose degree is a Mersenne exponent Inform. Contr. 15, 1 (1969), 67-69
• 7: Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
• 8: MARTIN-LOF, P The defimtlon of random sequences Inform. Contr 9, 6 (1966), 602-619.
• 9: MARTIN-LOF, P. Algomthms and randomness. Rev Internat Statzst instlt 37, 3 (1969), 265-272

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

General Terms:
Algorithms, Design, Measurement, Performance, Theory