## Strongly Efficent Algorithms for Light-tailed Random Walks: An Old Folk Song Sung to a Faster New Tune
We revisit a classical problem in rare-event simulation, namely, efficient
estimation of the probability that the sample mean of n independent identically distributed
light tailed (i.e. with finite moment generating function in a neighborhood
of the origin) random variables lies in a sufficiently regular closed convex set that
does not contain their mean. It is well known that the optimal exponential tilting
(OET), although logarithmically efficient, is not strongly efficient (typically, the
squared coefficient of variation of the estimator grows at rate n *Dupuis, P., Wang, H.: Importance sampling, large deviations, and differential games. Stoch. and Stoch. Reports 76, 481–508 (2004) |