Sensitivity analysis of stationary performance measures for Markov chains (Q1922200)

Many practical systems, such as communication systems, manufacturing systems for example, can be well described by Markov chains. In this very nice paper, the author is interested in derivative estimation of performance measures of Markov chains. He considers \(X\) a finite state space, irreducible, and a periodic Markov chain with transition matrix \(P(\theta)\) for a discrete-time system, or an infinitesimal generator \(Q(\theta)\) for a continuous-time system, and he assumes that \(\theta\in (a,b)\subset \mathbb{R}\). The state space and the cost function do not depend on \(\theta\) explicitly, since \(J(\theta)=E[f(\theta)]\), which represents the mean cost of making a state transition when the chain is stationary, is a function of \(\theta\) through \(P(\theta)\) or \(Q(\theta)\) only. This paper proposes an algorithm which is a special implementation of the structural infinitesimal perturbation analysis (SIPA) algorithm; it is designed for estimation via simulation but can be easily tailored to address the needs of derivative estimation from sample path observation. The basic procedure is to simulate the same Markov chain but with a new cost function. At each step, the value of this new cost function is estimated from some extra simulations. At one step, the extra simulations are guaranteed to require bounded computational effort. The author theoretically proves that the algorithm converges to \(J(\theta)\) at rate \(T^{-1/2}\), as the simulation time \(T\) goes to infinity. The rate \(T^{-1/2}\) is the best possible rate for derivative estimation methods such as perturbation analysis and likelihood ratio, the two best-known methods for derivative estimation. This work is different from previous ones in that the author not only imposes minimum assumptions but also guarantees a consistent estimate that attains the best possible rate of convergence.