Gain coefficients for scrambled Halton points
share
Randomized quasi-Monte Carlo, via certain scramblings of digital nets, produces unbiased estimates of ∫_[0,1]^df(x) dx with a variance that is o(1/n) for any f∈ L^2[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, Γ⩽exp(1)≐ 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⩽ d⩽ 10^6, the upper bound on the gain coefficient is never larger than 3/2+log(d/2).
READ FULL TEXT