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]