Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Average equidistribution and statistical independence properties of digital inversive pseudorandom numbers over parts of the period

Author: Frank Emmerich
Journal: Math. Comp. 71 (2002), 781-791
MSC (2000): Primary 65C10; Secondary 11K45
Published electronically: October 25, 2001
MathSciNet review: 1885628
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This article deals with the digital inversive method for generating uniform pseudorandom numbers. Equidistribution and statistical independence properties of the generated pseudorandom number sequences over parts of the period are studied based on the distribution of tuples of successive terms in the sequence. The main result is an upper bound for the average value of the star discrepancy of the corresponding point sets. Additionally, lower bounds for the star discrepancy are established. The method of proof relies on bounds for exponential sums.

References [Enhancements On Off] (What's this?)

  • 1. J. Eichenauer-Herrmann, Inversive congruential pseudorandom numbers: a tutorial, Internat. Statist. Rev. 60 (1992), 167-176.
  • 2. -, Pseudorandom number generation by nonlinear methods, Internat. Statist. Rev. 63 (1995), 247-255.
  • 3. Jürgen Eichenauer-Herrmann, Eva Herrmann, and Stefan Wegenkittl, A survey of quadratic and inversive congruential pseudorandom numbers, Monte Carlo and quasi-Monte Carlo methods 1996 (Salzburg), Lecture Notes in Statist., vol. 127, Springer, New York, 1998, pp. 66–97. MR 1644512, 10.1007/978-1-4612-1690-2_4
  • 4. J. Eichenauer-Herrmann and H. Niederreiter, Digital inversive pseudorandom numbers, ACM Trans. Modeling and Computer Simulation 4 (1994), 339-349.
  • 5. F. Emmerich, Pseudorandom number and vector generation by compound inversive methods, Thesis, Darmstadt, 1996.
  • 6. -, Statistical independence properties of inversive pseudorandom vectors over parts of the period, ACM Trans. Modeling and Computer Simulation 8 (1998), 140-152.
  • 7. Peter Hellekalek, General discrepancy estimates: the Walsh function system, Acta Arith. 67 (1994), no. 3, 209–218. MR 1292735
  • 8. J. Kiefer, On large deviations of the empiric D. F. of vector chance variables and a law of the iterated logarithm, Pacific J. Math. 11 (1961), 649–660. MR 0131885
  • 9. Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
  • 10. Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997
  • 11. -, Pseudorandom vector generation by the inversive method, ACM Trans. Modeling and Computer Simulation 4 (1994), 191-212.
  • 12. Harald Niederreiter, New developments in uniform pseudorandom number and vector generation, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lecture Notes in Statist., vol. 106, Springer, New York, 1995, pp. 87–120. MR 1445782, 10.1007/978-1-4612-2552-2_5
  • 13. Harald Niederreiter, Improved bounds in the multiple-recursive matrix method for pseudorandom number and vector generation, Finite Fields Appl. 2 (1996), no. 3, 225–240. MR 1398075, 10.1006/ffta.1996.0015
  • 14. H. Niederreiter and I. E. Shparlinski, On the distribution of pseudorandom numbers and vectors generated by inversive methods, Appl. Algebra Engrg. Comm. Comput. 10 (2000), 189-202.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65C10, 11K45

Retrieve articles in all journals with MSC (2000): 65C10, 11K45

Additional Information

Frank Emmerich
Affiliation: T-Nova Deutsche Telekom Innovationsgesellschaft, Technologiezentrum, Am Kavalleriesand 3, D-64295 Darmstadt, F. R. Germany

Keywords: Uniform pseudorandom numbers, digital inversive method, average equidistribution behaviour, average statistical independence properties, star discrepancy, exponential sums
Received by editor(s): November 10, 1999
Received by editor(s) in revised form: July 12, 2000
Published electronically: October 25, 2001
Article copyright: © Copyright 2001 American Mathematical Society