Generalized inversive congruential pseudorandom numbers

Example

Let take m = 15 = 3 × 5 a = 2 , b = 3 and y 0 = 1 . Hence φ ( m ) = 2 × 4 = 8 and the sequence ( y n ) n ⩾ 0 = ( 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 ≤ i ≤ r let Z p i = { 0 , 1 , … , p i − 1 } , m i = m / p i and a i , b i ∈ Z p i be integers with

a ≡ m i 2 a i ( mod p i ) and  b ≡ m i b i ( mod p i ) . 

Let ( y n ) n ⩾ 0 be a sequence of elements of Z p i , given by

y n + 1 ( i ) ≡ a i ( y n ( i ) ) p i − 2 + b i ( mod p i ) ,  n ⩾ 0 where y 0 ≡ m i ( y 0 ( i ) ) ( mod p i ) is assumed. 

Theorem 1

Let ( y n ( i ) ) n ⩾ 0 for 1 ≤ i ≤ r be defined as above. Then

y n ≡ m 1 y n ( 1 ) + m 2 y n ( 2 ) + ⋯ + m r y n ( r ) ( mod 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 ≡ 0 ( mod p j ) , for i ≠ j , and hence y n ≡ m 1 y n ( 1 ) + m 2 y n ( 2 ) + ⋯ + m r y n ( r ) ( mod m ) if and only if y n ≡ m i ( y n ( i ) ) ( mod p i ) , for 1 ≤ i ≤ r which will be shown on induction on n ⩾ 0 .

Recall that y 0 ≡ m i ( y 0 ( i ) ) ( mod p i ) is assumed for 1 ≤ i ≤ r . Now, suppose that 1 ≤ i ≤ r and y n ≡ m i ( y n ( i ) ) ( mod p i ) for some integer n ⩾ 0 . Then straightforward calculations and Fermat's Theorem yield

y n + 1 ≡ a y n φ ( m ) − 1 + b ≡ m i ( a i m i φ ( m ) ( y n ( i ) ) φ ( m ) − 1 + b i ) ≡ m i ( a i ( y n ( i ) ) p i − 2 + b i ) ≡ m i ( y n + 1 ( i ) ) ( mod 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 m s = 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 ≥ 2 .

Higher bound

Let s ≥ 2 Then the discrepancy D m s satisfies D m s < m − 1 / 2 × ( 2 π × log ⁡ m + 7 5 ) s × ∏ i = 1 r ( 2 s − 2 + s ( p i ) − 1 / 2 ) + s m − 1 for any Generalized Inversive Congruential operator.

Lower bound:

There exist Generalized Inversive Congruential Generators with D m s ≥ 1 2 ( π + 2 ) × m − 1 / 2  : × ∏ i = 1 r ( 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 m ( s ) = 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 m ( s ) which is at least of the order of magnitude m − 1 / 2 for all dimension s ≥ 2 . However,if m is composed only of small primes, then r can be of an order of magnitude ( log ⁡ m ) / log ⁡ log ⁡ m and hence ∏ i = 1 r ( 2 s − 2 + s ( p i ) − 1 / 2 ) = O ( m ϵ ) for every ϵ > 0 . Therefore, one obtains in the general case D m s = O ( m − 1 / 2 + ϵ ) for every ϵ > 0 .

Since ∏ i = 1 r ( ( p i − 3 ) / ( p i − 1 ) ) 1 / 2 ⩾ 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 ϵ > 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 ( log ⁡ log ⁡ 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.