An introduction to Randomized Quasi-Monte Carlo Methods and its Applications

DATES: 2 - 6 March 2020 (5 sessions)
TIME: 9:30 - 11:30 (a total of 10 hours)
LOCATION: BCAM Seminar room

ABSTRACT:
An inevitable task of numerous mathematical applications is the approximation of a high- dimensional integral or, equivalently, the estimation of the expected value of a random variable that represents a complicated stochastic model. A widely known technique to carry out this task is Monte Carlo (MC), where one uses the empirical mean of n evaluations of the integrand/simulations of the model, which are obtained by an uniformly distributed sample. In doing so, the variance of this estimator converges as 1/n asymptotically in n. In this course, we analyze and discuss two refinements of MC which lead to considerably faster convergence rates of pertinent error measures in many cases. These are quasi-Monte Carlo (QMC) and randomized quasi-Monte Carlo (RQMC) methods. For QMC, the random sample is replaced by deterministically chosen, very evenly distributed points. RQMC uses such QMC samples and randomizes them through specialized techniques. This restores the theoretical uniform distribution of the sample and induces negative dependence between the points for variance reduction. The aim of this course is not only to give an insight into the theoretical framework of (R)QMC, but also, firstly, to make (R)QMC easily accessible to the attendants by familiarizing them with state-of-the-art software tools and, secondly, to convey the competitive edge of (R)QMC over MC through its application to option pricing, the simulation of chemical reaction networks, and probability density estimation of stochastic models.

PROGRAMME:
1. Introduction. On the first day, we discuss the conceptual differences between MC, QMC, and RQMC, introduce basic notions, and provide a quick guide through the foundations of these methods.
2. Convergence analysis in reproducing kernel Hilbert spaces. We introduce the notion of reproducing kernel Hilbert spaces and illustrate why they are particularly useful for (R)QMC error analysis with the help of the so-called Korobov space. The demonstrated techniques can be applied one-to-one in many other function spaces.
3. Weighted spaces, explicit constructions, and the curse of dimensionality. Modern (R)QMC theory allows to allocate weights to (collections of) variables to account for their importance for the problem at hand. We consider this, again, for functions in the Korobov space. Moreover, we present fast explicit problem-specific construction algorithms for QMC points and discuss tractability, i.e., the relation between the dimensionality of the problem and the necessary sample size to attain a certain error bound.
4. R)QMC software and density estimation with (R)QMC During the first half of this day, we guide through two state-of-the-art pieces of software for (R)QMC: LatNetBuilder (a tool to generate QMC samples) and Stochastic Simulation in Java (a library that allows for easy implementation of (R)QMC experiments). During the second half, we focus on one novel application for RQMC, namely estimating probability densities of stochastic models.
5. Simulating Markov chains with array-RQMC Simulating Markov chains is particularly hard for RQMC. A specialized algorithm, array-RQMC, helps to overcome several of the inherent issues. Little is known theoretically about the performance of array-RQMC, so we demonstrate its efficiency with two applications (option pricing and chemical reaction networks), and outline and discuss open problems.

REFERENCES:
- A. Ben Abdellah, P. L'Ecuyer, A. B. Owen, and F. Puchhammer, ``Density Estimation by Randomized Quasi-Monte Carlo,'' Under revision, 2019. (arXiv:1807.06133)
- A. Ben Abdellah, P. L'Ecuyer, F. Puchhammer, ``Array-RQMC for Option Pricing Under Stochastic Volatility Models,'' Proceedings of the 2019 Winter Simulation Conference, IEEE Press, 2019, to appear.
- J. Dick, F. Pillichshammer, Digital Nets and Sequences - Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010
- P. L'Ecuyer, ``Randomized Quasi-Monte Carlo: An Introduction for Practitioners'', invited tutorial, in Monte Carlo and Quasi Monte Carlo Methods: MCQMC 2016, P. W. Glynn and A. B. Owen, Eds., Springer-Verlag, 2018, 29-52.
- P. L'Ecuyer, L. Meliani, and J. Vaucher, ``SSJ: A Framework for Stochastic Simulation in Java'', Proceedings of the 2002 Winter Simulation Conference, IEEE Press, Dec. 2002, 234-242.
- P. L'Ecuyer and D. Munger, ``Algorithm 958: LatticeBuilder: A General Software Tool for Constructing Rank-1 Lattice Rules'', ACM Transactions on Mathematical Software, 42, 2 (2016), Article 15
- P. L'Ecuyer, F. Puchhammer, and A. Ben Abdellah, ``Monte Carlo and Quasi-Monte Carlo Density Estimation via Conditioning,'' submitted, 2019. (arXiv:1906.04607)
- G. Leobacher, F. Pillichshammer, "Introduction to Quasi-Monte Carlo Integration and Applications", Birkhäuser, Basel, 2014.


*Registration is free, but mandatory before February 28th. To sign-up go to https://forms.gle/pFsm9o1gLQdsgUZh6 and fill the registration form.

Student grants are available. Please, let us know if you need support for travel and accommodation expenses in the previous form before January 31st.

• An Introduction To Randomized Quasi-Monte Carlo Methods And Its Applications - Slides
• BCAM_Course_2020_03_02