Generalized inversive congruential pseudorandom numbers

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,\dots p_r$ with arbitrary distinct primes $p_1,\dots ,p_r\ge 5$ will be present here.

Let ${\mathbb{Z}}_m=\{0,1,\mathrm{...},m-1\}$. For integers $a,b\in {\mathbb{Z}}_m$ with gcd (a,m) = 1 a generalized inversive congruential sequence $(y_n{)}_{n⩾0}$ of elements of ${\mathbb{Z}}_m$ is defined by

$y_0=\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{d}$

$y_{n+1}\equiv a{y}_n^{\phi (m)-1}+b(\mathrm{mod}m)\text{, }n⩾0$

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

Example

Let take m = 15 = $3\times 5a=2,b=3$ and $y_0=1$. Hence $\phi (m)=2\times 4=8$ and the sequence $(y_n{)}_{n⩾0}=(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{Z}}_{p_i}=\{0,1,\dots ,p_i-1\},m_i=m/p_i$ and $a_i,b_i\in {\mathbb{Z}}_{p_i}$ be integers with

$a\equiv m_i^2{a}_i(\mathrm{mod}{p}_i)\text{and }b\equiv m_i{b}_i(\mathrm{mod}{p}_i)\text{. }$

Let $(y_n{)}_{n⩾0}$ be a sequence of elements of ${\mathbb{Z}}_{p_i}$, given by

$y_{n+1}^{(i)}\equiv a_i(y_n^{(i)}{)}^{p_i-2}+b_i(\mathrm{mod}{p}_i)\text{, }n⩾0\text{where}{y}_0\equiv m_i(y_0^{(i)})(\mathrm{mod}{p}_i)\text{is assumed. }$

Theorem 1

Let $(y_n^{(i)}{)}_{n⩾0}$ for $1\le i\le r$ be defined as above. Then

$y_n\equiv m_1{y}_n^{(1)}+m_2{y}_n^{(2)}+\dots +m_r{y}_n^{(r)}(\mathrm{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 ${\mathbb{Z}}_{p_1},\dots ,{\mathbb{Z}}_{p_r}$ but not in ${\mathbb{Z}}_m.$

Proof:

First, observe that $m_i\equiv 0(\mathrm{mod}{p}_j),\text{for}i\ne j,$ and hence $y_n\equiv m_1{y}_n^{(1)}+m_2{y}_n^{(2)}+\dots +m_r{y}_n^{(r)}(\mathrm{mod}m)$ if and only if $y_n\equiv m_i(y_n^{(i)})(\mathrm{mod}{p}_i)$, for $1\le i\le r$ which will be shown on induction on $n⩾0$.

Recall that $y_0\equiv m_i(y_0^{(i)})(\mathrm{mod}{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_n^{(i)})(\mathrm{mod}{p}_i)$ for some integer $n⩾0$. Then straightforward calculations and Fermat's Theorem yield

$y_{n+1}\equiv a{y}_n^{\phi (m)-1}+b\equiv m_i(a_i{m}_i^{\phi (m)}(y_n^{(i)}{)}^{\phi (m)-1}+b_i)\equiv m_i(a_i(y_n^{(i)}{)}^{p_i-2}+b_i)\equiv m_i(y_{n+1}^{(i)})(\mathrm{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,\dots ,x_m-1)$ where $x_n=(x_n,x_n+1,\dots ,x_n+s-1)$ Template:Math $[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^{-1/2}$ Template:Math $(\frac{2}{\pi }$ Template:Math$\log m+\frac{7}{5}{)}^s$ Template:Math ${\prod }_{i=1}^r(2s-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$ Template:Math $\frac{1}{2(\pi +2)}$ Template:Math$m^{-1/2}$ :Template:Math ${\prod }_{i=1}^r(\frac{p_i-3}{p_i-1}{)}^{1/2}$ for all dimension s Template:Math 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\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 ${\prod }_{i=1}^r(2s-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 ${\prod }_{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.

See also

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

Notes

• Template:Citation