Accession Number : AD0689295


Title :   REGULARITIES IN CONGRUENTIAL RANDOM NUMBER GENERATORS


Corporate Author : BOEING SCIENTIFIC RESEARCH LABS SEATTLE WA MATHEMATICS RESEARCH LAB


Personal Author(s) : Marsaglia, George


Full Text : http://www.dtic.mil/get-tr-doc/pdf?AD= AD0689295


Report Date : May 1969


Pagination or Media Count : 8


Abstract : The paper suggests that points in n-space produced by congruential random number generators are too regular for general Monte Carlo use. Regularity was established previously for multiplicative congruential generators by showing that all the points fall in sets of relatively few parallel hyperplanes. The existence of many containing sets of parallel hyperplanes was easily established, but proof that the number of hyperplanes was small required a result of Minkowski from the geometry of numbers--a symmetric, convex set of volume 2 to the nth power must contain at least two points with integral coordinates. The present paper takes a different approach to establishing the course lattice structure of congruential generators. It gives a simple, selfcontained proof that points in n-space produced by the general congruential generator r sub (i+1) is identically equal to a(r sub i) + b mod m must fall on a lattice with unit-cell volume at least m to the power (n-1). There is no restriction on a or b; this means that all congruential random number generators must be considered unsatisfactory in terms of lattices containing the points they produce, for a good generator of random integers should have an n-lattice with unit-cell volume 1.


Descriptors :   *NUMERICAL ANALYSIS , MONTE CARLO METHOD , NUMBER THEORY , RANDOM VARIABLES , SET THEORY , THEOREMS


Subject Categories : Theoretical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE