Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability

DOI10.1515/UDT-2018-0004MaRDI QIDQ5230692zbMATH OpenOpenAlexFDO

Authors Mario Neumüller, Friedrich Pillichshammer

Publication date 28 August 2019

Published in Uniform distribution theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1605.00378

zbMATH Keywords

quasi-Monte Carlostar discrepancypolynomial tractabilitydigital Kronecker-sequence

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45) Special sequences (11K31)

Abstract: The star discrepancy $D_N^{\ast }(mathcalP)$ is a quantitative measure for the irregularity of distribution of a finite point set $mathcalP$ 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 $Nge2$ there are point sets $mathcalP$ in $[0,1{)}^d$ with $|mathcalP|=N$ and $D_N^{\ast }(mathcalP)=O((logN{)}^{d-1}/N)$. However, for small $N$ compared to the dimension $d$ this asymptotically excellent bound is useless (e.g. for $Nle{me}^{d-1}$). In 2001 it has been shown by Heinrich, Novak, Wasilkowski and Wo'{z}niakowski that for every integer $Nge2$ there exist point sets $mathcalP$ in $[0,1{)}^d$ with $|mathcalP|=N$ and $D_N^{\ast }(mathcalP)leCsqrtd/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 are known. Quite recently L"obbe studied lacunary subsequences of Kronecker's $$-sequence and showed a metrical discrepancy bound of the form $Csqrtd(logd)/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.

Recommendations

• Metrical lower bounds on the discrepancy of digital Kronecker-sequences
• A metrical lower bound on the star discrepancy of digital sequences
• Metrical results on the discrepancy of Halton-Kronecker sequences
• On the inverse of the discrepancy for infinite dimensional infinite sequences
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers

Cited in

(5)

• A generalization of NUT digital (0,1)-sequences and best possible lower bounds for star discrepancy
• A note on the existence of sequences with small star discrepancy
• Metrical lower bounds on the discrepancy of digital Kronecker-sequences
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Discrepancy of Digital Sequences: New Results on a Classical QMC Topic

This page was built for publication: Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230692)