The researcher faced with a computationally intensive simulation will either seek powerful processing capa bilities or turn to variance reduction techniques. In many situations, a combination of both approaches is required to achieve the desired accuracy. In the study of rare events, importance sampling (IS) is the only variance reduction technique which has been shown to offer the potential for substantial run time im provement. Indeed the dramatic improvements in run time demonstrated in the literature is strong motiva tion for the researcher to adopt IS as a day-to-day simulation tool. For this reason, it is important to have a clear understanding of the problems inherent in IS as well as the possibilities for improvement it offers. Hence in this paper, we discuss the potential problem with IS in underestimating the probability of rare events. We describe and illustrate the problem and suggest diagnostic plots to check for its occur rence. These diagnostics are quick and simple to use in any simulation and give the experimenter an easily interpreted output to identify the possible presence of underestimation in the simulation.
Al-Qaq, W.A. , Devetsikiotis, M. and Townsend. J.K.Importance sampling methodologies for simulation of communication systems with time-varying channels and adaptive equalizers . IEEE Transactions on Communications. Vol. 11, No. 3, pp 317-327, 1993.
2.
Al-Qaq, W.A. , Devetsikiotis, M. and Townsend. J.K.Stochastic gradient optimization of importance sampling for the efficient simulation of digital communication systems. IEEE Transactions on Communications . Vol. 43, No. 12. pp 2975-2985, 1995.
3.
Andradottir, S. and Heyman, D.P.On the choice of alternative measures in importance sampling with Markov-chains. Operations Research. Vol. 43, No. 3, pp 509-519, 1995.
4.
Letaief, K.B. and Sadowsky, J.S.Computing bit-error probabilities for avalanche photodiode receivers by large deviations theory. IEEE Transactions on Information. Vol. 38, No. 3, pp 1162-1169, 1992.
5.
Bucher, C.G.Adaptive sampling-an iterative fast Monte Carlo procedure. Structural Safety. Vol. 5, pp 119-126, 1988.
6.
Bucklew, J.A.Large Deviation Techniques in decision, simulation and estimation. John Wiley, New York, 1990.
7.
Bucklew, J.A. , Ney, P. and Sadowsky, J.S.Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Prob. Vol. 27, pp 44-59, 1990.
8.
Chen, J.-C. , Lu, D., Sadowsky , J.S, and Yao, K.On importance sampling in digital communication—Part I: Fundamentals. IEEE Journal on Selected Areas in Communications . Vol. 11, No. 3, pp 289-299, 1993.
9.
Cottrell, M., Fort, J.C. and Malgouyres , G.Large Deviations and rare events in the study of stochastic algorithms. IEEE Transactions on Automatic Control. Vol. AC-28, No. 9, pp 907-920, 1983.
10.
Davis, B.R.An improved importance sampling method for digital communication system simulations. IEEE Transactions on Communications. COM, Vol. 34, No. 7, pp 715-719, 1986.
11.
Devetsikiotis, M. and Townsend, J.K.An algorithmic approach to the optimization of importance sampling parameters in digital communication system simulation . IEEE Transactions on Communication. Vol. 41, No. 10, pp 1464-1473, 1993 .
12.
Devetsikiotis, M. and Townsend, J.K.Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks . IEEE/ACM Transactions on Networking. Vol. 1, No. 3, pp 293-305, 1993.
13.
Gao, H. and Smith, P.J.Design and analysis for coherent optical systems. Report No. 3., Technical Report, ISOR, Victoria University of Wellington, Wellington, New Zealand, 1992.
14.
Glynn, P.W. and Iglehart, D.L.Importance sampling for stochastic simulations. Management Science, Vol. 35, pp 1367-1392, 1989 .
15.
Hahn, P. and Jeruchim, M.C.Developments in the theory and application of importance sampling . IEEE Transactions on Communications. COM, Vol. 35, No. 7, 706-714, 1987.
16.
Hammersley, J.M. and Handscomb , D.C.Monte Carlo Methods . Chapman and Hall. New York, 1964 .
17.
Hopmans, A.C.M. and Kleijnen , J.P.C.Importance samplings in systems simulation: A practical failure. Math. and Comput. in Simulation. Vol. 31, pp 209-220, 1979.
Jeruchim, M.C.Techniques for estimating the bit error rate in the simulation of digital communication systems. IEEE Journal on Selected Areas in Communications. SAC, Vol 2, No. 1, pp 153-170, 1984.
20.
Kahn, H.Random sampling (Monte Carlo) techniques in neutron attenuation problems. I. Nucleonics. pp 27-37, May 1950.
21.
Kahn, H.Use of different Monte Carlo sampling techniques. In Meyer, H.A (editor). Symposium on Monte Carlo Methods. John Wiley, 1956.
22.
Kendall, M.G. , Stuart, A., Ord , J.K. and O'Hagan, A.Kendall's advanced theory of statistics. Sixth Edition. Halsted Press, London. 1994.
23.
Lewis, P.A.W. and Orav, E.J.Simulation methodology for Statisticians , Operations Analysts, and Engineers. Vol. 1. Wadsworth & Brooks/Cole Advanced Books & Software. Pacific Grove, CA. 1989.
24.
Lu, D. and Yao, K.Improved importance sampling technique for efficient simulation of digital communication systems. IEEE Journal on Selected Areas in Communications. Vol. 6, No. 1, pp 67-75, 1988.
Nelson, B.L. and Schmeiser, B.W.Decomposition of some well-known variance reduction techniques. J. Statistical Computation Simulation. Vol. 23, pp 183-209, 1986.
27.
Orsak, G.C. and Aazhang, B.A class of optimum importance sampling strategies . Information Sciences. Vol. 84, No. 1-2, pp 139-160, 1995.
28.
Orsak, G.C. and Aazhang, B.Constrained solutions in importance sampling via robust statistics. IEEE Journal on Information Theory. Vol. 37, No. 2, pp 307-316, 1991.
29.
Ripley, B.Stochastic Simulation. Wiley, New York, 1987.
30.
Sadowsky, J.S.A new method for Viterbi decoder simulation using importance sampling. IEEE Transactions on Communications. Vol. 38, No. 9, pp 1341-1351, 1990.
31.
Sadowsky, J.S.On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Transactions on Information Theory. Vol. 39, No. 1, pp 119-128, 1993.
32.
Sadowsky, J.S. and Bucklew, J.A.On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Transactions on Information Theory. Vol. 36, No. 3, pp 579-588, 1990.
33.
Shanmugam, K.S. and Balaban, P.A modified Monte-Carlo simulation technique for the evaluation of error rate in digital communication systems . IEEE Transactions and Communications. COM, Vol. 28, No. 11, pp 1916-1924, 1980 .
34.
Smith, P.J.Shafi, M. and Gao, H.Quick simulation: A review of importance sample techniques in communication systems. IEEE Journal on Selected Areas in Communications. Vol. 15, pp 597-613, 1997.
35.
Stadler, J.S. and Roy, S.Importance sampling for detection of scale problems. IEEE Transactions on Communications. Vol. 43, No. 12, pp 2862-2965, 1995 .
36.
Wilson, J.R.Variance reduction techniques for digital simulation . Ann. J. Math. Manage. Sci. Vol 4, No. 3, pp 277-312, 1984.
