Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands (Q638795): Difference between revisions

The random sampling technique to approximate the integral \(\int_{[0,1]^{s}}f({\mathbf x}) d {\mathbf x}\) by averaging the function at some sampling points is stydied. Here, the integrand is a smooth function. The convergence rate of the approximation error depends on the smoothness of the function and the sampling technique. The present paper introduces a new randomized quasi-Monte Carlo algorithm, and it is proved that it achives a convergence rate of the root mean-square error of order \({\mathcal O}(N^{- \alpha - {1 \over 2} + \varepsilon}).\) Here in general the integrands have square integrable partial mixed derivatives up to order \(\alpha > 1\) in each variable. In the introduction the standardized problem of approximating integrals over the unit cube by Monte Carlo or quasi-Monte Carlo algorithms is considered. The notions of worst-case error and root mean-square error are reminded. Briefly Owen's algorithm for scrambling digital nets is mentioned. In Subsection 1.1 the idea of a new randomized QMC algorithm is given. In Subsection 1.2, as a particular realization of the theoretical model, developed in Subsection 1.1, some simple numerical results on one- and two-dimensional cases, are presented. In Section 2 the necessary backgrounds on QMC methods are given. In Subsection 2.1 the notions of worst-case error, the discrepancy of a point net and the inequality of Koksma-Hlawka are presented. In Subsection 2.2 the theoretical base and the constructive principle of digital \((t,m,s)\)-nets in base \(b \geq 2\) are reminded. In Subsection 2.3 the definition and some basic properties of the Walsh function in base \(b\) are presented. In Subsection 2.4 Owen's scrambling on order \(d\) is given. In Section 3 the integral \(\int_{[0,1]^{s}}f({\mathbf x}) d {\mathbf x}\) is approximated by the algorithm \(\widehat{I}(f) = {1 \over b^{m}} \sum_{n=0}^{b^{m}-1}f({\mathbf y}_{n})\) which uses points, obtained by applying a random Owen's scrambling on order \(d\) to the digital \((t,m,s)\)-net. The variance \(\operatorname{Var}[\widehat{I}(f)]\) (the root mean square worst-case error of the integration) of the estimator \(\widehat{I}(f)\) is considered. In Lemma 7 an exact formula for \(\operatorname{Var}[\widehat{I}(f)]\) is obtained. In Subsections 3.1 and 3.2 the components of the formula, presented in Lemma 7 are estimated. The main result of the paper is given in Theorem 10. In this theorem an upper bound of \(\operatorname{Var}[\widehat{I}(f)]\) by using a random Owen's scrambling on order \(d\) to the digital \((t,m,s)\)-net is presented in terms of the variation of the integrand, the parameters of the \((t,m,s)\)-net, and the order \(\alpha\) of smoothness. Theorem 10 shows the convergence rate of the standard deviation of the estimator \(\widehat{I}(f)\) of \({\mathcal O}\left( N^{- \min(\alpha, d) - 1/2} (\log N)^{s\min(\alpha + 1, d+ 1) / 2} \right).\) In Section 4 the obtained results and the techniques for their obtainment are discussed and compared with results, obtained by an application of other scrambling techniques. In Appendix A some properties of the digit interlacing function are proved. In Appendix B some useful results are proved.