Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus (Q2564982): Difference between revisions

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.