On the average discrepancy of successive tuples of pseudo-random numbers over parts of the period
type: Item
instance of: scholarly article
title: On the average discrepancy of successive tuples of pseudo-random numbers over parts of the period
zbMATH Open document ID: 0932.11049
author: Gerhard Larcher
author: Jürgen Eichenauer-Herrmann
author: R. Wolf
published in: Monatshefte für Mathematik
publication date: 2000-03-19T00:00:00Z
review text: Let \(p\) be prime and \(g\in \mathbb{Z}_p[x]\) be a permutation polynomial of \(\mathbb{Z}_p\) with \(1\leq \deg(g)\leq p-2\). Define a sequence \((y_n)_{n\in \mathbb{Z}_p}\) by \(y_n= g(n)\) for all \(n\in \mathbb{Z}_p\) and set \(x_n= y_n/p\). We also define the nonoverlapping \(s\)-tuples \(x_n= (x_{sn}, x_{sn+1},\dots, x_{sn+s-1})\in [0,1)^s\) and the overlapping \(s\)-tuples \(x_n'= (x_n, x_{n+1},\dots, x_{n+s-1})\in [0,1)^s\). \textit{H. Niederreiter} [Monatsh. Math. 106, 149-159 (1988; Zbl 0652.65007)] gave an upper bound for the discrepancy of the first \(N\) \(s\)-tuples \(x_n'\) \((n=0,\dots, N-1)\) for any \(g\) of degree \(d\geq s+1\) and all \(N\) with \(1\leq N< p\). In this paper the authors consider the average value over the set \(P\) of all permutation polynomials of \(\mathbb{Z}_p\) of the discrepancy \(D_N^{(s)}(g)\) of non-overlapping \(s\)-tuples \(x_n\) \((n=0,\dots, N-1)\). They prove that if \(2\leq s<p/2\) and \(1\leq N\leq p\), then \[ \frac{1}{30} N^{-1/2}< \frac{1}{p!} \sum_{g\in P} D_N^{(s)}(g)< N^{-1/2} \biggl(\frac{2}{\pi} \log p+ \frac{7}{5} \biggr)^2\cdot \sqrt{\frac{p}{p-2s+1}}+ \frac{s}{p}. \] These estimates are also sharp up to logarithmic factors even for rather small parts of the period.
reviewed by: Yaochen Zhu
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 1295443
zbMATH Keywords: pseudo-random numbers
zbMATH Keywords: permutation polynomial
zbMATH Keywords: discrepancy
zbMATH Keywords: period
MaRDI profile type: Publication
full work available at URL: s006050050029
OpenAlex ID: W1966861476
DOI: 10.1007/S006050050029
Recommended article: Permutations with low discrepancy consecutive \(k\)-sums
Recommended article: Distribution of nonlinear congruential pseudorandom numbers modulo almost squarefree integers
Recommended article: How permutations displace points and stretch intervals
Recommended article: Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus
Recommended article: On the number of permutations with constraints on their cycle lengths
Recommended article: Permutations in Abelian groups and the sequence \(n!\pmod p\).
Recommended article: On the average distribution of pseudorandom numbers generated by nonlinear permutations
Recommended article: Average discrepancy, hyperplanes, and compound pseudorandom numbers
Recommended article: Equidistribution properties of nonlinear congruential pseudorandom numbers
Recommended article: On the Carlitz rank of permutations of \(\mathbb F_q\) and pseudorandom sequences
description: scientific article; zbMATH DE number 1295443