A unified approach to the analysis of compound pseudorandom numbers (Q1344099)

Compound versions of some nonlinear congruential methods introduced by the author [Computing 51, No. 2, 175-182 (1993; Zbl 0787.65004); and Monatsh. Math. 117, 213-222 (1994; Zbl 0803.65003)] can provide sequences having a very large period length. In this paper the author gives a unified approach to the analysis of the full period and of parts of the period for such compound pseudorandom numbers. Let \(p_ 1, \dots, p_ r\) be distinct primes, and \((y_ n^{(i)})_{n\geq 0}\) be a sequence of elements of \(\mathbb{Z}_{p_ i}\) \((i=1,\dots, r)\). Then the sequence \((x_ n)_{n\geq 0}\) of compound pseudorandom numbers in the interval \([0,1)\) defined by \[ x_ n\equiv y_ n^{(1)}/p_ 1+ y_ n^{(2)}/ p_ 2+\ldots+ y_ n^{(r)}/ p_ r \pmod 1, \qquad n\geq 0 \] is purely periodic with period length \(m= p_ 1\cdots p_ r\). We put \(\vec x_ n=(x_{sn}, x_{sn+1}, \dots,x_{sn+ s- 1})\in[0,1)^ s\), \(n\geq0\), and let \(D_ N^{(s)}= D_ N^{(s)} (\vec x_ 0, \dots, \vec x_{N-1})\) be the discrepancy of the point set \(\{\vec x_ 0, \dots, \vec x_{N-1}\}\). For \(i\in\{ 1,\dots, r\}\) and \(\overset{\overset \sim \rightarrow} {h}\in\mathbb{Z}^{s+1}\) we define \[ S_ i(\overset {\overset \sim \rightarrow} {h})= \sum_{k\in \mathbb{Z}_{p_ i}}e(\overset {\overset \sim \rightarrow} {h}\cdot \overset {\overset \sim \rightarrow} {x}_ k^{(i)} ), \] where \(\overset {\overset \sim \rightarrow} {x}_ k^{(i)}= (y_{sk}^{(i)}, y_{sk+1}^{(i)}\) \(,\ldots, y_{sk+s-1}^{(i)}, k)/p_ i\in [0,1)^{s+1}\), \(e(t)= e^{2\pi it}\), and \(\vec u\cdot \vec v\) stands for the standard inner product of \(\vec u,\vec v\in \mathbb{R}^{s+1}\). The author proves the following: (1) If \(| S_ i (\vec h,0)|\leq B_ i\) for any \(\vec h\in \mathbb{Z}^ s\) with \(\vec h\not\equiv \vec 0 \pmod {p_ i}\) and \(1\leq i\leq r\), then \[ D_ m^{(s)}< {\textstyle {1\over m}} \prod_{i=1}^ r (B_ i+1) \Bigl( {\textstyle {2\over\pi}} \log m+ {\textstyle {7\over 5}} \Bigr)^ s; \] (2) If \(| S_ i (\overset {\overset \sim \rightarrow} {h})| \leq B_ i\) for any \(\overset{\overset\sim\rightarrow}{h}\in \mathbb{Z}^{s+1}\) with \(\overset {\overset \sim \rightarrow} {h} \not\equiv \vec 0\pmod {p_ i}\) and \(1\leq i\leq r\), then \[ D_ N^{(s)}< {\textstyle {1\over N}} \prod_{i=1}^ r (B_ i+1) \Bigl( {\textstyle {2\over \pi}} \log m+ {\textstyle {7\over 5}} \Bigr)^{s+1} \qquad \text{for } 1\leq N< m. \] Applying these results to the compound nonlinear congruential methods mentioned above, the author improves known upper bounds for the discrepancy over the full period and gives new upper bounds for the discrepancy over parts of the period.