1

Introduction to randomized quasi-Monte Carlo

aft
methods in simulation

Abstract, outline, and references

Pierre L’Ecuyer

Dr Université de Montréal, Canada

ETICS, Saissac, September 2024

Abstract

aft
Randomized quasi-Monte Carlo (RQMC) provides unbiased estimators whose variance
converges at a faster rate than standard Monte Carlo when estimating an integral, under
appropriate conditions. Variants of RQMC have been designed recently for the simulation of
Markov chains, for function approximation and optimization, for density estimation, for
solving partial differential equations, etc. In this tutorial, we will review the basic principles
and main results on RQMC, discuss their practical aspects, and give numerical illustrations
showing that they can reduce the variance by huge factors. We will look at how RQMC point
sets are constructed, how we measure their uniformity, why they can work even for

Dr
high-dimensional integrals, and how can they work when simulating Markov chains over a
large number of steps. We will show how these methods can be applied in practice by using a
Java software library that supports RQMC.
 3

Outline
▶ Monte Carlo, quasi-Monte Carlo, randomized quasi-Monte Carlo

aft
▶ QMC point sets (lattices, digital nets) and their randomizations
▶ Software and numerical illustrations with SSJ
▶ Variance bounds and convergence rates
▶ Underlying theory: Why and when does it work?
▶ Transforming the function to help RQMC
▶ Optimizing vs randomizing the point set constructions

Dr
▶ More numerical examples
▶ RQMC for Markov chains
▶ RQMC for density estimation
▶ QMC/RQMC for function approximation
 4

Software Tools in Java for QMC/RQMC

aft
For all my experiments with MC, QMC, RQMC, I use the Java library
SSJ: Stochastic Simulation in Java.
The official GitHub release is here: [Link] All the
installation instructions are there.
My own working version is at [Link] It is more recent
and has some additional material, but some parts are under construction and not fully
documented.

