Statistical independence of a new class of inversive congruential pseudorandom numbers

Eichenauer-Herrmann, Jürgen

doi:10.1090/S0025-5718-1993-1159168-9

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

Statistical independence of a new class of inversive congruential pseudorandom numbers

Author: Jürgen Eichenauer-Herrmann
Journal: Math. Comp. 60 (1993), 375-384
MSC: Primary 65C10; Secondary 11K45
MathSciNet review: 1159168
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Linear congruential pseudorandom numbers show several undesirable regularities which can render them useless for certain stochastic simulations. This was the motivation for important recent developments in nonlinear congruential methods for generating uniform pseudorandom numbers. It is particularly promising to achieve nonlinearity by employing the operation of multiplicative inversion with respect to a prime modulus. In the present paper a new class of such inversive congruential generators is introduced and analyzed. It is shown that they have excellent statistical independence properties and model true random numbers very closely. The methods of proof rely heavily on Weil-Stepanov bounds for rational exponential sums.

[1] Itshak Borosh and Harald Niederreiter, Optimal multipliers for pseudorandom number generation by the linear congruential method, BIT 23 (1983), no. 1, 65–74. MR 689604 (84e:65012), http://dx.doi.org/10.1007/BF01937326
[2] J. Eichenauer, H. Grothe, and J. Lehn, Marsaglia's lattice test and non-linear congruential pseudo random number generators, Metrika 35 (1988), 241-250.
[3] Jürgen Eichenauer, Holger Grothe, Jürgen Lehn, and Alev Topuzoğlu, A multiple recursive nonlinear congruential pseudo random number generator, Manuscripta Math. 59 (1987), no. 3, 331–346. MR 909849 (89f:65008), http://dx.doi.org/10.1007/BF01174798
[4] Jürgen Eichenauer and Jürgen Lehn, A nonlinear congruential pseudorandom number generator, Statist. Hefte 27 (1986), no. 4, 315–326. MR 877295 (88i:65014)
[5] Jürgen Eichenauer and Jürgen Lehn, On the structure of quadratic congruential sequences, Manuscripta Math. 58 (1987), no. 1-2, 129–140. MR 884989 (88h:65019), http://dx.doi.org/10.1007/BF01169087
[6] 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 (89i:65007), http://dx.doi.org/10.1090/S0025-5718-1988-0958641-1
[7] Jürgen Eichenauer and Harald Niederreiter, On Marsaglia’s lattice test for pseudorandom numbers, Manuscripta Math. 62 (1988), no. 2, 245–248. MR 963009 (90c:65011), http://dx.doi.org/10.1007/BF01278982
[8] Jürgen Eichenauer-Herrmann, A remark on the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. 43 (1992), no. 3, 383–387. MR 1193815 (93i:65010), http://dx.doi.org/10.1016/0377-0427(92)90023-Q
[9] Jürgen Eichenauer-Herrmann, Construction of inversive congruential pseudorandom number generators with maximal period length, J. Comput. Appl. Math. 40 (1992), no. 3, 345–349. MR 1170913 (93d:65010), http://dx.doi.org/10.1016/0377-0427(92)90190-9
[10] -, Inversive congruential pseudorandom numbers: a tutorial, Internat. Statist. Rev. 60 (1992), 167-176.
[11] Jürgen Eichenauer-Herrmann, Inversive congruential pseudorandom numbers avoid the planes, Math. Comp. 56 (1991), no. 193, 297–301. MR 1052092 (91k:65021), http://dx.doi.org/10.1090/S0025-5718-1991-1052092-X
[12] J. Eichenauer-Herrmann, On the autocorrelation structure of inversive congruential pseudorandom number sequences, Statist. Papers 33 (1992), no. 3, 261–268. MR 1186171 (94b:65016), http://dx.doi.org/10.1007/BF02925329
[13] Jürgen Eichenauer-Herrmann, On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus, Manuscripta Math. 71 (1991), no. 2, 153–161. MR 1101266 (92c:11081), http://dx.doi.org/10.1007/BF02568399
[14] J. Eichenauer-Herrmann and H. Grothe, A new inversive congruential pseudorandom number generator with power of two modulus, ACM Trans. Modeling Computer Simulation (to appear)
[15] J. Eichenauer-Herrmann, H. Grothe, H. Niederreiter, and A. Topuzoğlu, On the lattice structure of a nonlinear generator with modulus 2^{𝛼}, J. Comput. Appl. Math. 31 (1990), no. 1, 81–85. Random numbers and simulation (Lambrecht, 1988). MR 1068151 (91j:65012), http://dx.doi.org/10.1016/0377-0427(90)90338-Z
[16] 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 (92i:65018), http://dx.doi.org/10.1090/S0025-5718-1992-1122066-X
[17] 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 (92c:65010), http://dx.doi.org/10.1016/0377-0427(91)90046-M
[18] J. Eichenauer-Herrmann and A. Topuzoğlu, On the period length of congruential pseudorandom number sequences generated by inversions, J. Comput. Appl. Math. 31 (1990), no. 1, 87–96. Random numbers and simulation (Lambrecht, 1988). MR 1068152 (92e:65008), http://dx.doi.org/10.1016/0377-0427(90)90339-2
[19] George S. Fishman, Multiplicative congruential random number generators with modulus 2^{𝛽}: an exhaustive analysis for 𝛽=32 and a partial analysis for 𝛽=48, Math. Comp. 54 (1990), no. 189, 331–344. MR 993929 (91e:65012), http://dx.doi.org/10.1090/S0025-5718-1990-0993929-9
[20] George S. Fishman and Louis R. Moore III, An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1, SIAM J. Sci. Statist. Comput. 7 (1986), no. 1, 24–45. MR 819455 (87g:65010a), http://dx.doi.org/10.1137/0907002
[21] F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), no. 3, 329–344. MR 1076267 (91i:65013), http://dx.doi.org/10.1016/0010-4655(90)90032-V
[22] 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 (24 #A1732)
[23] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878 (83i:68003)
[24] 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 (86c:11106)
[25] George Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 0235695 (38 #3998)
[26] George Marsaglia, Regularities in congruential random number generators, Numer. Math. 16 (1970/1971), 8–10. MR 0273775 (42 #8651)
[27] Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 0476679 (57 #16238)
[28] Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447 (80d:65016), http://dx.doi.org/10.1090/S0002-9904-1978-14532-7
[29] Harald Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46 (1985), no. 1, 51–68. MR 777824 (86i:65010), http://dx.doi.org/10.1007/BF01400255
[30] H. Niederreiter, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988), no. 6, 321–328. MR 980847 (90e:11119), http://dx.doi.org/10.1007/BF02613320
[31] Harald Niederreiter, Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math. 106 (1988), no. 2, 149–159. MR 968332 (89j:11079), http://dx.doi.org/10.1007/BF01298835
[32] Harald Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), no. 185, 135–144. MR 971407 (90e:65008), http://dx.doi.org/10.1090/S0025-5718-1989-0971407-2
[33] Harald Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Math. Comp. 55 (1990), no. 191, 277–287. MR 1023766 (91e:65016), http://dx.doi.org/10.1090/S0025-5718-1990-1023766-0
[34] 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 (92h:65010), http://dx.doi.org/10.1007/BF02204856
[35] -, Nonlinear methods for pseudorandom number and vector generation, Simulation and Optimization (G. Pflug and U. Dieter, eds.), Lecture Notes in Economics and Math. Systems, vol. 374, Springer, Berlin, 1992, pp. 145-153.
[36] B. D. Ripley, Computer generation of random variables: a tutorial, Internat. Statist. Rev. 51 (1983), no. 3, 301–319 (English, with French summary). MR 731146 (85a:65016), http://dx.doi.org/10.2307/1402590
[37] B. D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London Ser. A 389 (1983), no. 1796, 197–204. MR 719645 (85i:65010)
[38] S. A. Stepanov, The estimation of rational trigonometric sums with prime denominator, Trudy Mat. Inst. Steklov. 112 (1971), 346–371, 389. (errata insert) (Russian). Collection of articles dedicated to Academician Ivan Matveevič Vinogradov on his eightieth birthday. I. MR 0318158 (47 #6706)
[39] André Weil, On some exponential sums, Proc. Nat. Acad. Sci. U. S. A. 34 (1948), 204–207. MR 0027006 (10,234e)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|