Asymptotic Simulation Efficiency Based on Large Deviations
Consider a simulation estimator alpha(c) based on expending c units of computer time to estimate a quantity alpha. In comparing competing estimators for alpha, a natural figure of merit is to choose the estimator that minimizes the computation time needed to reduce the error probability P(vertical bar alpha(c) - alpha vertical bar > epsilon) to below some prescribed value delta. In this paper, we develop large deviations results that provide approximations to the computational budget necessary to reduce the error probability to below delta when delta is small. This approximation depends critically on both the distribution of the estimator itself and that of the random amount of computer time required to generate the estimator, and leads to different conclusions regarding the choice of preferred estimator than those obtained when one requires the error tolerance epsilon to be small. The "small epsilon" regime leads to variance-based selection criteria, and has a long history in the simulation literature going back to Hammersley and Handscomb.
efficiency large deviations monte carlo simulation