ANALYTICAL PERTURBATIONS IN MARKOV-CHAINS

The problem of recomputing the steady-state probabilities in a Markov chain is considered, after a small deviation is introduced to the original infinitesimal generator. Approximate expressions are developed to calculate the corresponding perturbed vector of probabilities. Computational stability and accuracy issues associated with the approximation are discussed. As an application, the perturbation approach is incorporated into an optimization scheme to identify workloads that maximize the output rate in a production line, where qualitative and quantitative measures are introduced to control the accuracy of the perturbation.