On the optimal Markov chain of IS simulation

We investigate the importance sampling (IS) simulation for the sample avera ge of an output sequence from an irreducible Markov chain. The optimal Mark ov chain used in simulation is known to be a twisted Markov chain, however, the proofs in [2], [3] are very complicated and do not give us a good pers pective. We give a simple and natural proof for the optimality of the simul ation Markov chain in terms of the Kullback-Leibler (KL) divergence of Mark ov chains. The performance degradation of the IS simulation by using a not optimal simulation Markov chain, i.e., the difference between the obtained variance and the minimum variance is shown to be represented by the KL dive rgence. Moreover, we show a geometric relationship between a simulation Mar kov chain and the optimal one.