Dr
Personally, I use Eclipse ([Link] with Maven for Java and SSJ.
A tutorial on SSJ with commented examples:
[Link]
 5

Other QMC/RQMC Software

aft
LatNet Builder: A tool to search for good parameters for QMC/RQMC point set
constructions: [Link]
qmcpy: QMC software in Python: [Link] and
[Link]
QMC in MATLAB:
[Link]

Dr
R package qrng: [Link]
An ordered selection of general base references on QMC and RQMC 5

L’Ecuyer, P. (2018). Randomized quasi-Monte Carlo: An introduction for practitioners. In Glynn, P. W. and
Owen, A. B., editors, Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016, 29–52, Springer.
L’Ecuyer, P. (2009). Quasi-Monte Carlo methods with applications in finance. Finance and Stochastics,

aft
13(3):307–349.
Pillichshammer, F. and Leobacher, G. (2014). Introduction to Quasi-Monte Carlo Integration and
Applications. Birkhäuser Cham.
Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods, volume 63 of SIAM
CBMS-NSF Reg. Conf. Series in Applied Mathematics. SIAM.
Dick, J. and Pillichshammer, F. (2010). Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte
Carlo Integration. Cambridge University Press, Cambridge, U.K.
Dick, J., Kritzer, P., and Pillichshammer, F. (2022). Lattice Rules: Numerical Integration, Approximation, and

Dr
Discrepancy. Springer.
Lemieux, C. (2009). Monte Carlo and Quasi-Monte Carlo Sampling. Springer-Verlag.
L’Ecuyer, P. and Lemieux, C. (2002). Recent advances in randomized quasi-Monte Carlo methods. In Dror,
M., L’Ecuyer, P., and Szidarovszky, F., editors, Modeling Uncertainty: An Examination of Stochastic
Theory, Methods, and Applications, pages 419–474. Kluwer Academic, Boston.
Owen, A. B. (2023). Monte Carlo theory, methods and examples. [Link]
L’Ecuyer, P. (2023). Stochastic simulation and Monte Carlo methods. Draft Textbook,
[Link]
 5
Other selected references on QMC and RQMC (my recent work, .pdf available on my web site)

L’Ecuyer, P., Nakayama, M., Owen, A. B., and Tuffin, B. (2023). Confidence intervals for randomized
quasi-Monte Carlo estimators. In Proceedings of the 2023 Winter Simulation Conference, 445–456.
L’Ecuyer, P., Marion, P., Godin, M., and Puchhammer, F. (2022a). A tool for custom construction of QMC

aft
and RQMC point sets. In Keller, A., editor, Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2020,
pages 51–70, Springer.
L’Ecuyer, P. and Puchhammer, F. (2022). Density estimation by Monte Carlo and quasi-Monte Carlo. In
Keller, A., editor, Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2020, pages 3–21, Springer.
L’Ecuyer, P., Puchhammer, F., and Ben Abdellah, A. (2022b). Monte Carlo and quasi-Monte Carlo density
estimation via conditioning. INFORMS Journal on Computing, 34(3):1729–1748.
L’Ecuyer, P., Cherkanihassani, Y., and Derkaoui, M. E. A. (2024). Pre-scrambled digital nets for randomized
quasi-Monte Carlo. In Proceedings of the 2024 Winter Simulation Conference.
T. Goda and P. L’Ecuyer, Construction-free median quasi-Monte Carlo rules for function spaces with

Dr
unspecified smoothness and general weights, SIAM Journal on Sci. Comput., 44, 4 (2022), A2765-A2788.
Puchhammer, F. and L’Ecuyer, P. (2022). Likelihood ratio density estimation for simulation models. In
Proceedings of the 2022 Winter Simulation Conference, pages 109–120. IEEE Press.
P. L’Ecuyer, D. Munger, and B. Tuffin, On the Distribution of Integration Error by Randomly-Shifted Lattice
Rules, Electronic Journal of Statistics, Volume 4 (2010), 950-993.
P. L’Ecuyer and C. Lemieux. Variance reduction via lattice rules. Manag. Science, 46(9):1214–1235, 2000.
P. L’Ecuyer and D. Munger. Algorithm 958: Lattice builder: A general software tool for constructing rank-1
lattice rules. ACM Trans. on Mathematical Software, 42(2):Article 15, 2016.
Monte Carlo and Quasi-Monte Carlo Methods 2022, 2020, 2018, ... Books by Springer.
 5
References on Array-RQMC for Markov chains:

P. L’Ecuyer, C. Lécot, and B. Tuffin. A randomized quasi-Monte Carlo simulation method for Markov chains.
Operations Research, 56(4):958–975, 2008.
P. L’Ecuyer, D. Munger, C. Lécot, and B. Tuffin. Sorting methods and convergence rates for array-rqmc:

aft
Some empirical comparisons. Mathematics and Computers in Simulation, 143: 191–201, 2018.
Puchhammer, F., Ben Abdellah, A., and L’Ecuyer, P. (2021). Variance reduction with Array-RQMC for
tau-leaping simulation of stochastic biological and chemical reaction networks. Bulletin of Mathematical
Biology, 83(Article 91).
M. Gerber and N. Chopin. Sequential quasi-Monte Carlo. Journal of the Royal Statistical Society, Series B,
77(Part 3):509–579, 2015.
P. L’Ecuyer, V. Demers, and B. Tuffin. Rare-events, splitting, and quasi-Monte Carlo. ACM Transactions on
Modeling and Computer Simulation, 17(2):Article 9, 2007.

Dr
P. L’Ecuyer, C. Lécot, and A. L’Archevêque-Gaudet. On array-RQMC for Markov chains: Mapping
alternatives and convergence rates. Monte Carlo and Quasi-Monte Carlo Methods 2008, pages 485–500,
Springer-Verlag, 2009.
P. L’Ecuyer and C. Sanvido. Coupling from the past with randomized quasi-Monte Carlo. Mathematics and
Computers in Simulation, 81(3):476–489, 2010.