Derivative estimates from discontinuous realizations: smoothing techniques

ABSTRACT

We develop two methods for estimating derivatives of expectations from simulation of functions whose realizations are discontinuous in the parameter of differentiation. We take as motivating example the estimation of the sensitivity of expected terminal reward for processes on discrete state spaces. Both our methods use conditional expectations to smooth discontinuites. The first smooths the dependence on the differentiation parameter, while the second smooths dependence on the time parameter. The methods are illustrated through examples, including stochastic networks, networks of queues, and Markov processes.

REFERENCES

• 1: Burman, D. Y., "Insensitivity in queueing systems", Advances an Applied Probability, 13, pp. 846--859, 1981.
• 2: Fox, B. L., "Complexity of gradient estimation for transient Markov chains", Technical Report, University of Montreal, 1987.
• 3: Fox, B. L. and Glynn, P. W., "Discrete time conversion for simulating finite-horizon Markov processes", Technical Report, University of Colorado, Denver, 1989.
• 4: Glasserman, P., "Performance continuity and differentiability in Monte Carlo optimization", Proceedings of the Winter Simulation Conference, M. Abrams, P. Haigh and J. Comfort, (eds.), pp. 518--524, 1988.
• 5: Glasserman, P., "Structural conditions for perturbation analysis derivative estimation: finite-time performance indices", submitted for publication, 1988.
• 6: Glasserman, P., "Derivative estimates from simulation of continuous-time Markov chains", submitted for publication, 1989.
• 7: Glasserman, P. and Gong, W. B., "Smoothed perturbation analysis for a class of discrete event systems", submitted for publication, 1989.
• 8: Gong, W. B. and Ho, Y. C., "Smoothed perturbation analysis of discrete event dynamical systems", IEEE Transactions on Automatic Control, 32, pp. 858--866, 1987.
• 9: Heidelberger, P. and Goyal, A., "Sensitivity analysis of continuous time Markov chains using uniformization", in 2nd International Workshop on Applied Mathematics and Performance/Reliability Models of Computer/Communication Systems, University of Rome II, pp. 93--104, 1987.
• 10: Karlin, S. and Taylor, H. M., A Second Course in Stochastic Processes", Academic Press, New York, 1981.
• 11: Zazanis, M., "Compensators and Derivative Estimation for Queueing Systems", Proceedings of the 26th Allerton Conference, pp. 549--555, 1988.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Smoothing

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Performance, Theory