  Large deviation theory has provided important clues for the choice of
importance sampling measures for Monte Carlo evaluation of exceedance
probabilities. However, Glasserman and Wang [Ann. Appl. Probab. 7 (1997)
731--746] have given examples in which importance sampling measures that are
consistent with large deviations can perform much worse than direct Monte
Carlo. We address this problem by using certain mixtures of exponentially
twisted measures for importance sampling. Their asymptotic optimality is
established by using a new class of likelihood ratio martingales and renewal
theory.
