Density estimation using quasi-Monte Carlo methods with smoothing by preintegration

Abstract

Approximating the cumulative distribution function (cdf), or probability density function (pdf), of a high-dimensional random variable is a difficult task that arises in many applications, ranging from derivatives pricing in finance to computing failure probabilities in engineering. Formulating the cdf as the expected value of an indicator function of the random variable, the problem reduces to computing a high-dimensional integral. Quasi-Monte Carlo (QMC) methods are deterministic quadrature rules that have recently achieved great success in efficiently computing high-dimensional integrals. But the success of QMC requires some level of smoothness in the integrand, which for the problem of computing a cdf is destroyed by the discontinuity caused by the indicator function. Recent work on preintegration (a.k.a. conditional sampling) showed that first integrating certain discontinuous functions with respect to a single variable results in a smoother function, but now in one dimension less. In this talk, I will present a QMC method based on randomly shifted lattice rules and a preintegration step, to approximate the cdf. The basic idea is to use preintegration to “integrate out” the discontinuity in one dimension, and then apply a lattice rule to the remaining function, which is now as smooth as the original random variable but in one dimension less. A rigorous analysis of the error shows that our cdf (and pdf) estimators achieve the same rate of convergence as using QMC to approximate the expected value only, namely, 1/N where N is the number of quadrature points. To illustrate the power of this method we apply it to a problem from option pricing and present numerical results. Along the way, I will discuss two interesting detours: an equivalence between function spaces that is the key to reconciling the QMC and preintegration theories, and the necessity of the condition that the original random variable be monotone with respect to the preintegration variable.