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.
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.
Quasi-Monte Carlo Beyond Hardy-Krause II: (1+ε)n Samples Suffice
Numerical integration studies how well one can estimate the integral of a function f over [0,1)d using n sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error Od(σSO(f)/n), where the smoothed-out variation σSO(f) can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires n2 i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant ε>0, we show that (1+ε)n i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.
Numerical integration---approximating the integral of a function f using n point evaluations---is a central task in science and engineering. The two main paradigms for this problem, the Monte Carlo and quasi-Monte Carlo methods, have distinct strengths and limitations, and a fundamental question is to design a method that combines the benefits of both. \smallskip Building on recent algorithmic advances in discrepancy theory, Bansal and Jiang \cite{BJ25a} gave a randomized QMC method that naturally bridges the MC and QMC error guarantees. Their method also achieves a surprising improvement over the classical Koksma--Hlawka inequality for QMC methods: it attains an error bound of O(σSO(f)/n), where σSO(f) is a new notion of \emph{smoothed-out variation} that they introduced and showed to be substantially smaller than the Hardy--Krause variation governing the classical bound. \smallskip However, the analysis in \cite{BJ25a} is quite involved: it must carefully exploit the structure of the dyadic decomposition and the randomness of the algorithm inside a sufficiently fine discretization of the Hlawka--Zaremba formula to obtain cancellations among the high-frequency components in the Fourier decomposition of f. The contribution of this article is twofold: (1) We give an equivalent characterization of σSO(f) in terms of the Haar--Besov seminorm of f, relating this new notion of smoothed-out variation to classical quantities. (2) Through this characterization, we provide a conceptually simpler and more direct analysis of the Bansal--Jiang QMC method via Haar decomposition, bypassing the use of the Hlawka--Zaremba formula, Fourier decomposition, and the delicate cancellation arguments of \cite{BJ25a} that heavily exploit the structure of dyadic decomposition.
Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .
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.
We study the convergence rate of randomized quasi-Monte Carlo (RQMC) methods for integrands with different smoothness. The Koksma--Hlawka inequality fails to be informative for certain L2 singular integrands. We provide convergence results based on spectral analysis.