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 R. R. Coveyou, “Random number generation is too important to be left to chance,” Studies in Appl. Math., v. 3, 1969, pp. 70-111. R. Dedekind, “Erläuterungen zu den Fragmenten XXVIII,” in Riemanns Gesammelten Werken, Leipzig, 1892, pp. 466-478.
- 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 U. Dieter, “Autokorrelation multiplikativ-erzeugter Pseudo-Zufallszahlen,” Operations Research-Verfahren, v. 6, 1969, pp. 69-85.
- 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 U. Dieter, “Pseudo-random numbers: Permutations of triplets.” (To appear.) U. Dieter, “Simple proofs for some identities for generalized Dedekind sums.” (To appear.)
- 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 M. Greenberger, “Method in randomness,” Comm. ACM, v. 8, 1965, pp. 177-179.
- 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 H. Rademacher, “Zur Theorie der Modulfunktionen,” J. Reine Angew. Math., v. 167, 1932, pp. 312-336.
- 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
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Math. Comp. 25 (1971), 855-883
- MSC: Primary 60E05
- DOI: https://doi.org/10.1090/S0025-5718-1971-0298727-8
- MathSciNet review: 0298727