×
Heidergott, Bernd; Leahu, Haralambie; Löpker, Andreas; Pflug, Georg

Perturbation analysis of inhomogeneous finite Markov chains. (English) Zbl 1337.60181

Adv. Appl. Probab. 48, No. 1, 255-273 (2016).
Summary: In this paper, we provide a perturbation analysis of finite time-inhomogeneous Markov processes. We derive closed-form representations for the derivative of the transition probability at time \(t\), with \(t > 0\). Elaborating on this result, we derive simple gradient estimators for transient performance characteristics either taken at some fixed point in time \(t\), or for the integrated performance over a time interval \([0,t]\). Bounds for transient performance sensitivities are presented as well. Eventually, we identify a structural property of the derivative of the generator matrix of a Markov chain that leads to a significant simplification of the estimators.

Cited in 4 Documents

MSC:

60J27 Continuous-time Markov processes on discrete state spaces
60J35 Transition functions, generators and resolvents
62M05 Markov processes: estimation; hidden Markov models
65C05 Monte Carlo methods

Keywords:

inhomogeneous finite Markov processes; gradient estimators; sensitivity analysis; infinitesimal generator
PDF BibTeX XML Cite
\textit{B. Heidergott} et al., Adv. Appl. Probab. 48, No. 1, 255--273 (2016; Zbl 1337.60181)
Full Text: DOI Euclid
  • logo of hbz
  • logo of WorldCat

References:

