skip to main content
research-article

Asymptotic robustness of estimators in rare-event simulation

Published: 08 February 2010 Publication History

Abstract

The asymptotic robustness of estimators as a function of a rarity parameter, in the context of rare-event simulation, is often qualified by properties such as bounded relative error (BRE) and logarithmic efficiency (LE), also called asymptotic optimality. However, these properties do not suffice to ensure that moments of order higher than one are well estimated. For example, they do not guarantee that the variance of the empirical variance remains under control as a function of the rarity parameter. We study generalizations of the BRE and LE properties that take care of this limitation. They are named bounded relative moment of order k (BRM-k) and logarithmic efficiency of order k (LE-k), where k ≥ 1 is an arbitrary real number. We also introduce and examine a stronger notion called vanishing relative centered moment of order k, and exhibit examples where it holds. These properties are of interest for various estimators, including the empirical mean and the empirical variance. We develop (sufficient) Lyapunov-type conditions for these properties in a setting where state-dependent importance sampling (IS) is used to estimate first-passage time probabilities. We show how these conditions can guide us in the design of good IS schemes, that enjoy convenient asymptotic robustness properties, in the context of random walks with light-tailed and heavy-tailed increments. As another illustration, we study the hierarchy between these robustness properties (and a few others) for a model of highly reliable Markovian system (HRMS) where the goal is to estimate the failure probability of the system. In this setting, for a popular class of IS schemes, we show that BRM-k and LE-k are equivalent and that these properties become strictly stronger when k increases. We also obtain a necessary and sufficient condition for BRM-k in terms of quantities that can be readily computed from the parameters of the model.

References

