Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

WORLD SCIENTIFIC eBooks

Multidimensional Variation for Quasi-Monte Carlo

Art B. Owen

Published Mar 1, 2005• 133 citations
Publisher

Abstract

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

DOI
10.1142/9789812567765_0004

Related papers

Quasi-Monte Carlo Beyond Hardy-Krause

Nikhil Bansal, Haotian Jiang

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.

arXiv:2408.06475•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•2 citations

Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice

Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang

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 $\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $σ_{\mathsf{SO}}(f)$ can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires $n^2$ 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 $\varepsilon > 0$, we show that $(1+\varepsilon)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}.

arXiv:2609.10921•Sep 10, 2026•0 citations

The average dimension of a multidimensional function for quasi-Monte Carlo estimates of an integral

Danil Asotsky, Elena Evgenievna Myshetskaya, Ilya M. Sobol

The effective dimension of a multidimensional function was previously introduced to measure the complexity of the function with respect to the evaluation of an integral by quasi-Monte Carlo methods. For the same goal, the concept of the average dimension is introduced, which, in contrast to the effective dimension, is independent of an arbitrary confidence level.

Computational Mathematics and Mathematical Physics•Dec 1, 2006•12 citations

QMC integration errors and quasi-asymptotics

Ilya M. Sobol, Boris V. Shukhman

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

Monte Carlo Methods and Applications•Jul 16, 2020•2 citations

Quasi-Monte Carlo integration of functions of unbounded variation

Ronald F. A. Cools, Tim Pillards

qMC integration of functions of unbounded variation Quasi-Monte Carlo Functions of unbounded variation Conclusion

•Sep 1, 2006•0 citations

On the Convergence Rate of Randomized Quasi--Monte Carlo for Discontinuous Functions

Zhijian He, Xiaoqun Wang

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)+\epsilon})$ for any $\epsilon>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/(4d_u-2)+\epsilon})$, where $d_u$ 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.

SIAM Journal on Numerical Analysis•Jan 1, 2015•28 citations
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(1 + \varepsilon)n(1+ε)n Samples Suffice
Numerical integration studies how well one can estimate the integral of a function fff over [0,1)d[0,1)^d[0,1)d using nnn 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 O~d(σSO(f)/n)\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)Od​(σSO​(f)/n), where the smoothed-out variation σSO(f)σ_{\mathsf{SO}}(f)σSO​(f) can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires n2n^2n2 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\varepsilon > 0ε>0, we show that (1+ε)n(1+\varepsilon)n(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)o(n^{-1/2})o(n−1/2) for discontinuous functions. For certain discontinuous functions in ddd dimensions, we prove that the RMSE of RQMC is O(n−1/2−1/(4d−2)+ϵ)O(n^{-1/2-1/(4d-2)+\epsilon})O(n−1/2−1/(4d−2)+ϵ) for any ϵ>0\epsilon>0ϵ>0 and arbitrary nnn. If some discontinuity boundaries are parallel to some coordinate axes, the rate can be improved to O(n−1/2−1/(4du−2)+ϵ)O(n^{-1/2-1/(4d_u-2)+\epsilon})O(n−1/2−1/(4du​−2)+ϵ), where dud_udu​ 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))O(n^{-1/2-1/(2d)})O(n−1/2−1/(2d)) for certain indicator functions.