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,...,m-1\}$ .For integers $a,b \in \mathbb{Z}_{m}$ with gcd (a,m) = 1 a generalized inversive congruential sequence $(y_{n})_{n \geqslant 0}$ of elements of $\mathbb{Z}_{m}$ is defined by

y_{0} = {\rm seed}

y_{n+1}\equiv a y_{n}^{\varphi(m)-1} + b \pmod m \text{, }n \geqslant 0

where $\varphi(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 5\, a=2 , b=3$ and $y_0= 1$ . Hence $\varphi (m)= 2 \times 4=8 \,$ and the sequence $(y_{n})_{n \geqslant 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}\pmod {p_{i}} \;\text{and }\; b\equiv m_{i} b_{i}\pmod {p_{i}} \text{. }

Let $(y_{n})_{n \geqslant 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} \pmod {p_{i}}\; \text{, }n \geqslant 0 \;\text {where} \;y_{0}\equiv m_{i} (y_{0}^{(i)})\pmod {p_{i}}\;\text{is assumed. }

Theorem 1

Let $(y_{n}^{(i)})_{n \geqslant 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)} \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{Z}_{p_{1}},\dots , \mathbb{Z}_{p_{r}}$ but not in $\mathbb{Z}_{m}.$

Proof:

First, observe that $m_{i}\equiv 0\pmod {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)} \pmod m$ if and only if $y_{n}\equiv m_{i} (y_{n}^{(i)})\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_{0}^{(i)})\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_{n}^{(i)})\pmod {p_{i}}$ for some integer $n \geqslant 0$ . Then straightforward calculations and Fermat's Theorem yield

y_{n+1}\equiv a y_{n}^{\varphi(m)-1} + b \equiv m_{i}(a_{i}m_{i}^{\varphi(m)}(y_{n}^{(i)})^{\varphi(m)-1}+ b_{i})\equiv m_{i}(a_{i}(y_{n}^{(i)})^{p_{i}-2} + b_{i})\equiv m_{i}(y_{n+1}^{(i)}) \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_m ^{s}=D_m (x_0,\dots , x_m-1)$ where $x_n=(x_n, x_n+1 ,\dots , x_n+s-1)$ $\in$ $[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}

\times

( \frac{2}{\pi}

\times

\log m + \frac{7}{5})^s

\times

\textstyle \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

\geq

\frac{1}{2(\pi+2)}

\times

m^{-1/2}

\times

\textstyle \prod_{i=1}^r (\frac {p_{i} - 3}{p_{i} - 1})^{1/2}

for all dimension s

: \geq

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 $\textstyle \prod_{i=1}^r (2s-2 + s(p_i)^{-1/2})= O{(m^\epsilon )}$ for every $\epsilon> 0$ .^[1] Therefore, one obtains in the general case $D_m^{s}=O(m^{-1/2+\epsilon})$ for every $\epsilon> 0$ .

Since $\textstyle \prod_{i=1}^r ((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 - \epsilon}$ 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} (\log\log m)^{1/2}$ 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.

References

↑ 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.

Notes

Eichenauer-Herrmann, Jürgen (1994), On Generalized Inversive Congruential Pseudorandom Numbers (first ed.), American Mathematical Society, JSTOR 2153575

This article is issued from Wikipedia - version of the Monday, May 05, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.