1. Super-polynomial accuracy of one dimensional randomized nets using the median of means.
- Author
-
Pan, Zexin and Owen, Art B.
- Subjects
- *
NATURAL numbers , *COMBINATORICS , *MEDIAN (Mathematics) - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF