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

Christoph Aistleitner; Dmitriy Bilyk; Aleksandar Nikolov

doi:10.1007/978-3-319-91436-7_8

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

Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

It is well-known that for every N≥ 1 and d≥ 1 there exist point sets x₁, ⋯, x_N∈ [0, 1]^d whose discrepancy with respect to the Lebesgue measure is of order at most (log N)^d ^- ¹N^-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 x₁, ⋯, x_N whose discrepancy with respect to μ is of order at most (log N)⁽ ³ ^d ⁺ ¹ ⁾ ^/ ²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 μ 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 language	English (US)
Title of host publication	Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016
Editors	Peter W. Glynn, Art B. Owen
Publisher	Springer New York LLC
Pages	169-180
Number of pages	12
ISBN (Print)	9783319914350
DOIs	https://doi.org/10.1007/978-3-319-91436-7_8
State	Published - 2018
Event	12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016 - Stanford, United States Duration: Aug 14 2016 → Aug 19 2016

Publication series

Name	Springer Proceedings in Mathematics and Statistics
Volume	241
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Other

Other	12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016
Country/Territory	United States
City	Stanford
Period	8/14/16 → 8/19/16

Bibliographical note

Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.

Keywords

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

Access

10.1007/978-3-319-91436-7_8

OpenUrl availability

Full text

Cite this

Tusnády’s problem, the transference principle, and non-uniform QMC sampling. / Aistleitner, Christoph; Bilyk, Dmitriy; Nikolov, Aleksandar.
Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016. ed. / Peter W. Glynn; Art B. Owen. Springer New York LLC, 2018. p. 169-180 (Springer Proceedings in Mathematics and Statistics; Vol. 241).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aistleitner, C, Bilyk, D & Nikolov, A 2018, Tusnády’s problem, the transference principle, and non-uniform QMC sampling. in PW Glynn & AB Owen (eds), Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016. Springer Proceedings in Mathematics and Statistics, vol. 241, Springer New York LLC, pp. 169-180, 12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016, Stanford, United States, 8/14/16. https://doi.org/10.1007/978-3-319-91436-7_8

@inproceedings{2968132bdefd473db55130f58d60969d,

title = "Tusn{\'a}dy{\textquoteright}s problem, the transference principle, and non-uniform QMC sampling",

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.",

keywords = "Gates of Hell, Low-discrepancy sequences, Non-uniform sampling, Tusn{\'a}dy{\textquoteright}s problem, combinatorial discrepancy",

author = "Christoph Aistleitner and Dmitriy Bilyk and Aleksandar Nikolov",

note = "Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016 ; Conference date: 14-08-2016 Through 19-08-2016",

year = "2018",

doi = "10.1007/978-3-319-91436-7_8",

language = "English (US)",

isbn = "9783319914350",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer New York LLC",

pages = "169--180",

editor = "Glynn, {Peter W.} and Owen, {Art B.}",

booktitle = "Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016",

}

TY - GEN

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

AU - Aistleitner, Christoph

AU - Bilyk, Dmitriy

AU - Nikolov, Aleksandar

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Gates of Hell

KW - Low-discrepancy sequences

KW - Non-uniform sampling

KW - Tusnády’s problem

KW - combinatorial discrepancy

UR - http://www.scopus.com/inward/record.url?scp=85049890770&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049890770&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-91436-7_8

DO - 10.1007/978-3-319-91436-7_8

M3 - Conference contribution

AN - SCOPUS:85049890770

SN - 9783319914350

T3 - Springer Proceedings in Mathematics and Statistics

SP - 169

EP - 180

BT - Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2016

A2 - Glynn, Peter W.

A2 - Owen, Art B.

PB - Springer New York LLC

T2 - 12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2016

Y2 - 14 August 2016 through 19 August 2016

ER -

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

Abstract

Publication series

Other

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this