Pseudo-random numbers. The exact distribution of pairs

Dieter, U.

doi:10.1090/S0025-5718-1971-0298727-8

Pseudo-random numbers. The exact distribution of pairs
HTML articles powered by AMS MathViewer

by U. Dieter PDF

Math. Comp. 25 (1971), 855-883 Request permission

Abstract:

Pseudo-random numbers are usually generated by linear congruential methods. Starting with an integer ${y_0}$, a sequence $\{ {y_i}\}$ is constructed by ${y_{i + 1}} \equiv a{y_i} + r \pmod m, m, a, r$ being integers. The derived fractions ${x_i} \equiv {y_i}/m$ are taken as samples from the uniform distribution on [0, 1). In this paper it is shown that the joint probability distribution of pairs ${x_i},{x_{i + s}}$ can be calculated exactly. Explicit calculations show that this distribution is surprisingly near to the uniform distribution for most ’reasonable’ generators. The best approximation to the uniform distribution on the unit-square is achieved if the continued fraction for ${a^s}$ and m (or ${a^s}$ and m/f) is long.

References

J. H. Ahrens, U. Dieter, and A. Grube, Pseudo-random numbers. A new proposal for the choice of multiplicators, Computing (Arch. Elektron. Rechnen) 6 (1970), 121–138 (English, with German summary). MR 279958, DOI 10.1007/bf02241740
R. R. Coveyou, Serial correlation in the generation of pseudo-random numbers, J. Assoc. Comput. Mach. 7 (1960), 72–74. MR 117869, DOI 10.1145/321008.321018
R. R. Coveyou and R. D. Macpherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100–119. MR 221727, DOI 10.1145/321371.321379

Studies in Appl. Math.

in Riemanns Gesammelten Werken, Leipzig

Ulrich Dieter, Das Verhalten der Kleinschen Funktionen $\log \sigma _{g,h}(\omega _{1}, \omega _{2})$ gegenüber Modultransformationen und verallgemeinerte Dedekindsche Summen, J. Reine Angew. Math. 201 (1959), 37–70 (German). MR 104644, DOI 10.1515/crll.1959.201.37

Operations Research-Verfahren

U. Dieter and J. Ahrens, An exact determination of serial correlations of pseudorandom numbers, Numer. Math. 17 (1971), 101–123. MR 286245, DOI 10.1007/BF01406000
Martin Greenberger, An a priori determination of serial correlation in computer generated random numbers, Math. Comp. 15 (1961), 383–389. MR 144489, DOI 10.1090/S0025-5718-1961-0144489-8

Comm. ACM

John H. Halton, A retrospective and prospective survey of the Monte Carlo method, SIAM Rev. 12 (1970), 1–63. MR 258231, DOI 10.1137/1012001
T. E. Hull and A. R. Dobell, Random number generators, SIAM Rev. 4 (1962), 230–254. MR 148202, DOI 10.1137/1004061
David L. Jagerman, The autocorrelation and joint distribution functions of the sequences $\{{a\over m}j^2\}$, $\{{a\over m}(j+\tau )^2\}$, Math. Comp. 18 (1964), 211–232. MR 177499, DOI 10.1090/S0025-5718-1964-0177499-8
Birger Jansson, Autocorrelations between pseudo-random numbers, Nordisk Tidskr. Informationsbehandling (BIT) 4 (1964), 6–27. MR 165654, DOI 10.1007/bf01939521
Birger Jansson, Random number generators, Almqvist & Wiksell, Stockholm, 1966. MR 0224253
M. L. Juncosa, Random number generation on the BRL high-speed computing machines, Ballistic Research Laboratories, Aberdeen Proving Ground, Md., 1953. Rep. No. 855,. MR 0059617
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
D. H. Lehmer, Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 1949, Harvard University Press, Cambridge, Mass., 1951, pp. 141–146. MR 0044899
M. Donald MacLaren and George Marsaglia, Uniform random number generators, J. Assoc. Comput. Mach. 12 (1965), 83–89. MR 170449, DOI 10.1145/321250.321257
George Marsaglia, Random variables and computers, Trans. Third Prague Conf. Information Theory, Statist. Decision Functions, Random Processes (Liblice, 1962) Publ. House Czech. Acad. Sci., Prague, 1964, pp. 499–512. MR 0164424
George Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 235695, DOI 10.1073/pnas.61.1.25
George Marsaglia, Regularities in congruential random number generators, Numer. Math. 16 (1970/71), 8–10. MR 273775, DOI 10.1007/BF02162401
C. Meyer, Über einige Anwendungen Dedekindscher Summen, J. Reine Angew. Math. 198 (1957), 143–203 (German). MR 104643, DOI 10.1515/crll.1957.198.143
C. Meyer, Bemerkungen zu den allgemeinen Dedekindschen Summen, J. Reine Angew. Math. 205 (1960/61), 186–196 (German). MR 124310, DOI 10.1515/crll.1960.205.186

J. Reine Angew. Math.

H. Rademacher, Some remarks on certain generalized Dedekind sums, Acta Arith. 9 (1964), 97–105. MR 163873, DOI 10.4064/aa-9-1-97-105
A. Rotenberg, A new pseudo-random number generator, J. Assoc. Comput. Mach. 7 (1960), 75–77. MR 117868, DOI 10.1145/321008.321019
Olga Taussky and John Todd, Generation and testing of pseudo-random numbers, Symposium on Monte Carlo methods, University of Florida, 1954, John Wiley and Sons, Inc., New York; Chapman and Hall, Ltd., London, 1956, pp. 15–28. MR 0080382
Peter H. Verdier, Relations within sequences of congruential pseudo-random numbers, J. Res. Nat. Bur. Standards Sect. B 73B (1969), 41–44. MR 239724, DOI 10.6028/jres.073B.005