[1]
Asmussen, S. 2002. Large deviations in rare events simulation: Examples, counterexamples, and alternatives. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K.-T. Fang, F. J. Hickernell, and H. Niederreiter Eds., Springer, New York, 1--9.
[2]
Asmussen, S. 2003. Applied Probability and Queues. Springer, Berlin.
[3]
Bentkus, V. and Götze, F. 1996. The Berry-Esseen bound for student's statistic. The Ann. Probab. 24, 1, 491--503.
[4]
Blanchet, J. and Glynn, P. W. 2006. Strongly efficient estimators for light-tailed sums. In Proceedings of the International Conference on Performance Evaluation Methodologies and Tools. ACM Press, New York.
[5]
Blanchet, J. and Glynn, P. W. 2008. Efficient rare-event simulation for the maximum of a random walk with heavy-tailed increments. Annals Appl. Probab. 18, 4, 1351--1378.
[6]
Blanchet, J., Glynn, P. W., and Liu, J. C. 2006. State-Dependent importance sampling and large deviations. In Proceedings of the 6th International Workshop on Rare Event Simulation. W. Sandmann Ed. 154--161.
[7]
Blanchet, J., Leder, K., and Glynn, P. W. 2009. Efficient simulation of light-tailed sums: An old folk song sung to a faster new tune. In Monte Carlo and Quasi-Monte Carlo Methods 2008, P. L'Ecuyer and A. B. Owen Eds., Springer-Verlag, 227--248.
[8]
Bolhuis, P. G., Chandler, D., Dellago, C., and Geissler, P. L. 2002. Transition path sampling: Throwing ropes over rough mountain passes, in the dark. Ann. Rev. Phys. Chem. 53, 291--318.
[9]
Boots, N. K. and Shahabuddin, P. 2000. Simulating GI/GI/1 queues and insurance processes with subexponential distributions. In Proceedings of the Winter Simulation Conference. IEEE Press, 656--665.
[10]
Bourin, C. and Bondon, P. 1998. Efficiency of high-order moment estimates. IEEE Trans. Signal Process. 46, 1, 255--258.
[11]
Bucklew, J., Ney, P., and Sadowsky, J. S. 1990. Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Probab. 27, 44--59.
[12]
Bucklew, J. A. 2004. Introduction to Rare Event Simulation. Springer, New York.
[13]
Cancela, H., Rubino, G., and Tuffin, B. 2002. MTTF estimation by Monte Carlo methods using Markov models. Monte Carlo Methods Appl. 8, 4, 312--341.
[14]
Cancela, H., Rubino, G., and Tuffin, B. 2005. New measures of robustness in rare event simulation. In Proceedings of the Winter Simulation Conference. M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines Eds., IEEE Press, 519--527.
[15]
Dupuis, P. and Wang, H. 2004. Importance sampling, large deviations, and differential games. Stoch. Stoch. Rep. 76, 481--508.
[16]
Dupuis, P. and Wang, H. 2005. Dynamic importance sampling for uniformly recurrent Markov chains. Ann. Appl. Probab. 15, 1--38.
[17]
Durrett, R. 1996. Probability: Theory and Examples 2nd Ed. Duxbury Press.
[18]
Ermakov, S. M. and Melas, V. B. 1995. Design and Analysis of Simulation Experiments. Kluwer Academic, Dordrecht, The Netherlands.
[19]
Feller, W. 1971. An Introduction to Probability Theory and Its Applications Vol. 2, 2nd Ed. Wiley, New York.
[20]
Glasserman, P. 2004. Monte Carlo Methods in Financial Engineering. Springer, New York.
[21]
Glasserman, P., Heidelberger, P., Shahabuddin, P., and Zajic, T. 1998. A large deviations perspective on the efficiency of multilevel splitting. IEEE Trans. Autom. Control AC-43, 12, 1666--1679.
[22]
Glasserman, P., Heidelberger, P., Shahabuddin, P., and Zajic, T. 1999. Multilevel splitting for estimating rare event probabilities. Oper. Res. 47, 4, 585--600.
[23]
Glynn, P. W. and Iglehart, D. L. 1989. Importance sampling for stochastic simulations. Manag. Sci. 35, 1367--1392.
[24]
Glynn, P. W. and Whitt, W. 1992. The asymptotic efficiency of simulation estimators. Oper. Res. 40, 505--520.
[25]
Goyal, A., Shahabuddin, P., Heidelberger, P., Nicola, V. F., and Glynn, P. W. 1992. A unified framework for simulating Markovian models of highly reliable systems. IEEE Trans. Comput. C-41, 36--51.
[26]
Hammersley, J. M. and Handscomb, D. C. 1964. Monte Carlo Methods. Methuen, London.
[27]
Heidelberger, P. 1995. Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul. 5, 1, 43--85.
[28]
Juneja, S. 2007. Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error. QUESTA 57, 115--127.
[29]
Juneja, S. and Shahabuddin, P. 2006. Rare event simulation techniques: An introduction and recent advances. In Simulation, S. G. Henderson and B. L. Nelson Eds., Handbooks in Operations Research and Management Science. Elsevier, Amsterdam, The Netherlands, 291--350. Chapter 11.
[30]
Kalos, M. H. and Whitlock, P. A. 1986. Monte Carlo Methods. John Wiley and Sons.
[31]
Katz, M. 1963. A note on the Berry-Esseen theorem. Ann. Math. Statist. 34, 1007--1008.
[32]
Kendall, M. and Stuart, A. 1977. The Advanced Theory of Statistics 4th Ed. Vol. 1: Distribution Theory. Macmillan, New York.
[33]
L'Ecuyer, P., Demers, V., and Tuffin, B. 2007. Rare-Events, splitting, and quasi-Monte Carlo. ACM Trans. Model. Comput. Simul. 17, 2, Article 9.
[34]
L'Ecuyer, P. and Tuffin, B. 2008a. Approximate zero-variance simulation. In Proceedings of the Winter Simulation Conference. IEEE Press, 170--181.
[35]
L'Ecuyer, P. and Tuffin, B. 2008b. Approximating zero-variance importance sampling in a reliability setting. Ann. Oper. Res. DOI 10.1007/s10479-009-0532-5.
[36]
Lewis, E. E. and Böhm, F. 1984. Monte Carlo simulation of Markov unreliability models. Nucl. Engin. Des. 77, 49--62.
[37]
Nakayama, M. K. 1996. General conditions for bounded relative error in simulations of highly reliable Markovian systems. Adv. Appl. Probab. 28, 687--727.
[38]
Petrov, V. V. 1995. Limit Theorems in Probability Theory. Oxford University Press, Oxford, UK.
[39]
Sadowsky, J. S. 1993. On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans. Inf. Theory IT-39, 119--128.
[40]
Shahabuddin, P. 1994. Importance sampling for the simulation of highly reliable Markovian systems. Manag. Sci. 40, 3, 333--352.
[41]
Siegmund, D. 1976. Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673--684.
[42]
Tuffin, B. 1999. Bounded normal approximation in simulations of highly reliable Markovian systems. J. Appl. Probab. 36, 4, 974--986.
[43]
Tuffin, B. 2004. On numerical problems in simulations of highly reliable Markovian systems. In Proceedings of the 1st International Conference on Quantitative Evaluation of SysTems (QEST). IEEE CS Press, 156--164.
[44]
Villén-Altamirano, M. and Villén-Altamirano, J. 2006. 2006. On the efficiency of RESTART for multidimensional systems. ACM Trans. Model. Comput. Simul. 16, 3, 251--279.
[45]
Wilks, S. S. 1962. Mathematical Statistics. Wiley, New York.

