Search for: All records

Abstract 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. 

Let $f$be analytic on $[0,1]$with $|f^{\left(k\right)}\left(1/2\right)|⩽<\#comment/>A{\mathrm{\alpha <\#comment/>}}^{k}k!$for some constants $A$and $\mathrm{\alpha <\#comment/>}>2$and all $k⩾<\#comment/>1$. We show that the median estimate of $\mathrm{\mu <\#comment/>}={\int <\#comment/>}_0^{1}f\left(x\right)\mathrm{d}x$under random linear scrambling with $n=2^m$points converges at the rate $O\left(n^{-<\#comment/>c\log <\#comment/>\left(n\right)}\right)$for any $c>3\log <\#comment/>\left(2\right)/{\mathrm{\pi <\#comment/>}}^2\approx <\#comment/>0.21$. We also get a super-polynomial convergence rate for the sample median of $2k-<\#comment/>1$random linearly scrambled estimates, when $k/m$is bounded away from zero. When $f$has a $p$’th derivative that satisfies a $\mathrm{\lambda <\#comment/>}$-Hölder condition then the median of means has error $O\left(n^{-<\#comment/>(p+\mathrm{\lambda <\#comment/>})+\mathrm{ϵ<\#comment/>}}\right)$for any $\mathrm{ϵ<\#comment/>}>0$, if $k\to <\#comment/>\mathrm{\infty <\#comment/>}$as $m\to <\#comment/>\mathrm{\infty <\#comment/>}$. The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number.