Английская Википедия: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 <math>m=p_1,\dots p_r</math> with arbitrary distinct primes <math>p_1,\dots ,p_r \ge 5</math> will be present here.
Let <math> \mathbb{Z}_{m} = \{0,1,...,m-1\} </math>. For integers <math> a,b \in \mathbb{Z}_{m} </math> with gcd (a,m) = 1 a generalized inversive congruential sequence <math> (y_{n})_{n \geqslant 0} </math> of elements of <math> \mathbb{Z}_{m} </math> is defined by
- <math> y_{0} = {\rm seed}</math>
- <math> y_{n+1}\equiv a y_{n}^{\varphi(m)-1} + b \pmod m \text{, }n \geqslant 0 </math>
where <math> \varphi(m)=(p_{1}-1)\dots (p_{r}-1)</math> denotes the number of positive integers less than m which are relatively prime to m.
Example
Let take m = 15 = <math> 3 \times 5\, a=2 , b=3</math> and <math>y_0= 1</math>. Hence <math> \varphi (m)= 2 \times 4=8 \,</math> and the sequence <math> (y_{n})_{n \geqslant 0}=(1,5,13,2,4,7,1,\dots )</math> is not maximum.
The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli.
For <math>1\le i \le r</math> let <math> \mathbb{Z}_{p_{i}}= \{0,1,\dots ,p_{i}-1\}, m_{i}= m / p_{i} </math> and <math> a_{i} ,b_{i} \in \mathbb{Z}_{p_{i}} </math> be integers with
- <math> a\equiv m_{i}^{2} a_{i}\pmod {p_{i}} \;\text{and }\; b\equiv m_{i} b_{i}\pmod {p_{i}} \text{. }</math>
Let <math> (y_{n})_{n \geqslant 0} </math> be a sequence of elements of <math> \mathbb{Z}_{p_{i}}</math>, given by
- <math> 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. } </math>
Theorem 1
Let <math>(y_{n}^{(i)})_{n \geqslant 0} </math> for <math>1\le i \le r</math> be defined as above. Then
- <math> y_{n}\equiv m_{1}y_{n}^{(1)} + m_{2}y_{n}^{(2)} + \dots + m_{r}y_{n}^{(r)} \pmod m. </math>
This theorem shows that an implementation of Generalized Inversive Congruential Generator is possible, where exact integer computations have to be performed only in <math> \mathbb{Z}_{p_{1}},\dots , \mathbb{Z}_{p_{r}}</math> but not in <math> \mathbb{Z}_{m}. </math>
Proof:
First, observe that <math> m_{i}\equiv 0\pmod {p_{j}}, \; \text {for} \; i\ne j, </math> and hence <math> y_{n}\equiv m_{1}y_{n}^{(1)} + m_{2}y_{n}^{(2)} + \dots + m_{r}y_{n}^{(r)} \pmod m </math> if and only if <math>y_{n}\equiv m_{i} (y_{n}^{(i)})\pmod {p_{i}}</math>, for <math>1\le i \le r</math> which will be shown on induction on <math>n \geqslant 0 </math>.
Recall that <math>y_{0}\equiv m_{i} (y_{0}^{(i)})\pmod {p_{i}} </math> is assumed for <math>1\le i \le r</math>. Now, suppose that <math>1\le i \le r</math> and <math>y_{n}\equiv m_{i} (y_{n}^{(i)})\pmod {p_{i}}</math> for some integer <math>n \geqslant 0 </math>. Then straightforward calculations and Fermat's Theorem yield
- <math> 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}}</math>,
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 <math>D_m ^{s}=D_m (x_0,\dots , x_m-1)</math> where <math> x_n=(x_n, x_n+1 ,\dots , x_n+s-1) </math> Шаблон:Math <math> [0,1)^s </math> of Generalized Inversive Congruential Pseudorandom Numbers for <math>s\ge 2</math>.
Higher bound
- Let <math>s\ge 2</math>
- Then the discrepancy <math> D_m ^s </math> satisfies
- <math> D_m </math> <math> ^s </math> < <math> m^{-1/2}</math> Шаблон:Math <math> ( \frac{2}{\pi}</math> Шаблон:Math<math> \log m + \frac{7}{5})^s</math> Шаблон:Math <math> \textstyle \prod_{i=1}^r (2s-2 + s(p_i)^{-1/2})+ s_{m}^{-1} </math> for any Generalized Inversive Congruential operator.
Lower bound:
- There exist Generalized Inversive Congruential Generators with
- <math> D_m </math> <math> ^s </math> Шаблон:Math <math> \frac{1}{2(\pi+2)}</math> Шаблон:Math<math> m^{-1/2} </math> :Шаблон:Math <math> \textstyle \prod_{i=1}^r (\frac {p_{i} - 3}{p_{i} - 1})^{1/2} </math> for all dimension s Шаблон:Math 2.
For a fixed number r of prime factors of m, Theorem 2 shows that <math> D_m^{(s)} = O (m^{-1/2} (\log m )^s)</math> for any Generalized Inversive Congruential Sequence. In this case Theorem 3 implies that there exist Generalized Inversive Congruential Generators having a discrepancy <math> D_m^{(s)} </math> which is at least of the order of magnitude <math> m^{-1/2} </math> for all dimension <math>s\ge 2</math>. However, if m is composed only of small primes, then r can be of an order of magnitude <math> (\log m)/\log\log m </math> and hence <math> \textstyle \prod_{i=1}^r (2s-2 + s(p_i)^{-1/2})= O{(m^\epsilon )} </math> for every <math> \epsilon> 0</math>.[1] Therefore, one obtains in the general case <math> D_m^{s}=O(m^{-1/2+\epsilon}) </math> for every <math> \epsilon> 0</math>.
Since <math> \textstyle \prod_{i=1}^r ((p_{i} - 3)/(p_{i} - 1))^{1/2} \geqslant 2^{-r/2} </math>, similar arguments imply that in the general case the lower bound in Theorem 3 is at least of the order of magnitude <math> m^{-1/2 - \epsilon}</math> for every <math>\epsilon> 0</math>. 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 <math> m^{-1/2} (\log\log m)^{1/2}</math> 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.
See also
- Pseudorandom number generator
- List of random number generators
- Linear congruential generator
- Inversive congruential generator
- Naor-Reingold Pseudorandom Function
References
Notes
