arXiv Analytics

Sign in

arXiv:1703.06127 [math.CO]AbstractReferencesReviewsResources

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

Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov

Published 2017-03-17Version 1

It is well-known that for every $N \geq 1$ and $d \geq 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-\frac12} N^{-1}$, which is almost as good as the discrepancy bound in the case of the Lebesgue measure.

Related articles: Most relevant | Search more
arXiv:1302.3507 [math.CO] (Published 2013-02-14)
Discrepancy of random graphs and hypergraphs
arXiv:math/0312022 [math.CO] (Published 2003-12-01, updated 2004-04-08)
Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap
arXiv:math/0404559 [math.CO] (Published 2004-04-30, updated 2004-05-10)
Graphs and Hermitian matrices: discrepancy and singular values