Tractability properties of the weighted star discrepancy of the Halton sequence. (English) Zbl 1443.11152
The authors study the weighted star discrepancy of the Halton sequence and show that strong polynomial tractability is achieved. The weights \((\gamma_{j})\) are of product type and satisfy the mild growth condition \[ \sup_{d\geq 1}\max_{\emptyset\neq u \subseteq \{1,\ldots, d\}}\prod_{j\in u}(j\gamma_{j})<\infty. \] Similar results hold for various other digital sequences as well as for the weighted unanchored discrepancy.
Reviewer: Robert F. Tichy (Graz)
MSC:
| 11K38 | Irregularities of distribution, discrepancy |
| 11K45 | Pseudo-random numbers; Monte Carlo methods |
Keywords:
weighted star discrepancy; tractability; Halton sequence; digital sequence; quasi-Monte CarloReferences:
| [1] | Pillichshammer, F., Tractability properties of the weighted star discrepancy of regular grids, J. Complexity, 46, 103-112 (2018) · Zbl 1398.65015 |
| [2] | Hickernell, F.; Sloan, I. H.; Wasilkowski, G. W., On strong tractability of weighted multivariate integration, Math. Comp., 73, 1903-1911 (2004) · Zbl 1071.41027 |
| [3] | Sloan, I. H.; Woźniakowski, H., When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity, 14, 1-33 (1998) · Zbl 1032.65011 |
| [4] | Novak, E.; Woźniakowski, H., Tractability of Multivariate Problems. Volume II: Standard Information for Functionals (2010), European Mathematical Society: European Mathematical Society Zürich · Zbl 1241.65025 |
| [5] | Beck, J.; Chen, W. W.L., Irregularities of Distribution (1987), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0617.10039 |
| [6] | Kuipers, L.; Niederreiter, H., Uniform Distribution of Sequences (1974), John Wiley: John Wiley New York, Reprint, Dover Publications, Mineola, NY, 2006 · Zbl 0281.10001 |
| [7] | Leobacher, G.; Pillichshammer, F., Introduction to Quasi-Monte Carlo integration and applications, (Compact Textbooks in Mathematics (2014), Birkhäuser: Birkhäuser Cham) · Zbl 1309.65006 |
| [8] | Matoušek, J., Geometric Discrepancy (1999), Springer: Springer Berlin · Zbl 0930.11060 |
| [9] | Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods (1992), SIAM: SIAM Philadelphia · Zbl 0761.65002 |
| [10] | Novak, E.; Woźniakowski, H., Tractability of Multivariate Problems. Volume I: Linear Information (2008), European Mathematical Society: European Mathematical Society Zürich · Zbl 1156.65001 |
| [11] | Novak, E.; Woźniakowski, H., Tractability of Multivariate Problems. Volume III: Standard Information for Operators (2012), European Mathematical Society: European Mathematical Society Zürich · Zbl 1359.65003 |
| [12] | Doerr, B.; Gnewuch, M.; Srivastav, A., Bounds and constructions for the star-discrepancy via \(\delta \)-covers, J. Complexity, 21, 691-709 (2005) · Zbl 1115.11046 |
| [13] | Heinrich, S.; Novak, E.; Wasilkowski, G. W.; Woźniakowski, H., The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith., 96, 279-302 (2001) · Zbl 0972.11065 |
| [14] | Aistleitner, Ch., Covering numbers, dyadic chaining and discrepancy, J. Complexity, 27, 531-540 (2011) · Zbl 1263.11072 |
| [15] | Hinrichs, A., Covering numbers, Vapnik-Červonenkis classes and bounds on the star-discrepancy, J. Complexity, 20, 477-483 (2004) · Zbl 1234.11101 |
| [16] | Hinrichs, A.; Pillichshammer, F.; W. Ch. Schmid, Tractability properties of the weighted star discrepancy, J. Complexity, 24, 134-143 (2008) · Zbl 1146.65002 |
| [17] | Aistleitner, Ch., Tractability results for the weighted star-discrepancy, J. Complexity, 30, 381-391 (2014) · Zbl 1296.65041 |
| [18] | Dick, J.; Leobacher, G.; Pillichshammer, F., Construction algorithms for digital nets with low weighted star discrepancy, SIAM J. Numer. Anal., 43, 76-95 (2005) · Zbl 1084.11040 |
| [19] | Dick, J.; Niederreiter, H.; Pillichshammer, F., Weighted star discrepancy of digital nets in prime bases, (Talay, D.; Niederreiter, H., Monte Carlo and Quasi-Monte Carlo Methods 2004 (2006), Springer: Springer Berlin Heidelberg New York) · Zbl 1096.11025 |
| [20] | Dick, J.; Pillichshammer, F., Digital nets and sequences, (Discrepancy Theory and Quasi-Monte Carlo Integration (2010), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1282.65012 |
| [21] | Dick, J.; Pillichshammer, F., The weighted star discrepancy of Korobov’s \(p\)-sets, Proc. Amer. Math. Soc., 143, 12, 5043-5057 (2015) · Zbl 1329.11078 |
| [22] | Wang, X., Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. Comp., 72, 823-838 (2003) · Zbl 1025.65010 |
| [23] | Wang, X., A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity, 18, 683-701 (2002) · Zbl 1022.65005 |
| [24] | Tezuka, S., Tractability of multivariate integration using low-discrepancy sequences, Unif. Distrib. Theory, 11, 23-43 (2016) · Zbl 1445.11080 |
| [25] | Halton, J. H., On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math., 2, 84-90 (1960) · Zbl 0090.34505 |
| [26] | Hickernell, F.; Niederreiter, H., The existence of good extensible rank-1 lattices, J. Complexity, 19, 286-300 (2003) · Zbl 1029.65004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