Cited By

View all
  • (2024)Some Asymptotic Regimes for Quantile EstimationProceedings of the Winter Simulation Conference10.5555/3712729.3712762(407-418)Online publication date: 15-Dec-2024
  • (2024)Adaptive Importance Sampling for Efficient Stochastic Root Finding and Quantile EstimationOperations Research10.1287/opre.2023.248472:6(2612-2630)Online publication date: 1-Nov-2024
  • (2024)Overconservativeness of Variance-Based Efficiency Criteria and Probabilistic Efficiency in Rare-Event SimulationManagement Science10.1287/mnsc.2023.497370:10(6852-6873)Online publication date: 1-Oct-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation
ACM Transactions on Modeling and Computer Simulation  Volume 20, Issue 1
January 2010
145 pages
ISSN:1049-3301
EISSN:1558-1195
DOI:10.1145/1667072
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 February 2010
Accepted: 01 December 2008
Revised: 01 December 2008
Received: 01 August 2007
Published in TOMACS Volume 20, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Rare-event simulation
  2. bounded relative error
  3. importance sampling
  4. logarithmic efficiency
  5. robustness
  6. zero-variance approximation

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)17
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Some Asymptotic Regimes for Quantile EstimationProceedings of the Winter Simulation Conference10.5555/3712729.3712762(407-418)Online publication date: 15-Dec-2024
  • (2024)Adaptive Importance Sampling for Efficient Stochastic Root Finding and Quantile EstimationOperations Research10.1287/opre.2023.248472:6(2612-2630)Online publication date: 1-Nov-2024
  • (2024)Overconservativeness of Variance-Based Efficiency Criteria and Probabilistic Efficiency in Rare-Event SimulationManagement Science10.1287/mnsc.2023.497370:10(6852-6873)Online publication date: 1-Oct-2024
  • (2024)Monte Carlo Methods for Economic CapitalINFORMS Journal on Computing10.1287/ijoc.2021.026136:1(266-284)Online publication date: 1-Jan-2024
  • (2024)Some Asymptotic Regimes for Quantile Estimation2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838783(407-418)Online publication date: 15-Dec-2024
  • (2023)Efficiency of Estimating Functions of Means in Rare-Event ContextsProceedings of the Winter Simulation Conference10.5555/3643142.3643171(351-362)Online publication date: 10-Dec-2023
  • (2023)Efficiency of Estimating Functions of Means in Rare-Event Contexts2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10407217(351-362)Online publication date: 10-Dec-2023
  • (2022)Rare-event Simulation for Neural Network and Random Forest PredictorsACM Transactions on Modeling and Computer Simulation10.1145/351938532:3(1-33)Online publication date: 6-Jul-2022
  • (2022)Truncated Multivariate Student Computations via Exponential TiltingAdvances in Modeling and Simulation10.1007/978-3-031-10193-9_4(65-87)Online publication date: 1-Dec-2022
  • (2022)Array-RQMC to Speed up the Simulation for Estimating the Hitting-Time Distribution to a Rare Set of a Regenerative SystemAdvances in Modeling and Simulation10.1007/978-3-031-10193-9_17(333-351)Online publication date: 1-Dec-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media