Importance Sampling for Markov Chains: Asymptotics for the Variance

P. W. Glynn

Stochastic Models, Vol. 10, 701-717 (1994)

In this paper, we apply the Perron-Frobenius theory for non-negative matrices to the analysis of variance asymptotics for simulations of finite state Markov chains to which importance sampling is applied. The results show that we can typically expect the variance to grow (at least) exponentially rapidly in the length of the time horizon simulated. The exponential rate constant is determined by the Perron-Frobenius eigenvalue of a certain matrix. Applications to cumulative costs, terminal costs, steady-state costs, and the likelihood ratio gradient estimator are presented. In addition, the implications for general discrete-event simulations are presented.