Low-discrepancy point sets for non-uniform measures

Understand

In the present paper 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--\v{C}ervonenkis classes.