Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-24T01:54:21.381Z Has data issue: false hasContentIssue false
  • English
  • Français

The Maclaurin series for performance functions of Markov chains

Part of: Inference from stochastic processes Markov processes Stochastic processes

Published online by Cambridge University Press:  01 July 2016

Xi-Ren Cao
Xi-Ren Cao*
Affiliation:
Hong Kong University of Science and Technology
*
∗ Postal address: The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We derive formulas for the first- and higher-order derivatives of the steady state performance measures for changes in transition matrices of irreducible and aperiodic Markov chains. Using these formulas, we obtain a Maclaurin series for the performance measures of such Markov chains. The convergence range of the Maclaurin series can be determined. We show that the derivatives and the coefficients of the Maclaurin series can be easily estimated by analysing a single sample path of the Markov chain. Algorithms for estimating these quantities are provided. Markov chains consisting of transient states and multiple chains are also studied. The results can be easily extended to Markov processes. The derivation of the results is closely related to some fundamental concepts, such as group inverse, potentials, and realization factors in perturbation analysis. Simulation results are provided to illustrate the accuracy of the single sample path based estimation. Possible applications to engineering problems are discussed.

Keywords

Perturbation analysisfundamental matrixsample path estimation

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60G17: Sample path properties 60J45: Probabilistic potential theory 62M05: Markov processes
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 30 , Issue 3 , September 1998 , pp. 676 - 692
Copyright
Copyright © Applied Probability Trust 1998 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Supported in part by Hong Kong UPGC under grant HKUST 690/95E.

References

Benes, V. E. (1965). Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York.Google Scholar
Berman, A. and Plemmons, R. J. (1994). Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia.Google Scholar
Blanc, J. P. C. (1990). A numerical approach to cyclic-server queueing models. Queueing Systems 6, 173–188.CrossRefGoogle Scholar
Breiman, L. (1968). Probability. Addison-Wesley, Reading, MA.Google Scholar
Cao, X. R. and Chen, H. F. (1997). Potentials, perturbation realization, and sensitivity analysis of Markov processes. IEEE Trans. Automatic Control 42, 1382–1393.Google Scholar
Çinlar, E., (1975). Introduction to Stochastic Processes. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Girish, M. K. and Hu, J. Q. (1996). The departure process of the MP/G/1 queue. Submitted.Google Scholar
Gong, W. B. and Hu, J. Q. (1992). The Maclaurin series for the GI/G/1 queue. J. Appl. Prob. 29, 176–184.CrossRefGoogle Scholar
Ho, Y. C. and Cao, X. R. (1991). Perturbation Analysis of Discrete-Event Dynamic Systems. Kluwer, Boston.CrossRefGoogle Scholar
Hooghiemstra, G., Keane, M. and van de Ree, S. (1988). Power series for stationary distribution of coupled processor systems. SIAM J. Appl. Math. 48, 1159–1166.Google Scholar
Hu, J. Q., Nananukul, S. and Gong, W. B. (1993). A new approach to (s, S) inventory systems. J. Appl. Prob. 30, 898–912.CrossRefGoogle Scholar
Kemeny, J. G. and Snell, J. L. (1960). Finite Markov Chains. Van Nostrand, New York.Google Scholar
Lasserre, L. B. (1991). Exact formula for sensitivity analysis of Markov chains. J. Optimization Theory Appl. 71, 407–413.Google Scholar
Lasserre, L. B. (1994). A formula for singular pertubations of Markov chains. J. Appl. Prob 31, 829–833.Google Scholar
Meyer, C. D. Jr. (1975). The role of the group generalized inverse in the theory of finite Markov chains. SIAM Rev. 17, 443–464.Google Scholar
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York.Google Scholar
Zhu, Y. and Li, H. (1993). The MacLaurin expansion for a G/G/1 queue with Markov-modulated arrivals and services. Questa 11, 125–134.Google Scholar