A note on the existence of sequences with small star discrepancy

DOI10.1016/J.JCO.2007.01.004MaRDI QIDQ2465294zbMATH OpenOpenAlexFDO

Authors Josef Dick

Publication date 9 January 2008

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2007.01.004

zbMATH Keywords

sequencestar discrepancytractability

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45)

Review text

By a well-known result of \textit{S. Heinrich} et al. [Acta Arith. 96, 279--302 (2001; Zbl 0972.11065)] there exists a set \(P\) of \(n\) points in \([0,1]^{s}\) such that the star-discrepancy \(D^{*}_{n,s}\) is \(\leq C \cdot \sqrt{\frac{s}{n}}\) (for some constant \(C\)). In the present paper this result is extended to infinite sequences \(P\) and a similar upper bound for \(D^{*}_{n,s} (P)\) (with an additional logarithmic factor) is obtained.

Recommendations

• On the inverse of the discrepancy for infinite dimensional infinite sequences
• Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability
• Component-by-component construction of low-discrepancy point sets of small size
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• scientific article; zbMATH DE number 5049855

Cites work

• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• Constructions of (t,m,s)-nets and (t,s)-sequences
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• Some open problems concerning the star-discrepancy
• The existence of good extensible polynomial lattice rules
• The existence of good extensible rank-1 lattices
• The inverse of the star-discrepancy depends linearly on the dimension

Cited in

(17)

• Polynomial discrepancy of sequences
• Some open problems concerning the star-discrepancy
• On the inverse of the discrepancy for infinite dimensional infinite sequences
• On the arrangement of point sets in the unit interval
• On the star discrepancy of sequences in the unit interval
• Minimizing the \(L_{2}\) and \(L_{\infty}\) star discrepancies of a single point in the unit hypercube
• Tractability properties of the weighted star discrepancy
• Probabilistic star discrepancy bounds for double infinite random matrices
• Some results on the complexity of numerical integration
• Component-by-component construction of low-discrepancy point sets of small size
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Discrepancy of Digital Sequences: New Results on a Classical QMC Topic
• Entropy, Randomization, Derandomization, and Discrepancy
• Low-discrepancy point sets for non-uniform measures
• Consistency of Markov chain quasi-Monte Carlo on continuous state spaces
• Covering numbers, dyadic chaining and discrepancy
• New bounds for the extreme and the star discrepancy of double-infinite matrices

This page was built for publication: A note on the existence of sequences with small star discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465294)