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 be analytic on [0,1] with |f^{(k)}(1/2)|\leqslant A\alpha ^kk! for some constants A and \alpha <2 and all k\geqslant 1. We show that the median estimate of \mu =\int _0^1f(x)\,\mathrm {d} x under random linear scrambling with n=2^m points converges at the rate O(n^{-c\log (n)}) for any c< 3\log (2)/\pi ^2\approx 0.21. We also get a super-polynomial convergence rate for the sample median of 2k-1 random linearly scrambled estimates, when k/m is bounded away from zero. When f has a p'th derivative that satisfies a \lambda-Hölder condition then the median of means has error O(n^{-(p+\lambda)+\epsilon }) for any \epsilon >0, if k\to \infty as m\to \infty. 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. [ABSTRACT FROM AUTHOR]

When a plain Monte Carlo estimate on n samples has variance σ 2 / n , then scrambled digital nets attain a variance that is o (1 / n) as n → ∞. For finite n and an adversarially selected integrand, the variance of a scrambled (t , m , s) -net can be at most Γ σ 2 / n for a maximal gain coefficient Γ < ∞. The most widely used digital nets and sequences are those of Sobol'. It was previously known that Γ ⩽ 2 t 3 s for any nets in base 2. For digital nets, Dick and Pillichshammer (2010) obtained the bound 2 t + s. In this paper we study digital nets in base 2 and show that Γ ⩽ 2 t + s − 1 for such nets. This bound is a simple, but apparently unnoticed, consequence of a microstructure analysis by Niederreiter and Pirsic in 2001. We obtain a sharper bound that is smaller than this for some digital nets. Our main finding is that all nonzero gain coefficients must be powers of two. A consequence of this latter fact is a simplified algorithm for computing gain coefficients of digital nets in base 2. [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]