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

Illinois Tech Undergraduate Research Journal

(Quasi-)Monte Carlo Improtance Sampling with QMCPY

Aleksei G. Sorokin, Fred J. Hickernell, Sou-Cheng Terrya Choi, Michael J. McCourt, Jagadeeswaran Rathinavel

Published Feb 3, 2023• 0 citations
Publisher

Abstract

(Quasi-)Monte Carlo, (Q)MC, methods are a class of powerful numerical integration algorithms that have been proven to scale well to high dimensions. Various techniques exist to decrease the computational cost of (Q)MC methods. This article focuses on importance sampling, a technique that performs variable transformations to make the integral easier for (Q)MC approximation. The build up to composed importance sampling is paralleled by code from our QMCPy package that implements these concepts.

DOI
10.18409/urjiit.v1i1.48

Related papers

QMCPy: A Python Framework for (Quasi-)Monte Carlo Algorithms

Aleksei G. Sorokin, Fred J. Hickernell, Sou-Cheng Terrya Choi +3 more

Monte Carlo (MC) methods estimate high-dimensional integrals by computing sample averages at independent and identically distributed (IID) random points.Quasi-Monte Carlo (QMC) methods replace IID samples with low-discrepancy (LD) sequences which more uniformly cover the integration domain, leading to faster convergence and reduced computational requirements.

The Journal of Open Source Software•Jan 19, 2026•0 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

Randomized Quasi-Monte Carlo: An Introduction for Practitioners

Pierre L’Ecuyer

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.

•Aug 14, 2016•2 citations

A Matlab Program for Testing Quasi-Monte Carlo Constructions

Lynne Serré

The Monte Carlo method uses a random sample of size n to approximate the value of an s-dimensional integral and has a convergence rate of O(n−1/2). By using lowdiscrepancy sampling, the quasi-Monte Carlo (QMC) method achieves a convergence rate of O(n−1(log n)), which is asymptotically faster than that of the Monte Carlo method. However, due to the dependence of the QMC error bound on the dimension s, this result doesn’t hold at practical values of n for even relatively small values of s. Still, many empirical studies have shown that QMC can outperform Monte Carlo integration in highdimensional problems at practical values of n. Empirical studies are often conducted by researchers to investigate the behaviour of QMC methods since the QMC error bound suffers from several practical limitations. This paper presents a Matlab program that implements some of the more commonly used numerical tests and provides a simple graphical summary of the results.

•Jan 1, 2010•3 citations

When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Ian H. Sloan, Henryk Woźniakowski

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.

Journal of Complexity•Mar 1, 1998•605 citations

Constructive approaches to quasi-Monte Carlo methods for multiple integration

Frances Y. Kuo

Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.

•Jan 1, 2002•2 citations
(Quasi-)Monte Carlo, (Q)MC, methods are a class of powerful numerical integration algorithms that have been proven to scale well to high dimensions. Various techniques exist to decrease the computational cost of (Q)MC methods. This article focuses on importance sampling, a technique that performs variable transformations to make the integral easier for (Q)MC approximation. The build up to composed importance sampling is paralleled by code from our QMCPy package that implements these concepts.
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.
The Monte Carlo method uses a random sample of size n to approximate the value of an s-dimensional integral and has a convergence rate of O(n−1/2). By using lowdiscrepancy sampling, the quasi-Monte Carlo (QMC) method achieves a convergence rate of O(n−1(log n)), which is asymptotically faster than that of the Monte Carlo method. However, due to the dependence of the QMC error bound on the dimension s, this result doesn’t hold at practical values of n for even relatively small values of s. Still, many empirical studies have shown that QMC can outperform Monte Carlo integration in highdimensional problems at practical values of n. Empirical studies are often conducted by researchers to investigate the behaviour of QMC methods since the QMC error bound suffers from several practical limitations. This paper presents a Matlab program that implements some of the more commonly used numerical tests and provides a simple graphical summary of the results.
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.
Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.