Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T15:15:59.151Z Has data issue: false hasContentIssue false
  • English
  • Français

Estimation of the derivative of a stationary measure with respect to a control parameter

Part of: Parametric inference

Published online by Cambridge University Press:  14 July 2016

Felisa J. Vázquez-Abad  and
Harold J. Kushner
Felisa J. Vázquez-Abad
Affiliation:
Brown University
Harold J. Kushner
Affiliation:
Brown University
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper deals with a problem which arises in the Monte Carlo optimization of steady state or ergodic systems which can be modelled by Markov chains. The transition probability depends on a parameter, and one wishes to find the parameter value at which some performance function is minimum. The only available data are obtained from either simulation or actual operating information. For such a problem one needs good statistical estimates of the derivatives. Conditions are given for the existence of the derivative of the stationary measure with respect to the parameter, in the sense that the derivative is a signed measure, and is the limit of the natural approximating sequence. Some properties and a useful characterization of the derivative are obtained. It is also shown that, under appropriate conditions, the derivative of the n-step transition function converges to the derivative of the stationary measure as n tends to ∞. This latter result is of particular importance whether one is simply estimating or is actually optimizing via some sequential Monte Carlo procedure, since the basic observations are always taken over a finite time interval.

Keywords

MONTE CARLO OPTIMIZATIONSYSTEM SENSITIVITYSTATIONARY SYSTEMS OPTIMIZATIONPARAMETRIC ERGODIC OPTIMIZATIONSTOCHASTIC APPROXIMATION

MSC classification

Primary: 62F99: None of the above, but in this section
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 2 , June 1992 , pp. 343 - 352
Copyright
Copyright © Applied Probability Trust 1992 

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

∗

Research partially supported by AFOSR 89-0015, ARO-DAAL-03-86-K-0171.

∗∗

Research partially supported by AFOSR 89-0015, NSF-ECS 85-05674.

References

[1] Glasserman, P. (1989) Derivative estimates from sample paths of queueing systems. Bell Laboratories Report.Google Scholar
[2] Glynn, P. (1986) Stochastic approximation for Monte Carlo optimization. Proc. 1986 Winter Simulation Meeting, IEEE , 356–365.Google Scholar
[3] Glynn, P. W. (1987) Likelihood ratio gradient estimators, an overview. Proc. 1987 Winter Simulation Meeting, IEEE. Google Scholar
[4] Glynn, P. and Iglehart, D. L. (1988) Simulation methods for queues; an overview. QUESTA 3, 221–256.Google Scholar
[5] Golub, G. H. and Meyer, C. D. Jr. (1986) Using the QR factorization to compute, differentiate and estimate the sensitivity of stationary probabilities for Markov chains. SIAM J. Alg. Disc. Meth. 7, 273–281.Google Scholar
[6] Ho, Y. and Cassandras, C. (1983) A new approach to the analysis of discrete event dynamical systems. Automatica 39, 149–167.Google Scholar
[7] Holtzman, J. M. (1989) On using perturbation analysis to do sensitivity analysis: derivatives vs. differences. 28th IEEE Conference on Decision and Control , 2018–2023.Google Scholar
[8] Kushner, H. J. and Huang, H. (1981) Averaging methods for the asymptotic analysis of learning and adaptive systems with small adjustment rate. SIAM J. Control Optim. 19, 635–650.Google Scholar
[9] Reiman, M. I. and Weiss, A. (1989) Sensitivity analysis for simulations via likelihood ratios. Operat. Res. 37, 820–844.Google Scholar
[10] Revuz, D. (1975) Markov Chains. North-Holland, Amsterdam.Google Scholar
[11] Rubinstein, R. Y. (1989) Sensitivity analysis and performance extrapolation for computer simulation models. Operat. Res. 37, 72–81.Google Scholar
[12] Schweitzer, P. J. (1968) Perturbation theory and Markov chains. J. Appl. Prob. 5, 401–413.CrossRefGoogle Scholar
[13] Suri, R. and Zazanis, M. (1984) Perturbation analysis gives strongly consistent estimates for the M/G/1 queue. Management Sci. 34, 39–64.Google Scholar
[14] Vázquez-Abad, F. J. (1989) Stochastic Recursive Algorithms for Optimal Routing in Queueing Networks. , Applied Mathematics, Brown University.Google Scholar
[15] Walrand, J. (1988) An Introduction to Queueing Networks. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar