Abstract
We consider first a discrete event static system that is to be simulated at values of a parameter or vector of parametersθ. The system is assumed driven by an inputX, where typicallyX is a vector of variables whose densityf θ (x) depends on the parameterθ. For the purpose of optimizing, finding roots, or graphing the expected performanceE θ L(X) for performance measureL, it is useful to estimate not only the expected value but also its gradient. An unbiased estimator for the latter is the score function estimator
This estimator and likelihood ratio analogues typically require variance reduction, and we consider conditioning on the value of the score function for this purpose. The efficiency gains due to performing the Monte Carlo conditionally can be very large. Extension to discrete event dynamic systems such as theM/G/1 queue and other more complicated systems is considered.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
H. Arsham, A. Feuerverger, D.L. McLeish, R.Y. Rubinstein and J. Kreimer, Sensitivity analysis and the “what if” problem in simulation analysis, Math. Comp. Mod. 12(1985)193–219.
S. Asmussen and R.Y. Rubinstein, The efficiency and heavy traffic properties of the score function method in sensitivity analysis of queueing models, Manuscript, Aalborg University, Denmark (1989).
X. Cao, Sensitivity estimates based on one realization of a stochastic system, J. Stat. Comp. Simul. 27(1987)211–232.
X. Cao, Convergence of parameter sensitivity estimates in a stochastic experiment, IEEE Trans. Auto. Control AC-30(1985)845–853.
X. Cao and Y.C. Ho, Estimating the sojoum times sensitivity in queueing networks using perturbation analysis, JOTA 53(1987)353–375.
D.R. Cox and D.V. Hinkley,Theoretical Statistics (Chapman and Hall, New York, 1974).
A. Feuerverger, D.L. McLeish and R.Y. Rubinstein, A cross spectral method for sensitivity analysis of computer simulation models, C.R. Math. Rep. Acad. Sci. Canada 8, no. 5 (1986).
P.W. Glynn, Gradient estimation for generalized semi-Markov processes,3rd TIMS/ORSA Special Interest Conf. on Applied Probability (1985).
P.W. Glynn, Sensitivity analysis for stationary probabilities of a Markov chain,Proc. 4th Army Conf. on Applied Mathematics and Computing (1986).
P.W. Glynn, Stochastic approximation for Monte Carlo optimization,Proc. 1986 Winter Simulation Conf. (1986).
P.W. Glynn, Optimization of stochastic systems via simulation,Proc. 1989 Winter Simulation Conf., ed. E.A. MacNair, K.J. Musselman and P. Heidelberger (1989), pp. 90–105.
J.M. Hammersley, Monte Carlo methods for solving multivariate problems, Ann. New York Acad. Sci. 86(1960)844–874.
P. Heidelberger, X. Cao, M.A. Zazanis and R. Suri, Convergence properties of infinitesimal perturbation analysis estimates, Manag. Sci. 34(1988)1281–1302.
Y.C. Ho and X. Cao, Perturbation analysis and optimization of queueing networks, JOTA 40(1983)559–582.
Y.C. Ho, M.A. Eyler and T.T. Chien, A gradient technique for general buffer storage design in a production line, Int. J. Prod. Res. 17(1979)557–580.
N. Metropolis, A.W. Teller, M.N. Rosenbluth, A.H. Teller and E. Teller, Equations of state calculations by fast computing machines, J. Chem. Phys. 21(1953)1087–1092.
C.R. Rao,Linear Statistical Inference and its Applications, 2nd ed. (Wiley, 1973).
M.I. Reiman and A. Weiss, Sensitivity analysis for simulations via likelihood ratios,Proc. 1986 Winter Simulation Conf., Washington DC (1986).
R.Y. Rubinstein, A Monte Carlo method for estimating the gradient in a stochastic network, Manuscript, Technion, Haifa, Israel (1976), unpublished.
R.Y. Rubinstein,Monte Carlo Optimization, Simulation and Sensitivity of Queueing Networks (Wiley, New York, 1986).
R.Y. Rubinstein, How to optimize discrete event systems from a single sample path by the score function method, Ann. Oper. Res. 27(1991)175–212.
R. Suri and M.A. Zazanis, Perturbation analysis gives strongly consistent sensitivity estimates for theM/G/1 queue, Manag. Sci. 34(1988)39–64.
H.F. Trotter and J.W. Tukey, Conditional Monte Carlo for normal samples, in:Symp. on Monte Carlo Methods, ed. H.A. Meyer (Wiley, New York, 1956), pp. 64–79.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
McLeish, D.L., Rollans, S. Conditioning for variance reduction in estimating the sensitivity of simulations. Ann Oper Res 39, 157–172 (1992). https://doi.org/10.1007/BF02060940
Issue Date:
DOI: https://doi.org/10.1007/BF02060940