Constructions and applications of quasi-random point sets with negative dependence

Abstract

Randomized Quasi-Monte Carlo (RQMC) methods are used as an alternative to the Monte Carlo (MC) method when performing numeric integration by replacing the random point set of MC with a randomized low-discrepancy sequence (LDS). Although RQMC methods have been shown to have better convergence rates than MC, especially for smooth functions, it does not hold in general that the RQMC method has lower variance than the MC method. Using the framework of negative dependence, a quasi-monotone function integrated using an LDS with the property of negative dependence has been shown to have variance no larger than that of the MC estimator. We show by numerical examples how to use the framework of negative dependence to evaluate the quality of various point sets, including Sobol' and Faure sequences.

We show, in a similar vein, how scrambled Halton sequences also have a form of negative dependence that is desirable for the purpose of improving upon the MC method for multivariate integration. The scrambling methods with such properties are based on either the nested uniform permutations of Owen or the random linear scrambling of Matousek. The framework of negative dependence is also used to develop new criteria for assessing the quality of generalized Halton sequences, in such a way that they can be analyzed for finite (potentially small) point set sizes and be compared to digital net constructions. Using this type of criteria, parameters for a new generalized Halton sequence are derived. Numerical results are presented to compare different generalized Halton sequences and their randomizations.

Applications of these point sets include mapping them onto surfaces that are not the unit hypercube. K. Basu and A. Owen have recently developed RQMC methods on the triangle based on the van der Corput sequence. We improve upon the poor one-dimensional projections of this deterministic triangular van der Corput sequence. Rather than using scrambling directly to address this issue, we show how to modify the triangular van der Corput sequence to construct a stratified sampling scheme. More precisely, we show that nested scrambling is a way to implement an extensible stratified estimator based on a stochastic but balanced allocation. We also perform a numerical study to compare the different constructions.