The nonzero gain coefficients of Sobol's sequences are always powers of two

DOI10.1016/J.JCO.2022.101700zbMath1518.65026arXiv2106.10534MaRDI QIDQ6370740

Zexin Pan, Art B. Owen

Publication date: 19 June 2021

Abstract: When a plain Monte Carlo estimate on $n$ samples has variance $sigm{a}^2/n$, then scrambled digital nets attain a variance that is $o(1/n)$ as $noinfty$. For finite $n$ and an adversarially selected integrand, the variance of a scrambled $(t,m,s)$-net can be at most $Gammasigm{a}^2/n$ for a maximal gain coefficient $Gamma<infty$. The most widely used digital nets and sequences are those of Sobol'. It was previously known that $Gammaleqslant{2}^t{3}^s$ for Sobol' points as well as Niederreiter-Xing points. In this paper we study nets in base $2$. We show that $Gammaleqslant{2}^{t+s-1}$ for nets. This bound is a simple, but apparently unnoticed, consequence of a microstructure analysis in Niederreiter and Pirsic (2001). We obtain a sharper bound that is smaller than this for some digital nets. We also show that all nonzero gain coefficients must be powers of two. A consequence of this latter fact is a simplified algorithm for computing gain coefficients of nets in base $2$.

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30)

This page was built for publication: The nonzero gain coefficients of Sobol's sequences are always powers of two