Randomized quasi-Monte Carlo (RQMC) methods estimate the expectation of a random variable by the average of n dependent realizations of it. In general, due to the strong dependence, the estimation error may not obey a central limit theorem. Analysis of RQMC methods have so far focused mostly on the convergence rates of asymptotic worst-case error bounds and variance bounds, when n ¿ ¿, but little is known about the limiting distribution of the error. Here we examine this limiting distribution for the special case of a randomly-shifted lattice rule, when the integrand is smooth. We start with simple one-dimensional functions, where we show that the limiting distribution is uniform over a bounded interval if the integrand is non-periodic, and has a square root form over a bounded interval if the integrand is periodic. In higher dimensions, for linear functions, the distribution function of the properly standardized error converges to a spline of degree equal to the dimension.
This paper studies the convergence rate of randomized quasi--Monte Carlo (RQMC) for discontinuous functions, which are often of infinite variation in the sense of Hardy and Krause. It was previously known that the root mean square error (RMSE) of RQMC is only
o(n−1/2) for discontinuous functions. For certain discontinuous functions in
d dimensions, we prove that the RMSE of RQMC is
O(n−1/2−1/(4d−2)+ϵ) for any
ϵ>0 and arbitrary
n. If some discontinuity boundaries are parallel to some coordinate axes, the rate can be improved to
O(n−1/2−1/(4du−2)+ϵ), where
du denotes the so-called irregular dimension, that is, the number of axes which are not parallel to the discontinuity boundaries. Moreover, this paper shows that the RMSE is
O(n−1/2−1/(2d)) for certain indicator functions.
We examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.
Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at
n equidistributed points. For scrambled digital nets, the resulting variance is typically
O~(n−θ), where
θ∈[1,3] depends on the smoothness of the integrand and
O~ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are
N integrand evaluations partitioned into
R independent replicates of
n=N/R RQMC points, and the RQMC variance is
Θ(n−θ), then an oracle minimizing the width of a Bennett confidence interval would choose
n=Θ(N1/(θ+1)). The resulting intervals have a width
Θ(N−θ/(θ+1)). Our empirical investigations had optimal values of
n grow slowly with
N, HBCI intervals that were usually narrower than the EBCI ones and optimal values of
n for HBCI that were equal to or smaller than the ones for the oracle.
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.
We study a random sampling technique to approximate integrals ∫[0, 1]s f(x) dx by averaging the function at some sampling points. We focus on cases where the integrand is smooth, which is a problem which occurs in statistics. The convergence rate of the approximation error depends on the smoothness of the function f and the sampling technique. For instance, Monte Carlo (MC) sampling yields a convergence of the root mean square error (RMSE) of order N−1/2 (where N is the number of samples) for functions f with finite variance. Randomized QMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE of order N−3/2+ε under the stronger assumption that the integrand has bounded variation. A combination of RQMC with local antithetic sampling achieves a convergence of the RMSE of order N−3/2−1/s+ε (where s ≥ 1 is the dimension) for functions with mixed partial derivatives up to order two. Additional smoothness of the integrand does not improve the rate of convergence of these algorithms in general. On the other hand, it is known that without additional smoothness of the integrand it is not possible to improve the convergence rate. This paper introduces a new RQMC algorithm, for which we prove that it achieves a convergence of the root mean square error (RMSE) of order N−α−1/2+ε provided the integrand satisfies the strong assumption that it has square integrable partial mixed derivatives up to order α > 1 in each variable. Known lower bounds on the RMSE show that this rate of convergence cannot be improved in general for integrands with this smoothness. We provide numerical examples for which the RMSE converges approximately with order N−5/2 and N−7/2, in accordance with the theoretical upper bound.