Strongly efficient estimators for light-tailed sums

Let (Sn : n ≥ 0) be a mean zero random walk (rw) with light-tailed increments. One of the most fundamental problems in rare-event simulation involves computing P (Sn > nβ) for β > 0 when n is large. It is well known that the optimal exponential tilting (OET), although logarithmically efficient, is not strongly efficient (the squared coefficient of variation of the estimator grows at rate n1/2). Our analysis of the zero-variance change-of-measure provides useful insights into why OET is not strongly efficient. In particular, the iid nature of OET induces an overshoot over the boundary nβ that is too big and causes the coefficient of variation to grow as [EQUATION]. We study techniques used to provide a state-dependent change-of-measure that yields a strongly efficient estimator. The application of our state-dependent algorithm to the Gaussian case reveals the fine structure of the zero-variance change-of-measure. We see how (Sn : n ≥ 0) transitions from a rw under OET to a process that looks "mean reverting" aroung βn, indicating that less bias is required as the process approaches the boundary βn.