2023/08/15 by Art B. Owen, Owen, Art B., Zexin Pan +1 · 1 citation
Mathematics · Computer Science · #Mathematical Approximation and Integration #Digital Image Processing Techniques
paper · pdf · doi:10.48550/arxiv.2308.08035
Randomized quasi-Monte Carlo, via certain scramblings of digital nets, produces unbiased estimates of ∫[0,1]df(\boldsymbolx) d\boldsymbolx with a variance that is o(1/n) for any f∈ L2[0,1]d. It also satisfies some non-asymptotic bounds where the variance is no larger than some Γ<∞ times the ordinary Monte Carlo variance. For scrambled Sobol' points, this quantity Γ grows exponentially in d. For scrambled Faure points, Γ\leqslant exp(1)\doteq 2.718 in any dimension, but those points are awkward to use for large d. This paper shows that certain scramblings of Halton sequences have gains below an explicit bound that is O(log d) but not O( (log d)1-ε) for any ε>0 as d→∞. For 6\leqslant d\leqslant 106, the upper bound on the gain coefficient is never larger than 3/2+log(d/2).