IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v34y1988i11p1281-1302.html
   My bibliography  Save this article

Convergence Properties of Infinitesimal Perturbation Analysis Estimates

Author

Listed:
  • Philip Heidelberger

    (IBM Research Division, Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, New York 10598)

  • Xi-Ren Cao

    (Digital Equipment Corporation, 200 Forest Street, Marlboro, Massachusetts 01752)

  • Michael A. Zazanis

    (Department of Industrial Engineering, Northwestern University, Evanston, Illinois 60201)

  • Rajan Suri

    (Department of Industrial Engineering, University of Wisconsin, Madison, Wisconsin 53706)

Abstract

Infinitesimal Perturbation Analysis (IPA) is a method for computing a sample path derivative with respect to an input parameter in a discrete event simulation. The IPA algorithm is based on the fact that for certain parameters and any realization of a simulation, the change in parameter can be made small enough so that only the times of events get shifted, but their order does not change. This paper considers the convergence properties of the IPA sample path derivatives. In particular, the question of when an IPA estimate converges to the derivative of a steady state performance measure is studied. Necessary and sufficient conditions for this convergence are derived for a class of regenerative processes. Although these conditions are not guaranteed to be satisfied in general, they are satisfied for the mean stationary response time in the M/G/1 queue. A necessary condition for multiple IPA estimates to simultaneously converge to the derivatives of steady state throughputs in a queueing network is determined. The implications of this necessary condition are that, except in special cases, the original IPA algorithm cannot be used to consistently estimate steady state throughput derivatives in queueing networks with multiple types of customers, state-dependent routing or blocking. Numerical studies on IPA convergence properties are also presented.

Suggested Citation

  • Philip Heidelberger & Xi-Ren Cao & Michael A. Zazanis & Rajan Suri, 1988. "Convergence Properties of Infinitesimal Perturbation Analysis Estimates," Management Science, INFORMS, vol. 34(11), pages 1281-1302, November.
    • Handle: RePEc:inm:ormnsc:v:34:y:1988:i:11:p:1281-1302
    DOI: 10.1287/mnsc.34.11.1281
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.34.11.1281
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.34.11.1281?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bernd Heidergott & Taoying Farenhorst-Yuan, 2010. "Gradient Estimation for Multicomponent Maintenance Systems with Age-Replacement Policy," Operations Research, INFORMS, vol. 58(3), pages 706-718, June.
    2. Barry L. Nelson, 2004. "50th Anniversary Article: Stochastic Simulation Research in Management Science," Management Science, INFORMS, vol. 50(7), pages 855-868, July.
    3. Koltai, Tamas & Lozano, Sebastian, 1998. "Sensitivity calculation of the throughput of an FMS with respect to the routing mix using perturbation analysis," European Journal of Operational Research, Elsevier, vol. 105(3), pages 483-493, March.
    4. Marvin K. Nakayama & Perwez Shahabuddin, 1998. "Likelihood Ratio Derivative Estimation for Finite-Time Performance Measures in Generalized Semi-Markov Processes," Management Science, INFORMS, vol. 44(10), pages 1426-1441, October.
    5. Cao, Xi-Ren, 1996. "Perturbation analysis of discrete event systems: Concepts, algorithms, and applications," European Journal of Operational Research, Elsevier, vol. 91(1), pages 1-13, May.
    6. Yao Zhao & Benjamin Melamed, 2006. "IPA Derivatives for Make-to-Stock Production-Inventory Systems with Backorders," Methodology and Computing in Applied Probability, Springer, vol. 8(2), pages 191-222, June.
    7. Benjamin Melamed & Yihong Fan & Yao Zhao & Yorai Wardi, 2010. "IPA derivatives for a discrete model of make-to-stock production-inventory systems with backorders," Annals of Operations Research, Springer, vol. 181(1), pages 1-19, December.
    8. Yihong Fan & Benjamin Melamed & Yao Zhao & Yorai Wardi, 2009. "IPA Derivatives for Make-to-Stock Production-Inventory Systems With Backorders Under the (R,r) Policy," Methodology and Computing in Applied Probability, Springer, vol. 11(2), pages 159-179, June.
    9. Erwan Koch & Christian Y. Robert, 2018. "Stochastic derivative estimation for max-stable random fields," Papers 1812.05893, arXiv.org, revised Nov 2020.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:34:y:1988:i:11:p:1281-1302. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.