AN ALGORITHMIC APPROACH TO THE OPTIMIZATION OF IMPORTANCE SAMPLING PARAMETERS IN DIGITAL-COMMUNICATION SYSTEM SIMULATION

Importance sampling is recognized as a potentially powerful method for reducing simulation runtimes when estimating the bit error rate (BER) of communications systems using Monte Carlo simulation. Analytically, minimizing the variance of the importance sampling (IS) estimator wit h respect to the biasing parameters has typically yielded solutions fo r systems for which the BER could be found analytically, e.g., linear system with additive Gaussian noise. We present in this paper a new te chnique for finding an asymptotically optimal set of biasing parameter values, in the sense that as the resolution of the search and the num ber of runs used both approach infinity, the algorithm converges to th e true optimum. A key feature is that repetitive, very short simulatio n runs are used to determine asymptotically optimal IS parameter value s. Thus, knowledge of the system-required by an effective importance s ampling scheme-is obtained from a controlled set of simulation runs. T he algorithm determines the amount of biasing that minimizes a statist ical measure of the variance of the BER estimate and exploits a theore tically justifiable relationship, for small sample sizes, between the BER estimate, P(e), and the amount of,biasing. In this paper we consid er the translation biasing scheme, although the algorithm is applicabl e to other parametric IS techniques. Only mild assumptions are require d of the noise distribution and system. Experimentally, improvement fa ctors ranging from two to eight orders of magnitude are obtained for a number of distributions for both linear and nonlinear systems with me mory.