We study the randomized worst-case error and the randomized error of scrambled quasi–Monte Carlo (QMC) quadrature as proposed by Owen. The function spaces considered in this article are the weighted Hilbert spaces generated by Haar-like wavelets and the weighted Sobolev-Hilbert spaces. Conditions are found under which multivariate integration is strongly tractable in the randomized worst-case setting and the randomized setting , respectively. The ε \varepsilon -exponents of strong tractability are found for the scrambled Niederreiter nets and sequences. The sufficient conditions for strong tractability for Sobolev spaces are more lenient for scrambled QMC quadratures than those for deterministic QMC net quadratures.
We study the numerical approximation of high-dimensional integrals using randomized quasi-Monte Carlo (RQMC) methods, with a focus on scrambled Sobol' sequences. While asymptotically faster than Monte Carlo, classical RQMC suffers from error bounds that grow exponentially in the dimension
s, and its root mean squared error (RMSE) convergence rate is generally no better than
O(N−3/2). To overcome these limitations, we combine two recent developments: Suzuki's coarse scrambling and the median trick. Coarse scrambling randomizes Sobol' sequences according to their generating base polynomials and significantly reduces the maximal gain coefficient. By appropriately choosing the base polynomials, we show that the coefficient can be made uniformly bounded in
s, yielding an
O(N−1/2) RMSE for
L2 integrands with a dimension-independent constant. The median trick then enables near-optimal convergence for function classes beyond
L2: for
Lp integrands with
p∈(1,2), the median of independent coarsely scrambled estimates achieves an error of
O(N−1+1/p) with high probability; for integrands in the Haar wavelet space
Hwav,α,s,p,q with
αp:=α−(1/p−1/2)+>0, we prove a high-probability error bound of
O(N−αp−1/2+ε) for any
ε>0; the bound improves to
O(N−r−αp−1/2+ε) when the integrand has dominating mixed derivatives of order
r≥1 that belong to
Hwav,α,s,p,q. The latter two bounds are uniform in
s under suitable conditions on the ANOVA components of the integrands. Numerical experiments confirm the predicted convergence rates and demonstrate the robustness of the proposed approach.
Monte Carlo (MQ) method is a powerful tool to approximate high dimensional integrals. The disadvantage of ordinary MQ is the slow convergence rate by cause of the essential randomness of this method. Computations of this convergence can lead to pure time consuming. Quasi-Monte Carlo (QMC) method yields considerably better results since this method is a deterministic alternative which uses Low-Discrepancy sequences instead of random samples . There are a multiplicity of big open problems in QMC-methods, problems partly arising from applications and partly arising from theory. QMC are developed to integrate over unite cube, where it has much more accuracy than MC for integrands of bounded variation. Integration over more general spaces such as triangles, disks and Cartesian products of such spaces is more challenging for QMC. Nevertheless in real-world applications various problems are defined over such spaces. The aim of this thesis is to provide a survey of a solution of such problems of numerical integration defined over non-cubical spaces. We present QMC and randomised QMC (RQMC) constructions in the triangle with a vanishing discrepancy based on the recent work of Basu 2016. The QMC construction is a version of the Van der Corput-Halton sequences specially made to the unit triangle. The attraction of scrambled net is replication based error estimation for QMC with slightly the same accuracy as QMC, and for smooth enough integrands.
Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.