REGULARITIES IN CONGRUENTIAL RANDOM NUMBER GENERATORS
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1969
- Accession Number
- AD0689295
Entities
People
- George Marsaglia
Organizations
- Boeing