Search

We study approximate integration of a function f over [0,1]^s based on taking the median of 2r-1 integral estimates derived from independently randomized (t,m,s)-nets in base 2. The nets are randomized by Matousek's random linear scramble with a random digital shift. If f is analytic over [0,1]^s, then the probability that any one randomized net's estimate has an error larger than 2^{-cm^2/s} times a quantity depending on f is O(1/\sqrt {m}) for any c<3\log (2)/\pi ^2\approx 0.21. As a result, the median of the distribution of these scrambled nets has an error that is O(n^{-c\log (n)/s}) for n=2^m function evaluations. The sample median of 2r-1 independent draws attains this rate too, so long as r/m^2 is bounded away from zero as m\to \infty. We include results for finite precision estimates and some nonasymptotic comparisons to taking the mean of 2r-1 independent draws. [ABSTRACT FROM AUTHOR]

Let |$f:[0,1]^{d}\to{\mathbb{R}}$| be a completely monotone integrand as defined by Aistleitner and Dick (2015, Acta Arithmetica, 167, 143–171) and let points |$\boldsymbol{x}_{0},\dots ,\boldsymbol{x}_{n-1}\in [0,1]^{d}$| have a non-negative local discrepancy (NNLD) everywhere in |$[0,1]^{d}$|⁠. We show how to use these properties to get a non-asymptotic and computable upper bound for the integral of |$f$| over |$[0,1]^{d}$|⁠. An analogous non-positive local discrepancy property provides a computable lower bound. It has been known since Gabai (1967, Illinois J. Math. 11, 1–12) that the two-dimensional Hammersley points in any base |$b\geqslant 2$| have NNLD. Using the probabilistic notion of associated random variables, we generalize Gabai's finding to digital nets in any base |$b\geqslant 2$| and any dimension |$d\geqslant 1$| when the generator matrices are permutation matrices. We show that permutation matrices cannot attain the best values of the digital net quality parameter when |$d\geqslant 3$|⁠. As a consequence the computable absolutely sure bounds we provide come with less accurate estimates than the usual digital net estimates do in high dimensions. We are also able to construct high-dimensional rank one lattice rules that are NNLD. We show that those lattices do not have good discrepancy properties: any lattice rule with the NNLD property in dimension |$d\geqslant 2$| either fails to be projection regular or has all its points on the main diagonal. Complete monotonicity is a very strict requirement that for some integrands can be mitigated via a control variate. [ABSTRACT FROM AUTHOR]