Importance sampling for markov chains: asymptotics for the variance

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. 1. INTRODUCTION Suppose that we are given a real-valued finite-horizon performance measure Y = f(X 0 ; X 1 ; \Δ \Δ \Δ ; Xn ), where X = (Xn : n 0) is a Markov chain having initial distribution ¯ and transition matrix P . (We assume throughout this paper that the state space S is finite, unless otherwise stated.) The s...