Discrepancy Bounds for a Class of Negatively Dependent Random Points Including Latin Hypercube Samples

Abstract

We introduce a class of $\gamma$-negatively dependent random samples. We prove that this class includes, apart from Monte Carlo samples, in particular Latin hypercube samples and Latin hypercube samples padded by Monte Carlo. For a $\gamma$-negatively dependent $N$-point sample in dimension $d$ we provide probabilistic upper bounds for its star discrepancy with explicitly stated dependence on $N$, $d$, and $\gamma$. These bounds generalize the probabilistic bounds for Monte Carlo samples from [Heinrich et al., Acta Arith. 96 (2001), 279--302] and [C.~Aistleitner, J.~Complexity 27 (2011), 531--540], and they are optimal for Monte Carlo and Latin hypercube samples. In the special case of Monte Carlo samples the constants that appear in our bounds improve substantially on the constants presented in the latter paper and in [C.~Aistleitner, M.~T.~Hofer, Math. Comp.~83 (2014), 1373--1381].

25 pages

References in corpus (6)

• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Calculation of Discrepancy Measures and Applications
• A Lower Bound for the Discrepancy of a Random Point Set
• On Negatively Dependent Sampling Schemes, Variance Reduction, and Probabilistic Upper Discrepancy Bounds
• Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples
• Note on Pairwise Negative Dependence of Randomized Rank-1 Lattices

Cited by in corpus (5)

• A Sharp Discrepancy Bound for Jittered Sampling
• The curse of dimensionality for the $L_p$-discrepancy with finite $p$
• Consistency of randomized integration methods
• Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
• Poissonian pair correlations for dependent random variables