Negative Dependence, Scrambled Nets, and Variance Bounds

In this paper, we provide a framework to study the dependence structure of sampling schemes such as those produced by randomized quasi-Monte Carlo methods. The main goal of this new framework is to determine conditions under which the negative dependence structure of a sampling scheme enables the construction of estimators with reduced variance compared to Monte Carlo estimators. To do this, we establish a generalization of the well-known Hoeffding’s lemma—expressing the covariance of two random variables as an integral of the difference between their joint distribution function and the product of their marginal distribution functions—that is particularly well suited to study such sampling schemes. We also provide explicit formulas for the joint distribution of pairs of points randomly chosen from a scrambled (0, m, s)-net. In addition, we provide variance bounds establishing the superiority of dependent sampling schemes over Monte Carlo in a few different setups. In particular, we show that a scrambled (0, m, 2)-net yields an estimator with variance no larger than a Monte Carlo estimator for functions monotone in each variable.