Key points are not available for this paper at this time.
We study approximate integration of a function f f over 0, 1 s 0, 1ˢ based on taking the median of 2 r − 1 2r-1 integral estimates derived from independently randomized (t, m, s) (t, m, s) -nets in base 2 2. The nets are randomized by Matousek’s random linear scramble with a random digital shift. If f f is analytic over 0, 1 s 0, 1ˢ, then the probability that any one randomized net’s estimate has an error larger than 2 − c m 2 / s 2^-cm²/s times a quantity depending on f f is O (1 / m) O (1/ m) for any c > 3 log (2) / π 2 ≈ 0. 21 c>3 (2) / ² 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) O (n^-c (n) /s) for n = 2 m n=2ᵐ function evaluations. The sample median of 2 r − 1 2r-1 independent draws attains this rate too, so long as r / m 2 r/m² is bounded away from zero as m → ∞ m. We include results for finite precision estimates and some nonasymptotic comparisons to taking the mean of 2 r − 1 2r-1 independent draws.
Pan et al. (Thu,) studied this question.