This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible, where exact integer computations have to be performed only in but not in
Proof:
First, observe that and hence if and only if , for which will be shown on induction on .
Recall that is assumed for . Now, suppose that and for some integer . Then straightforward calculations and Fermat's Theorem yield
,
which implies the desired result.
Generalized Inversive Congruential Pseudorandom Numbers are well equidistributed in one dimension. A reliable theoretical approach for assessing their statistical independence properties is based on the discrepancy of s-tuples of pseudorandom numbers.
We use the notation where ∈ of Generalized Inversive Congruential Pseudorandom Numbers for .
Higher bound
Let
Then the discrepancy satisfies
< × × × for any Generalized Inversive Congruential operator.
Lower bound:
There exist Generalized Inversive Congruential Generators with
≥ × : × for all dimension s :≥ 2.
For a fixed number r of prime factors of m, Theorem 2 shows that
for any Generalized Inversive Congruential Sequence. In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy which is at least of the order of magnitude for all dimension . However, if m is composed only of small primes, then r can be of an order of magnitude and hence for every .[1] Therefore, one obtains in the general case for every .
Since , similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude
for every . It is this range of magnitudes where one also finds the discrepancy of m independent and uniformly distributed random points which almost always has the order of magnitude
according to the law of the iterated logarithm for discrepancies.[2] In this sense, Generalized Inversive Congruential Pseudo-random Numbers model true random numbers very closely.
^G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Clarendon Press, Oxford, 1979.
^J. Kiefer, On large deviations of the empiric d.f. Fo vector chance variables and a law of the iterated logarithm, PacificJ. Math. 11(1961), pp. 649-660.