×

Statistical independence properties of pseudorandom vectors produced by matrix generators. (English) Zbl 0708.65007

For a short general discussion of the generators see p. 87 of [P. L’Écuyer: Random numbers for simulation, CACM 33, 86 ff (1990)] who also explains discrepancy (informally) and its importance.
In the present publication the tests for one-dimensional generators are generalised to k-vectors of random numbers from multiplicative congruential generators with constant square matrix factor and a common prime p as modulus.
The analysis requires recourse to some number theory in order to get results characteristic of the powers of a matrix over the finite field of order p.
Upper and lower bounds for the discrepancy are derived, the latter one by introducing a condensing “figure of merit” analog to the one- dimensional case. With these results matrices as factors with good statistical behaviour may be constructed for any dimension depending on the “lag”s (length of series of vectors considered for discrepancy, i.e. for mutually independent behaviour).
Reviewer: K.G.Brokate

MSC:

65C10 Random number generation in numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afflerbach, L.; Grothe, H., The lattice structure of pseudo-random vectors generated by matrix generators, J. Comput. Appl. Math., 23, 1, 127-131 (1988) · Zbl 0658.65006
[2] Afflerbach, L.; Weilbächer, R., The exact determination of rectangle discrepancy for linear congruential pseudo-random numbers, Math. Comp., 53, 343-354 (1989) · Zbl 0672.65008
[3] Cochrane, T., On a trigonometric inequality of Vinogradov, J. Number Theory, 27, 9-16 (1987) · Zbl 0629.10030
[4] Dieter, U., Pseudo-random numbers: The exact distribution of pairs, Math. Comp., 25, 855-883 (1971) · Zbl 0257.65010
[5] Eichenauer, J.; Grothe, H.; Lehn, J., Marsaglia’s lattice test and non-linear congruential pseudo random number generators, Metrika, 35, 241-250 (1988) · Zbl 0653.65006
[6] Eichenauer, J.; Lehn, J., A non-linear congruential pseudo random number generator, Statist. Papers, 27, 315-326 (1986) · Zbl 0607.65001
[7] Eichenauer, J.; Lehn, J.; Topuzoǧlu, A., A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp., 51, 757-759 (1988) · Zbl 0701.65008
[8] Grothe, J., Matrixgeneratoren zur Erzeugung gleichverteilter Zufallsvektoren, (Afflerbach, L.; Lehn, J., Kolloquium über Zufallszahlen und Simulationen (1986), Teubner: Teubner Stuttgart), 29-34
[9] Grothe, H., Matrix generators for pseudo-random vector generation, Statist. Papers, 28, 233-238 (1987) · Zbl 0629.65006
[10] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1960), Clarendon Press: Clarendon Press Oxford · Zbl 0086.25803
[11] Lidl, R.; Niederreiter, H., Finite Fields (1983), Addison-Wesley: Addison-Wesley Reading, MA
[12] Niederreiter, H., Pseudo-random numbers and optimal coefficients, Adv. in Math., 26, 99-181 (1977) · Zbl 0366.65004
[13] Niederreiter, H., Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc., 84, 957-1041 (1978) · Zbl 0404.65003
[14] Niederreiter, H., Statistical tests for Tausworthe pseudo-random numbers, (Grossmann, W.; Pflug, G. C.; Wertz, W., Probability and Statistical Inference (1982), Reidel: Reidel Dordrecht), 265-274 · Zbl 0479.65005
[15] Niederreiter, H., The performance of \(k\)-step pseudorandom number generators under the uniformity test, SIAM J. Sci. Statist. Comput., 5, 798-810 (1984) · Zbl 0557.65005
[16] Niederreiter, H., The serial test for pseudo-random numbers generated by the linear congruential methods, Numer. Math., 46, 51-68 (1985) · Zbl 0541.65004
[17] Niederreiter, H., A pseudorandom vector generator based on finite field arithmetic, Math. Japon., 31, 759-774 (1986) · Zbl 0619.65002
[18] Niederreiter, H., Pseudozufallszahlen und die Theorie der Gleichverteilung, Sitzungsber. Österr. Akad. Wiss. Math.-Natur. Kl. Abt. II, 195, 109-138 (1986) · Zbl 0616.10040
[19] Niederreiter, H., A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM J. Sci. Statist. Comput., 8, 1035-1051 (1987) · Zbl 0634.65003
[20] Niederreiter, H., Point sets and sequences with small discrepancy, Monatsh. Math., 104, 273-337 (1987) · Zbl 0626.10045
[21] Niederreiter, H., The serial test for digital \(k\)-step pseudorandom numbers, Math. J. Okayama Univ., 30, 93-119 (1988) · Zbl 0666.65003
[22] Niederreiter, H., Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math., 106, 149-159 (1988) · Zbl 0652.65007
[23] Niederreiter, H., The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp., 52, 135-144 (1989) · Zbl 0657.65007
[24] Reiner, I., On the number of matrices with given characteristic polynomial, Illinois J. Math., 5, 324-329 (1961) · Zbl 0098.01402
[25] Tahmi, E. A.D. E., Contribution aux générateurs de vecteurs pseudo-aléatoires, (Thèse (1982), Univ. Sci. Techn. H: Univ. Sci. Techn. H Boumedienne, Algiers)
[26] Tezuka, S., On the discrepancy of GFSR pseudorandom numbers, J. Assoc. Comput. Mach., 34, 939-949 (1987) · Zbl 0633.65005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.