A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy

Gnewuch, Michael; Pasing, Hendrik; Weiß, Christian

doi:10.1090/mcom/3666

A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
HTML articles powered by AMS MathViewer

by Michael Gnewuch, Hendrik Pasing and Christian Weiß HTML | PDF

Math. Comp. 90 (2021), 2873-2898 Request permission

Abstract:

We prove a generalized Faulhaber inequality to bound the sums of the $j$-th powers of the first $n$ (possibly shifted) natural numbers. With the help of this inequality we are able to improve the known bounds for bracketing numbers of $d$-dimensional axis-parallel boxes anchored in $0$ (or, put differently, of lower left orthants intersected with the $d$-dimensional unit cube $[0,1]^d$). We use these improved bracketing numbers to establish new bounds for the star-discrepancy of negatively dependent random point sets and its expectation. We apply our findings also to the weighted star-discrepancy.

References

Christoph Aistleitner, Covering numbers, dyadic chaining and discrepancy, J. Complexity 27 (2011), no. 6, 531–540. MR 2846704, DOI 10.1016/j.jco.2011.03.001
Christoph Aistleitner, On the inverse of the discrepancy for infinite dimensional infinite sequences, J. Complexity 29 (2013), no. 2, 182–194. MR 3018138, DOI 10.1016/j.jco.2012.06.002
Christoph Aistleitner, Tractability results for the weighted star-discrepancy, J. Complexity 30 (2014), no. 4, 381–391. MR 3212778, DOI 10.1016/j.jco.2013.12.004
Christoph Aistleitner and Markus Hofer, Probabilistic discrepancy bound for Monte Carlo point sets, Math. Comp. 83 (2014), no. 287, 1373–1381. MR 3167462, DOI 10.1090/S0025-5718-2013-02773-1
Christoph Aistleitner and Markus Weimar, Probabilistic star discrepancy bounds for double infinite random matrices, Monte Carlo and quasi-Monte Carlo methods 2012, Springer Proc. Math. Stat., vol. 65, Springer, Heidelberg, 2013, pp. 271–287. MR 3145566, DOI 10.1007/978-3-642-41095-6_{1}0
Jan Baldeaux and Michael Gnewuch, Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition, SIAM J. Numer. Anal. 52 (2014), no. 3, 1128–1155. MR 3200424, DOI 10.1137/120896001
J. Fernando Barbero G., Juan Margalef-Bentabol, and Eduardo J. S. Villaseñor, A two-sided Faulhaber-like formula involving Bernoulli polynomials, C. R. Math. Acad. Sci. Paris 358 (2020), no. 1, 41–44 (English, with English and French summaries). MR 4102976, DOI 10.5802/crmath.10
Dmitriy Bilyk and Michael T. Lacey, On the small ball inequality in three dimensions, Duke Math. J. 143 (2008), no. 1, 81–115. MR 2414745, DOI 10.1215/00127094-2008-016
Dmitriy Bilyk, Michael T. Lacey, and Armen Vagharshakyan, On the small ball inequality in all dimensions, J. Funct. Anal. 254 (2008), no. 9, 2470–2502. MR 2409170, DOI 10.1016/j.jfa.2007.09.010
O. Bousquet, S. Gelly, K. Kurach, O. Teytaud, and D. Vincent, Critical hyper-parameters: no random, no cry, preprint, arXiv:1706.03200v1, 2017.
R. E. Caflisch, W. Morokoff, and A. B. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comp. Finance 1 (1997), 27–46.
R. Cranley and T. N. L. Patterson, Randomization of number theoretic methods for multiple integration, SIAM J. Numer. Anal. 13 (1976), no. 6, 904–914. MR 494820, DOI 10.1137/0713071
Josef Dick, A note on the existence of sequences with small star discrepancy, J. Complexity 23 (2007), no. 4-6, 649–652. MR 2372019, DOI 10.1016/j.jco.2007.01.004
Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
Benjamin Doerr, A lower bound for the discrepancy of a random point set, J. Complexity 30 (2014), no. 1, 16–20. MR 3132867, DOI 10.1016/j.jco.2013.06.001
B. Doerr, A sharp discrepancy bound for jittered sampling, preprint, arXiv:2103.15712, 2021.
Benjamin Doerr, Carola Doerr, and Michael Gnewuch, Probabilistic lower bounds for the discrepancy of Latin hypercube samples, Contemporary computational mathematics—a celebration of the 80th birthday of Ian Sloan. Vol. 1, 2, Springer, Cham, 2018, pp. 339–350. MR 3822241
Benjamin Doerr, Michael Gnewuch, Peter Kritzer, and Friedrich Pillichshammer, Component-by-component construction of low-discrepancy point sets of small size, Monte Carlo Methods Appl. 14 (2008), no. 2, 129–149. MR 2431686, DOI 10.1515/MCMA.2008.007
Benjamin Doerr, Michael Gnewuch, and Anand Srivastav, Bounds and constructions for the star-discrepancy via $\delta$-covers, J. Complexity 21 (2005), no. 5, 691–709. MR 2170868, DOI 10.1016/j.jco.2005.05.002
Benjamin Doerr, Michael Gnewuch, and Magnus Wahlström, Implementation of a component-by-component algorithm to generate small low-discrepancy samples, Monte Carlo and quasi-Monte Carlo methods 2008, Springer, Berlin, 2009, pp. 323–338. MR 2743904, DOI 10.1007/978-3-642-04107-5_{2}0
Benjamin Doerr, Michael Gnewuch, and Magnus Wahlström, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, J. Complexity 26 (2010), no. 5, 490–507. MR 2719644, DOI 10.1016/j.jco.2010.03.004
Carola Doerr, Michael Gnewuch, and Magnus Wahlström, Calculation of discrepancy measures and applications, A panorama of discrepancy theory, Lecture Notes in Math., vol. 2107, Springer, Cham, 2014, pp. 621–678. MR 3330332, DOI 10.1007/978-3-319-04696-9_{1}0
Michael B. Giles and Benjamin J. Waterhouse, Multilevel quasi-Monte Carlo path simulation, Advanced financial modelling, Radon Ser. Comput. Appl. Math., vol. 8, Walter de Gruyter, Berlin, 2009, pp. 165–181. MR 2648461, DOI 10.1515/9783110213140.165
Paul Glasserman, Monte Carlo methods in financial engineering, Applications of Mathematics (New York), vol. 53, Springer-Verlag, New York, 2004. Stochastic Modelling and Applied Probability. MR 1999614
Michael Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 24 (2008), no. 2, 154–172. MR 2400314, DOI 10.1016/j.jco.2007.08.003
Michael Gnewuch, Construction of minimal bracketing covers for rectangles, Electron. J. Combin. 15 (2008), no. 1, Research Paper 95, 20. MR 2426158
Michael Gnewuch, Entropy, randomization, derandomization, and discrepancy, Monte Carlo and quasi-Monte Carlo methods 2010, Springer Proc. Math. Stat., vol. 23, Springer, Heidelberg, 2012, pp. 43–78. MR 3173829, DOI 10.1007/978-3-642-27440-4_{3}
M. Gnewuch and N. Hebbinghaus, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, preprint (To appear in Ann. Appl. Prob, arXiv:2102.04451, 2019).
Ana I. Gómez, Domingo Gómez-Pérez, and Friedrich Pillichshammer, Secure pseudorandom bit generators and point sets with low star-discrepancy, J. Comput. Appl. Math. 396 (2021), Paper No. 113601, 8. MR 4254544, DOI 10.1016/j.cam.2021.113601
N. Hebbinghaus, Mixed sequences and application to multilevel algorithms, Master’s thesis, Christ Church, University of Oxford, 2012.
Stefan Heinrich, Erich Novak, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001), no. 3, 279–302. MR 1814282, DOI 10.4064/aa96-3-7
Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, and Klaus Ritter, Multi-level Monte Carlo algorithms for infinite-dimensional integration on $\Bbb R^{\Bbb N}$, J. Complexity 26 (2010), no. 3, 229–254. MR 2657363, DOI 10.1016/j.jco.2010.02.002
Aicke Hinrichs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, J. Complexity 20 (2004), no. 4, 477–483. MR 2068153, DOI 10.1016/j.jco.2004.01.001
Aicke Hinrichs, David Krieg, Robert J. Kunsch, and Daniel Rudolf, Expected dispersion of uniformly distributed points, J. Complexity 61 (2020), 101483, 9. MR 4149213, DOI 10.1016/j.jco.2020.101483
Aicke Hinrichs, Friedrich Pillichshammer, and Wolfgang Ch. Schmid, Tractability properties of the weighted star discrepancy, J. Complexity 24 (2008), no. 2, 134–143. MR 2400312, DOI 10.1016/j.jco.2007.08.002
Donald E. Knuth, Johann Faulhaber and sums of powers, Math. Comp. 61 (1993), no. 203, 277–294. MR 1197512, DOI 10.1090/S0025-5718-1993-1197512-7
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
Pierre L’Ecuyer, Randomized quasi–Monte Carlo: an introduction for practitioners, Monte Carlo and quasi–Monte Carlo methods, Springer Proc. Math. Stat., vol. 241, Springer, Cham, 2018, pp. 29–52. MR 3828133, DOI 10.1007/978-3-319-91436-7_{2}
Christiane Lemieux, Negative dependence, scrambled nets, and variance bounds, Math. Oper. Res. 43 (2018), no. 1, 228–251. MR 3774642, DOI 10.1287/moor.2017.0861
C. Levaillant, Wilson’s theorem modulo $p^2$ derived from Faulhaber polynomials, arXiv:1912.06652, 2019.
Mario Neumüller and Friedrich Pillichshammer, Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability, Unif. Distrib. Theory 13 (2018), no. 1, 65–86. MR 3806586, DOI 10.1515/udt-2018-0004
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Art B. Owen, Randomly permuted $(t,m,s)$-nets and $(t,s)$-sequences, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 299–317. MR 1445791, DOI 10.1007/978-1-4612-2552-2_{1}9
Hendrik Pasing and Christian Weiß, Improving a constant in high-dimensional discrepancy estimates, Publ. Inst. Math. (Beograd) (N.S.) 107(121) (2020), 67–74. MR 4122318, DOI 10.2298/pim2021067p
S. H. Paskov, Computing high dimensional integrals with applications to finance, Columbia University. Technical Report CUCS-023-94, 1994.
Daniel Rudolf, An upper bound of the minimal dispersion via delta covers, Contemporary computational mathematics—a celebration of the 80th birthday of Ian Sloan. Vol. 1, 2, Springer, Cham, 2018, pp. 1099–1108. MR 3822275
Wolfgang M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21 (1972), 45–50. MR 319933, DOI 10.4064/aa-21-1-45-50
Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
Eric Thiémard, An algorithm to compute bounds for the star discrepancy, J. Complexity 17 (2001), no. 4, 850–880. Complexity of multivariate problems (Kowloon, 1999). MR 1881674, DOI 10.1006/jcom.2001.0600
M. Ullrich and J. Vybíral, Deterministic constructions of high-dimensional sets with small dispersion, preprint, arXiv:1901.06702, 2019
Aad W. van der Vaart and Jon A. Wellner, Weak convergence and empirical processes, Springer Series in Statistics, Springer-Verlag, New York, 1996. With applications to statistics. MR 1385671, DOI 10.1007/978-1-4757-2545-2
Christian Weiß and Zoran Nikolić, An aspect of optimal regression design for LSMC, Monte Carlo Methods Appl. 25 (2019), no. 4, 283–290. MR 4036631, DOI 10.1515/mcma-2019-2049
J. Wiart, C. Lemieux, and G. Dong, On the dependence structure of scrambled $(t,m,s)$-nets, preprint, arXiv:1903.09877, 2019.
M. Wnuk, M. Gnewuch, and N. Hebbinghaus, On Negatively Dependent Sampling Schemes, Variance Reduction, and Probabilistic Upper Discrepancy Bounds. In: D. Bylik, J. Dick, F. Pillichshammer (Eds.), Discrepancy Theory, Radon Series on Computational and Applied Mathematics 26 pp. 43–68, DeGruyter, arXiv:1904.10796, 2010.
Marcin Wnuk and Michael Gnewuch, Note on pairwise negative dependence of randomly shifted and jittered rank-1 lattices, Oper. Res. Lett. 48 (2020), no. 4, 410–414. MR 4100870, DOI 10.1016/j.orl.2020.04.005