Quasi-Monte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasi-Monte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasi-Monte Carlo sample values by any practical way. A recently proposed method, called randomized quasi-Monte Carlo methods, takes advantage of Monte Carlo and quasi-Monte Carlo methods. Randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques in randomized quasi-Monte Carlo methods, which provide an elegant approach to obtain error estimates for quasi-Monte Carlo based on treating each scrambled sequence as a different and independent random sample. The core of randomized quasi-Monte Carlo is to find an effective and fast algorithm to scramble (randomize) quasirandom sequences. This dissertation surveys research on algorithms and implementations of scrambled quasirandom sequences and proposes some new algorithms to improve the quality of scrambled quasirandom sequences. Besides obtaining error estimates for quasi-Monte Carlo, scrambling techniques provide a natural way to parallelize quasirandom sequences. This scheme is especially suitable for distributed or grid computing. By scrambling a quasirandom sequence we can produce a family of related quasirandom sequences. Finding one or a subset of optimal quasirandom sequences within this family is an interesting problem, as such optimal quasirandom sequences can be quite useful for quasi-Monte Carlo. The process of finding such optimal quasirandom sequences is called the derandomization of a randomized (scrambled) family. We summarize aspects of this technique and propose some new algorithms for finding optimal sequences from the Halton, Faure and Sobol sequences. Finally we explore applications of derandomization.
Quasi-Monte Carlo (QMC) methods are now widely used in scientific computation, especially in estimating integrals over multidimensional domains and in many different financial computations. The use of randomized QMC methods, where randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques, brings more wide applications for QMC. However, the integration variance can depend strongly on the scrambling methods. Much of the work dealing with scrambling methods has been aimed at ways of linear scrambling methods. In this paper, we take a close look at the quadratic scrambling method for Faure sequences and compare with other linear scrambling methods. We will investigate the implementation and the performance of nonlinear scrambling methods for Faure sequences. The scrambling methods will focus on quadratic and inversive scrambling. We will compare those nonlinear scrambling methods with linear scrambling methods by a set of test-integral functions. Pseudorandom number generation by nonlinear methods will be expensive when their moduli are large. In our case, the modulus is relatively small. To the best of our knowledge, such a comparison has never been done before.
We survey basic ideas and results on randomized quasi-Monte Carlo (RQMC) methods, discuss their practical aspects, and give numerical illustrations. RQMC can improve accuracy compared with standard Monte Carlo (MC) when estimating an integral interpreted as a mathematical expectation. RQMC estimators are unbiased and their variance converges at a faster rate (under certain conditions) than MC estimators, as a function of the sample size. Variants of RQMC also work for the simulation of Markov chains, for function approximation and optimization, for solving partial differential equations, etc. In this introductory survey, we look at how RQMC point sets and sequences are constructed, how we measure their uniformity, why they can work for high-dimensional integrals, and how can they work when simulating Markov chains over a large number of steps.
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.
Despite possessing the low-discrepancy property, the classical d-dimensional Halton sequence is known to exhibit poorly distributed projections when
dbecomes even moderately large. This, in turn, often implies bad performance when implemented in quasi-Monte Carlo (QMC) methods in comparison to, for example, the Sobol’ sequence. As an attempt to eradicate this issue, we propose an adapted Halton sequence built by integer and irrational based van der Corput sequences and show empirically improved performance with respect to the accuracy of estimates in numerical integration and simulation. In addition, for the first time, a scrambling algorithm is proposed for irrational based digital sequences.
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.
The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the Halton sequence (the Halton sequence leaped) and a new construction of the generalized Halton sequence are suggested for unrestricted number of dimensions and are shown to improve considerably on the original Halton sequence. Problems associated with estimation of the error in quasi Monte Carlo integration and with the selection of test functions are identified. Then an estimate of the maximum error of the quasi Monte Carlo integration of nine test functions is computed for up to 400 dimensions and is used to evaluate the known generators mentioned above and the two new generators. An empirical formula for the error of the quasi Monte Carlo integration is suggested.