Low-discrepancy and low-dispersion sequences. (English) Zbl 0651.10034

Let \({\mathfrak x}_ 1,{\mathfrak x}_ 2,..\). be a sequence of points in the unit cube \(I^ s=[0,1)^ s\), \(s\geq 1\). Let J be a subinterval of I and \(D(J;N)=A(J;N)-V(J)N\), where A(J;N) is the number of n, \(1\leq n\leq N\), with \({\mathfrak x}_ n\in J\) and V(J) is the volume of J. Then \(\Delta (N)=\sup_{J} | D(J;N)|\) is called the discrepancy of the first N terms of the sequence \({\mathfrak x}_ 1,{\mathfrak x}_ 2...\). Halton first constructed a low-discrepancy sequence such that \(\Delta (N)\leq c_ s(\log N)^ s+O(c \log N)^{s-1},\quad N\geq 2.\) The author obtains sequences in \(I^ s\) based on the theory of (t,s)-sequences with smallest constant \(c_ s\) that is currently known.
Reviewer: Wang Yuan


11K38 Irregularities of distribution, discrepancy
11K06 General theory of distribution modulo \(1\)
Full Text: DOI


[1] Faure, H., Discrépances de suites associées à un système de numération (en dimension un), Bull. Soc. Math. France, 109, 143-182 (1981) · Zbl 0488.10052
[2] Faure, H., Discrépance de suites associées à un système de numération (en dimension \(s)\), Acta Arith., 41, 337-351 (1982) · Zbl 0442.10035
[3] Halton, J. H., Berichtigung, Numer. Math., 2, 196 (1960)
[4] Hua, L. K.; Wang, Y., (Applications of Number Theory to Numerical Analysis (1981), Springer: Springer Berlin) · Zbl 0465.10045
[5] Kuipers, L.; Niederreiter, H., (Uniform Distribution of Sequences (1974), Wiley: Wiley New York) · Zbl 0281.10001
[6] Lambert, J. P., A sequence well dispersed in the unit square (1986), University of Alaska: University of Alaska Fairbanks, preprint · Zbl 0655.10055
[7] Larcher, G., The dispersion of a special sequence, Arch. Math., 47, 347-352 (1986) · Zbl 0584.10031
[8] Lidl, R.; Niederreiter, H., (Finite Fields (1983), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0554.12010
[9] Niederreiter, H., Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc., 84, 957-1041 (1978) · Zbl 0404.65003
[10] Niederreiter, H., A quasi-Monte Carlo method for the approximate computation of the extreme values of a function, (Studies in Pure Mathematics (To the Memory of Paul Turán) (1983), Birkhäuser: Birkhäuser Basel), 523-529 · Zbl 0527.65041
[11] Niederreiter, H., On a measure of denseness for sequences, (Topics in Classical Number Theory (Budapest, 1981). Topics in Classical Number Theory (Budapest, 1981), Colloquia Math. Soc. János Bolyai, Vol. 34 (1984), North-Holland: North-Holland Amsterdam), 1163-1208 · Zbl 0547.10045
[12] Niederreiter, H., Quasi-Monte Carlo methods for global optimization, (Proc. Fourth Pannonian Symp. on Math. Statistics. Proc. Fourth Pannonian Symp. on Math. Statistics, Bad Tatzmannsdorf, 1983 (1986), Reidel: Reidel Dordrecht), 251-267 · Zbl 0603.65043
[13] Niederreiter, H., Good lattice points for quasirandom search methods, (Prékopa, A.; Szelezsán, J.; Strazicky, B., System Modelling and Optimization. System Modelling and Optimization, Lecture Notes in Control and Information Sciences, Vol. 84 (1986), Springer: Springer Berlin), 647-654 · Zbl 0619.90066
[14] Niederreiter, H., Point sets and sequences with small discrepancy, Monatsh. Math., 104, 273-337 (1987) · Zbl 0626.10045
[15] Niederreiter, H.; McCurley, K., Optimization of functions by quasi-random search methods, Computing, 22, 119-123 (1979) · Zbl 0405.65042
[16] Peart, P., The dispersion of the Hammersley sequence in the unit square, Monatsh. Math., 94, 249-261 (1982) · Zbl 0484.10033
[17] Roth, K. F., On irregularities of distribution, Mathematika, 1, 73-79 (1954) · Zbl 0057.28604
[18] Schmidt, W. M., Irregularities of distribution. VII, Acta Arith., 21, 45-50 (1972) · Zbl 0244.10035
[19] Sobol’, I. M., The distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. i Mat. Fiz., 7, 784-802 (1967), [Russian]
[20] Sobol’, I. M., (Multidimensional Quadrature Formulas and Haar Functions (1969), Nauka: Nauka Moscow), [Russian] · Zbl 0195.16903
[21] Sobol’, I. M., On an estimate of the accuracy of a simple multidimensional search, Dokl. Akad. Nauk SSSR, 266, 569-572 (1982), [Russian] · Zbl 0534.41013
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.