Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus
Let \(a,c\) be integers with \(a\equiv 1\pmod 4\) and \(c\equiv 1\pmod 2\), and let \(m=2^\omega\) for some integer \(\omega\geq 3\). Define a sequence \((x_n)_{n\geq 0}\) of inversive congruential pseudorandom numbers in \([0,1)\) by \[ y_{n+1} \equiv ac^2 y_n^{-1}+ 2c \pmod m\quad \text{and} \quad x_n=y_n/m,\;n\geq 0, \] where \(z^{-1}\) denotes the multiplicative inverse of an odd integer \(z\) modulo \(m\). It is purely periodic with the maximum possible period length \(m/2\). Let \(1\leq N\leq m/2\) and \(D_{N;a,c}\) be the discrepancy of the point set \(\{x_0,x_1, \dots, x_{N-1}\}\). The author gives the following upper bound estimate of the average value of \(D_{N;a,c}\) over the parameter \(c\in \mathbb{Z}_m^* =\{1,3, \dots, m-1\}\): \[ {2 \over m} \sum_{c\in\mathbb{Z}^*_m} D_{N;a,c} \leq {2\over N} \sqrt {\min(N,m/2-N)} \left({1 \over\pi} \log m+ {1\over 5} \right)+ {2\over m} \] for any \(a\equiv 1\pmod 4\). Further, he also proves that for any \(a\equiv 1\pmod 4\) there exist more than \((1-\alpha) m/2\) (here \(0<\alpha \leq 1)\) values of \(c\in \mathbb{Z}^*_m\) such that \(D_{N;a,c} \leq 1/ \alpha\) times this upper bound, and, on the other hand, there is \(c\in\mathbb{Z}_m^*\) such that \[ D_{N;a,c} \geq{1\over 2N} \sqrt {\min(N,m/2-N)}. \] These results fit well with the equidistribution behaviour of true random numbers.
- Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus
- Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
- On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus
- An Estimate Concerning the Kolmogroff Limit Distribution
- scientific article; zbMATH DE number 53679 (Why is no real title available?)
- Inversive Congruential Pseudorandom Numbers: A Tutorial
- Kloosterman-type sums and the discrepancy of nonoverlapping pairs of inversive congruential pseudorandom numbers
- Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
- Pseudo-random numbers and optimal coefficients
- Pseudorandom Number Generation by Nonlinear Methods
- The Serial Test for Congruential Pseudorandom Numbers Generated by Inversions
- Average discrepancy, hyperplanes, and compound pseudorandom numbers
- On the average discrepancy of successive tuples of pseudo-random numbers over parts of the period
- On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus. II
- Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus
- Exponential sums on the sequences of inversive congruential pseudorandom numbers
- Kloosterman-type sums and the discrepancy of nonoverlapping pairs of inversive congruential pseudorandom numbers
- Explicit Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
- Properties of the x/sup 2/ mod N pseudorandom number generator
- Distribution of short subsequences of inversive congruential pseudorandom numbers modulo $2^t$
This page was built for publication: Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2564982)
