Low-discrepancy point sets for non-uniform measures

Christoph Aistleitner ¹   ; Josef Dick ¹

¹ School of Mathematics and Statistics University of New South Wales Sydney, NSW 2052, Australia

Acta Arithmetica, Tome 163 (2014) no. 4, pp. 345-369

Résumé

We prove several results concerning the existence of low-discrepancy point sets with respect to an arbitrary non-uniform measure $\mu $ on the $d$-dimensional unit cube. We improve a theorem of Beck, by showing that for any $d \geq 1$, $N \geq 1,$ and any non-negative, normalized Borel measure $\mu $ on $[0,1]^d$ there exists a point set $x_1, \dots , x_N \in [0,1]^d$ whose star-discrepancy with respect to $\mu $ is of order $$ D_N^*(x_1, \dots , x_N; \mu ) \ll \frac {(\log N)^{(3d+1)/2}}{N}. $$ For the proof we use a theorem of Banaszczyk concerning the balancing of vectors, which implies an upper bound for the linear discrepancy of hypergraphs. Furthermore, the theory of large deviation bounds for empirical processes indexed by sets is discussed, and we prove a numerically explicit upper bound for the inverse of the discrepancy for Vapnik–Chervonenkis classes. Finally, using a recent version of the Koksma–Hlawka inequality due to Brandolini, Colzani, Gigante and Travaglini, we show that our results imply the existence of cubature rules yielding fast convergence rates for the numerical integration of functions having discontinuities of a certain form.

Détail

DOI : 10.4064/aa163-4-4

Keywords: prove several results concerning existence low discrepancy point sets respect arbitrary non uniform measure d dimensional unit cube improve theorem beck showing geq geq non negative normalized borel measure there exists point set dots whose star discrepancy respect order * dots frac log proof theorem banaszczyk concerning balancing vectors which implies upper bound linear discrepancy hypergraphs furthermore theory large deviation bounds empirical processes indexed sets discussed prove numerically explicit upper bound inverse discrepancy vapnik chervonenkis classes finally using recent version koksma hlawka inequality due brandolini colzani gigante travaglini results imply existence cubature rules yielding fast convergence rates numerical integration functions having discontinuities certain form