×

On negative dependence properties of Latin hypercube samples and scrambled nets. (English) Zbl 1473.11149

Summary: We study the notion of \(\gamma\)-negative dependence of random variables. This notion is a relaxation of the notion of negative orthant dependence (which corresponds to 1-negative dependence), but nevertheless it still ensures concentration of measure and allows to use large deviation bounds of Chernoff-Hoeffding- or Bernstein-type. We study random variables based on random points \(P\). These random variables appear naturally in the analysis of the discrepancy of \(P\) or, equivalently, of a suitable worst-case integration error of the quasi-Monte Carlo cubature that uses the points in \(P\) as integration nodes. We introduce the correlation number, which is the smallest possible value of \(\gamma\) that ensures \(\gamma\)-negative dependence. We prove that the random variables of interest based on Latin hypercube sampling or on \((t,m,d)\)-nets do, in general, not have a correlation number of 1, i.e., they are not negative orthant dependent.

MSC:

11K38 Irregularities of distribution, discrepancy
65D32 Numerical quadrature and cubature formulas
65C05 Monte Carlo methods
11K06 General theory of distribution modulo \(1\)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aistleitner, C., Covering numbers, dyadic chaining and discrepancy, J. Complex., 27, 531-540 (2011) · Zbl 1263.11072
[2] Block, H. W.; Savits, T. H.; Shaked, M., Some concepts of negative dependence, Ann. Probab., 10 (1982) · Zbl 0501.62037
[3] Dick, J.; Pillichshammer, F., Digital Nets and Sequences (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1282.65012
[4] Doerr, B., A lower bound for the discrepancy of a random point set, J. Complex., 30, 16-20 (2014) · Zbl 1295.60012
[5] Doerr, B., Probabilistic tools for the analysis of randomized optimization heuristics, (Doerr, B.; Neumann, F., Theory of Evolutionary Computation: Recent Developments in Discrete Optimization (2020), Springer), 1-87, Also available at · Zbl 1429.68004
[6] Doerr, B.; Doerr, C.; Gnewuch, M., Probabilistic lower discrepancy bounds for Latin hypercube samples, (Dick, J.; Kuo, F. Y.; Woźniakowski, H., Contemporary Computational Mathematics – a Celebration of the 80th Birthday of Ian Sloan (2018), Springer-Verlag), 339-350 · Zbl 1405.65089
[7] Faure, H., Discrépance de suites associées à un systéme de numération (en dimension s), Acta Arith., 41, 338-351 (1982) · Zbl 0442.10035
[8] Gnewuch, M.; Hebbinghaus, N., Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, Ann. Appl. Probab. (2019), in press. Preprint
[9] Gnewuch, M.; Pasing, H.; Weiß, C., A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy, Math. Comput. (2020), in press. Preprint
[10] 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
[11] L’Ecuyer, P.; Lemieux, C., Recent advances in randomized quasi-Monte Carlo methods, (Modeling Uncertainty. Modeling Uncertainty, Internat. Ser. Oper. Res. Management Sci., vol. 46 (2002), Kluwer Acad. Publ.: Kluwer Acad. Publ. Boston, MA), 419-474
[12] Lemieux, C., Negative dependence, scrambled nets, and variance bounds, Math. Oper. Res., 43, 228-251 (2018) · Zbl 1445.62126
[13] Matoušek, J., On the \(L_2\)-discrepancy for anchored boxes, J. Complex., 14, 527-556 (1998) · Zbl 0942.65021
[14] Matoušek, J., Geometric Discrepancy (2010), Springer-Verlag: Springer-Verlag Berlin Heidelberg · Zbl 1197.11092
[15] McKay, M. D.; Beckman, R. J.; Conover, W. J., A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 21, 239-245 (1979) · Zbl 0415.62011
[16] Niederreiter, H., Point sets and sequences with small discrepancy, Monatshefte Math., 104, 273-337 (1987) · Zbl 0626.10045
[17] Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63 (1992), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia · Zbl 0761.65002
[18] Owen, A. B., Randomly permuted \((t, m, s)\)-nets and \((t, s)\)-sequences, (Niederreiter, H.; Shiue, P. J.-S., Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (1995), Springer: Springer New York), 299-317 · Zbl 0831.65024
[19] Owen, A. B., Monte Carlo variance of scrambled net quadrature, SIAM J. Numer. Anal., 34 (1997) · Zbl 0890.65023
[20] Owen, A. B., Variance with alternative scramblings of digital nets, ACM Trans. Model. Comput. Simul., 13, 363-378 (2003) · Zbl 1390.65037
[21] Panconesi, A.; Srinivasan, A., Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds, SIAM J. Comput., 26, 350-368 (1997) · Zbl 0867.05063
[22] A. Panconesi, A. Srinivasan, 2020, Personal communication.
[23] Robbins, H., A remark on Stirling’s formula, Am. Math. Mon., 62, 26-29 (1955) · Zbl 0068.05404
[24] Sobol’, I. M., The distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. Mat. Fiz., 7, 784-802 (1967) · Zbl 0185.41103
[25] Wiart, J.; Lemieux, C.; Dong, G. Y., On the dependence structure of scrambled \((t, m, s)\)-nets (2020), preprint
[26] Wnuk, M.; Gnewuch, M.; Hebbinghaus, N., On negatively dependent sampling schemes, variance reduction, and probabilistic upper discrepancy bounds, (Bylik, D.; Dick, J.; Pillichshammer, F., Discrepancy Theory. Discrepancy Theory, Radon Series on Computational and Applied Mathematics, vol. 26 (2020), DeGruyter), 43-68 · Zbl 1523.65003
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.