Sensitivity analysis of stationary performance measures for Markov chains
type: Item
instance of: scholarly article
title: Sensitivity analysis of stationary performance measures for Markov chains
zbMATH Open document ID: 0857.93105
DOI: 10.1016/0895-7177(96)00069-6
author: Liyi Dai
published in: Mathematical and Computer Modelling
publication date: 1997-03-12T00:00:00Z
review text: 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.
reviewed by: Claude Deniau
Mathematics Subject Classification ID: 93E99
zbMATH DE Number: 927172
zbMATH Keywords: derivative estimation
zbMATH Keywords: Markov chains
zbMATH Keywords: structural infinitesimal perturbation analysis
zbMATH Keywords: simulation
zbMATH Keywords: consistent estimate
zbMATH Keywords: rate of convergence
MaRDI profile type: Publication
full work available at URL: 0895-7177(96)00069-6
OpenAlex ID: W2056060678
cites work: Q4101255
cites work: Q4000306
cites work: Q4002098
cites work: Structural infinitesimal perturbation analysis (SIPA) for derivative estimation of discrete-event dynamic systems
cites work: Convergence Rates of Finite-Difference Sensitivity Estimates for Stochastic Systems
cites work: Smoothed (conditional) perturbation analysis of discrete event dynamical systems
cites work: Derivatives of likelihood ratios and smoothed perturbation analysis for the routing problem
cites work: Smoothed perturbation analysis derivative estimation for Markov chains
cites work: Maximal coupling and rare perturbation sensitivity analysis
cites work: Q5822308
cites work: A simple coupling of renewal processes
cites work: Maximal coupling
cites work: Estimating Derivatives Via Poisson's Equation
cites work: Q5332558
cites work: On a Stochastic Approximation Method
cites work: The Asymptotic Efficiency of Simulation Estimators
cites work: Q5732992
cites work: First-order perturbation analysis of a simple multi-class finite source queue
cites work: Q3323320
cites work: Q3026011
cites work: Markov chains and stochastic stability
description: scientific article; zbMATH DE number 927172