Explicit inversive congruential pseudorandom numbers: The compound approach
type: Item
instance of: scholarly article
title: Explicit inversive congruential pseudorandom numbers: The compound approach
zbMATH Open document ID: 0787.65004
DOI: 10.1007/BF02243851
published in: Computing
publication date: 1994-01-12T00:00:00Z
review text: Let \(p_ 1,p_ 2,\dots,p_ r\geq 5\) be distinct primes. For \(1\leq i\leq r\) let \(a_ i\in \mathbb{Z}_{p_ i}\backslash \{0\}\), and \(b_ i\in\mathbb{Z}_{p_ i}\). Define the corresponding explicit inversive congruential sequence \((y^{(i)}_ n)_{n\geq 0}\) in \(\mathbb{Z}_{p_ i}\) by \(y^{(i)}_ n\equiv \overline{a_ i n+b_ i}(\text{mod } p_ i)\), \(n\geq 0\), where \(\bar z\) denotes the inverse of \(z\) modulo \(p_ i\). Let \(m=p_ 1\cdots p_ r\) and \(m_ i= m/p_ i\) for \(1\leq i\leq r\). Then define the compound explicit inversive congruential sequence \((y_ n)_{n\geq 0}\) in \(\mathbb{Z}_ m\) by \(y_ n\equiv m_ 1 y^{(1)}_ n+\cdots+ m_ r y^{(r)}_ n(\text{mod } m)\),\(n\geq 0\). Let \(x_ n= y_ n/m\), \(n\geq 0\). Finally, define the \(s\)-tuples \(\vec x_ n= (x_{n+n_ 1},\dots,x_{n+n_ s})\in [0,1)^ s\), \(n\geq 0\), where \(2\leq s\leq \min(p_ 1,\dots,p_ r)\), and \(n_ 1,\dots,n_ s\) are arbitrary integers such that \(0= n_ 1<n_ 2<\cdots <n_ s<\min(p_ 1,\dots,p_ r)\). The author proves that the discrepancy \(D^{(s)}_ m\) of the sequence \(\{\vec x_ 0,\dots,\vec x_{m-1}\}\) satisfies \[ D^{(s)}_ m< m^{- 1/2}\left({2\over \pi}\log m+{7\over 5}\right)^ s\prod^ r_{i=1} (2s- 2+(s+2)p^{-1/2}_ i)+ sm^{-1}, \] and shows that this upper bound for \(D^{(s)}_ m\) is best possible up to the logarithmic factor.
reviewed by: Yaochen Zhu
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11K38
zbMATH DE Number: 482261
zbMATH Keywords: pseudorandom numbers
zbMATH Keywords: statistical independence
zbMATH Keywords: explicit inversive congruential sequence
zbMATH Keywords: discrepancy
author: Jürgen Eichenauer-Herrmann
describes a project that uses: AS 183
MaRDI profile type: Publication
cites work: Q3746773
cites work: Q4295075
cites work: Inversive Congruential Pseudorandom Numbers: A Tutorial
cites work: Inversive Congruential Pseudorandom Numbers Avoid the Planes
cites work: Statistical Independence of a New Class of Inversive Congruential Pseudorandom Numbers
cites work: Q3136941
cites work: On large deviations of the empiric D.F. of vector chance variables and a law of the iterated logarithm
cites work: Pseudo-random numbers and optimal coefficients
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: Q4026983
cites work: Q4003879
cites work: Q4295076
full work available at URL: https://doi.org/10.1007/bf02243851
OpenAlex ID: W1588495577
Recommended article: On the distribution of compound inversive congruential pseudorandom numbers
Recommended article: Q3136941
Recommended article: On Generalized Inversive Congruential Pseudorandom Numbers
Recommended article: Q4214771
Recommended article: Explicit Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
Recommended article: Q4295075
Recommended article: Nonoverlapping pairs of explicit inversive congruential pseudorandom numbers
description: scientific article; zbMATH DE number 482261