<abstract xmlns="http://www.w3.org/1999/xhtml">The star discrepancy <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0004_eq_001.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><msubsup><mi>D</mi><mi>N</mi><mo>*</mo></msubsup><mrow><mo>(</mo><mi>𝒫</mi><mo>)</mo></mrow></math><tex-math>$D_N^* \left( {\cal P} \right)$</tex-math></alternatives></inline-formula> is a quantitative measure for the irregularity of distribution of a finite point set <italic>𝒫</italic> in the multi-dimensional unit cube which is intimately related to the integration error of quasi-Monte Carlo algorithms. It is known that for every integer <italic>N ≥</italic> 2 there are point sets <italic>𝒫</italic> in [0, 1)<italic>d</italic> with <italic>|𝒫|</italic> = <italic>N</italic> and <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0004_eq_002.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><msubsup><mi>D</mi><mi>N</mi><mo>*</mo></msubsup><mrow><mo>(</mo><mi>𝒫</mi><mo>)</mo></mrow><mo>=</mo><mi>O</mi><mrow><mo>(</mo><mrow><msup><mrow><mrow><mo>(</mo><mrow><mo>log</mo><mi> </mi><mi>N</mi></mrow><mo>)</mo></mrow></mrow><mrow><mi>d</mi><mo>-</mo><mn>1</mn></mrow></msup><mo>/</mo><mi>N</mi></mrow><mo>)</mo></mrow></math><tex-math>$D_N^* \left( {\cal P} \right) = O\left( {\left( {\log \,N} \right)^{d - 1} /N} \right)$</tex-math></alternatives></inline-formula>. However, for small <italic>N</italic> compared to the dimension <italic>d</italic> this asymptotically excellent bound is useless (e.g., for <italic>N ≤</italic> e<italic>d</italic>−1).In 2001 it has been shown by Heinrich, Novak, Wasilkowski and Woźniakowski that for every integer <italic>N ≥</italic> 2there exist point sets <italic>𝒫</italic> in [0, 1)<italic>d</italic> with <italic>|𝒫|</italic> = <italic>N</italic> and <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0004_eq_003.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><msubsup><mi>D</mi><mi>N</mi><mo>*</mo></msubsup><mrow><mo>(</mo><mi>𝒫</mi><mo>)</mo></mrow><mo>≤</mo><mi>C</mi><msqrt><mrow><mi>d</mi><mo>/</mo><mi>N</mi></mrow></msqrt></math><tex-math>$D_N^* \left( {\cal P} \right) \le C\sqrt {d/N}$</tex-math></alternatives></inline-formula>. Although not optimal in an asymptotic sense in <italic>N</italic>, this upper bound has a much better (and even optimal) dependence on the dimension <italic>d</italic>.Unfortunately the result by Heinrich et al. and also later variants thereof by other authors are pure existence results and until now no explicit construction of point sets with the above properties is known. Quite recently Löbbe studied lacunary subsequences of Kronecker’s (<italic>n</italic><bold>α</bold>)-sequence and showed a metrical discrepancy bound of the form <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2018-0004_eq_004.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mi>C</mi><msqrt><mrow><mi>d</mi><mrow><mo>(</mo><mrow><mo>log</mo><mi> </mi><mi>d</mi></mrow><mo>)</mo></mrow><mo>/</mo><mi>N</mi></mrow></msqrt></math><tex-math>$C\sqrt {d\left({\log \,d} \right)/N}$</tex-math></alternatives></inline-formula> with implied absolute constant <italic>C></italic> 0 independent of <italic>N</italic> and <italic>d</italic>.In this paper we show a corresponding result for digital Kronecker sequences, which are a non-archimedean analog of classical Kronecker sequences.</abstract>

The star discrepancy DN*(𝒫)$D_N^* \left( {\cal P} \right)$ is a quantitative measure for the irregularity of distribution of a finite point set 𝒫 in the multi-dimensional unit cube which is intimately related to the integration error of quasi-Monte Carlo algorithms. It is known that for every integer N ≥ 2 there are point sets 𝒫 in [0, 1)d with |𝒫| = N and DN*(𝒫)=O((log N)d-1/N)$D_N^* \left( {\cal P} \right) = O\left( {\left( {\log \,N} \right)^{d - 1} /N} \right)$. However, for small N compared to the dimension d this asymptotically excellent bound is useless (e.g., for N ≤ ed−1).In 2001 it has been shown by Heinrich, Novak, Wasilkowski and Woźniakowski that for every integer N ≥ 2there exist point sets 𝒫 in [0, 1)d with |𝒫| = N and DN*(𝒫)≤Cd/N$D_N^* \left( {\cal P} \right) \le C\sqrt {d/N}$. Although not optimal in an asymptotic sense in N, this upper bound has a much better (and even optimal) dependence on the dimension d.Unfortunately the result by Heinrich et al. and also later variants thereof by other authors are pure existence results and until now no explicit construction of point sets with the above properties is known. Quite recently Löbbe studied lacunary subsequences of Kronecker’s (nα)-sequence and showed a metrical discrepancy bound of the form Cd(log d)/N$C\sqrt {d\left({\log \,d} \right)/N}$ with implied absolute constant C> 0 independent of N and d.In this paper we show a corresponding result for digital Kronecker sequences, which are a non-archimedean analog of classical Kronecker sequences.

Metrical Star Discrepancy Bounds for Lacunary Subsequences of Digital Kronecker-Sequences and Polynomial Tractability

Department of Financial Mathematics and Applied Number Theory

Uniform distribution theory

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

The star discrepancy DN*(𝒫)$D_N^* \left( {\cal P} \right)$ is a quantitative measure for the irregularity of distribution of a finite point set 𝒫 in the...

Metrical Star Discrepancy Bounds for Lacunary Subsequences of Digital Kronecker-Sequences and Polynomial Tractability

Published Online: Jul 20, 2018

Page range: 65 - 86

Received: Sep 28, 2016

Accepted: Nov 09, 2017

DOI: https://doi.org/10.1515/udt-2018-0004

Keywords
star discrepancy, digital Kronecker-sequence, polynomial tractability, quasi-Monte Carlo

© 2018 Mario Neumüller et al., published by Sciendo

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

Metrical Star Discrepancy Bounds for Lacunary Subsequences of Digital Kronecker-Sequences and Polynomial Tractability

Published Online: Jul 20, 2018

Page range: 65 - 86

Received: Sep 28, 2016

Accepted: Nov 09, 2017

DOI: https://doi.org/10.1515/udt-2018-0004

Keywordsstar discrepancy, digital Kronecker-sequence, polynomial tractability, quasi-Monte Carlo

© 2018 Mario Neumüller et al., published by Sciendo

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

Keywords
star discrepancy, digital Kronecker-sequence, polynomial tractability, quasi-Monte Carlo