Hellekalek, Peter; Leeb, Hannes Dyadic diaphony. (English) Zbl 0868.11034 Acta Arith. 80, No. 2, 187-196 (1997). A priori correlation analysis of pseudorandom numbers is based upon the assessment of finite sequences of points in the \(s\)-dimensional unit cube \([0,1[^s\) by certain figures of merit. Currently, the two most important quantities for this task are discrepancy [see H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM (1992; Zbl 0761.65002)] and the spectral test [see R. R. Coveyou and R. D. MacPherson, J. ACM 14, 100-119 (1967; Zbl 0155.22801)]. In what concerns the practice of pseudorandom number generation, both quantities have their limitations. Discrepancy cannot be computed for samples in higher dimensions due to its high complexity. The spectral test is restricted to samples with lattice structure. Several interesting variations of the spectral test like the Walsh spectral test of S. Tezuka [Commun. ACM 30, 731-735 (1987; Zbl 0632.65003)] or Compagner’s concept of correlation coefficients [A. Compagner, Operational conditions for random-number generation, Phys. Rev. E 52, 5634-5645 (1995)] do not yield computationally efficient quantities. The concept of the weighted spectral test of the first author [Correlations between pseudorandom numbers: theory and numerical practice. In: P. Hellekalek, G. Larcher, and P. Zinterhof (eds.), Proceedings of the 1st Salzburg Minisymposium on Pseudorandom Number Generation and Quasi-Monte Carlo Methods, Salzburg, Nov 18, 1994, volume ACPC/TR 95-4 of Technical Report Series, pages 43-73. ACPC – Austrian Center for Parallel Computation, University of Vienna, Austria (1995); and On correlation analysis of pseudorandom numbers. Submitted to Proceedings of the Second International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Salzburg, July 9-12, 1996 (1996)] allows to define numerical quantities that are appropriate for the same number-theoretic analysis of pseudorandom number generators as discrepancy, provide for efficient practical computation of their value even in higher dimensions \(s\), are not restricted to sequences \(\omega\) with lattice structure, and possess a statistical background, like a known expectation, variance or asymptotic distribution. In this paper we present a realization of this concept, the dyadic diaphony. It is a numerical quantity that measures the irregularity of the distribution of sequences in the \(s\)-dimensional unit cube, similar to discrepancy. We show that a sequence is uniformly distributed in the \(s\)-dimensional unit cube \([0,1[^s\) if and only if the dyadic diaphony of its initial segments tends to zero. From our proof Weyl’s criterion for the Walsh function system and the inequality of Erdös-Turán-Koksma for the dyadic diaphony will follow as corollaries. Further, we prove a fundamental identity for the dyadic diaphony that allows its computation in \(O(s\cdot N^2)\) steps, for any \(N\) dyadic rational points in \([0,1[^s\). We point out its relation to the Walsh spectral test of Tezuka (loc. cit.) and compute its value for regular dyadic grids. Reviewer: P.Hellekalek (Salzburg) Cited in 6 ReviewsCited in 11 Documents MSC: 11K38 Irregularities of distribution, discrepancy 11K45 Pseudo-random numbers; Monte Carlo methods 65C10 Random number generation in numerical analysis Keywords:uniform distribution of sequences; discrepancy; pseudorandom number generation; weighted spectral test; dyadic diaphony; irregularity of the distribution of sequences; higher-dimensional unit cube; Weyl’s criterion for the Walsh function system; inequality of Erdös-Turán-Koksma; Walsh spectral test; regular dyadic grids Citations:Zbl 0761.65002; Zbl 0155.22801; Zbl 0632.65003 PDFBibTeX XMLCite \textit{P. Hellekalek} and \textit{H. Leeb}, Acta Arith. 80, No. 2, 187--196 (1997; Zbl 0868.11034) Full Text: DOI EuDML