<abstract xmlns="http://www.w3.org/1999/xhtml">

We provide an algorithm to approximate a finitely supported discrete measure <italic>μ</italic> by a measure <italic>νN</italic> corresponding to a set of <italic>N</italic> points so that the total variation between <italic>μ</italic> and <italic>νN</italic> has an upper bound. As a consequence if <italic>μ</italic> is a (finite or infinitely supported) discrete probability measure on [0, 1]<italic>d </italic>with a sufficient decay rate on the weights of each point, then <italic>μ</italic> can be approximated by <italic>νN</italic> with total variation, and hence star-discrepancy, bounded above by (log <italic>N</italic>)<italic>N−</italic>1. Our result improves, in the discrete case, recent work by Aistleitner, Bilyk, and Nikolov who show that for any normalized Borel measure <italic>μ</italic>, there exist finite sets whose star-discrepancy with respect to <italic>μ</italic> is at most <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2021-0003_eq_001.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><msup><mrow><mrow><mrow><mo>(</mo><mrow><mo>log</mo><mi> </mi><mi>N</mi></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mi>d</mi><mo>−</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></msup><msup><mrow><mi>N</mi></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup></mrow></math>
<tex-math>{\left( {\log \,N} \right)^{d - {1 \over 2}}}{N^{ - 1}}</tex-math>
</alternatives>
</inline-formula>. Moreover, we close a gap in the literature for discrepancy in the case <italic>d</italic> =1 showing both that Lebesgue is indeed the hardest measure to approximate by finite sets and also that all measures without discrete components have the same order of discrepancy as the Lebesgue measure.
</abstract>

We provide an algorithm to approximate a finitely supported discrete measure μ by a measure νN corresponding to a set of N points so that the total variation between μ and νN has an upper bound. As a consequence if μ is a (finite or infinitely supported) discrete probability measure on [0, 1]d with a sufficient decay rate on the weights of each point, then μ can be approximated by νN with total variation, and hence star-discrepancy, bounded above by (log N)N−1. Our result improves, in the discrete case, recent work by Aistleitner, Bilyk, and Nikolov who show that for any normalized Borel measure μ, there exist finite sets whose star-discrepancy with respect to μ is at most 


(log N)d−12N−1
{\left( {\log \,N} \right)^{d - {1 \over 2}}}{N^{ - 1}}

. Moreover, we close a gap in the literature for discrepancy in the case d =1 showing both that Lebesgue is indeed the hardest measure to approximate by finite sets and also that all measures without discrete components have the same order of discrepancy as the Lebesgue measure.

Families of Well Approximable Measures

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Families of Well Approximable Measures"}

We provide an algorithm to approximate a finitely supported discrete measure μ by a measure νN corresponding to a set of N points so that the total variation...

Families of Well Approximable Measures

Publié en ligne: 30 oct. 2021

Pages: 53 - 70

Reçu: 02 sept. 2020

Accepté: 13 avr. 2021

DOI: https://doi.org/10.2478/udt-2021-0003

Mots clés
star-discrepancy, low-discrepancy sequences, Borel Measures, total variation

© 2021 Samantha Fairchild et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Families of Well Approximable Measures

Publié en ligne: 30 oct. 2021

Pages: 53 - 70

Reçu: 02 sept. 2020

Accepté: 13 avr. 2021

DOI: https://doi.org/10.2478/udt-2021-0003

Mots clésstar-discrepancy, low-discrepancy sequences, Borel Measures, total variation

© 2021 Samantha Fairchild et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Mots clés
star-discrepancy, low-discrepancy sequences, Borel Measures, total variation