Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Generalized inversive congruential pseudorandom numbers
open-in-new
<h2 id="example">Example</h2> <p>Let take m = 15 = 3 × 5 a = 2 , b = 3 {\displaystyle 3\times 5\,a=2,b=3} and y 0 = 1 {\displaystyle y_{0}=1} . Hence φ ( m ) = 2 × 4 = 8 {\displaystyle \varphi (m)=2\times 4=8\,} and the sequence ( y n ) n ⩾ 0 = ( 1 , 5 , 13 , 2 , 4 , 7 , 1 , … ) {\displaystyle (y_{n})_{n\geqslant 0}=(1,5,13,2,4,7,1,\dots )} is not maximum. </p><p>The result below shows that these sequences are closely related to the following inversive congruential sequence with prime moduli. </p><p>For 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} let Z p i = { 0 , 1 , … , p i − 1 } , m i = m / p i {\displaystyle \mathbb {Z} _{p_{i}}=\{0,1,\dots ,p_{i}-1\},m_{i}=m/p_{i}} and a i , b i ∈ Z p i {\displaystyle a_{i},b_{i}\in \mathbb {Z} _{p_{i}}} be integers with </p> a ≡ m i 2 a i ( mod p i ) and b ≡ m i b i ( mod p i ) . {\displaystyle a\equiv m_{i}^{2}a_{i}{\pmod {p_{i}}}\;{\text{and }}\;b\equiv m_{i}b_{i}{\pmod {p_{i}}}{\text{. }}} <p>Let ( y n ) n ⩾ 0 {\displaystyle (y_{n})_{n\geqslant 0}} be a sequence of elements of Z p i {\displaystyle \mathbb {Z} _{p_{i}}} , given by </p> 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. {\displaystyle 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. }}} <h2 id="theorem-1">Theorem 1</h2> <p>Let ( y n ( i ) ) n ⩾ 0 {\displaystyle (y_{n}^{(i)})_{n\geqslant 0}} for 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} be defined as above. Then </p> y n ≡ m 1 y n ( 1 ) + m 2 y n ( 2 ) + ⋯ + m r y n ( r ) ( mod m ) . {\displaystyle y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+\dots +m_{r}y_{n}^{(r)}{\pmod {m}}.} <p>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 {\displaystyle \mathbb {Z} _{p_{1}},\dots ,\mathbb {Z} _{p_{r}}} but not in Z m . {\displaystyle \mathbb {Z} _{m}.} </p><p>Proof: </p><p>First, observe that m i ≡ 0 ( mod p j ) , for i ≠ j , {\displaystyle m_{i}\equiv 0{\pmod {p_{j}}},\;{\text{for}}\;i\neq j,} and hence y n ≡ m 1 y n ( 1 ) + m 2 y n ( 2 ) + ⋯ + m r y n ( r ) ( mod m ) {\displaystyle 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 ≡ m i ( y n ( i ) ) ( mod p i ) {\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}} , for 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} which will be shown on induction on n ⩾ 0 {\displaystyle n\geqslant 0} . </p><p>Recall that y 0 ≡ m i ( y 0 ( i ) ) ( mod p i ) {\displaystyle y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}} is assumed for 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} . Now, suppose that 1 ≤ i ≤ r {\displaystyle 1\leq i\leq r} and y n ≡ m i ( y n ( i ) ) ( mod p i ) {\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}} for some integer n ⩾ 0 {\displaystyle n\geqslant 0} . Then straightforward calculations and <a href="/facts/Fermat%27s_little_theorem/qIjSIm2s">Fermat's Theorem</a> yield </p> 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 ) {\displaystyle y_{n+1}\equiv ay_{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}}}} , <p>which implies the desired result. </p><p>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 <i>s</i>-tuples of pseudorandom numbers. </p> <h2 id="discrepancy-bounds-of-the-gic-generator">Discrepancy bounds of the GIC Generator</h2> <p>We use the notation D m s = D m ( x 0 , … , x m − 1 ) {\displaystyle D_{m}^{s}=D_{m}(x_{0},\dots ,x_{m}-1)} where x n = ( x n , x n + 1 , … , x n + s − 1 ) {\displaystyle x_{n}=(x_{n},x_{n}+1,\dots ,x_{n}+s-1)} ∈ [ 0 , 1 ) s {\displaystyle [0,1)^{s}} of Generalized Inversive Congruential Pseudorandom Numbers for s ≥ 2 {\displaystyle s\geq 2} . </p><p>Higher bound </p> Let s ≥ 2 {\displaystyle s\geq 2} Then the discrepancy D m s {\displaystyle D_{m}^{s}} satisfies D m {\displaystyle D_{m}} s {\displaystyle ^{s}} < m − 1 / 2 {\displaystyle m^{-1/2}} × ( 2 π {\displaystyle ({\frac {2}{\pi }}} × log m + 7 5 ) s {\displaystyle \log m+{\frac {7}{5}})^{s}} × ∏ i = 1 r ( 2 s − 2 + s ( p i ) − 1 / 2 ) + s m − 1 {\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})+s_{m}^{-1}} for any Generalized Inversive Congruential operator. <p>Lower bound: </p> There exist Generalized Inversive Congruential Generators with D m {\displaystyle D_{m}} s {\displaystyle ^{s}} ≥ 1 2 ( π + 2 ) {\displaystyle {\frac {1}{2(\pi +2)}}} × m − 1 / 2 {\displaystyle m^{-1/2}} : × ∏ i = 1 r ( p i − 3 p i − 1 ) 1 / 2 {\displaystyle \textstyle \prod _{i=1}^{r}({\frac {p_{i}-3}{p_{i}-1}})^{1/2}} for all dimension <i>s</i> :≥ 2. <p>For a fixed number <i>r</i> of prime factors of <i>m</i>, Theorem 2 shows that D m ( s ) = O ( m − 1 / 2 ( log m ) s ) {\displaystyle 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 ) {\displaystyle D_{m}^{(s)}} which is at least of the order of magnitude m − 1 / 2 {\displaystyle m^{-1/2}} for all dimension s ≥ 2 {\displaystyle s\geq 2} . However, if <i>m</i> is composed only of small primes, then <i>r</i> can be of an order of magnitude ( log m ) / log log m {\displaystyle (\log m)/\log \log m} and hence ∏ i = 1 r ( 2 s − 2 + s ( p i ) − 1 / 2 ) = O ( m ϵ ) {\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}} for every ϵ > 0 {\displaystyle \epsilon >0} .<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> Therefore, one obtains in the general case D m s = O ( m − 1 / 2 + ϵ ) {\displaystyle D_{m}^{s}=O(m^{-1/2+\epsilon })} for every ϵ > 0 {\displaystyle \epsilon >0} . </p><p>Since ∏ i = 1 r ( ( p i − 3 ) / ( p i − 1 ) ) 1 / 2 ⩾ 2 − r / 2 {\displaystyle \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 − ϵ {\displaystyle m^{-1/2-\epsilon }} for every ϵ > 0 {\displaystyle \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 {\displaystyle m^{-1/2}(\log \log m)^{1/2}} according to the law of the iterated logarithm for discrepancies.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> In this sense, Generalized Inversive Congruential Pseudo-random Numbers model true random numbers very closely. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Pseudorandom_number_generator/sIrCxIBq">Pseudorandom number generator</a></li> <li><a href="/facts/List_of_random_number_generators/oWbCuAdA">List of random number generators</a></li> <li><a href="/facts/Linear_congruential_generator/E4PyJQ5U">Linear congruential generator</a></li> <li><a href="/facts/Inversive_congruential_generator/bRNhg1hA">Inversive congruential generator</a></li> <li><a href="/facts/Naor-Reingold_Pseudorandom_Function/Fl1Jwqu2">Naor-Reingold Pseudorandom Function</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Eichenauer-Herrmann, Jürgen (1994), "On Generalized Inversive Congruential Pseudorandom Numbers", <i>Mathematics of Computation</i>, 63 (207) (first ed.), American Mathematical Society: 293–299, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0025-5718-1994-1242056-8">10.1090/S0025-5718-1994-1242056-8</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2153575">2153575</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Clarendon Press, Oxford, 1979. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>