On integration methods based on scrambled nets of arbitrary size

详细信息    查看全文

• 作者：Mathieu Gerber ; ^{mathieugerber@fas.harvard.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Integration ; Randomized quasi-Monte Carlo ; Scrambling ; Sequential quasi-Monte Carlo
• 刊名：Journal of Complexity
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：31
• 期：6
• 页码：798-816
• 全文大小：623 K

文摘

We consider the problem of evaluating $I\left(蠁\right):={\int }_{{[0,1)}^s}蠁\left(x\right)dx$ for a function 蠁∈L²[0,1)^s$蠁\in L^2{[0,1)}^s$. In situations where I(蠁)$I\left(蠁\right)$ can be approximated by an estimate of the form $N^{-1}{\sum }_{n=0}^{N-1}蠁\left(x^n\right)$, with ${\left\{x^n\right\}}_{n=0}^{N-1}$ a point set in [0,1)^s${[0,1)}^s$, it is now well known that the O_P(N^−1/2)${\mathcal{O}}_P\left(N^{-1/2}\right)$ Monte Carlo convergence rate can be improved by taking for ${\left\{x^n\right\}}_{n=0}^{N-1}$ the first c40ba0be65147197a2967b432a28f6f4" title="Click to view the MathML source">N=位b^m$N=位b^m$ points, 05c47acf25ae070626dd5cd5072" title="Click to view the MathML source">位∈{1,…,b−1}$位\in \{1,\dots ,b-1\}$, of a scrambled (t,s)$(t,s)$-sequence in base b≥2$b\ge 2$. In this paper we derive a bound for the variance of scrambled net quadrature rules which is of order O(N⁻¹)$\mathcal{O}\left(N^{-1}\right)$ without any restriction on N$N$. As a corollary, this bound allows us to provide simple conditions to get, for any pattern of N$N$, an integration error of size O_P(N^−1/2)${\mathcal{O}}_P\left(N^{-1/2}\right)$ for functions that depend on the quadrature size N$N$. Notably, we establish that sequential quasi-Monte Carlo (Gerber & Chopin, 2015) reaches the O_P(N^−1/2)${\mathcal{O}}_P\left(N^{-1/2}\right)$ convergence rate for any values of N$N$. In a numerical study, we show that for scrambled net quadrature rules we can relax the constraint on N$N$ without any loss of efficiency when the integrand 蠁$蠁$ is a discontinuous function while, for sequential quasi-Monte Carlo, taking N=位b^m$N=位b^m$ may only provide moderate gains.