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 with respect to the biasing parameters has typically yielded solutions for systems for which the BER could be found analytically. A technique for finding an asymptotically optimal set of biasing parameter values, in the sense that as the resolution of the search and the number of runs used both approach infinity, the algorithm converges to the true optimum, is proposed. The algorithm determines the amount of biasing that minimizes a statistical measure of the variance of the BER estimate and exploits a theoretically justifiable relationship, for small sample sizes, between the BER estimate and the amount of biasing. The translation biasing scheme is considered, although the algorithm is applicable to other parametric IS techniques. Only mild assumptions are required of the noise distribution and system. Experimentally, improvement factors ranging from two to eight orders of magnitude are obtained for a number of distributions for both linear and nonlinear systems with memory.>