Algorithms for sensitivity analysis of Markov systems through potentials and perturbation realization

Abstract—We provide algorithms to compute the performance derivatives of Markov chains with respect to changes in their transition matrices and of Markov processes with respect to changes in their infinitesimal generators. Our algorithms are readily applicable to the control and optimization of these Markov systems, since they are based on analyzing a single sample path and do not need explicit specification of transition matrices, nor infinitesimal generators. Compared to infinitesimal perturbation analysis (IPA), the algorithms have a wider scope of application and require nearly the same computational effort. Numerical examples are provided to illustrate the applications of the algorithms. In particular, we apply one of our algorithms to a closed queueing network and the results are promising. Index Terms—Importance sampling, on-line optimization, per-formance sensitivity, perturbation methods, queueing networks. I