Generalized inversive congruential pseudorandom numbers explained

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the [[Inversive congruential generator]] with prime modulus. A generalization for arbitrary composite moduli

m = p _{1,...} p _{r} with arbitrary distinct primes p _{1,...} ,p _{r} \ge 5 will be present here.

Let

Z _{m} = \{ 0 , 1 ,...,m -1 \} . For integers a,b \in Z _{m} with gcd (a,m) = 1 a generalized inversive congruential sequence (y _{n} ) _{n} of elements of Z _{m} is defined byy _{0} = {\rm seed} y _{n+1} \equiv a y ^{\varphi(m) -1} _{n} + b \pmod m , n \geqslant 0

where

\varphi(m) = (p _{1} -1 ) ... (p _{r} -1 ) denotes the number of positive integers less than m which are relatively prime to m.

Example

Let take m = 15 =

3 x 5 a =2 , b =3 and y _{0=} 1 . Hence \varphi (m) = 2 x 4=8 and the sequence (y _{n} ) _{n} = ( 1 , 5 , 13 , 2 , 4 , 7 , 1 , ... ) is not maximum.

The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli.

For

1 \le i \le r let Z _{p _{i}} = \{ 0 , 1 , ... ,p _{i} -1 \}, m _{i} = m / p _{i} and a _{i} ,b _{i} \in Z _{p _{i}} be integers witha\equiv m ^{2} _{i} a _{i} \pmod {p _{i} } \;\text\; b\equiv m_ b_\pmod \text

Let

(y _{n} ) _{n} be a sequence of elements of Z _{p _{i}} , given byy ^{(i)} _{n +1} \equiv a _{i} (y ^{(i)} _{n} ) ^{p _{i} -2} + b _{i} \pmod {p _{i} }\; \textn \geqslant 0 \;\text \;y_\equiv m_ (y_^)\pmod \;\text

Theorem 1

Let

(y ^{(i)} _{n} ) _{n} for 1 \le i \le r be defined as above.Then y _{n} \equiv m _{1} y ^{( 1 )} _{n} + m _{2} y ^{( 2 )} _{n} + ... + m _{r} y ^{(r)} _{n} \pmod m.

This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible, where exact integer computations have to be performed only in

Z _{p _{1}} , ... , Z _{p _{r}} but not in Z _{m} .

Proof:

First, observe that

m _{i} \equiv 0 \pmod {p _{j} }, \; \text \; i\ne j, and hence y _{n} \equiv m _{1} y ^{( 1 )} _{n} + m _{2} y ^{( 2 )} _{n} + ... + m _{r} y ^{(r)} _{n} \pmod m if and only if y _{n} \equiv m _{i} (y ^{(i)} _{n} )\pmod {p _{i} }, for 1 \le i \le r which will be shown on induction on n \geqslant 0 .

Recall that

y _{0} \equiv m _{i} (y ^{(i)} _{0} )\pmod {p _{i} } is assumed for 1 \le i \le r . Now, suppose that 1 \le i \le r and y _{n} \equiv m _{i} (y ^{(i)} _{n} )\pmod {p _{i} } for some integer n \geqslant 0 . Then straightforward calculations and Fermat's Theorem yieldy _{n+1} \equiv a y ^{\varphi(m) -1} _{n} + b \equiv m _{i} (a _{i} m ^{\varphi(m)} _{i} (y ^{(i)} _{n} ) ^{\varphi(m)-1} + b _{i} )\equiv m _{i} (a _{i} (y ^{(i)} _{n} ) ^{p _{i} -2} + b _{i} )\equiv m _{i} (y ^{(i)} _{n +1} ) \pmod {p _{i} },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.

Discrepancy bounds of the GIC Generator

We use the notation

D ^{s} _{m} = D _{m} (x _{0,...} , x _{m-1)} where x _{n=(x} _{n,} x _{n+1} , ... , x _{n+s-1)} [ 0 , 1 ) ^{s} of Generalized Inversive Congruential Pseudorandom Numbers for s\ge 2 .

Higher bound

Let

s\ge 2

Then the discrepancy

D ^{s} _{m} satisfiesD _{m} ^{s} < m ^{-1/2} ( (2)/(\pi) log m + (7)/(5) ) ^{s} style \prod ^{r} _{i =1} ( 2 s -2 + s(p ^{-1 / 2} _{i)} ) + s ^{-1} _{m} for any Generalized Inversive Congruential operator.

Lower bound:

There exist Generalized Inversive Congruential Generators with

D _{m} ^{s} (1)/(2 (\pi +2 )) m ^{-1/2} : style \prod ^{r} _{i =1} ( (p _{i} -3)/(p _{i} -1) ) ^{1/2} for all dimension s 2.

For a fixed number r of prime factors of m, Theorem 2 shows that

D ^{(s)} _{m} = O (m ^{-1/2} ( log m ) ^{s)} for any Generalized Inversive Congruential Sequence. In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy D ^{(s)} _{m} which is at least of the order of magnitude m ^{-1/2} for all dimension s\ge 2 . However, if m is composed only of small primes, then r can be of an order of magnitude ( log m)/ loglog m and hence style \prod ^{r} _{i =1} ( 2 s -2 + s(p ^{-1 / 2} _{i)} ) = O{(m ^{\epsilon} )} for every \epsilon> 0 . Therefore, one obtains in the general case D ^{s} _{m} = O(m ^{-1/2+\epsilon} ) for every \epsilon> 0 .

Since

style \prod ^{r} _{i =1} ((p _{i} - 3 )/(p _{i} - 1 )) ^{1/2} \geqslant 2 ^{-r/2} , similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude m ^{-1/2} for every \epsilon> 0 . 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 m ^{-1/2} ( loglog m) ^{1/2} according to the law of the iterated logarithm for discrepancies. In this sense, Generalized Inversive Congruential Pseudo-random Numbers model true random numbers very closely.

See also

• Pseudorandom number generator
• List of random number generators
• Linear congruential generator
• Inversive congruential generator
• Naor-Reingold Pseudorandom Function