A pivotal concept in quasi-Monte Carlo (QMC) methods is the total variation, in the sense of Hardy and Krause, of a multidimensional function. The Hardy and Krause variation in turn is based on the Vitali variation. This paper presents an account of variation for QMC. It includes a perhaps surprising find that a bounded function arising in financial valuation has infinite variation. Also included is a previously unpublished low variation function extension method due to Sobol'.
A pivotal concept in quasi-Monte Carlo (QMC) methods is the total variation, in the sense of Hardy and Krause, of a multidimensional function. The Hardy and Krause variation in turn is based on the Vitali variation. This paper presents an account of variation for QMC. It includes a perhaps surprising find that a bounded function arising in financial valuation has infinite variation. Also included is a previously unpublished low variation function extension method due to Sobol'.
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}.
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}} .
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.