Tusnády's problem, the transference principle, and non-uniform QMC sampling

Abstract

It is well-known that for every $N\ge 1$ and $d\ge 1$ there exist point sets $x_1,\dots ,x_N\in [0,1{]}^d$ whose discrepancy with respect to the Lebesgue measure is of order at most $(\log N{)}^{d-1}{N}^{-1}$. In a more general setting, the first author proved together with Josef Dick that for any normalized measure $\mu$ on $[0,1{]}^d$ there exist points $x_1,\dots ,x_N$ whose discrepancy with respect to $\mu$ is of order at most $(\log N{)}^{(3d+1)/2}{N}^{-1}$. The proof used methods from combinatorial mathematics, and in particular a result of Banaszczyk on balancings of vectors. In the present note we use a version of the so-called transference principle together with recent results on the discrepancy of red-blue colorings to show that for any $\mu$ there even exist points having discrepancy of order at most $(\log N{)}^{d-\frac{1}{2}}{N}^{-1}$, which is almost as good as the discrepancy bound in the case of the Lebesgue measure.

11 pages

References in corpus (1)

• An Algorithm for Komlós Conjecture Matching Banaszczyk's bound