Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus
type: Item
instance of: scholarly article
title: Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus
zbMATH Open document ID: 0916.11046
DOI: 10.1007/BF01317314
author: Jürgen Eichenauer-Herrmann
author: Harald Niederreiter
published in: Monatshefte für Mathematik
publication date: 1999-07-19T00:00:00Z
full work available at URL: https://eudml.org/doc/178808
review text: Let \(m= 2^\omega\) with some integer \(\omega\geq 4\), and for integers \(n\geq 1\) let \(\mathbb{Z}^*_n\) be the set of all odd integers among \(0,1,\dots,n- 1\). For \(y_0\in \mathbb{Z}^*_m\) and parameters \(a,c\in \mathbb{Z}^*_m\) with \(a\equiv 1\pmod 4\), define \[ y_{n+ 1}\equiv ac^2 y^{-1}_n+ 2c\pmod m, \] where \(z^{-1}\) means the multiplicative inverse \(\text{mod }m\) of \(z\in \mathbb{Z}^*_m\). Let \(x_n= y_n/m\) for \(n\geq 0\). Thus, we obtain a sequence \((x_n)_{n\geq 0}\) of inversive congruential pseudorandom numbers in \([0,1)\). It is purely periodic with the maximum possible period length \(m/2\). The authors consider triples \(\vec x_n= (x_n,x_{n+ 1},x_{n+ 2})\in [0,1)^3\) \((n= 0,1,2,\dots)\), and prove that for any parameters \(a,c\in\mathbb{Z}^*_m\) as above the discrepancy of the points \(\vec x_0,\vec x_1,\dots,\vec x_{(m/2)- 1}\) is of an order of magnitude at least \(m^{-1/3}\). Of course, this lower bound remains valid for the discrepancy of \(k\)-tuples with \(k\geq 4\). The proof of this result is based on a detailed discussion of certain rational exponential sums.
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 1154521
zbMATH Keywords: inversive congruential pseudorandom numbers
zbMATH Keywords: discrepancy
zbMATH Keywords: rational exponential sums
reviewed by: Yaochen Zhu
MaRDI profile type: Publication
cites work: A Nonlinear Congruential Pseudorandom Number Generator with Power of Two Modulus
cites work: Inversive Congruential Pseudorandom Numbers: A Tutorial
cites work: Pseudorandom Number Generation by Nonlinear Methods
cites work: Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus
cites work: On the discrepancy of quadratic congruential pseudorandom numbers
cites work: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
cites work: Kloosterman-type sums and the discrepancy of nonoverlapping pairs of inversive congruential pseudorandom numbers
cites work: Uniform random number generation
cites work: The Serial Test for Congruential Pseudorandom Numbers Generated by Inversions
cites work: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers
cites work: Recent trends in random number and random vector generation
cites work: Q4003879
cites work: Q4856455
OpenAlex ID: W2141368662
Recommended article: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
Recommended article: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers
Recommended article: Improved upper bounds for the discrepancy of pairs of inversive congruential pseudorandom numbers with power of two modulus
Recommended article: Improved Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers
Recommended article: On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus. II
Recommended article: On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus
Recommended article: On the discrepancy of quadratic congruential pseudorandom numbers with power of two modulus
Recommended article: Discrepancy bounds for nonoverlapping pairs of quadratic congruential pseudorandom numbers
Recommended article: Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus
description: scientific article; zbMATH DE number 1154521