On-line sensitivity analysis of Markov chains

The authors consider discrete-event systems modeled as continuous-time Markov processes and characterized by some integer-valued parameter. The problem they address is that of estimating performance sensitivities with respect to this parameter by directly observing a single sample path of the system. The present approach is based on transforming the nominal Markov chain into a reduced augmented chain, whose stationary state probabilities can be easily combined to obtain stationary state probability sensitivities with respect to the given parameter. Under certain conditions, the reduced augmented chain state transitions are observable with respect to the state transitions of the system itself, and no knowledge of the nominal Markov chain state transition rates is required. Applications for some queueing systems are included. The approach incorporates estimation of unknown transition rates when needed, and is extended to real-valued parameters.