ON THE OPTIMALITY AND STABILITY OF EXPONENTIAL TWISTING IN MONTE-CARLO ESTIMATION

Let S(n) = SIGMA(k=1)n X(k) be a sum of n i.i.d. random variables. Estimation of the large deviations probability P(S(n) greater-than-or-equal-to gamman) via importance sampling, a Monte Carlo technique based on sampling (X1,...,X(n) from a sampling distribution Q(.) not-equal P(.), is considered. It has been previously shown that within the nonparametric candidate family all i.i.d. (or, more generally, Markov) distributions, the optimized exponentially twisted distribution is the unique asymptotically optimal sampling distribution. As n --> infinity, the sampling cost required to stabilize the normalized variance var(Q)[p(n)]/p(n)2 grows with strictly positive exponential rate for any suboptimal sampling distribution, while this sampling cost for the optimal exponentially twisted distribution is only O(n1/2). Here, it is established that the optimality is actually much stronger. As n --> infinity, this solution simultaneously stabilizes all error moments of both the sample mean and the sample variance estimators with sampling cost O(n1/2). In addition, it is shown that the embedded parametric family of exponentially twisted distributions has a certain uniform asymptotic stability property. The technique is stable even if the optimal twisting parameter(s) cannot be precisely determined.