Asymptotically Optimal Allocation of Stratified Sampling with Adaptive Variance Reduction by Strata

作者：Kawai Reiichiro^*

来源：ACM Transactions on Modeling and Computer Simulation, 2010, 20(2): 9.

DOI：10.1145/1734222.1734225

• Brownian bridge
• control variates
• importance sampling
• variance reduction
• Poisson stratification
• stochastic approximation algorithm
• stratified sampling

To enhance efficiency in Monte Carlo simulations, we develop an adaptive stratified sampling algorithm for allocation of sampling effort within each stratum, in which an adaptive variance reduction technique is applied. Given the number of replications in each batch, our algorithm updates allocation fractions to minimize the work-normalized variance of the stratified estimator of the mean. We establish the asymptotic normality of the stratified estimator of the mean as the number of batches tends to infinity. Although implementation of the proposed algorithm requires a small amount of initial work, the algorithm has the potential to yield substantial improvements in estimator efficiency. Equally important is that the adaptive framework avoids the need for frequent recalibration of the parameters of the variance reduction methods applied within each stratum when changes occur in the experimental conditions governing system performance. To illustrate the applicability and effectiveness of our algorithm, we provide numerical results for a Black-Scholes option pricing, where we stratify the underlying Brownian motion with respect to its terminal value and apply an importance sampling method to normal random variables filling in the Brownian path. Relative to the estimator variance with proportional allocation, the proposed algorithm achieved a fourfold reduction in estimator variance with a negligible increase in computing time.

• 出版日期2010-4