Inversive congruential pseudorandom numbers: distribution of triples
HTML articles powered by AMS MathViewer
- by Jürgen Eichenauer-Herrmann and Harald Niederreiter PDF
- Math. Comp. 66 (1997), 1629-1644 Request permission
Abstract:
This paper deals with the inversive congruential method with power of two modulus $m$ for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that, on the average over the parameters in the inversive congruential method, the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude between $m^{-1/2}$ and $m^{-1/2}(\log m)^3$. The method of proof relies on a detailed discussion of the properties of certain exponential sums.References
- Jürgen Eichenauer, Jürgen Lehn, and Alev Topuzoğlu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51 (1988), no. 184, 757–759. MR 958641, DOI 10.1090/S0025-5718-1988-0958641-1
- J. Eichenauer–Herrmann, Inversive congruential pseudorandom numbers: a tutorial, Internat. Statist. Rev. 60 (1992), 167–176.
- —, Pseudorandom number generation by nonlinear methods, Internat. Statist. Rev. 63 (1995), 247–255.
- —, Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus, Metrika 44 (1996), 199–205.
- —, Improved upper bounds for the discrepancy of pairs of inversive congruential pseudorandom numbers with power of two modulus, Preprint.
- Jürgen Eichenauer-Herrmann and Harald Niederreiter, On the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. 34 (1991), no. 2, 243–249. MR 1107870, DOI 10.1016/0377-0427(91)90046-M
- Jürgen Eichenauer-Herrmann and Harald Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus, Math. Comp. 58 (1992), no. 198, 775–779. MR 1122066, DOI 10.1090/S0025-5718-1992-1122066-X
- Jürgen Eichenauer-Herrmann and Harald Niederreiter, Kloosterman-type sums and the discrepancy of nonoverlapping pairs of inversive congruential pseudorandom numbers, Acta Arith. 65 (1993), no. 2, 185–194. MR 1240124, DOI 10.4064/aa-65-2-185-194
- —, Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus, Monatsh. Math. (to appear).
- 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 131885, DOI 10.2140/pjm.1961.11.649
- Pierre L’Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77–120. Simulation and modeling. MR 1310607, DOI 10.1007/BF02136827
- 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
- Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 476679, DOI 10.1016/0001-8708(77)90028-7
- Harald Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), no. 185, 135–144. MR 971407, DOI 10.1090/S0025-5718-1989-0971407-2
- Harald Niederreiter, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), no. 1-4, 323–345. Stochastic programming, Part II (Ann Arbor, MI, 1989). MR 1118905, DOI 10.1007/BF02204856
- 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, DOI 10.1137/1.9781611970081
- —, New developments in uniform pseudorandom number and vector generation, Monte Carlo and Quasi–Monte Carlo Methods in Scientific Computing (H. Niederreiter and P.J.-S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, Springer, New York, 1995, pp. 87–120.
Additional Information
- Jürgen Eichenauer-Herrmann
- Affiliation: Fachbereich Mathematik, Technische Hochschule, Schloßgartenstraße 7, D–64289 Darmstadt, Germany
- Harald Niederreiter
- Affiliation: Institut für Informationsverarbeitung, Österr. Akademie der Wissenschaften, Sonnenfelsgasse 19, A–1010 Wien, Austria
- Email: niederreiter@oeaw.ac.at
- Received by editor(s): April 12, 1996
- Received by editor(s) in revised form: August 23, 1996
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 1629-1644
- MSC (1991): Primary 65C10; Secondary 11K45
- DOI: https://doi.org/10.1090/S0025-5718-97-00867-3
- MathSciNet review: 1423072