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.
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.
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.