An "Augmented chain " approach for on-line sensitivity analysis of Markov process

We consider discrete event systems modelled as continuous time Markov processes and characterized by some integervalued parameter. The problem we address is that of estimating performance sensitivities with respect to this parameter by directly observing a single sample path of the system. Our approach is based on combining a nominal and perturbed Markov chain into a "reduced augmented chain," with state transitions that are observable in a realization of the nominal chain. Furthermore, its stationary state probabilities can be easily combined to obtain stationary state probability sensitivities with respect to the given parameter. Under certain conditions, this approach requires no knowledge of the observed Markov process state transition rates. Applications for some queueing systems are included. The approach incorporates estimation of unknown transition rates when needed and may be extended to real-valued parameters.