  In this paper it is shown that adaptive importance sampling algorithms
converge at exponential rate for Markov chain expectation problems that admit a
combination of a filtered estimator and a Markov zero-variance measure. It
extends a chain of results---special purpose proofs were already known for
several cases (Kollman et al, Baggerly et al, Desai). A recent paper (Awad et
al) provides a complete description of the class of combinations of Markov
process expectations of path functionals and filtered estimators that admit
zero-variance importance measures that retain the Markov property. In a way,
this is the maximal class for which adaptive importance sampling algorithms
might exhibit exponential convergence. The main purpose of this paper is to
prove that this is the case: for (most of) those combinations the natural
adaptive importance sampling algorithm converges at exponential rate. In
addition, the applicability of general Markov chain theory for this purpose is
discussed through the analysis of a counterexample presented in (Desai and
Glynn).
