### - Art Gallery -

In computational number theory, Marsaglia's theorem connects modular arithmetic and analytic geometry to describe the flaws with the pseudorandom numbers resulting from a linear congruential generator. As a direct consequence, it is now widely considered that linear congruential generators are weak for the purpose of generating random numbers. Particularly, it is inadvisable to use them for simulations with the Monte Carlo method or in cryptographic settings, such as issuing a public key certificate, unless specific numerical requirements are satisfied. Poorly chosen values for the modulus and multiplier in a Lehmer random number generator will lead to a short period for the sequence of random numbers. Marsaglia's result may be further extended to a mixed linear congruential generator. 
Main statement

Consider a Lehmer random number generator with

$$r_{i+1}\equiv kr_{i}\mod m}$$

for any modulus m and multiplier k where each $$0<r_{i}<m}$$, and define a sequence

$$u_{1}={\frac {r_{1}}{m}},u_{2}={\frac {r_{2}}{m}},u_{3}={\frac {r_{3}}{m}},\ldots }$$

Define the points

$$\pi _{1}=(u_{1},\ldots ,u_{n}),\pi _{2}=(u_{2},\ldots ,u_{n+1}),\pi _{3}=(u_{3},\ldots ,u_{n+2}),\ldots }$$

on a unit n-cube formed from successive terms of the sequence of u. With such a multiplicative number generator, all } n-tuples of resulting random numbers lie in at most $$(n!m)^{1/n}}$$ hyperplanes. Additionally, for a choice of constants $$c_{1},c_{2},\ldots ,c_{n}}$$ which satisfy the congruence

$$c_{1}+c_{2}k+c_{3}k^{2}+\cdots +c_{n}k^{n-1}\equiv 0\mod m,}$$

there are at most $$|c_{1}|+|c_{2}|+\cdots +|c_{n}|}$$ parallel hyperplanes which contain all n-tuples produced by the generator. Proofs for these claims may be found in Marsaglia's original paper. 

References

Greenberger, Martin (October 1961). "An A Priori Determination of Serial Correlation in Computer Generated Random Numbers" (PDF). American Mathematical Society. 15 (76): 383–389. doi:10.2307/2003027.
Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi:10.1073/pnas.61.1.25. PMC 285899. PMID 16591687.

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License