{
"id": "1703.06127",
"version": "v1",
"published": "2017-03-17T17:43:59.000Z",
"updated": "2017-03-17T17:43:59.000Z",
"title": "Tusnády's problem, the transference principle, and non-uniform QMC sampling",
"authors": [
"Christoph Aistleitner",
"Dmitriy Bilyk",
"Aleksandar Nikolov"
],
"comment": "11 pages",
"categories": [
"math.CO",
"cs.CC",
"math.NA",
"math.PR"
],
"abstract": "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.",
"revisions": [
{
"version": "v1",
"updated": "2017-03-17T17:43:59.000Z"
}
],
"analyses": {
"keywords": [
"transference principle",
"non-uniform qmc sampling",
"tusnádys problem",
"discrepancy",
"lebesgue measure"
],
"note": {
"typesetting": "TeX",
"pages": 11,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}