Quasi-Monte Carlo Methods: What, Why, and How?

Abstract

Many questions in quantitative finance, uncertainty quantification, and other disciplines are answered by computing the population mean, $\hat{I}¼:=\mathbb{E}(Y)$, where instances of $Y:=f(\mathbf{X})$ may be generated by numerical simulation and $\mathbf{X}$ has a simple probability distribution. The population mean can be approximated by the sample mean, $\hat{\hat{I}}{¼}_n:=n^{-1}{\sum }_{i=0}^{n-1}f({\mathbf{x}}_i)$ for a well chosen sequence of nodes, $\{{\mathbf{x}}_0,{\mathbf{x}}_1,\dots \}$ and a sufficiently large sample size, $n$. Computing $\hat{I}¼$ is equivalent to computing a $d$-dimensional integral, $\int f(\mathbf{x})\varrho (\mathbf{x})\mathrm{d}\mathbf{x}$, where $\varrho$ is the probability density for $\mathbf{X}$. Quasi-Monte Carlo methods replace independent and identically distributed sequences of random vector nodes, $\{{\mathbf{x}}_i{\}}_{i=0}^{\infty }$, by low discrepancy sequences. This accelerates the convergence of $\hat{\hat{I}}{¼}_n$ to $\hat{I}¼$ as $n\to \infty$. This tutorial describes low discrepancy sequences and their quality measures. We demonstrate the performance gains possible with quasi-Monte Carlo methods. Moreover, we describe how to formulate problems to realize the greatest performance gains using quasi-Monte Carlo. We also briefly describe the use of quasi-Monte Carlo methods for problems beyond computing the mean, $\hat{I}¼$.