Importance sampling for Markov chains: computing variance and determining optimal measures

ABSTRACT

In this paper we describe several computational algorithms useful in studying importance sampling (IS) for Markov chains. Our algorithms compute optimal IS measures and evaluate the estimate variance for a given measure. As knowledge of the optimal IS measure implies knowledge of the quantity to be estimated, our algorithms produce this quantity as a by-product. Since effective IS measures must often closely approximate the optimal measure, the use of these algorithms for small problems may produce in sights that lead to effective measures for larger problems of actual interest. We consider two classes of problems: hitting times and fixed-horizon costs.

REFERENCES

• 1: Andrad6ttir, S., Heyman, D.P., and Teunis, J.Ott, 1995, "On the Choice of Alternative Measures in Importance Sampling with Markov Chains," Operations Research, Vol. 43, No. 3, May-June 1995.
• 2: Dimitri P. Bertsekas, Dynamic programming: deterministic and stochastic models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 4: Cottrell, M., Fort, J. and MMgouyres, G., 1983, " Large Deviations and Rare Events in the Study of Stochastic Algorithms," IEEE Transactions on Automatic Control, Vol. AC-28, No. 9, pp. 907-920.
• 5: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 6: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 7: Kemeny, J.G., and Snell,J.L., 1976, Fini~.e Markov Chains, Springer-Verlag, New York.
• 8: Kuruganti, I., and Strickland, S.G., 1995, "Optimal Importance Sampling For Markovian Systems," Proceedings of the 1995 IEEE Conference on Systems, Man and Cybernetics.
• 9: Parekh, S., and Walrand, J., 1989, "A Quick Simulation Method for Excessive Backlogs in Networks of Queues," IEEE Transactions on Automatic Control, Vol. 34, No.l, pp. 54-66.
• 10: Sadowsky, J., S., 1993, "On the Optimality and Stability of Exponential Twisting in Monte Carlo Estimation," IEEE Transactions on Informalion Theory, Vol. 39, pp. 119-128.
• 11: Stephen G. Strickland, Optimal importance sampling for quick simulation of highly reliable Markovian systems, Proceedings of the 25th conference on Winter simulation, p.437-444, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256683]