CONSTRAINED SOLUTIONS IN IMPORTANCE SAMPLING VIA ROBUST STATISTICS

The problem of estimating expectations of functions of random vectors via simulation is investigated. Monte Carlo simulations, also known as simple averaging, have been employed as a direct means of estimation. A technique known as Importance Sampling can be used to modify the simulation via weighted averaging in the hope that the estimate will converge more rapidly to the expected value than standard Monte Carlo simulations. The fundamental problem in Importance Sampling is to determine the appropriate density function for the underlying random vector in the simulation. Since the unconstrained optimal solution to this problem is typically degenerate, suboptimal solutions have been of the form of a scaled, linearly shifted or exponentially tilted version of the original density. In this paper, we derive a constrained optimal solution to the problem of minimizing the variance of the Importance Sampling estimator. This is accomplished by finding the distribution which is "closet" to the unconstrained optimal solution in the Ali-Silvey sense. The solution from the constraint class is shown to be the least favorable density function in terms of Bayes risk against the optimal density function. Examples of constraint classes, which include membership-sign-mixture, will show that the constrained optimal solution can be made arbitrarily close to the optimal solution. Applications to estimating probability of error in communication systems are presented.