Generalized Inversive Congruential Pseudorandom Numbers

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval ,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli $m=p_1,\dots p_r$ with arbitrary distinct primes $p_1,\dots ,p_r \ge 5$ will be present here.

Let $\mathbb_ = \$. For Prime number">primes $p_1,\dots ,p_r \ge 5$ will be present here.

Let $\mathbb_ = \$. For integers $a,b \in \mathbb_$ with gcd (a,m) = 1 a generalized inversive congruential sequence $(y_)_$ of elements of $\mathbb_$ is defined by

: $y_ =$
: $y_\equiv a y_^ + b \pmod m \textn \geqslant 0$

where $\varphi(m)=(p_-1)\dots (p_-1)$ denotes the number of positive integers less than ''m'' which are relatively prime to ''m''.

Example

Let take m = 15 = $3 \times 5\, a=2 , b=3$ and $y_0= 1$. Hence $\varphi (m)= 2 \times 4=8 \,$ and the sequence $(y_)_=(1,5,13,2,4,7,1,\dots )$ 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 $\mathbb_= \, m_= m / p_$ and $a_ ,b_ \in \mathbb_$ be integers with

: $a\equiv m_^ a_\pmod \;\text\; b\equiv m_ b_\pmod \text$

Let $(y_)_$ be a sequence of elements of $\mathbb_$, given by

: $y_^\equiv a_ (y_^)^ + b_ \pmod \; \textn \geqslant 0 \;\text \;y_\equiv m_ (y_^)\pmod \;\text$

Theorem 1

Let $(y_^)_$ for $1\le i \le r$ be defined as above.
Then
: $y_\equiv m_y_^ + m_y_^ + \dots + m_y_^ \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 $\mathbb_,\dots , \mathbb_$ but not in $\mathbb_.$

Proof:

First, observe that $m_\equiv 0\pmod , \; \text \; i\ne j,$ and hence $y_\equiv m_y_^ + m_y_^ + \dots + m_y_^ \pmod m$ if and only if $y_\equiv m_ (y_^)\pmod$, for $1\le i \le r$ which will be shown on induction on $n \geqslant 0$.

Recall that $y_\equiv m_ (y_^)\pmod$ is assumed for $1\le i \le r$. Now, suppose that $1\le i \le r$ and $y_\equiv m_ (y_^)\pmod$ for some integer $n \geqslant 0$. Then straightforward calculations and Fermat's little theorem">Fermat's Theorem yield

: $y_\equiv a y_^ + b \equiv m_(a_m_^(y_^)^+ b_)\equiv m_(a_(y_^)^ + b_)\equiv m_(y_^) \pmod$,
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 ^=D_m (x_0,\dots , x_m-1)$ where $x_n=(x_n, x_n+1 ,\dots , 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_m ^s$ satisfies
:$D_m$ $^s$ < $m^$ $( \frac$ $\log m + \frac)^s$ $\textstyle \prod_^r (2s-2 + s(p_i)^)+ s_^$ for any Generalized Inversive Congruential operator.

Lower bound:

:There exist Generalized Inversive Congruential Generators with
:$D_m$ $^s$ $\frac$ $m^$ : $\textstyle \prod_^r (\frac )^$ for all dimension ''s'' 2.

For a fixed number ''r'' of prime factors of ''m'', Theorem 2 shows that $D_m^ = O (m^ (\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^$ which is at least of the order of magnitude $m^$ 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)/\log\log m$ and hence $\textstyle \prod_^r (2s-2 + s(p_i)^)= O$ for every $\epsilon> 0$. Therefore, one obtains in the general case $D_m^=O(m^)$ for every $\epsilon> 0$.

Since $\textstyle \prod_^r ((p_ - 3)/(p_ - 1))^ \geqslant 2^$, similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude
$m^$ 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^ (\log\log m)^$
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

References

Notes

*

{{DEFAULTSORT:Generalized Inversive Congruential Pseudorandom Numbers
Pseudorandom number generators