Average equidistribution properties of compound nonlinear congruential pseudorandom numbers

Eichenauer-Herrmann, Jürgen; Larcher, Gerhard

doi:10.1090/S0025-5718-97-00802-8

Average equidistribution properties of compound nonlinear congruential pseudorandom numbers
HTML articles powered by AMS MathViewer

by Jürgen Eichenauer-Herrmann and Gerhard Larcher PDF

Math. Comp. 66 (1997), 363-372 Request permission

Abstract:

The present paper deals with the compound nonlinear congruential method for generating uniform pseudorandom numbers, which has been introduced recently. Equidistribution properties of the generated sequences over parts of the period are studied, based on the discrepancy of the corresponding point sets. Upper and lower bounds for the average value of these discrepancies are established, which are essentially best possible. These results show that the average equidistribution behavior of compound nonlinear congruential pseudorandom numbers fits well the equidistribution properties of true random numbers. The method of proof relies heavily on estimates of the average value of incomplete exponential sums.

References

Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
J. Eichenauer–Herrmann, Inversive congruential pseudorandom numbers: a tutorial, Int. Statist. Rev. 60 (1992), 167–176.
Jürgen Eichenauer-Herrmann, Equidistribution properties of nonlinear congruential pseudorandom numbers, Metrika 40 (1993), no. 6, 333–338. MR 1247135, DOI 10.1007/BF02613697
Jürgen Eichenauer-Herrmann, Compound nonlinear congruential pseudorandom numbers, Monatsh. Math. 117 (1994), no. 3-4, 213–222. MR 1279113, DOI 10.1007/BF01299703
—, Pseudorandom number generation by nonlinear methods, Int. Statist. Rev. 63 (1995), 247–255.
Jürgen Eichenauer-Herrmann, A unified approach to the analysis of compound pseudorandom numbers, Finite Fields Appl. 1 (1995), no. 1, 102–114. MR 1334628, DOI 10.1006/ffta.1995.1007
J. Eichenauer–Herrmann and G. Larcher, Average behaviour of compound nonlinear congruential pseudorandom numbers, Finite Fields and Their Appl. 2 (1996), 111–123.
J. Eichenauer–Herrmann and H. Niederreiter, On the statistical independence of nonlinear congruential pseudorandom numbers, ACM Trans. Modeling and Computer Simulation 4 (1994), 89–95.
Harald Niederreiter, Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math. 106 (1988), no. 2, 149–159. MR 968332, DOI 10.1007/BF01298835
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
—, Nonlinear methods for pseudorandom number and vector generation, Simulation and Optimization (G. Pflug and U. Dieter, eds.), Lecture Notes in Econom. and Math. Systems, vol. 374, Springer, Berlin, 1992, pp. 145–153.
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
Harald Niederreiter, Finite fields, pseudorandom numbers, and quasirandom points, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 375–394. MR 1199844