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

Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is well-known that for every N≥ 1 and d≥ 1 there exist point sets x1, ⋯, xN∈ [0, 1]d whose discrepancy with respect to the Lebesgue measure is of order at most (log N)d - 1N-1. In a more general setting, the first author proved together with Josef Dick that for any normalized measure μ on [0, 1 ]d there exist points x1, ⋯, xN whose discrepancy with respect to μ is of order at most (log N)( 3 d + 1 ) / 2N- 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 μ there even exist points having discrepancy of order at most (logN)d-12N-1, which is almost as good as the discrepancy bound in the case of the Lebesgue measure.

Original languageEnglish (US)
Title of host publicationMonte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016
EditorsPeter W. Glynn, Art B. Owen
PublisherSpringer New York LLC
Pages169-180
Number of pages12
ISBN (Print)9783319914350
DOIs
StatePublished - Jan 1 2018
Event12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016 - Stanford, United States
Duration: Aug 14 2016Aug 19 2016

Publication series

NameSpringer Proceedings in Mathematics and Statistics
Volume241
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Other

Other12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016
CountryUnited States
CityStanford
Period8/14/168/19/16

Keywords

  • Gates of Hell
  • Low-discrepancy sequences
  • Non-uniform sampling
  • Tusnády’s problem
  • combinatorial discrepancy

Fingerprint Dive into the research topics of 'Tusnády’s problem, the transference principle, and non-uniform QMC sampling'. Together they form a unique fingerprint.

  • Cite this

    Aistleitner, C., Bilyk, D., & Nikolov, A. (2018). Tusnády’s problem, the transference principle, and non-uniform QMC sampling. In P. W. Glynn, & A. B. Owen (Eds.), Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016 (pp. 169-180). (Springer Proceedings in Mathematics and Statistics; Vol. 241). Springer New York LLC. https://doi.org/10.1007/978-3-319-91436-7_8