×

zbMATH — the first resource for mathematics

General discrepancy estimates. III: The Erdös-Turán-Koksma inequality for the Haar function system. (English) Zbl 0827.11047
[For Parts I, II see Acta. Arith. 67, 209-218 (1994; Zbl 0805.11055); and ibid., 313-322 (1994; Zbl 0813.11046).]
The inequality of Erdös-Turán-Koksma is a central quantitative result in the theory of uniform distribution of sequences modulo one. It gives an upper bound of the discrepancy of a sequence \(\omega= (x_n )_{n\geq 0}\) in the \(s\)-dimensional unit cube \([0, 1[^s\) in terms of Weyl sums \[ S_N (\chi_{\mathbf k}, \omega):= {\textstyle {1\over N}} \sum_{n=0}^{N-1} \chi_{\mathbf k} (x_n), \qquad {\mathbf k}\neq \mathbf{0}, \] relative to some function system \({\mathcal F}= \{\chi_{\mathbf k}\}\) on \([0, 1[^s\). If we choose for \({\mathcal F}\) the system of trigonometric functions, we obtain the classical inequality of Erdös- Turán-Koksma [see L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley and Sons, New York (1974; Zbl 0281.10001), p. 112, 114, 116].
Niederreiter has proved important variants of the Erdös-Turán-Koksma inequality for finite rational point sets, as they appear in pseudorandom number generation and quasi-Monte Carlo integration. Due to Niederreiter’s results, theoretical analysis of the serial test has been feasible for most types of uniform pseudorandom number generators (see the comprehensive monograph of H. Niederreiter [Random number generation and quasi-Monte Carlo methods, SIAM (1992; Zbl 0761.65002)] and the recent surveys by J. Eichenauer-Herrmann [Int. Stat. Rev. 60, 167-176 (1992; Zbl 0766.65002); and Z. Angew. Math. Mech. 73, T 644– T 647 (1993; Zbl 0796.11029)] and H. Niederreiter [New methods for pseudorandom number and pseudorandom vector generation, in Proc. 1992 Winter Simulation Conf., Arlington, Va., 1992, 264-269, IEEE Press, Piscataway, N.J. (1992)).
In this paper we continue the study of general discrepancy estimates begun by the author in Parts I–II (loc. cit.). We prove the inequality of Erdös-Turán-Koksma for generalized Haar function systems, for the extreme and the star discrepancy of arbitrary sequences in \([0, 1[^s\). This extends results of Part I (loc. cit.). Further, we show the existence of the inequality of Erdös-Turán-Koksma for the isotropic discrepancy, for generalized Haar and Walsh function systems. In the appendix, we indicate how to extend our results to more general systems of numeration. Finally, we survey interesting related results.

MSC:
11K38 Irregularities of distribution, discrepancy
65C10 Random number generation in numerical analysis
42C10 Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.)
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Cochrane, T.: Trigonometric approximation and uniform distribution modulo one. Proc. Amer. Math. Soc.103, 695-702 (1988). · Zbl 0667.10031
[2] Eichenauer-Herrmann, J.: Inversive congruential pseudorandom numbers: a tutorial. Int. Statist. Rev.60, 167-176 (1992). · Zbl 0766.65002
[3] Eichenauer-Herrmann, J.: Inverive congruential pseudorandom numbers. Z. angew. Math. Mech.73, T644-T647 (1993). · Zbl 0796.11029
[4] Faure, H.: Discrépances des suites associées à un système de numération (un dimension un). Bull. Soc. Math. France109, 143-182 (1981). · Zbl 0488.10052
[5] Grabner, P. J.: Erdös-Turán type discrepancy bounds. Mh. Math.111, 127-135 (1991). · Zbl 0719.11046
[6] Grabner, P. J., Tichy, R. F.: Remark on an inequality of Erdös-Turán-Koksma. Anz. Österr. Akad. Wiss. Math.-Natur. Kl.127, 15-22 (1990). · Zbl 0715.11037
[7] Hellekalek, P.: Regularities in the distribution of special sequences. J. Number Th.18, 41-55 (1984). · Zbl 0531.10055
[8] Hellekalek, P.: General discrepancy estimates: the Walsh function system. Acta. Arith. To appear (1993). · Zbl 0805.11055
[9] Hellekalek, P.: General discrepancy estimates II: the Haar function system. Acta Arith. To appear (1993).
[10] Kuipers, L., Niedrreiter, H.: Uniform Distribution of Sequences. New York: Wiley 1974.
[11] Larcher, G., Schmid, W. C., Wolf, R.: Representation of functions as Walsh series to different bases and an application to the numerical integration of high-dimensional Walsh series. Math. Comp. To appear (1993). · Zbl 0821.42017
[12] Larcher, G., Traunfellner, C.: On the numerical integration of Walsh series by number-theoretical methods. Math. Comp.63, 277-291 (1994). · Zbl 0806.65013
[13] Niederreiter, H.: On the distribution of pseudo-random numbers generated by the linear congruential method. III. Math. Comp.30, 571-597 (1976). · Zbl 0342.65002
[14] Niederreiter, H.: Pseudo-random numbers and optimal coefficients. Adv. in Math.26, 99-181 (1977). · Zbl 0366.65004
[15] Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc.84, 957-1041 (1978). · Zbl 0404.65003
[16] Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Österr. Akad. Wiss. Math.-Naturw. Kl. II,195, 109-138 (1986). · Zbl 0616.10040
[17] Niederreiter, H.: The distribution of values of Kloosterman sums. Arch. Math.56, 270-277 (1991). · Zbl 0752.11055
[18] Niederreiter, H.: New methods for pseudorandom number and pseudorandom vector generation. In: Proc. 1992 Winter Simulation Conference (Arlington, Va., 1992), pp. 264-269. Piscataway, N. J.: IEEE Press. 1992. · Zbl 0849.11055
[19] Niedereiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Philadelphia: SIAM. 1992.
[20] Niederreiter, H.: Pseudorandom vector generation by the inversive method. ACM Trans. Modelling and Computer Simulation. To appear. (1993). · Zbl 0847.11039
[21] Niederreiter, H., Philipp, W.: Berry-Esseen bounds and a theorem of Erdös and Turán on uniform distribution mod 1. Duke Math. J.40, 633-649 (1973). · Zbl 0273.10043
[22] Niederreiter, H., Wills, J. M.: Diskrepanz und Distanz von Maßen bezüglich konvexer und Jordanscher Mengen. Math. Z.144, 125-134. (1975). · Zbl 0295.28028
[23] Schipp, F., Wade, W. R., Simon, P., Pál, J.: Walsh Series. An Introduction to Dyadic Harmonic Analysis. Bristol and New York: Adam Hilger. 1990. · Zbl 0727.42017
[24] Sobol’, I. M.: The distribution of points in a cube and the approximate evaluation of integrals. Zh. Vychsil. Math. i Mat. Fiz.7, 784-802 (1967).
[25] Sobol’, I. M.: Multidimensional Quadrature Formulas and Haar Functions. Moscow: Izdat. ?Nauka?. 1969. (In Russian). · Zbl 0195.16903
[26] Tezuka, S.: Walsh-spectral test for GFSR pseudorandom number generators. Comm. ACM.30, 731-735 (1987). · Zbl 0632.65003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.