Efficient simulation of random walks exceeding a nonlinear boundary

Let $S_n:[0, 1] \rightarrow \Bbk{R}$ denote the polygonal approximation of a random walk with zero-mean increments, where both time and space are scaled by n. We consider the estimation of the probability that, for fixed n ∈ $\Bbk{N}$, Sn exceeds some positive function e. As a result of the scaling, this probability decays exponentially in n, and importance sampling can be used to achieve variance reduction. Two simulation methods are considered: path-level twisting and step-level twisting. We give necessary and sufficient conditions for both methods to be asymptotically efficient as n $\rightarrow$ ∞. Our conditions improve upon those in earlier work of Sadowsky [17].