On lower bounds for the L₂-discrepancy

DOI10.1016/J.JCO.2010.11.002MaRDI QIDQ2431333zbMATH OpenOpenAlexFDO

Authors Aicke Hinrichs, Lev Markhasin

Publication date 13 April 2011

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

Full work available at URL https://arxiv.org/abs/1010.1950

zbMATH Keywords

discrepancyHaar systemnumerical integrationquasi-Monte Carlo algorithms

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Monte Carlo methods (65C05) Numerical integration (65D30)

Abstract: The L_2-discrepancy measures the irregularity of the distribution of a finite point set. In this note we prove lower bounds for the L_2 discrepancy of arbitrary N-point sets. Our main focus is on the two-dimensional case. Asymptotic upper and lower estimates of the L_2-discrepancy in dimension 2 are well-known and are of the sharp order sqrt(log N). Nevertheless the gap in the constants between the best known lower and upper bounds is unsatisfactory large for a two-dimensional problem. Our lower bound improves upon this situation considerably. The main method is an adaption of the method of K. F. Roth using the Fourier coefficients of the discrepancy function with respect to the Haar basis.

Recommendations

• Lower bounds for \(L_1\) discrepancy
• On the \(L_2\)-discrepancy for anchored boxes
• ON IRREGULARITIES OF DISTRIBUTION II
• The exponent of discrepancy is at least 1. 0669
• \(L_2\) discrepancy of generalized Zaremba point sets

Cites work

• \(L_2\) discrepancy of generalized two-dimensional Hammersley point sets scrambled with arbitrary permutations
• Discrepancy of Hammersley points in Besov spaces of dominating mixed smoothness
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• Note on irregularities of distribution
• On irregularities of distribution
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.

Cited in

(25)

• The exponent of discrepancy is at least 1. 0669
• On the \(L_2\)-discrepancy for anchored boxes
• BMO and exponential Orlicz space estimates of the discrepancy function in arbitrary dimension
• A lower bound for two-dimensional Lebesgue constants
• On Proinov's lower bound for the diaphony
• A note on the periodic \(L_2\)-discrepancy of Korobov's \(p\)-sets
• A new lower bound for wrap-around \(L_2\)-discrepancy on two and three mixed level factorials
• Proof techniques in quasi-Monte Carlo theory
• Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension
• Discrepancy of point sequences on fractal sets
• An improved lower bound for the \(L_2\)-discrepancy
• Exponential Squared Integrability of the Discrepancy Function in Two Dimensions
• scientific article; zbMATH DE number 740357 (Why is no real title available?)
• The exponent of discrepancy is at most 1.4778...
• The inverse of the star-discrepancy depends linearly on the dimension
• On the discrepancy of combinatorial rectangles
• scientific article; zbMATH DE number 822312 (Why is no real title available?)
• Discrepancy of line segments for general lattice checkerboards
• \(L_p\)- and \(S_{p,q}^rB\)-discrepancy of (order \(2\)) digital nets
• Lower bounds for \(L_1\) discrepancy
• Uniformity of point samples in metric spaces using gap ratio
• Lower bounds for the directional discrepancy with respect to an interval of rotations
• Fibonacci sets and symmetrization in discrepancy theory
• Optimal and typical \(L^2\) discrepancy of 2-dimensional lattices
• On the discrepancy function in arbitrary dimension, close to L^1

This page was built for publication: On lower bounds for the \(L_2\)-discrepancy

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