×

Dyadic diaphony. (English) Zbl 0868.11034

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.

MSC:

11K38 Irregularities of distribution, discrepancy
11K45 Pseudo-random numbers; Monte Carlo methods
65C10 Random number generation in numerical analysis
PDFBibTeX XMLCite
Full Text: DOI EuDML