[1] Abdalla, N. and Boucherie, R. J. (2002). Blocking probabilities in mobile communications networks with time-varying rates and redialing subscribers. Ann. Operat. Res. 112, 15-34. · Zbl 1013.90015
[2] Abramov, V. and Liptser, R. (2004). On the existence of limiting distributions for time-nonhomogeneous countable Markov process. Queueing Systems 46 , 353-361. · Zbl 1061.90026
[3] Andreychenko, A., Crouzen, P. and Wolf, V. (2011). On-the-fly uniformization of time-inhomogeneous infinite Markov population models. In Proc. QAPL EPTCS , pp. 1-15. Available at http://published.eptcs.org Artalejo, J. R. and Gómez-Corral, A. (2008). Retrial Queueing Systems . Springer, Berlin.
[4] Banasiak, J. and Arlotti, L. (2006). Perturbations of Positive Semigroups with Applications. Springer, London. · Zbl 1097.47038
[5] Bellman, R. (1997). Introduction to Matrix Analysis , 2nd edn. SIAM, Philadelphia, PA. · Zbl 0872.15003
[6] Brémaud, P. (1992). Maximal coupling and rare perturbation sensitivity analysis. Queueing Systems Theory Appl. 11 , 307-333. · Zbl 0776.60080
[7] Brémaud, P. and Vázquez-Abad, F. J. (1992). On the pathwise computation of derivatives with respect to the rate of a point process: the phantom RPA method. Queueing Systems Theory Appl. 10 , 249-269. · Zbl 0747.60046
[8] Cao, X.-R. (2007). Stochastic Learning and Optimization: A Sensitivity-Based Approach . Springer, New York. · Zbl 1130.93057
[9] Dollard, J. D. and Friedman, C. N. (1978). On strong product integration. J. Funct. Anal. 28, 309-354. · Zbl 0404.34047
[10] Falin, G. (1990). A survey of retrial queues. Queueing Systems Theory Appl. 7 , 127-167. · Zbl 0709.60097
[11] Falin, G. I. and Templeton, J. G. C. (1997). Retrial Queues. Chapman & Hall, London. · Zbl 0944.60005
[12] Feldman, Z., Mandelbaum, A., Massey, W. A. and Whitt, W. (2008). Staffing of time-varying queues to achieve time-stable performance. Manag. Sci. 54 , 324-338. · Zbl 1232.90275
[13] Fu, M. C. (2006). Gradient estimation. In Handbook on Operations Research and Management Science: Simulation , eds S. G. Henderson and B. L. Nelson, Elsevier, Amsterdam, pp. 575-616.
[14] Fu, M. and Hu, J.-Q. (1997). Conditional Monte Carlo: Gradient Estimation and Optimization Applications . Kluwer, Boston, MA. · Zbl 0874.62093
[15] Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: tutorial, review, and research prospects. Manufacturing Service Operat. Manag. 5 , 79-141.
[16] Gill, R. D. and Johansen, S. (1990). A survey of product-integration with a view toward application in survival analysis. Ann. Statist. 18, 1501-1555. · Zbl 0718.60087
[17] Glasserman, P. (1991). Gradient Estimation via Perturbation Analysis . Kluwer, Boston, MA. · Zbl 0746.90024
[18] Glasserman, P. and Gong, W.-B. (1990). Smoothed perturbation analysis for a class of discrete-event systems. IEEE Trans. Automatic Control 35 , 1218-1230. · Zbl 0721.93051
[19] Gong, W.-B. and Ho, Y.-C. (1987). Smoothed (conditional) perturbation analysis of discrete event dynamical systems. IEEE Trans. Automatic Control 32 , 858-866. · Zbl 0634.93076
[20] Green, L. V., Kolesar, P. J. and Whitt, W. (2007). Coping with time-varying demand when setting staffing requirements for a service system. Production Operat. Manag. 16 , 13-39.
[21] Heidergott, B. and Hordijk, A. (2003). Taylor series expansions for stationary Markov chains. Adv. Appl. Prob. 35 , 1046-1070. (Correction: 36 (2004), 1300.) · Zbl 1043.60056
[22] Heidergott, B. and Leahu, H. (2010). Weak differentiability of product measures. Math. Operat. Res. 35 , 27-51. · Zbl 1228.60008
[23] Heidergott, B. and Vázquez-Abad, F. J. (2008). Measure-valued differentiation for Markov chains. J. Optimization Theory Appl. 136 , 187-209. · Zbl 1149.90173
[24] Ho, Y.-C. and Cao, X.-R. (1991). Perturbation Analysis of Discrete Event Dynamic Systems . Kluwer, Boston, MA.
[25] Johansen, S. (1986). Product integrals and Markov processes. CWI Newslett. 12, 3-13. · Zbl 0639.60081
[26] Kato, T. (1984). Perturbation Theory for Linear Operators , 2nd edn. Springer, Berlin. · Zbl 0531.47014
[27] Kulkarni, V. G. and Liang, H. M. (1997). Retrial queues revisited. In Frontiers in Queueing , CRC, Boca Raton, FL, pp. 19-34. · Zbl 0871.60074
[28] Massey, W. A. (1985). Asymptotic analysis of the time dependent \(M/M/1\) queue. Math. Operat. Res. 10 , 305-327. · Zbl 0567.60089
[29] Massey, W. A. (2002). The analysis of queues with time-varying rates for telecommunication models. Telecommun. Systems 21 , 173-204.
[30] Massey, W. A. and Whitt, W. (1998). Uniform acceleration expansions for Markov chains with time-varying rates. Ann. Appl. Prob. 8 , 1130-1155. · Zbl 0937.60066
[31] Otte, P. (1999). An integral formula for section determinants of semi-groups of linear operators. J. Phys. A 32, 3793-3803. · Zbl 0995.47022
[32] Pflug, G. C. (1996). Optimization of Stochastic Models . Kluwer, Boston, MA. · Zbl 0909.90220
[33] Rubinstein, R. Y. (1992). Sensitivity analysis of discrete event systems by the ‘push out’ method. Ann. Operat. Res. 39 , 229-250. · Zbl 0776.93024
[34] Rubinstein, R. Y. and Melamed, B. (1998). Modern Simulation and Modeling . John Wiley, New York. · Zbl 0903.60001
[35] Rubinstein, R. Y. and Kroese, D. P. (2008). Simulation and the Monte Carlo Method , 2nd edn. John Wiley, Hoboken, NJ. · Zbl 1147.68831
[36] Van Dijk, N. M. (1992). Uniformization for nonhomogeneous Markov chains. Operat. Res. Lett. 12, 283-291. · Zbl 0757.60066
[37] Van Loan, C. (1977). The sensitivity of the matrix exponential. SIAM J. Numer. Anal. 14, 971-981. · Zbl 0368.65006
[38] Vázquez-Abad, F. J. (1999). Strong points of weak convergence: a study using RPA gradient estimation for automatic learning. Automatica 35 , 1255-1274. · Zbl 0940.93078
[39] Yang, T. and Templeton, J. G. C. (1987). A survey on retrial queues. Queueing Systems 2 , 201-233. (Correction: 4 (1989), 94.) · Zbl 0658.60124
[40] Yin, G. and Zhang, Q. (1989). Continuous Time Markov Chains and Applications . Springer, New York.
[41] Zeifman, A. and Korotysheva, A. (2011). Weak ergodicity of M\(_{t}/\)M\(_{t}/N/N+R\) queue. Pliska Stud. Math. Bulgar . 20 , 243-254.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.